# Improving Route Selections in ZigBee Wireless Sensor Networks
## 2 Overview of ZigBee
### Many-To-One Source Routing Algorithm  
ZigBee specifies the many-to-one (M2O) Source Routing algorithm to setup routes between multiple devices and a single node, called the concentrator [1; 4].  
As specified in [13], to establish routes to the concentrator, the M2O routing algorithm uses a flooding of route request (RREQ) messages: the concentrator periodically broadcasts a RREQ message; nodes that receive the RREQ message rebroadcast the RREQ; and, as the RREQ travels through the network, nodes store the previous relay in their routing tables as the next hop to reach the concentrator. For example, in Figure 1, node 0 is the concentrator and periodically broadcasts a RREQ message. When nodes 1 and 2 receive the RREQ, they store in their routing tables that the concentrator can be reached directly; and, after a random delay, nodes 1 and 2 rebroadcast the RREQ message. When node 4 receives the RREQ from node 1, it stores in its routing table that node 1 is the next hop to reach node 0. Likewise, node 5 stores that node 2 is the next hop to reach node 0. The RREQ is rebroadcast by nodes until a specified maximum number of hops.  
A node may have multiple routes to the concentrator, and to differentiate among routes, the RREQ message has a route cost field. This field is used by nodes to compute the cumulative route cost toward the concentrator. More precisely, whenever a node receives a RREQ message, it estimates the link cost from the transmitter to itself and adds it to the RREQ's route cost field, forming the cumulative route cost. If the cumulative route cost is greater than the cumulative cost of a previously discovered route, then the node ignores the RREQ message. Otherwise, the routing table is updated with the next hop information and the cumulative cost; and the RREQ is rebroadcast with the route cost field updated with the cumulative cost.  
The M2O algorithm allows nodes to adapt their routes to the environment. To enable routes to adapt, the concentrator broadcasts the RREQ periodically. Each broadcast of the RREQ by the concentrator marks a RREQ period. The RREQ period is defined by the RREQ identifier (RREQ-ID). The RREQ-ID is present in the RREQ message and is incremented whenever the concentrator transmits a new RREQ message. When a node receives a RREQ with a new RREQ-ID, it updates its routing table even if the cumulative route cost is higher than the cost obtained from a previous RREQ period (see first paragraph of page 348 of [13]).  
The flooding of RREQ messages enables the establishment of routes from nodes to the concentrator; however, for reverse routes, the M2O algorithm uses route record (RREC) messages and source routing. A RREC message is a control packet sent by nodes to the concentrator. Whenever a node has a message to send to the concentrator, it first checks if a new RREQ period has started or if its next hop to the concentrator has changed. If either of these conditions have happened, the node sends the RREC message destined to the concentrator using the next hop node. As the RREC travels through next hop nodes, nodes append their addresses to the RREC message. When the RREC message arrives in the concentrator, it extracts and stores the whole route towards the node from the RREC message. Later, when the concentrator needs to transmit a message to the node, it uses the stored route to transmit to the target node using source routing; i.e., when transmitting the data packet, the concentrator adds the whole route in the header of the network layer. Relay nodes find out the next relay node from the header and remove their addresses before forwarding the packet.