Searchlight: Helping mobile devices find their neighbors

The rapid deployment of millions of handheld communication devices has resulted in a demand for physical proximity-based opportunistic networking. However, the success of these emerging ad hoc networks requires that a device should be able to search and find other devices in its vicinity without infrastructure support, without consuming too much battery power, and preferably without requiring clock synchronization. While approaches exist to solve this problem of energy-efficient asynchronous neighbor discovery, they present an unpleasant trade-off between good average-case performance (probabilistic approaches) and strict bound on worst case discovery latency (deterministic approaches). In response to these limitations, we present Searchlight, an asynchronous neighbor discovery protocol that has both deterministic and probabilistic components, a novel combination that enables it to have both good average-case performance and the best worst-case bound for any given energy budget.