# Gathering Big Data in Wireless Sensor Networks by Drone +
## 5 Heuristics for the GBD Problem
### Incremental Heuristic
In line 19, the _LSearch()_ function is called to perform the Local Search algorithm (described in Section 5.3) in order to try to reduce the value of \(T_{total}\) calculated at each iteration. When this function finds a smaller \(T_{total}\), it also returns _route_, that is, the drone tour of the current iteration, and \(st\) as the graph with the data routes between every sensor nodes and the \(PDP\). In line 20, the \(T_{total}\) is recalculated but now considering the data gathering with the drone in motion. This calculation is not in the original Incremental algorithm, but it is used at this point to show how to call the proposed algorithm for Big Data Gathering During Drone Movement. From line 21 to 27, the algorithm evaluates if the current solution has a \(T_{total}\) value smaller than the best solution value found so far. Otherwise, the loop is finished. The _show_ function in line 29 reports \(P\) and \(S_{subsets}\) as results. On the original result, we added \(D_{mov}\) that represents the result of the algorithm proposed here. As an example, consider the sensor network presented by Figure 4(a), \(r=60\) m and the distance between two \(PDP\)s is 84 m. Figure 4(b) presents the first iteration, that creates \(R_{1}=\{PDP_{4}\}\), since the \(PDP_{4}\) has the largest weight \(w_{4}=4.83\). Figure 4(c) presents the second iteration, that creates \(R_{2}=\{PDP_{4},PDP_{2}\}\), that is, \(PDP_{2}\) has been added to \(R_{1}\) to form \(R_{2}\). \(PDP_{1}\) and \(PDP_{5}\) have weight greater than \(PDP_{2}\) (\(w_{1}=3.41\), \(w_{5}=4.33\)); however, they were not added to \(R_{1}\) since they are at distances less than \(2r\). Figure 5: Example of how the Incremental Algorithm works. (**a**) Sensor nodes, \(PDPs\) and possible direct communication between two sensor nodes and between sensor nodes and the drone hovering each \(PDP\). It also shows how to calculate the weights of each \(PDP\). (**b**) First tour (\(R_{1}=\{PDP_{4}\}\)) created at the first loop iteration. \(PDP_{4}\) has the biggest weight. (**c**) Second tour (\(R_{2}=\{PDP_{2},PDP_{4}\}\)) created at the second loop interaction. \(PDP_{1}\) and \(PDF_{3}\) were not included to \(R_{2}\) because they are less then \(2r\) from \(PDP_{1}\). ```
1:procedureIncremental(\(S\), \(P_{\textit{grid}},m,b\), \(\textit{d}\textit{speed}\))
2:\(\textit{besttime}\leftarrow\infty\)
3:\(P\longleftarrow\varnothing\)
4:\(S_{\textit{subsets}}\longleftarrow\varnothing\)
5:\(\textit{route}\longleftarrow\varnothing\)
6:\(D_{\textit{move}}\longleftarrow\varnothing\)
7:\(\textit{CG}\longleftarrow\textit{CreateCG}(S,P_{\textit{grid}})\)
8:\(\textit{TG}\longleftarrow\textit{CreateTG}(P_{\textit{grid}})\)
9:\(i\longleftarrow\varnothing\)
10:\(R_{i}\longleftarrow\varnothing\)
11:while\(i\mid\mid P_{\textit{grid}}\)do
12:\(R_{i+1}\longleftarrow R_{i}\cup\{\textit{NewPDP}(\textit{CG},R_{i},\textit{TG})\}\)
13:\(i\longleftarrow i+1\)
14:\(st\longleftarrow\textit{SpanningTree}(R_{i},\textit{CG})\)
15:\(T_{\textit{allocating}}\longleftarrow\textit{CollectingTime}(st,d,b)\)
16:\(route\longleftarrow TSP(R_{i},\textit{TG})\)
17:\(T_{\textit{trip}}\longleftarrow\textit{TripTime}(route,\textit{TG},\textit{d} \textit{speed})\)
18:\(T_{\textit{total}}\longleftarrow T_{\textit{allocating}}+T_{\textit{trip}}\)
19:\(T_{\textit{total}}\longleftarrow\textit{LSarch}(R_{i},\textit{CG},\textit{TG},d, \textit{best},\textit{route})\)
20:\(T_{\textit{total}}\longleftarrow\textit{CreateSubsets}(P,S,d_{\textit{ moved}},b,m,r,\textit{kD}_{\textit{move}})\)
21:if\(\textit{Track}\)\(<\)\(\textit{besttime}\)then
22:\(\textit{besttime}\longleftarrow\textit{T}_{\textit{total}}\)
23:\(S_{\textit{subsets}}\longleftarrow st\)
24:\(P\longleftarrow\textit{route}\)
25:else
26:\(\textit{break}\)
27:endif
28:endwhile
29:\(\textit{show}(P,S_{\textit{subsets}},D_{\textit{move}})\)
30:endprocedure
```  
**Algorithm 1** Incremental Heuristic.