Neighbor discovery is a fundamental service for initialization and managing network dynamics in wireless sensor networks and mobile sensing applications. In this paper, we present a novel design principle named Talk More Listen Less (TMLL) to reduce idle-listening in neighbor discovery protocols by learning the fact that more beacons lead to fewer wakeups. We propose an extended neighbor discovery model for analyzing wakeup schedules in which beacons are not necessarily placed in the wakeup slots. Furthermore, we are the first to consider channel occupancy rate in discovery protocols by introducing a new metric to trade off among duty-cycle, latency and channel occupancy rate. Guided by the TMLL principle, we have designed Nihao, a family of energy-efficient asynchronous neighbor discovery protocols for symmetric and asymmetric cases. We compared Nihao with existing state of the art protocols via analysis and real-world testbed experiments. The result shows that Nihao significantly outperforms the others both in theory and practice.
Asymmetric neighbor discovery is proposed for cases that duty-cycle requirements are different. Lai extend Quorum to support the asymmetric case of two independent duty-cycles. Disco @cite_15 utilizes the Chinese Remainder Theorem to guarantee discovery between two nodes with different duty-cycles. U-Connect and Hello employ similar coprime approach for asymmetric cases. SearchLight and BlindDate adopt another power-multiple approach with a poor duty-cycle granularity. Hedis and Todis @cite_10 present wakeup schedules with better duty-cycle granularities for asymmetric cases. Our design supports asymmetric cases with the same duty-cycle granularity as Todis and Hedis, but has a better performance on latency.
@cite_15 @cite_10
1524689014 2072679814 1964981474 1978599484
Neighbor discovery plays a crucial role in the formation of wireless sensor networks and mobile networks where the power of sensors (or mobile devices) is constrained. Due to the difficulty of clock synchronization, many asynchronous protocols based on wake-up scheduling have been developed over the years in order to enable timely neighbor discovery between neighboring sensors while saving energy. However, existing protocols are not fine-grained enough to support all heterogeneous battery duty cycles, which can lead to a more rapid deterioration of long-term battery health for those without support. Existing research can be broadly divided into two categories according to their neighbor-discovery techniques — the quorum based protocols and the co-primality based protocols. In this paper, we propose two neighbor discovery protocols, called Hedis and Todis, that optimize the duty cycle granularity of quorum and co-primality based protocols respectively, by enabling the finest-grained control of heterogeneous duty cycles. We compare the two optimal protocols via analytical and simulation results, which show that although the optimal co-primality based protocol (Todis) is simpler in its design, the optimal quorum based protocol (Hedis) has a better performance since it has a lower relative error rate and smaller discovery delay, while still allowing the sensor nodes to wake up at a more infrequent rate. Neighbor discovery is crucial for both wireless sensor networks and mobile computing applications. The crux of the problem is to achieve energy efficiency, which has been demonstrated to be difficult by prior work. In this paper we propose Hello, a generic flexible protocol for neighbor discovery. With an unrestricted parameter, it serves as a generic framework that incorporates existing deterministic protocols. Under the framework, we expose optimal parameters for either symmetric or asymmetric duty cycles, which is the first to our knowledge. As a result, it exhibits great flexibility by adjusting itself to any configuration that best meets application demands. Besides, several techniques are applied to removing redundant discoveries without sacrificing the worst-case latency. We evaluate Hello through extensive simulation and real-world sensor experiments. The results show that Hello is highly energy-efficient under symmetric and asymmetric duty cycles. In particular, it is two times better than the state of the art in terms of the worst-case latency under asymmetric duty cycles. Many wireless applications urgently demand an efficient neighbor discovery protocol to build up bridges connecting user themselves or to some service providers. 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. First, we study Asynchronous Symmetry Neighbor Discovery problem, in which potential neighbor devices with asynchronous time clocks but the same duty cycle aim to find each other. Second, we propose an efficient protocol (utilizing Bouncing strategy) named BlindDate with guaranteed worst-case performance @math where @math is a small fraction of the length of a time slot unit and @math is the duty cycle. Third, we extend this strategy to address Asynchronous Asymmetry Neighbor Discovery problem, in which both the time clock and the duty cycles of potential neighbors are considered to be heterogeneous. We conduct extensive experiments and simulations to examine the feasibility and efficiency of the proposed protocols, and results show that BlindDate greatly outperforms existing approaches in average-case. Compared with known protocols, BlindDate also achieves a better worst-case discovery latency bound (e.g., @math percent performance gain comparing with Searchlight [1] ). Neighbor discovery is a fundamental problem in wireless networks. In this paper, we study asynchronous neighbor discovery between duty-cycled mobile devices. Each node is duty-cycled, i.e., its radio may only be active for a small fraction of the time. The duty cycles of the nodes can be the same or different, leading to symmetric or asymmetric cases of the neighbor discovery problem. In addition, the setting is asynchronous, i.e., clocks of different nodes may not be synchronized. Most existing studies assume an integer model (where time proceeds in discrete steps); two recent studies break away from this assumption, which allows them to develop significantly more efficient schemes. Our study improves the state-of-the-art in three main fronts. Firstly, we develop a generalized non-integer model (where time is continuous) that permits unified treatment of the assumptions in existing studies. We also provide a reduction that transforms any schedule in the basic integer model to a corresponding schedule in the generalized non-integer model while improving the performance by a factor of two. Applying this reduction, an optimal schedule in the integer model becomes an optimal schedule in the non-integer model. Thirdly, we establish a new family of lower bounds for the best achievable latency guarantee in the non-integer model. They are applicable to both symmetric and asymmetric settings, and encompass the lower bounds for the integer model as special cases. Finally, we develop a novel optimal construction based on Sidon sets for the symmetric setting. Our approach differs from the approaches taken by all existing studies, and provides a new direction for constructing neighbor discovery schedules.