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.
Existing asynchronous neighbor discovery protocols can be roughly divided into two categories: probabilistic and deterministic @cite_18 . Birthday @cite_14 is a probabilistic neighbor discovery protocol using random independent transmissions to find neighbors. Each time slot randomly chooses one state among listen, transmit and idle with probabilities which is determined by the required duty-cycle. Although Birthday protocol has an excellent performance on average discovery latency thanks to its probabilistic nature, it exhibits a long tail for discovering the last few neighbors, and the worst-case latency is unbounded.
@cite_18 @cite_14
2057467539 2078612414
Due to slow advance in battery technology, power remains a bottleneck to limit wide applications of mobile ad hoc and wireless sensor networks. Among all extensive studies on minimizing power consumption, neighbor discovery is one of the fundamental components focusing on communication and access. This work surveys research literature on neighbor discovery protocols (NDPs). In general, they can be roughly classified by four underlying principles: randomness, over-half occupation, rotation-resistant intersection, and coprime cycles. The Birthday protocols act as representatives of NDPs using randomness, in which a node decides to listen, transmit, or sleep with probabilities. The original idea of over-half occupation is to be active over at least half of each period, though several refinements have been proposed to decrease its high duty cycle. Methods of rotation-resistant intersection formulate the problem of discovery using combinatorial characteristics of discrete time slots, and guarantee discovery at least once per period. Moreover, neighbor discovery can also be guaranteed within a worst-case bound, as shown by methods adopting coprime cycles. In this paper, we elaborate on these ideas and present several representative protocols, respectively. In particular, we give an integrative analysis of deterministic protocols via a generic framework. A qualitative comparison incorporating multiple criteria and a quantitative evaluation on energy efficiency are also included. Finally, we point out promising research directions towards energy-efficient neighbor discovery. In this paper, we address two problems associated with static ad hoc wireless networks; methods of saving energy during a deployment of the nodes, and efficient methods of performing adjacent neighbor discovery. To meet these goals we introduce a family of "birthday protocols"which use random independent transmissions to discover adjacent nodes. Various modes of the birthday protocol are used to solve the two problems. We provide a mathematical model and analysis of two modes of the protocol and are led to a third mode which is the probabilistic analog of the deterministic round robin scheduling algorithm. We show by analysis and simulation that the birthday protocols are a promising tool for saving energy during the deployment of an ad hoc network as well as an efficient and flexible means of having the nodes discover their neighbors