Battery allocation for wireless sensor network lifetime maximization under cost constraints

Wireless sensor networks hold the potential to open new domains to distributed data acquisition. However, such networks are prone to premature failure because some nodes deplete their batteries more rapidly than others due to workload variations, non-uniform communication, and heterogeneous hardware. Many-to-one traffic patterns are common in sensor networks, further increasing node power consumption heterogeneity. Most previous sensor network lifetime enhancement techniques focused on balancing power distribution, based on the assumption of uniform battery capacity allocation among homogeneous nodes. This paper gives a formulation and solution to the cost-constrained lifetime-aware battery allocation problem for sensor networks with arbitrary topologies and heterogeneous power distributions. An integer nonlinear programming formulation is given. Based on an energy-cost battery pack model and optimal node partitioning algorithm, a rapid battery pack selection heuristic is developed and its deviation from optimality is quantified. Experimental results indicate that the proposed technique achieves network lifetime improvements ranging from 3-11× compared to uniform battery allocation, with no more than 10 battery pack energy levels. The proposed technique achieves 2-5 orders of magnitude speedup compared to a general-purpose commercial nonlinear program solver, solution quality improves, and little approximation error is observed.