Show icon Show search tips...
Hide icon Hide search tips...

[CCICADA-announce] DIMACS/CCICADA Interdisciplinary Seminar Series- Monday, March 7, 2011

Linda Casals lindac at
Mon Mar 7 08:53:05 EST 2011

DIMACS/CCICADA Interdisciplinary Seminar Series Presents
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


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.

See: <a href=>
DIMACS/CCICADA Interdisciplinary Series, Spring 2011</a>

More information about the Dimacs-ccicada-announce mailing list