Frugal Sensor Assignment
Authors
Matthew P. Johnson, Hosam Rowaihy, Diego Pizzocaroz, Amotz Bar-Noy, Stuart Chalmers, Thomas La Porta, Alun Preece
Abstract
When a sensor network is deployed in the field, such as in monitoring applications, it is typically required to support multiple simultaneous missions, which may start and finish at different times. Schemes that match sensor resources to mission demands thus become necessary. In this paper, we consider new sensor-assignment problems motivated by frugality, i.e., the conservation of resources, for both static and dynamic settings. In general, the problems we study are NP-hard \emph{even to approximate}, and so we focus on heuristic algorithms that perform well in practice. For some interesting constrained problems settings, however, we give optimal or guaranteed approximation algorithms. Some of our algorithms can be run in a distributed fashion. For the NP-hard problem settings, we implement our approximation algorithms and test them on randomly generated data. In the online setting, available sensors propose to nearby missions, which then decide which proposals to accept. We find that overall performance can be significantly improved if available sensors sometimes refuse to offer utility to missions they could help. The decision of whether to make the offer is based on the value of the mission, the sensor's remaining battery level, and (if known) the remaining lifetime of the sensor network.
Publication Date
June, 2008
Venue
4th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS '08)
Published To
Conference
Publication Type
Externally published
ITA Area
Project 8, Technical area 3
Download a copy of the paper here
ipsn08.pdf
Return to main page