Optimal coverage of an infrastructure network using sensors with distance-decaying sensing quality

Abstract

Motivated by recent applications of wireless sensor networks in monitoring infrastructure networks, we address the problem of optimal coverage of infrastructure networks using sensors whose sensing performance decays with distance. We show that this problem can be formulated as a continuous p-median problem on networks. The literature has addressed the discrete p-median problem on networks and in continuum domains, and the continuous p-median problem in continuum domains extensively. However, in-depth analysis of the continuous p-median problem on networks has been lacking. With the sensing performance model that decays with distance, each sensor covers a region equivalent to its Voronoi partition on the network in terms of the shortest path distance metric. Using Voronoi partitions, we define a directional partial derivative of the coverage metric with respect to a sensor's location. We then propose a gradient descent algorithm to obtain a locally optimal solution with guaranteed convergence. The quality of an optimal solution depends on the choice of the initial configuration of sensors. We obtain an initial configuration using two approaches: by solving the discrete p-median problem on a lumped network and by random sampling. We consider two methods of random sampling: uniform sampling and D2-sampling. The first approach with the initial solution of the discrete p-median problem leads to the best coverage performance for large networks, but at the cost of high running time. We also observe that the gradient descent on the initial solution with the D2-sampling method yields a solution that is within at most 7% of the previous solution and with much shorter running time.© 2013 Elsevier Ltd. All rights reserved.