LAUSR

Large-scale urban pipeline systems (LSUPSs) are complex pipeline networks of flows (e.g., water, oil, or gas). Flow capacity intelligent monitoring, e.g., automatically monitor the sum of flows in an LSUPS, is an important task in smart cities. Recently, mobile sensors and static receiver nodes are used to perform the task. Mobile sensors are released into the network at selected entrances to collect data, and upload the data to receiver nodes deployed at selected locations of the network for further analysis. Due to cost constraints, the numbers of mobile sensors and receiver nodes are limited, which cause the problem that some pipelines may not be monitored. However, applications normally require that some Zones of Interest (ZoIs) in the network have to be monitored. Therefore, how to select optimal entrances and locations for given numbers of mobile sensors and receiver nodes, so that the capacity of monitored flow is maximized within a given time under the constraint that all ZoIs are also monitored with expected probabilities, is a challenging problem. First, we prove the problem is NP-complete. Then, we design two algorithms based on submodular set function optimization to solve it. The first algorithm can obtain an approximate optimal solution with high time complexity, while the second algorithm can obtain a suboptimal solution with much lower time complexity. Finally, we analyze time complexity and approximate ratio of the two algorithms. Theoretical analyses and simulation results show that the proposed algorithms outperform the state-of-the-art algorithms.