Optimal movement-assisted sensor deployment and its extensions in wireless sensor networks

In wireless sensor networks (WSNs), a good sensor deployment method is vital to the quality of service (QoS) provided by WSNs. This QoS depends on the coverage of the monitoring area. In WSNs with locomotion facilities, sensors can move around and self-deploy to ensure coverage and load balancing, where each unit of monitoring area is covered by the same number of sensors. The movement-assisted sensor deployment deals with moving sensors to meet coverage and load balancing requirements. In SMART J. Wu, S. Yang, SMART: a scan-based movement-assisted sensor deployment method in wireless sensor networks, in: Proceedings of INFOCOM, 2005], various optimization problems are defined to minimize different parameters, including total moving distance, total number of moves, communication/computation cost, and convergence rate. In this paper, we focus on minimizing the total moving distance and propose an optimal, but centralized solution, based on the Hungarian method. This solution is illustrated in an application where the monitoring area is a 2-D grid-based mesh. We then propose several efficient, albeit non-optimal, distributed solutions based on the scan-based solution in Wu and Yang (2005). Extensive simulations have been done to verify the effectiveness of the proposed distributed solutions.