# Gathering Big Data in Wireless Sensor Networks by Drone +
## 5 Heuristics for the GBD Problem
### Incremental Heuristic  
The Incremental Heuristic creates a drone tour at each loop iteration. The first tour \(R_{1}\) is composed of only one \(PDP\). Then, it performs the local search to improve \(R_{1}\) (described in Section 5.3). In the second iteration, the heuristic adds a new \(PDP\) to \(R_{1}\) in order to create the tour \(R_{2}\) (composed of two \(PDPs\)) and performs the local search again. In other words, at each iteration a new \(PDP_{j}\) is added to the tour (\(R_{i+1}=R_{i}\cup PDP_{j}\)), the local search is performed over this tour and \(T_{total}\) is calculated. The algorithm ends when the \(T_{total}\) value does not decrease further with the addition of a new \(PDP\) in the tour. The algorithm creates a weight \(w_{j}\) for each \(PDP\) in \(P_{grid}\). At each iteration, it chooses a \(PDP\) to add to \(R_{i}\) as the \(PDP\) with the highest \(w_{j}\). However, the chosen \(PDP\) must be at least \(2r\) away from the other \(PDPs\) in \(R_{i}\). If there is no \(PDP\) with this characteristic, the minimum distance will be divided by 2. Using this strategy, this algorithm avoids \(PDPs\) close to each other in \(R_{i}\). The weight \(w_{j}\) is calculated according to Equation (3):  
\[w_{j}=\sum_{h=1}^{z}\frac{hop_{h}}{h} \tag{3}\]  
Figure 4: **(a)** Example of Wireless Sensor Network (WSN) and (b) correspondent Connectivity Graph (CG). where \(hop_{h}\) is the number of sensor nodes in \(CG\) that are connected to the \(PDP\)\(p_{j}\) by edges with weight equal to \(h\), and \(z\) is the biggest weight of the edges that link \(PDP_{j}\) to the sensor nodes in \(CG\). Since the weights of the edges in \(CG\) correspond to the distance in hops between a sensor node and the drone over \(PDP_{j}\), the \(PDP\)s on crowded regions receive the highest weight. Figure 4(a) presents how to calculate the weight of each \(PDP\). As an example, the drone over the \(PDP_{1}\) uses one hop (direct communication) to communicate with two sensor nodes, two hops to communicate with one node, three hops to communicate with two nodes, and four hops to communicate with one sensor node. Hence, the weight of the \(PDP_{1}\) is \(w_{1}=\frac{2}{1}+\frac{1}{2}+\frac{2}{3}+\frac{1}{4}=3.41\). The Incremental algorithm works according to Algorithm 1. The lines 6 and 20 are not in the original Incremental algorithm. We added them to this pseudocode to show how to use the proposed algorithm. Incremental receives as parameters the set \(S\) with the locations of all sensor nodes, the set of all \(PDP\)s in \(P_{grid}\), the amount of data stored in each sensor node \(m\), the network bandwidth \(b\), and the drone speed _dspeed_. In line 2, the variable that will store the best \(T_{total}\) is initialized with infinity. In lines 3 and 4, the set forming the best drone tour \(P\) and the set with the data paths between sensor nodes and each hovering point in \(P\) are initialized to empty. In line 5, the variable _route_ also receives empty; it stores the tour created at each iteration. As aforementioned, the line 6 is not in the original Incremental algorithm. We put this line in the pseudocode to show how to use the proposed algorithm for Big Data Gathering During Drone Movement. In this line, we initialized the set of subsets of sensor nodes that have to send data to the drone when it is moving. The Connecting Graph (\(CG\)) and the Trip Graph (\(TG\)) are created in lines 7 and 8. The counter \(i\) is initialized with 0. It represents the amount of \(PDP\)s in the current solution. Line 10 initializes the set \(R_{i}\) to empty, which will be increased with a new \(PDP\) at each loop iteration. From line 11 to 28, there is a loop, so that each iteration creates a new solution with one more \(PDP\) than the last iteration. The line 12 includes in \(R_{i}\) the \(PDP\) returned by the function _NewPDP()_. This function chooses the \(PDP\) to be added. In line 13, the counter \(i\) is incremented. \(T_{total}\) is calculated from line 14 to line 18.