# A Practical Neighbor Discovery Framework for Wireless Sensor Networks
## 3 Preliminaries
### Neighbor Discovery  
Neighbor discovery is the foundation of constructing WSNs. When the sensor nodes are deployed in the monitoring area, each node can only know its local information; the nodes have to find their neighboring nodes, and then the network can be established.  
Suppose node \(u_{i}\) starts at time \(t_{i}^{s}\) and it tries to discover its neighbors by turning on the radio. In order to save energy, the node runs some pre-defined algorithms to generate a discovery schedule \(S_{i}=\{s_{i}(t)|t\geq t_{i}^{s}\}\), where:  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Description** \\ \hline \(u_{i}\) & Sensor node \(u_{i}\) \\ \(l_{i}\) & Identifier of node \(u_{i}\) \\ \(P_{max}\) & The maximum energy of each sensor \\ \(P_{i}(t)\) & The remaining energy of \(u_{i}\) at time \(t\) \\ \(t_{0}\) & The length of each time slot \\ \(p_{n}\) & The consumed energy to turn on the radio in each slot \\ \(d_{c}\) & Communication range of each sensor \\ \(t_{i}^{s}\) & Start time of node \(u_{i}\) \\ \(S_{i}\) & Neighbor discovery schedule of node \(u_{i}\) \\ \(s_{i}(t)\) & The schedule of node \(u_{i}\) at time \(t\) \\ \(L(i,j)\) & Discovery latency between \(u_{i}\), \(u_{j}\) \\ \(N_{i}\) & The set of neighbors of node \(u_{i}\) \\ \(L(i,N_{i})\) & The latency for \(u_{i}\) to discover all neighbors \\ \(\theta_{i}(T_{1},T_{2})\) & Node \(u_{i}\)’s duty cycle between time \([T_{1},T_{2}]\) \\ \(t_{i}^{e}\) & The time node \(u_{i}\) runs out of energy \\ \(Lf_{i}\) & Lifetime of node \(u_{i}\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Notations for Neighbor Discovery.  
\[s_{i}(t)=\left\{\begin{array}{ll}0,&\text{if $u_{i}$ turns the radio $OFF$,}\\ 1,&\text{if $u_{i}$ turns the radio $ON$.}\end{array}\right.\]  
The **neighbor discovery** problem between two neighboring nodes is defined as:  
**Problem 1**.: _For two neighboring nodes \(u_{i}\) and \(u_{j}\), design the discovery schedules \(S_{i},S_{j}\) respectively such that there exists \(T\) satisfying:_  
\[s_{i}(T)=s_{j}(T)=1.\]  
Two nodes may start at different times, which is referred to as the _asynchronous_ case in the literature, and the _discovery latency_ is defined as:  
**Definition 1**.: _The discovery latency between two neighboring nodes \(u_{i}\) and \(u_{j}\) is the time cost to turn on the radio simultaneously after they both have started:_  
\[L(i,j)=T-\max\{t_{i}^{\text{s}},t_{j}^{\text{s}}\}. \tag{1}\]  
Considering the network with multiple nodes, the neighbor discovery problem for node \(u_{i}\) is defined as:  
**Problem 2**.: _For each node \(u_{i}\), denote the set of neighboring nodes as \(N_{i}=\{u_{j}|d(u_{i},u_{j})\leq d_{c}\}\). Design the discovery schedule for each node, such that there exists \(T_{i,j}\) satisfying:_  
\[\left\{\begin{array}{ll}s_{i}(T_{i,j})=s_{j}(T_{i,j})=1,\\ s_{k}(T_{i,j})=0,\forall u_{k}\in N_{i},u_{k}\
eq u_{j}.\end{array}\right.\]  
Similarly, the _discovery latency_ for node \(u_{i}\) is defined as:  
**Definition 2**.: _The discovery latency for node \(u_{i}\) is the time cost to find all neighbors:_  
\[L(i,N_{i})=\max_{u_{k}\in N_{i}}T_{i,k}-t_{i}^{\text{s}}. \tag{2}\]  
Most neighbor discovery algorithms generate their discovery schedules with regard to the _duty cycle_ which is defined as:  
**Definition 3**.: _The duty cycle of node \(u_{i}\) between time \(T_{1},T_{2}\) (\(T_{1}<T_{2}\)) is the percentage of time slots when \(u_{i}\) turns on the radio:_  
\[\theta_{i}(T_{1},T_{2})=\frac{|\{s_{i}(t)=1|T_{1}\leq t\leq T_{2}\}|}{T_{2}-T _{1}}.\]  
The existing deterministic algorithms try to minimize the discovery latency between two neighbors for pre-defined duty cycles. Both symmetric and asymmetric duty cycles should be considered.