A Flexible Solutions Methodology for Resource Allocation with Applications to Sensor Network Operations

Motivated by the need to judiciously allocate scarce sensing resources to attain the highest benefit for the applications that sensor networks serve, in this paper, we develop a flexible solutions methodology for maximizing the overall reward attained subject to constraints on the resource demands under fairly general reward or demand functions. We map a broad class of related problems into an integer programming problem and provide an iterative Lagrangian relaxation technique to solve it. Each iteration step involves solving for a maximum weight independent set of an appropriately constructed graph, which, in many cases, can be obtained in polynomial time. We apply our methodology to the problem of tracking targets moving over a period of time through a non-homogeneous, energy-constrained sensor field. With rewards represented by the quality of information attained in tracking, we study its trade-offs and relationship with energy consumption and periodic measurement taking. We further illustrate how to apply our methodology to an entirely different problem of how an unmanned air vehicle must traverse through a network of unattended ground sensors such that it maximizes the information collected from these sensors under delay constrains.

By: Srikanth Hariharan; Chatschik Bisdikian; Lance M. Kaplan; Tien Pham

Published in: RC25115 in 2010


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .