BlindDate: A Neighbor Discovery Protocol

Many wireless applications urgently demand an efficient neighbor discovery protocol to build up a bridge connecting users to service providers or to other users. However, due to intrinsic constraints of wireless devices, e.g., limited energy and error of clock synchronization, there is still absence of effective and efficient neighbor discovery protocols in the literature. In this work, we propose neighbor discovery protocols for the following two problems. We first study Asynchronous Symmetry Neighbor Discovery problem, in which potential neighbor devices with asynchronous time clock but the same duty cycle aim to find each other. We further propose an efficient protocol (using Bouncing strategy) named Blind Date with guaranteed worst-case performance 9/10(1 + δ)²x² where δ is a small fraction of the length of time slot unit and 1/x is the duty cycle. Next, we extend this design to address Asynchronous Asymmetry Neighbor Discovery problem, in which both time clock and the duty cycles of potential neighbors are considered to be heterogeneous. We conduct extensive simulations to examine the feasibility and efficiency of the proposed protocols. Results show that Blind Date protocol outperforms existing approaches in average-case. We conclude that, compared with known protocols, Blind Date achieves a better worst-case discovery latency bound (e.g., 10% performance gain comparing with Searchlight [1]).