## 4 Protocol Description  
### Initialized Routing Structure  
_Initialized Sink Beacon_:  
The purpose of routing initialization is to form an initialized neighborhood and routing construction after the sensors are deployed and connected as a WSN in the building. We assume that sinks are deployed in a relatively safe place such that they are less likely to be destroyed, for example due to walls collapsing. Once the network is deployed, each sink generates a HEIGHT message using power level \(p_{0}\). This serves to advertise to neighbor nodes and includes a \"_height_\" parameter that represents the hop count toward the sink, and is initialized to 0. The height value is incremented by each forwarding hop. Each node records the height information in its local neighborhood table when it receives the first HEIGHT message. The message contains a sequence number so that a node can determine if it has seen the message already, in which case it ignores it. If it is the first time that it receives a HEIGHT message, the node forwards the HEIGHT message out. As explained below this process serves to ensure that each node will know a minimal delay route path from itself toward one of the sinks. Figure 1: State transition diagram for each node. In this HEIGHT message broadcasting process, the end-to-end delay from a node to the sink could be approximated by the cumulative delay on each hop. We use \"delay estimate\" in our EAR routing mechanism to make the forwarding choice. We denote _delay_ (_sink_, _i_) as the delay experienced from the sink to each node, and then we could use _delay_ (_sink_, _i_) as a bound to guide a real-time delivery from the node to the sink. The delay in transmitting a packet is estimated by:  
\[delay(sink,i)=\sum_{n=1}^{h}Avg\_-delay=\sum_{n=1}^{h}(T_{c}+T_{t}+T_{q})*R \tag{1}\]  
In formula (1), \(n\) is the hop count from the sink to node \(i\), _Tc_ is the time it takes for each hop to obtain the wireless channel with carrier sense delay and backoff delay. _Tt_ is the time to transmit the packet that determined by channel bandwidth, packet length and the adopted coding scheme. _Tq_ is the queuing delay, which depends on the traffic load, and \(R\) is the retransmission count. Among them, we omit the propagation delay, as in a WSN this is negligible due to the use of short-range radios. In the delay calculation, the delay of MAC layer with MAC protocol used is counted in. The average end-to-end delay from each node to the sink can be computed as the cumulative hop-by-hop delay, and the delay experienced in the current hop is calculated and updated locally, and then recorded in the HEIGHT message. Then _delay_ (_sink_, _i_) is recorded into the neighborhood table of each node. We use a periodic HEIGHT message update to calculate an average end-to-end delay (from multiple end-to-end delay estimates) as reference. Since packets in WSNs always tend to be relatively small, we consider it reasonable to ignore any impact of delay differences related to packet size. Furthermore, delay estimate utilizes [PERSON]'s algorithm [PERSON] (1974) to make adjustment by considering both the weighted average and variation of the estimated variable and as a result provides a good estimate of the delay. It can work well when link quality and network load varies. The calculation of average end-to-end delay and variation avoids a large number of deadline misses due to high variability in communication delays. Since the traffic from the node to the sink is usually heavier than the traffic from the sink to the node under the same radio situation according to sensor applications, we can say that queuing delay \(T_{q}(sink,\)\(i)\leq T_{q}(i,\)\(sink)\). This is bounded by the maximum queuing delay, _i.e.,_\(T_{q}(i,\)\(sink)\leq T_{qmax}\). When assuming the same radio and link quality for downstream and upstream links on the counterpart route path, we can get that: _delay_ (\(i,\)\(sink)\leq delay_{qmax}(sink,\)\(i)\).