Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks
Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks
复制标题
DOI：
10.1061/(asce)0733-9496(2008)134:6(516
复制
发表时间：
2008-11-01
期刊：
影响因子：
--
通讯作者：
Faloutsos, Christos
中科院分区：
文献类型：
--
作者：
Krause, Andreas;Leskovec, Jure;Faloutsos, Christos
为了检测污染物的恶意引入，考虑了在大型配水网络中部署传感器的问题。结果表明，一大批现实的目标函数——如减少检测时间和保护不受污染的水的人口——表现出一种重要的收益递减效应，称为亚模块性。利用这些目标的子模块化来设计具有可证明性能保证的高效放置算法。本文提出的算法不依赖于混合整数规划，可以很好地适用于任意大小的网络。在本文中提出的方法中考虑的问题实例比文献中解决的最大问题要大几个数量级（72倍）。它显示了这里提出的方法如何扩展到多准则优化，选择位置对传感器故障的鲁棒性和优化极小极大准则。本文在两个基准分配网络和一个超过21,000个节点的实际饮用水分配系统上提出了广泛的经验证据，证明了本文提出的方法的有效性。
The problem of deploying sensors in a large water distribution network is considered, in order to detect the malicious introduction of contaminants. It is shown that a large class of realistic objective functions-such as reduction of detection time and the population protected from consuming contaminated water-exhibits an important diminishing returns effect called submodularity. The submodularity of these objectives is exploited in order to design efficient placement algorithms with provable performance guarantees. The algorithms presented in this paper do not rely on mixed integer programming, and scale well to networks of arbitrary size. The problem instances considered in the approach presented in this paper are orders of magnitude (a factor of 72) larger than the largest problems solved in the literature. It is shown how the method presented here can be extended to multicriteria optimization, selecting placements robust to sensor failures and optimizing minimax criteria. Extensive empirical evidence on the effectiveness of the method presented in this paper on two benchmark distribution networks, and an actual drinking water distribution system of greater than 21,000 nodes, is presented.