Virtually Moving Base Stations for Energy Efficiency in Wireless Sensor Networks

Energy efficiency of wireless sensor networks (WSNs) can be improved by moving base stations (BSs), as this scheme evenly distributes the communication load in the network. However, physically moving BSs is complicated and costly. In this paper, we propose a new scheme: virtually moving BSs. We deploy an excessive number of BSs and adaptively re-select a subset of active BSs so as to emulate the physical movement. Beyond achieving high energy efficiency, this scheme obviates the difficulties associated with physically moving BSs. Challenges are that (i) the energy efficiency of BSs should be considered as well, in addition to that of the sensor nodes; (ii) the number of candidate subset of active BSs is exponential with the number of BSs. We show that scheduling the virtual movement of BSs is NP-hard. Then, we propose a polynomial-time algorithm that is guaranteed under mild conditions to achieve a lifetime longer than 62% of the optimal one. In practice, as verified through extensive numerical simulations, the lifetime achieved by the proposed algorithm is always very close to the optimum.