【2023年第10期】基于链路质量与节点负载估计的Q学习UANET路由协议
"移动自组织"专题 · 03
基于链路质量与节点负载估计的
Q学习UANET路由协议
王柄焱1，郑向平2,3，贾文杰1，李大鹏1
（1.南京邮电大学通信与信息工程学院，江苏 南京 210003；
2.江苏永丰机械有限责任公司，江苏 南京 210094；
3.重庆理工大学计算机科学与工程学院，重庆 400054）
【摘 要】针对无人机自组网（UANET）网络拓扑变化频繁，传统路由协议建立链路的稳定性较差，而导致的链路断裂、高负载情况下的业务丢失等问题，提出了基于链路质量与节点负载估计的Q学习UANET路由协议，该协议在最优链路状态路由（OLSR）协议的基础上，使用Q-learning算法，将跳数、链路质量和节点负载作为路由决策的奖励函数，以加权的综合评价指标作为路由的决策准则。实验结果表明，改进后的协议更加适用于无人机自组网中高动态、高负载的网络环境。
【关键词】无人机自组网；路由协议；OLSR；Q-Learning
doi:10.3969/j.issn.1006-1010.20230825-0001
中图分类号：TN929.5 文献标志码：A
文章编号：1006-1010(2023)10-0017-07
引用格式：王柄焱,郑向平,贾文杰,等. 基于链路质量与节点负载估计的Q学习UANET路由协议[J]. 移动通信, 2023,47(10): 17-23.
WANG Bingyan, ZHENG Xiangping, JIA Wenjie, et al. Q-Learning UANET Routing Protocol Based on Link Quality and Node Load Estimation[J]. Mobile Communications, 2023,47(10): 17-23.
0 引言
移动自组网（Mobile Ad Hoc Networks，MANET）是一种自组织、无中心、多跳传输的无线网络，与传统中心控制的无线网络相比，移动自组网不依赖任何中央基础设施，可以实现低成本，快速的网络部署，同时也便于扩展和维护，近年来得到了广泛的应用[1-2]。无人机自组网（Unmanned Aerial Vehicles Ad Hoc Networks, UANET）是MANET在无人机领域的扩展应用，有动态性高、链路长、资源有限、数据交互频繁的特点，这给执行任务带来了多样性与灵活性，但也给路由协议的设计带来了很大的挑战[3-5]。
目前，OLSR（Optimized Link State Routing）协议是应用比较广泛的主动式路由协议[6]，相比于以AODV（Ad hoc On-Demand Distance Vector Routing）为代表的被动式路由协议，OLSR协议中的节点会周期性地交互路由测度信息，更新路由表，当要发送业务时，可以直接查询已经建立的路由，而被动式路由协议采用的是一种有业务发送时才开启路由建立的执行方式，所以，在对实时性要求较高的无人机网络场景中，OLSR协议更有优势[7] 。
OLSR协议中的节点通过广播Hello分组来完成链路探测与邻居发现，通过广播拓扑控制（TC, Topology Control）分组来共享网络拓扑信息，同时通过多点中继技术（MPR, Multi-Point Relay），在一定程度上减少了路由维护开销[8-10]。但传统的OLSR协议仅使用跳数作为路由的决策准则，选择的标准过于单一，难以适应真实的UANET场景。
针对网络拓扑变化频繁的场景，王旭东等人[11]提出了一种基于位置信息的速度加权SW-OLSR协议，通过预估计算一个ETX值来度量无线链路的链路质量，进而辅助路由决策。周长家等人[12]针对UANET的动态性和能量受限的特点提出了一种适用于UANET的UAV-OLSR协议，通过感知在发送Hello消息间隔内的邻居变动状况以及发送TC消息间隔内的拓扑变动状况动态调整两种控制信息的发送周期，同时通过评估节点能量优化了MPR机制；姚玉坤等人[13]提出在选取MPR节点集时，加入链路稳定性和链路存在时间这两个链路状态指标，使得选取的MPR节点集更稳定、合理，同时结合Q-learning算法实现了对TC消息发送间隔的动态调整，在一定程度上降低了路由控制开销。实际上，上述改进协议都针对运动拓扑对OLSR协议进行了优化，但缺少对节点负载的考量。王靖等人[14]采用跨层协议设计理论，通过对节点负载、链路投递率和链路可用性等信息进行感知，并以此为依据来推理链路质量，进一步优化了路由选择，保证了网络的负载均衡，有效地提高了协议的可靠性。但该协议引入了较大的控制开销，难以适用于节点能量有限的UANET。
针对OLSR协议路由选择指标单一的问题，本文提出了在无人机自组网场景中，基于链路质量与节点负载估计的Q学习OLSR协议（UQL-OLSR, Q-learning OLSR Based on Link Quality and Node Load Estimation for UANET），主要内容包括：1）针对高动态和高吞吐两种网络场景，分别定义了链路质量和节点负载两个参数，并提供了相应的估计方法；2）基于Q学习算法，结合OLSR协议控制信息的交互过程，设计了基于跳数、链路质量、节点负载三方面的奖励函数，并提供了路由建立过程中Q值表与路由表的更新方法，用于指导在多因素影响下的路由决策。该协议已在某网络仿真环境中实现，实验结果表明，优化后的协议更加适用于高动态、高负载环境下的无人机自组网。
1 系统模型与问题分析
1.1 系统模型
本文使用Q学习算法对OLSR协议在UANET场景下的路由选择与路由建立过程建立模型。Q学习是一种基于值函数的无模型强化学习（Reinforcement Learning, RL）算法[15]，它能够将学习任务分散到每一个网络节点中，通过周期性的与邻居交互控制信息来动态更新路由表，这意味着网络中的节点可以根据它们的互动经验不断改善路由决策，以提高网络性能和可靠性。这种方法有助于优化数据传输，使网络更有效地工作。
图1为Q学习的基本模型，以马尔可夫决策过程（Markov Decision Process，MDP）为理论基础。在MDP中，智能体（Agent）处于一个由状态（State）、动作（Action）和奖励（Reward）组成的环境中，假设在t时刻智能体的状态为St，在收到基于上一次动作环境反馈的奖励值Rt之后，经过决策执行最优动作At并进入状态St+1，智能体循环执行以上操作，经过了动作带来奖励后又反过来影响动作决策的过程，以达到在特定的环境中选择最优决策的问题[16]。
Q学习算法通过Q值来评估状态行动的价值，其中Q值的更新规则如下：
式中Q(st, at) 是状态-动作对(s, a)的值函数，表示在状态s下采取动作a所能获得的奖励期望，α∈(0, 1)为学习率，用于控制学习的速度，γ∈(0, 1)为折扣因子，用于控制长期奖励的重要性。
为了让网络中的节点能够自主学习，及时感知拓扑结构与节点状态，将Q学习算法与OLSR协议结合，定义智能体Agent为网络中的节点，学习环境为整个UANET。
定义三元组（A, S, R）如下：
1）动作（A）：节点通过感知邻居与拓扑变化，新增或更新本地路由表项，从一跳邻居集N={N1, N2,…,Nn}中选取一个节点作为相应目的的下一跳。
2）状态（S）：节点的本地路由信息及状态统计信息，包括跳数hop、节点地理位置 (x, y)、数据接收速率R等，反应节点当前的情况，用于指导路由决策。
3）奖励（R）：整个网络对节点的即时反馈值，可以根据网络性能的需求，将跳数、时延、负载、能耗等指标映射到奖励R中，使节点能够适应动态的网络环境。
在路由建立过程中，网络中的每个节点都维护一张Q值表，表中的列表示经过本节点的目的节点ID，行表示本节点的一跳邻居节点ID，用来记录当前节点在指定目的节点的情况下，选择某个邻居节点作为下一跳可以得到的累积奖励期望值，节点会选择Q值最大的邻居作为下一跳节点。Q值表的具体格式如表1所示。
基于该路由策略，参考公式(1)，以D作为目的节点，源节点S将邻居节点N作为下一跳的质量评估值，即对应Q值的更新公式变为：
其中α为学习率，γ为折扣因子，Ns为源节点S的一跳邻居集。
Q学习作为一种无模型算法，其复杂度可以表示为O(SAH)，其中S表示状态空间的大小，A表示动作空间的大小，H表示每一次执行所走的步长[17]。S的大小受到网络规模的影响，节点越多，需要统计的状态参量相应增加；A的大小则与网络节点的一跳邻居集大小相关，具体的，节点可供选择的下一跳节点数量越多，动作空间越大；同时，由于每次执行动作只会新增或更新一行路由表项，因此步长H可视为1。综上，通过Q学习实现路由建立的复杂度受到网络规模与节点密集程度的影响，设置合理的节点总数与拓扑结构可以显著降低算法的复杂度。
1.2 问题分析
传统的OLSR协议仅基于跳数，使用Dijkstra算法计算路径，生成路由。选择路由的标准过于单一，难以适应网络拓扑的快速变化，会导致链路易断裂，路由更新不及时等问题[18]，同时，在业务量较大的场景中，MPR节点的负载加重，业务发生拥塞的可能性增加，进而也会降低网络的性能[19]，因此：
1）考虑到无人机节点的移动性：在制定路由转发策略时，选择质量更高，稳定性更好的下一跳节点，能够延长路径生存时间，减少链路断裂，提高路由质量和数据传输的可靠性。
2）考虑到高负载情况下的数据拥塞问题：在路由选择时，选择负载较小，空闲度较大的转发节点可以减少这种问题的发生，降低网络的时延[20]。
综合考虑以上2个问题，同时也保留对跳数的考量，定义跳数因子HF、链路质量因子QF和节点空闲度因子LF，共同构成Q学习中对节点的即时奖励R（奖励函数的设计见2.1节），用于指导节点在多因素影响下的路由决策。
2.2 路由方案设计
（1）路由建立过程
在路由建立的过程中，每个节点都会周期性广播Hello分组用于探测邻居节点，为了判断应该转发来自哪些节点的广播消息，节点会在本地维护一张MPR_S（MPR Selector）集合。节点将MPR_S集合中的信息加入TC分组后，向全网洪泛TC分组用于交互网络的拓扑信息，由MPR节点进行处理和转发，参考1.1节中对Q表的定义，网络中的节点通过交互Hello和TC分组维护一张Q值表，更新路由时，选择Q值最大的邻居节点作为下一跳节点，无人机节点维护Q表的示意图如图2所示：
为了计算本节点到对应目的节点的Q值，节点首先会收集并计算本地路由与状态测度信息，再将这些信息添加到Hello分组中，并定期地将这些数据共享给邻居节点，MPR节点接收到邻居的测度信息后，会将这些信息添加到TC分组中，向全网广播。在开始阶段，每个节点Q表的初始值都设为0，当节点接收到邻居节点发送来的TC分组后，将在本地维护一个拓扑表，提取其中记录的目的地址Dt、TC分组中的上一跳地址Pt、节点地理位置、接收速率等相关信息，按照公式(11)计算奖励值R，然后将Dt作为Q值参数的目的节点Di， Pt作为邻居节点Ni，按公式(2)更新本地Q值表。经过这一过程，就更新了当前节点以MPR_S集合中的节点为目的，上一跳节点为邻居的Q值。更新完成后，如果当前节点是MPR节点，则将上一跳地址设为自己，再以单跳广播的方式向全网转发该TC分组。同理，收到其他邻居节点发来的TC分组也如此处理，经过一段时间的算法收敛，以全网中其他节点为目的的Q值都得到更新。
UQL-OLSR协议的路由建立流程如图3所示。
（2）路由维护过程
在路由建立的过程中，为了应对高动态场景中节点入网，退网的场景，制定了Q值表中节点的有效时间，在这个有效时间内，如果某个节点的Q值没有被更新，系统会将该目的节点视为下线，并清除相应行的数据。同时，需要根据网络规模设置TC报文的生存时间（TTL），在确保全网能够感知拓扑信息的情况下，减少控制信息的冗余。
由于Q学习算法需要需要一定时间才能收敛，在当前节点到所有其他节点的Q值都收敛时，更新后的路由才能逐渐趋近最佳。然而，在更新路由表时，Q值可能与稳态值存在较大偏差。为了尽快达到Q值收敛，特别是在动态性较高的网络中，需要适度降低Hello报文和TC报文的发送间隔，以促进Q值的快速更新。同时为了减少控制信息在网络中的竞争和碰撞，实验过程中设定控制信息的发送时延为γT,其中γ为[0,1]之间的随机数，T为控制报文的发送间隔，每个节点错开控制信息的发送时间，确保网络中的消息传输更均匀，保证在路由建立过程中控制信息的接收速率和占用的带宽基本保持恒定。
3 仿真与分析
本文使用某网络仿真平台对UQL-OLSR协议进行仿真验证，将其与集成的标准版OLSR协议以及文献[11]中的基于位置信息的速度加权OLSR协议（SW-OLSR）进行对比分析，并分别设计了如下仿真实验：
1）预估UQL-OLSR协议的路由建立时间，通过获得业务源节点本地Q表中最大Q值的收敛时间来估计；
2）验证节点吞吐量一致的情况下，网络拓扑变化频繁程度对时延和分组投递率的影响；
3）验证网络拓扑变化程度一致的情况下，节点吞吐量的变化对时延和分组投递率的影响。
实验中设置最小跳数、链路稳定性和节点空闲度的权重因子分别为0.3、0.4和0.3，场景规模为2 km×2 km；节点的移动方式采用随机移动（Random WayPoint），整体实验仿真参数如表2所示：
3.1 路由建立时间分析
在2.2节中提到，只有当节点的Q值都达到收敛状态时，更新后的路由才会逐渐接近最佳路由，所以为了评估UQL-OLSR协议的性能，需要保证在传输业务数据时，节点维护的Q值都达到收敛状态。在路由选择时，节点选择Q值最大的邻居作为下一跳节点，因此可以通过最大Q值的收敛时间来预估学习过程的收敛时间和路由建立的时间。
设置场景中节点的最大移动速度为5 m/s，设置5条端到端业务，发送速率为4 kbps，随机选取实验场景中的一条端到端业务，源节点的Qmax值随仿真时间的收敛过程如图4所示。
在仿真的开始阶段，Qmax增加迅速，随着时间的增加增幅逐渐变缓，并在20 s左右趋于稳定，这说明在协议运行期间，源节点从网络中学习最小跳数、网络拓扑变化情况以及链路空闲程度信息，这些信息最终反应在Q值的大小上。随着节点的运动和网络中业务负载的变化，Qmax也可能小幅度波动，但不会像路由建立初期那样剧烈变化。可以认为，在按照表2配置的仿真参数下，路由建立的时间为20 s左右，因此为了避免误差，业务数据的传输应该设置在网络启动运行20 s之后。
3.2 性能分析
为了测试网络拓扑运动的剧烈程度对协议性能的影响，设置业务源节点的发送速率一致，均为4 kbps。无人机最大移动速度在0～25 m/s时的端到端时延和分组投递率变化情况分别如图5和图6所示，可以看到，节点的移动速度越快，端到端时延逐渐增加，分组投递率逐渐降低，在无人机移动速度较低时，拓扑结构的变化不大，三种协议的端到端时延和分组投递率基本保持一致，当无人机最大速度上升到25 m/s时，SW-OLSR通过引入速度加权的ETX和节点位置信息，UQL-OLSR通过加入对链路质量和节点负载的评估和Q-learning奖励机制，在时延上相比OLSR分别降低了9.8%和13.5%，在分组投递率上分别提高了46.2%和51.8%。两种优化OLSR协议都考虑了拓扑结构变化对数据传输的影响，能够选择稳定性更高的下一跳节点，减少了网络中链路断裂的情况。
同时，为了测试节点吞吐量对协议性能的影响，统一设置节点的最大移动速度为5 m/s，在场景中随机添加5条端到端业务，统计业务速率在100 kbps～500 kbps下的端到端时延和分组投递率变化情况。如图7和图8所示，随着业务速率的提高，网络中的节点负载增加，端到端时延提高，分组投递率降低。同样，发送速率较低时三种协议的端到端时延和分组投递率没有明显区别，但当发送速率相对较大，为500 kbps时，SW-OLSR协议由于考虑了无人机节点运动的因素，在时延和分组投递率上分别进步了17.0%和21.2%，但UQL-OLSR协议同时还考虑了节点邻居的负载程度，优先选择负载较小的下一跳邻居，因此，在业务速率较大的场景下，时延和分组投递率进一步优化了7.4%和12.1%。
4 结束语
传统OLSR协议在更新路由时仅使用路径跳数作为判决准则，无法适应现今无人机自组网中高动态、高负载的场景，针对这个问题，本文以Q学习框架为基础，将路径跳数、链路质量和节点负载三个因子作为路由测度，设计了UQL-OLSR协议，在协议的工作过程中，节点通过广播Hello和TC分组交互路由测度信息，网络节点通过维护一个Q值表实现动态的路由更新。实验结果表明，UQL-OLSR协议相比OLSR协议在平均端到端时延和分组投递率上有明显优势，更加适用于节点高速移动，数据交互频繁的无人机自组网场景。
参考文献：（上下滑动浏览）
[1] 吴院. 移动自组网中路由协议的分析与研究[J]. 单片机与嵌入式系统应用, 2014,14(01): 16-19.
[2] 张德干, 葛辉, 刘晓欢, 等. 一种基于 Q-Learning 策略的自适应移动物联网路由新算法[J]. 电子学报, 2018,46 (10): 2325-2332.
[3] 孙晨,莫国美,舒坚. 基于强化学习的无人机自组网路由研究综述[J]. Application Research of Computers/Jisuanji Yingyong Yanjiu, 2023, 40(07):1937-1946.
[4] Liu J, Ren F, Miao L, et al. A-ADHOC: An adaptive real-time distributed MAC protocol for Vehicular Ad Hoc Networks[J]. Mobile Networks and Applications, 2011, 16: 576-585.
[5] Maxa J, Mahmoud B S M, Larrieu N. Survey on UAANET Routing Protocols and Network Security Challenges[J]. Ad Hoc & Sensor Wireless Networks,2017,37(1-4).
[6] Gupta L, Jain R, Vaszkun G. Survey of important issues in UAV communication networks[J]. IEEE communications surveys & tutorials, 2015, 18(02): 1123-1152.
[7] Ferronato J J, Trentin M A S. Analysis of routing protocols OLSR, AODV and ZRP in real urban vehicular scenario with density variation[J]. IEEE Latin America Transactions, 2017, 15(09): 1727-1734.
[8] Jacquet P, Muhlethaler P, Clausen T, et al. Optimized link state routing protocol for ad hoc networks[C]// IEEE International Multi Topic Conference, 2001. IEEE INMIC 2001. Technology for the 21st Century. IEEE, 2001: 62-68.
[9] 段薇,李大双,姜永广,等. 对OLSRv2草案及其相关规范的研究[J]. 通信技术,2014(5):527-531.
[10] Maccari L, Maischberger M, Cigno R L. Where have all the MPRs gone? On the optimal selection of Multi-Point Relays[J]. Ad Hoc Networks, 2018, 77: 69-83.
[11] 王旭东, 米志超, 姜雨卿, 等. 一种基于位置信息的速度加权 OLSR 算法[J]. 通信技术, 2018, 51(12): 2885-2890.
[12] 周长家,周建国. 一种基于OLSR的无人机网络适用路由算法[J]. 计算机工程, 2021,47(10):174-179,185.
[13] 姚玉坤, 张本俊, 周杨. 无人机自组网中基于 Q-learning 算法的及时稳定路由策略[J]. Application Research of Computers/Jisuanji Yingyong Yanjiu, 2022, 39(02): 531-536
[14] 王靖, 李芳芳, 于全. 基于链路状态感知的无线 Mesh 网优化路由协议[J]. 计算机科学, 2012, 39(11): 37-40.
[15] Watkins J C, Dayan P. Technical Note Q-Learning.[J]. Machine Learning,1992,8(03): 279-292.
[16] 黄鑫陈,陈光祖,郑敏等.基于Q-learning的飞行自组织网络QoS路由方法[J].中国科学院大学学报,2022,39(01):134-143.
[17] Jin C, Allen-Zhu Z, Bubeck S, et al. Is Q-learning provably efficient?[J]. Advances in neural information processing systems, 2018, 31: 4868-4878.
[18] 熊轲, 金鑫, 刘强. QL-OLSR: 一种基于 Q-Learning 思想优化的移动自组织网络路由协议[J]. 北京交通大学学报, 2020, 44(02): 66-73.
[19] 徐久强, 李鹤群, 王进法, 等. 基于边权与节点负载的路由策略研究[J]. 东北大学学报 (自然科学版), 2015, 36(12): 1691-1695.
[20] 周通. 移动自组网负载自适应的多路径传输方法研究[D]. 上海: 上海交通大学, 2017. ★
★扫描二维码，到知网阅读下载本篇论文
★原文发表于《移动通信》2023年第10期★
doi:10.3969/j.issn.1006-1010.20230825-0001
中图分类号：TN929.5 文献标志码：A
文章编号：1006-1010(2023)10-0017-07
引用格式：王柄焱,郑向平,贾文杰,等. 基于链路质量与节点负载估计的Q学习UANET路由协议[J]. 移动通信, 2023,47(10): 17-23.
WANG Bingyan, ZHENG Xiangping, JIA Wenjie, et al. Q-Learning UANET Routing Protocol Based on Link Quality and Node Load Estimation[J]. Mobile Communications, 2023,47(10): 17-23.
《移动通信》投稿方式为在线投稿
请您登录网页投稿系统
链接地址：http://ydtx.cbpt.cnki.net
面向6G的物联网技术 | 2023年第8期专题论文（11篇）
空天地海一体化网络 | 2023年第7期专题论文（13篇）
《移动通信》用论文解读通信
《移动通信》杂志由中国电子科技集团公司主管，中国电子科技集团公司第七研究所主办，是中国期刊方阵“双效期刊”、工业和信息化部精品电子期刊、中国科技论文统计源刊、中国科协《高质量科技期刊分级目录》入选期刊、日本JST收录期刊。国内连续出版物号：CN44-1301/TN，国际连续出版物号：ISSN1006-1010，邮发代号：46-181。