EasiND: Effective Neighbor Discovery Algorithms for Asynchronous and Asymmetric-Duty-Cycle Multi-channel Mobile WSNs

详细信息    查看全文

• 作者：Tingpei Huang ; Haiming Chen ; Yuqing Zhang ; Li Cui
• 关键词：Wireless sensor networks ; Neighbor discovery ; Quorum system ; Multi ; channel communications ; Asymmetrical duty ; cycle system
• 刊名：Wireless Personal Communications
• 出版年：2015
• 出版时间：October 2015
• 年：2015
• 卷：84
• 期：4
• 页码：3031-3055
• 全文大小：1,855 KB
• 参考文献：1.Abdelali, D., Theoleyre, F., Bachir, A., & Duda, A. (2010). Neighbor discovery with activity monitoring in multichannel wireless mesh networks. In IEEE wireless communications and networking conference (WCNC) (pp. 1鈥?).
  2.Bakht, M., Carlson, J., Loeb, A., & Kravets, R. (2012). United we find: Enabling mobile devices to cooperate for efficient neighbor discovery. In Proceedings of the ACM workshop on Mobile computing systems & applications (HotMobile) (pp. 1鈥?).
  3.Bian, K., Park, J. M., & Chen, R. (2009). A quorum-based framework for establishing control channels in dynamic spectrum access networks. In Proceedings of the ACM annual international conference on Mobile computing and networking (MobiCom) (pp. 25鈥?6).
  4.Chen, L., Gu, Y., Guo, S., He, T., Shu, Y., Zhang, F., et al. (2012). Group-based discovery in low-duty-cycle mobile sensor networks. In Proceedings of the IEEE communications society conference on sensor, mesh and ad hoc communications and networks (SECON) (pp. 542鈥?50).
  5.Colbourn, C. J., & Dinitz, J. H. (2006). Handbook of combinatorial designs (Vol. 42). Boca Raton: Chapman & Hall/CRC.CrossRef
  6.Cui, L., Liu, Q., & Li, D. (2010). The system framework and equipments of the internet of things. Communications of the China Computer Federation, 6(4), 18鈥?2.
  7.Dutta, P., & Culler, D. (2008). Practical asynchronous neighbor discovery and rendezvous for mobile sensing applications. In Proceedings of the ACM conference on embedded network sensor systems (SenSys) (pp. 71鈥?4).
  8.Ganti, R. K., Ye, F., & Lei, H. (2011). Mobile crowdsensing: Current state and future challenges. IEEE Communications Magazine, 49(11), 32鈥?9.CrossRef
  9.Gonga, A., Charalambous, T., & Johansson, M. (2013). Neighbor discovery in multichannel wireless clique networks: An epidemic approach. In Proceedings of the IEEE 10th international conference on mobile ad-hoc and sensor systems (MASS) (pp. 131鈥?35).
  10.Han, B., & Srinivasan, A. (2012). ediscovery: Energy efficient device discovery for mobile opportunistic communications. In Proceedings of the IEEE international conference on network protocols (ICNP) (pp. 1鈥?0).
  11.Huang, T., Chen, H., Cui, L., & Zhang, Y. (2013). Easind: Neighbor discovery in duty-cycled asynchronous multichannel mobile wsns. International Journal of Distributed Sensor Networks (IJDSN), 2013, 1鈥?5.
  12.Inc., T.I.: 2.4 GHz ieee 802.15.4/zigbee-ready rf transceiver.
  13.Incel, O. D. (2011). A survey on multi-channel communication in wireless sensor networks. Computer Networks, 55(13), 3081鈥?099.CrossRef
  14.Jiang, J. R., Tseng, Y. C., Hsu, C. S., & Lai, T. H. (2005). Quorum-based asynchronous power-saving protocols for ieee 802.11 ad hoc networks. Mobile Networks and Applications, 10(1), 169鈥?81.CrossRef
  15.Kandhalu, A., Lakshmanan, K., & Rajkumar, R. R. (2010). U-connect: A low-latency energy-efficient asynchronous neighbor discovery protocol. In Proceedings of the ACM/IEEE international conference on Information processing in sensor networks (IPSN) (pp. 350鈥?61).
  16.Karowski, N., Viana, A. C., & Wolisz, A. (2011). Optimized asynchronous multi-channel neighbor discovery. In Proceedings of the IEEE annual joint conference on Computer and communications societies (INFOCOM) (pp. 536鈥?40).
  17.Karowski, N., Viana, A. C., & Wolisz, A. (2013). Optimized asynchronous multichannel discovery of ieee 802.15.4-based wireless personal area networks. IEEE Transactions on Mobile Computing, 12(10), 1972鈥?985.CrossRef
  18.Khalili, R., Goeckel, D.L., Towsley, D., & Swami, A. (2010). Neighbor discovery with reception status feedback to transmitters. In Proceedings of the IEEE annual joint conference on computer and communications societies (INFOCOM) (pp. 1鈥?).
  19.Kravets, R., Alkaff, H., Campbell, A., Karahalios, K., & Nahrstedt, K. (2013). Crowdwatch: Enabling in-network crowd-sourcing. In Proceedings of the second ACM SIGCOMM workshop on Mobile cloud computing (pp. 57鈥?2).
  20.Kravets, R. H. (2012). Enabling social interactions off the grid. IEEE Pervasive Computing, 11(2), 8鈥?1.CrossRef
  21.Lai, S., Ravindran, B., & Cho, H. (2010). Heterogenous quorum-based wake-up scheduling in wireless sensor networks. IEEE Transactions on Computers, 59(11), 1562鈥?575.MathSciNet CrossRef
  22.Li, D., & Sinha, P. (2014). Rbtp: Low-power mobile discovery protocol through recursive binary time partitioning. IEEE Transactions on Mobile Computing, 13(2), 263鈥?73.CrossRef
  23.Luk, W. S., & Wong, T. T. (1997). Two new quorum based algorithms for distributed mutual exclusion. In Proceedings of the IEEE international conference on distributed computing systems (ICDCS) (pp. 100鈥?06).
  24.McGlynn, M. J., & Borbash, S. A. (2001). Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks. In Proceedings of the ACM international symposium on mobile ad hoc networking and computing (MobiHoc) (pp. 137鈥?45).
  25.Purohit, A., Priyantha, B., & Liu, J. (2011). Wiflock: Collaborative group discovery and maintenance in mobile sensor networks. In Proceedings of the ACM/IEEE international conference on information processing in sensor networks (IPSN) (pp. 37鈥?8).
  26.Stinson, D. R. (2003). Combinatorial designs: Construction and analysis. Berlin: Springer.
  27.Sun, W., Yang, Z., Wang, K., & Liu, Y. (2014). Hello: A generic flexible protocol for neighbor discovery. In Proceedings of the IEEE annual joint conference on computer and communications societies (INFOCOM) (pp. 1鈥?).
  28.Sun, W., Yang, Z., Zhang, X., & Liu, Y. (2014). Energy-efficient neighbor discovery in mobile ad hoc and wireless sensor networks: A survey. IEEE Communications Survey and Tutorials, 16(3), 1鈥?2.MathSciNet CrossRef
  29.Tseng, Y. C., Hsu, C. S., & Hsieh, T. Y. (2002). Power-saving protocols for ieee 802.11-based multi-hop ad hoc networks. In Proceedings of the IEEE annual joint conference on computer and communications societies (INFOCOM) (pp. 200鈥?09).
  30.Vasudevan, S., Towsley, D., Goeckel, D., & Khalili, R. (2009). Neighbor discovery in wireless networks and the coupon collector鈥檚 problem. In Proceedings of the ACM annual international conference on mobile computing and networking (MobiCom) (pp. 181鈥?92).
  31.Willig, A., Karowski, N., & Hauer, J. H. (2010). Passive discovery of ieee 802.15. 4-based body sensor networks. Ad Hoc Networks, 8(7), 742鈥?54.CrossRef
  32.Zeng, W., Vasudevan, S., Chen, X., Wang, B., Russell, A., & Wei, W. (2011). Neighbor discovery in wireless networks with multipacket reception. In Proceedings of the ACM international symposium on mobile ad hoc networking and computing (MobiHoc) (pp. 3:1鈥?:10).
  33.Zhang, D., He, T., Liu, Y., Gu, Y., Ye, F., Ganti, R. K., et al. (2012). Acc: Generic on-demand accelerations for neighbor discovery in mobile applications. In Proceedings of the ACM conference on embedded network sensor systems (SenSys) (pp. 169鈥?82).
  34.Zheng, R., Hou, J., & Sha, L. (2003). Asynchronous wakeup for ad hoc networks. In Proceedings of the ACM international symposium on mobile ad hoc networking and computing (MobiHoc) (pp. 35鈥?5).
  
• 作者单位：Tingpei Huang (1)
  Haiming Chen (2)
  Yuqing Zhang (1)
  Li Cui (2)
  
  1. No. 19A Yuquan Road, Beijing, 100049, China
  2. No. 6 Kexueyuan South Road Zhongguancun, Haidian District, Beijing, China
  
• 刊物类别：Engineering
• 刊物主题：Electronic and Computer Engineering
  Signal,Image and Speech Processing
  Processor Architectures
  
• 出版者：Springer Netherlands
• ISSN：1572-834X

文摘

Neighbor discovery is a fundamental building block for wireless sensor networks (WSNs), because it is the first step to establish communication links between sensor nodes. Traditional neighbor discovery problems mainly focus on static wireless networks, or networks where all nodes operate on the same frequency. However, the proliferation of mobile devices and multi-channel communications post new challenges to this problem. In this paper, we present an effective neighbor discovery system named EasiND for asynchronous and asymmetrical duty-cycle multi-channel mobile WSNs. Firstly, we propose an optimal synchronous multi-channel neighbor discovery algorithm based on quorum system, which can bound the discovery latency in multi-channel scenario with low power consumption. Secondly, we design an asynchronous neighbor discovery quorum system for multi-channel WSNs. Theoretical analyses demonstrate that EasiND achieves a 33.3 and 50 % reduction in power-latency product when compared to U-Connect and Acc respectively. Thirdly, in order to enable EasiND to be applied to asymmetrical duty-cycle system, we propose an on-demand time slot activation scheme that combines random and cooperative methods together, which effectively reduces discovery latency. Finally, we present a channel scanning acceleration approach based on spatio-frequency characteristics of discovered neighbors, which further decreases discovery latency. We evaluate the performance of EasiND through comprehensive test-bed experiments. Experimental results show that EasiND decreases average discovery latency by up to 84.5 % compared to U-Connect and Acc, and achieves at least 95.6 and 97 % average fraction of discoveries in a predefined time limitation under 12 and 3 % duty-cycles. Keywords Wireless sensor networks Neighbor discovery Quorum system Multi-channel communications Asymmetrical duty-cycle system