### Interdisciplinary Seminar Series

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.

DIMACS/CCICADA Interdisciplinary Series, Spring 2011