Authors: Jie Wang, Ning Zhong
Addresses: Department of Computer Science, University of Massachusetts, Lowell, MA 01854, USA. ' Department of Computer Science, University of Massachusetts, Lowell, MA 01854, USA
Abstract: Suppose we need to watch a set of targets continuously for a required period of time, and suppose we choose any number of sensors from a fixed set of sensor types and place them at selected sites. We want to find a sensor arrangement to achieve the required coverage lifetime such that the total (monetary) cost of the chosen sensors is minimum. This is an NP-hard problem. We approach this problem by modelling it as an Integer Linear Programming problem. We devise a polynomial-time approximation algorithm to this problem with a proven approximation guarantee. We observe that the actual approximation ratios are small in practice. We then present a time-slotted scheduling to produce a timetable for each sensor. We also consider a special case with only one type of sensor that can watch one target at a time. We present a different method for solving this problem.
Keywords: wireless sensor networks; WSNs; minimum-cost sensor arrangement; lifetime requirement; integer linear programming; ILP; approximation algorithms; time-slotted scheduling; simulation; wireless networks.
International Journal of Sensor Networks, 2008 Vol.3 No.3, pp.165 - 174
Available online: 25 May 2008 *Full-text access for editors Access for subscribers Purchase this article Comment on this article