开放科学（资源服务）标志码（OSID）：

0 概述

近年来，无人机在抢险救灾^[1]、应急通信^[2]、目标侦查^[3]、城市交通管理^[4]、中继网络^[5]等领域得到广泛应用。与传统的移动自组织网络（Mobile Ad-hoc Network，MANET）^[6]相比，无人机自组网（Flying Ad-hoc Network，FANET）^[7]的网络动态性更强、链路变化更为剧烈且网络稳定性更差^[8-9]。此外，无人机集群的状态存在编队飞行和自主飞行2种状态，在不同的状态下，FANET会表现出不同的网络特性。为了提升FANET的网络性能，确保较低的端到端延迟以及较高的数据包投递率，必须针对FANET的网络特点设计与之匹配的路由协议。

本文在优化链路状态路由（Optimized Link State Routing，OLSR）^[10]协议的基础上，提出一种无人机网络适用路由（UAV-OLSR）算法。在算法设计过程中考虑无人机集群的飞行状态，选择高质量的节点作为多点中继（MPR）节点，同时引入多径的思想，通过路径评估选择较优路径进行当前数据包转发。在数据转发过程中，采用备选转发机制来确保数据包能够被正确投递。

1 相关研究

针对FANET的路由研究主要有2个方向：一是对传统MANET路由进行改进，使其适合于FANET的网络特性；二是结合实际应用场景的特性，针对FANET设计一种全新的路由协议。

YI等^[11]介绍一种具备移动和负载感知的增强OLSR路由协议（ML-OLSR），通过获取UAV节点的地理位置计算节点的稳定性，实现移动感知，并通过负载感知算法实现负载均衡，最后将移动感知用于MPR选择，将负载感知用于路径选择，仿真结果表明，ML-OLSR可以有效提高数据包投递率并降低平均端到端延迟，但是，其对比对象仅为OLSR，过于单一。OUBBATI等^[12]设计一种FANET环境下的节能路由ECaD，其采用与AODV类似的路由发现方法，NS2下的仿真结果表明，ECaD能够有效均衡网络中节点的能量消耗，但是，其在平均端到端延迟方面表现欠佳。

PI等^[13]提出一种全新的分布式路由算法RBDR，其主要创新点在于为每个节点定义信誉度的概念，该路由算法能够有效降低无人机网络节点的能量和存储空间消耗，并能适应网络的高动态性，但是，RBDR降低能耗的代价是数据包平均传输延迟有所增加。LADTR^[14]是针对灾害环境下的无人机网络设计的一种路由协议，该协议中引入了轮渡无人机，并结合定位辅助转发与存储转发技术，可以有效降低端到端延迟并提高数据包投递率，但是，轮渡无人机的负载较大，会使得网络生存时间缩短。文献[15]将无人机的放置与预测性路由相结合，从而提升网络容量，但其仅适用于无人机运动轨迹可控的情况。ECoR^[16]是一种能量感知路由，可以根据无人机节点的剩余能量进行任务卸载，但其重点关注延长网络的生存时间，没有考虑如何提升网络性能。

上述研究工作多是针对FANET的某一特点进行设计，具有一定的局限性。本文提出的路由策略综合考虑无人机节点耗能、网络服务质量（QoS）^[17]等因素，进而实现较优的数据路由。

2 UAV-OLSR算法设计

OLSR的核心在于MPR，通过MPR机制能够有效降低路由开销。OLSR通过HELLO消息和TC消息感知全网拓扑，每个节点都维护一个邻居链路集合$ {L}_{s} $、一跳邻居集合$ {N}_{1\_s} $、两跳邻居集合$ {N}_{2\_s} $以及网络拓扑集合$ {T}_{s} $。

UAV-OLSR基于OLSR设计实现，路由设计包含无人机集群状态感知、MPR节点选取、多径路由设计以及数据转发策略4个部分。

2.1 无人机集群状态感知

本文考虑无人机集群编队飞行以及自主飞行2种状态：对于编队飞行状态，认为无人机集群的节点保持相对静止状态，网络拓扑结构可认为保持不变；对于自主飞行状态，无人机集群中的每个节点都有随机的移动方向和速度，网络的拓扑结构变化较为剧烈。

网络的拓扑变化情况能够直观反映无人机集群的不同飞行状态，因此，可以通过网络的拓扑变化情况估计无人机集群的飞行状态。UAV-OLSR通过$ {N}_{1\_s} $与$ {T}_{s} $的变化情况共同感知无人机集群的飞行状态，前者表示为$ {N}_{c} $，后者表示为$ {T}_{c} $，相关定义如下：

1）$ {N}_{c} $：节点在当前HELLO消息间隔时间内新增或删除的一跳邻居节点数目，计算如式（1）所示：

$ {N}_{c}={n}_{\mathrm{a}\mathrm{d}\mathrm{d}\mathrm{e}\mathrm{d}}+{n}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{t}} $

(1)

其中：$ {n}_{\mathrm{a}\mathrm{d}\mathrm{d}\mathrm{e}\mathrm{d}} $、$ {n}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{t}} $分别代表当前HELLO消息周期间隔内新增、删除的一跳邻居节点数目。

2）$ {T}_{c} $：节点在当前TC消息间隔时间内新增或删除的网络拓扑链接数目，计算如式（2）所示：

$ {T}_{c}={t}_{\mathrm{a}\mathrm{d}\mathrm{d}\mathrm{e}\mathrm{d}}+{t}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{t}} $

(2)

其中：$ {t}_{\mathrm{a}\mathrm{d}\mathrm{d}\mathrm{e}\mathrm{d}} $代表当前TC消息周期间隔内新增的拓扑链接数目；$ {t}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{t}} $代表当前TC消息周期间隔内删除的拓扑链接数目。

用符号“0”代表编队飞行状态，符号“1”代表自主飞行状态，则无人机集群的飞行状态通过式（3）确定。

$ S=\left\{\begin{array}{l}1, {N}_{c}>{T}_{\mathrm{t}\mathrm{h}}^{1}\\ 1, {T}_{c}>{T}_{\mathrm{t}\mathrm{h}}^{2}\\ 1, \frac{{N}_{c}}{{n}_{nb}}>{T}_{\mathrm{t}\mathrm{h}}^{3}\\ 1, \frac{{T}_{c}}{{n}_{tp}}>{T}_{\mathrm{t}\mathrm{h}}^{4}\\ 0, \mathrm{ }\mathrm{e}\mathrm{l}\mathrm{s}\mathrm{e}\end{array}\right. $

(3)

其中：$ {n}_{nb} $为节点当、前的邻居节点个数；$ {n}_{tp} $为节点当前拓扑集合中的元素个数；$ {T}_{\mathrm{t}\mathrm{h}}^{i}(i=\mathrm{1, 2}, \mathrm{3, 4}) $为阈值。

$ S $的取值进一步影响网络中路由控制消息的发送频率，具体地，UAV-OLSR会根据$ S $的值改变HELLO消息和TC消息的发送间隔，设置方式如式（4）所示：

$ ({H}_{\mathrm{i}\mathrm{v}\mathrm{l}}, {T}_{\mathrm{i}\mathrm{v}\mathrm{l}})=\left\{\begin{array}{c}({I}_{h\_q}, {I}_{t\_q}), S=1\\ ({I}_{h\_s}, {I}_{t\_s}), S=0\end{array}\right. $

(4)

其中：$ {I}_{h\_q}\mathrm{、}{I}_{h\_s}\mathrm{、}{I}_{t\_q}\mathrm{、}{I}_{t\_s} $为预设的变量值。改变消息发送间隔的同时需要改变消息的有效时间，具体地，$ {V}_{\mathrm{h}\mathrm{e}\mathrm{l}\mathrm{l}\mathrm{o}}=3{H}_{\mathrm{i}\mathrm{v}\mathrm{l}} $，$ {V}_{\mathrm{t}\mathrm{c}}=3{T}_{\mathrm{i}\mathrm{v}\mathrm{l}} $。

当无人机集群处于自主飞行状态时，节点会保持较高的HELLO消息和TC消息发送频率，从而确保网络拓扑能够及时更新；反之，节点会降低HELLO消息和TC消息的发送频率，从而降低自身能耗并减少路由开销。

2.2 MPR节点选取

在OLSR路由协议中，MPR节点选取将直接影响路由开销，并在较大程度上影响网络路由的可靠性。因此，为了建立可靠的端到端路由，确保网络性能，必须选择合适的MPR节点。在FANET中，节点的高动态性会使得链路的通断变得更加频繁，因此，在MPR节点的选取过程中，应考虑节点的稳定性。此外，无人机节点的能量通常较为有限^[18]，为了平衡网络中的能量消耗，在进行MPR节点选取时，应考虑节点的能量因素。

为实现可靠的MPR节点选取，在UAV-OLSR中定义如下3个参量：

1）链路变化率（$ {L}_{cr} $），计算如式（5）所示：

$ {L}_{cr}=\frac{{N}_{c}}{{n}_{nb\_c}} $

(5)

其中：$ {N}_{c} $的定义如式（1）所示；$ {n}_{nb\_c} $为当前一跳邻居节点的个数。

2）剩余能量百分比（$ {P}_{re} $），计算如式（6）所示：

$ {P}_{re}=\frac{{p}_{c}}{{p}_{t}} $

(6)

其中：$ {p}_{c} $为当前剩余能量；$ {p}_{t} $为节点初始能量。

3）节点中心度（$ {R}_{c} $），计算如式（7）所示：

$ {R}_{c}=\frac{{n}_{nb\_c}}{{n}_{2nb\_c}} $

(7)

其中：$ {n}_{nb\_c} $（$ {n}_{2nb\_c} $）为当前的一跳（两跳）邻居节点数目。

进一步地，对上述3个变量进行非线性映射处理，得到可用于评估节点质量的参数$ {E}_{\mathrm{E}\mathrm{P}}^{i} $（$ i $=1，2，3）。

1）对于$ {L}_{cr} $，映射方法为：$ {E}_{\mathrm{E}\mathrm{P}}^{1}=\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{ }\{{L}_{cr}, 1\} $。

2）对于$ {P}_{re} $，其数值越大，代表节点的能量越充足，且当其数值小到一定程度时，对网络的影响会更加明显，因此，采用如下的方式进行映射处理：$ {E}_{\mathrm{E}\mathrm{P}}^{2}=1-(1-{P}_{re}{)}^{3} $。

3）对于$ {R}_{c} $，其值越小，代表节点所处的位置越接近网络中心，节点的评分也就越高，因此，使用双曲正切函数进行映射处理：$ {E}_{\mathrm{E}\mathrm{P}}^{3}=1-\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{h}\mathrm{ }\left({R}_{c}\right) $。

最后对各个指标进行加权求和，得到节点质量的评估结果$ {E}_{\mathrm{E}\mathrm{P}}^{} $。本文采用层次分析法（AHP）^[19]进行加权系数确定。在本文方案中，认为3个参数的重要性排序为：$ {E}_{\mathrm{E}\mathrm{P}}^{1} $，$ {E}_{\mathrm{E}\mathrm{P}}^{2} $，$ {E}_{\mathrm{E}\mathrm{P}}^{3} $。构造判断矩阵$ \boldsymbol{A}=({a}_{ij}{)}_{3\times 3} $，其中：$ {a}_{ii}=1(i=\mathrm{1, 2}, 3) $；$ {a}_{12}=2 $；$ {a}_{13}=3 $；$ {a}_{23}=2 $；$ {a}_{ij}\times {a}_{ij}=1 $。矩阵A的最大特征值所对应的特征向量（归一化值）即为$ {E}_{\mathrm{E}\mathrm{P}}^{1} $、$ {E}_{\mathrm{E}\mathrm{P}}^{2} $以及$ {E}_{\mathrm{E}\mathrm{P}}^{3} $的加权系数，得到$ {E}_{\mathrm{E}\mathrm{P}}^{} $的表达式如下：

$ {E}_{\mathrm{E}\mathrm{P}}^{}=0.539\mathrm{ }6\times {E}_{\mathrm{E}\mathrm{P}}^{1}+0.297\mathrm{ }0\times {E}_{\mathrm{E}\mathrm{P}}^{2}+0.163\mathrm{ }4\times {E}_{\mathrm{E}\mathrm{P}}^{3} $

(8)

在改进的MPR选择算法中，不再使用节点意愿度（willingness）的概念，而是使用节点质量评分$ {E}_{\mathrm{E}\mathrm{P}}^{} $作为相应的标准，算法流程与标准OLSR中的选取算法类似。

2.3 多径路由设计

在FANET中，高速移动的节点会降低路由的可靠性，因此，可建立多条从源到达目的端的路径，以降低链路不稳定所带来的影响。同时制定合适的路由度量标准，选择较优的一条路径作为当前数据包的转发路径。

2.3.1 路径度量

在标准OLSR中，通过数据包从源到达目的端所需要进行的转发次数来对路径进行度量，但在部分情况下最少的转发次数并不是最佳的路径选择。针对该问题，有研究人员选择期望传输次数（ETX）^[20]、节点密度参数和干扰率^[21]、能源效率度量标准（RESDN）^[22]等作为路径度量标准，以选择较优的路径进行数据转发。

在UAV-OLSR中，本文考虑影响路径质量的多个指标，并综合这些指标对路径的质量进行定量描述。其中，考虑的因素包括路径上节点的剩余能量占比（$ {P}_{re} $）、节点的对称一跳邻居节点比例（$ {R}_{s\_n} $）、节点的质量评分（$ {E}_{\mathrm{E}\mathrm{P}}^{} $）、节点的可用缓冲区比例（$ {R}_{r\_b} $）以及数据转发所需跳数（H_HOP）。部分参量通过在HELLO消息包和TC消息包中添加额外的字段（$ {P}_{re} $（16 bit）、$ {R}_{s\_n} $（8 bit）、$ {E}_{\mathrm{E}\mathrm{P}}^{} $（8 bit）、$ {R}_{r\_b} $（8 bit））实现全网感知。

$ {P}_{re} $和$ {E}_{\mathrm{E}\mathrm{P}}^{} $的定义分别如式（6）和式（8）所示，H_HOP是指数据从源到达目的端所需要的转发次数。$ {R}_{s\_n} $定义为节点的对称一跳邻居节点数量与节点的一跳邻居数量集合中节点数量的比值：

$ {R}_{s\_n}=\frac{{n}_{\mathrm{s}\mathrm{y}\mathrm{m}}}{{n}_{\mathrm{a}\mathrm{l}\mathrm{l}}} $

(9)

其中：$ {n}_{\mathrm{s}\mathrm{y}\mathrm{m}} $为对称一跳邻居节点数量；$ {n}_{\mathrm{a}\mathrm{l}\mathrm{l}} $为一跳邻居节点总数量。

$ {R}_{r\_b} $定义为缓冲区可用的队列长度与初始化的缓冲区队列长度最大值的比值：

$ {R}_{r\_b}=1-\frac{{q}_{\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{d}}}{{q}_{\mathrm{a}\mathrm{l}\mathrm{l}}} $

(10)

其中：$ {q}_{\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{d}} $是当前缓冲区中排队等候的数据包数量；$ {q}_{\mathrm{a}\mathrm{l}\mathrm{l}} $是初始化的缓冲区队列长度最大值。

此外，在从源到目的端的路径上，本文对除去源节点和目的节点的其余节点的$ {R}_{s\_n} $、$ {R}_{r\_b} $、$ {P}_{re} $、$ {E}_{\mathrm{E}\mathrm{P}}^{} $进行分析。对于$ {R}_{r\_b} $、$ {P}_{re} $和$ {E}_{\mathrm{E}\mathrm{P}}^{} $，取其最小值作为整条路径的度量参数。对于$ {R}_{s\_n} $，将路径上节点$ {R}_{s\_n} $值的乘积作为路径度量参数。最后，分析相关参数对路径质量的影响类型，并将它们分为加性影响和乘性影响两类。路径度量准则$ {R}_{\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{u}\mathrm{r}\mathrm{e}} $定义如下：

$ \begin{array}{*{20}{l}} {{R_{{\rm{meaure}}}} = \frac{1}{{{H_{{\rm{HOP}}}}}}\left[ {{\alpha _1} \cdot _{n\left( i \right)}^{{\rm{min}}}\left( {{E_{{\rm{EP}}}}} \right) + {\alpha _2} \cdot _{n\left( i \right)}^{{\rm{min}}}\left( {{P_{re}}} \right) + } \right.}\\ {\left. {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\alpha _3} \cdot _{n\left( i \right)}^{{\rm{min}}}\left( {{R_{r\_b}}} \right) + {\alpha _4} \cdot \prod\limits_{n\left( i \right)} {\left( {{R_{s\_n}}} \right)} } \right]} \end{array} $

(11)

其中：$ {\alpha }_{i}(i=\mathrm{1, 2}, \mathrm{3, 4}) $为加权系数，通过层次分析法确定；$ _{n\left( i \right)}^{{\rm{min}}}\left( x \right) $表示对所有的非源节点和目的节点$ n\left(i\right) $取$ x $的最小值；$ \prod\limits_{n\left( i \right)} {\left( x \right)} $表示所有非源节点和目的节点的$ x $连乘。

2.3.2 多径计算

在UAV-OLSR中，针对目的节点与源节点的距离制定了不同的多路径计算策略，并采用按需计算的方法进行多路径计算。具体地，将目的节点分为一跳可达节点、两跳可达节点、其余类型节点三类。

对于一跳可达节点，为其建立最多2条路径：$ {r}_{1} $为从源到目的地的直接路径；$ {r}_{2} $为经过一次中转的路径，且中转节点也为源节点的邻居节点。需要注意的是，$ {r}_{2} $存在的条件为目的节点既是源节点的一跳邻居节点也是其两跳邻居节点。

对于两跳可达节点，为其建立不超过3条路径：$ {r}_{1} $和$ {r}_{2} $都为最短路径（转发次数最少，下同）；$ {r}_{3} $为次短路径（路径长度为最短路径长度加1）。两跳可达节点多径计算方法描述如算法1所示。

算法1  两跳可达节点多径计算算法

输入  一跳邻居集合$ {N}_{1\_s} $，两跳邻居集合$ {N}_{2\_s} $，拓扑集合$ {T}_{s} $，目的节点d

输出  最短路径$ {r}_{1} $、$ {r}_{2} $，次短路径$ {r}_{3} $

Begin

$ {\mathrm{r}}_{1}={\mathrm{r}}_{2}={\mathrm{r}}_{3}= $NULL；

Create（$ {\mathrm{r}}_{1} $，$ {\mathrm{r}}_{2}, {\mathrm{N}}_{2\_\mathrm{s}} $，d）；/*在两跳邻居集合中查找到达d的2条最短路径*/

For e in $ {\mathrm{N}}_{1\_\mathrm{s}} $：/*迭代$ {N}_{1\_s} $中的每一个节点*/

If $ (\mathrm{e}\in {\mathrm{N}}_{2\_\mathrm{s}}\&\&(\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{k}(\mathrm{e}, \mathrm{d})) $：/*如果e属于$ {\mathrm{N}}_{2\_\mathrm{s}} $且存在一条边的2个端点为e和d*/

Build（$ {\mathrm{r}}_{3} $）；/*新建$ {\mathrm{r}}_{3} $并判断其有效性（与$ {\mathrm{r}}_{1} $、$ {\mathrm{r}}_{2} $的交点仅为源和目的节点时有效）*/

If（$ {\mathrm{r}}_{3} $）：break；/*得到有效路径，结束*/

End if

End if

End for

If（$ {\mathrm{r}}_{3} $==NULL）：

Find（$ {\mathrm{r}}_{3}, {\mathrm{T}}_{\mathrm{s}} $）；/*按照前述步骤在$ {\mathrm{T}}_{\mathrm{s}} $中寻找$ {\mathrm{r}}_{3} $*/

End if

End

对于最少需三跳到达的节点，多径计算方法描述如算法2所示。

算法2  多跳（大于2）可达节点多径计算算法

输入  一跳邻居集合$ {N}_{1\_s} $，两跳邻居集合$ {N}_{2\_s} $，拓扑集合$ {T}_{s} $，目的节点d

输出  最短路径$ {r}_{1} $、$ {r}_{2} $，次短路径$ {r}_{3} $

Begin

$ {\mathrm{r}}_{1} $=$ {\mathrm{r}}_{2} $=$ {\mathrm{r}}_{3} $=NULL；

$ {\mathrm{T}}_{\mathrm{m}\_\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}} $=NULL；/*临时等长度多径路由表*/

/*第1步，添加一跳邻居路由*/

Create_1（$ {\mathrm{T}}_{\mathrm{m}\_\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}}, {\mathrm{N}}_{1\_\mathrm{s}} $）；/*为一跳邻居建立单路径，存储于$ {\mathrm{T}}_{\mathrm{m}\_\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}} $*/

/*第2步，添加两跳邻居路由*/

Create_2（$ {\mathrm{T}}_{\mathrm{m}\_\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}}, {\mathrm{N}}_{1\_\mathrm{s}}, {\mathrm{N}}_{2\_\mathrm{s}} $）；/*为两跳邻居建立不超过2条路径，路径长度为2*/

/*第3步，循环递推到达目的节点的路径*/

If（！$ {\mathrm{T}}_{\mathrm{m}\_\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}} $.find（d） & & $ {\mathrm{T}}_{\mathrm{m}\_\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}} $.refresh（））：/*不存在到达d的路径，且$ {\mathrm{T}}_{\mathrm{m}\_\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}} $存在更新*/

For t in $ {\mathrm{T}}_{\mathrm{s}} $：/*迭代*/

P₁=$ {\mathrm{T}}_{\mathrm{m}\_\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}} $.find（t.s）；/*到达t的端点t.s的路径*/

P₂=$ {\mathrm{T}}_{\mathrm{m}\_\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}} $.find（t.e）；/*到达t的端点t.e的路径*/

If（P₁ & & ！P₂）：/*存在到达t.s的路径，不存在到达t.e的路径*/

Create_t₁（$ {\mathrm{T}}_{\mathrm{m}\_\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}} $，t）；/*得到到达t.e的m条路径，m=1或2*/

Else if（P₁ & & P₂ & & P₁.length+1=P₂.length）：/*路径长度差1*/

Create_t₂（$ {\mathrm{T}}_{\mathrm{m}\_\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}} $，t）；/*得到到达t.e的2条最短路径，若有多条路径选择，按照式（12）选择重复度低的2条路径*/

End if

End if

End for

End if

If（$ {\mathrm{T}}_{\mathrm{m}\_\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}} $.find（d））：/*存在路径*/

[$ {\mathrm{r}}_{1} $，$ {\mathrm{r}}_{2} $]=$ {\mathrm{T}}_{\mathrm{m}\_\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}} $.find（d）；/*最短路径*/

For t₂ in $ {\mathrm{T}}_{\mathrm{s}} $：

Build_r₃（t₂，$ {\mathrm{r}}_{3}, {\mathrm{r}}_{1} $，$ {\mathrm{r}}_{2} $）；/*判断能否通过t₂建立一条次短路径，且选择和$ {\mathrm{r}}_{1} $，$ {\mathrm{r}}_{2} $的公共节点较小的路径作为当前$ {\mathrm{r}}_{3} $*/

End for

End if

End

路径a和b的重复度定义如下：

$ {p_{re}}(a, b) = \frac{{\sum\limits_{i = 1}^M n \left( i \right) \cdot {2^{M - i}}}}{{\sum\limits_{i = 1}^M i \cdot {2^{M - i}}}} $

(12)

其中：$ M=h $为路径上的节点个数（不含源节点和目的节点）；E为长度为h的数组，若路径a与b中第$ j $个节点一致（不含源节点和目的节点），则E中位置j处的元素为1，反之为0；$ n\left(i\right) $表示E中连续$ i $个1出现的次数，例如$ E=[\mathrm{1, 1}, \mathrm{1, 0}, \mathrm{1, 0}] $，则$ n\left(1\right)=4 $，$ n\left(2\right)=2 $，$ n\left(3\right)=1 $，$ n\left(4\right)=n\left(5\right)=n\left(6\right)=0 $。

2.3.3 多径维护

UAV-OLSR的多径路由采用按需计算，因此仅对多径路由表中已有的路由进行维护。为每组路径（$ s->d $）定义一个有效时间$ t $，每隔一个HELLO周期对$ t $进行更新。若在当前HELLO周期内该组路径被使用，则$ t $设置为最大值；反之，将$ t $减1。若$ t $ ≤ 0，则该组路径记为失效，从路由表中将其删除。

当前节点接收到HELLO消息或TC消息后，将对路由表进行更新。首先检查每组路由的有效时间$ t $，若$ t\le 0 $，则将该组路径删除；反之，对路由项进行更新，每组路径的更新步骤如下：

1）计算到目的节点的最短路径所需跳数，如果该值与当前路由表中该组路由的最少跳数一致，则进入第2步，反之进入第4步。

2）检查路径的连通性，如果路径仍连通，则进入第3步，反之进入第4步。

3）计算该组路径中每条路径的度量分数，如果其最大值小于阈值$ \phi $，则进入第4步，反之进入第5步。

4）按照2.3.2节所述方法重新计算到达目的节点的多条路径并选择度量分数较大的路径作为备选。

5）对每条路径的度量分数进行更新。

2.4 数据转发策略

在UAV-OLSR中，多径路由仅在源节点进行计算，且路径信息包含在数据包的IP头部，中间节点根据IP头部的路径信息进行数据转发。由于网络拓扑更新存在延迟，源节点计算的路径可能存在部分无效的情况。为解决该问题，本文在UAV-OLSR中保留了OLSR原有的路由表，若中间节点检测到数据包头部的路径信息无效，则中间节点对数据包头部信息进行修改，并将数据包按照标准OLSR中的转发方式进行转发。

3 仿真分析

为验证UAV-OLSR的有效性，在NS2中进行网络仿真测试，并将UAV-OLSR与AODV、OLSR进行比较。对于自组织网络而言，其性能参数包括数据包投递率、端到端延迟、端到端吞吐量等，由于无人机节点的能量高度受限，因此网络生存时间也是FANET需要考虑的关键因素。

在仿真测试中，主要分析FANET的数据包投递率、平均数据包传输延迟和网络节点剩余能量。在数据包大小已知的情况下，数据包投递率和平均传输延迟也可以间接反映网络吞吐量，网络节点剩余能量最小值是指某一时刻网络中所有节点的剩余能量最小值，该值越大，代表网络的生存时间越长。仿真测试部分关键参数如表 1所示。

具体地，建立一个固定大小的仿真区域，随机初始化无人机节点的位置，并让每个节点随机移动，在网络中随机生成固定数目的数据流（cbr流），按照预设的仿真时间进行网络仿真，并对仿真得到的数据进行处理，进而分析网络的相关性能。

图 1所示为某时刻的网络拓扑，图中不同的线条箭头代表不同的数据流（仅列出部分）。网络节点的移动具有较大的随机性，因此，网络拓扑会呈现出高度的动态性。

在仿真过程中，节点剩余能量百分比的最小值随时间的变化情况如图 2所示。在仿真初始阶段，由于各节点剩余能量的百分比都较大，能量均衡效果并不明显，因此，不同路由协议的节点剩余能量之间差异较小。随着仿真的进行，不同路由协议的能量均衡效果差异逐渐体现出来，具体表现为曲线在垂直方向上的间隔逐渐扩大，由于OLSR接收到HELLO消息或者TC消息后都会进行路由更新，因此其节点间的能量均衡效果优于AODV，而UAV-OLSR采用了能量均衡设计，其性能表现更优于OLSR。

图 3和图 4所示分别为数据包的平均传输延迟和丢包率情况，曲线上点的纵坐标代表以当前横坐标为中心的一个时间区间内的统计平均值。从图 3可以看出，在仿真起始阶段，因为网络中拥塞现象不明显，所以3种路由协议的数据包平均延迟基本一致，在网络仿真过程中，OLSR路由协议的数据包平均传输延迟在多数情况下比AODV路由协议低，而UAV-OLSR协议的数据包平均传输延迟始终低于OLSR和AODV。从图 4可以看出，在仿真起始阶段，3种路由协议的性能差异并不明显，在整个仿真过程中，OLSR与AODV的数据包投递率差异不明显，而UAV-OLSR的数据包投递率明显高于OLSR与AODV。

4 结束语

本文针对无人机自组网的高动态特性以及节点能量高度受限的特点，提出一种基于OLSR的无人机网络适用路由协议UAV-OLSR。通过无人机集群状态感知机制调整路由协议的相关参数，进而适应无人机集群的状态变化。根据多维度的节点质量评估和路径评估机制选择可靠的中间节点进行数据转发。使用自定义的多路径计算方法计算从源到达目的端的多条路径，并结合路径评估和数据转发策略选择较优的路径进行数据转发。实验结果表明，与OLSR、AODV等传统移动自组网路由协议相比，UAV-OLSR能够提高数据包投递率，降低数据包延迟，从而实现较好的网络能量均衡。下一步将在UAV-OLSR的基础上引进节点休眠机制，以延长网络的生存时间。