# A Practical Neighbor Discovery Framework for Wireless Sensor Networks
## 4 Spear: Neighbor Discovery Framework
### Energy Module  
The energy module receives the remaining energy and the latency constraints from the application module as inputs. The output is the duty cycle which the node is to adopt. Two main functions are incorporated into the energy module: _computing the node's lifetime_ and _adjusting the duty cycle_.  
For any node \(u_{i}\) which starts at time \(t_{i}^{s}\), suppose the generated schedule is \(S_{i}=\{s_{i}(t)|t\geq t_{i}^{s}\}\) and it runs out of energy at time \(t_{i}^{e}\). We have the following equation:  
\[\int_{t_{i}^{e}}^{t_{i}^{e}}s_{i}(t)\cdot p_{n}=P_{max}. \tag{3}\]  
Then, the lifetime of node \(u_{i}\) (denoted as \(Lf_{i}\)) is \(Lf_{i}=t_{i}^{e}-t_{i}^{s}\).  
Notice that we assume a sensor node has only two states \(\{ON,OFF\}\) in Section 3.1. The generated schedule \(S_{i}=\{s_{i}(t)\}\) contains a sensor state of each time slot \(t\); specifically, \(s_{i}(t)=0\) if the state of the node is \(OFF\) while \(s_{i}(t)=1\) is the state of the node is \(ON\). We define two identification functions as \(f_{n2f}(t)=1\) if and only if \(s_{i}(t-1)=1,s_{i}(t)=0,f_{f2n}(t)=1\) if and only if \(s_{i}(t-1)=0,s_{i}(t)=1\). The first one implies that the node switches its state from \(ON\) to \(OFF\), while the other one implies that the node switches its state from \(OFF\) to \(ON\). Combining these, a complete energy formulation should be  
\[\int_{t_{i}^{e}}^{t_{i}^{e}}s_{i}(t)\cdot p_{n}+(1-s_{i}(t))\cdot p_{f}+f_{n2f }(t)\cdot p_{nf}+f_{f2n}(t)\cdot p_{fn}=P_{max}.\]  
Since we assume the consumed energy of state \(OFF\) and switching states are zero, i.e., \(p_{f}=p_{nf}=p_{fn}=0\), we derive the simplified formulation as Equation (3).  
If node \(u_{i}\) turns the radio on all the time, Equation (3) can be rewritten as:  
\[(t_{i}^{e}-t_{i}^{s})\cdot p_{n}=P_{max}\]  
Figure 3: Overview of Spear.  
and the lifetime is \(Lf_{i}=\frac{P_{max}}{p_{n}}\), which is the minimum value.  
To extend the lifetime, node \(u_{i}\) turns on the radio for a fraction of the time. If node \(u_{i}\) selects the duty cycle as a fixed value \(\hat{\theta}\in(0,1)\), we can rewrite Equation (3) as:  
\[(t_{i}^{e}-t_{i}^{s})\cdot\hat{\theta}\cdot p_{n}+(t_{i}^{e}-t_{i}^{s})\cdot(1 -\hat{\theta})\cdot p_{f}\approx P_{max}.\]  
We use '\(\approx\)' since the schedule may not be a complete cycle, but it makes very little difference, and we can just regard it as '\(=\)'. As we assume \(p_{f}=0\), the lifetime of node \(u_{i}\) is computed as:  
\[Lf_{i}=\frac{P_{max}}{p_{n}\cdot\hat{\theta}}. \tag{4}\]  
Suppose that node \(u_{i}\) adjusts the duty cycle timely. Denote the time that \(u_{i}\) changes the duty cycle as: \(T_{0}<T_{1}<\ldots<T_{m}\), where \(T_{0}=t_{i}^{s}\) and \(T_{m}<t_{i}^{e}\). For simplicity, denote \(T_{m+1}=t_{i}^{e}\) and Equation (3) is rewritten as:  
\[\begin{array}{ll}&\sum_{k=0}^{m}(\int_{T_{k}}^{T_{k+1}}s_{i}(t)\cdot p_{n} )=P_{max}\\ \Rightarrow&\sum_{k=0}^{m}(T_{k+1}-T_{k})\cdot\theta_{i}(T_{k},T_{k+1})\cdot p _{n}=P_{max}.\end{array}\]  
Since \(\theta_{i}(T_{k},T_{k+1})\) and \(T_{i},i\in[0,m]\) are known beforehand, \(t_{i}^{e}=T_{m+1}\) is computed as:  
\[t_{i}^{e}=\frac{\frac{P_{max}}{p_{n}}-\sum_{k=0}^{m-1}(T_{k+1}-T_{k})\cdot \theta_{i}(T_{k},T_{k+1})}{\theta_{i}(T_{m},T_{m+1})}+T_{m}. \tag{5}\]  
Then, the lifetime can be computed. In Section 5, we analyze the impact of the node's lifetime by different strategies that adjust the duty cycles.