基于深度强化学习的无人机可信地理位置路由协议

张雅楠 仇洪冰

(桂林电子科技大学信息与通信学院 桂林 541004)

(广西无线宽带通信与信号处理重点实验室 桂林 541004)

1 引言

近年来，随着高精密模具、服务器、通信设备、传感器的高速发展，无人机(Unmanned Aerial Vehicle, UAV)在物联网中的应用越来广泛，例如火灾检测[1]、应急通信[2]、智慧农业[3]。在复杂场景中，无人机通常使用自组织的方式构成网络(UAV Ad hoc NETwork, UANET)，UANET具有部署灵活、鲁棒性高的优点。为了高效协同的完成任务，UANET中无人机采用多跳方式转发数据、传递信息[4]。无人机节点一般会按照系统分配的任务完成数据包收发，但也有一些存在异常，这包括：老化、设备故障、自私行径和恶意攻击[5]。与异常节点进行通信会导致时延增加或者丢包，降低网络性能。因此路由协议需要建立节点的信任管理机制[6]，在路由选择时综合考虑邻居的网络拓扑、异常程度等信息做出最优决策，保障UANET的安全性和可靠性。基于以上分析，作为UANET中的关键技术，亟需设计一种高效且可信的无人机路由协议。

无人机的高移动性导致了网络拓扑频繁变化，位置信息能更好地辅助路由决策，因此在UANET中普遍使用基于地理位置的路由协议[7]。Karp等人[8]提出了经典的贪婪周边无状态路由协议(Greedy Perimeter Stateless Routing, GPSR)，通过邻居周期性广播的位置信息结合贪婪算法进行路由选择。在此基础上，Jung等人[9]提出了基于Q学习的地理路由协议(Q-learning-based Geographic routing protocol, QGeo)，引入强化学习(Reinforcement Learning, RL)与Q表格法，并使用链路与位置误差辅助路由选择，使协议在动态变化的环境下逼近最优解。Lyu等人[10]提出了基于GPSR的Q网络增强地理路由协议(Q-Network enhanced geographic routing protocol based on GPSR,QNGPSR)，采用深度强化学习(Deep Reinforcement Learning, DRL)算法，构建深度Q网络并结合邻居拓扑信息协助路由选择，提升了协议在复杂场景中的自适应能力。在此基础上Liu等人[11]提出了基于Q学习的多目标优化路由协议(Q-learning based Multi- objective optimization Routing protocol, QMR)，在路由选择过程中周期性更新邻居状态并结合新的探索-利用机制，选择更可靠的下一跳。然而，上述协议主要致力于提升高速移动网络中的网络服务质量，却没有考虑异常节点对网络造成的潜在影响。

为了感知异常节点，主流研究方案采用节点信任度衡量节点的异常程度，Zhu等人[12]提出了异常行为概率检测模型(iTrust)，使用可信授权机构在通信过程中收集节点的路由证据并检查出错概率，评估节点信任度。Cho等人[13]提出了基于源的延迟容忍网络信任模型(PROVEnance-baSed Trust model, PROVEST)，将证据插入到数据包中，通过包的传播来收集证据，以此降低网络开销。不过PROVEST对证据的分析仅限于目的节点，且可能因为丢包或空洞区域而丢失证据。Ge等人[14]使用分布式信任模型UAV-pro解决了上述难题，通过来源感知技术和消息完整性，对节点行为进行记录并生成观测证据，评估节点信任度并标记恶意节点。然而上述研究需要在通信过程中检测证据，引入了额外的检测开销，并且需要在决策前更新节点的信任度，降低了网络性能。

针对上述问题，本文提出了一种基于深度强化学习的无人机可信地理位置路由协议(Deep reinforcement learning based Trusted Geographic Routing protocol, DTGR)。DTGR使用信任度衡量节点异常程度，结合目标节点的地理位置、邻居拓扑信息作为状态特征，将路由选择过程建模成马尔可夫决策过程(Markov Decision Process, MDP)，然后使用DRL算法进行决策。DTGR在包含异常节点的场景中能显著降低端到端时延、提升包递交率。DTGR的主要贡献点如下：

(1) 提出了新的节点的信任度模型。使用可信第三方提供、更新节点的信任度。降低了评估开销；

(2) 优化了文献[10]中对邻居拓扑信息的处理，减少了输入特征的维度，降低计算开销；

(3) 使用信任度结合深度强化学习模型辅助路由决策，改进了奖励函数，让节点更智能地选择最优下一跳，提升网络性能。

2 系统模型

2.1 节点信任度模型

节点信任度用来反映节点的服务能力，是一个标量。它用来评估邻居在通信过程中出现积极或者消极行为的概率，通常使用网络相关的性能参数进行量化[15]。假定传播时延和信道干扰相对于处理时延忽略不计，并且节点在每次通信中具有相似的表现，从两个维度考虑单个节点的服务能力：

时延偏差δ：表示节点从接收到转发数据包之间的理论时延、实际时延差值与理论时延之比。理论时延视为数据包大小的函数，该函数参数是固定值，由节点的计算能力决定。而实际时延通过在数据包中添加字段进行记录[10]。影响δ的主要因素为：排队时延和节点异常。

丢包率η：表示节点丢包的概率，通过统计节点转发成功和转发失败的总数据包数计算得到，影响η的主要因素为：缓冲区溢出和节点异常。

节点的信任度T定义为关于δ和η的函数

可信第三方负责存储节点的δ与η并通过式(1)计算节点的信任度，在每次通信前，节点通过可信第三方获取其他节点的信任度并在整个通信过程中使用，在通信结束后基于本次服务对其他节点的信任度进行更新。信任度更新方式见式(2)

2.2 路由选择

2.3 马尔可夫决策过程

使用MDP 4元组〈S,A,P,R〉来描述路由决策过程，并使用智能体(agent)代表决策的实体。则S表示智能体所处的状态集合，A为动作集合，P用来描述状态转移的概率，R为即时奖励函数。当节点接收到数据包时，路由选择过程的决策任务是在其所有邻居集中选择下一跳节点并转发此数据包。执行完动作后状态由当前节点转移至下一跳，不断重复以上过程直至到达终点或投递失败。根据以上分析可以建立以下的决策过程：

转移概率P：由真实环境决定，在本文中P是随机且未知的。

奖励函数R：为了让智能体能够感知下一跳的异常程度从而辅助决策，在奖励函数中引入信任度，当节点选择信任度为Tx的 邻居节点x作为下一跳时，使用R e(x)给出信任值对应的奖励：

其中，τ是信任权重且取值为正。使用信任度改进后的即时奖励函数R(x)定义为

3 基于深度强化学习的无人机可信地理位置路由协议设计

3.1 深度强化学习算法

相比较于传统算法，强化学习训练的智能体可以自动适应不断变化的环境，并在交互中更新决策，优化路由性能。算法首先考虑策略函数π

RL算法的最终目标是让智能体在训练中习得最优策略π∗，最大化累积奖励

3.2 DTGR协议

结合DRL算法设计DTGR协议，DTGR主要包含邻居表建立和路由选择过程。

邻居表建立：和GPSR类似[8]，通信中的节点c在通信时会通过信标周期性的广播Lc和N Fc信息至邻居节点。当节点u收 到来自v的信标时，还会通过可信第三方获得Tv， 进而更新自身的邻居表NTu和邻居拓扑信息N Fu。

路由选择：当节点c接收到数据包p时，执行以下路由选择算法如表1所示。

表1 DTGR路由选择算法(算法1)

图1 本文构建的DQN模型

通过对输入特征向量的优化，将位置相关的特征从5维减少至4维，减少了通信过程中神经网络中输入的数据量，使整体计算开销降低20%。

提出的DTGR协议的主要架构如图2所示，无人机通过邻居广播的信标获得邻居信息并基于这些信息构建邻居表，当发送数据包时，通过邻居表和数据包信息构建状态空间，并使用DQN网络输出路由决策，从而选择合适的下一跳。

图2 DTGR协议架构

4 仿真分析

为了验证无人机路由协议的性能，通过平均端到端时延和包递交率这两个网络性能指标对GPSR,QGeo,QNGPSR和DTGR 4组基于地理位置的路由协议进行仿真对比。

在仿真实验中，QGeo采用等宽法对输入特征进行离散化。每个维度的特征值被均匀地划分成5个区间，每个特征值用最近的端点表示，对应Q值表的状态大小被设置为55=3125。

4.1 实验设置

使用Python3.6仿真实现多无人机的底层通信、DRL决策模型以及路由协议。具体而言，在一个2000 m×2000 m的地图内随机生成40～120个无人机节点，按照一定比例产生异常节点，根据节点类型对应的阈值随机初始化每个节点的时延偏差、丢包率，然后计算信任度。无人机的通信半径为350 m、移动速度为3～10 m/s、移动方向随机。广播信标的周期为0.5 s。DTGR中构建的DQN网络共4层，神经元个数为5×16×4×1，输入特征采用最大最小标准化方法处理，并使用SELU作为激活函数。在DQN的训练过程中使用Adam作为优化器且学习率α设置为0.001，更新时使用小批量梯度下降法，批大小为32。仿真实验的主要参数见表2。

表2 仿真实验参数

4.2 实验结果和分析

上述基于RL算法的路由协议包含训练阶段和测试阶段，实验中每个回合对应100 s的仿真时间，训练阶段共100个回合且每回合使用不同的地图。为了保证算法不会因为移动导致的丢包而无法收敛，训练阶段中的无人机节点是静止的，而测试阶段进行随机移动。为了展示算法的泛化性能，测试阶段采用的地图与训练阶段的地图均不相同。在训练阶段选择总节点数为100、异常节点数比例为0.15作为基准值。

不同协议的训练曲线见图3，图3展示了4个协议(GPSR是非学习算法故用直线表示)在训练过程中的平均端到端时延变化。在收敛速度上，DTGR在训练了1～2回合后即趋向收敛并且波动较小，而QGeo算法则需要5个回合以后。另外DTGR拥有最好的训练性能，曲线位于图形的最下方，说明DTGR能够适应无人机自组网中动态变化的网络拓扑与异常的节点，通过与环境的交互学习最优路由决策，降低时延。

图3 不同协议的训练曲线

选择异常节点数比例为0.05,0.1,0.15,0.2和0.25对协议进行测试，验证DTGR在不同异常节点比例下的平均端到端时延和包递交率，结果如图4所示。可以看出当异常节点比例升高时，所有协议的时延都在上升、包递交率都在下降。这与直觉相符，因为当总节点数量固定时，异常节点数量越多则传输链路包含异常节点的概率增大、转发成功的概率减小、传输时延提升。另外DTGR相比于其他协议拥有最低的时延、最高的包递交率。其原因是DTGR能够感知节点的信任度。当邻居节点具有不同位置和信任度时，GPSR和QNGPSR的路由选择过程等价于最短路近似算法，异常节点被选择的概率增多，造成更多的丢包和时延的增加。而DTGR利用神经网络评估每个节点潜在的路由能力，选择网络性能最优的下一跳。实验结果说明了DTGR在异常节点的密度发生改变时，相较其他协议能进行更优的路由决策，保障网络性能。

图4 异常节点比例对协议性能的影响

图5展示了总节点数量为40,60,80,100,120时，不同协议的性能。从图5可以看出，当节点数量在60及以上时，DTGR拥有最优的平均端到端时延和包递交率。总节点数量为40时DTGR包递交率略低于GPSR和QNGPSR，这是因为DTGR不具备周边转发模式[8]。周边转发模式会在节点无可选下一跳时，尝试重传数据包给已转发过的节点，在节点数量稀疏、可达链路很少时此模式能显著增加包递交率。但重复选择异常节点会引入额外的时延增加通信开销，故DTGR放弃使用周边转发模式。此外，DTGR和QNGPSR协议在节点数量为60和80时，平均端到端时延大幅低于GPSR，这是因为通信过程中存在大量空洞区域[10]。这一结果也验证了本文对邻居拓扑信息的优化是合理正确的，DTGR能够使用降维后的位置特征评估两跳节点的位置优势，减少进入空洞区域的概率，最终降低时延。在总节点数量较大的UANET中，采用DTGR算法的网络性能更好。

图5 总节点数量对协议性能的影响

5 结论

无人机路由协议需要考虑频繁变化的网络拓扑和异常节点的评估，本文提出一种基于深度强化学习的可信无人机地理路由协议DTGR。利用可信第三方提供节点信任度，减少了检测成本。改进了邻居拓扑信息，降低了计算开销。仿真实验表明，DTGR能够在高移动性且存在异常节点的网络中根据节点特征选择最优下一跳。在端到端时延和包递交率两个指标上，DTGR的表现均优于其他协议。此外，DTGR能够适应异常节点数量和密度的改变，自适应做出有效且高效的路由决策，鲁棒性好。DTGR为无人机自组网提供了高效可靠的网络通信方案。