Quality-of-sensing aware budget constrained contaminant detection sensor deployment in water distribution system

Water contamination or pollution has raised serious disasters and social impact. It is significant to alleviate its impact or reduce the risks. Deploying water quality monitoring sensors in the water distribution systems naturally becomes a promising solution. In the consideration of sensor deployment, the deployment cost and the achieved quality-of-sensing, usually in terms of coverage, are always two contradictive issues. Although massively deploying sensors implies higher quality-of-sensing, it may also incur extremely high deployment cost. Actually, it is usually infeasible with the consideration of limited sensor deployment budget. In this paper, we are motivated to investigate a budget constrained sensor deployment in water distribution system, with the goal of maximizing the quality-of-sensing. Two kinds of sensors with different prices and hence different communication capabilities are considered. The cheaper one equips with only sensor-to-sensor communication capability. While, the expensive one is further capable of cellular communication. We first formally describe our problem using a mixed integer non-linear programming (MINLP) problem. To address the complexity on solving MINLP, we further propose a heuristic algorithm based on genetic algorithm, whose high efficiency is extensively validated by simulation based studies.