# Gathering Big Data in Wireless Sensor Networks by Drone +
## 5 Heuristics for the GBD Problem
### Decremental Heuristic
Right after, Incremental checks and stores if \(T_{total}\) is the smallest one calculated so far (lines 25 to 31 and removes one \(PDP\) from \(R_{i}\) to create the next solution \(R_{i-1}\) (line 32). If \(T_{total}\) is greater than the best value found so far, the loop finishes in line 30. The algorithm returns the best solution found in line 35. As an example, lets start with the graph \(st\) presented by Figure 6a. It has the shortest paths between each sensor node and a \(PDP\). This graph was created from the Connecting Graph presented by Figure 4b. First, the Decremental heuristic creates the tour \(R_{3}=\{PDP_{1},PDP_{3},PDP_{4}\}\), such as presented by Figure 6b. \(PDP_{2}\) was not considered because it has no edge connected to it. The first loop iteration removes \(PDP_{4}\) and an edge connecting this \(PDP\) to a sensor node. Another edge is included in the graph to keep the WSN connected. Since both edges have weight 1, the impact of the removal of \(PDP_{4}\) is 0. Figure 6c presents the resulting graph. \(PDP_{1}\) is removed in the second loop iteration. As shown in Figure 6d, \(PDP_{1}\) has an impact of removal equal to 1 (the smallest) since the heuristic replaces an edge with weight 1 with another with weight 2. The heuristic stops in the next iteration. The weights of the inserted edges are obtained in the Connecting Graph presented by Figure 4b. Figure 6: Example of the Decremental Heuristic. (**a**) The graph representing the shortest path (in hops) between each sensor node and a \(PDP\). (**b**) The first tour \(R_{3}=\{PDP_{1},PDP_{3},PDP_{4}\}\). \(PDP_{2}\) was removed because it has no edge connecting it to a sensor node. (**c**) The second tour \(R_{2}=\{PDP_{1},PDP_{3}\}\). \(PDP_{4}\) was removed because its impact removal is the smallest, i.e., 0. (**d**) The third tour \(R_{1}=\{PDP_{1}\}\). \(PDP_{3}\) was removed because its impact of removal is the smallest, i.e., 1. ```
1:procedureDecremental(\(S,P_{grid},m,b,\textit{dspeed}\))
2:\(\textit{besttime}\longleftarrow\infty\)
3:\(P\longleftarrow\oslash\)
4:\(S_{\textit{subshots}}\longleftarrow\oslash\)
5:\(D_{\textit{mw}}\longleftarrow\oslash\)
6:\(CG\longleftarrow\textit{CreateCG}(S,P_{grid})\)
7:\(TG\longleftarrow\textit{CreateTG}(g_{\textit{grid}})\)
8:\(st\longleftarrow\textit{SpanningTree}(P_{grid},CG)\)
9:\(i\longleftarrow 0\)
10:\(R_{i}\longleftarrow\oslash\)
11:foreach\(v\in P_{grid}\)do
12:if\(v\in st\)then
13:\(R_{i}\longleftarrow R_{i}\cup\{v\}\)
14:\(i\longleftarrow i+1\)
15:endif
16:endfor
17:while\(|R_{i}|>0\)do
18:\(st\longleftarrow\textit{SpanningTree}(R_{i},CG)\)
19:\(T_{\textit{calculating}}\longleftarrow\textit{CollectingTime}(st,d,b)\)
20:\(route\longleftarrow TSP(R_{i},TG)\)
21:\(T_{\textit{trip}}\longleftarrow\textit{TriPTime(route,TG,dspeed)}\)
22:\(T_{\textit{total}}\longleftarrow T_{\textit{calculating}}+T_{\textit{trip}}\)
23:\(T_{\textit{total}}\longleftarrow\textit{LSarch}(R_{i},CG,TG,d,\textit{ Rest},\textit{kroute})\)
24:\(T_{\textit{total}}\longleftarrow\textit{CreateSubsets}(P,S,d_{\textit{speed}},b,m,r, \textit{kD}_{\textit{mw}})\)
25:if\(T_{\textit{total}}<\textit{besttime}\)then
26:\(\textit{besttime}\longleftarrow T_{\textit{total}}\)
27:\(S_{\textit{subshots}}\longleftarrow st\)
28:\(P\longleftarrow\textit{route}\)
29:else
30:\(\textit{break}\)
31:endif
32:\(R_{i}\longleftarrow R_{i}\setminus\{\textit{SmallRemovallImpact}(R_{i},st)\}\)
33:\(i\longleftarrow i-1\)
34:endwhile
35:\(\textit{show}(P,S_{\textit{subshots}},D_{\textit{mw}})\)
36:endprocedure
```  
**Algorithm 2** Construction Phase: Decremental Heuristic.