基于函数逼近的强化学习FANET 路由优化算法

谢勇盛，杨余旺，邱修林，王吟吟

（南京理工大学计算机科学与工程学院，南京 210094）

0 概述

近年来，无人机群在森林防火、智能农业、渗透侦察、火力打击等民用和军用领域具有广泛应用。为完成复杂的协同任务，稳健的通信方式是必不可少的。移动自组网（Mobile Ad-Hoc Network，MANET）［1］作为一种无中心、多跳、自治的无线网络，被认为是最适合无人机的通信方式之一［2-3］。在MANET 中，每个节点不仅作为终端主机，也充当转发消息的路由器。但由于节点是移动的，这导致通信链路的频繁变化，因此需要一个能够帮助网络组网和维护链路稳定的路由协议。目前，对MANET 路由协议的研究已经有了很大的发展，根据不同的路由策略，可将路由协议分为主动路由协议、按需路由协议和混合路由协议。在主动路由协议中，在进行业务传输前，节点主动探测周边邻居节点并维护链路信息。这种优先确定路由链路的方式相较按需路由协议和混合路由协议具有更高的实时性［4］。但由于无人机节点移动速度快，网络拓扑变化迅速，传统的MANET 路由协议已经难以满足无人机通信组网的需求，为此研究人员提出飞行自组网（Flying Ad-Hoc Network，FANET）［5］，因此探究适用于FANET 环境的路由技术对改善网络性能具有着重要的意义。

FANET 虽源于MANET，但 比MANET 有着更复杂的应用环境，具有高动态性、高稀疏性、链路质量多变等通信特点，为建立稳定链路带来很大困难。因此，FANET 路由协议应综合考虑无人机应用、服务器性质、节点高速移动等特性。常见的FANET 路由协议设计思路源于对传统的MANET 路由协议进行适当改进。MANET 研究初期的路由协议对节点移动性并不敏感，若要使网络适应飞行节点的动态特性，则需要节点自身能够通过问候消息（即HELLO 消息）或链路层反馈机制探测和维护可连通邻居节点，以此保障链路畅通。与链路反馈机制相比，通过路由协议定期交换问候消息更优，因为前者并不受限于任何特定的链路层技术［6］。这种主动发送探测包的路由技术在MANET 中被称为主动路由协议，其中应用较广泛的为最优链路状态路由（Optimal Link State Routing，OLSR）［4］协议。

但对于高动态FANET 而言，这种定期交换HELLO 消息的路由协议难以适应多变的网络环境。在主动路由协议中，HELLO 消息时隙的选择对于链路的发现起着决定性的作用［3］。时隙越短，越有助于快速检测新邻居或链路中断，但会产生更高的开销，阻碍正常数据包的发送。时隙越长，开销会越少，但会限制邻居发现和链接中断检测能力。在高动态FANET 中，需要在实时感知环境的同时自适应修改HELLO 时隙并优化整个网络性能［7-8］。针对FANET 高动态网络场景下的节点链路探测问题，本文对传统OLSR 算法进行改进，提出一种基于强化学习的自适应链路状态路由算法QLA-OLSR。通过感知动态环境下节点邻居数量变化程度和业务负载能力，获取最优HELLO 时隙决策，并利用自学习不断调整和完善这一决策，以达到优化网络性能的目的。

1 相关工作

主动路由协议节点定期发送HELLO 消息，探测周围链路情况，能帮助网络更快地适应环境。但无人机高速移动和分布稀疏的特性又造成了节点交汇的时间减少、相遇的可能性降低等问题。针对传统MANET 路由协议的HELLO 时隙改进以适应节点高速运动，一些研究人员提出了不同的方案。

MAHMUD 等［7］提出一 种EE-OLSR 路由协 议，通过计算网络密度，感知节点能量消耗、综合节点密度等多种参量达到选择时隙的目的。

HERNANDEZ-CONS 等［9］提出一种基于链路变化率的自适应HELLO 时隙方法。节点统计单位时间内添加或删除的链路总数作为衡量链路变化的标准，如果链路变化率高，则邻居变化快，探测消息时隙缩短，反之，增加时隙。

GIRUKA 等［10］提出另一种解决方案，节点感知自身运动速度，在特定速度时采用响应的时隙发送HELLO 消息。由于节点具有不同速度，因此为高速节点分配了较短的探测报文时隙，为低速节点分配了较长的探测报文时隙，且局部采用最优时隙，达到整个网络性能的均衡稳定。

HAN 等［11］提出一种用于邻居发现的自适应HELLO 消息传递方案。该方案利用平均事件间隔，即节点上两个连续事件（发送或接收数据包）之间的平均时间间隔，估计节点在发送或转发中的活跃程度。如果某个节点在给定时间内未参与任何通信，则无需维护链路状态，在此期间广播HELLO 消息是不必要的，因为抑制不必要的问候消息可节省能量，并且能持续对链路状态进行检测。

2 QLA-OLSR 算法

2.1 Q 学习算法流程

Q 学习［12］是一种智能体在可控马尔科夫域中选取并执行最优动作的强化学习算法，类似于一种动态规划的增量方法，通过不断获取特定状态下特定动作的累计奖惩值，为下一次遇到相似环境状态时选择最优动作提供依据。强化学习不同于机器学习，学习过程没有监督者，智能体通过接收环境反馈奖励信号来评估动作价值，并且反馈是延迟的，表现为一系列状态价值函数对下一步动作的影响。

图1 给出了强化学习流程。智能体通过与环境进行交互获得回报来修正动作，其行为步骤可以表示为一个马尔科夫决策（Markov Decision Process，MDP）过程。MDP 可以描述为一个三元组其基本流程是：当t时刻智能体的状态为st(st∈S)时，智能体会收到环境给予它的回报rt(rt∈R)；智能体根据累计的回报值，做出决策选择动作at(at∈A)并执行；智能体进入新的状态st+1。循环执行这些操作，达到在特定环境下选择最优策略的目的。

图1 强化学习流程Fig.1 Procedure of reinforcement learning

2.2 模型构建

在使用强化学习优化OLSR 路由协议前，需要先将HELLO 时隙调整问题描述为MDP 过程。

2.2.1 状态

无人机节点具有高动态特点，网络拓扑变化可能很复杂，尤其是考虑到网络一直在运行，可用于表示网络的连续高维状态空间，可以生成几乎无限数量的状态。因此，无人机节点需要确定适当的状态变量，以捕获节点选择时隙带来的性能差异并保障学习过程中的易处理性。本文选择以下3 个状态变量：

1）snbr，表示当前节点时间步长Δt内邻居节点变化程度。snbr计算如式（1）所示：

其中：nt表示t时刻邻居表中的节点数目。

2）sload，表示节点接口队列中待发送的数据包个数。

3）ssolt，表示当前节点的HELLO 时隙长度。

节点主要是通过与邻居节点交互HELLO 消息来发现连通链路。频繁的HELLO 消息可以让节点更快地探测出邻居节点的存在，并改变邻居表中节点的数目，但是这也必然会增加网络负载，阻碍节点数据队列中数据的发送。本文通过QLA-OLSR 权衡两者之间的关系，使其处于一个平衡的状态。

2.2.2 动作

选择下一动作是Q 学习的主要目标，也是影响协议性能的关键因素。在本文中动作指定为智能体感知邻居节点拓扑变化和周边环境的变化来更改其HELLO 消息发送时隙。本文使用3 个动作来简化动作空间，如表1 所示。动作指定节点为响应网络环境的变化需要改变其感知时隙，减少时隙必然能加快邻居节点的感知速度，但是随之会带来网络开销的增长，节点通过接收到的奖励来选择一个动作，从而达到感知速度快与网络开销低之间的均衡。

表1 QLA-OLSR 动作Table 1 QLA-OLSR action

2.2.3 效用函数和回报函数

学习的目标是找到调整HELLO 时隙的调整策略，采取决策动作后，接收环境反馈的回报，累计此回报值作为下一次决策的依据。为此，需要根据环境给出回报正负价值的衡量标准，并定义如下效用函数：

其中：C表示节点在时间步t内邻居节点的数量变化程度，计算公式如式（3）所示；L表示当前节点的业务负载能力［13-14］，计算公式如式（4）所示，其中l表示节点的队列缓存长度；α和δ表示邻居节点变化程度和业务负载能力的相对权重，在本文中分别设置为50%。可以直观地看出，该函数能够表示在最大程度上快速平稳邻居节点探测并最大化保留节点转发业务数据的能力。

在连续的效用值中，通过其差值来定义如下回报函数：

其中：ζ表现为一个可调参数。当连续时刻效用函数差值大于ζ时，取两者之差为回报函数，若回报函数为正值，则表现为奖励，若回报函数为负值时，则表现为惩罚。

2.3 算法训练

训练QLA-OLSR 算法试图找到一种策略，该策略选定特定状态下的动作执行，并使智能体所接收到的长期奖励值最大。在QLA-OLSR 中，奖励通过效用值函数，训练策略的目的是自适应调整HELLO时隙变化策略，在高拓扑变化情况下，以最大程度地提高节点感知邻居的速度，达到更高的吞吐量，同时在低拓扑变化情况下，最大程度地减少网络开销。因此，训练算法的学习速度和质量是QLA-OLSR 性能的关键。

Q 学习用一个简单的迭代值去更新决策过程，决策动作记录在一个Q 表中。在时间步t时，对应有一个状态st和一个动作at。算法计算出该时间步的预期折扣奖励Q(st,at)，更新规则如下：

其中：α为学习率，满足0 ≤α≤1；γ为折扣因子，满足0<γ≤1。在Q 学习中所有状态下的Q(st,at)存储在Q 表中。

Q 学习为小规模、离散状态空间问题提供了一个良好的解决方案，并且表现出较好的学习性和收敛性，但在大规模、非离散状态空间中的伸缩性非常差。因为在这种情况下，枚举状态量是无限的，使用Q 表记录每个状态或状态动作的价值函数是不切实际的。为了减少存储大Q 表所需的内存和更新访问状态或动作状态对应的Q值所需的训练时间，在采用RL 算法时，使用函数逼近将相似状态之间的值关联起来，使连续状态空间能够映射到有限的域，添加函数逼近方式后的强化学习流程如图2 所示。

图2 基于函数逼近的强化学习流程Fig.2 Procedure of reinforcement learning based on function approximation

3 基于函数逼近的QLA-OLSR 算法

节点可感知的状态空间是极大且连续的，对于Q 学习算法而言，迭代出完整的Q 表是极具挑战性的。为此，本文采用Kanerva 编码的函数逼近策略，以减少训练所需的状态数量，可以在存在高维连续状态空间的情况下简化Q 学习［15］。

3.1 Kanerva 编码算法

在Kanerva 编码算法中，选择一组原型状态，并用于估计值函数，其中状态值是通过本地原型状态值的线性组合来估算的。在每次迭代中，只有与输入状态相邻的原型状态才会被更新。原型状态由一系列状态变量描述，每个状态变量都有一定的数值范围。在迭代学习之前选择k个原型作为状态集。假设给定状态s和原型状态pi，‖s-pi‖表示两者数值差值，如果相差小于某一定值ε，则认为状态s和原型状态pi相邻，定义s与pi的隶属度μ(s,pi)如下：

若相差大于给定值，则μ(s,pi)=0。考虑到原型状态pi的Q值由其相邻状态共同决定，因此使每一个原型状态pi和动作a维护一个θ(pi,a)，则状态-动作对应的为状态s与动作a的相邻原型状态的θ值之和，具体定义如下：

当智能体在状态s时采取动作a、获得奖励r并进入下一状态s′时，在新的状态下已经选择出了新的动作a′，每个原型pi与动作a维护的θ值更新规则如下：

其中：N是状态s的相邻原型的数量。

对于原型状态集，Kanerva 编码通常从整个状态空间中随机选择一组初始原型开始学习。然而，原型的选择对Kanerva 编码的性能有着重要影响，即估计并分配原型集对于逼近函数能力是非常敏感的，如果原型不能很好地分布在状态空间区域中，可能造成许多输入样本找不到足够的相邻原型，这样很难估计它们的Q值。若原型设置不合理，则会造成大量原型碰撞，使得在强化学习过程中遇到两个不同的状态动作具有相同的隶属度［16］。

3.2 优化的Kanerva 编码算法

由上文可知，每个原型状态pi维护一个半径为ε的接收场，接收场的大小反映原型状态的泛化程度。文献［17］提出一种自适应邻接法，为每个原型接收场调整大小。以该方式管理泛化能力，代替整个学习过程中的固定接收场，但需要在原型饥饿时（接收场过小难以起到函数逼近的功能），将其与避免过度概括进行权衡。

为进一步提高Kanerva 的性能，本文提出一种状态相似度机制（State Similarity Mechanism，SSM），它能够准确测量出多维连续状态空间中的状态相似性，并计算出输入状态与原型状态的相似度等级，以此代替二进制隶属度，具体步骤如下：

1）定义相似距离dij(s,pi)，表示为多维状态空间中n维输入状态与原型状态p=在第j维上的差值平方除以一个恒定方差σ2，如式（10）所示：

2）对相似距离进行归一化处理，表示为相似度等级mij。相似度等级mij在2 个状态变量相同时数值为1，2 个状态变量相差很大时数值接近0，如式（11）所示：

3）在s和p的所有维度中选择最小状态等级作为状态s与原型p的隶属度μ(s,pi)，如式（12）所示：

3.3 算法步骤

将每个节点看作是一个独立的智能体，智能体以当前HELLO 报文时隙为周期感知自身所在状态，并根据当前状态下的Q值选择调整时隙的下一决策，以此进入下一状态，具体算法流程如下：

算法1基于Kanerva 编码函数逼近的时隙决策

对于每个智能体，循环感知自身所在状态，并通过上述算法做出下一步的HELLO 报文时隙调整策略，与此同时不停更新θ值，计算出新的Q值。

4 仿真结果与性能分析

实验选取传统OLSR算法、EE-OLSR算法［7］作为本文QLA-OLSR 算法的比较对象。通过仿真实验对比分析各算法之间的吞吐量与网络开销这两个网络性能指标，根据路由算法在不同迭代次数下的性能表现，验证算法的稳定性与收敛性。

4.1 仿真设置

实验采用NS2 仿真工具进行建模仿真，将每个节点看作是智能体，即要求每个节点有相应的计算能力。在仿真实验中，为方便起见，将每个节点的状态输入到一个智能体中，输出各自不同的时隙结果，有利于智能体获得更多的状态，并且学习效果更好，如图3 所示。

图3 建模仿真框架Fig.3 Framework of modeling and simulation

为体现网络拓扑的高动态性，贴合真实情况下无人机群飞行场景，实验选用高斯马尔科夫模型（Gauss Markov Model，GMM）模拟无人机飞行场景［18-20］，仿真参数设置如表2 所示。

表2 仿真参数设置Table 2 Setting of simulation parameters

4.2 性能分析

4.2.1 网络动态拓扑分析

实验节点以不同速度在GMM 模型下运动仿真无人机飞行实际场景，其中以速度这一变量来直观表示高动态网络拓扑的变化程度［21］。实验目的是在相同业务负载下，模拟QLA-OLSR 算法在高动态FANET 场景下的性能表现，并与EE-OLSR［7］、传统OLSR 算法进行比较，分析各协议的吞吐量与网络开销。

无人机在不同节点移动速度下的网络吞吐量与网络开销如图4 所示，可以看出吞吐量受节点移动速度的影响较大。随着节点移动速度的增加，网络拓扑变化随之加快，原来稳定的链路由于节点离开而断开，新来的节点由于HELLO 消息时隙长而未被发现，节点路由表跟不上链路的变化，因此网络吞吐量降低。但是，在QLA-OLSR 算法中节点能够更快速地感知链路变化，维护新的链路，保持较优的吞吐量。对于网络开销，固定时隙的OLSR 协议在相同时刻发送的HELLO 消息应该是相近的，QLA-OLSR和EE-OLSR 算法在节点移动速度增加时相应的节点需减少时隙，导致开销增加，并且节点在感知链路变化的同时也会感知业务负载，低业务负载的节点会减少HELLO 时隙。由此可见，在不同节点移动速度下，QLA-OLSR 算法相比OLSR 与EE-OLSR 算法具有更优的网络吞吐量和网络开销。

图4 不同节点移动速度下的网络吞吐量和网络开销对比Fig.4 Comparison of network throughput and overhead at different node moving speeds

4.2.2 网络负载分析

实验仿真在不同节点负载任务下，通过调整任务节点的发送数据量，分析相同节点移动速度下各协议的网络吞吐量与网络开销。

无人机在不同IP 业务负载下的网络吞吐量与网络开销如图5 所示，可以看出随着业务负载的增加吞吐量随之增加，但由于网络容量的限制会达到峰值，但在QLA-OLSR 算法中，在不影响网络性能的同时，会减少网络开销以增加网络容量，因此峰值会在更靠后时刻到来。关于网络开销，OLSR 和EE-OLSR算法对于业务负载不形成依赖，因此它们的网络开销变化不明显，但QLA-OLSR 算法在高业务负载时会更倾向于发送业务数据包，从而通过增加时隙来减少HELLO 消息的发送。由此可见，在不同节点业务负载下，QLA-OLSR 算法相比OLSR 与EE-OLSR协议具有更优的网络吞吐量和网络开销。

图5 不同IP 业务负载下的网络吞吐量和网络开销对比Fig.5 Comparison of network throughput and overhead at different IP business loads

4.2.3 算法性能分析

强化学习算法是通过学习过往经验来优化当前动作，当算法稳定后节点只需查找Q值来对下一动作进行选择。Kanerva 编码方式可优化网络状态空间，加快算法收敛，提高算法效率。为验证Kanerva编码方式的优化效果，实验给出了QLA-OLSR 算法的网络性能随迭代次数的变化情况。

如表3 所示，在选定节点移动速度为100 m/s、IP业务负载为50 kb/s 的场景下，QLA-OLSR 算法初始时的性能表现并不好，此时算法随机性较大，但随着学习迭代次数的增加，吞吐量开始逐步上升，网络开销亦逐步下降，当迭代到一定次数时逐步趋于稳定，在没有较大网络波动下算法收敛，可见QLA-OLSR算法具有较好的适应性。

表3 QLA-OLSR 算法性能随迭代次数的变化情况Table 3 The changes of QLA-OLSR algorithm performance with the number of iterations

5 结束语

本文提出一种基于强化学习的自适应链路状态路由算法QLA-OLSR，利用强化学习算法对传统OLSR 协议的HELLO 时隙算法进行优化，使得节点对环境有认知能力，并采用最大回报的方式选择调整时隙的决策。仿真结果表明：相比传统OLSR、EE-OLSR 算法，QLA-OLSR 算法在高动态网络拓扑场景下能够更快适应环境，具有更高的吞吐量和更低的丢包率；在平稳的网络拓扑场景下，在保持较高网络吞吐量的同时，降低了网络开销，为环境多变的FANET 通信提供了有效的解决方案。但由于拓扑控制分组传输也是影响QLA-OLSR 算法性能的重要因素，因此后续将优化拓扑控制分组发送方式，并在时隙算法中考虑无人机在实际场景中节点能量受限这一因素，进一步提升网络性能。