Coverage hole optimization with a mobile sensor in wireless sensor networks

Wireless Sensor Networks have many different application areas. In some areas such as battlefield surveillance, emergency rescue, and target detection, monitoring the target area with sensors that compose the network is of great importance for data reliability and event detection. However, due to many different reasons such as obstacles in the target area, loss of functionality, or uneven distribution of sensors, the target area cannot be fully covered, and therefore coverage holes emerge. In this study, the motivation is to eliminate coverage holes which occur when randomly deployed static sensors in Wireless Sensor Networks cannot cover the entire target region using a mobile sensor. After a thorough literature review of Wireless Sensor Network optimization, it has been observed that there is a lack of mathematical model-based approaches for the coverage problem. Therefore, for the specified problem, we propose a mathematical model so as to find the shortest path to be followed by the mobile sensor. The proposed model includes variables and constraints similar to those in the Hub Location and Traveling Salesman problems. Two decisions are handled simultaneously in the model. The first is to determine the stops in the mobile sensor's path so that each coverage hole is within the sensing range of the mobile sensor in at least one of these stops, i.e, to ensure full coverage when the mobile sensor completes its tour. Moreover, the second is to find the shortest one of such tours. Each stop of the mobile sensor represents a cluster-head, and the Hub Location constraints are used to determine these cluster-heads whereas the Traveling Salesman Problem constraints are included to minimize the total distance. It gets quite difficult to solve the resulting model to optimality even for medium sized instances using commercial solvers. Moreover, the optimality gaps are large for the best solutions obtained at the end of the specified time limit. To this end, a new model with a restriction on the set of possible cluster head locations and a two-phase mathematical model are introduced so as to get better solutions. Consequently heuristic methods are discussed in order to obtain good solutions in a short time. Accordingly, in addition to a heuristic algorithm with two versions, a hybrid method in which the mathematical modeling is used in accordance with heuristic algorithms is used to balance the trade-off between solution time and quality. Test results show that the hybrid method is quite effective in terms of solution time and quality.