Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2009

Filename

wucse-2009-3.pdf

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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7154F96

Share

COinS