Optimal Citizen-Centric Sensor Placement for Citywide Environmental Monitoring - A Submodular Approach

Abstract

The general environmental monitoring problem refers to the task of placing sensors or stations to optimize certain objectives under budget constraints. Application scenarios include monitoring temperature, water contamination, air quality etc. As citizens are increasingly concerned about the surrounding environment, it is important to provide sufficient and accurate information to the public. In this study, we focus on the problem of optimal citizen-centric sensor placement, i.e, given a set of locations within the city, we aim at placing sensors or stations at locations that will benefit as many citizens as possible under budget constraints. We prove that the problem is NP-hard, yet the objective function has the nice non-decreasing and submodular property. Then the efficient greedy algorithm and its variants can be adopted with a guaranteed approximation ratio of (1-1/e) for the unit cost case and 1/2 (1-1/e) for the general cost case. Finally we demonstrate the effectiveness of the proposed approach by comparing with two baseline algorithms through a case study.