Efficient Aerial Data Collection with UAV in Large-Scale Wireless Sensor Networks

3.2.1. The Distributed Node Location Based on Probability

The algorithm described as follows is RSSI based. Through abundant tests and static analysis, when the wireless signal strength is fixed, the relative distance between the unknown nodes and beacon nodes fits the normal distribution [20]. Figure 2(a) shows the probability distribution of relative distance between the unknown nodes and the beacon nodes when the signal strength is 70 (it is a relative value without unit). After fitting into the normal distribution function, the mean value of the normal distribution curve is 25 meters, as is shown in the figure. This means that when the signal strength is 70, the relative distance of 25 meters is more reliable. For different signal strength, the fitting results of relative distances vary. Figure 2(b) [22] shows the probability distribution of different signal strength that varies from 66 to 90.

OPEN IN VIEWER

Figure 2

(a) Probability distribution when signal is 70. (b) Probability distribution of different signal strength (figure source: [22]).

Based on the abovementioned probability distribution, the positioning of unknown nodes could use two beacon nodes at the same time to improve the accuracy of positioning. Figure 3(a) shows the process of two beacon nodes positioning one unknown node. S 1 and S 2 are beacon nodes. S 3 is the unknown node to be positioned. The location information of S 1 and S 2 that S 3 receives fits the Gaussian distribution. So S 3 is most likely to locate in the mean value of the Gaussian distribution. Thus, the location information of S 3 is identified, as is shown in Figure 3(b).

OPEN IN VIEWER

Figure 3

(a) Location of the unknown node. (b) The final position (figure source: [22]).

When the environment is the same, the normal distribution of signal strength and relative distance is fixed, which can be measured by its mean value and variance and then stored in the nodes that need to be positioned. If the environment where the nodes were deployed has changed, the nodes could change the corresponding mean value and variance to adapt to the new environment and get positioned accurately.

3.2.2. Algorithm Description

P is the location information of nodes, while C represents the constraint that the relative distance varies with the change of signal strength. Algorithm 1 gives a detailed description of the process of nodes positioning.

Algorithm 1: LOC.

In this algorithm, the key step is to calculate the value of constraint C (Line (7) to Line (13)). According to the different sources of location information, constraint C can be divided into two categories. The methods for calculating constraint C for these two categories are different. Hence, we have the following: 1.

If the location information comes from the beacon signal, then the value of C fits the Gaussian normal distribution.

The calculation of constraint C is specific to single piece of location information. The process of the whole algorithm is shown as follows: 1.

Firstly, visit all the unknown nodes and use global region to initialize the location information P of the node (Line (1)).

3.3.1. Grid Division

In the root grid P G , when 0 ≤ v , h < k , build a subgrid S G ( v , h ) . As long as 0 ≤ h < k , V L ( v ) denotes the collection of vertical lines of P G whose index modulus on k equals v. Similarly, as long as 0 ≤ h < k , H L ( h ) denotes the collection of horizontal line P G whose index modulus on k equals h. So, the vertical and horizontal lines of the subgrid S G ( v , h ) consist of V L ( v ) ∪ H L ( h ) .

For the fixed horizontal partitioning index v and vertical partitioning index h, the horizontal line and vertical line of S G ( v , h ) divide the global region into several quadrate regions with a side length of 2 R × h . Each of the quadrate regions is called a square region and is denoted by J. Any nonempty J containing one or more circular regions is denoted by D. Note that there are situations when the circular region is not completely contained in J. Define the intersection place of the circular region and J as the disk sector, D - S e c t o r . So D - S e c t o r = J ∩ D . Every circular region that is completely contained in J can be treated as a special kind of D - S e c t o r . So, in a nonempty J, there is one D - S e c t o r or more. The set D J ( v , h ) denotes all the D - S e c t o r contained in J. For different squares J and J ′ , D J ( v , h ) ∩ D J ′ ( v , h ) = ⌀ .

As is shown in Figure 4, divide the grid S G ( 0,0 ) when k = 2 , v = 0 , and h = 0 , and the grid has been divided into four squares— J 1 , J 2 , J 3 , and J 4 . The circular region D 3 crosses two squares, J 1 and J 2 , and is divided into two different disk sections, D - S e c t o r 1 and D - S e c t o r 2 . Also, the circular region D 4 is divided into two disk sections, D - S e c t o r 3 and D - S e c t o r 4 . So, in square D J 1 ( 0,0 ) = { D 1 , D 2 , D - S e c t o r 1 , D - S e c t o r 2 , D - S e c t o r 5 } . So, to calculate the minimum coverage of J 1 is to obtain the minimum coverage through full research of the set D J 1 0,0 . If a disk sector is chosen as the minimum coverage solution, the circular region that contains the disk section will be chosen as the answer. Based on this rule, when calculating the minimum coverage through grid division, this kind of situation might happen; as is shown in the figure, in J 1 , if D - S e c t o r 3 is chosen as the minimum coverage, then D 3 will be the solution. Similarly, in J 2 , to choose D - S e c t o r 2 as the minimum circle coverage solution is to choose D 4 as the minimum circle coverage solution. In reality, D 3 and D 4 are overlapping with each other. So, in a grid division, the circular region positioning on the grid line may cause the result that one grid division cannot obtain the optimum solution.

OPEN IN VIEWER

Figure 4

Grid subdivisions of S G ( 0,0 ) ( k = 2 , v = 0 , a n d h = 0 ) .

To obtain the needed optimum solution, several times of subgrid division are needed. When the value of k is given, the values of v and h are on the interval of [ 0 , k - 1 ] and there are k × k possibilities. O P T ( v , h ) denotes the optimum solution when the value of v , h is fixed and the subgrid is divided. Then, there are k × k optimum solutions and the smallest solution of all the optimum solutions is the final solution, O P T ′ ( v , h ) . Then, O P T ′ ( ν , h ) = m i n ( O P T ( ν , h ) ) ( 0 ≤ ν , h ≺ k ) .

This optimum solution is the minimum coverage solution in the circular region. After converting the circular region into the corresponding nodes, the current set of circular regions is converted into the corresponding set of nodes, that is, S m i n , and a position of corresponding node in S m i n will be an anchor point for UAV. Thus, the mission of finding the minimum coverage for aerial data collection is accomplished.

3.3.2. The Minimum Spanning Circle Algorithm

Algorithm 2 depicts the obtaining of the minimum coverage in one grid. This algorithm considers the nonempty square J as the input after calculating and outputting the minimum coverage D J of square J. In this algorithm, define set U as the collection of D - S e c t o r in J and now U contains all the elements in J. That is, U absolutely covers J. Count is the number of elements in the solution. U is the initial solution; then, the initial value of Count is the number of elements in U. Cyclically reduce the number of D - S e c t o r elements in U until the D - S e c t o r in U covers all the nodes in J and the number of D - S e c t o r cannot be reduced anymore. Then, U is the solution.

Algorithm 2: CALCOVER.

Algorithm 3 cites Algorithm 2. The main task of this algorithm is to accomplish the grid division of the whole region. And then use Algorithm 2 to calculate the minimum coverage of every nonempty square after the set of squares is obtained through division and combine all the minimum coverage of every square into global minimum coverage. Now, the grid still needs multiple times of division and each time global minimum coverage is obtained. In the end, the global minimum coverage containing the least nodes is the final solution. The key point of the algorithm is to obtain the nonempty square set G ( v , h ) for every group of v , h and to call Algorithm 2 for every J in G ( v , h ) to calculate the minimum coverage solution M J ( v , h ) for all the circular region set D J ( v , h ) in J. After the division of the grid, combine all M J ( v , h ) and remove the overlapped areas and leave the global minimum coverage M ( v , h ) of this grid division. Because there are errors in the minimum circle spanning during the grid division, first save the fixed value M ( v , h ) to the result set O P T . When all the global minimum coverage of all combinations of v , h is accomplished, take the global minimum coverage in the O P T which has the least circular regions as the final solution.

Algorithm 3: MINCOVER.

4.3.1. Paths in Square Areas

Because of the random nodes distribution, there could be some empty squares which would be ignored in the path planning. Based on the precedence principle, the other squares can obtain the sequential nonempty square set G s o r t in the primary flight path.

With the division of grid, node set S o p t would be decentralized into each nonempty square J ( J ∈ G s o r t ) . S J denotes the node set of square J, so S J ⊆ S o p t . In J, path-ordering is the local square path drawn by quick sorting algorithm and ordered in the primary flying direction of S J , and the corresponding sequential node set is denoted by S J s o r t .

Although S J s o r t concludes all nodes in J, for the whole path, H o u t and H i n in J are still not ideal. So, after obtaining S J s o r t , paired operators path optimization algorithm (Algorithm 5) would be transferred to determine the ingress node and out node of the square. Algorithm 4 has described the process of the square path planning and the whole path planning. This algorithm focuses on the traversal of square (Line (3) to Line (8)). During the loop operation, a square is chosen each time. By quick sorting algorithm, all H nodes in the present square J would be sorted in the primary flight path; then, Algorithm 5 is transferred. After Algorithm 5, it is possible to find that the ingress node and out node of a square are modified. So, the returned value can be merged into the whole path S s o r t .

Algorithm 4: SquarePlan.

Algorithm 5: IOPlan.

4.3.2. Optimum of the Paired Operators' Path

To optimize the distance from the present square to the next square, the concept of operator is introduced to determine the ingress node and out node of a square. The operator seeking the ingress node is defined as ingress operator denoted by f i n d I n ; the operator seeking the out node is defined as the out operator denoted by f i n d O u t . Suspicious set is the node set while working out the ingress node, which is denoted by P. The number of nodes in the suspicious set is defined as the capacity of a suspicious set defined by η. Ingress node and its nearby nodes form a suspicious set, defined as ingress suspicious set denoted by P i n . Out node and its nearby node formed a suspicious set, defined as out suspicious set denoted by P o u t . Thereby, the process of seeking ingress node is the process of f i n d I n seeking ingress node in P i n , and the process of seeking out node is the process of f i n d I n seeking out node in P o u t .

L ( H , H ′ ) is the flight path distance from node H to node H ′ . When H ∈ S J , H ′ ∈ S J ′ , and the flight path is from J to J ′ , L ( H , H ′ ) represents the flying distance from the present square to the next one. If L m i n ( H , H ′ ) represents the minimal distance, node H is the node H o u t sought by f i n d O u t . So, the process of f i n d I n and f i n d O u t seeking ingress node and out node should be collaboratively operated with the f i n d O u t of the present square and the f i n d I n of the next square to determine the ingress node and out node of a square. J f i n d O u t denotes the out operator of the present square, and J f i n d I n ′ denotes the ingress operator of the present square, so the combination of J f i n d O u t and J f i n d I n ′ is called paired operators, and P J o u t in corresponding square J and P J ′ i n in J is paired suspicious set.

The key point of paired operators seeking ingress and out node is to choose the right seeking way while guaranteeing the minimal distance when entering into the next square from the present square and improve the efficiency of the algorithm. Aimed at the position of suspicious set, the following will explain the seeking method of corresponding paired operators.

START-END is the suspicious set including ingress node and out node when the aircraft enters and exits from the whole area. In the whole area, entrance and exit mean the beginning and end of data collection, so there would be two suspicious sets: P s t a r t denotes the one at the beginning and P e n d denotes the one in the end. Lacking directly connected square, f i n d I n and f i n d O u t would see the node nearest boundary as the ingress and out node. As shown in Figure 6, the grid includes the sketch of P s t a r t and P e n d , and f i n d I n chooses H 1 as the ingress node while f i n d O u t chooses H 47 as the out node.

OPEN IN VIEWER

Figure 6

Workflow of FPPWR.

UP-DOWN is the paired suspicious set made up of two suspicious sets when the aircraft leaves for another line from the present line. If the present square is J, and the next line to be accessed is J ′ , P J o u t and P J ′ i n formed a paired suspicious set. The paired operators would sort nodes in P J o u t and P J ′ i n in the vertical direction and choose the bottom node in P J o u t as the out node of J and the top node in P J ′ i n as the ingress node of J ′ . As shown in Figure 6, the suspicious set made by P 3 o u t and P 4 i n is up-down suspicious set. f i n d O u t chooses H 16 in P 3 o u t as the out node. f i n d I n chooses H 17 in P 4 i n as the ingress node.

LEFT-RIGHT is the paired suspicious set made up of two suspicious sets when the aircraft moves from one square to the next square. In the function of paired operators, if the aircraft is from J to J ′ , the operator would choose the combination of nodes to make L ( H , H ′ ) ( H ∈ P J r i g h t , H ′ ∈ P J ′ l e f t ) get the minimal value. f i n d O u t chooses H as the out node of J. f i n d I n chooses H ′ as the ingress node of J ′ . As shown in Figure 6, P 2 o u t and P 3 i n form the left-right paired suspicious set. Paired operators choose H 10 as the out node of J and H 11 as the ingress node of J ′ .

After the out and ingress node of square J are determined, the ingress node would be modulated to the head of S J s o r t and the out node to the rear of S J s o r t , by which the path of a square is optimized.

4.6.1. Analysis of Time Consumption

When planning the path in different node scale, time consumed by the FPPWR algorithm is various. From the number of nodes and the time consumed in path planning in Figure 6, we can conclude the relationship between time consumption and number of nodes, shown in Figure 8(a).

OPEN IN VIEWER

Figure 8

(a) Time consumption. (b) Uniform contrast. (c) Nonuniform contrast.

From the figure, it is possible to find that the fewer the nodes, the less the time consumption of FPPWR. When the number of nodes is less than 3000, the time consumed is less than 1 ms; when the number of nodes increases, the time consumption increases linearly.

By contrasting with LKH algorithm and greedy algorithm, the time consumption between them has a huge difference, as shown in Figure 8(a). From the figure, when the number of nodes is less than 3000, the time consumption of these three algorithms is less, while FPPWR algorithm is the least time consuming. When the number of nodes is more than 3000, the time consumption of these three algorithms begins to show a huge difference, and the time consumption of LKH is the largest. From the figure, when the number of nodes reached 50000, the time consumption of LKH is 957820.4 ms, which is about eighty thousand times bigger than the time consumption of FPPWR. The reason for this huge difference is that LKH algorithm and greedy algorithm search the solution accessing target nodes within the global scope, aiming at less path distance, while FPPWR divides the global scope into square area using grid and searches the solution with Row-prior principle. From the experiment, we can conclude that when there are a very large number of sensor nodes in the network, FPPWR algorithm is more advantageous in time consumption of computing the path planning.

4.6.2. Analysis of the Path Distance

Since the minimal path distance can be obtained through heuristic algorithm, the distance obtained through heuristic algorithm is regarded as datum which is used to compare with other distances obtained by other algorithms. After calculating its specific value, we can draw the path distance and node number chart as in Figure 8(b).

From the chart, it is possible to find that when the number of nodes is small, the short distance can be obtained from both heuristic algorithm and greedy algorithm. However, with the number of nodes increasing greatly, the FPPWR algorithm and the other two algorithms have the same effect.

In conclusion, when the number of nodes increases, the consumption of time increases greatly in greedy algorithm and heuristic algorithm. When the number reached 5000, the time consumed by heuristic algorithm is 10 times that of greedy algorithm and thousands of times that of the FPPWR algorithm. Meanwhile, as for the path distance, with the number of nodes increasing, the result of the FPPWR algorithm is close to that of the heuristic algorithm. So, if the path planning is not required to be too accurate, grid division has more advantages than other algorithms.

However, the FPPWR algorithm requires the node to be deployed evenly. For the unevenly deployed nodes, the feasible solution can be obtained through the algorithm but this solution has no advantage in finding the path distance. How the unevenly deployed nodes affect the FPPWR algorithm will be shown in the experiment.

5.1.1. The Explanation of Basic Parameters

Table 2 shows the key parameters and notes in the simulation platform. All the parameters show the information of sensor network and nodes and deploy the corresponding simulation modules.

OPEN IN VIEWER

Table 2

Algorithm parameters of the FPPWR.

Name	Type	Node
Nodes	Integer	The number of sensor nodes in WSN
Deployment	Enumeration	The way of WSN deployment (manual, random, or with rules)
Coverage radius	Integer	The radius of the signal from sensors (meter)
Transmission rate	Float	The rate of the wireless communication (KB/s)
Acquisition rate	Integer	Sampling frequency (Byte/min)
UAV speed	Float	Speed of the UAV (m/s)
Sojourn time	Integer	The time staying on the top of the head nodes for collecting data (s)

5.1.2. The Effect of the Simulation Platform

The simulation platform is deployed according to the key parameters. Figure 10 shows the network coverage obtained when the network scale is 135 and the deployment is random and well-distributed.

OPEN IN VIEWER

Figure 10

The node coverage of simulation platform.

As is shown in Figure 10, simulation platform provides simulation network, minimal coverage, the path planning, and generation of NS2 script. Their functions are the following.

Simulation network: it generates needed sensor network according to the scale of the network and the deployment method, including ordinary nodes and movable sink nodes.

Minimal coverage: it uses the Minimum Spanning Circle Method to achieve the head nodes through transfer network, covering radius, and so forth.

Path planning: it cites the FPPWR algorithm to make quick path planning in accordance with the returned head nodes in minimal coverage.

Generation of NS2 script: it transfers the data collected by the aircraft and guided by FPPWR algorithm into TCL script and controls the simulation aircraft with sink node in NS2 WSN access node sequentially.

After the four processes, a TCL script would be generated in NS2. To achieve the simulation condition of aerial data collection in NS2, the experiment would track the parameters of received and transmitted data as well as the energy consumption and record the distance and time of the simulated aircraft. Figure 11 shows the simulation condition of sensor network in NS2 when the node scale is 135.

OPEN IN VIEWER

Figure 11

The simulation of network with NS2.

From Figure 11, when the time is 239.2 seconds, the sink node labeled 0 directly approaches the head node labeled 30 from the head node labeled 24 at a speed of 5 m/s. When moved to a head node, the sink node should stay for 20 seconds. Finally, at 1349.9, sink node stops moving, and the simulation network stops.