Sensor-Mission Assignment in Constrained Environments
Authors:
- 18 February 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 21 (11) , 1692-1705
Abstract
When a sensor network is deployed in the field 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 the most general setting, 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 what we call the dynamic setting, missions arrive over time and have different durations. For this setting, we give heuristic algorithms in which available sensors propose to nearby missions as they arrive. We find that the overall performance can be significantly improved if available sensors sometimes refuse to offer utility to missions they could help, making this decision 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.Keywords
This publication has 15 references indexed in Scilit:
- Assigning Sensors to Competing Missions2008
- On Sensor Sampling and Quality of Information: A Starting Point2007
- An efficient approximation for the Generalized Assignment ProblemInformation Processing Letters, 2006
- Customer-Driven Sensor ManagementIEEE Intelligent Systems, 2006
- Global node selection for localization in a distributed sensor networkIEEE Transactions on Aerospace and Electronic Systems, 2006
- Optimal sensor management under energy and reliability constraints2004
- Utility-based decision-making in wireless sensor networks2002
- Bidding and allocation in combinatorial auctions2000
- GPSR2000
- Computationally Manageable Combinational AuctionsManagement Science, 1998