# A Practical Neighbor Discovery Framework for Wireless Sensor Networks
## 1 Introduction  
With the ascent of Internet-of-Things (IoT) [1; 2; 3; 4; 5; 6; 7], wireless sensor networks (WSNs) are increasingly being adopted for tracking and monitoring applications in various areas such as health-caring, smart buildings, agricultural management and assisted living [8; 9; 10]. For example, WSN has been deployed for agriculture information monitoring [11], and sensors can be attached to inventory items in a large warehouse for object identification [12]. As a crucial process in constructing a wireless network, _neighbor discovery_, where sensor nodes try to find the existence of neighboring nodes within their communication range, has drawn much attention in the last decade or so [12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27]. Sensor nodes are powered by batteries. To minimize the overall energy consumption, most existing work focuses on designing discovery schedules that maintain a low _duty cycle_. However, despite decades of efforts, designing practical neighbor discovery protocols for real-life WSNs remains a big challenge, especially when considering all three critical factors as pointed out by previous works:1. Collisions happen when multiple nodes transmit on the same communication channel simultaneously. 2. Bounded latency is required for time-sensitive applications. For example, object detection applications require discovering the neighbors for transmitting emergent information with very low latency. 3. Prolonged lifetime of sensor nodes. In order to reduce the energy consumption and prolong the lifetime of sensor nodes, affective energy management methods that can dynamically adjust nodes' duty cycles during the discovery process are crucial. Neglecting all these practical concerns, sensor nodes will likely fail to discover all neighbors before running out of energy. Unfortunately, no existing work has considered all of the above-mentioned concerns in one setting. Typically, only one factor is considered at a time. Among all solutions, two major types of protocols exist: probability-based and deterministic ones. Probability-based protocols turn on the radio with different probabilities to reduce communication collisions [20; 25; 27; 28; 29], but the discovery latency often varies significantly. Compared to probability-based protocols, deterministic protocols are much more popular in practice. This approach is also the main focus of this paper because with a deterministic discovery schedule the discovery latency is mostly stable [12; 13; 15; 16; 18; 21; 22; 26; 30; 31]. However, existing deterministic protocols mainly target at only two neighbors, where collision often does not occur. As shown in Figure 1, when these (bare) deterministic protocols (Hedis [15], Hello [22], Searchlight [13], and U-Connect [18]) are adopted in a network of 1000 nodes, the discovery rates are only 33.0-65.9% because of collisions. In this paper, we propose **S****pear** (Speer is a general, powerful ancient weapon), a practical neighbor discovery framework that deals with all the critical factors mentioned above. The advantages of **S****pear** are:  
1. [label=()]
2. **S****pear creates two new methods, Pure Probability Reducing (PPR) and Decreased Probability Reducing (DPR), to reduce communication collisions among multiple nodes. Running in **S****pear**, a deterministic protocol targeting at two neighbors can be automatically extended to support multiple nodes, while still keeping a stable discovery latency;
3. **S****pear** introduces two methods to manage energy and one unified method to handle latency constraints; it prolongs the node's lifetime and enhances the availability for various applications;
4. **S****pear enables the quantitative analysis of various neighbor discovery protocols, and generates the optimal neighbor discovery schedule automatically. Figure 1: Spear greatly improves discovery rates for four notable protocols. Discovery rate for each protocol is defined as the number of discovered neighbors divided by all actual neighbors.