## 5 Analysis  
_Lemma1._ The EAR routing of the sensor network graph is loop-free.  
Proof: Suppose that there exists a loop \"A\(\rightarrow\)B\(\rightarrow\)C\(\rightarrow\)D\(\rightarrow\)E\(\rightarrow\)A\" in the network graph by EAR routing. Each node selects its next node which has less height towards the sink. When a node is stuck in local minimum, _i.e.,_ in a routing hole, the node could increase its transmission range to find another node that has less height towards the sink if exists. According to this, we could get:  
Figure 3: Timeout update in fire and route reconfiguration.  
\(height(\text{A})<\cdots<height(\text{E})<height(\text{D})<height(\text{C})<height( \text{B})<height(\text{A})\). This is a contradiction, so we conclude that the EAR routing of the network graph is loop-free.  
_Theorem1._ If there exists a route within delay bound from a node to one of the sinks, EAR can find this route.  
Proof: From Lemma 1, we know that there is no loop in the routing graph. Since the number and height of sensor nodes is limited, so the routes will lead to the sink eventually as long as the real-time route exists.  
_Theorem2._ For a given delay bound \(T_{max}\), the routing path found by EAR is within the delay requirement.  
Proof: We denote _delay_ (_sink_, _i_) as the delay estimate that is the minimal delay from the sink to the node, while _delay_ (_i_, _sink_) as the delay from the node to the sink on the counterpart route path. We denote \(T\) (_i_, _sink_) as the realistic delay experienced from a node to the sink. For queuing delay in wireless sensor networks, data packets are always reported from the node to the sink, while less traffic (usually control command) is delivered from the sink to the node. So \(T_{q}(\textit{sink},\textit{i})\leq T_{q}(\textit{i},\textit{sink})\). When assuming the same link quality of upstream and downstream links, there exists: _delay_ (_sink_, _i_) \(\leq\)_delay_ (_i_, _sink_) \(\leq\)_T_ (_i_, _sink_). In EAR, we use _delay_ (_sink_, _i_) as estimate of delay time form the node to the sink in routing discovery to find a route that meets the lower delay threshold, _i.e.,_ using _delay_ (_sink_, _i_) to estimate \(T\) (_i_, _sink_). In this way, we could improve the real-time delivery ratio from the node to the sink. Since we measure the average delay with HEIGHT using power \(p_{0}\), we get the maximal delay estimate time _delay_ (_sink_, _i_) on the minimum delay route path from the sink to the node within different power levels. In EAR, we find a relay node \(i\) that delay \(T\) from \(i\) to the sink with this route path should satisfy that it is no larger than the delay estimation on the route path, _i.e.,_\(T\) (_i_, _sink_) \(\leq\)_delay_ (_sink_, _i_). Otherwise, we increase the power level to find another forwarding choice \(j\), and such a node \(j\) (with increasing power) exists by satisfying: _delay_ (_sink_, _j_) + _Ave_delay_ (_i_, _j_) \(\leq\)_T_\({}_{slack}\); where \(T_{slack}=T_{max}-T(\textit{s},\textit{i})\). The end-to-end delay time \(T\) satisfies: \(T(\textit{s},\textit{sink})=T(\textit{s},\textit{i})+T(\textit{i},\textit{sink} )\leq T(\textit{s},\textit{i})+Ave\_delay(\textit{i},\textit{j})+delay(\textit{sink },\textit{j})\leq T(\textit{s},\textit{i})\)\(+\)\(T_{slack}\leq T_{max}\). So, we find a route from node \(s\) to the sink that satisfies \(T(\textit{s},\textit{sink})\leq T_{max}\).  
From the above situations, if a real-time route exists, EAR can find a route path satisfying that the end-to-end delay is within the delay requirement \(T_{max}\).