Dynamic state-based routing for load balancing and efficient data gathering in wireless sensor networks

We consider the online data gathering problem in wireless sensor networks and examine the key issues of load balancing the nodes to achieve longer network lifetime, and that of load balancing the network links to achieve greater reliability in the network. We model the given network as a shortest-path DAG D, which defines a set of parent nodes for each node that determine the minimum-hops paths from the node to a sink. Data gathering in D is accomplished using a dynamic routing approach, where each node selects a parent using a parent selection function σ to forward the sensed data. We investigate a dynamic state-based routing approach where σ is defined using the current state of the network and propose two routing algorithms — MPE Routing and WPE Routing, that aim to load balance the nodes as well as the edges of D. Load balancing the nodes achieves longer network lifetime while load balancing the edges yields greater disjointness and thus greater reliability and trust in the network. Our simulation results show that our algorithms perform consistently better than our benchmark algorithms and other existing data gathering schemes with respect to our three goodness measures — network lifetime, nodal load balancing and disjointness.