蜂群无人机自组网多优先级自适应退避算法

刘炜伦， 张衡阳， 郑博， 高维廷

(空军工程大学 信息与导航学院， 西安 710077)

无人机蜂群作战的概念是美军于20世纪90年代末率先提出的。无人机蜂群由若干配备多种任务载荷的低成本小型无人机组成，相比有人战机，其个体分散性较强，作战时无人机蜂群可进行专业化分工，每架无人机的功能不尽相同，因而可以执行多种任务。由于无人机蜂群作战技术对协同和自主的要求极高，并且需要建立全新的大规模蜂群指挥控制模式，因此需要解决协同作战算法、集群个体间通信、远程指挥控制等关键技术[1-2]。蜂群无人机自组网，也称飞行自组网(Flying Ad hoc Networks，FANETs)[3-5]，是无人机蜂群协同作战的基础和前提，性能将直接决定协同作战目标能否实现。它的基本思想是：多无人机间的通信不完全依赖于地面控制站或卫星等基础通信设施，而是将无人机作为网络节点，各节点能够相互转发控制指令，交换态势感知、情报搜集等数据，并自动建立一个Ad hoc网络。FANETs采用动态组网、无线中继等技术实现无人机间的互连互通，具备自组织、自修复能力和高效、快速组网优势，可使无人机蜂群形成一个整体去执行作战任务。

FANETs存在大尺度稀疏分布、多业务并存、信道质量不稳定等问题。随着网络负载的增大，易使信道中产生大量拥塞和冲突，导致网络性能的下降，将无法保障控制指令等高优先级业务低时延、高可靠的服务质量(Quality of Service, QoS)需求[6]。针对上述问题，退避算法作为FANETs媒质接入控制(MAC)协议的重要组成部分，其设计的关键在于有效降低信道中的大量冲突，同时兼顾各优先级业务的不同QoS需求，保证信息传输的时效性、可靠性。因此，针对FANETs设计一种高效、合理的退避算法是有效提升网络性能的关键。

目前移动Ad hoc网络广泛采用的是二进制指数退避(Binary Exponential Backoff, BEB)算法[7-9]。研究表明，该类算法存在无法根据网络负载情况快速选取最佳竞争窗口、在饱和状态时网络性能急剧下降且不能区分服务类别等不足。近年来，许多研究者针对BEB算法的不足，根据网络实际需求提出并设计了多种退避算法。例如，文献[10]提出一种增强型退避(Enhanced Backoff, EBO) 算法，能够有效降低重负载下网络中的冲突，并提高短期公平性，但无法区分优先级，且不能根据负载情况将竞争窗口收敛到最佳状态；文献[11]提出一种支持QoS的自适应竞争窗口退避算法(Adaptive Contention Window Backoff Algorithm for QoS, Q-ABACW)，根据分组碰撞概率估计网络中的不同业务的活跃节点数量并动态调整各优先级竞争窗口，实现了多业务区分，但对于大尺度稀疏分布的FANETs，活跃节点数量难以准确估计；文献[12]提出一种区分业务优先级的自适应退避 (Priority Adaptive Backoff, PAB) 算法，通过实时调整节点相邻退避阶段的前后转移概率，为多种优先级业务提供区分服务，但其通过载波侦听判定信道忙闲从而决定节点下一阶段退避状态的方法并不准确，无法实际应用于FANETs。

针对文献[10-12]存在的不足并结合FANETs特点，本文提出并设计了一种基于负载反馈和竞争窗口实时更新的多优先级自适应退避算法(Multiple Priority Adaptive Backoff Algorithm,MPABA)。本文算法采用忙闲因子自适应机制和最优竞争窗自适应机制，通过信道忙闲程度自适应调整各优先级的忙闲自适应因子，并依据网络状态信息自适应调整最优竞争窗自适应因子，从而实时动态更新各优先级竞争窗口长度并使其快速收敛到最佳状态，实现了多优先级业务区分服务、改善了网络在重负载下的性能且能有效保障高优先级业务低时延、高可靠的QoS需求。

1 算法描述

由于FANETs中各优先级业务具有不同的QoS需求，MPABA可通过忙闲因子自适应机制和最优竞争窗自适应机制，实现对不同优先级业务的区分服务和最优的系统吞吐量性能。该算法的基本原理如图1所示，首先对上层产生的业务分组进行纠错编码[13]，然后分别插入各自的优先级队列等待发送。到达队首的分组接入信道前需要进行信道忙闲判定，若信道忙闲程度小于其对应的接入门限，分组立即接入信道，反之执行退避机制，并根据忙闲因子自适应机制和最优竞争窗自适应机制实时更新竞争窗口长度并使其快速收敛到最佳状态。其中，最高优先级(优先级1)业务具有严格的时效性与可靠性需求，不对其进行接入控制。

该算法主要包含以下2大核心机制：

1) 忙闲因子自适应机制。用节点接收机在一段时间内收集到的负载数目量对下一时刻的负载数目接收值实时预测，并根据预测值量化信道忙闲程度[14]，然后将结果反馈给接入判定模块，根据信道忙闲程度确定各优先级业务不同的忙闲自适应因子从而实现多业务区分服务。

2) 最优竞争窗自适应机制。为了获得饱和状态下的最优接入参数，假设各优先级业务存在同一最优竞争窗自适应因子βCWI，算法能根据网络状态信息(信道负载、节点数量及信道数目等)自适应调整βCWI，以适应动态网络变化，从而获得更好的网络性能(系统吞吐量最优)。

图1 MPABA原理Fig.1 Principle of MPABA

(1)

令i表示优先级r分组在第j次退避阶段时根据信道忙闲程度所确定的忙闲自适应因子i∈[1,lr]，其值由式(2)确定，即

(2)

式中：⎣」表示向下取整。

将i作为竞争窗口调整参数，构造优先级r分组在第j个退避阶段的竞争窗口表达式为

(3)

2 MPABA性能分析

2.1 退避过程三维Markov链模型

令pr表示优先级r的分组到达缓冲区队首时经信道忙闲判定后不能接入的概率，m表示最大退避次数。令gr(t)表示优先级r的分组在t时刻的忙闲自适应因子，sr(t)表示优先级r的分组在t时刻所处的退避阶段，br(t)表示优先级r的分组在t时刻退避计数器的值，则三维随机过程(gr(t),sr(t),br(t))构成如图2所示的离散三维Markov链，其各状态稳态概率为

(4)

引入状态(0,-1,0)表示发送缓冲区队首恰好为空的概率(即前一分组服务完成时，后一分组还未进入队首的瞬时状态)，由图2可得，节点退避状态的一步转移概率可表示为

(5)

图2 优先级r分组退避状态的三维Markov链模型Fig.2 Three-dimensional Markov chain model of backoff stage for priority r traffic

Pr{i,j,k|i,j,k+1}=1

(6)

(7)

Pr{0,-1,0|i,j,0}=1-pr

i∈[1,lr];j∈[0,m)

(8)

Pr{0,-1,0|i,m,0}=1i∈[1,lr]

(9)

式中：qr为单个节点有优先级r分组进入相应队列的概率。

式(5)表示发送缓冲区队首分组经信道忙闲判定后首次执行退避的概率；式(6)表示状态转移图中同一行向左转移的概率；式(7)表示状态转移图中分组经信道忙闲判定后无法接入信道并根据式(2)重新确定忙闲自适应因子并进入下一退避阶段的概率；式(8)表示分组经信道忙闲判定后允许接入信道并回到初始状态的概率；式(9)表示分组经m次退避后仍不能接入信道，节点将分组丢弃并回到初始状态的概率。

又由图2可得

(10)

结合式(10)及图2推导可得

(11)

令λr表示单个节点中优先级r的分组到达率，σ表示单位时隙长度，则在σ内，单个节点有优先级r分组进入相应队列的概率qr为

qr=1-e-λrσ

(12)

根据三维Markov链的归一化条件，一个节点所有状态概率应满足

(13)

根据式(10)～式(13)可求解图2中每个状态的取值。

定义τr表示优先级r分组经退避和信道忙闲判定后允许接入的概率，即

(14)

由于采用优先抢占式的信道接入策略，节点发送端服务器每次仅能服务一个分组，因此可得分组在任一时隙σ能接入信道的概率为

(15)

则单个节点的分组接入速率λin为

(16)

2.2 各优先级接入门限求解

由于接入网络的分组会在时域、频域发生碰撞。因此，分组成功接收需保证在同一条信道上，当前分组与其前后一个分组的发送间隔时间同时大于其信道传输时延Tsend。对于单个信道，假设接入网络中的分组在间隔时间上服从参数为λper=Nλin/M(N为节点数量，M为信道数量)的负指数分布[15]。定义Pb表示分组成功接收概率，则

(17)

令Nb为分组拆分后的突发包个数，Mb为恢复原分组所需最少突发个数。根据纠错编码机制原理，可得分组成功传输概率ppac为

(18)

假设最高优先级业务所要求的最低传输成功概率为99%，则令ppac=99%，联立式(17)～式(18)可得当前网络所对应的信道负载为Gmax。

(19)

(20)

2.3 系统吞吐量

定义S表示系统吞吐量，表示单位时间内信道实际传输成功的所有优先级分组比特数之和，即

S=λinNLpacPb

(21)

式中：Lpac为数据分组的比特长度。

2.4 平均MAC时延

令E[Dr]表示优先级r分组的平均MAC时延，即分组到其相应优先级队首至该分组接入信道前所需时间的平均值，表示为

E[Dr]=E[Tr]σ

(22)

式中：E[Tr]为优先级r的分组成功传输所需的平均时隙数，可表示为

(23)

2.5 最优竞争窗自适应因子求解

为提高接入方案的吞吐量性能，通过式(21)求解可使S达到最优的λin，并通过λin求解最优竞争窗自适应因子βCWI的值，从而通过自适应调整βCWI，使S达到最优。

式(21)可表示为

(24)

通过求吞吐量S关于λin的偏导数，令∂S/∂λin=0，易知式(24)存在唯一极大值点可使S达到最大。解得该极大值为

(25)

联立式(16)和式(25)，可得

(26)

整理式(26)可得

(27)

式中：

(28)

将式(28)进行整理，并对其取以e为底的对数可得

(29)

(30)

(31)

由式(27)和式(31)可知，最优竞争窗自适应因子βCWI与信道负载(网络中所有节点分组接入速率之和)Gtra、信道数目M直接相关。在表1和表2的参数设置下，得到βCWI与信道负载、信道数目的关系图3。由图3可知，相同信道数目下的βCWI与信道负载呈正比关系；信道负载相同的情况下βCWI与信道数目呈反比关系。

定义信道负载Gtra表示网络中所有节点的分组接入网络的速率之和。

表1 仿真参数设置Table 1 Simulation parameter setting

表2 各业务类型相关参数Table 2 Related parameters of each priority type

图3 βCWI与Gtra及M的关系Fig.3 Relation of βCWI with Gtra and M

3 仿真分析

下面采用OMNeT++仿真平台对MPABA的性能进行仿真分析。仿真场景大小设置为200 km×200 km×10 km，所有节点在该场景中的随机分布，每个节点随机选择目的节点通信，MAC层采用多信道ALOHA协议。仿真结果取2 000次蒙特卡罗实验的平均值，具体参数设置见表1。

根据FANETs的实际应用需求，对MPABA设定4种优先级业务，其中优先级1为最高优先级，其分组到达率固定为60 packet/s，优先级2、3、4的分组到达率之比为1∶3∶6。在设定优先级1分组最低成功传输概率为99%的条件下，在表1的参数设置下解得Gmax=1 875 packet/s，其他相关参数如表2所示。

图4 信道负载对MPABA性能的影响Fig.4 Influence of channel loads on performance of MPABA

首先对MPABA性能的数学模型进行仿真验证。不同信道负载下的平均MAC时延和系统吞吐量的理论计算和仿真结果如图4所示。由图4(a)可以看出，当信道处于轻负载时，各优先级的平均MAC时延均相对较低，表明此时信道负载小于各优先级接入门限，各优先级业务均能保证良好的时延性能；在重负载时，优先级1业务MAC时延保持稳定且在2 ms以内，其余各优先级业务的时延均显著增大，表明此时开始执行退避算法，由于各优先级业务每次退避时的忙闲自适应因子不同，导致不同业务每次选取的竞争窗口长度不同，从而实现了区分服务。由图4(b)可以看出，在重负载时，MPABA能使吞吐量达到最大且稳定在最大值6.7 Mbit/s，表明MPABA可自适应调整βCWI，使吞吐量达到最优值。由图4可知，MPABA的理论计算结果和仿真实验数据基本吻合，表明理论计算结果准确有效。

下面将本文提出的MPABA与Q-ABACW[11]、PAB算法[12]的性能进行仿真实验对比，其中PAB算法、Q-ABACW均包含4种与表2相同的优先级业务类别，在相同仿真参数设置下得到仿真对比结果如图5所示。

由图5(a)、(b)可知，MPABA虽然对低优先级业务的时延保障能力较差，但能为高优先级业务提供严格的时效性保障。由图5(c)可知，相比MPAB、Q-ABACW，MPABA在重负载时能够使系统吞吐量保持最优且稳定，具有明显的性能优势，可为FANET提供较高的系统容量需求。

图5 MPABA、PAB算法与Q-ABACW性能对比Fig 5 Comparison of performance among MPABA, PAB algorithm and Q-ABACW

综合以上仿真结果，可以得到以下结论：

1) 当信道轻负载时，MPABA中各优先级业务均可获得较好的QoS性能。

2) 当信道重负载时，低优先级的分组需执行退避算法，根据信道忙闲程度确定各自的忙闲自适应因子并自适应调整竞争窗口大小，从而将冲突维持在可控范围内，为高优先级的分组提供严格的时效性需求。

3) MPABA可根据网络状况自适应调整βCWI，从而可使系统吞吐量达到最优。

4)对比PAB算法、Q-ABACW，MPABA能为高优先级业务提供更好的服务，并使得系统吞吐量达到最优。

4 结 论

本文为FANETs提出并设计了一种多优先级自适应退避算法，旨在实现多业务区分服务并有效改善网络在重负载下的性能。

1) 能根据信道忙闲程度和网络状态参数自适应调整各优先级竞争窗口长度，从而可将竞争窗口收敛到最佳状态，为不同优先级业务提供了不同的QoS保障能力，得到了最优的系统性能。

2) 仿真实验验证了所建模型准确有效，与Q-ABACW和PAB算法相比，算法在吞吐量性能上具有明显的优势。