Energy-Efficient Neighbor Discovery for the Internet of Things

Internet of Things (IoT) networks are usually distributed in nature. Due to the possible mobility of IoT devices, it is common and critical for each IoT device to keep discovering who is in its neighborhood, referred to as neighbor discovery. Due to the limited battery capacity of IoT devices, it is challenging to design a neighbor discovery protocol (NDP) that can achieve both low duty cycle and low discovery latency. In this article, we build a model called Circle to characterize the process of neighbor discovery in IoT networks. Then, we give a necessary and sufficient condition for neighbor discovery and theoretically prove its correctness. This is the first time in the research community that a necessary and sufficient condition is given for neighbor discovery. According to the necessary and sufficient condition, we analytically derive a lower bound of the worst case discovery latency and demonstrate when the lower bound can be achieved. The analytical model is generic as it can be used to analyze existing NDPs. Based on the Circle model and the analysis, we propose an NDP, which is also called Circle. We compare Circle with the state-of-the-art NDPs in a real testbed, and experimental results show that Circle is superior to the existing state-of-the-art NDPs.