[Speaker]: Alex Cornejo (MIT)
[Title]: Neighbor Discovery in Mobile Ad-Hoc Networks
[Date]: Oct. 30th (Fri)
[Time]: 1PM - 2:30PM
[Place]: Bldg. 32 (Stata), G631

[Abstract]:
We study the neighbor discovery problem in mobile ad-hoc networks, informally
a neighbor discovery layer provides each node with a time-varying set of nodes
that reflect the existing links in the underlying communication graph.

Knowledge of neighboring nodes is often assumed by distributed algorithms,
nonetheless it is rarely provided directly by the MAC layer. We take
advantage of
the reliability and time bounds provided by the Abstract MAC Layer [1]
to implement
an efficient neighbor discovery protocol.

We characterize the neighbor discovery problem in terms of safety,
synchronization
and progress properties. In particular we focus on the region-based variant of
neighbor discovery, where the safety, synchronization and progress
conditions are
stated for nodes which are in regions which are k-hops away.

In this talk I will describe the algorithm and correctness proof of a neighbor
discovery protocol for k=0, and cover some work in progress towards arbitrary k
neighbor discovery. If time permits I will discuss the inherent
relationship between
the speed of motion, the granularity of regions and the communication complexity
of the protocol.


Joint work with Nancy Lynch, Saira Viqar and Jennifer Welch.