Assigning Sensors to Missions with Demands
Authors
Amotz Bar-Noy, Theodore Brown, Matthew P. Johnson, Thomas La Porta, Ou Liu, Hosam Rowaihy
Abstract
Abstract. We introduce Semi-Matching with Demands (SMD), which models the problem in sensor networks when individual sensors must be assigned to sensing tasks. If there are multiple sensing tasks or missions to be accomplished simultaneously, and if sensor assignment must be exclusive, then this is a bipartite semi-matching problem. Each mission is associated with a demand value and a profit value; each sensor-mission pair is associated with a utility offer (possibly 0). The goal is a sensor assignment that maximizes the profits of the satisfied missions (with no credit for partially satisfied missions). SMD is an NP-Complete problem which is as hard to approximate as Maximum Independent Set. Therefore we investigate less difficult constrained versions of the problem. We give a simple greedy -approximation algorithm for a degree-constrained version (-SMD), in which each mission receives positive utility offers from at most sensors. For small , we show that -SMD is equivalent to k-Set Packing (with k = ), which yields a polynomial-time (+1)/2-approximation. For = 2, we solve the problem optimally by reduction to maximum matching. Finally, we introduce a geometric version which remains strongly NP-Complete but has a PTAS.
Publication Date
July, 2007
Venue
AlgoSensors Workshop, July 2007
Published To
Conference
Publication Type
Externally published
ITA Area
Project 8, Technical area 3
Download a copy of the paper here
SMD_0.pdf
Return to main page