Author : T.Shilpa 1
Date of Publication :7th March 2016
Abstract: Neighbor discovery is an important first step in the initialization of a wireless ad hoc network. In this paper, we design and analyze several algorithms for neighbor discovery in wireless networks. Starting with a single-hop wireless network of nodes, we propose a ALOHA-like neighbor discovery algorithm when nodes cannot detect collisions, and an order-optimal receiver feedback-based algorithm when nodes can detect collisions. Our algorithms neither require nodes to have a priori estimates of the number of neighbors nor synchronization between nodes. Our algorithms allow nodes to begin execution at different time instants and to terminate neighbor discovery upon discovering all their neighbors. We finally show that receiver feedback can be used to achieve a running time, even when nodes cannot detect collisions. We then analyze neighbor discovery in a general multihop setting. We establish an upper bound of on the running time of the ALOHA-like algorithm, where denotes the maximum node degree in the network and the total number of nodes. We also establish a lower bound of on the running time of any randomized neighbor discovery algorithm. Our result thus implies that the ALOHA-like algorithm is at most a factor worse than optimal.
Reference :
-
- R. Madan and S. Lall, “An energy-optimal algorithm for neighbor discovery in wireless sensor networks,” In proc of Mobile Networks and Applications, ACM, pp. 317–326, 2006
- Dutta and Culler, “Practical Asynchronous Neighbor Discovery and Rendezvous for Mobile Sensing Applications”, In Proceedings of the 6th ACM conference on Embedded network sensor systems, SenSys ‟08, 2008
- Valerie Galluzzi and Ted Herman”, Survey: Discovery in Wireless Sensor Networks”, International Journal of Distributed Sensor Networks, Volume 2012 (2012), Article ID 271860
- E. B. Hamida, G. Chelius, and E. Fleury, “Revisiting n e i g h b o r discovery with interferences consideration,” In Proceedings of 3rd ACM international workshop on Performance Evaluation of Wireless Ad hoc, Sensor and Ubiquitous Networks (PEWASUN 2006), pp. 74–81, 2006
- V. C. Giruka and M. Singhal. “Hello protocols for adhoc networks: Overhead and accuracy tradeoffs” , In proceedings of Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks (WoWMoM‟05), 2005.
- I. D. Chakeres and E. M. Belding-Royer,” The utility of hello messages for determining link connectivity”, In Proceedings of the 5th International Symposium on Wireless Personal Multimedia Communications (WPMC ‟02), 2002.
- S. R. Biradar, Koushik Majumder, Subir Kumar Sarka and Puttamadappa C,” Performance Evaluation and Comparison of AODV and AOMDV”, In International Journal on Computer Science and Engineering Vol. 02, pp. 373-377, 2010
- S. Mehta and K.S. Kwak, “H-MAC, A Hybrid MAC protocol for Wireless Sensor Networks”, In International journal of Computer Networks and Communications, Vol 2, 2010
- Heping Wang, Xiaobo Zhang, Farid Naït-Abdesselam, and Ashfaq Khokhar, “Cross-Layer Optimized MAC to Support Multihop QoS Routing for Wireless Sensor Networks”, In IEEE Transactions on Vehicular