# Improving Route Selections in ZigBee Wireless Sensor Networks
## 3 Estimating Link and Route Costs
### Link Status (LS)-Based Estimation Procedure  
In the LS-based estimation procedure suggested in the ZigBee specifications (Section 3.6.3.1 of [13]), the cost \(c_{z_{1},z_{2}}\) of a node \(z_{1}\) transmitting to a node \(z_{2}\) is estimated by first estimating the probability \(p_{z_{1},z_{2}}\) that \(z_{1}\) successfully transmits a packet to \(z_{2}\); and such an estimate is obtained from the transmission of broadcast LS messages.  
To obtain the estimate \(\hat{p}_{z_{1},z_{2}}^{(LS)}(t)\) at time \(t\), let \(T_{avg}\) be the duration of the estimation window; let \(N_{z_{1}}^{(LS),tx}(t)\) be the number of LS messages transmitted by node \(z_{1}\) in the last \(T_{avg}\) seconds; let \(N_{z_{1},z_{2}}^{(LS),rx}(t)\) be the number of these messages that were received by node \(z_{2}\). The estimate for \(\hat{p}_{z_{1},z_{2}}^{(LS)}(t)\) is given by  
\[\hat{p}_{z_{1},z_{2}}^{(LS)}(t):=\frac{N_{z_{1},z_{2}}^{(LS),rx}(t)}{N_{z_{1}} ^{(LS),tx}(t)}; \tag{3}\]  
From the estimate \(\hat{p}_{z_{1},z_{2}}^{(LS)}(t)\), the estimate \(\hat{c}_{z_{1},z_{2}}^{(LS)}(t)\) is obtained with  
\[\hat{c}_{z_{1},z_{2}}^{(LS)}(t):=\min\left\{\gamma,\text{round}\left(\frac{1}{ \hat{p}_{z_{1},z_{2}}^{(LS)}(t)}^{4}\right)\right\}. \tag{4}\]  
It is important to observe that \(\hat{c}_{z_{1},z_{2}}^{(LS)}(t)\) is computed at the node \(z_{2}\), which is the node receiving the LS messages; but \(\hat{c}_{z_{1},z_{2}}^{(LS)}(t)\) is used by node \(z_{1}\) in routing decisions. Recall from the description of the M2O routing algorithm in Section 2.2 that a node \(z_{1}\) needs to estimate \(c_{z_{1},z_{2}}\) to determine the cumulative cost toward the concentrator node if it receives a RREQ from node \(z_{2}\). Since \(c_{z_{1},z_{2}}\) is estimated at node \(z_{2}\), node \(z_{2}\) needs to transmit its estimate \(\hat{c}_{z_{1},z_{2}}^{(LS)}(t)\) to node \(z_{1}\). In ZigBee, this is accomplished with LS messages as well: whenever node \(z_{2}\) transmits its own LS message, it attaches to it the latest cost estimates that it computed from any of its neighbors, including \(\hat{c}_{z_{1},z_{2}}^{(LS)}(t)\). Note further that, to compute \(\hat{c}_{z_{1},z_{2}}^{(LS)}(t)\), node \(z_{2}\) is able to determine \(N_{z_{1}}^{(LS),tx}(t)\) because it follows the same procedure for transmitting LS messages, and therefore, \(N_{z_{1}}^{(LS),tx}(t)\approx N_{z_{2}}^{(LS),tx}(t)\).  
From the individual link costs, the cumulative cost of a route \(z_{1},\ldots,z_{K}\) is given by  
\[\hat{c}_{z_{1},\ldots,z_{K}}^{(LS)}(t)=\sum_{i=1}^{K-1}\hat{c}_{z_{i},\hat{z}_{i +1}}^{(LS)}(t), \tag{5}\]  
where we observe that \(\hat{c}_{z_{1},\ldots,z_{K}}^{(LS)}(t)\) is computed in a distributed manner. For instance, consider the route 3,1,0 in Figure 1. As described in Section 2.2, node 0 constantly estimates \(\hat{c}_{1,0}^{(LS)}(t)\) and sends its latest estimate to node 1 whenever it sends a LS packet. Likewise, node 1 constantly estimates \(\hat{c}_{3,1}^{(LS)}(t)\) and sends its latest estimate to node 3 whenever it sends a LS packet. Whenever a RREQ packet is broadcast over the network, node 1 adds the latest received \(\hat{c}_{1,0}^{(LS)}(t)\) to the route cost field of the RREQ message. When node 3 receives the RREQ, it adds the latest received \(\hat{c}_{3,1}^{(LS)}(t)\) to the cost in the route cost field, obtaining \(\hat{c}_{3,1,0}^{(LS)}(t)\).  
We further note that both the individual link costs and the route cost are functions of time because of the randomness in the reception of LS messages.