Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

A knapsack approach to sensor-mission assignment with uncertain demands

Pizzocaro, Diego ORCID:, Johnson, Matthew P., Rowaihy, Hosam, Chalmers, Stuart, Preece, Alun David ORCID:, Bar-Noy, Amotz and La Porta, Thomas 2008. A knapsack approach to sensor-mission assignment with uncertain demands. Presented at: Unmanned/unattended sensors and sensor networks V, Cardiff, UK, 16-18 September 2008. Published in: Carapezza, Edward M. ed. Unmanned/Unattended Sensors and Sensor Networks V, Cardiff, Wales, United Kingdom, 16–18 September 2008. Proceedings of SPIE (7112) Bellingham, WA: SPIE, p. 711205. 10.1117/12.799859

Full text not available from this repository.


A sensor network in the field is usually required to support multiple sensing tasks or missions to be accomplished simultaneously. Since missions might compete for the exclusive usage of the same sensing resource we need to assign individual sensors to missions. Missions are usually characterized by an uncertain demand for sensing resource capabilities. In this paper we model this assignment problem by introducing the Sensor Utility Maximization (SUM) model, where each sensor-mission pair is associated with a utility offer. Moreover each mission is associated with a priority and with an uncertain utility demand. We also define the benefit or profit that a sensor can bring to a mission as the fraction of mission's demand that the sensor is able to satisfy, scaled by the priority of the mission. The goal is to find a sensor assignment that maximizes the total profit, while ensuring that the total utility cumulated by each mission does not exceed its uncertain demand. SUM is NP-Complete and is a special case of the well known Generalized Assignment Problem (GAP), which groups many knapsack-style problems. We compare four algorithms: two previous algorithms for problems related to SUM, an improved implementation of a state-of-the-art pre-existing approximation algorithm for GAP, and a new greedy algorithm. Simulation results show that our greedy algorithm appears to offer the best trade-off between quality of solution and computation cost.

Item Type: Conference or Workshop Item (Paper)
Date Type: Publication
Status: Published
Schools: Computer Science & Informatics
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Publisher: SPIE
ISBN: 9780819473448
Last Modified: 11 Jun 2023 01:17

Citation Data

Cited 3 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item