Title: Efficient Algorithms for Neighbor Discovery in Wireless Networks
Speaker: Sudarshan Vasudevan, Bell Labs
Date: Monday, March 7, 2011 12:00 - 1:00 pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Neighbor discovery is an important first step in the initialization of a wireless ad hoc network. Neighbor discovery algorithms need to cope with numerous practical challenges such as no a priori estimate of number of neighbors and lack of synchronization between nodes. Furthermore, nodes may start execution at different time instants and also need to determine when to terminate neighbor discovery. In this talk, I will present several neighbor discovery algorithms that address these challenges. Starting with the setting of a single-hop wireless network of n nodes, we propose a Theta(n log n) ALOHA-like neighbor discovery algorithm when nodes cannot detect collisions, and an order-optimal Theta(n) receiver feedback-based algorithm when nodes can detect collisions. We then show that receiver feedback can be used to achieve a Theta(n) running time, even when nodes cannot detect collisions. In the general multi-hop network setting, we establish an O(Delta log n) upper bound on the running time of the ALOHA-like algorithm, where Delta denotes the maximum node degree in the network. We also establish an Omega( Delta + log |E|) lower bound on the running time of any randomized neighbor discovery algorithm, where |E| denotes the total number of edges in the network. Our result thus implies that when |E| = Omega(n), the ALOHA-like algorithm is at most a factor min(Delta,log n) worse than the optimal.