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.