Coverage Hole Optimization With a Mobile Sensor in Wireless Sensor Networks for Smart Grid

Abstract

The Smart Grid (SG) enables electricity and energy exchange between two ends of the grid. Wireless Sensor Networks (WSNs) are considered as an enabling communication technology for effective SG management. How well the target region is covered by a WSN indicates the service quality of the relevant implementation. Since effective monitoring is key to exploiting the benefits of the SG, maintaining the desired coverage level is critical in WSN for SG applications. However, some uncovered regions (coverage holes) might emerge due to several reasons such as improper localization or sensor malfunctioning. In this paper, we propose using a mobile sensor to cover such blind regions in a timely and hence energy-efficient way. First, we present a novel 0-1 mixed integer programming model without restrictive assumptions about the mobility pattern to find the shortest trajectory for the mobile sensor. Then we show that the problem is NP-hard with a polynomial reduction to the Traveling Salesman Problem. Consequently, we present an optimization-based heuristic, two heuristic-based algorithms, and a hybrid algorithm. We show that our heuristics are efficient as they find high quality solutions in a few seconds. We also observe that assumptions about the starting point of the tour and the potential set of stops significantly affect the final tour's length.