## 3 LBMR: Load Balancing Multipath Routing
### Load Estimation Algorithm  
LEA is the core of LBMR. In order to achieve load balancing, every node periodically sends a Load Estimation message to notify neighbors of its own current traffic load. LRC allows nodes to have alternative paths to the gateway, and therefore nodes can choose the path with the least traffic as the next-hop to the gateway. If every sensor node always chooses the most unoccupied link, the network can become more load-balanced and bottleneck problem can be eliminated in the case where alternative routes are available.  
Each node periodically broadcasts Load Estimation message consisting of four fields: _Source Address, Estimated Load, Layer Value_, and _Routing Flag_. Routing flag is used for route maintenance and will be explained in the RM section. When receiving Load Estimation messages, nodes update their routing tables by adding new upper-layer nodes and the corresponding estimated loads. Once a node N receives a load estimation message M, it first compares M's layer value and the layer value of upper-layer nodes in the routing table. If M's layer value is smaller, node N updates the layer value in its routing table and subsequently replaces current upper-layer nodes with M's source address with M's estimated load. Otherwise, node N discards message M because a larger layer value implies a longer distance from the gateway. LEA uses an exponential weighted moving average (EWMA) formula [21] to calculate estimated load. EWMA can be used to predict future traffic and reduce  
Figure 4: Routing table and neighbor table in LBMR.  
fluctuation of future traffic flow. LEA estimates future load, which can reflect dramatic traffic changes in advance and avoid inaccurate next-hop selections.  
The sample code of LEA is presented in Table 2. In LEA, i is time slot number, Estimated_Load\({}_{i}\) represents the estimated load in the ith time slot. Estimated_Load\({}_{i-1}\) represents the estimated load of the (i - 1)th time slot, which is the previous time slot of the ith time slot. SampleLoad represents the current load and \(\alpha\) is the parameter used to estimate future estimated load from SampleLoad.  
In the beginning, Estimated_Load\({}_{0}\) is set to SampleLoad. There are two conditions of SampleLoad for determining Estimated_Load\({}_{i}\) in the ith time slot. If SampleLoad is 0, the Estimated_Load\({}_{i}\) is not set to 0 but to half of the previous estimated load to prevent the estimated load from dropping dramatically. If SampleLoad is non-zero, estimated load is determined by EWMA. \(\alpha\) is the weight of SampleLoad and is used to determine the influence of current traffic load on predicting the future traffic load. The impact of \(\alpha\) is discussed in Section 4 through our experiments. If the estimated load of some particular node N is larger, it means node N would potentially experience heavier traffic, and _vice versa_. In LEA, every node periodically calculates its own estimated load and broadcasts to neighbors through load estimation messages. While all nodes know the future estimated load of their upper-layer nodes, they can select the one with the least estimated load. Under this rule, the traffic is directed to the less busy channel and the network is well-balanced.