We consider the online data gathering problem in wireless sensor networks and focus on load balancing for maximizing the network lifetime. We model the network as a shortest-path DAG which assigns a set of parent nodes for each node. Routing in the DAG is defined by forwarding the data from each node to one of its parents. We show that static routing approaches perform poor load balancing and are also NP-hard for optimizing the network lifetime. Hence, we define the notion of optimal network lifetime and optimal load balancing and consider two different dynamic forests based routing approaches in the DAG – probabilistic routing, and state-based routing.
Our probabilistic routing approach associates a non-0/1 Markov probability distribution on the edges of the DAG for making the parent selection. Using flow theory and probability theory we propose an efficient algorithm for computing the Markov probability distribution. Based on our results we have developed our two probabilistic routing algorithms – PBF routing and its variant a-PBF routing. Our state-based routing approach, on the other hand, uses the current state of the network to make the parent selection decision. Each node maintains a routing table with an entry for each parent node and the entries are updated based on current network state. Using the residual energy of a node as a parameter we have developed two state-based routing algorithms – MPE routing, and WPE routing. Based on extensive simulations we show that our algorithms achieve greater network lifetime and perform better load balancing compared to our lower-bound and upper-bound benchmark algorithms as well as other existing algorithms.
Among our other contributions, we have developed a novel way of capturing the inherent topological imbalance in the network called the Red-White-Blue (RWB) Balance diagrams. Further, since our results are based on the DAG modeling rather than the WSN itself, they are also applicable to other networks.