# Gathering Big Data in Wireless Sensor Networks by Drone +
## 5 Heuristics for the GBD Problem
### Decremental Heuristic  
At each iteration, the Decremental heuristic reduces by one the number of _PDPs_ in the tour compared to the previous iteration and calculates \(T_{\textit{total}}\). The loop finishes when the tour has no _PDPs_ or when \(T_{\textit{total}}\) increases if compared with the previous iteration. The first step of the Decremental heuristic is to create the tour \(R_{i}\) composed of all vertices of \(\textit{CG}\) that represents the _PDPs_ and has at least one edge connected to it. The variable \(i\) contains the amount of \(PDPs\) in \(R_{i}\). At each iteration, the algorithm removes a _PDP_ from the tour \(R_{i}\) to create the tour \(R_{i}-1\) and calculates \(T_{\textit{total}}\). For each \(R_{i}\), the algorithm creates a graph \(st\subseteq\textit{CG}\), whose vertices are the _PDPs_ in \(R_{i}\) and all sensor nodes. For each sensor node in \(st\), the algorithm creates an edge connecting this node to the closest \(PDP\). The weights of these edges are the distance in number of hops from every node to the \(PDP\). \(st\) represents the data paths of all sensor nodes and the drone hovering a \(PDP\). The heuristic chooses the \(PDP\) to be removed from \(R_{i}\) based on the _impact of removal_ on the value of \(T_{\textit{collecting}}\). When \(PDP_{j}\) is removed from \(R_{i}\), the edges connecting it to the sensor nodes in \(st\) also have to be removed. Hence, the nodes connected to \(PDP_{j}\) must be connected to other _PDPs_. Thus, \(st\) receives other edges from \(\textit{CG}\). The impact of removal is calculated by subtracting the sum of the new edges' weights from the sum of the weights of the removed edges. Algorithm 2 presents the pseudocode of this heuristic. It receives as parameters the set \(S\) with the locations of all sensor nodes, \(P_{\textit{grid}}\) the set of all _PDPs_, the amount of data stored in each sensor node \(m\), the links bandwidth \(b\), and the drone speed _dspeed_. In line 2, the variable _besttime_ is initialized with infinity. It will store the best \(T_{\textit{total}}\). In lines 3 and 4, the set forming the best drone tour \(P\) and the set with the data paths between sensor nodes and drone \(S_{\textit{subsets}}\) are initialized to empty. In line 5, the set of subsets of sensor nodes that have to send data to the drone when it is moving is initialized. This set is not part of the original Decremental algorithm. It is used in the proposed algorithm for Big Data Gathering During Drone Movement. The ConnectingGraph (\(CG\)) and the Trip Graph (\(TG\)) are created in lines 6 and 7. The _SpanningTree_() function is called in line 8. It creates \(st\), which is a graph with vertices representing the \(PDPs\) in the current tour (\(R_{i}\)) and all sensor nodes. This graph has an edge for each sensor node, which represents the smallest data path connecting each sensor node to a \(PDP\) in \(R_{i}\). In line 9, the counter \(i\) is initialized with 0. It represents the amount of \(PDPs\) in the current solution. In line 10, the set \(R_{i}\) is initialized to empty. It represents the current solution at each loop iteration. From line 11 to 16, there is a loop to create the first tour. It look at the graph \(st\) and adds to \(R_{i}\) only the \(PDPs\) connected to at least one sensor node. At the end of this loop, \(R_{i}\) has no vertex representing a \(PDP\) without edges and \(i\) has the amount of \(PDPs\) in \(R_{i}\). The lines from 17 to 28 are the main loop of the algorithm. At each iteration, it calculates \(T_{total}\) for the current solution \(R_{i}\) (lines 18-22), performs the Local Search to verify if \(T_{total}\) can be reduced (line 23), and calls \(CreateSubsets()\) (line 24) to find the sensor nodes that will send data to drone during its motion. This call is not in the original algorithm; it is used at this point to show how to use the proposed algorithm for Big Data Gathering During Drone Movement.