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)业务具有严格的时效性与可靠性需求，不对其进行接入控制。
 |
| 图 1 MPABA原理 Fig. 1 Principle of MPABA |
| 图选项 |
该算法主要包含以下2大核心机制：
1) 忙闲因子自适应机制。用节点接收机在一段时间内收集到的负载数目量对下一时刻的负载数目接收值实时预测，并根据预测值量化信道忙闲程度[14]，然后将结果反馈给接入判定模块，根据信道忙闲程度确定各优先级业务不同的忙闲自适应因子从而实现多业务区分服务。
2) 最优竞争窗自适应机制。为了获得饱和状态下的最优接入参数，假设各优先级业务存在同一最优竞争窗自适应因子βCWI，算法能根据网络状态信息(信道负载、节点数量及信道数目等)自适应调整βCWI，以适应动态网络变化，从而获得更好的网络性能(系统吞吐量最优)。
定义αr表示优先级r∈{2, 3, …, R}业务的忙闲自适应因子，其大小受负载数目的预测值G与各优先级对应的接入门限Athr实时控制，可将αr量化表示为
 | (1) |
且设定αr的最大值为αrmax=lr。
令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) |
 |
| 图 2 优先级r分组退避状态的三维Markov链模型 Fig. 2 Three-dimensional Markov chain model of backoff stage for priority r traffic |
| 图选项 |
引入状态(0, -1, 0)表示发送缓冲区队首恰好为空的概率(即前一分组服务完成时，后一分组还未进入队首的瞬时状态)，由图 2可得，节点退避状态的一步转移概率可表示为
 | (5) |
 | (6) |
 | (7) |
 | (8) |
 | (9) |
式中：qr为单个节点有优先级r分组进入相应队列的概率。
式(5)表示发送缓冲区队首分组经信道忙闲判定后首次执行退避的概率；式(6)表示状态转移图中同一行向左转移的概率；式(7)表示状态转移图中分组经信道忙闲判定后无法接入信道并根据式(2)重新确定忙闲自适应因子并进入下一退避阶段的概率；式(8)表示分组经信道忙闲判定后允许接入信道并回到初始状态的概率；式(9)表示分组经m次退避后仍不能接入信道，节点将分组丢弃并回到初始状态的概率。
又由图 2可得
 | (10) |
结合式(10)及图 2推导可得
 | (11) |
令λr表示单个节点中优先级r的分组到达率，σ表示单位时隙长度，则在σ内，单个节点有优先级r分组进入相应队列的概率qr为
 | (12) |
根据三维Markov链的归一化条件，一个节点所有状态概率应满足
 | (13) |
联立式(5)~式(13)可求解b1, 0, 0r的表达式。
根据式(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。
为了保障最高优先级业务的时效性与可靠性需求，需对优先级r∈{2, 3, …, R}业务设置接入门限。设接入网络的优先级1, 2, …, R业务比例为k1:k2:…:kR。设优先级r业务的接入门限为Athr，其含义为其业务恰好无法接入信道时，网络中所对应的负载。Athr需满足
 | (19) |
通过式(19)可以求解所有Athr的值，即各优先级业务的接入门限值。
根据接入门限Athr可求解pr，即
 | (20) |
2.3 系统吞吐量 定义S表示系统吞吐量，表示单位时间内信道实际传输成功的所有优先级分组比特数之和，即
 | (21) |
式中：Lpac为数据分组的比特长度。
2.4 平均MAC时延 令E[Dr]表示优先级r分组的平均MAC时延，即分组到其相应优先级队首至该分组接入信道前所需时间的平均值，表示为
 | (22) |
式中：E[Tr]为优先级r的分组成功传输所需的平均时隙数，可表示为
 | (23) |
2.5 最优竞争窗自适应因子求解 为提高接入方案的吞吐量性能，通过式(21)求解可使S达到最优的λin，并通过λin求解最优竞争窗自适应因子βCWI的值，从而通过自适应调整βCWI，使S达到最优。
式(21)可表示为
 | (24) |
通过求吞吐量S关于λin的偏导数，令
 | (25) |
联立式(16)和式(25)，可得
 | (26) |
整理式(26)可得
 | (27) |
式中：
 | (28) |
将式(28)进行整理，并对其取以e为底的对数可得
 | (29) |
由于qr, pr∈(0, 1)，忽略prm和prm+1的影响，并近似认为(lr－1)lr－1≈1，可推导出
 | (30) |
因此有
 | (31) |
由式(27)和式(31)可知，最优竞争窗自适应因子βCWI与信道负载(网络中所有节点分组接入速率之和) Gtra、信道数目M直接相关。在表 1和表 2的参数设置下，得到βCWI与信道负载、信道数目的关系图 3。由图 3可知，相同信道数目下的βCWI与信道负载呈正比关系；信道负载相同的情况下βCWI与信道数目呈反比关系。
表 1 仿真参数设置 Table 1 Simulation parameter setting
| 参数 | 数值 |
| 节点数量 | 50 |
| 信道数量 | 10 |
| 信道传输速率/(Mbit·s-1) | 3 |
| 分组长度/bit | 1000 |
| 编码效率 | 1/3 |
| 单位时隙/μs | 100 |
| 各优先级最大退避次数 | 10 |
| 分组拆分突发数 | 28 |
| 分组成功接收所需最低突发数 | 14 |
表选项
表 2 各业务类型相关参数 Table 2 Related parameters of each priority type
| 优先级 | 信息种类 | lr | Athr/(packet·s-1) |
| 1 | 武器协同信息 | ||
| 2 | 态势感知信息 | 20 | 18750 |
| 3 | 网络管理信息 | 30 | 5745 |
| 4 | 天气、环境信息 | 40 | 1875 |
表选项
 |
| 图 3 βCWI与Gtra及M的关系 Fig. 3 Relation of βCWI with Gtra and M |
| 图选项 |
定义信道负载Gtra表示网络中所有节点的分组接入网络的速率之和。
3 仿真分析 下面采用OMNeT++仿真平台对MPABA的性能进行仿真分析。仿真场景大小设置为200km×200km×10km，所有节点在该场景中的随机分布，每个节点随机选择目的节点通信，MAC层采用多信道ALOHA协议。仿真结果取2000次蒙特卡罗实验的平均值，具体参数设置见表 1。
根据FANETs的实际应用需求，对MPABA设定4种优先级业务，其中优先级1为最高优先级，其分组到达率固定为60packet/s，优先级2、3、4的分组到达率之比为1:3:6。在设定优先级1分组最低成功传输概率为99%的条件下，在表 1的参数设置下解得Gmax=1875packet/s，其他相关参数如表 2所示。
首先对MPABA性能的数学模型进行仿真验证。不同信道负载下的平均MAC时延和系统吞吐量的理论计算和仿真结果如图 4所示。由图 4(a)可以看出，当信道处于轻负载时，各优先级的平均MAC时延均相对较低，表明此时信道负载小于各优先级接入门限，各优先级业务均能保证良好的时延性能；在重负载时，优先级1业务MAC时延保持稳定且在2ms以内，其余各优先级业务的时延均显著增大，表明此时开始执行退避算法，由于各优先级业务每次退避时的忙闲自适应因子不同，导致不同业务每次选取的竞争窗口长度不同，从而实现了区分服务。由图 4(b)可以看出，在重负载时，MPABA能使吞吐量达到最大且稳定在最大值6.7Mbit/s，表明MPABA可自适应调整βCWI，使吞吐量达到最优值。由图 4可知，MPABA的理论计算结果和仿真实验数据基本吻合，表明理论计算结果准确有效。
 |
| 图 4 信道负载对MPABA性能的影响 Fig. 4 Influence of channel loads on performance of MPABA |
| 图选项 |
下面将本文提出的MPABA与Q-ABACW[11]、PAB算法[12]的性能进行仿真实验对比，其中PAB算法、Q-ABACW均包含4种与表 2相同的优先级业务类别，在相同仿真参数设置下得到仿真对比结果如图 5所示。
 |
| 图 5 MPABA、PAB算法与Q-ABACW性能对比 Fig. 5 Comparison of performance among MPABA, PAB algorithm and Q-ABACW |
| 图选项 |
由图 5(a)、(b)可知，MPABA虽然对低优先级业务的时延保障能力较差，但能为高优先级业务提供严格的时效性保障。由图 5(c)可知，相比MPAB、Q-ABACW，MPABA在重负载时能够使系统吞吐量保持最优且稳定，具有明显的性能优势，可为FANET提供较高的系统容量需求。
综合以上仿真结果，可以得到以下结论：
1) 当信道轻负载时，MPABA中各优先级业务均可获得较好的QoS性能。
2) 当信道重负载时，低优先级的分组需执行退避算法，根据信道忙闲程度确定各自的忙闲自适应因子并自适应调整竞争窗口大小，从而将冲突维持在可控范围内，为高优先级的分组提供严格的时效性需求。
3) MPABA可根据网络状况自适应调整βCWI，从而可使系统吞吐量达到最优。
4) 对比PAB算法、Q-ABACW，MPABA能为高优先级业务提供更好的服务，并使得系统吞吐量达到最优。
4 结论 本文为FANETs提出并设计了一种多优先级自适应退避算法，旨在实现多业务区分服务并有效改善网络在重负载下的性能。
1) 能根据信道忙闲程度和网络状态参数自适应调整各优先级竞争窗口长度，从而可将竞争窗口收敛到最佳状态，为不同优先级业务提供了不同的QoS保障能力，得到了最优的系统性能。
2) 仿真实验验证了所建模型准确有效，与Q-ABACW和PAB算法相比，算法在吞吐量性能上具有明显的优势。
参考文献
| [1] | 袁政英. 美空军未来20年小型无人机发展路线图[J]. 防务视点, 2016(10): 58-59. YUAN Z Y. United States air force in the next 20 years the development of a small UAV roadmap[J]. Defense Point, 2016(10): 58-59. (in Chinese) |
| [2] | 陈方舟, 黄靖皓, 赵阳辉. 美军无人"蜂群"作战技术发展分析[J]. 装备学院学报, 2016, 27(2): 34-37. CHEN F Z, HUANG J H, ZHAO Y H. Analysis on unmanned swarm fighting system of US armed forces[J]. Journal of Equipment Academy, 2016, 27(2): 34-37. DOI:10.3783/j.issn.2095-3828.2016.02.008 (in Chinese) |
| [3] | SHARMA V, KUMAR R, KUMAR N. DPTR:Distributed priority tree-based routing protocol for FANETs[J]. Computer Communications, 2018, 122: 129-151. DOI:10.1016/j.comcom.2018.03.002 |
| [4] | KHAN M A, SAFI A, QURESSHI I M, et al.Flying ad-hoc networks (FANETs): A review of communication architectures, and routing protocols[C]//2017 First International Conference on Latest trends in Electrical Engineering and Computing Technologies (INTELLECT).Piscataway, NJ: IEEE Press, 2017: 1-9. |
| [5] | BEKMEZCI I, SAHINGOZ O K, TEMEL S. Flying ad hoc networks(FANETs):A survey[J]. Ad hoc Networks, 2013, 11(3): 1254-1270. |
| [6] | OZGUR K S. Networking models in flying ad-hoc network evaluation:Challenges concepts and challenges[J]. Journal of Intelligent & Robotic Systems, 2014, 74(1-2): 513-527. |
| [7] | ULLAH A, AHN J S. Performance evaluation of X-MAC/BEB protocol for wireless sensor networks[J]. Journal of Communications and Networks, 2016, 18(5): 857-869. DOI:10.1109/JCN.2016.000114 |
| [8] | DIACONU F.A modified binary exponential backoff algorithm for improving the quality of service in highly populated IEEE 802.11e networks[C]//International Symposium on Signals, Circuits and Systems ISSCS2013.Piscataway, NJ: IEEE Press, 2013: 1-4. |
| [9] | FIRYAGUNA F, CARVALHO M M. Performance of polling disciplines for the receiver-initiated binary exponential backoff MAC protocol[J]. Ad Hoc Networks, 2015, 59(1): 1-19. |
| [10] | QI H, HU Z Q, WEN X M.An enhanced MAC backoff algorithm for heavy user loaded WLANs[C]//2017 IEEE Wireless Communications and Networking Conference (WCNC).Piscataway, NJ: IEEE Press, 2017: 1-6. |
| [11] | IKRAM S, SEUNG-HUN S, BYEONG-HEE R, et al. Performance improvement of QoS-enabled WLANs using adaptive contention window backoff algorithm[J]. IEEE Systems Journal, 2018, 12(4): 3260-3270. DOI:10.1109/JSYST.2017.2694859 |
| [12] | 卓琨, 张衡阳, 郑博, 等. 一种优先级区分的机载无线网络MAC层自适应退避算法[J]. 航空学报, 2016, 37(4): 1281-1291. ZHUO K, ZHANG H Y, ZHENG B, et al. An adaptive backoff algorithm in MAC layer for airborne network based on priority differentiation[J]. Acta Aeronautica et Astronautica Sinica, 2016, 37(4): 1281-1291. (in Chinese) |
| [13] | ZHANG B, HU Z, XING K.Performance of RS-Turbo concatenated code in AOS[C]//11th International Conference on Electronic Measurement & Instruments.Piscataway, NJ: IEEE Press, 2013: 983-987. |
| [14] | 刘炜伦, 张衡阳, 郑博. 机载自组网信道占用统计预测机制[J]. 计算机工程与应用, 2018, 54(15): 78-83. LIU W L, ZHANG H Y, ZHENG B. Statistical prediction mechanism for channel occupancy in airborne ad hoc network[J]. Computer Engineering and Applications, 2018, 54(15): 78-83. DOI:10.3778/j.issn.1002-8331.1801-0211 (in Chinese) |
| [15] | XU D H, ZHANG H Y, ZHENG B, et al.A priority differentiated and multi-channel MAC protocol for airborne networks[C]//The 8th IEEE International Conference on Communication Software and Networks(ICCSN).Piscataway, NJ: IEEE Press, 2016: 64-70. |
