## 4 Protocol Description
### Routing Mechanism Details  
_Forwarding Choice_:  
For a given application-specific _Tmax_, we use _slack_ to remember the time left on the path from the current node to the sink. Each node in the neighborhood table is associated with _forward flag_ and a _timeout_. The flag is used to identify the next hop as a best forwarding choice, _i.e.,_ when a node is chosen as the best forwarding choice, the _forward flag_ is set to 1. The _timeout_ value is the valid time for the current forwarding node and used to prevent state neighborhood information (introduced in Section 4.3.) If \"_timeout_\" of a forwarding choice is due, its forwarding flag is set to 0 to evict the stale relay node. To select the best forwarding choice from each neighborhood table, we use the following criteria:  
Firstly, we filter the forwarding choices by _trigger_ to choose the nodes with lower height. Secondly, choose the node with _enough slack_ time according to delay estimate on the path. Thirdly, we filter the remaining forwarding choices by node state in the priority from \"_safe_\" to \"_infire_\". If there is more than one node satisfied, we select the best forwarding choice with higher residual energy. If there is still a tie, we choose the lower ID. If we cannot find a best forwarding choice with the current transmission power, we say that a \"hole\" has occurred (_i.e._ stuck in local minimum). _Hole Problem Handler:_ _On adapting Power level_:  
If a sensor node cannot find a next hop that satisfies the real-time constraint with current power level, it means that the node is stuck in a local minimum. The solution is to increase the transmission power gradually by levels to find another neighbor or invoke a new neighbor discovery. Otherwise, a notify message is sent back to its upstream node (_i.e.,_ parent) to stop sending data packets to the current node; and then a routing re-discovery is invoked by the upstream node. If we could find another node existing in the neighborhood table by adapting the transmission power, then we increase the power level and name this neighbor as a forwarding choice. Otherwise, a new neighbor discovery is invoked by increasing the transmission power gradually by levels. We increase power level gradually but not to the maximal power level directly by considering of the big interference incurred by larger power. We know that there are only two to three power levels provided on existing MICA motes and most of the motes currently used. So, it converges very quickly to the optimal power level. Figure 2 shows an example of a new neighbor discovery, where _sink1_ and _sink2_ are two sinks, and the other nodes are sensors. Node \(i\) reports and routes data to the sink. The number on each node represents the \"_height_\" of each node toward the sink. As the route path \(\{i,\,a,\,sink1\}\) with \(p_{0}\) is invalid because _slack_ cannot satisfy the estimated end-to-end delay, node \(i\) is in the \"hole\". If there are no existing eligible neighbors, then \(i\) will increase its power to _p1_ to reach node \(j\) and delivers the packets to another sink _sink2_ by route path \(\{i,j,\,sink2\}\) when \"_slack_\" on this route is no less than delay estimate. Each sensor has \(k\) levels of power setting: \(\{p_{0}\}\)\(p_{1}\), \(p2\)...\(p_{k\)-1} and could be in \(k\) levels of maximal transmission range as: \(\{r_{0},\,r_{1}\}\)\(r_{k}\), where \(r_{0}\) is the \(k\) threshold function to find appropriate transmission power by increasing the power as follows:  
\[p=p_{cur+1},\,\iota=1,\,2,\,3\,\ldots\,k\text{-}1 \tag{2}\]  
where, _cur_ is the current number of transmission range level among \(k\) levels, \(t\) is the count of unsuccessful attempts. A sensor will increase its transmission power gradually in levels if it cannot find an eligible new neighbor. A node increases its power according to formula (2) until one of the following conditions is satisfied:  
(1) It finds a node as a forwarding choice in \"_safe_\" state according to the height and delay estimate.