# A Novel Data Forwarding Strategy for a Drone Delay Tolerant Network with Range Extension
## 4 Heuristic Flight Path Planning (HFPP)
When the drones charge their battery, \(e_{budget}\) increases and accordingly \(l_{max}\) increases. It should be noted that adding next waypoint to the path is subjected to not pass the assignment delivery due. Hence, it is guaranteed that data delivery will not cause over due to the consignments' shipment. Another important factor to every drone \(i\) should consider is \(\delta_{i}\) that implies the maximum delay that the drone can have until return to the origin base. This limits the use of charging waypoints to extend flight duration. Algorithm 1 show how this heuristic algorithm works upon a contact. It takes as input \(G\subset D\) that is the destinations of packets in exchange pool, \(L_{max}\) as maximum length of flight for the drone, and consignment's destination. It outputs a set of destinations associated with packets, charging stations, and a drone origin base to be met. In details, HFPP starts the flight path with adding the origin base to \(\mathbf{N}\) that represents the index of registered destination and \(d_{cons}\) that is the destination of carried assignment (see line 6). Then in lines 8-12, it adds the highest weighted destination node. Upon receiving new data packets and assigning weight to the packets, HFPP calls our modified TSP solver which is the extended work of [PERSON]'s heuristic [31] (see line 17) to return the cost of flight path for given destinations which have highest weights. If the flight path length is less than the maximum length of drone's flight \(L_{max}\), the selected destination (lines 8-12) remains as \(\mathbf{N}\) (see lines 18-25). However, if the time to live of any of the packets associated with a destination in the path expires before arriving or the opposite drone (where drone \(i\) is current drone and drone \(j\) is the opposite) can deliver it quicker or the added waypoint causes overdue consignment delivery, it is removed from the current drone's flight path (see line 21-23). Also, if the returned cost from TSP function is larger than \(L_{max}\), the nearby wireless charging station with respect to the location of latest destination is added to \(\mathbf{N}\) and then add the next destination (see lines 26-30). However, if the duration of flight for a current drone exceeds \(\delta_{\text{current}}\), the destination is removed from the flight path (line 18). As discussed earlier, we also modified the TSP solver to ensure that the consignment is delivered before the deadline. Please note that the main objective is to deliver the consignment and as a value-added service, data delivery is conducted. This implies that consignment delivery always should be guaranteed. Hence, in the modified algorithm, when the nearest destination of data is added as next destination, we compare the impact of such detour in delivery delay of the consignment. If it causes to overdue delivery, the nearest destination is removed as next destination and is replaced with \(d_{cons}\). Now, let us consider the following scenario where drones \(n_{1}\) and \(n_{2}\) departed from \(b_{2}\) and \(b_{1}\) respectively. Figure 1 shows that \(n_{1}\) is carrying a packet to be delivered in \(d_{6}\). However, \(d_{6}\) is far away from the base and costs 3.5 km (\(d_{4}\) to \(d_{6}\)) + 3.5 km (\(d_{6}\) to \(b_{2}\)) flight to reach the base. Also, drone \(n_{2}\) is carrying a packet to be delivered in \(d_{2}\) that is far away from the base \(b_{1}\). As we see in Figure 2, when the summary of exchange packets in the pool is considered, the packet with destination \(d_{1}\) that has the maximum weight is involved in TSP solver of both drones. The TSP outcome reveals that the delivery delay is smaller if the packet with destination \(d_{1}\) is carried by \(n_{1}\). This is because \(n_{1}\) has a shorter distance to \(d_{1}\). The next destination selection by drones is \(d_{7}\) with the weight of 1.7, that due to the shorter distance to \(n_{2}\), it will be added to its route.