## 4 Protocol Description
### Routing Reconfiguration  
In building fire emergencies, robust routing is crucial due to the impact of quickly moving fire on node liveness. In this section, we explain how we reconfigure to deal with failures. We assume that: (1) the minimal time interval between \"_infire_\" and \"_unsafe_\" state of a node is chosen as a parameter known beforehand and denoted as _tunsafe_. (2) We use necessary transmission range for connectivity between nodes (according to selected power level) to approximate the minimal fire spreading time between two nodes. In practice, there are well-known guidelines for estimating the rate of fire spread [18-19], taking into account of building materials, building geometry, _etc._ It's also the case that obstacles, such as walls, that mitigate radio propagation also have the effect of slowing fire spread. When a forwarding choice is used for relaying, we add \"_timeout_\" and avoid using stale and unsafe paths, _i.e.,_ every node on the path from source \(s\) to destination \(d\) has \"_timeout_\" to record the valid time of each link on this route. The _timeout_ is updated when node state changes occur among the neighborhood. The forwarding choice that exceeds the _timeout_ value is considered invalid and then evicted. We assign an initialized large constant value to represent the estimated value time for the node in \"_safe_\" state. When a neighbor node \(j\) is caught in fire, a STATE (IN-FIRE) message is broadcast. If a \"_safe_\" node \(i\) receives a STATE (IN-FIRE) message from its neighbor node \(i\) will enter into the \"_lowsafe_\" state. The timeout of node \(i\) is updated, _i.e.,_ the valid time of node \(i\) is updated as the minimal time that this node may be caught in fire until it is out of function:  
\[timeout\ (i)=\min(\textit{s}\textit{s}\textit{e}\textit{e}\textit{a}\textit{t} \textit{i}\textit{e}\textit{a}\textit{e}\textit{a}\textit{e}\  
The re-discovery process stops when it finds another new forwarding choice with a valid route path cached toward one of the sinks (that could be a different sink from current one). Figure 3 shows an example for timeout update in fire. For _sf_, it reports _sf_ sink by route path: \(\{\)_f, b, i, j, sink\(\}\). After working for a while, sensor \(i\) (colored red) senses the fire occurrence. Then sensor \(i\) broadcasts a STATE (IN-FIRE) message to _notify_ its communication neighbors (colored yellow): \(a\), \(b\), \(d\), \(j\), and \(c\). When these nodes receive the message, they will enter into the \"_lowsafe_\" state. For the state change of sensor \(i\), then _timeout_ (_i_) is updated as \(t_{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_  
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}(sink,i)\leq T_{q}(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 one form the node to the sink in routing discovery to find a route that meets the lower delay threshold, \(i\),  
The packet dismiss ratio by delay estimate (we use \"dismiss ratio\" in the following paragraph) is defined as the ratio of packets discarded by delay estimate and the total sending packets.