## 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 \(t_{unsafe}\). (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 valid 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 enters 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(spread\_time(i,j)+t_{unsafe} \tag{6}\]  
Then the _timeout_ value of both downstream and upstream links that are adjacent to node \(i\) are also updated accordingly. If node \(i\) becomes \"_infire_\", the _timeout_ of adjacent links are updated as \(t_{unsafe}\), _i.e., timeout_ (\(i\)) = \(t_{unsafe}\). Otherwise, if node \(i\) becomes \"_unsafe_\" by local sensed data and threshold, then _timeout_ (\(i\)) is updated as 0 and the _timeout_ of the adjacent links are also updated to 0. The link _timeout_ value is updated as the state of the node adjacent to the link changes. When a node state is changed for fire, the \"_timeout_\" on upstream and downstream links that are adjacent to this node will both be updated. For path link (\(i\), \(j\)) on each route path, the _timeout_ value for this link is calculated as:  
\[timeout\ (link(i,j))\text{=}\min(timeout(i),\ timeout(j)) \tag{7}\]  
In formula (7), _timeout_ (\(i\)) and _timeout_ (\(j\)) represents the valid time for node \(i\), \(j\) of the route in fire, respectively. In a building fire, node failures because of fire damage will trigger routing tree reconfiguration. In case of a path link _timeout_ value that is lower than a threshold (_i.e.,_ the route path will be invalid very soon), a route reconfiguration is invoked to find another available route path before the current one becomes invalid. The reconfiguration is only invoked by an upstream node \(i\) of the path link (\(i\), \(j\)whose valid time is no less than the timeout of the link, _i.e., timeout_ (_i_) \(\geq\)_timeout_ (_link_ (_i_, _j_)). The routing reconfiguration of the node is invoked as a routing re-discovery by broadcasting a RTR message to set up a new route path search. The search of the forwarding choice is invoked in its neighborhood table to find if one of the existing neighbors is eligible to act as a relay or not by adapting the power to the setting recorded in local neighborhood. Otherwise, we will start a neighbor re-discovery process by increasing its power level gradually. 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.