Frugal Sensor Assignment (ACITA 2008)
AuthorsMatthew Johnson, Hosam Rowaihy, Diego Pizzocaro, Amotz Bar-Noy, Stuart Chalmers, Thomas La Porta and Alun Preece
When a sensor network is deployed in the ?eld it is typically required to support multiple simultaneous missions, which may start and ?nish 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 even to approximate, and so we focus on heuristic algorithms that perform well in practice. In the static setting, we propose a greedy centralized solution and a more sophisticated solution that uses the Generalized Assignment Problem model and can be implemented in a distributed fashion. In the dynamic setting, we give heuristic algorithms in which available sensors propose to nearby missions as they arrive. We ?nd that the overall performance can be significantly improved if available sensors sometimes refuse to offer utility to missions they could help based on the value of the mission, the sensorís remaining energy, and (if known) the remaining target lifetime of the network. Finally, we evaluate our solutions through simulations.
Publication DateSeptember, 2008
Publication TypeITA Conference paper
ITA AreaProject 8, Technical area 3
Download a copy of the paper herefrugalassignment.pdf
Return to main page