Document Type
Technical Report
Publication Date
2009
DOI:
10.7936/K7154F96
Technical Report Number
wucse-2009-3
Abstract
With the fast development of wireless sensor network (WSN) technologies, WSNs have widely shifted from a specialized platform for a single application to an integrated infrastructure supporting multiple applications. It is hence a critical problem to allocate multiple applications to multiple sensors in order to maximize user utility subject to various resource constraints. The resulting constrained optimization problem is difficult since it is discrete, nonlinear, and not in closed-form. In this report, we develop an efficient optimization algorithm with rigorous approximation bounds for submodular monotonic optimization with multiple knapsack constraints. Based on a variance reduction formulation, we prove several important theoretical properties, including the monotonicity and submodularity of functions and the multiple knapsack structure of constraints. Then, by exploiting these properties, we propose a local search algorithm with fractional relaxation of constraints and prove the approximation bound that is better than any known results. Experimentally, we verify the theoretical properties on a large dataset from the Intel Berkeley Lab. Comparison against other constrained search algorithms show that our algorithm is superior in both solution time and quality, making it a practical choice for WSN design.
Recommended Citation
Xu, You; Chen, Yixin; Lu, Chenyang; Bhattacharya, Sangeeta; and Saifullah, Abu, "Submodular utility optimization in sensor networks for capacity constraints" Report Number: wucse-2009-3 (2009). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/14
Comments
Permanent URL: http://dx.doi.org/10.7936/K7154F96