Near optimal multi-application allocation in shared sensor networks

Recent years have witnessed the emergence of shared sensor networks as integrated infrastructure for multiple applications. It is important to allocate multiple applications in a shared sensor network, in order to maximize the overall Quality of Monitoring (QoM) subject to resource constraints (e.g., in terms of memory and network bandwidth). The resulting constrained optimization problem is a difficult and open problem since it is discrete, nonlinear, and not in closed-form. This paper makes several important contributions towards optimal multi-application allocation in shared sensor networks. (1) We formulate the optimal application allocation problem for a common class of distributed sensing applications whose QoM can be modeled as variance reduction functions. (2) We prove key theoretical properties of the optimization problem, including the monotonicity and submodularity of the variance reduction functions and the multiple knapsack structure of constraints; (3) By exploiting these properties, we propose a local search algorithm, which is efficient and has a good approximation bound, for application allocation in shared sensor networks. Simulations based on both real-world datasets and randomly generated networks demonstrate that our algorithm is competitive against simulated annealing in term of QoM, with up to three orders of magnitude reduction in execution times, making it a practical solution towards multi-application allocation in shared sensor networks.