## 3 LBMR: Load Balancing Multipath Routing
### Layer Routing Construction  
As shown in Figure 3, LRC is based on layer routing. The data gateway is the top level of the network. Each node, functions as a router, has a _layer value_ indicating the distance to the gateway. _Nth-layer_ nodes are at the layer _N-hop_ to the gateway. When the distance to the gateway is shorter, the layer value is smaller and the layer is upper, and _vice versa_. In LRC, nodes in the upper layers are closer to the gateway than nodes in the lower layers. Each sensor may play both roles of lower-layer and upper-layer nodes in different relationships. For example, the distances to the gateway of three nodes are denoted as \(X_{d}\), \(Y_{d}\) and \(Z_{d}\). Given that \(X_{d}<Y_{d}<Z_{d}\), \(Y\) is in \(X\)'s lower layer and \(Y\) is in \(Z\)'s upper layer. Therefore, there are several layering sets of LRC. Each lower-layer node only needs to know the information of next-hop nodes in the immediate upper layer to the gateway. In Figure 3, Layer-1 nodes are connected with the gateway directly through wired connections. All the other nodes communicate with one another through wireless connection. LRC can quickly build routes because it is a top-down approach and nodes only require partial-topology information for route construction. LRC provides  
Figure 2: LBMR routing in a Zigbee stack. available multiple paths with equivalent hops to the gateway and all these equivalent paths are the shortest ones. If one node fails, another close-by node can be another next-hop to the gateway. This reinforces the network robustness. To initiate the network, all nodes including the gateway initialize their own layer values. The gateway sets its own layer value as 0 and all the other nodes set their initial layer value as 255. Subsequently, the gateway broadcasts a Route Construct message consisting of two fields, _Source Address_ and _Layer Value_. When sensor nodes receive Route Construct messages, they take route construction action differently in three diverse conditions described in the next paragraph and the constructed routes are totally loop-free and the shortest paths to the gateway. Once a node X receives a Route Construct message from node Y, X checks Y's layer value carried in the received Route Construct message. As illustrated in Table 1, X performs route construction according to different layer value conditions:  
\begin{table}
\begin{tabular}{l} \hline // y is sender and x is receiver. \\ Receive Route Construct; \\ If (layer,\({}_{>}\) (layer\({}_{{}_{X}}-1\)) ) \\ // Condition 1 avoids routing loop \\ Drop Route Construct; \\ ] Else if (layer\({}_{{}_{Y}}\)\(<\) (layer\({}_{{}_{X}}-1\)) ) \\ // Condition 2 ensures the shortest path. \\ If (routing table is empty) \\ Add y node to routing table; \\ ] Else { \\ Delete all routing entry \& \\ Add y node to Routing Table; \\ ] \\ layer\({}_{{}_{X}}\)\(=\)layer\({}_{{}_{Y}}+1\); \\ For the new Route Construct \\ layer \(=\)layer\({}_{{}_{Y}}\)\(\sim\)\(=\)\(=\)\(=\)\(=\)\(=\)\(=\)\(=\)\(=\)  
Condition 1 (X's layer value \(-\) 1 \(<\) Y's layer value):  
X discards this Route Construct message without adding Y to Routing Table because Y is farther from the gateway than X is. This guarantees a _loop-free_ network. Condition 2 (X's layer value \(-\) 1 \(>\) Y's layer value):  
X deletes all entries of its own Routing Table because Y becomes the best next-hop candidate. X updates its own layer value to (Y's layer value + 1)  
X adds Y to Routing Table. Condition 3 (X's layer value \(-\) 1 \(=\) Y's layer value):  
X adds Y to its own Routing Table as another equivalent path to the gateway. Multiple next-hop choices can enhance routing robustness. The routing table of each node consists of _Layer value_ and _Route values_, which has several upper-layer nodes associated with estimated loads. A next hop represents an upper-layer node on the path to the gateway, and estimated load is illustrated in LEA section in the following. Besides Routing Table, another Neighbor Table is used to record available neighbors to the gateway.