灾后无人机自组网高动态多信道TDMA调度算法

doi:10.19665/j.issn1001-2400.20230414

摘要/Abstract

摘要：

以自然灾害、事故灾难为主要类型的极端突发事件对应急通信网络快速重组与灾情信息实时回传提出了严峻挑战,亟需构建具备快速响应能力、按需动态调整的应急通信网络。为了在断电、断路、断网“三断”极端条件下实现灾情信息实时回传,可通过多无人机形成飞行自组网对受灾区域进行网络通信覆盖。针对灾后复杂环境受限条件下飞行自组织网络通信资源调度不合理引起的信道冲突问题,提出了基于Q-learning的自适应多信道时分多址调度算法。根据无人机间的链路干扰关系建立顶点干扰图,结合图着色理论,将高动态场景下多信道时分多址调度问题抽象为动态二重着色问题。考虑无人机的高速移动性,通过自适应调整Q-learning的学习因子,实现算法的收敛速度与最优解探索能力的权衡优化,以适应高动态的网络拓扑。通过仿真实验证明,所提算法可以实现网络通信冲突和收敛速度的权衡优化,能够解决灾后高动态场景下资源分配决策与快变拓扑适配问题。

关键词: 无人机, 多信道时分多址, 图论, 自适应Q-learning

Abstract:

Extreme emergencies,mainly natural disasters and accidents,have posed serious challenges to the rapid reorganization of the emergency communication network and the real-time transmission of disaster information.It is urgent to build an emergency communication network with rapid response capabilities and dynamic adjustment on demand.In order to realize real-time transmission of disaster information under the extreme conditions of "three interruptions" of power failure,circuit interruption and network connection,the Flying Ad Hoc Network can be formed by many unmanned aerial vehicles to cover the network communication in the disaster-stricken area.Aiming at the channel collision problem caused by unreasonable scheduling of FANET communication resources under the limited conditions of complex environment after disasters,this paper proposes a multi-channel time devision multiple access(TDMA) scheduling algorithm based on adaptive Q-learning.According to the link interference relationship between UAVs,the vertex interference graph is established,and combined with the graph coloring theory,and the multi-channel TDMA scheduling problem is abstracted into a dynamic double coloring problem in highly dynamic scenarios.Considering the high-speed mobility of the UAV,the learning factor of Q-learning is adaptively adjusted according to the change of network topology,and the trade-off optimization of the convergence speed of the algorithm and the exploration ability of the optimal solution is realized.Simulation experiments show that the proposed algorithm can realize the trade-off optimization of network communication conflict and convergence speed,and can solve the problem of resource allocation decision and fast-changing topology adaptation in post-disaster high-dynamic scenarios.

Key words: unmanned aerial vehicles, multi-channel TDMA, graph theory, adaptive Q-learning

中图分类号:

TN929.5

孙彦景, 李林, 王博文, 李松. 灾后无人机自组网高动态多信道TDMA调度算法[J]. 西安电子科技大学学报, 2024, 51(2): 56-67.

SUN Yanjing, LI Lin, WANG Bowen, LI Song. Highly dynamic multi-channel TDMA scheduling algorithm for the UAV ad hoc network in post-disaster[J]. Journal of Xidian University, 2024, 51(2): 56-67.

图/表 9

图1

图2

图3

表1

图4

图5

图6

图7

图8

参考文献 27

[1]	DO-DUY T, NGUYEN L D, DUONG T Q, et al. Joint Optimisation of Real-Time Deployment and Resource Allocation for UAV-Aided Disaster Emergency Communications[J]. IEEE Journal on Selected Areas in Communications, 2021, 39(11):3411-3424.
[2]	LI L, WEN X, LU Z, et al. Energy-Efficient Multi-UAVs Deployment and Movement for Emergency Response[J]. IEEE Communications Letters, 2021, 25(5):1625-1629.
[3]	杨欣, 毛雅淇, 王伶. 无人机辅助通信的密集无线网络MAC协议[J]. 西安电子科技大学学报, 2022, 49(3):10-20.
	YANG Xin, MAO Yaqi, WANG Ling. MAC Protocol for the Dense Wireless Network of UAV Assisted Communication[J]. Journal of Xidian University, 2022, 49(3):10-20.
[4]	田霖, 苏智杰, 冯婉媚, 等. 面向多无人机携能网络的轨迹与资源规划算法[J]. 西安电子科技大学学报, 2021, 48(6):115-122.
	TIAN Lin, SU Zhijie, FENG Wanmei, et al. Trajectory and Resource Allocation for Multi-UAV Enabled Swipt Systems[J]. Journal of Xidian University, 2021, 48(6):115-122.
[5]	王博文, 孙彦景. 基于联盟图博弈的地下空间无人机应急通信网络拓扑控制算法[J]. 电子与信息学报, 2022, 44(3):996-1005.
	WANG Bowen, SUN Yanjing. Coalitional Graph Game Based Topology Control Algorithm for Unmanned Aerial Vehicle Emergency Networks in Underground Space[J]. Journal of Electronics & Information Technology, 2022, 44(3):996-1005.
[6]	CUI Y, ZHANG Q, FENG Z, et al. Topology-Aware Resilient Routing Protocol for FANETs:An Adaptive Q-Learning Approach[J]. IEEE Internet of Things Journal, 2022, 9(19):18632-18649.
[7]	BALASUNDARAM B, BUTENKO S. Graph Domination,Coloring and Cliques in Telecommunications[M].Handbook of Optimization in Telecommunications. Heidelberg:Springer, 2006:865-890.
[8]	LIU W, LIU K, TIAN L, et al. Joint Interference Alignment and Subchannel Allocation in Ultra-Dense Networks[J]. IEEE Transactions on Vehicular Technology, 2022, 71(7):7287-7296.
[9]	YAO K, WANG J, XU Y, et al. Self-Organizing Slot Access for Neighboring Cooperation in UAV Swarms[J]. IEEE Transactions on Wireless Communications, 2020, 19(4):2800-2812.
[10]	WANG B, SUN Y, ZHAN N, et al. Learn to Coloring:Fast Response to Perturbation in UAV-Assisted Disaster Relief Networks[J]. IEEE Transactions on Vehicular Technology, 2020, 69(3):3505-3509.
[11]	LEE J, JEONG W C. Multi-Channel TDMA Link Scheduling for Wireless Multi-Hop Sensor Networks[C]// 2015 International Conference on Information and Communication Technology Convergence(ICTC). Piscataway:IEEE, 2015: 630-635.
[12]	檀华丽, 夏娜, 伊君, 等. 基于协作型学习自动机的多信道TDMA调度算法研究[J]. 合肥工业大学学报, 2018, 41(3):318-324.
	TAN Huali, XIA Na, YI Jun, et al. Research on Multi-Channel TDMA Scheduling Algorithm Based on Collaborative Learning Automaton[J]. Journal of Hefei University of Technology, 2018, 41(3):318-324.
[13]	LAKHLEF H, RAYNAL M, TAIANI F. Vertex Coloring with Communication Constraints in Synchronous Broadcast Networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 30(7):1672-1686.
[14]	张家波, 吴昌玉, 袁凯. V2V 通信中基于超图理论的资源分配算法[J]. 计算机工程与设计, 2020, 41(9):2408-2414.
	ZHANG Jiabo, WU Changyu, YUAN Kai. Resource Allocation Algorithm Based on Hypergraph Theory in V2V Communication[J]. Computer Engineering and Design, 2020, 41(9):2408-2414.
[15]	WANG B, SUN Y, SUN Z, et al. UAV-Assisted Emergency Communications in Social IoT:A Dynamic Hypergraph Coloring Approach[J]. IEEE Internet of Things Journal, 2020, 7(8):7663-7677.
[16]	DU B, DI X, LIU D, et al. Dynamic Graph Optimization and Performance Evaluation for Delay-Tolerant Aeronautical Ad Hoc Network[J]. IEEE Transactions on Communications, 2021, 69(9):6018-6036.
[17]	ZHANG M, DONG C, FENG S, et al. Adaptive 3D Routing Protocol for Flying Ad Hoc Networks Based on Prediction-Driven Q-Learning[J]. China Communications, 2022, 19(5):302-317.
[18]	CUI J, LIU Y, NALLANATHAN A. Multi-Agent Reinforcement Learning-Based Resource Allocation for UAV Networks[J]. IEEE Transactions on Wireless Communications, 2019, 19(2):729-743.
[19]	ARAFAT M Y, MOH S. A Q-Learning-Based Topology-Aware Routing Protocol for Flying Ad Hoc Networks[J]. IEEE Internet of Things Journal, 2021, 9(3):1985-2000.
[20]	JIANG A, MI Z, DONG C, et al. CF-MAC:A Collision-Free MAC Protocol for UAVs Ad-Hoc Networks[C]// 2016 IEEE Wireless Communications and Networking Conference.Piscataway:IEEE, 2016: 1-6.
[21]	徐子蒙, 王博文, 云霄, 等. 灾后无人机不确定偏好序下稳定中继选择方法[J]. 西安电子科技大学学报, 2022, 49(6):32-41.
	XU Zimeng, WANG Bowen, YUN Xiao, et al. Stable Relay Selection Method under an Uncertain Preference Ordinal for UAV in Post-Disater[J]. Journal of Xidian University, 2022, 49(6):32-41.
[22]	YANG L, TAO P, LI T, et al. Reservation and Traffic Intent-Aware Dynamic Resource Allocation for FANET[C]// 2021 IEEE 21st International Conference on Communication Technology(ICCT).Piscataway:IEEE, 2021: 971-975.
[23]	BAIRAGI A K, MUNIR M S, ALSENWI M, et al. A Matching Based Coexistence Mechanism between EMBB and URLLC in 5G Wireless Networks[C]//Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing. New York: ACM, 2019:2377-2384.
[24]	MAAKAR S K, SINGH Y, SINGH R. Implementation of Three Dimensional Model for Flying Ad Hoc Network[C]// 2019 2nd International Conference on Intelligent Communication and Computational Techniques(ICCT).Piscataway:IEEE, 2019: 303-307.
[25]	MA Z, AI B, HE R, et al. A Wideband Non-Stationary Air-to-Air Channel Model for UAV Communications[J]. IEEE Transactions on Vehicular Technology, 2020, 69(2):1214-1226.
[26]	SELIM M Y, KAMAL A E. Post-Disaster 4G/5G Network Rehabilitation Using Drones:Solving Battery and Backhaul Issues[C]// 2018 IEEE Globecom Workshops(GC Wkshps). Piscataway:IEEE, 2018:1-6.
[27]	CHECCO A, LEITH D J. Fast,Responsive Decentralized Graph Coloring[J]. IEEE/ACM Transactions on Networking, 2017, 25(6):3628-3640.

参数	设定值或模型
UAV飞行高度/m	100~300
UAV飞行速度/(m·s^-1)	10~40
UAV发射功率^[16]/W	1
UAV通信范围^[16]/m	250
UAV数量	60~100
UAV初始能量^[16]/J	1 000
能量阈值^[16]/J	100
传输模型	自由空间路径损耗
γ更新间隔^[16]/ms	100
移动模型	高斯-马尔可夫移动模型