Development of a Greedy Auction-Based Distributed Task Allocation Algorithm for UAV Swarms with Long Range Communication

Abstract

This study proposes a greedy auction-based distributed task allocation algorithm (GCAA) for swarm unmanned aerial vehicles (UAVs) with long range (LoRa) communication capabilities. Air-to-air (A2A) communication channels are established using LoRa technology to enable inter-agent communication, while air-to-ground (A2G) communication is facilitated through narrowband Internet of Things (NB-IoT) technology. The negotiation phase is conducted over these communication channels. Using LoRa and NB-IoT parameters, a link budget analysis is performed to determine the A2A reference distance, and a k-means clustering algorithm is developed. The proposed algorithm places base stations at cluster centers and prepares a simulation environment. The decentralized algorithm is compared with a greedy optimization algorithm under uninterrupted and interrupted communication scenarios, and the simulation results are presented in MATLAB. The developed distributed task allocation algorithm demonstrates lower system costs and shorter task completion times compared to the conventional greedy optimization algorithm. Additionally, the performance parameters exhibit more excellent stability in cumulative distribution functions.

Keywords

• Greedy auction-based distributed task allocation algorithm
• A2A/A2G communication
• LoRa
• NB-IoT

Uzak Mesafe Haberleşmesine Sahip İHA Sürüleri için Açgözlü Açık Artırma Temelli Dağıtılmış Görev Tahsis Algoritmasının Geliştirilmesi

Abstract

Bu çalışmada uzak mesafe (long range, LoRa) iletişimine sahip sürü insansız hava araçlarında (İHA) açgözlü açık artırma temelli dağıtık görev tahsis algoritması (greedy auction-based distributed task allocation algorithm, GCAA) önerilmiştir. Ajanlar arası haberleşmesinin sağlanabilmesi için LoRa teknolojisi kullanılarak havadan havaya (air-to-air, A2A), dar bant nesnelerin interneti (narrowband Internet of Things, NB-IoT) teknolojisi kullanılarak da havadan yere (air-to-ground, A2G) haberleşme kanalları oluşturulmuş ve müzakere aşaması bu haberleşme kanallarından sağlanmıştır. LoRa ve NB-IoT parametreleri kullanılarak hat bütçe analizi ile A2A referans mesafesi ve k-ortalamalı kümeleme algoritması geliştirilmiştir. Geliştirilen algoritma ile küme merkezlerine baz istasyonları yerleştirerek, simülasyon ortamı hazırlanmıştır. Önerilen merkezi olmayan algoritma ile haberleşmenin kesintisiz ve kesintili olduğu ortamda açgözlü optimizasyon algoritması ile karşılaştırılarak, MATLAB ortamında benzetim sonuçları aktarılmıştır. Geliştirilen dağıtık görev tahsis algoritması, geleneksel açgözlü optimizasyon algoritmasına göre sistem maliyetinin ve görev bitirme süresinin daha kısa olduğu gözlenmiştir. Aynı zamanda performans parametrelerinin, birikimsel dağılım fonksiyonlarında daha kararlı olduğu gözlenmiştir.

Keywords

• Açgözlü açık artırma temelli dağıtık görev tahsis algoritması
• A2A/A2G haberleşme
• LoRa
• NB-IoT

References

1. E. Can, B. I. Kirklar, M. Namdar, and A. Basgumus, “Deep learning based target tracking and diving algorithm in kamikaze UAVs,” in Innovations in Intelligent Systems and App. Conf. (ASYU), 2024, pp. 1–6. DOI: 10.1109/ASYU62119.2024.10757004.
2. E. Can, Z. Yildirim, Y. Kaya, M. Eser, M. Namdar, and A. Basgumus, “Development of greedy auction-based distributed decision-making algorithm and agent communication language in swarm unmanned aerial vehicles,” in IEEE National Conf. on Electrical and Electronics Eng. (ELECO), 2024, pp. 1–5. DOI: 10.1109/ELECO64362.2024.10847247.
3. Y. Demir, “Tekrarli acgozlu algoritma uzerine kapsamli bir analiz,” Journal of the Institute of Science and Technology, vol. 11, no. 4, pp. 2716–2728, 2021. DOI: 10.21597/jist.935652.
4. Y. Jia, S. Zhou, Q. Zeng, et al., “The UAV path coverage algorithm based on the greedy strategy and ant colony optimization,” Electronics, vol. 11, no. 17, p. 2667, 2022. DOI: 10.3390/electronics11172667.
5. J. Zhou, X. Zhao, X. Zhang, D. Zhao, and H. Li, “Task allocation for multi-agent systems based on distributed many-objective evolutionary algorithm and greedy algorithm,” IEEE Access, vol. 8, pp. 19 306–19 318, 2020. DOI: 10.1109/ACCESS.2020.2967061.
6. M. Braquet and E. Bakolas, “Greedy decentralized auction-based task allocation for multi-agent systems,” IFAC-PapersOnLine, vol. 54, no. 20, pp. 675–680, 2021. DOI: 10.1016/j.ifacol.2021.11.249.
7. C. Sommer, S. Joerer, and F. Dressler, “On the applicability of two-ray path loss models for vehicular network simulation,” in IEEE Vehicular Netw. Conf., 2012, pp. 64–69. DOI: 10.1109/VNC.2012.6407446.
8. E. Zöchmann, K. Guan, and M. Rupp, “Two-ray models in mmWave communications,” in IEEE Int. Workshop on Signal Proc. Adv. in Wireless Comm., 2017, pp. 1–5. DOI: 10.1109/SPAWC.2017.8227681.

9. K. Uchida, J. Honda, T. Tamaki, and M. Takematsu, “Handover simulation based on a two-rays ground reflection model,” in IEEE Int. Conf. on Complex, Intelligent, and Software Intensive Systems, 2011, pp. 414–419. DOI: 10.1109/CISIS.2011.119.
10. R. He, Z. Zhong, B. Ai, J. Ding, and K. Guan, “Analysis of the relation between fresnel zone and path loss exponent based on two-ray model,” IEEE Antennas and Wireless Propagation Letters, vol. 11, pp. 208–211, 2012. DOI: 10.1109/LAWP.2012.2187270.
11. S. Kurt and B. Tavli, “Path-loss modeling for wireless sensor networks: A review of models and comparative evaluations,” IEEE Antennas Propag. Mag., vol. 59, no. 1, pp. 18–37, 2017. DOI: 10.1109/MAP.2016.2630035.
12. J. Walfisch and H. L. Bertoni, “A theoretical model of uhf propagation in urban environments,” IEEE Trans. Antennas Propag., vol. 36, no. 12, pp. 1788–1796, 1988. DOI: 10.1109/8.14401.
13. S. Duangsuwan and P. Jamjareegulgarn, “Exploring ground reflection effects on received signal strength indicator and path loss in far-field air-to-air for unmanned aerial vehicle-enabled wireless communication,” Drones, vol. 8, no. 11, p. 677, 2024. DOI: 10.3390/drones8110677.
14. J. Lee, S. Lee, S. H. Chae, and H. Lee, “Performance analysis of cooperative dynamic framed slotted-ALOHA with random transmit power control in A2G communication networks,” IEEE Access, vol. 10, pp. 106 699–106 707, 2022. DOI: 10.1109/ACCESS.2022.3211943.
15. S. Lee, H. Yu, and H. Lee, “Multiagent Q-learning-based multi-UAV wireless networks for maximizing energy efficiency: Deployment and power control strategy design,” IEEE Internet of Things Journal, vol. 9, no. 9, pp. 6434–6442, 2021. DOI: 10.1109/JIOT.2021.3113128.
16. S. Lee, S. Lim, S. H. Chae, B. C. Jung, C. Y. Park, and H. Lee, “Optimal frequency reuse and power control in multi-UAV wireless networks: Hierarchical multi-agent reinforcement learning perspective,” IEEE Access, vol. 10, pp. 39 555–39 565, 2022. DOI: 10.1109/ACCESS.2022.3166179.
17. A. Almarhabi, A. J. Aljohani, and M. Moinuddin, “Lora and high-altitude platforms: Path loss, link budget and optimum altitude,” in IEEE Int. Conf. Intell. Adv. Syst., 2021, pp. 1–6. DOI: 10.1109/ICIAS49414.2021.9642705.
18. A. Goldsmith, Wireless communications. Cambridge university press, 2005, ISBN: 978-0-521-83716-3.
19. K. Akpado, O. Oguejiofor, A. Adewale, and A. Ejiofor, “Pathloss prediction for a typical mobile communication system in nigeria using empirical models,” IRACST-Int. J. Comput. Netw. Wirel. Commun., vol. 3, no. 2, pp. 207–211, 2013, ISSN: 2250-3501.
20. M. Al Rashdi, Z. Nadir, and H. Al-Lawati, “Applicability of okumura–hata model for wireless communication systems in Oman,” in IEEE Int. IOT, Electronics and Mechatronics Conf. (IEMTRONICS), 2020, pp. 1–6. DOI: 10.1109/IEMTRONICS51293.2020.9216441.
21. Z. K. Adeyemo, O. K. Ogunremi, and I. A. Ojedokun, “Optimization of okumura-hata model for long term evolution network deployment in Lagos, Nigeria,” terrain, vol. 4, no. 7, p. 14, 2016. DOI: 10.15866/irecap.v6i3.9012.
22. K. L. B. Ponce, S. Inca, D. Díaz, and M. Núñez, “Towards adaptive lora wireless sensor networks: Link budget and energy consumption analysis,” in IEEE Int. Conf. Electron. Electr. Eng. Comput., 2021, pp. 1–4. DOI: 10.1109/INTERCON52678.2021.9532685.
23. H. Soy, “Coverage analysis of LoRa and NB-IoT technologies on LPWAN-based agricultural vehicle tracking application,” Sensors, vol. 23, no. 21, p. 8859, 2023. DOI: 10.3390/s23218859.
24. M. Mardi and M. R. Keyvanpour, “GBKM: A new genetic based k-means clustering algorithm,” in IEEE Int. Conf. on Web Research (ICWR), 2021, pp. 222–226. DOI: 10.1109/ICWR51868.2021.9443113.
25. S. Kapil, M. Chawla, and M. D. Ansari, “On K-means data clustering algorithm with genetic algorithm,” in IEEE Int. Conf. Parallel Distrib. Grid Comput., 2016, pp. 202–206. DOI: 10.1109/PDGC.2016.7913145.