## 4 Protocol Description
### Routing Mechanism Details
(2) If \(p=p_{max}\); in this case, it finds the new neighbor as a forwarding choice by the height and delay estimate in a priority from \"_safe_\", \"_lowsafe_\" to \"_infire_\"; otherwise, no eligible new neighbor can be found. In the new neighbor discovery, sensor \(i\) will broadcast out a Routing Request (RTR) message. In this process, sensor \(i\) piggybacks _height_, _slack_ and the newly adapted power _p1_ in RTR message. For a node \(j\) that hears the message, if the estimated end-to-end delay is no more than _slack_ and its height is lower than _height_(_i_, _sink_), as well as its state is \"_safe_\", then \(j\) is selected as a new neighbor. If sensor \(j\) hears the RTR with \(p_{max}\), and if its height is lower than _height_ (_i_, _sink_), then \(j\) is selected a new neighbor when \(j\) is not in \"_unsafe_\" state. The new neighbor will reply to node \(i\) with the same power  
Figure 2: New neighbor discovery to solve routing “hole”  
that node \(i\) is using, after a random backoff to avoid collisions. The forwarding choices send reply message with \(p_{i}\) only as necessary for reaching node \(i\), otherwise reverting to their previous power level. Upon receiving the reply, node \(i\) inserts the new neighbors into its neighbor table. During RTR and reply message exchange, we could calculate the delay between \(i\) and its new neighbor \(j\) as follows:  
\[\mathit{Ave\_delay}(i,j)=\mathit{{}_{Round\_trip\_time}/2} \tag{3}\]  
For meeting real-time requirements, the forwarding choices should satisfy that: \"_slack_\" is no less t than the average delay between \(i\) and \(j\) plus the delay estimate at node \(j\), _i.e.,_  
\[\mathit{slack}(i)\geqslant\mathit{{}_{Ave\_delay}(i,j)+delay(sink,j)} \tag{4}\]  
If there is more than one new neighbor found, a best forwarding node is selected by the priority of state from \"_safe_\", \"_lowsafe_\" to \"_infire_\". If there is still a tie, the best relay is selected by the node with higher residual energy and lower ID number. For a node that works in a larger transmission range could still be adapted to decrease the transmission power to improve energy efficiency and network capacity, while delay deadline is loose. So we define when a node detects a good connectivity with safe neighborhood that is larger than a predefined threshold, _i.e., \(|\mathit{Neighbor_{safe}}|>N\_threshold\)_, power decreases is invoked. We defined a function to find appropriate transmission range by decreasing transmission power as follows:  
\[p=p\mathit{{}_{Round\_trip}}=1, \tag{5}\]  
In formula (5), _cur_ is the current number of transmission power level among \(k\) levels. \(\mathit{t}^{\prime}\) is the count of decrement. A node is eligible for power decrease until:  
(1) The minimum power has been reached. (2) There are two consecutive power levels such that at the lower level the required delay is not met but at the higher power level the required delay is met. (3) There are two consecutive power levels such that at the lower level the required safe neighborhood connectivity \(N\_threshold\) is not met but at the higher power level it is. _Neighbored Table Management_:  
The neighborhood table records information including transmission power for reaching the neighbor nodes, and is updated by periodic HEIGHT messages from sinks. For power adaptation and new neighbor discovery, the neighborhood table will be updated with the new neighbors and new transmission power. The node also updates its neighborhood with the neighbors and new states as they change. If it receives a STATE (UNSAFE) message, the unsafe neighbor is removed from the table.