Constructing routing structures for sensor data collection with dynamic traffic patterns

In continuous sensor data collection, the network traffic pattern usually exhibits the dynamically changing characteristics. Different traffic patterns in the network result in the different proportion of energy spent on receiving, transmitting and idle listening at each node and thus require different routing structures for load balancing. Most existing routing approaches do not model the idle listening in their work since they target at the full network traffic pattern in which each node generates one data packet to transport to the base station at each sampling interval. This paper attempts to construct a single routing infrastructure to maximize the network lifetime under dynamic traffic patterns. We investigate the DAG (Directed Acyclic Graph) routing structure which allows each node to have multiple parents and child nodes and thus can better distribute the traffic load across different routes. We formulate the problem of finding the lifetime-optimal DAG routing structure as a mixed integer programming problem. We present a greedy algorithm to obtain a near-lifetime-optimal DAG and propose two methods to make use of the obtained DAG structure for data collection. Simulation results demonstrate the efficiency of the greedy algorithm and the promising of the proposed DAG-based methods in extending the network lifetime under dynamic traffic patterns.