Abstract
A major challenge affecting the lifetime of Wireless Sensor Networks (WSNs) comes from the unbalanced energy consumption over different parts of the network. This unbalanced energy consumption is a direct result of having a stationary sink: nodes near the sink are intensively used to relay data for other nodes to the sink. A natural solution to such a problem is to have multiple mobile sink nodes (which we call data collectors), and to change their locations periodically so that the load is distributed evenly among all sensor nodes. In this paper we propose a mobile data collector placement scheme for extending the lifetime of the network. In our scheme the lifetime of the network is divided into rounds and data collectors are moved to new locations at the beginning of each round. While previous work has focused on placing data collectors at predefined spots (e.g., the work in Gandham et al. (2003) [1]) or at the boundary of the network (e.g., the work in Azad and Chockalingam (2006) [2]), we define and solve two problems which are more general: the on-track placement where data collectors can be placed only along predefined tracks (roads) spanning the sensing field, and the general placement where data collectors may be placed at any point in the sensing field.
We formulate the problems as Mixed Integer Linear Programs (MILPs) and use a MILP solver (with a constant time limit) to find near-optimal placements of the data collectors and to find routing paths to deliver data to data collectors. Our experiments show that our schemes make significant extension to the lifetime of the network.