# Designing an Optimal Water Quality Monitoring Network

Xiaohui Zhu, Yong Yue, Yixin Zhang, Prudence Wong, Jianhong Tan

► To cite this version:

Xiaohui Zhu, Yong Yue, Yixin Zhang, Prudence Wong, Jianhong Tan. Designing an Optimal Water Quality Monitoring Network. 2nd International Conference on Intelligence Science (ICIS), Oct 2017, Shanghai, China. pp.417-425, 10.1007/978-3-319-68121-4_45. hal-01820934

HAL Id: hal-01820934

https://inria.hal.science/hal-01820934

Submitted on 22 Jun 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
Designing an Optimal Water Quality Monitoring
Network

Xiaohui Zhu<sup>1,3</sup>, Yong Yue<sup>1,*</sup>, Yixin Zhang<sup>2</sup>, Prudence W.H. Wong<sup>3</sup>, Jianhong Tan<sup>4</sup>

<sup>1</sup> Department of Computer Science and Software Engineering, Xi'an-Jiaotong Liverpool
University, Suzhou, Jiangsu Province,
215123 P.R. China

<sup>2</sup> Research Institute of New-type Urbanization, Huai'an, Jiangsu Province,
223005 P.R. China

<sup>3</sup> Department of Computer Science, University of Liverpool, Liverpool,
L69 3BX United Kingdom

<sup>4</sup>Jiangsu Province Hydrology and Water Resources Investigation Bureau Suzhou Branch
Suzhou, Jiangsu Province 215011 P.R. China

{xiaohui.zhu, yong.yue, yixin.zhang}@xjtlu.edu.cn,
pwong@liverpool.ac.uk,
jianhong_tan@qq.com

**Abstract.** The optimal design of water quality monitoring network can improve the monitoring performance. In addition, it can reduce the redundant monitoring locations and save the investment and costs for building and operating the monitoring system. This paper modifies the original Multi-Objective Particle Swarm Optimization (MOPSO) to optimize the design of water quality monitoring network based on three optimization objectives: minimum pollution detection time, maximum pollution detection probability and maximum centrality of monitoring locations. We develop a new initialization procedure as well as a discrete velocity and position updating function to optimize the design of water quality monitoring network. The Storm Water Management Model (SWMM) is used to model a hypothetical river network which was studied in the literature for comparative analysis of our work. We simulate pollution events in SWMM to obtain all the pollution detection time for all the potential monitoring locations. Experimental results show that the modified MOPSO can obtain steady Pareto frontiers and better optimal deployment solutions than genetic algorithm (GA).

**Keywords:** Optimal water quality monitoring network, multi-objective optimization, SWMM, closeness centrality

# 1 Introduction

River systems play a crucial role in the sustainable development of a community. However, industry and living activities are creating more and more pollutants to freshwater sources. It is estimated that 40 billion dollars are lost each year in China due to freshwater pollution events [1]. Water quality monitoring has become one of the routine efforts for environmental protection all over the world. However, monitoring water quality remains a very complex process due to the large number of factors to consider such as monitoring locations, selection of water quality parameters,
monitoring frequency and identification of monitoring objectives [3]. The costs of
building and operating an automatic monitoring station are also very high (about
500,000-600,000 dollars per station for construction and 14,000 dollars per year for
operating and maintaining). Planning and optimizing water quality monitoring
networks have been addressed since 1940s. Dozens of papers have been published on
this subject [3,4,5,6].

In this paper, we proposed a modified MOPSO algorithm to optimize the design of water quality monitoring network based on three optimization objectives: maximum pollution detection probability, minimum pollution detection time and maximum centrality of a monitoring network. Two discrete functions were developed to calculate particle's velocity and update particle's position respectively. Experimental results show that our algorithm can get steady Pareto frontiers and obtain better optimal deployment solutions than genetic algorithm (GA).

## 2 Methodology

### 2.1 Hypothetical River Network

To compare our study results with the achievements given by the literature (Quyang et al. 2008; Telci et al. (2008, 2009)), we use the same hypothetical river network as Figure 1 shows. There are 6 inlet locations (1, 3, 5, 8, 10, 11), 5 intermediate locations (2, 4, 6, 7, 9) and 1 outlet location (12) in the river network. We assume that a pollution event can occur at any location randomly with the same amount of pollutant spilling and there is only one pollution event at each time. We simulate the water flows for 24 hours from 00:00 to 23:59 with a steady water flow of $10ft^3/s$ for each inlet location. The pollution event occurs at 10:00 and lasts for 1 hour during the simulation. We also assume that the pollutant concentration is $10mg/L$. The remaining characteristics of the river network is shown in Table 1, which is the same as Telci used [7].

### 2.2 Hydraulic Simulations

The Storm Water Management Model (SWMM) is a dynamic rainfall-runoff simulation model used for single event or long-term (continuous) simulation of runoff

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Hypothetical river network</figcaption></figure>
<table><caption>**Table 1.** Hydraulic characteristics of the river network</caption><thead><tr><th>Catchment</th><th>Width (ft)</th><th>Channel's slope</th><th>Manning's coefficient</th><th>Flow rate (ft³/s)</th></tr></thead><tbody><tr><td>A</td><td>10</td><td>0.0001</td><td>0.02</td><td>10</td></tr><tr><td>B</td><td>10</td><td>0.0001</td><td>0.02</td><td>10</td></tr><tr><td>C</td><td>10</td><td>0.0001</td><td>0.02</td><td>10</td></tr><tr><td>D</td><td>10</td><td>0.0001</td><td>0.02</td><td>10</td></tr><tr><td>E</td><td>10</td><td>0.0001</td><td>0.02</td><td>10</td></tr><tr><td>F</td><td>10</td><td>0.0001</td><td>0.02</td><td>10</td></tr><tr><td>G</td><td>10</td><td>0.0001</td><td>0.02</td><td>20</td></tr><tr><td>H</td><td>10</td><td>0.0001</td><td>0.02</td><td>20</td></tr><tr><td>I</td><td>10</td><td>0.0001</td><td>0.02</td><td>30</td></tr><tr><td>J</td><td>10</td><td>0.0001</td><td>0.02</td><td>30</td></tr><tr><td>K</td><td>10</td><td>0.0001</td><td>0.02</td><td>60</td></tr></tbody></table>

<table><caption>**Table 2.** Pollution detection time at each potential locations</caption><thead><tr><th rowspan="2">Locations</th><th colspan="12">Pollution detection time and probability at each location</th></tr><tr><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th></tr></thead><tbody><tr><td>1</td><td>0</td><td>27</td><td>-</td><td>81</td><td>-</td><td>118</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>198</td></tr><tr><td>2</td><td>-</td><td>0</td><td>-</td><td>40</td><td>-</td><td>75</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>152</td></tr><tr><td>3</td><td>-</td><td>27</td><td>0</td><td>81</td><td>-</td><td>118</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>198</td></tr><tr><td>4</td><td>-</td><td>-</td><td>-</td><td>0</td><td>-</td><td>23</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>96</td></tr><tr><td>5</td><td>-</td><td>-</td><td>-</td><td>28</td><td>0</td><td>62</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>139</td></tr><tr><td>6</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>62</td></tr><tr><td>7</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>38</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td><td>113</td></tr><tr><td>8</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>79</td><td>27</td><td>0</td><td>-</td><td>-</td><td>-</td><td>157</td></tr><tr><td>9</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>111</td><td>57</td><td>-</td><td>0</td><td>-</td><td>-</td><td>190</td></tr><tr><td>10</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>133</td><td>78</td><td>-</td><td>10</td><td>0</td><td>-</td><td>213</td></tr><tr><td>11</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>156</td><td>99</td><td>-</td><td>27</td><td>-</td><td>0</td><td>236</td></tr><tr><td>12</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td></tr></tbody></table>

quantity and quality from primarily urban areas [8]. It is widely used for dynamically simulating storm water runoff and drainage systems in urban areas. Here we use SWMM to simulate the hydraulic model, pollution events and pollutants transport along the river system.

We set the pollution detection threshold to 0.01mg/L and run hydraulic simulations in SWMM. Table 2 shows the simulation results of pollution detection time for each potential monitoring location. The “-” in Table 2 represents an infinite value, which means the pollution event cannot be successfully detected at a monitoring location.

## 2.3 Optimization objectives

### a) Minimum Pollution Detection Time and Maximum Pollution Detection Probability

Telci et al. (2008) proposed a real-time optimal monitoring network design in river networks. They designed two optimization objectives of minimum pollution detection
time and maximum pollution detection. A genetic algorithm (GA) was used to optimize the water quality monitoring network according to these two optimization objectives. Here we also use the same two objectives in our algorithm. The detailed definition of these two optimization objectives can be found in [7].

b) Maximum Centrality of Monitoring Network

We argue that in practical environment, different potential monitoring locations may have different monitoring priorities, which should be considered when we design a monitoring network. In river network simulations, graph theory and network analysis are usually used to model river systems. The centrality is one of the most important indicators in graph theory. It can identify the importance of vertexes in a graph or network. Here we use the closeness centrality as an evaluation criterion of location priority. The closeness centrality for each potential monitoring location is described as Formula 1.

$$
C(i) = \left[ \frac{\sum_{j=1}^{m} d(i, j)}{m-1} \right]^{-1} \qquad (1)
$$

where *m* is the total number of potential monitoring locations, *d(i,j)* is the length from location *i* to location *j*. The total closeness centrality for a potential deployment solution *S*<sub>*k*</sub> is shown in Formula 2.

$$
C(S_k) = \sum_{i=1}^{n} C(S_{ki}) \qquad (2)
$$

where *n* is the number of monitoring devices deployed in a river network, *S*<sub>*ki*</sub> is a monitoring location in deployment solution *S*<sub>*k*</sub>.

The third optimization objective is to maximize the total closeness centrality for all deployment solutions, which is shown in Formula 3.

$$
C(S) = \max\{C(S_1), C(S_2), \dots, C(S_T)\} \quad (3)
$$

where *T* is the total number of potential deployment solutions.

2.4 MOPSO Algorithm

Assume that we will deploy *n* monitoring devices in a river system out of *m* potential monitoring locations (*n* <= *m*). It is easy to know that the total number of potential deployment combinations *T* is:

$$
T = C_{\text{im}}^{n} \qquad (4)
$$

We can find from Formula 4 that when we increase the value of *m* and/or *n*, the number of deployment solutions will be also increased exponentially, which is too large to calculate using enumeration search methods within a reasonable time. In addition, these optimization objectives normally conflict with each other, which means we aim to find some good trade-off solutions among multi objectives [9,10].

Multi-objective Particle Swarm Optimization (MOPSO) is one of the popular evolution algorithms used in recent year. Coello et al. (2004) compared MOPSO against
**procedure** INITIALIZATION (Integer k)

for i=1 to k do

particle(i).position = [];

particle(i).velocity = [];

for j=1 to n do

particle(i).position(j) = random(1, m);

particle(i).velocity(j) = 0;

end for

end for

**end procedure**

<caption>**Fig. 2.** Pseudocode of MOPSO initialization</caption>

**procedure** VEL_POS_UPDATING (int k)

MaxVel = round((m - 1)/10);

for i=1 to k do

for j=1 to n do

particle(i).velocity(j) = round(w * particle(i).velocity(j))

+c₁ * r₁ * (particle(i).best-position(j) - particle(i).position(j))

+c₂ * r₂ * (reph(j) - particle(i).position(j))];

particle(i).velocity(j) = min(max(particle(i).velocity(j), -MaxVel), +MaxVel);

particle(i).position(j) = particle(i).position(j) + particle(i).velocity(j);

if particle(i).position(j) < 1 or particle(i).position(j) > m then

particle(i).velocity(j).flag = -particle(i).velocity(j).flag;

particle(i).position(j) = min(max(particle(i).position(j), 1), m);

end if

end for

end for

**end procedure**

<caption>**Fig. 3.** Pseudocode of velocity and position updating</caption>

three state-of-the art multi-objective evolutionary algorithms of Nondominated Sorting Genetic Algorithm II (NSGA-II), Pareto Archived Evolution Strategy (PAES) and Microgenetic Algorithm for Multi-Objective Optimization (MicroGA) using 5 different test functions. Experimental results show that MOPSO has a highly competitive performance and can be considered a viable alternative to solve multi-objective optimization problems with low computational time. Here we use MOPSO to design an optimal water quality monitoring network. The velocity and position of particles during the computing iteration are updated by the following equations:

$$V_i(t + 1) = w V_i(t) + c_1 r_1 (pbest(i, t) - P_i(t)) + c_2 r_2 (gbest(t) - P(t)) \quad (5)$$

$$P_i(t + 1) = P_i(t) + V_i(t + 1) \quad (6)$$

where V denotes the particle's velocity, w is an inertia weight constant, r₁ and r₂ are uniformly distributed random variables within range [0, 1], pbest(i,t) is the best position that the particle i has had, gbest(t) is the best position in all current particles, and c₁ and c₂ are positive constant coefficients for acceleration.
<figure><img src="image_3.png" /><figcaption>Fig. 4. Velocity updating process</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 5. Hypothetical river network</figcaption></figure>

The classical MOPSO is a powerful algorithm to get global optimal results for continuous definition domains. However, it cannot be applied to discrete problems directly. In this paper, we redesign the initialization procedure and the velocity and position calculation function to optimize this discrete issue.

a) Particle design and swarm initialization

Assume we select *n* locations to deploy water quality monitoring devices out of *m* potential monitoring locations in a river network (*n* <= *m*). Each potential monitoring location is named from *l* to *m* respectively resulting in a location set *S*={1, 2, 3, ..., *m*}. Each particle in a swarm denotes a deployment solution with *n* monitoring locations. Therefore, each particle has *n* positions and each position represents a monitoring location in set *S*. As a result, particle *P* can be defined as a vector with *n* elements shown in Formula 7.

$$
\begin{equation}
\begin{aligned}
P &= [p_1 \ p_2 \ \dots \ p_i \ \dots \ p_n] \\
\text{subject to} \quad & n \le m \ \& \ 1 \le p_i \le m
\end{aligned}
\end{equation}
$$
<table><caption>**Table 3.** Optimal deployment solutions</caption><thead><tr><th>Monitoring locations</th><th>Detection time (min)</th><th>Detection probability</th><th>Centrality</th></tr></thead><tbody><tr><td>6,9,12</td><td>45.8</td><td>100%</td><td>0.0414</td></tr><tr><td>6,7,12</td><td>54.8</td><td>100%</td><td>0.0455</td></tr><tr><td>4,6,9</td><td>34.9</td><td>91.7%</td><td>0.0500</td></tr><tr><td>2,6,7</td><td>36.4</td><td>91.7%</td><td>0.0514</td></tr><tr><td>4,6,7</td><td>44.6</td><td>91.7%</td><td>0.0561</td></tr><tr><td>4,7,9</td><td>29.4</td><td>83.3%</td><td>0.0487</td></tr><tr><td>2,4,7</td><td>34.3</td><td>83.3%</td><td>0.0505</td></tr><tr><td>2,7,9</td><td>14.8</td><td>66.7%</td><td>0.0451</td></tr><tr><td>2,4,9</td><td>14.9</td><td>66.7%</td><td>0.0455</td></tr><tr><td>2,5,9</td><td>13</td><td>58.3%</td><td>0.0420</td></tr><tr><td>5,7,9</td><td>10.7</td><td>50%</td><td>0.0447</td></tr><tr><td>7,8,9</td><td>7.4</td><td>41.7%</td><td>0.0444</td></tr><tr><td>2,4,5</td><td>10.8</td><td>41.7%</td><td>0.0466</td></tr><tr><td>5,9,11</td><td>2.5</td><td>33.3%</td><td>0.0379</td></tr><tr><td>2,3,5</td><td>6.75</td><td>33.3%</td><td>0.0401</td></tr><tr><td>5,8,10</td><td>0</td><td>25%</td><td>0.0399</td></tr></tbody></table>

Assume we create *k* initial particles, we use a random integer function to initialize *n* positions and velocities for each particle in MOPSO. The swarm initialization procedure is as Figure 2 shows. The position value for all the particles is constrained between 1 and *m*. All the velocities are initialized to 0.

### b) Velocity and Position Updating

Equations 5 and 6 show that the original velocity and position in MOPSO are both real values. However, we use integers to denote monitoring locations in a particle. Figure 3 shows a procedure to update particle's velocity and position. We let *MaxVel* be a maximum velocity during calculation. A *round* function is used to calculate a new integer value of velocity for each particle based on current *gbest* and *pbest* particles. Because the new velocity may be out of the boundary of [-MaxVel,+MaxVel], we use *max* and *min* functions to restrict the velocity scope. The detailed velocity updating process is shown in Figure 4.

## 3 Simulations and Analysis

We run the MOPSO algorithm several times based on data in Table 2 and get several Pareto frontiers as Figure 5 shows. The simulation results show that these Pareto frontiers are almost the same except for few (one or two) Pareto frontier particles. It means that the simulation results of MOPSO algorithm are quite steady and we can use it to design an optimal water quality monitoring network. Table 3 shows the optimal deployment solutions based on the Pareto frontier particles.

We can find from Table 3 that if we deploy 3 monitoring devices at locations 6, 9 and 12, we can detect all the potential pollution events and the pollution detection time
is only 45.8 minutes. The centrality of this monitoring network is 0.0414. If we deploy
monitoring devices at locations 6, 7 and 12, potential pollution events can still be all
detected. However, the pollution detection time is increased to 54.8 minutes. If the
monitoring devices are deployed at locations 4, 6 and 9. The pollution detection time is
significantly decreased to 34.9 minutes while the detection probability is slightly
decreased to 91.7%, which is also the second highest pollution detection probability
solution in our deployment solutions and we can get a better centrality of 0.05. However,
the second highest pollution detection probability in Telci's paper is only 83%.

4 Conclusions and Future Work

We presented a novel method based on a modified MOPSO algorithm to design an
optimal water quality monitoring network with three optimization objectives of
minimum pollution detection time, maximum pollution detection probability,
maximum closeness centrality. Results show that the modified MOPSO can get a
better optimal deployment solutions than GA.

In the future, this novel approach will be applied to a real case of water quality
monitoring network. Further research is planned to explore the feasibility of
redesigning the velocity and position calculation procedure to avoid same positions
in a particle, which can further improve the computing performance.

Acknowledgements

This work was partly supported by the Natural Science Foundation of Jiangsu
Province (BK20151245), the Natural Science Foundation of Huai'an City
(HAG2015007), the Natural Science Foundation of Nantong City (MS12016048).

References

1. Yuqing Yang. How to Look at the GDP Receiving Much Attention[J]. Revolution, 2015(12):26-32.

2. Behmel S, Damour M, Ludwig R, et al. Water quality monitoring strategies - A review and future perspectives[J]. Science of The Total Environment, 2016: 1312-1329.

3. Park S Y, Choi J H, Wang S, et al. Design of a water quality monitoring network in a large river system using the genetic algorithm[J]. Ecological modelling, 2006, 199(3): 289-297.

4. Chilundo M, Kelderman P. Design of a water quality monitoring network for the Limpopo River Basin in Mozambique[J]. Physics and Chemistry of the Earth, Parts A/B/C, 2008, 33(8): 655-665.

5. Chang, Chia-Ling, and You-Tze Lin. A water quality monitoring network design using fuzzy theory and multiple criteria analysis[J]. Environmental monitoring and assessment 186.10 (2014): 6459-6469.

6. Ouyang, H. T., Yu, H., Lu, C. H., & Luo, Y. H. (2008). Design optimization of river sampling network using genetic algorithms. Journal of Water Resources Planning and Management, 134(1), 83-87.

7. Telci, I. T., Nam, K., Guan, J., & Aral, M. M. (2008). Real time optimal monitoring network design in river networks. In World Environmental and Water Resources Congress 2008: Ahupua'A (pp. 1-10).
8. Rossman, Lewis A. Storm water management model user's manual, version 5.0. Cincinnati, OH: National Risk Management Research Laboratory, Office of Research and Development, US Environmental Protection Agency, 2010.

9. Reyes-Sierra, M., & Coello, C. C. (2006). Multi-objective particle swarm optimizers: A survey of the state-of-the-art. International journal of computational intelligence research, 2(3), 287-308.

10. Coello C A, Lechuga M. MOPSO: a proposal for multiple objective particle swarm optimization[C]. congress on evolutionary computation, 2002: 1051-1056.

11. Telci, I. T., Nam, K., Guan, J., & Aral, M. M. (2009). Optimal water quality monitoring network design for river systems. Journal of environmental management, 90(10), 2987-2998.