Maximum Data Collection Least-Cost Routing in Energy Constrained Wireless Sensor Networks

Sensor networks are deployed to gather some useful data from a field and forward it toward a set of base stations or sinks for data analysis and decision making. Each sensor node is endowed with a finite amount of energy, and each byte transmission or reception costs a certain fixed fraction of energy as well as a variable fraction that depends on the distance between sender and receiver. Maximizing the volume of data collected at the sinks until some particular set of nodes exhaust their battery and partition the network is a very desirable trait in sensor networks, as it equates with a high level of energy efficiency. In this paper we formulate the problem of maximum data collection routing for sensor networks as a utility maximization problem subject to energy constraints, and invoke lagrange relaxation, duality and sub-gradient technique to solve the problem. We then focus on the problem of path oscillation, which is well known to happen in routing algorithms where link costs are function of the traffic load and propose heuristic solutions to address this oscillation problem