# Improving Route Selections in ZigBee Wireless Sensor Networks
## 6 Proposed Link Cost Estimation and Modified Route Selection Procedure
### Modified Route Selection Procedure  
Recall from Section 2.2 that ZigBee specifies that nodes compare the costs of candidate routes and select the next hop towards the concentrator whenever they receive a RREQ packet. In order to remain compliant with the ZigBee protocol, our modified route selection procedure still selects routes whenever RREQ packets are received; however, our route selection procedure has an additional treatment to decide among routes with the same cost. The original ZigBee route selection procedure and our proposed route selection procedure are illustrated in Figure 2(a),b respectively. Comparing these figures, it is possible to notice that our procedure starts processing an incoming RREQ in the same way as in the ZigBee specification: whenever a node \(z_{1}\) receives an incoming RREQ from a node \(z_{2}\), it computes the cumulative route cost toward the concentrator. If such a cost is lower than the cumulative route cost of the current next hop node, then node \(z_{1}\) updates its routing table to reflect node \(z_{2}\) as the next hop toward the concentrator. If such a cost is greater than the cumulative route cost of the current next hop node, then node \(z_{1}\) disregards the RREQ. The novelty of the proposed procedure is in the treatment when two or more next hop candidates have the same cumulative route cost, in the second test of Figure 3b. To understand this step and its effect, consider the scenario of Figure 1; assume that node 3 has node 1 as the current next hop towards the concentrator and assume node 3 receives a RREQ from node 2 with the same cumulative route cost as node 1. Recall that \(N_{3,1}^{(u),tx}(t)\) and \(N_{3,2}^{(u),tx}(t)\) refer to the number of unicast packets sent by node 3 on the last \(T_{avg}\) seconds to nodes 1 and 2 respectively. If \(N_{3,2}^{(u),tx}(t)\geq N_{3,1}^{(u),tx}(t)\), then node 3 disregards the RREQ and node 1 remains as the next hop toward the concentrator. However, if \(N_{3,2}^{(u),tx}(t)<N_{3,1}^{(u),tx}(t)\), then node 3 selects node 2 as the next hop. The reason for this is to enable node 3 to collect more samples from the link \(3,2\) in order to obtain a low variance estimate for \(\hat{p}_{3,2}^{(URR)}(t)\) in subsequent RREQ cycles. As subsequent RREQ packets with the same cumulative route cost from other next hop candidates arrive, the procedure performs the same comparison. In effect, among the next hop candidates that have the same cumulative route cost, node 3 selects the next hop candidate with lowest number of unicast packets transmitted during the last \(T_{avg}\) seconds. A second non-trivial aspect of the second test of Figure 3b is that it causes a node to, in effect, select multiple routes to the concentrator over multiple RREQ intervals. To understand this aspect, assume in the illustration of the previous paragraph that \(N_{3,2}^{(u),tx}(t)<N_{3,1}^{(u),tx}(t)\), causing node 3 to select node 2 as the next hop. This causes node 3 to stop sending the application packets to the concentrator using node 1 as next hop and start sending them using node 2. This causes \(N_{3,2}^{(u),tx}(t)\) to increase, and as previous transmissions using node 1 fall out of the averaging window \(T_{avg}\), causes \(N_{3,1}^{(u),tx}(t)\) to decrease. Eventually, in subsequent RREQ intervals, \(N_{3,2}^{(u),tx}(t)>N_{3,1}^{(u),tx}(t)\) and node 3 selects node 1 as next hop towards the concentrator. This results in node 3 selecting each next hop  
Figure 3: (a) ZigBee’s treatment of a route request (RREQ) message in the M2O routing procedure; and (b) modified treatment of a RREQ message in the U-RR procedure. This figure illustrates the treatment of a RREQ arriving from node 2 at node 3. Node 3 has previously received a RREQ from node 1 and stored node 1 and the estimated cumulative route cost of the route 3,1,0 in its routing table. candidate with the same cumulative route cost in a round-robin fashion.