A Generic Framework for Optimal Mobile Sensor Redeployment

Wireless sensor networks (WSNs) are widely used for various applications. In some applications, it is very likely that the number of sensors is limited, the initial deployment is random, and deployment “holes” (i.e., subareas where there is no sensor) may exist. Therefore, a major challenge in WSNs is to improve the network coverage. A viable solution is to enhance some sensors with mobility capability so that they can move inside the WSNs after the initial deployment, which is referred to as mobile sensor redeployment. In this paper, we target at a generic framework for the optimal mobile sensor redeployment problem in WSNs. In particular, in this paper, the area of a WSN is partitioned into a number of grids, and the gap of each grid is defined as the difference of the number of sensors in the grid from the desired number of sensors. Then, the mobile sensor redeployment problem is formulated as an optimization problem with three optimization requirements: to minimize the sum of gaps of all grids, to minimize the Lp-norm (1 ≤ p ≤ ∞) of the gap vector (where Lp-norm represents a family of optimization objectives when p takes different values), and to minimize the total movement cost of all mobile sensors. Bipartite matching-based redeployment (BMrD) algorithms are provided to solve the optimization problems with different values of p. In this paper, the framework is generic for mobile sensor redeployment because 1) the mobility capabilities of the sensors, the initial sensor distribution, the movement cost measures, and the sensor types are all arbitrary; 2) the coverage requirements in different grids can be heterogeneous; and 3) the BMrD algorithms are generic for different p values. The effectiveness of the BMrD algorithms is validated through theoretical proofs and extensive simulations.