A Novel Data Forwarding Strategy for a Drone Delay Tolerant Network with Range Extension
<p>Original flight paths of two drones.</p> "> Figure 2
<p>Optimized flight paths of the two drones in <a href="#electronics-08-00659-f001" class="html-fig">Figure 1</a> based on Heuristic Flight Path Planning (HFPP).</p> "> Figure 3
<p>(<b>a</b>) delivery ratio of comparable schemes, (<b>b</b>) average data delivery delay of comparable schemes, when number of drones varies.</p> "> Figure 4
<p>Overhead ratio of comparable schemes when number of drones varies.</p> "> Figure 5
<p>(<b>a</b>) Average consignment delivery delay, and (<b>b</b>) average energy inefficiency, of HFPP when number of drones varies.</p> "> Figure 5 Cont.
<p>(<b>a</b>) Average consignment delivery delay, and (<b>b</b>) average energy inefficiency, of HFPP when number of drones varies.</p> ">
Abstract
:1. Introduction
- We fit wireless charging stations along the flight path to charge the drones for a short period in the case of meeting more nearby waypoints (packets’ destinations). This results in the data network to last longer with increased delivery ratio and reduced delay.
- We propose a Heuristic Flight Path Planning (HFPP) that finds an optimal flight path that minimizes delivery delay and maximizes delivery ratio. HFPP assigns a weight to every data packet’s destination and planning to include wireless charging stations followed by most weighted destinations along the path to increase flight duration and deliver more data. The weight is based on the packet’s remaining time to live, priority, and size to get the chance to be fit along the drone’s flight path.
- We compare the properties and effectiveness of HFPP against two well-known routing protocols namely Epidemic [8], and EBR and a flight planning algorithm [16] using a Java-based simulator called ONE [17]. The results show that HFPP delivers up to 33% more data packets as compared to the existing methods. Also, HFPP reduces data delivery delays up to 85% while overhead ratio is low.
2. Related Work
3. Problem Formulation
- There are v drones represented by the set , …, and q registered destinations including item buyers and data destinations indicated by , …, .
- Drones are responsible to pick up purchased items from m bases indicated by , …, that belong to different retail or logistic companies and deliver them to the registered destination in D.
- Every drone i has a maximum flight duration, , to return to the origin disregarding of the remaining energy. This parameter implies that there is another package to be picked up within time period for drone i. This parameter may change over the flight as the package may be allocated to another drone or being cancelled.
- There are k wireless charging stations represented by the set , …, that transfer up to 500 Watt.
- Each drone may stay on the charging pad for different time periods Recall, max time to return to the base for every drone i is regardless of the remaining energy.
- Charging stations are assumed to have enough wireless charging panels to avoid waiting time.
- Each drone has a maximum flying distance, , that is determined based on the remaining energy.
- For every packet i in the network, the priority of is assigned by the source, meaning how important is the packet. The value of is from 1 to 10 meaning maximum to minimum importance respectively.
- Every packet i has time to live, , that if it expires, the packet will be dropped from the buffer.
- Each drone has an infinite buffer space to store data packets.
- Drones stay within the communication range of sources, destinations, and other drones until all forwarding packets are transferred.
- Packet destinations wireless charging stations are registered in logistic companies, retailers and regulators, meaning that each drone is aware of the location of the destinations, wireless charging stations, and the location of every other drone.
- All the nodes communicate at Wi-Fi frequencies with the radio range of R.
- Every drone moves independently with a fixed speed of S.
4. Heuristic Flight Path Planning (HFPP)
Algorithm 1 Heuristic Flight Path Planning (HFPP) |
Input: G, , , // and represent destination and delivery deadline of consignment Output: , , …, , where , 1 begin 2 int ; //counter for number of registered destinations added to the list of deliveries 3 int ; ; ; // and are the maximum weight and the index of registered destinations respectively 4 float ; 5 boolean ; 6 ; ; 7 while do 8 for to do 9 if then 10 ; ; ; 11 end if 12 end for 13 if then 14 break; 15 end if 16 ; ; ; 17 ; 18 if then 19 if then 20 for to do 21 if 22 ; ; 23 ; ; 24 end if 25 end for 26 end if 27 if then 28 ; 29 ; 30 goto line 17 31 else 32 ; ; 33 ; ; 34 goto line 8 35 end if 36 end if 37 end while |
5. Evaluation
5.1. Results
5.2. Discussion
6. Conclusions
Author Contributions
Funding
Conflicts of Interest
References
- Wu, D.; Regan, A.C.; Venkatasubramanian, N. ADDSEN: Adaptive data processing and dissemination for drone swarms in urban sensing. IEEE Trans. Comput. 2016, 66, 183–198. [Google Scholar] [CrossRef]
- Fadlullah, Z.M.; Takaishi, D.; Nishiyama, H.; Kato, N.; Miura, R. A dynamic trajectory control algorithm for improving the communication throughput and delay in UAV-aided networks. IEEE Netw. 2016, 30, 100–105. [Google Scholar] [CrossRef]
- Krishnamoorthy, K.; Casbeer, D.; Pachter, M. Minimum time UAV pursuit of a moving ground target using partial information. In Proceedings of the IEEE International Conference on Unmanned Aircraft Systems (ICUAS), Denver, CO, USA, 9–12 June 2015. [Google Scholar]
- Yanmaz, E.; Yahyanejad, S.; Rinner, B.; Hellwagner, H.; Bettstetter, C. Drone networks: Communications, coordination, and sensing. Ad Hoc Netw. 2018, 68, 1–15. [Google Scholar] [CrossRef]
- Desjardins, J. Business Insider. Available online: https://www.businessinsider.com/amazon-and-ups-are-betting-big-on-drone-delivery-2018-3/?r=AU&IR=T (accessed on 3 November 2018).
- Louw, D.B.; Silk, R.J. Trigger Agents in Video Streams from Drones. U.S. Patent 9,714,089 B1, 25 July 2017. [Google Scholar]
- Thomas, A.; Raja, G. FINDER: A D2D based critical communications framework for disaster management in 5G. Peer-to-Peer Netw. Appl. 2018, 1–12. [Google Scholar] [CrossRef]
- Vahdat, A.; Becker, D. Epidemic Routing for Partially-Connected Ad Hoc Networks; Duke University: Durham, NC, USA, 2000. [Google Scholar]
- Lindgren, A.; Doria, A.; Schelén, O. Probabilistic routing in intermittently connected networks. ACM Int. Symp. Mob. Ad Hoc Netw. Comput. Mob 2003, 7, 19–20. [Google Scholar] [CrossRef]
- Iranmanesh, S.; Raad, R.; Chin, K.W. A novel destination-based routing protocol (DBRP) in DTNs. In Proceedings of the IEEE International Symposium on Communications and Information Technologies (ISCIT), Goldcoast, Australia, 2–5 October 2012. [Google Scholar]
- Nelson, S.C.; Bakht, M.; Kravets, R. Encounter–based routing in DTNs. In Proceedings of the IEEE INFOCOM, Rio de Janeiro, Brazil, 19–25 April 2009. [Google Scholar]
- Iranmanesh, S.; Chin, K.-W. A novel mobility-based routing protocol for semi-predictable disruption tolerant networks. Springer Int. J. Wirel. Inf. Netw. 2015, 22, 138–146. [Google Scholar] [CrossRef]
- Raheel, M.S.; Iranmanesh, S.; Raad, R. A novel energy-efficient video streaming method for decentralized mobile ad-hoc networks. Elsevier Pervasive Mob. Comput. 2017, 40, 301–323. [Google Scholar]
- Iranmanesh, S. A novel queue management policy for delay-tolerant networks. EURASIP J. Wirel. Commun. Netw. 2016, 2016, 88. [Google Scholar] [CrossRef]
- Iranmanesh, S.; Raad, R.; Raheel, M.S.; Tubbul, F. Novel DTN mobility-driven routing in autonomous drone Logistics networks. IEEE Trans. Veh. Technol. 2019. submitted. [Google Scholar]
- Giannini, C.; Shaaban, A.A.; Buratti, C.; Verdone, R. Delay Tolerant networking for smart city through drones. In Proceedings of the IEEE International Symposium on Wireless Communication Systems (ISWCS), Poznan, Poland, 20–23 September 2016. [Google Scholar]
- Keränen, A.; Ott, J.; Kärkkäinen, T. The one simulator for DTN protocol evaluation. In Proceedings of the SIMUTools ‘09: Proceedings of the 2nd International Conference on Simulation Tools and Techniques, Rome, Italy, 2–6 March 2009. [Google Scholar]
- Yang, P.; Tang, K.; Lozano, J.A.; Cao, X. Path planning for single unmanned aerial vehicle by separately eving waypoints. IEEE Trans. Robot. 2015, 31, 1130–1146. [Google Scholar] [CrossRef]
- Zheng, C.; Li, L.; Xu, F.; Sun, F. Evolutionary route planner for unmanned air vehicles. IEEE Trans. Robot. 2015, 21, 609–620. [Google Scholar] [CrossRef]
- Nikolos, I.K.; Valavanis, K.P.; Tsourveloudis, N.C.; Kostaras, A.N. Evolutionary algorithm based offline/online path planner for UAV navigation. IEEE Trans. Syst. Man Cybern. 2003, 33, 898–912. [Google Scholar] [CrossRef] [PubMed]
- Nikolos, I.K.; Tsourveloudis, N.C.; Valavanis, K.P. Valavanis, Evolutionary algorithm-based path planning for multiple UAV cooperation. Springer Adv. Unmanned Aer. Veh. 2007, 33, 309–340. [Google Scholar]
- Zhang, X.; Duan, H. An improved constrained differential evolution algorithm for unmanned aerial vehicle global route planning. Appl. Soft Comput. 2015, 26, 270–284. [Google Scholar] [CrossRef]
- de la Cruz, J.M.; Besada-Portas, E.; Torre-Cubillo, L.; Andres-Toro, B.; Lopez-Orozco, J.A. Lopez-Orozco, Evolutionary path planner for UAVs in realistic environments. In Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, Atlanta, GA, USA, 12–16 July 2008. [Google Scholar]
- Sujit, P.B.; Beard, R. Multiple UAV path planning using anytime algorithms. In Proceedings of the American Control. Conference, Missouri, MO, USA, 10–12 June 2009. [Google Scholar]
- Szczerba, R.J.; Galkowski, P.; Glicktein, I.S.; Ternullo, N. Robust algorithm for real-time route planning. IEEE Trans. Aerosp. Electr. Syst. 2000, 36, 869–878. [Google Scholar] [CrossRef] [Green Version]
- Zhang, S.; Zhang, H.; Di, B.; Song, L. Cellular controlled cooperative unmanned aerial vehicle networks with sense-and-send protocol. IEEE Int. Things J. 2018, 6, 1–13. [Google Scholar]
- Mosheiov, G. The travelling salesman problem with pick-up and delivery. Eur. J. Oper. Res. 1994, 79, 299–310. [Google Scholar] [CrossRef]
- Stolaroff, J.K.; Samaras, C.; O’Neill, E.R.; Lubers, A.; Mitchell, A.S.; Ceperley, D. Ceperley, Energy use and life cycle greenhouse gas emissions of drones for commercial package delivery. Nat. Commun. 2018, 409, 9. [Google Scholar]
- Salarian, H.; Chin, K.-W.; Naghdy, F. An energy efficient mobile sink path selection strategy for WSNs. IEEE Trans. Veh. Technol. 2014, 63, 2407–2419. [Google Scholar] [CrossRef]
- Kreyszig, E. Advanced Engineering Mathematics, 2nd ed.; Wiley: New York, NY, USA, 1979; p. 880. [Google Scholar]
- ohnson, D.S.; Gutin, G.; McGeoch, L.A.; Yeo, A.; Zhang, W.; Zverovitch, A. Experimental analysis of heuristics for the ATSP. In The Traveling Salesman Problem and Its Variations. Combinatorial Optimization; Springer: Boston, MA, USA, 2007; pp. 445–487. [Google Scholar]
Variables | Description |
---|---|
set of v drones | |
vth drone | |
set of q destinations | |
qth destination | |
set of b bases | |
mth base | |
set of k wireless charging stations | |
kth wireless charging station | |
Maximum flight duration that means drone i should be at the origin base after that | |
maximum flying distance | |
Degree of packet i’s importance | |
Packets i’s time to live | |
S | Speed of drone |
R | Radio range of drone |
© 2019 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
Share and Cite
Iranmanesh, S.; Raad, R. A Novel Data Forwarding Strategy for a Drone Delay Tolerant Network with Range Extension. Electronics 2019, 8, 659. https://doi.org/10.3390/electronics8060659
Iranmanesh S, Raad R. A Novel Data Forwarding Strategy for a Drone Delay Tolerant Network with Range Extension. Electronics. 2019; 8(6):659. https://doi.org/10.3390/electronics8060659
Chicago/Turabian StyleIranmanesh, Saeid, and Raad Raad. 2019. "A Novel Data Forwarding Strategy for a Drone Delay Tolerant Network with Range Extension" Electronics 8, no. 6: 659. https://doi.org/10.3390/electronics8060659