飞行自组网中ECHO协议的连通支配集优化及能量控制方案

Connected dominating set optimization and energy control scheme of ECHO protocol for flying ad hoc network

摘要

在无线多跳网络中，利用虚拟骨干网转发报文可以有效提高网络效率。在现有ECHO协议的基础上，提出了一种ECHO‑OPT优化方案，在关键节点决策过程中考虑节点的能量因素，并在消息转发的过程中对关键节点集中的冗余节点进行优化裁剪。在实验中研究了通信范围对冗余节点的影响并在固定网络密度与动态网络密度下测试协议的网络性能。仿真结果表明，在高密度网络中，ECHO‑OPT相对于ECHO可平均优化4.67个关键节点集大小，同时相对于多点中继（multi-point relay，MPR）与ECHO分别降低了65%与32%的网络负载，而且ECHO-OPT还拥有更高的网络生命周期。

Abstract

In wireless multi-hop networks，using the broadcast backbone to forward messages can effectively improve network efficiency.Based on the existing ECHO protocol，an optimized ECHO-OPT scheme was proposed，which considered the energy factor of nodes in the decision-making process of critical nodes，and optimized the redundant nodes in the critical node set in the process of message forwarding.In the experiments，the influence of communication range on redundant nodes was studied and the network performance of the protocol was tested under fixed network density and dynamic network density.The simulation results show that compared with ECHO，ECHO-OPT can optimize the size of critical node set by an average of 4.67 in high-density networks，and reduce the network load by 65% and 32% respectively compared with MPR and ECHO.At the same time，ECHO-OPT also has a higher network lifetime.

关键词

无人机 / 飞行自组网 / 虚拟骨干网络 / 网络负载 / 连通支配集

Key words

unmanned aerial vehicle / flying ad hoc network / virtual backbone network / network load / unifying connected dominating set

由于工作效率高于单体无人机，无人机集群已广泛应用于遥感、灾后搜救^［1-2］、应急通信^［3-5］等领域。飞行自组网（flying ad hoc network，FANET）是由无人机集群组成的无需依赖于基础设施，以无人机节点作为通信节点的空中多跳自组网^［6］。无线通信的通信范围受到功率的限制，致使无线网络中的节点无法与所有其他节点直接通信，因此需要一个或多个中间节点将数据从源转发到目标，以实现整体的网络全联通^［7］。由于不需要事先建立端到端连接，广播成为多跳无线网络^［8］的常用模式，其中传统和常用的广播模式是泛洪协议^［9］。泛洪协议是路由协议中的一种基本方式，用于在网络中传输数据包。泛洪协议不依赖于具体的拓扑结构或路由表，而是将数据包从一个节点发送到网络中的所有其他节点。泛洪协议的工作原理是当一个节点接收到一个数据包时，它会将该数据包转发给接收者之外的其他所有相邻节点。每个节点重复该过程，直到所有节点都接收到该数据包或者达到某个预定的停止条件为止。

尽管泛洪协议简单且易于实现，但仍旧存在一些问题。首先，泛洪协议会导致网络中数据包的大量冗余，从而增加网络流量和资源消耗。其次，在无任何控制措施下，数据包可能会无限循环地在网络中传播，广播数据充斥网络无法处理，形成“广播风暴”。因此，泛洪协议通常只适用于小型网络或用于特殊目的。为了解决上述问题，许多具有代表性的协议应运而生，如自组织网络按需距离矢量路由协议（Ad hoc on-demand distance vector，AODV）^［10］、动态源路由（dynamic source routing，DSR）^［11］、优化链路状态路由协议（optimized link state routing，OLSR）^［12］等。在OLSR协议中，链路状态信息由被选为多点中继的节点生成，从而减少了网络中泛洪的控制信息，消息只由MPR节点转发进而在很大程度上降低了网络负载。但是，随着无人机节点数量的增加，路由开销也会呈现与节点数量的平方成正比的增长趋势。尽管可以通过降低更新频率来减少开销，但该举措会增加延迟。因此，在无线自组网中，如何以最小的路由维护开销实现快速路由更新并确保网络正常运行成为一个关键问题。在无人机集群中，构建虚拟骨干网^［13］是减少路由开销和消息转发量的有效手段。

虚拟骨干网是一种在物理网络基础上构建的逻辑网络结构，旨在提供用于数据传输和路由的稳定、可靠的网络骨干。虚拟骨干网络的主要目标是优化网络性能，提供高效的数据传输路径。它可以解决网络中的拥塞问题，降低延迟，提高带宽利用率，同时增强网络的可靠性和稳定性。构建虚拟骨干网络的方式通常是通过骨干节点的选取来实现，这些骨干节点通常具备更好的计算和通信能力，并且具有更可靠的连接性。

Toorchi等^［14］基于骨架结构设计提出了一种名为服务器端渲染（server-side rendering，SSR）的路由变形方案，该方案包含一个寻址系统，用于为各个节点提供几何坐标，在此基础上构建了一个具有互连路径的管道。这种路由方案具有低复杂度，并且能够避免消息拥堵，实现管道内的平衡。SSR方案采用几何转发的方式避免整个网络中路由搜索消息的泛滥。统一连通支配集（unifying connected dominating set，UCDS）算法的概念最早由Young等^［15］提出，UCDS算法是一种分布式算法，其中虚拟骨干节点由支配集（dominating set，DS）和连通集（connected set，CS）的成员组成。DS成员负责路由分发和中继转发，而CS成员负责连接控制集的成员。CS成员的选举由节点自行决定，选举结果会广播给相邻的DS成员，最终由DS成员选出CS成员。然而，这个过程繁琐复杂，导致虚拟骨干网的构建效率低下，而且拓扑收敛速度较慢。Liang等^［16］提出一种AMDS算法解决VBN的维护问题，通过动态恢复d-CDS的最小性和连通性以处理FANET的拓扑变化，包括节点的进入、离开和移动，为稳定的虚拟骨干维护问题开发了一个自适应解决方案框架，在路由开销、更新时间和每次拓扑更新的维护成本之间实现更好的权衡。面对网络中一些节点传输半径不稳定的情况，Liang等^［16］为提高对传输范围不稳定的WSN的可靠性，并获得更具鲁棒性的虚拟骨干网络，提出了d‑robust CDS的概念和相应的算法，构造出d‑robust CDS，在不稳定传输范围的无线网络中进行应用。研究中还首次提出了针对d‑robust CDS问题的逼近算法，该算法生成的CDS具有较好的鲁棒性。在最小化路由成本的同时，较小规模的CDS对于网络是有益和必要的。然而，CDS形成所需的信息交换会带来大量的流量开销，在完全分布的自组网中，CDS大小和信息交换间需要存在一种权衡。Farooq等^［17］提出了一种基于无线自组网的连接主导集的点播路由（CDS-OR）机制。该协议确保Hello消息大小不超过一个小的常量，并且网络规模的增加不会影响Hello消息的大小。此外，该协议尝试使用不同节点上行和下行流量，以使网络拥塞最小化。同时，该协议生成了一个最小CDS，并确保广播消息在整个网络范围内可达。该方案通过选择分层连接器形成连接集，在最大独立集的节点之间建立连接，减少路由开销，并在数据包传递率方面表现优异。

在密集且带宽有限的网络中，大多数协议利用控制包来收集拓扑信息。然而，这种依赖控制包的方式对于可伸缩性来说过于重要，并且限制了网络的扩展性。为了解决这个问题，Dusia等^［18］提出了一种名为ECHO的协议，这是第一个确定的、无需预先知道位置的、零控制包的协议，可用于在移动多跳无线网络中进行高效的全网络广播。ECHO协议利用数据包内的信息，以完全分布且独立于源的方式确定关键节点的集合，这些节点的传输足以实现网络范围的广播。然而，随着节点的移动，关键节点的选择频繁出现冗余的情况，而且节点在回复消息时的顺序没有得到控制。在此基础上，如果能量较低的节点被选择为关键节点，则关键节点由于能量耗尽而退出集群时会导致频繁的链路中断。为了解决这一问题，本文提出了一种基于ECHO的优化方案，称为ECHO‑OPT，通过仿真对比验证了该方案的有效性。与此同时，本文提出了一种新的关键节点选择策略，从剩余能量角度出发，确保剩余能量更多的节点更有可能成为关键节点，以此来提高集群的网络寿命，从而保持链路的稳定性。随后分析产生冗余节点的原因，根据数据包中的邻居信息对关键节点进行优化裁剪，在保证关键节点广播覆盖整个集群的前提下，减少集群中关键节点的数量。通过重复实验与对比分析，研究通信范围对CDS大小及包传输比的影响。

1 ECHO‑OPT

ECHO‑OPT协议提出了一种考虑节点能量因素的关键节点选择新策略。同时，分析了冗余节点产生的原因，并进行优化剪裁，缩减了关键节点的数量，降低了网络负载。

1.1 协议流程

ECHO‑OPT协议划分为全泛洪阶段（full flooding，FF）和优化泛洪（optimized flooding，OF）两个阶段，FF阶段的数据包报头由以下字段组成：

origin： 最初发送数据包的节点。

sender： 数据包发送方的节点ID。

previous‑sender： sender第一次收到该报文的发送方节点ID （如果发送方是源节点，则将该字段置为0）。

seq‑num： 数据包从源节点发出后该数据包的唯一序列号。

flood‑indicator： 一个1比特的字段，指示报文是全泛洪阶段报文还是优化泛洪阶段报文。当节点接收到数据包并解析出其中的“flood‑indicator”字段为FF时，它将以泛洪方式转发该数据包。在泛洪过程中，每个节点仅进行一次数据包转发。同时，在此过程中，每个节点会根据关键节点选择策略来确定是否将自身标记为关键节点。当节点接收到标记为FF的数据包时，首先检查数据包中的“seq-num”字段是否重复。存在以下两种情况：

1）若消息不重复，节点将使用数据包中的“sender”字段值覆盖“previous-sender”字段，并将“sender”字段值设置为当前节点的NodeID。同时，节点会设置一个超时定时器“ECHO-timer”，并重新发送数据包。

2）若消息重复，节点将检查“previous-sender”字段是否为自身的NodeID。若是，节点将自己标记为“CRITICAL”关键节点。倘若在“ECHO-timer”规定的时间内没有满足此条件的数据包，则节点将自身标记为非关键节点。

在OF阶段，每个节点都会执行算法1，并根据1.3节中的优化策略对关键节点进行优化。随后，经过优化的关键节点将负责转发数据，图1为ECHO-OPT协议流程。

1.2 关键节点选择策略

在ECHO-OPT中，由于没有控制包的存在，关键节点的选择过程受数据包发送与接收顺序的主导。然而，在无线自组网中，数据链路层通过一种称为载波感知多路访问（carrier sense multiple access，CSMA）的协议控制节点的消息发送顺序^［19］。在CSMA协议中，当一个节点要发送数据时，首先进行信道检测并判断其是否空闲，如果信道正在被其他节点使用，则需要等待一段时间后再次尝试发送。该机制确保了节点之间的公平竞争，以避免碰撞和冲突。

竞争窗口是指在无线通信中等待时间的范围，它由最小竞争窗口大小和最大竞争窗口大小两个参数所确定。当节点在发送数据过程中遇到冲突时，节点会根据一随机数选择一个退避时间，并在［0，CW］进行等待，其中CW代表当前的竞争窗口大小^［20］。冲突发生时，竞争窗口大小将自适应地增加，以提供更多的退避时间。这样的机制旨在降低冲突概率，并增加节点成功发送数据的机会。通过增大竞争窗口大小，节点可以有更多的时间来回避其他节点的活动，从而降低冲突的可能性。

在数据包传输过程中，节点经历发送、接收和处理3个阶段。因此，一次传输过程中的能量消耗可以表示为 ( P_{\mathrm{t}} + P_{\mathrm{r}} + P_{\mathrm{h}} ) \times T，其中， P_{\mathrm{t}} 为节点的数据包发射功率； P_{\mathrm{r}}为节点的数据包接收功率； P_{\mathrm{h}}为节点的数据包处理功率； T为时间，即数据包大小与传输速率的比值。如果节点的初始能量为 E，则一次传输过程后节点的剩余能量 E_{\mathrm{r}} = E - ( P_{\mathrm{t}} + P_{\mathrm{r}} + P_{\mathrm{h}} ) \times T。因此，为了确保节点能够进行一次完整的数据包交互，节点的最小剩余能量 E_{{\mathrm{r}}_{\mathrm{m}\mathrm{i}\mathrm{n}}}需要满足 E_{{\mathrm{r}}_{\mathrm{m}\mathrm{i}\mathrm{n}}} \ge ( P_{\mathrm{t}} + P_{\mathrm{r}} + P_{\mathrm{h}} ) \times T。

在关键节点选择过程中，如果能量较低的节点被选为关键节点，可能会导致后续通信过程中链路中断的情况。例如，在节点A广播消息时，节点B和节点C的消息发送顺序直接影响最终的关键节点选择结果。节点B因能量耗尽退出集群，如图2所示。假设节点B是能量较少的节点且优先发送消息，则当节点D回复消息给节点B时，节点B将被选为关键节点。然而，由于其能量不足，链路的稳定性无法得到保证。若节点B因能量耗尽而离开集群，则节点D将无法接收来自其他节点的消息。

针对以上情况，本文对CSMA中的退避规则进行了改进，考虑了节点的剩余能量因素，修改了回退窗口大小的函数，以使剩余能量较多的节点更有可能成为关键节点。具体而言，用函数来调整回退窗口大小，如式（1）所示。

C W^{\mathrm{*}} = \mathrm{s} \mathrm{l} \mathrm{o} \mathrm{t} \times \gamma \times {\mathrm{2}}^{\mathrm{m}\mathrm{i}\mathrm{n}(\frac{E}{E_{\mathrm{r}}},\beta )} （1）

式中： \mathrm{s} \mathrm{l} \mathrm{o} \mathrm{t}为单位时隙； \mathrm{\gamma } 为稀疏系数，目的是避免节点剩余能量过小时在一定范围内发生频繁碰撞； E为节点初始能量； E_{\mathrm{r}} 为节点当前剩余能量； \beta为严格上界参数，目的是将回退窗口大小控制在一定范围内。由于所有无人机具有相同的初始能量，因此具有更多剩余能量的节点将获得较小的竞争窗口，进而能够更快地获得信道的回复消息并成为关键节点，从而维护集群的稳定性。

1.3 连接支配集优化策略

算法1 ECHO-OPT关键节点的选择与优化

1： procedure WHENPACKETRECEIVED（pkt）

2：  if pkt.flood-indicator is FF then

3：   if pkt.seq-num has not been received earlier then

4：   pkt.previous-sender pkt.sender

5：   pkt.sender <-C

6：   select backofftimer

7：   transmit pkt

8：   set echo timer

9：   else if pkt.previous-sender equals C

10：  mark CRITICAL

11：  discard pkt

12：  clear echo timer

13：   end if

14：  else if pkt.flood-indicator is PF then

15：   if Node.symbol is CRITICAL then

16：   if pkt.sender.NeighborCoverdNode.Neighbor

then Node.symbol ==NORMAL

transmit pkt

17：   else if Node.Neighbor.num==1 and

18：    Node.Neighbor.Symbol==CRITICAL

then Node.Symbol=NORMAL

19：    transmit pkt

20：   end if

21：   end if

22：  else discard pkt

23：  end if

24： end procedure

边缘关键节点：图3为边缘节点被选作关键节点。节点B作为源节点首先进行消息广播。节点C接收到该消息并解析后，将报文中的“previous‑sender”字段设置为节点B的NodeID，并转发消息。节点B收到消息后，分析出报文中的“previous‑sender”字段与自身的NodeID相同，因此将自己标记为“CRITICAL”。类似的，节点A接收到来自节点C的广播消息后，将报文中的“previous‑sender”字段设置为节点C的NodeID，并转发该消息。节点C再次接收到该消息后，标记自身为“CRITICAL”。由此可知，当前网络中同时存在关键节点C和B。现假设节点C收到了一个无法传递给节点B的数据包，并尝试将其转发给节点B。即使节点C意识到这是一条重复消息，仍然将数据包传递给节点B，增加了额外的通信负载。

邻居重复覆盖：在假设的场景中，假设源节点为节点A，在节点A广播消息时，节点B、C和D都能接收到该数据包。每个节点在处理数据包时，将“previous-sender”字段更改为节点A的NodeID，并启动随机回退窗口用以竞争信道。根据两个假设条件：

1） ECHO-timer未超时。

2） 节点D首先占用了信道并转发了消息。

当节点A接收到这个数据包时，它解析出报文中“previous-sender”字段的值与自身的NodeID相同，因此将自身标记为“CRITICAL”。基于图4中节点的分布，可以推断节点B、C和D是关键节点。然而，从图2中还可以观察到节点C覆盖了节点D的单跳邻居。在OF阶段，节点C和节点D会重复发送消息，增加了额外的通信负载。

2 通信复杂度计算

本文对Flooding、MPR、ECHO和ECHO-OPT的通信复杂度进行了分析。其中MPR是一种用于无线传感器网络中的拓扑控制协议，协议的工作流程如下：节点定期发送Hello数据包，其中包含邻居列表和链接状态信息。当节点接收到Hello数据包时，它会将发送方添加到自己的邻居列表中，并使用Hello数据包中的邻居列表来更新自己的两跳邻居信息。节点记录发送Hello数据包的节点作为MPR节点。通过应用RFC 3626^［12］的启发式算法，选择具有最佳覆盖范围和网络连通性的MPR节点。选定的MPR节点负责转发其他节点的数据包，以构建整个网络的路由路径，从而实现全局的路由路径。这种方式使得数据包能够通过一系列的MPR节点传递到目标节点，实现节点之间的有效通信。

设CX为每秒通过网络传输的字节总数，N为节点数量，L为有效载荷大小（以字节为单位）。 l_{\mathrm{1}} 、 l_{\mathrm{2}} 、 l_{\mathrm{3}}和 l_{\mathrm{4}}分别为Flooding、MPR、ECHO和ECHO-OPT报头的大小。假设每个节点以每秒R _Gen个数据包的速率周期性地生成广播流量。

在泛洪算法中，每个节点生成的字节数为 R_{\mathrm{G}\mathrm{e}\mathrm{n}} ( L + l_{\mathrm{1}} )，则对于N个节点的集群，泛洪的通信复杂度为

C X_{\mathrm{F}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}} = R_{\mathrm{G}\mathrm{e}\mathrm{n}} N^{\mathrm{2}} ( L + l_{\mathrm{1}} ) （2）

从前文得知，MPR中需要考虑其Hello数据包的产生速率，若Hello数据包的产生速率为 R_{\mathrm{H}\mathrm{e}\mathrm{l}\mathrm{l}\mathrm{o}}，则MPR的通信复杂度为

C X_{\mathrm{M}\mathrm{P}\mathrm{R}} = R_{\mathrm{H}\mathrm{e}\mathrm{l}\mathrm{l}\mathrm{o}} N N_{\mathrm{N}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}} + R_{\mathrm{G}\mathrm{e}\mathrm{n}} N ( N_{\mathrm{M}\mathrm{P}\mathrm{R}} + \mathrm{1} ) ( L + l_{\mathrm{2}} ) （3）

式中： N_{\mathrm{N}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}}为平均一跳邻居数量； N_{\mathrm{M}\mathrm{P}\mathrm{R}}为MPR中继节点数量。

在ECHO中，消息发送分为两个阶段即FF与OF，若 R {}_{\mathrm{F}\mathrm{F}}{}^{}为FF阶段数据包的产生速率，且 R_{\mathrm{G}\mathrm{e}\mathrm{n}} > R_{\mathrm{F}\mathrm{F}}，则ECHO通信复杂度为

C X_{\mathrm{E}\mathrm{C}\mathrm{H}\mathrm{O}} = R_{\mathrm{f}\mathrm{f}} N ( L + l_{\mathrm{3}} ) + R_{\mathrm{G}\mathrm{e}\mathrm{n}} N ( N_{\mathrm{C}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{I}\mathrm{C}\mathrm{A}\mathrm{L}} + \mathrm{1} ) ( L + l_{\mathrm{3}} ) （4）

式中： N_{\mathrm{C}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{I}\mathrm{C}\mathrm{A}\mathrm{L}}为网络中关键节点的数量。

ECHO-OPT的FF阶段与ECHO相同，但是在OF阶段对于冗余节点进行了优化裁剪，则ECHO-OPT的通信复杂度为

\begin{array}{l}C{X}_{\mathrm{E}\mathrm{C}\mathrm{H}\mathrm{O}-\mathrm{O}\mathrm{P}\mathrm{T}}=R_{\mathrm{F}\mathrm{F}}N(L+l_{\mathrm{4}})+R\mathrm{F}\mathrm{F}N(N_{\mathrm{C}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{I}\mathrm{C}\mathrm{A}\mathrm{L}}+\mathrm{1})·\\ (L+l_{\mathrm{4}})+(R_{\mathrm{G}\mathrm{e}\mathrm{n}}-{\mathrm{R}}_{\mathrm{F}\mathrm{F}})N(N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}}+\mathrm{1})(L+l_{\mathrm{4}})\end{array} （5）

式中： N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}}为优化后的关键节点数量，且 R_{\mathrm{G}\mathrm{e}\mathrm{n}} > R_{\mathrm{F}\mathrm{F}}， N_{\mathrm{C}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{I}\mathrm{C}\mathrm{A}\mathrm{L}} > N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}}。

随后对泛洪算法、MPR、ECHO和ECHO-OPT的通信复杂度增益进行了分析，如式（6）所示。

\frac{C{X}_{\mathrm{F}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}}}{C{X}_{\mathrm{E}\mathrm{C}\mathrm{H}\mathrm{O}-\mathrm{O}\mathrm{P}\mathrm{T}}} = \frac{L+l_{\mathrm{1}}}{L+l_{\mathrm{4}}} \left[\frac{R_{\mathrm{G}\mathrm{e}\mathrm{n}}N}{R_{\mathrm{F}\mathrm{F}}(N_{\mathrm{C}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{I}\mathrm{C}\mathrm{A}\mathrm{L}}+\mathrm{2})+(R_{\mathrm{G}\mathrm{e}\mathrm{n}}-R_{\mathrm{F}\mathrm{F}})(N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}}+\mathrm{1})}\right] （6）

式中： ，则通信复杂度增益与 N_{\mathrm{C}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{I}\mathrm{C}\mathrm{A}\mathrm{L}}和 N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}}呈负相关 。

\frac{C{X}_{\mathrm{M}\mathrm{P}\mathrm{R}}}{C{X}_{\mathrm{E}\mathrm{C}\mathrm{H}\mathrm{O}-\mathrm{O}\mathrm{P}\mathrm{T}}} =

\frac{L+l_{\mathrm{2}}}{L+l_{\mathrm{4}}} \left[\frac{R_{\mathrm{H}\mathrm{e}\mathrm{l}\mathrm{l}\mathrm{o}}{N}_{\mathrm{N}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}}/(L+l_{\mathrm{2}})+R_{\mathrm{G}\mathrm{e}\mathrm{n}}(N_{\mathrm{M}\mathrm{P}\mathrm{R}}+\mathrm{1})}{R_{\mathrm{f}\mathrm{f}}(N_{\mathrm{C}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{I}\mathrm{C}\mathrm{A}\mathrm{L}}+\mathrm{2})+(R_{\mathrm{G}\mathrm{e}\mathrm{n}}-R_{\mathrm{F}\mathrm{F}})(N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}}+\mathrm{1})}\right] （7）

式中： R_{\mathrm{H}\mathrm{e}\mathrm{l}\mathrm{l}\mathrm{o}}为报文发送时间间隔； N_{\mathrm{N}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}}为节点的单跳邻居。可以看出，通信复杂度增益与 R_{\mathrm{H}\mathrm{e}\mathrm{l}\mathrm{l}\mathrm{o}}和 N_{\mathrm{N}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}}呈正相关。

\frac{C{X}_{\mathrm{E}\mathrm{C}\mathrm{H}\mathrm{O}}}{C{X}_{\mathrm{E}\mathrm{C}\mathrm{H}\mathrm{O}-\mathrm{O}\mathrm{P}\mathrm{T}}} =

\frac{L+l_{\mathrm{3}}}{L+l_{\mathrm{4}}} \left[\frac{R_{\mathrm{F}\mathrm{F}}/R_{\mathrm{G}\mathrm{e}\mathrm{n}}+N_{\mathrm{C}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{I}\mathrm{C}\mathrm{A}\mathrm{L}}+\mathrm{1}}{(N_{\mathrm{C}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{I}\mathrm{C}\mathrm{A}\mathrm{L}}-N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}}+\mathrm{1})R_{\mathrm{F}\mathrm{F}}/R_{\mathrm{G}\mathrm{e}\mathrm{n}}+N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}}+\mathrm{1}}\right] （8）

因为 且 ，所以 。由此可见，通信复杂度增益与 N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}}和 N_{\mathrm{C}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{I}\mathrm{C}\mathrm{A}\mathrm{L}}的差值呈负相关。当节点数较少或者节点密度较小时， N_{\mathrm{C}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{I}\mathrm{C}\mathrm{A}\mathrm{L}} = N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}}，则ECHO与ECHO-OPT的通信复杂度相等。

由于式中 R_{\mathrm{F}\mathrm{F}}、 R_{\mathrm{G}\mathrm{e}\mathrm{n}}、 L、 l_i均为常数项，则式（5）简化为

\begin{array}{l}C{X}_{\mathrm{E}\mathrm{C}\mathrm{H}\mathrm{O}-\mathrm{O}\mathrm{P}\mathrm{T}}=(L+l_{\mathrm{4}})N[R_{\mathrm{F}\mathrm{F}}(N_{\mathrm{C}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{I}\mathrm{C}\mathrm{A}\mathrm{L}}{N}_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}}+\mathrm{1})+\\ R_{\mathrm{G}\mathrm{e}\mathrm{n}}(N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}}+\mathrm{1})]\end{array} （9）

式中： N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}} > N_{\mathrm{C}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{I}\mathrm{C}\mathrm{A}\mathrm{L}} - N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}}，则ECHO-OPT的渐近复杂度为 O ( N N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}} )。以上4种协议的渐进通信复杂度如表1所示。

3 算法仿真结果及分析

本文对Flooding、MPR、ECHO和ECHO-OPT进行了性能比较。所有的节点被随机分布在一个3 km×3 km的区域内。在节点初始化阶段，每个节点确保至少有一个其他节点位于其通信范围内。仿真参数如表2所示，其中MPR节点的Hello时间间隔与ECHO和ECHO-OPT的FF时间间隔保持一致。实验中每0.5 s随机选取节点生成一个数据包，总共生成500个数据包。每个实验都使用不同的随机种子数，并重复5次以消除偶然性的影响。实验比较了以下指标：1）通信负载（communication load，CL），即单位时间内网络中的总字节数；2）端到端时延（end-to-end delay，E2E），即从源节点到目的节点的传输时间；3）连通支配集（connection dominance set，CDS），即关键节点的数量。

首先，针对不同传输范围对关键节点数量即连通支配集大小的影响进行了测试，通信距离变化对CDS大小的影响如图5所示。实验结果显示，随着通信范围的增加，冗余节点逐渐减少，并最终趋向于零。另外，对不同传输范围下的数据包传输率进行了比较，通信距离变化对包传输比的影响如图6所示。

在传输范围较小的情况下，数据包的传输比相对较低。这说明在稀疏网络中，由于节点的移动导致链路中断频繁，从而导致包传输比下降。为了更好地验证ECHO-OPT协议的网络性能，在实验中需要同时考虑冗余节点数和包传输比，并确保包传输比高于95%。综合考虑以上因素，实验中的通信距离设置为700 m。

3.1 连通支配集大小

图7a为相同网络密度下CDS的大小随节点数量的变化，展示了节点数量从20到120时，ECHO和ECHO-OPT算法的CDS大小的变化情况。在实验中，为了消除偶然性，对结果进行了多次验证，因此可能存在小数值，但这并不影响对最终网络性能的评估。对于前文提出的边缘节点，在FF阶段只有在源节点发送报文时才会选择它们作为源节点，所以在节点数量较少的情况下，边缘节点被选为源节点的概率较低。同时，由于节点数量较少，每个节点的邻居数量与节点数成正比，这种情况下ECHO-OPT算法的优化效果不太明显。然而，随着节点数量的增加，冗余节点出现的概率逐渐升高。在OF阶段，ECHO-OPT算法会对关键节点进行冗余修剪，从而导致CDS大小相对于ECHO算法有所减小。根据实验数据，当节点数量从60增加到120时，关键节点的数量平均减少了约2.26个，这些被优化修剪的关键节点几乎都是重复的邻居节点。

随后根据实验设计，在固定的区域内调整节点数量以测试ECHO-OPT和ECHO在不同网络密度下连通支配集的变化情况。图7b为不同网络密度下CDS大小随节点数量的变化，实验结果表明，随着网络密度的增加，ECHO-OPT比ECHO表现出更好的优化效果。这是因为随着网络密度的增加，冗余节点的数量也随之增加，与CDS大小之间的差异逐渐扩大。因此，在OF阶段，ECHO-OPT能够更好地削减冗余节点并进行优化。实验数据显示，在高密度网络中，ECHO-OPT能够平均优化4.67个CDS。

3.2 网络负载

图8a显示了在相同网络密度下，节点数量为20~120时的通信负载情况。当节点数量较少时，ECHO-OPT的可优化关键节点数量几乎为零，因此 N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}}接近 N_{\mathrm{C}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{I}\mathrm{C}\mathrm{A}\mathrm{L}}，从而导致ECHO与ECHO-OPT的通信复杂度相等。然而，随着节点数量的增加，关键节点集中的冗余节点逐渐增多，使得 N_{\mathrm{T}\mathrm{r}\mathrm{i}\mathrm{m}}小于 N_{\mathrm{C}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{I}\mathrm{C}\mathrm{A}\mathrm{L}}，进而使得ECHO-OPT协议的通信复杂度小于ECHO协议的通信复杂度。在4种协议中，由于每个节点都参与数据转发，传统的泛洪协议一直具有最高的通信负载。尽管MPR通过选择一定策略的中继节点来减少负载，但由于每个MPR节点都参与报文转发，并且MPR节点的数量远远大于关键节点的数量，因此其负载相对于ECHO和ECHO-OPT仍然较高。实验数据表明，节点数量的变化对于ECHO和ECHO-OPT的相对差值影响不大。这是因为在相同的节点数量下，冗余节点的数量始终保持在较低水平。

如图8b所示，在不同网络密度下，4种协议的网络负载情况呈现出明显差异。在动态网络密度下，ECHO-OPT比ECHO表现出更好的优化效果。这是因为在动态网络密度下，随着网络密度的变化，冗余节点的数量也会发生变化。而ECHO-OPT在OF阶段能够更好地发挥其优化能力，从而实现较低的网络负载。然而，Flooding协议在高网络密度下无法有效处理网络风暴问题，导致网络负载急剧上升。尽管在MPR中选择了一些MPR中继节点来转发消息，但在高网络密度下，节点的一跳邻居数量较多，导致较高的网络负载。值得注意的是，在高网络密度下，相比ECHO，ECHO-OPT通过优化转发阶段的优化剪裁成功地减少约32%的网络负载。与Flooding和MPR协议相比，其优化效果分别达到约76.27%和65.00%。实验结果显示，ECHO-OPT在动态和高密度网络环境中具有较好的性能表现，能够有效降低网络负载并优化网络传输效率。

3.3 端到端延迟

节点数量对端到端延迟的影响如图9所示，传统的Flooding和MPR协议在高网络负载下有严重的消息排队现象，从而导致相对较高的延迟。然而，ECHO-OPT协议通过使用较少的关键节点减少跳数，并且低网络负载也带来了较低的延迟。实验结果显示，与Flooding和MPR协议相比，ECHO-OPT协议的延迟分别降低了15.74%和17.26%。此外，相对于ECHO协议，ECHO-OPT协议的延迟降低了11.82%。这些结果进一步证明了ECHO-OPT协议在降低延迟方面的有效性。

3.4 节点能耗

首先对数据传输过程中的节点能量消耗进行了量化，其中接收数据包消耗0.01能量，处理数据包消耗0.01能量，发送数据包消耗0.02能量。为了测试每个协议在能量耗尽时所能产生的源数据包数量，所有节点的初始能量被设置为1，并且节点数量调整为100。图10为相同能耗下包转发数量，实验结果表明，在相同初始能量条件下，ECHO-OPT相对于其他协议能够实现更多的数据包传输次数。这得益于ECHO-OPT在节点转发过程中对剩余能量情况的综合考虑。相比之下，泛洪和MPR参与转发的节点数量远大于ECHO和ECHO-OPT，导致它们能够转发的数据包数量较少。由于其优化机制，ECHO-OPT在能耗方面相比ECHO提升了30%。

4 结论

本文提出了一种无人机多跳自组织网络骨干网集选择优化方案ECHO-OPT。在ECHO协议的基础上，增加了关键节点的优化机制，修剪了主干集中的冗余节点，缩短了主干集的大小，降低了网络负载与延迟。与此同时，在关键节点决策过程中充分考虑了节点能量情况，提高了网络寿命。实验表明，ECHO-OPT相比ECHO在高密度网络下平均优化了4.67个关键节点集大小，在网络负载方面，ECHO-OPT相比ECHO降低了32%的网络负载，对比Flooding与MPR优化效果分别达到了76.27%和65.00%。与此同时，ECHO-OPT相对于ECHO在能耗方面提升了大约30%。

下一步的工作将更深层次地研究关键节点失效的原因，从多方面因素入手，形成关键节点的备份机制，增强链路稳定性。

参考文献

[1] Zhao N， Lu W D， Sheng M，et al.UAV-assisted emergency networks in disasters［J］.IEEE Wireless Communications，2019，26（1）：45-51.

[2] Erdos D， Erdos A， Watkins S E.An experimental UAV system for search and rescue challenge［J］.IEEE Aerospace and Electronic Systems Magazine，2013，28（5）：32-37.

[3] Pitre R R， Li X R， Delbalzo R.UAV route planning for joint search and track missions：an information-value approach［J］.IEEE Transactions on Aerospace and Electronic Systems，2012，48（3）：2551-2565.

[4] Yan S， Peng M G， Cao X Y.A game theory approach for joint access selection and resource allocation in UAV assisted IoT communication networks［J］.IEEE Internet of Things Journal，2019，6（2）：1663-1674.

[5] Huang M F， Liu A F， Xiong N N，et al.A UAV-assisted ubiquitous trust communication system in 5G and beyond networks［J］.IEEE Journal on Selected Areas in Communications，2021，39（11）：3444-3458.

[6] Mozaffari M， Saad W， Bennis M，et al.A tutorial on UAVs for wireless networks：applications，challenges，and open problems［J］.IEEE Communications Surveys & Tutorials，2019，21（3）：2334-2360.

[7] Karimi-Bidhendi S， Guo J， Jafarkhani H.Energy-efficient deployment in static and mobile heterogeneous multi-hop wireless sensor networks［J］.IEEE Transactions on Wireless Communications，2022，21（7）：4973-4988.

[8] Sinha A， Modiano E.Throughput-optimal broadcast in wireless networks with point-to-multipoint transmissions［J］.IEEE Transactions on Mobile Computing，2021，20（1）：232-246.

[9] Obraczka K， Viswanath K， Tsudik G.Flooding for reliable multicast in multi-hop ad hoc networks［J］.Wireless Networks，2001，7（6）：627-634.

[10] Perkins C， Belding R E， Das S.2003.Ad hoc on-demand distance vector （AODV） routing［EB/OL］.（2023-07-10）［2020-07-09］.

[11] Johnson D B， Maltz D A， Broch J.DSR：the dynamic source routing protocol for multi-hop wireless Ad Hoc networks［EB/OL］.（2022-12-15）［2024-01-09］.multi-hop%20wireless%20ad%20hoc%20networks%20of%20mobile%20nodes.

[12] Clausen T， Jacquet P.Optimized link state routing protocol［EB/OL］.（2003-10-23）［2021-09-12］.

[13] Akbari T J.A stable virtual backbone for wireless MANETS［J］.Telecommunication Systems，2014，55（1）：137-148.

[14] Toorchi N， Hu F， Bentley E S，et al.Skeleton-based swarm routing （SSR）：intelligent smooth routing for dynamic UAV networks［J］.IEEE Access，2020，9（99）：1286-1303.

[15] Young C D， Amis A D.UCDS：unifying connected dominating set with low message complexity，fault tolerance，and flexible dominating factor［C］//2011-MILCOM 2011 Military Communications Conference.Baltimore：IEEE，2011：1357-1362.

[16] Liang X Y， Liang J R， Zhang W G.Constructing drobust connected dominating sets in wireless sensor networks with unstable transmission ranges［J］.IEEE Transactions on Communications，2021，69（1）：398-415.

[17] Farooq M U， Zeeshan M.Connected dominating set enabled on-demand routing （CDS-OR） for wireless mesh networks［J］.IEEE Wireless Communications Letters，2021，10（11）：2393-2397.

[18] Dusia A， Ramanathan R， Ramanathan W，et al.ECHO：efficient zero-control-packet broadcasting for mobile ad hoc networks［J］.IEEE Transactions on Mobile Computing，2022，21（9）：3163-3175.

[19] Tong J W， Fu L Q， Han Z.Throughput enhancement of full-duplex CSMA networks using multiplayer bandits［J］.IEEE Internet of Things Journal，2021，8（15）：11807-11821.

[20] Huang X Q， Liu A J， Zhou H B，et al.FMAC：a self-adaptive MAC protocol for flocking of flying ad hoc network［J］.IEEE Internet of Things Journal，2021，8（1）：610-625.

基金资助

国家自然科学基金(62376165)