Mobile Sensor Deployment Optimization Algorithm for Maximizing Monitoring Capacity of Large-Scale Acyclic Directed Pipeline Networks in Smart Cities

In smart cities, data monitoring for basic infrastructures, such as an urban water supply pipeline system or an oil/gas supply pipeline system, has become one of the most important tasks. An urban pipeline system that can be called a large-scale acyclic directed pipeline network (LSADPN), which has some characteristics, such as wide geographical distribution, complex connection, and deep underground. Therefore, it is difficult to be monitored comprehensively and accurately in real time. In recent years, some studies have proposed methods that use mobile sensors that are put into a pipeline network to obtain accurate monitoring results from the interior of the network. However, the mobile sensors have no motion devices and can only flow with the liquid in the pipelines. When a pipeline connection is encountered, it is uncertain whether all branches of the connection can be covered. Therefore, the maximum monitoring capacity, i.e., liquid capacity in the network monitored by the mobile sensors, is difficult to be maximized. In this article, the problem of maximizing the monitoring capacity of LSADPN is first proved to be NP-hard. Then, two new mobile sensors deployment algorithms based on the submodular function optimization method are proposed. Theoretical analyses and experimental results show that the two algorithms can monitor a whole network with high probability and achieve near maximum monitoring capacity with a specified number of mobile sensors and a given time.