# A Practical Neighbor Discovery Framework for Wireless Sensor Networks
## 2 Related Works  
The neighbor discovery problem in WSNs has been widely studied and the goal is to reduce the duty cycle or to reduce the latency of discovering the neighboring nodes. Generally speaking, there are two categories of neighbor discovery algorithms.  
One category is _probability algorithms_, which utilize randomness to discover the neighbors in a short expected time. _Birthday protocol_[20] is one of the earliest algorithms that works on the _birthday paradox_, i.e., the probability that two people have the same birthday exceeds \(\frac{1}{2}\) among 23 people. In the birthday protocol, each node transmits with probability \(p\in[0,1]\) and listens on the channel with probability \(1-p\) in each time slot independently; this protocol ensures that the nodes can discover the neighbors with high probability, but it cannot deduce a bounded discovery time. Aloha-like protocol [28] assumes each node is awake in each slot with probability \(p_{w}\) and an awake node transmits with probability \(p_{t}\) and listens with probability \(p_{t}\); one can derive the expected time to discover all neighbors with this protocol, but cannot guarantee successful discovery for the worst case situation. Following that, more smarter probabilistic algorithms were proposed [25; 27; 29], but they cannot guarantee an upper bound on the discovery latency among the nodes.  
The other category is _deterministic algorithms_, which adopt some mathematic tools to ensure discovery between every two neighbors. The first tool is called _quorum system_: for any two intersected quorums, two neighboring nodes could choose any quorum in the system to design the discovery schedule and the discovery latency can be bounded in a short time. Many algorithms are related to the quorum system [15; 17; 18; 19; 30], but only a few of them support asymmetric duty cycles of the nodes, such as Hedis [15]. Another important tool is _co-primality_ where two co-prime numbers are chosen by the neighbors to design the discovery schedule, and they can discover each other within a bounded latency by the Chinese Remainder Theorem [32]. Some representative algorithms are Disco [16], U-Connect [18], and Todis [15].  
In short, probabilistic algorithms cannot guarantee two neighboring nodes discover each other in a finite time, but they assure that the discovery can be successful with a high probability in an expected discovery time. In contrast, deterministic algorithms can ensure the discovery process between the nodes, and they can limit the maximum discovery latency to within a bounded time.  
Many neighbor discovery protocols assume that time is divided into slots of equal length and the nodes have aligned slots. Some works also study a general scenario that the slots are aligned between the users. They use _probe_, _beacon_ or _anchor_ to design the discovery protocols, and the representative algorithms are Searchlight [13], Hello [22] and Nihao [21]. There are also some other neighbor discovery protocols that are based on different techniques, such as combinatorial design [33], BlindDate [26], and Panda [12], the details of which we omit here. Among these algorithms, some of them only support _symmetric duty cycle_ (the nodes select the same duty cycle), such as Quorum and BalancedNihao [21], while others support asymmetric duty cycles (nodes select different duty cycles), such as Disco, U-Connect, Searchlight [13], Hello [22], Hedis and Todis [15].  
To the best of our knowledge, most deterministic neighbor discovery algorithms are designed for two neighbors, with symmetric or asymmetric duty cycles. A few of them consider the energy management of each node and they ignore the communication collisions when they are extended for multiple nodes. Therefore, we propose a practical framework incorporating these issues and enable the existing deterministic protocols to be applicable for networks with multiple nodes.