A Sweep Coverage Scheme Based on Vehicle Routing Problem

Abstract

As an emerging coverage problem in wireless sensor networks, sweep coverage which introducing mobile sensors to cover points of interest within certain time interval can satisfy monitoring request in some particular application scenarios with less number of nodes than the conventional static coverage approach. In this work, aiming to support dynamical POI coverage and data delivery simultaneously, a novel sweep coverage scheme, named VRPSC(Vehicle Routing Problem based Sweep Coverage), is proposed by modeling the minimum number of required sensors problem in sweep coverage as a Vehicle Routing Problem (VRP). In VRPSC, an insertion algorithm is first introduced to create the initial scanning routes for POIs, and then the Simulated Annealing is employed to optimize these routes. The simulation results show that the VRPSC scheme achieves better performance than existing schemes. DOI: http://dx.doi.org/10.11591/telkomnika.v11i4.2380