Maximizing the Lifetime of a Wireless Sensor Network with Fixed Targets
In this work we address the problem of maximizing the lifetime of a wireless sensor network (WSN) deployed over a field with fixed targets. The target locations to be covered are assumed to be known a priori but the locations of the sensors are assumed to be random and known only after their deployment on the field. The goal is to assign optimally some of the sensor nodes to monitor the targets, with the remaining nodes serving only as relay nodes of the data generated by the monitoring nodes and/or other relay nodes. We first obtain an optimal solution via an integer linear programming (ILP) formulation. We then present a practical procedure (referred to as DISP) which is based on standard linear programming as opposed to ILP, and heuristically assigns as monitoring sensor nodes the nodes that have the lowest local dispatch cost for each target. Experimental results demonstrate that DISP achieves practically the same solution as the ideal ILP formulation and is far better than an alternative heuristic that assigns as monitoring sensor node for each target the sensor node that is physically closest to it. In the second part of the work, we address the doughnut effect, i.e., the problem of the reduction of the WSN lifetime caused by the fact that the nodes closer to the base station deplete their battery earlier than the rest of the WSN nodes, and we use procedure DISP to evaluate the potential of increasing the density and/or battery level of the nodes closer to the base station in order to avoid it. Our simulation results indicate that for the same fixed total number of nodes and total battery amount, single-level battery configurations achieve practically the same performance as two level battery configurations, without the manufacturing and deployment cost of the latter.
Keywords: Wireless sensor networks, battery allocation, fixed targets, lifetime maximization, doughnut effect, energy efficient routing.