# Path Optimization of Mobile Sink Node in Wireless Sensor Network Water Monitoring System

Authors: Fan Chao; Zhiqin He; Aiping Pang; Hongbo Zhou; Junjie Ge
Journal: Complexity
 (2019)

---

## Abstract

In the water area monitoring of the traditional wireless sensor networks (WSNs), the monitoring data are mostly transmitted to the base station through multihop. However, there are many problems in multihop transmission in traditional wireless sensor networks, such as energy hole, uneven energy consumption, unreliable data transmission, and so on. Based on the high maneuverability of unmanned aerial vehicles (UAVs), a mobile data collection scheme is proposed, which uses UAV as a mobile sink node in WSN water monitoring and transmits data wirelessly to collect monitoring node data efficiently and flexibly. In order to further reduce the energy consumption of UAV, the terminal nodes are grouped according to the dynamic clustering algorithm and the nodes with high residual energy in the cluster are selected as cluster head nodes. Then, according to the characteristics of sensor nodes with a certain range of wireless signal coverage, the angular bisection method is introduced on the basis of the traditional ant colony algorithm to plan the path of UAV, which further shortens the length of the mobile path. Finally, the effectiveness and correctness of the method are proved by simulation and experimental tests.


---

## Body

## 1. Introduction

The wireless sensor network, composed of a large number of static or mobile sensors in a self-organizing and multihop manner, is widely used in military, medical health, smart homes, building monitoring, environmental monitoring, and other fields [1]. In the water area detection of traditional wireless sensor networks, a terminal node transmits data to a sink node by multihop [2]. However, multihop transmission tends to cause an energy hole. In other words, the nodes around the sink node, undertaking too many data forwarding tasks and thus consuming a lot of energy or even exhausting the energy, will damage the connectivity of the entire wireless network. At the same time, the multihop transmission also produces additional communication overhead due to collision caused by frequent communication and data transmission between nodes.In order to solve the above problems, a wireless sensor network with mobile nodes was born. The sink nodes are carried on by mobile terminals to collect data, which not only avoids energy hole and uneven energy consumption, prolongs the life cycle of the whole network, but also improves the flexibility of data collection and the reliability of data transmission [3–14]. In reference [2], the data acquisition strategy of the mobile sink node is studied, which improves the efficiency of the work, but the specific acquisition path is not planned and studied. In reference [3], the ant colony algorithm is optimized to plan the path of mobile sink nodes, which solves the problem that the global search ability of traditional ant colony algorithm is weak and easy to fall into the local optimal solution, but it fails to make use of the wireless signal coverage characteristics of nodes in WSN. Reference [4], taking into consideration the characteristics of wide deployment range and irregular position of the mobile terminal in the farmland information acquisition system, proposes an energy-efficient data collection scheme. According to factors such as node energy and location, the node cluster head can be selected optimally, but this scheme cannot be applied to the scene with high real-time requirements. In reference [5], a maximum-minimum energy consumption probability model is proposed to optimize the path between network neutron nodes and sink nodes, but the energy limitation of the mobile sink itself is not taken into account. On the basis of introducing a mobile data collector, an algorithm of maximizing cache mechanism is proposed in reference [6] to avoid the overflow of cluster head due to insufficient cache space and prolong the life cycle of the network, but the energy consumption of mobile data collector is also not taken into account. A mobile data collection strategy combined with DSDV routing protocol is proposed in [7], which improves the reliability of data transmission and extends the network life cycle, however, the level of timeliness and adaptability is not high. In reference [8], the mobile data transmitter (MDT) is used as the mobile sink node, and a heuristic discrete firefly algorithm is proposed, which can be used to collect the data optimally from the sensor node. In reference [9], in order to solve the problem of energy hole in traditional wireless sensor networks, a new path planning scheme is proposed in this paper. It forms a generating tree to connect all sensors, and then selects each convergence point according to the number and distance of hops in the tree and the amount of forwarding data from other sensors, and proposes an enhancement algorithm to further reduce the path distance. This paper presents a new optimization method for the path of the mobile node, which is simple in principle and has high practicability and can provide some reference for such problems.This paper mainly considers the self-moving energy consumption in the mobile data collection of the mobile sink node from the actual environment. UAV is applied to wireless sensor networks as a mobile sink node and puts forward a new path optimization algorithm to optimize its moving path and reduce the total energy consumption. According to the dynamic clustering algorithm, the network is divided into clusters, and the cluster head nodes are selected according to the energy level. The cluster head nodes of each cluster become the residence point of UAV. UAV traverses each cluster head node from the base station, collects the data, and returns to the base station. Its energy consumption is mainly composed of two parts: the first part is mobile energy consumption; the second part is consumption due to data collection. Compared with the energy consumption of receiving data, the mobile energy consumption of UAV is an important part of its total energy consumption. Therefore, how to plan the moving path of UAV and reduce its moving length as much as possible has become an important part of the problem of mobile data collection. This paper takes into account the path planning of mobile sink nodes in WSN and the wireless signal coverage characteristics of nodes, further reduces the line distance of mobile sink nodes, improves the efficiency of data extraction, and increases the endurance ability of mobile sink nodes.The remainder of this paper is as follows: In the second part, we present the model of the problem and analyze it. In the third part, the optimization scheme is put forward, and the simulation and experiment are carried out to prove the effectiveness and reliability of the scheme. In the fourth part, the summary of the proposed work is made.


## 2. Problem Modeling and Formulation

### 2.1. Problem Modeling

In the water area monitoring system of the wireless sensor network, the sensor monitoring node collects the data to send to each cluster head node, and then the UAV collects the data of each cluster head node [15–17]. The overall network model is shown in Figure 1.Figure 1
Overall structure diagram of the system.Combined with the given network model, before putting forward the model of the UAV path planning problem, the following assumptions are made for the problem, which is convenient for analysis and calculation.(1)
The altitude of the monitoring nodes will be different in the area where the monitoring nodes are arranged. In order to simplify the problem without losing its generality, it is assumed that the monitoring nodes are all in the same plane.(2)
The wireless signal coverage area of the mobile sink node and the monitoring node is circular, and the specific range is determined by the radius of the stable transmission data of the hardware wireless communication module. Each monitoring node and the mobile sink node are respectively the centers of the circle. At the same time, the monitoring node and the mobile sink node are abstracted into the points in the area.Based on the above assumptions, considering the coverage of the mobile sink node and the monitoring node, the schematic diagram of the mobile sink node line can be analyzed, as shown in Figure2.Figure 2
Schematic diagram of the problem model.In Figure2, z0 is the original position of the mobile sink node, x1,x2,x3,x4 is the location of each monitoring node. If there are overlapping areas between the two nodes, the middle point between the selected quantity nodes is taken as the extraction point on the line, if not, the edge of the coverage area is selected as the stop point, expressed as a1,a2,a3, and it is called the middle selection point. y1,y2,y3,y4 is the point with considering the wireless signal coverage. So the line z0−x1−x2−x3−x4 is the traditional traveling salesman problem routes [8–14], represented as TS; the line of the middle selection point is represented as MS, y1−y2−y3−y4 is the line of best stop point with considering the coverage of wireless signal, represented as SS. As we can see from Figure 2, the line SS line is shorter than the other two.


### 2.2. Problem Formulation

The problem model is analyzed and explained in detail below.The conventional travel quotient line TS is a better line without regard to the coverage of the wireless signal. For line MS, the radius of wireless signal coverage is usually smaller than the interval distance of node arrangement, and the final line is not as good as line SS even when there is an intersection area. Therefore, the line planning of the mobile sink node considering the coverage of the wireless signal is transformed into the solution of the SS line. At the same time, in the SS line, the position of the best stop point can be found by a strategy, and the final SS line section is composed of the initial position of the mobile sink node and each satisfactory solution point. The shortest line planning is mainly to determine the location of each best stop point and the access order between them by joint programming to construct the optimization expression [18–24].In the shortest route planning problem of the flight path of the mobile sink node, there are directly connected road sections between the origin point and the best stop point of the mobile sink node and the best stop point without considering the obstacle. Therefore, the initial position point and the best stop point of the moving sink node form a directed graph, which is expressed as follows:G = (V, E), in which V=x0,y0,y1,…,yn, E is the set of lines in figure G, and the S matrix is used to indicate whether the line segment in E is selected as the optimal line section; if Sij=1, the line yi,yj is selected, if Sij=0, it means yi,yj is not selected for the optimal line section.Through the above definition and explanation of the symbol, the flight path planning problem of the mobile sink node considering the wireless signal coverage area will be expressed as follows:(1)SS:MinΓY,S=∑i=0n∑j=0nSijyi−yj,xi−yi≤r,i=1,2,…,n,∑i=0nSij=1,j=1,2,…,n,∑j=0nSij=1,i=1,2,…,n,Sij∈0,1.In the above model,Γ is the objective function. The parameter is the position Y of the best stop point and the road selection matrix S. At the same time, the model is explained as follows: (1)
The expression 1 is the objective function of the model, indicating the length of the travel path of the mobile aggregation node. At the same time, in the formula,Sij indicates whether the line segment is a segment in the travel path of the mobile aggregation node. The distance between the best stop point i and the best stop point j is expressed as yi−yj.(2)
The expression 2 is a constraint condition of the mobile aggregation node and the best stop point and indicates that the mobile aggregation node needs to be satisfied with the path corresponding to the effective communication range of each sensor monitoring node and the mobile aggregation node, and the range is a circle centered onxi and the effective communication radius is r.(3)
Expressions 3 and 4 represent the access constraints of each satisfactory solution point. On the flight line of the mobile sink node, there is only one line that leaves and enters each satisfactory solution point.(4)
Expression 5 represents the selected matrix of the road section, with 1 for selection and 0 for unchecked.


## 2.1. Problem Modeling

In the water area monitoring system of the wireless sensor network, the sensor monitoring node collects the data to send to each cluster head node, and then the UAV collects the data of each cluster head node [15–17]. The overall network model is shown in Figure 1.Figure 1
Overall structure diagram of the system.Combined with the given network model, before putting forward the model of the UAV path planning problem, the following assumptions are made for the problem, which is convenient for analysis and calculation.(1)
The altitude of the monitoring nodes will be different in the area where the monitoring nodes are arranged. In order to simplify the problem without losing its generality, it is assumed that the monitoring nodes are all in the same plane.(2)
The wireless signal coverage area of the mobile sink node and the monitoring node is circular, and the specific range is determined by the radius of the stable transmission data of the hardware wireless communication module. Each monitoring node and the mobile sink node are respectively the centers of the circle. At the same time, the monitoring node and the mobile sink node are abstracted into the points in the area.Based on the above assumptions, considering the coverage of the mobile sink node and the monitoring node, the schematic diagram of the mobile sink node line can be analyzed, as shown in Figure2.Figure 2
Schematic diagram of the problem model.In Figure2, z0 is the original position of the mobile sink node, x1,x2,x3,x4 is the location of each monitoring node. If there are overlapping areas between the two nodes, the middle point between the selected quantity nodes is taken as the extraction point on the line, if not, the edge of the coverage area is selected as the stop point, expressed as a1,a2,a3, and it is called the middle selection point. y1,y2,y3,y4 is the point with considering the wireless signal coverage. So the line z0−x1−x2−x3−x4 is the traditional traveling salesman problem routes [8–14], represented as TS; the line of the middle selection point is represented as MS, y1−y2−y3−y4 is the line of best stop point with considering the coverage of wireless signal, represented as SS. As we can see from Figure 2, the line SS line is shorter than the other two.


## 2.2. Problem Formulation

The problem model is analyzed and explained in detail below.The conventional travel quotient line TS is a better line without regard to the coverage of the wireless signal. For line MS, the radius of wireless signal coverage is usually smaller than the interval distance of node arrangement, and the final line is not as good as line SS even when there is an intersection area. Therefore, the line planning of the mobile sink node considering the coverage of the wireless signal is transformed into the solution of the SS line. At the same time, in the SS line, the position of the best stop point can be found by a strategy, and the final SS line section is composed of the initial position of the mobile sink node and each satisfactory solution point. The shortest line planning is mainly to determine the location of each best stop point and the access order between them by joint programming to construct the optimization expression [18–24].In the shortest route planning problem of the flight path of the mobile sink node, there are directly connected road sections between the origin point and the best stop point of the mobile sink node and the best stop point without considering the obstacle. Therefore, the initial position point and the best stop point of the moving sink node form a directed graph, which is expressed as follows:G = (V, E), in which V=x0,y0,y1,…,yn, E is the set of lines in figure G, and the S matrix is used to indicate whether the line segment in E is selected as the optimal line section; if Sij=1, the line yi,yj is selected, if Sij=0, it means yi,yj is not selected for the optimal line section.Through the above definition and explanation of the symbol, the flight path planning problem of the mobile sink node considering the wireless signal coverage area will be expressed as follows:(1)SS:MinΓY,S=∑i=0n∑j=0nSijyi−yj,xi−yi≤r,i=1,2,…,n,∑i=0nSij=1,j=1,2,…,n,∑j=0nSij=1,i=1,2,…,n,Sij∈0,1.In the above model,Γ is the objective function. The parameter is the position Y of the best stop point and the road selection matrix S. At the same time, the model is explained as follows: (1)
The expression 1 is the objective function of the model, indicating the length of the travel path of the mobile aggregation node. At the same time, in the formula,Sij indicates whether the line segment is a segment in the travel path of the mobile aggregation node. The distance between the best stop point i and the best stop point j is expressed as yi−yj.(2)
The expression 2 is a constraint condition of the mobile aggregation node and the best stop point and indicates that the mobile aggregation node needs to be satisfied with the path corresponding to the effective communication range of each sensor monitoring node and the mobile aggregation node, and the range is a circle centered onxi and the effective communication radius is r.(3)
Expressions 3 and 4 represent the access constraints of each satisfactory solution point. On the flight line of the mobile sink node, there is only one line that leaves and enters each satisfactory solution point.(4)
Expression 5 represents the selected matrix of the road section, with 1 for selection and 0 for unchecked.


## 3. Path Optimization Algorithm

In view of the above analysis, it can be seen that the main problem of the shortest path planning of mobile sink nodes is the need to determine the location of best stop points in the wireless signal coverage range of each node and their access order (that is, the order in which the data of each monitoring node is extracted). In this paper, the problem is divided into three steps: one is to cluster the nodes through the dynamic clustering algorithm and select the cluster head nodes, the other is to determine the access order of each cluster head node, and the third is to determine the location of each optimal stop point.


### 3.1. Prioritization Scheme

#### 3.1.1. ImprovedK-Means Clustering Algorithm

In order to divide the nodes in the network into clusters evenly and balance the energy consumption of the network and the cluster heads of each cluster, we use the dynamic clustering algorithm to cluster the nodes in the monitoring area.In the practical application, theK-means algorithm is simple and practical and has higher efficiency with respect to the clustering algorithm such as neighbor clustering and fuzzy clustering. The K-means algorithm is based on minimizing the clustering function [25], and the clustering function is defined as(2)Jj=∑i=1NjXi−Zj2,Xi∈Sj,where Sj is the J cluster set, Zj is a clustering center, and Nj is the number of samples contained in the J cluster set and the selection of the cluster center should minimize Jj, so ∂Jj/∂Zj = 0, so(3)∂∂Zj∑i=1NXi−Zj2=0,Zj=1Nj∑i=1NjXi.The algorithm flow is as follows:(1)
OptionalK initial clustering centers: Z11,Z21,…,Zk1(2)
According to the principle of minimum distance (Euclidean distance), the remaining samples are assigned to one of theK clustering centers(3)
To getZjk+1, j = 1, 2, …, k(4)
IfZjk+1≠Zjk, then go back to (2) reclassify the samples and repeat the iterative calculation until Zjk+1=Zjk, the algorithm converges, results are calculated and retainedHowever, the final clustering results of theK-means algorithm will be affected by the location and number of the initial clustering center, and it is easy to converge to the local optimal rather than the global optimum. Therefore, we use the binary K-means algorithm, which can overcome the convergence of the K-means clustering algorithm to the local optimal. The basic idea is that first, all points are treated as a cluster, clustering is performed (K = 2), and then the cluster that can minimize the sum of error squares (SES) is selected to be divided (K = 2), until the number of clusters is equal to the number specified by us [26–29]. The region is divided into K clusters by the dynamic clustering algorithm; then, with energy as the competitive weight, the node with the highest energy in each cluster is selected as the cluster head node.


#### 3.1.2. Determine the Order of Access to Nodes

In the research and discussion of analyzing the data extraction order of each monitoring node, it can be classified as a travel dealer problem [30, 31], because the coverage area of the wireless signal is not considered at this time. At the same time, for the following research, the access order of the monitoring node is found; that is to say, the access sequence of the best stop point corresponding to the monitoring node is found.Through the analysis, it can be seen that the path planning of the UAV is the traversal optimal path problem in the discrete area [32]. Therefore, when determining the order of extracting the data from each monitoring node, the ant colony algorithm [33] is used to realize the optimal path planning of the mobile sink node, and the line here is presented as the connection of each sensor monitoring node, and the access order of the node is also determined.In the above analysis, the ant colony algorithm is used to plan the flight path, and the access sequence of node data extraction is determined, as shown in Figure3. Therefore, when solving the shortest line planning of the mobile sink node considering the coverage of wireless signal, the preliminary line planning and access sequence are obtained according to the ant colony algorithm, and then the access order of best stop points is determined. In this paper, according to the constraint that the access node is 1, a monitoring node will correspond to the best stop point, so the access order of the monitoring node is determined; that is, the access order of the best stop point is obtained. At this point, we can classify it as a simplified NP problem [34]. In the next step, a suitable and feasible method is needed to solve the position of the best stop point.Figure 3
An example of path planning with ant colony algorithm regardless of signal range.


#### 3.1.3. Determination of Best Stop Points

The position of the best stop point needs not only qualitative analysis but also a quantitative solution. Since the wireless signal coverage area of the sensor monitoring node and the mobile sink node is circular and the center of the circle is its own position, According to the preliminary planning of the flight line in the previous section, a preliminary schematic diagram containing the coverage of the wireless signal can be obtained, as shown in Figure4:Figure 4
An example of considering node wireless signal coverage.Combined with the problem model diagram and the requirement for the quantitative solution of best stop points, an angular bisection method is proposed to solve the specific position of satisfactory solution points. The specific implementation methods are as follows:Starting from the preliminary path line diagram planned by the ant colony algorithm,L is used to represent the distance sum of the initially planned path, and there is(4)L=l0+l1+l2+⋯+ln,where l0 is the section of the road x0,x1, l1 is the section of the road x1,x2, l2 is the section of the road x2,x3, and ln is the section of the road xn,x0Bisect the angle (the inferior angle) which is formed by two paths across the center of a node. And extend to the intersection of the boundary of the wireless signal coverage area, at which point of intersection is identified as the best stop point, and the intuitive effect is shown in Figure5:Figure 5
Angular bisection line to solve best stop point diagram.And then cross pointx0 to make the angular bisection of clip 2φ0 between l0 and ln, the extension line of the angular bisector intersects the communication boundary of point x0 at point y0, in the same manner, cross point x1 to make the angular bisection of angle 2φ1 between l0 and l1, the extension line of the angular bisector intersects the communication boundary of point x1 at point y1 and connects points y0 and x1 and points y0 and point y1. At this point, the first optimized line segment with best stop point connection can be reached, that is, the path of the final planning for the mobile sink node after considering the wireless signal coverage area. s0 is the line segment connecting points y0 and y1, and φ1=θ1+θ1′. As shown in Figure 5, at this point, the length of s0 can be expressed:(5)s0=d02+r2−2rd0cosθ1′,d02=l02+r2−2rl0cosφ0,cosθ1=l02+d02−r22l0d0.The simultaneous formula can be obtained:(6)cosθ1=l0−rcosφ0d0.Becauseφ1=θ1+θ1′,(7)θ1′=φ1−arccosl0−rcosφ0d0,cosθ1′=l0−rcosφ0d0cosφ1+sinφ11−l0−rcosφ0d02.So we can figure out the length ofS0:(8)s0=d02+r2−2rd0l0−rcosφ0d0cosφ1+sinφ11−l0−rcosφ0d02.In the same way, there is(9)s1=d12+r2−2rd1cosθ2′,d12=l12+r2−2rl1cosφ1,cosθ2=l12+d12−r22l1d1,s1=d12+r2−2rd1l1−rcosφ1d1cosφ2+sinφ21−l1−rcosφ1d12.of whichφ2=θ2+θ2′.In the end, there are(10)sn−1=dn−12+r2−2rdn−1ln−1−rcosφn−1dn−1cosφn+sinφn1−ln−1−rcosφn−1dn−12,sn=dn2+r2−2rdnln−rcosφndncosφ0+sinφ01−ln−rcosφndn2.After the last best stop node is obtained, it is necessary to return to the position of the original node. Therefore, for any line segment connected by best stops points, it can be obtained by making angular bisection of the angle formed by each line segment after the preliminary path diagram planned by the ant colony algorithm, and the length of each line segment can be obtained. This section mainly focuses on the flight path of UAV when extracting monitoring node data. Firstly, through the analysis of the traditional path planning algorithm, then according to the actual situation, the path system model diagram with wireless signal coverage area is constructed, and the reasonable system model and objective function are established. Then the solution is put forward, the angular bisection method is introduced to quantitatively calculate the position of the optimal stop point, and the rationality and feasibility of the method are proved by formula derivation.


### 3.2. Simulation of Path Optimization Results

In this part, we simulate and analyze the above optimization scheme. The main parameters and their values of the simulation are given in Table1.Table 1
Simulation parameter.
Parameter name
Parameter values
Number of nodes (N)
100
Clustering quantity (K)
10
Cluster head proportion (P)
0.1
Heuristic factor (α)
1
Expectation heuristic factor (β)
5
Information intensity (Q)
500
Pheromone volatile factor (η)
0.5
Number of ant colonies (m)
18
Communication radius (r)
15 mFirst, we randomly deploy 100 monitoring nodes in the monitoring area, as shown in Figure6. Then, the improved K-means dynamic clustering algorithm is used to cluster the 100 nodes, and the nodes with the largest remaining energy in the cluster are used as cluster head nodes. The clustering results and cluster head selection results are shown in Figure 7.Figure 6
Node distribution.Figure 7
Selection of cluster and cluster head.After determining the cluster head node, then the ant colony algorithm is used to plan the path of the ten cluster head nodes according to the position of the ten cluster head nodes, as shown in Figure8 and the average path distance and final collection of the iteration are optimized for the given ten nodes by the algorithm at this time. The shortest path of convergence is shown in Figure 9.Figure 8
Path that does not initially consider wireless signal coverage.Figure 9
Average distance and shortest distance.According to the analysis in the previous section, after considering the coverage of the wireless signal of the node, the preliminary lines of the ten cluster head nodes are obtained, as shown in Figure10.Figure 10
Cluster head node wireless signal coverage.The path optimization of the ten cluster head nodes is carried out again after the introduction of the angle bisection method. The optimization results are shown in Figures11and 12.Figure 11
Optimal diagram of angular bisection path.Figure 12
Average distance and shortest distance after optimization.Through the comparison of the simulation results of Figures9 and 12, it can be seen that the shortest distance of the path is 695.3 m without considering the wireless signal coverage, and the final distance of the path replanned by the angular bisection method is 602.1 m without considering the wireless signal coverage area. Then, we simulated the path optimization of different clustering results and obtained the results in Table 2 and Figure 13.Table 2
Comparison of path simulation results atr = 15 m.
Number of cluster heads (r = 15 m)
Traditional distance (m)
Optimized distance (m)
Optimization degree (%)
10
684.2
581.6
15
10
736.7
617.6
16
10
767.4
636.9
17Figure 13
Comparison of path length before and after optimization.From the above results, we can see that it is feasible to use the angular bisection method to optimize the path according to the characteristics of wireless signal coverage (where the position of the ten nodes is set in the simulation, and the radius of the wireless signal coverage arear is 15 m when the path is planned by the angular bisection method, the value of r is measured by the wireless communication module, and the size of r is measured by the hardware of the wireless module).


### 3.3. Verification of Experimental Results

According to the simulation results, the actual test of the scheme is carried out to verify the reliability of data collection. The workflow of data collection is shown in Figure14.Figure 14
Data collection flowchart.Due to the limited experimental conditions, we select the representative temperature and PH value as a monitoring index. The detection range of the DS18B20 temperature sensor with waterproof type is 55–125. The detection accuracy is 0.5. We used theE-201-C PH composite electrode, and its detection range is 0–14. The physical diagram is shown in Figure 15.Figure 15
Physical image of UAV test.The whole test process is carried out in the visual environment on the edge of the water area, and the test distance is widened continuously during the test process. Through the test of the reception of 1000 packets, the test results are shown in Table3. It can be seen from the table that, with the increase of test distance, the packet loss rate and packet error rate will also increase, and the transmission quality cannot be guaranteed after more than 30 m and basically cannot be transmitted after 40 m, so the distance should be controlled within 20 m when deploying the node, which can meet the requirements of data transmission.Table 3
Test results of communication quality.
Distance (m)
Number of packets sent
Number of packets lost
Packet loss rate
10
1000
0
0
15
1000
0
0
20
1000
1
0.001
25
1000
23
0.022
30
1000
101
0.121
35
1000
382
0.394
40
1000
1000
1Data are collected every 30 minutes of the system, and statistical analysis of the experimental data is carried out to obtain the experimental value and the actual measurement value of the system (Table4). The results show that the temperature error is between 0.81% and 1.24%, and the error range is reasonable. Therefore, the system can collect the data of the water area monitoring more accurately.Table 4
Comparison of the experimental and actual measured values of the system.
Acquisition time
Average measurement value °C/pH
Actual value °C/pH
Fractional error (%)
14 : 00
24.5/8.1
24.7/8.2
0.81/1.22
14 : 30
24.5/8.1
24.7/8.2
0.81/1.22
15 : 00
24.5/8.2
24.7/8.2
0.81/1.22
15 : 30
24.5/8.1
24.6/8.2
0.47/1.22
16 : 00
24.5/8.1
24.7/8.2
0.81/1.22
16 : 30
24.1/7.9
24.3/8.0
0.82/1.25
17 : 00
23.9/7.9
24.2/8.0
1.24/1.25


## 3.1. Prioritization Scheme

### 3.1.1. ImprovedK-Means Clustering Algorithm

In order to divide the nodes in the network into clusters evenly and balance the energy consumption of the network and the cluster heads of each cluster, we use the dynamic clustering algorithm to cluster the nodes in the monitoring area.In the practical application, theK-means algorithm is simple and practical and has higher efficiency with respect to the clustering algorithm such as neighbor clustering and fuzzy clustering. The K-means algorithm is based on minimizing the clustering function [25], and the clustering function is defined as(2)Jj=∑i=1NjXi−Zj2,Xi∈Sj,where Sj is the J cluster set, Zj is a clustering center, and Nj is the number of samples contained in the J cluster set and the selection of the cluster center should minimize Jj, so ∂Jj/∂Zj = 0, so(3)∂∂Zj∑i=1NXi−Zj2=0,Zj=1Nj∑i=1NjXi.The algorithm flow is as follows:(1)
OptionalK initial clustering centers: Z11,Z21,…,Zk1(2)
According to the principle of minimum distance (Euclidean distance), the remaining samples are assigned to one of theK clustering centers(3)
To getZjk+1, j = 1, 2, …, k(4)
IfZjk+1≠Zjk, then go back to (2) reclassify the samples and repeat the iterative calculation until Zjk+1=Zjk, the algorithm converges, results are calculated and retainedHowever, the final clustering results of theK-means algorithm will be affected by the location and number of the initial clustering center, and it is easy to converge to the local optimal rather than the global optimum. Therefore, we use the binary K-means algorithm, which can overcome the convergence of the K-means clustering algorithm to the local optimal. The basic idea is that first, all points are treated as a cluster, clustering is performed (K = 2), and then the cluster that can minimize the sum of error squares (SES) is selected to be divided (K = 2), until the number of clusters is equal to the number specified by us [26–29]. The region is divided into K clusters by the dynamic clustering algorithm; then, with energy as the competitive weight, the node with the highest energy in each cluster is selected as the cluster head node.


### 3.1.2. Determine the Order of Access to Nodes

In the research and discussion of analyzing the data extraction order of each monitoring node, it can be classified as a travel dealer problem [30, 31], because the coverage area of the wireless signal is not considered at this time. At the same time, for the following research, the access order of the monitoring node is found; that is to say, the access sequence of the best stop point corresponding to the monitoring node is found.Through the analysis, it can be seen that the path planning of the UAV is the traversal optimal path problem in the discrete area [32]. Therefore, when determining the order of extracting the data from each monitoring node, the ant colony algorithm [33] is used to realize the optimal path planning of the mobile sink node, and the line here is presented as the connection of each sensor monitoring node, and the access order of the node is also determined.In the above analysis, the ant colony algorithm is used to plan the flight path, and the access sequence of node data extraction is determined, as shown in Figure3. Therefore, when solving the shortest line planning of the mobile sink node considering the coverage of wireless signal, the preliminary line planning and access sequence are obtained according to the ant colony algorithm, and then the access order of best stop points is determined. In this paper, according to the constraint that the access node is 1, a monitoring node will correspond to the best stop point, so the access order of the monitoring node is determined; that is, the access order of the best stop point is obtained. At this point, we can classify it as a simplified NP problem [34]. In the next step, a suitable and feasible method is needed to solve the position of the best stop point.Figure 3
An example of path planning with ant colony algorithm regardless of signal range.


### 3.1.3. Determination of Best Stop Points

The position of the best stop point needs not only qualitative analysis but also a quantitative solution. Since the wireless signal coverage area of the sensor monitoring node and the mobile sink node is circular and the center of the circle is its own position, According to the preliminary planning of the flight line in the previous section, a preliminary schematic diagram containing the coverage of the wireless signal can be obtained, as shown in Figure4:Figure 4
An example of considering node wireless signal coverage.Combined with the problem model diagram and the requirement for the quantitative solution of best stop points, an angular bisection method is proposed to solve the specific position of satisfactory solution points. The specific implementation methods are as follows:Starting from the preliminary path line diagram planned by the ant colony algorithm,L is used to represent the distance sum of the initially planned path, and there is(4)L=l0+l1+l2+⋯+ln,where l0 is the section of the road x0,x1, l1 is the section of the road x1,x2, l2 is the section of the road x2,x3, and ln is the section of the road xn,x0Bisect the angle (the inferior angle) which is formed by two paths across the center of a node. And extend to the intersection of the boundary of the wireless signal coverage area, at which point of intersection is identified as the best stop point, and the intuitive effect is shown in Figure5:Figure 5
Angular bisection line to solve best stop point diagram.And then cross pointx0 to make the angular bisection of clip 2φ0 between l0 and ln, the extension line of the angular bisector intersects the communication boundary of point x0 at point y0, in the same manner, cross point x1 to make the angular bisection of angle 2φ1 between l0 and l1, the extension line of the angular bisector intersects the communication boundary of point x1 at point y1 and connects points y0 and x1 and points y0 and point y1. At this point, the first optimized line segment with best stop point connection can be reached, that is, the path of the final planning for the mobile sink node after considering the wireless signal coverage area. s0 is the line segment connecting points y0 and y1, and φ1=θ1+θ1′. As shown in Figure 5, at this point, the length of s0 can be expressed:(5)s0=d02+r2−2rd0cosθ1′,d02=l02+r2−2rl0cosφ0,cosθ1=l02+d02−r22l0d0.The simultaneous formula can be obtained:(6)cosθ1=l0−rcosφ0d0.Becauseφ1=θ1+θ1′,(7)θ1′=φ1−arccosl0−rcosφ0d0,cosθ1′=l0−rcosφ0d0cosφ1+sinφ11−l0−rcosφ0d02.So we can figure out the length ofS0:(8)s0=d02+r2−2rd0l0−rcosφ0d0cosφ1+sinφ11−l0−rcosφ0d02.In the same way, there is(9)s1=d12+r2−2rd1cosθ2′,d12=l12+r2−2rl1cosφ1,cosθ2=l12+d12−r22l1d1,s1=d12+r2−2rd1l1−rcosφ1d1cosφ2+sinφ21−l1−rcosφ1d12.of whichφ2=θ2+θ2′.In the end, there are(10)sn−1=dn−12+r2−2rdn−1ln−1−rcosφn−1dn−1cosφn+sinφn1−ln−1−rcosφn−1dn−12,sn=dn2+r2−2rdnln−rcosφndncosφ0+sinφ01−ln−rcosφndn2.After the last best stop node is obtained, it is necessary to return to the position of the original node. Therefore, for any line segment connected by best stops points, it can be obtained by making angular bisection of the angle formed by each line segment after the preliminary path diagram planned by the ant colony algorithm, and the length of each line segment can be obtained. This section mainly focuses on the flight path of UAV when extracting monitoring node data. Firstly, through the analysis of the traditional path planning algorithm, then according to the actual situation, the path system model diagram with wireless signal coverage area is constructed, and the reasonable system model and objective function are established. Then the solution is put forward, the angular bisection method is introduced to quantitatively calculate the position of the optimal stop point, and the rationality and feasibility of the method are proved by formula derivation.


## 3.1.1. ImprovedK-Means Clustering Algorithm

In order to divide the nodes in the network into clusters evenly and balance the energy consumption of the network and the cluster heads of each cluster, we use the dynamic clustering algorithm to cluster the nodes in the monitoring area.In the practical application, theK-means algorithm is simple and practical and has higher efficiency with respect to the clustering algorithm such as neighbor clustering and fuzzy clustering. The K-means algorithm is based on minimizing the clustering function [25], and the clustering function is defined as(2)Jj=∑i=1NjXi−Zj2,Xi∈Sj,where Sj is the J cluster set, Zj is a clustering center, and Nj is the number of samples contained in the J cluster set and the selection of the cluster center should minimize Jj, so ∂Jj/∂Zj = 0, so(3)∂∂Zj∑i=1NXi−Zj2=0,Zj=1Nj∑i=1NjXi.The algorithm flow is as follows:(1)
OptionalK initial clustering centers: Z11,Z21,…,Zk1(2)
According to the principle of minimum distance (Euclidean distance), the remaining samples are assigned to one of theK clustering centers(3)
To getZjk+1, j = 1, 2, …, k(4)
IfZjk+1≠Zjk, then go back to (2) reclassify the samples and repeat the iterative calculation until Zjk+1=Zjk, the algorithm converges, results are calculated and retainedHowever, the final clustering results of theK-means algorithm will be affected by the location and number of the initial clustering center, and it is easy to converge to the local optimal rather than the global optimum. Therefore, we use the binary K-means algorithm, which can overcome the convergence of the K-means clustering algorithm to the local optimal. The basic idea is that first, all points are treated as a cluster, clustering is performed (K = 2), and then the cluster that can minimize the sum of error squares (SES) is selected to be divided (K = 2), until the number of clusters is equal to the number specified by us [26–29]. The region is divided into K clusters by the dynamic clustering algorithm; then, with energy as the competitive weight, the node with the highest energy in each cluster is selected as the cluster head node.


## 3.1.2. Determine the Order of Access to Nodes

In the research and discussion of analyzing the data extraction order of each monitoring node, it can be classified as a travel dealer problem [30, 31], because the coverage area of the wireless signal is not considered at this time. At the same time, for the following research, the access order of the monitoring node is found; that is to say, the access sequence of the best stop point corresponding to the monitoring node is found.Through the analysis, it can be seen that the path planning of the UAV is the traversal optimal path problem in the discrete area [32]. Therefore, when determining the order of extracting the data from each monitoring node, the ant colony algorithm [33] is used to realize the optimal path planning of the mobile sink node, and the line here is presented as the connection of each sensor monitoring node, and the access order of the node is also determined.In the above analysis, the ant colony algorithm is used to plan the flight path, and the access sequence of node data extraction is determined, as shown in Figure3. Therefore, when solving the shortest line planning of the mobile sink node considering the coverage of wireless signal, the preliminary line planning and access sequence are obtained according to the ant colony algorithm, and then the access order of best stop points is determined. In this paper, according to the constraint that the access node is 1, a monitoring node will correspond to the best stop point, so the access order of the monitoring node is determined; that is, the access order of the best stop point is obtained. At this point, we can classify it as a simplified NP problem [34]. In the next step, a suitable and feasible method is needed to solve the position of the best stop point.Figure 3
An example of path planning with ant colony algorithm regardless of signal range.


## 3.1.3. Determination of Best Stop Points

The position of the best stop point needs not only qualitative analysis but also a quantitative solution. Since the wireless signal coverage area of the sensor monitoring node and the mobile sink node is circular and the center of the circle is its own position, According to the preliminary planning of the flight line in the previous section, a preliminary schematic diagram containing the coverage of the wireless signal can be obtained, as shown in Figure4:Figure 4
An example of considering node wireless signal coverage.Combined with the problem model diagram and the requirement for the quantitative solution of best stop points, an angular bisection method is proposed to solve the specific position of satisfactory solution points. The specific implementation methods are as follows:Starting from the preliminary path line diagram planned by the ant colony algorithm,L is used to represent the distance sum of the initially planned path, and there is(4)L=l0+l1+l2+⋯+ln,where l0 is the section of the road x0,x1, l1 is the section of the road x1,x2, l2 is the section of the road x2,x3, and ln is the section of the road xn,x0Bisect the angle (the inferior angle) which is formed by two paths across the center of a node. And extend to the intersection of the boundary of the wireless signal coverage area, at which point of intersection is identified as the best stop point, and the intuitive effect is shown in Figure5:Figure 5
Angular bisection line to solve best stop point diagram.And then cross pointx0 to make the angular bisection of clip 2φ0 between l0 and ln, the extension line of the angular bisector intersects the communication boundary of point x0 at point y0, in the same manner, cross point x1 to make the angular bisection of angle 2φ1 between l0 and l1, the extension line of the angular bisector intersects the communication boundary of point x1 at point y1 and connects points y0 and x1 and points y0 and point y1. At this point, the first optimized line segment with best stop point connection can be reached, that is, the path of the final planning for the mobile sink node after considering the wireless signal coverage area. s0 is the line segment connecting points y0 and y1, and φ1=θ1+θ1′. As shown in Figure 5, at this point, the length of s0 can be expressed:(5)s0=d02+r2−2rd0cosθ1′,d02=l02+r2−2rl0cosφ0,cosθ1=l02+d02−r22l0d0.The simultaneous formula can be obtained:(6)cosθ1=l0−rcosφ0d0.Becauseφ1=θ1+θ1′,(7)θ1′=φ1−arccosl0−rcosφ0d0,cosθ1′=l0−rcosφ0d0cosφ1+sinφ11−l0−rcosφ0d02.So we can figure out the length ofS0:(8)s0=d02+r2−2rd0l0−rcosφ0d0cosφ1+sinφ11−l0−rcosφ0d02.In the same way, there is(9)s1=d12+r2−2rd1cosθ2′,d12=l12+r2−2rl1cosφ1,cosθ2=l12+d12−r22l1d1,s1=d12+r2−2rd1l1−rcosφ1d1cosφ2+sinφ21−l1−rcosφ1d12.of whichφ2=θ2+θ2′.In the end, there are(10)sn−1=dn−12+r2−2rdn−1ln−1−rcosφn−1dn−1cosφn+sinφn1−ln−1−rcosφn−1dn−12,sn=dn2+r2−2rdnln−rcosφndncosφ0+sinφ01−ln−rcosφndn2.After the last best stop node is obtained, it is necessary to return to the position of the original node. Therefore, for any line segment connected by best stops points, it can be obtained by making angular bisection of the angle formed by each line segment after the preliminary path diagram planned by the ant colony algorithm, and the length of each line segment can be obtained. This section mainly focuses on the flight path of UAV when extracting monitoring node data. Firstly, through the analysis of the traditional path planning algorithm, then according to the actual situation, the path system model diagram with wireless signal coverage area is constructed, and the reasonable system model and objective function are established. Then the solution is put forward, the angular bisection method is introduced to quantitatively calculate the position of the optimal stop point, and the rationality and feasibility of the method are proved by formula derivation.


## 3.2. Simulation of Path Optimization Results

In this part, we simulate and analyze the above optimization scheme. The main parameters and their values of the simulation are given in Table1.Table 1
Simulation parameter.
Parameter name
Parameter values
Number of nodes (N)
100
Clustering quantity (K)
10
Cluster head proportion (P)
0.1
Heuristic factor (α)
1
Expectation heuristic factor (β)
5
Information intensity (Q)
500
Pheromone volatile factor (η)
0.5
Number of ant colonies (m)
18
Communication radius (r)
15 mFirst, we randomly deploy 100 monitoring nodes in the monitoring area, as shown in Figure6. Then, the improved K-means dynamic clustering algorithm is used to cluster the 100 nodes, and the nodes with the largest remaining energy in the cluster are used as cluster head nodes. The clustering results and cluster head selection results are shown in Figure 7.Figure 6
Node distribution.Figure 7
Selection of cluster and cluster head.After determining the cluster head node, then the ant colony algorithm is used to plan the path of the ten cluster head nodes according to the position of the ten cluster head nodes, as shown in Figure8 and the average path distance and final collection of the iteration are optimized for the given ten nodes by the algorithm at this time. The shortest path of convergence is shown in Figure 9.Figure 8
Path that does not initially consider wireless signal coverage.Figure 9
Average distance and shortest distance.According to the analysis in the previous section, after considering the coverage of the wireless signal of the node, the preliminary lines of the ten cluster head nodes are obtained, as shown in Figure10.Figure 10
Cluster head node wireless signal coverage.The path optimization of the ten cluster head nodes is carried out again after the introduction of the angle bisection method. The optimization results are shown in Figures11and 12.Figure 11
Optimal diagram of angular bisection path.Figure 12
Average distance and shortest distance after optimization.Through the comparison of the simulation results of Figures9 and 12, it can be seen that the shortest distance of the path is 695.3 m without considering the wireless signal coverage, and the final distance of the path replanned by the angular bisection method is 602.1 m without considering the wireless signal coverage area. Then, we simulated the path optimization of different clustering results and obtained the results in Table 2 and Figure 13.Table 2
Comparison of path simulation results atr = 15 m.
Number of cluster heads (r = 15 m)
Traditional distance (m)
Optimized distance (m)
Optimization degree (%)
10
684.2
581.6
15
10
736.7
617.6
16
10
767.4
636.9
17Figure 13
Comparison of path length before and after optimization.From the above results, we can see that it is feasible to use the angular bisection method to optimize the path according to the characteristics of wireless signal coverage (where the position of the ten nodes is set in the simulation, and the radius of the wireless signal coverage arear is 15 m when the path is planned by the angular bisection method, the value of r is measured by the wireless communication module, and the size of r is measured by the hardware of the wireless module).


## 3.3. Verification of Experimental Results

According to the simulation results, the actual test of the scheme is carried out to verify the reliability of data collection. The workflow of data collection is shown in Figure14.Figure 14
Data collection flowchart.Due to the limited experimental conditions, we select the representative temperature and PH value as a monitoring index. The detection range of the DS18B20 temperature sensor with waterproof type is 55–125. The detection accuracy is 0.5. We used theE-201-C PH composite electrode, and its detection range is 0–14. The physical diagram is shown in Figure 15.Figure 15
Physical image of UAV test.The whole test process is carried out in the visual environment on the edge of the water area, and the test distance is widened continuously during the test process. Through the test of the reception of 1000 packets, the test results are shown in Table3. It can be seen from the table that, with the increase of test distance, the packet loss rate and packet error rate will also increase, and the transmission quality cannot be guaranteed after more than 30 m and basically cannot be transmitted after 40 m, so the distance should be controlled within 20 m when deploying the node, which can meet the requirements of data transmission.Table 3
Test results of communication quality.
Distance (m)
Number of packets sent
Number of packets lost
Packet loss rate
10
1000
0
0
15
1000
0
0
20
1000
1
0.001
25
1000
23
0.022
30
1000
101
0.121
35
1000
382
0.394
40
1000
1000
1Data are collected every 30 minutes of the system, and statistical analysis of the experimental data is carried out to obtain the experimental value and the actual measurement value of the system (Table4). The results show that the temperature error is between 0.81% and 1.24%, and the error range is reasonable. Therefore, the system can collect the data of the water area monitoring more accurately.Table 4
Comparison of the experimental and actual measured values of the system.
Acquisition time
Average measurement value °C/pH
Actual value °C/pH
Fractional error (%)
14 : 00
24.5/8.1
24.7/8.2
0.81/1.22
14 : 30
24.5/8.1
24.7/8.2
0.81/1.22
15 : 00
24.5/8.2
24.7/8.2
0.81/1.22
15 : 30
24.5/8.1
24.6/8.2
0.47/1.22
16 : 00
24.5/8.1
24.7/8.2
0.81/1.22
16 : 30
24.1/7.9
24.3/8.0
0.82/1.25
17 : 00
23.9/7.9
24.2/8.0
1.24/1.25


## 4. Conclusion

In this paper, a new mobile data collection scheme for WSN water monitoring is proposed, which combines UAV with WSN. According to the characteristics of the water monitoring network, the path planning problem of the mobile sink node in WSN is discussed. In view of the wireless signal coverage of nodes in WSN, the nodes are divided into clusters and the cluster head nodes are selected as the residence points of mobile sink nodes according to the remaining energy. Then, on the basis of the ant colony algorithm, the angular bisection method is added to find the best stop point in the coverage area, and the new path is replanned. The derivation and simulation results show that the optimal stop point position and the new path can be obtained, and the distance of the new path is shorter than that planned by the traditional algorithm. Finally, experiments are carried out to further verify the reliability of the proposed path planning scheme for collecting data.



---

*Source: 5781620-2019-11-25.xml*