, 陆建华 1 1. 清华大学 电子工程系, 北京 100084;
2. 清华大学 宇航技术研究中心, 北京 100084;
3. 北京航天飞行控制中心, 北京 100094
收稿日期：2016-11-11
基金项目：国家自然科学基金重点支持项目（91338108，91438206）
作者简介：高晓琳 (1979-), 女, 博士研究生
通信作者：晏坚, 副研究员, E-mail:yanjian_ee@tsinghua.edu.cn
摘要：针对现有航空Ad hoc网络的媒体接入控制（media access control，MAC）协议存在信道资源分配缺乏公平性的问题，该文提出一种优先级权重速率控制（priority weighted rate control，PWRC）算法。该算法在MAC层上采用加权队列模型，利用业务的优先级及权重值共同控制业务的降速因子，达到在保证高优先级业务服务质量（quality of ser-vice，QoS）的同时提升信道资源利用的公平性。仿真结果表明：与现有MAC协议相比，使用该方法时相同优先级业务的公平性指数接近理论上限1，对信道资源的利用率最高可提升40%；同时，可降低相同优先级业务平均端到端延时及延时抖动。
关键词：航空Ad hoc网络媒体接入控制 (MAC)优先级权重值权重公平队列 (WFQ)服务质量 (QoS)
Priority weighted rate control algorithm in aeronautical Ad hoc networks
GAO Xiaolin1,3, YAN Jian2
, LU Jianhua11.Department of Electronic Engineering, Tsinghua University, Beijing 100084, China;
2.Tsinghua Space Center, Tsinghua University, Beijing 100084, China;
3.Beijing Aerospace Control Center, Beijing 100094, China
Abstract: Current media access control (MAC) protocols for aeronautical Ad hoc networks can not achieve fair channel resource utilization. This paper describes a priority weighted rate control (PWRC) algorithm, which uses the fair queuing model in the MAC layer. The traffic speed reduction factor is determined by its priority and weight. The PWRC guarantees the quality of service (QoS) while the channel resource is fairly utilized. Simulations indicate that the traffic fairness index with the same priority is closer to the upper band 1 than with existing MAC protocols. The channel resource utilization is improved about 40% and the end-to-end delay and jitter are reduced.
Key words: aeronautical Ad hoc networksmedia access control (MAC)priorityweightweight fair queue (WFQ)quality of service (QoS)
由各类飞行器组成的航空Ad hoc网络面临为多种业务提供服务质量 (quality of service，QoS) 保障的需求[1]。媒体接入控制 (media access control, MAC) 协议控制节点的数据报文和消息何时接入无线信道发送，其对QoS的支持能力决定了无线信道资源能否高效地利用。相比地面移动Ad hoc网络，航空Ad hoc网络具有覆盖范围广、网络拓扑高动态、信道质量不稳定等特性。因此，可支持QoS的MAC协议成为航空Ad hoc网络研究的重点内容之一[2]。
现有Ad hoc网络中支持QoS的MAC协议分为2类：一类是采用划分业务优先级来实现区分服务，如802.11EDCF[3]；另一类是利用调度算法实现数据业务对信道资源的公平使用，如Banchs和Nitin等[4-5]分别提出了DWFQ算法和DFS算法。文[6-7]分析表明，802.11EDCF协议这种方式是以高优先级业务占据大量的带宽资源为前提来满足其QoS的需求，牺牲了低优先级业务对信道的使用，其采用的绝对优先级压制机制无公平性可言；另一类算法未使用优先级机制，而是在802.11EDCF协议基础上使用了分布式的公平调度算法，实现了不同权重值 (weight) 的业务对信道资源的比例分配使用。
对于航空Ad hoc网络这种具有高传播延时特征的广域网络来说，基于碰撞重传的MAC协议将会带来高数据延时。为同时保证数据的低延时和高可靠性，文[8-12]提出了一类适用于航空自组织网络的MAC协议，其利用统计的信道业务负载作为接入信道的判断依据，结合802.11EDCF的优先级退避算法，通过降低数据碰撞来减小重传带来的延时。但这类MAC协议由于采用了绝对优先级机制，在高优先级业务量较低时，低优先级业务无法使用全部信道资源，浪费了大量带宽资源。
针对以上问题，本文提出了一种优先级权重速率控制 (priority weighted rate control，PWRC) 算法。该算法在MAC层上采用加权队列模型，利用业务的优先级及权重值共同控制其降速因子。仿真结果表明，该方法在提升了业务对信道资源的利用的公平性的同时，还提升了业务对信道的利用率；在高业务负载条件下，仍可实现高优先级对信道资源的绝对抢占性。该方法还降低了相同优先级业务平均端到端延时及抖动，与现有基于优先级的航空Ad hoc网络MAC协议相比，在QoS保证能力方面有大幅度提升。
1 航空Ad hoc网络优先级权重调度接入模型在航空Ad hoc网中，由于多个节点共享同一条无线信道，当节点内部存在多种待发业务数据时，在实现其内部业务流对共享的无线信道分配使用的同时，还需与其他共享无线信道的邻居节点的业务流竞争信道带宽资源[7]。故从业务流的角度来看，调度算法需要从单节点内部扩展到多个有业务数据发送的节点之间。
考虑到信道接入的限制，当调度算法作用在节点内部时，其结果不能直接映射为业务实际占用的带宽量，即受到MAC层接入算法的制约，节点不能贯彻执行调度命令。
基于上述分析，在航空Ad hoc网的现有优先级MAC层上结合公平队列模型，联合考虑调度与信道接入算法。本文使用的调度接入模型框图如图 1所示。图中节点1和n分别有若干业务流等待调度接入信道发送。每个业务流将队列中首个分组的优先级及其权重值送至速率控制器，该控制器调用物理层周期性统计的信道负载量，运行PWRC算法计算不同节点不同业务流的平均接入速率，来实现业务分布式调度接入。
 |
| 图 1 调度接入模型 |
| 图选项 |
2 PWRC算法实现在说明PWRC算法前，先对经典权重公平队列算法及航空Ad hoc网络基于优先级的支持QoS的MAC协议进行介绍。
2.1 经典权重公平队列调度算法经典权重公平队列调度算法—WFQ (weighted fair queuing) 算法[13]能够实现不同权重业务对信道带宽的比例公平共享，比例值由业务权重值决定。
假设第i个队列的第k个分组在ai, k时刻到达，其长度为Li, k。用Si, k和Fi, k分别表示开始服务这个分组和结束服务这个分组的虚拟时间标签。对所有的i，定义Fi, 0=0，则
| $\begin{array}{c}{S_{i,k}} = {\rm{max}}\left\{ {{F_{i,k - 1}},V({a_{i,k}})} \right\},\\{F_{i,k}} = {S_{i,k}} + {L_{i,k}}/{w_i}.\end{array}$ |
2.2 基于优先级的支持QoS的MAC协议航空Ad hoc网络基于优先级的支持QoS的MAC协议采用了信道负载控制技术，信道上允许同时传输多个数据分组。文[11]中给出了信道负载统计的具体方法，并建立了的分组碰撞模型，实现了信道中分组业务量与接收成功概率之间的映射关系，获得业务接入的最大门限值A_TH，也就是信道最大负载Max_NL的计算方法。其中，Max_NL由信道允许同时接入传输的用户数量和单用户信息发送速率决定。
在不考虑优先级情况时，如果节点有数据要发送，先统计当前信道负载，若低于A_TH，即刻接入信道发送；若不低于A_TH，则在[0，cw]中随机选择B为退避间隔，退避时长Tb=B·aslottime，aslottime为时隙长度。其中cw称为竞争窗口。当B递减为0时，若当前信道负载低于A_TH，则节点数据发送，同时cw重置为CWmin，即系统设置的最小竞争窗口；当B递减为0但信道负载不低于A_TH时，cw增大一倍，重新设置B。
多优先级业务时，为每个优先级指定了优先级门限A_THpj，对应最小竞争窗口CWmin、最大竞争窗口CWmax。为保证高优先级的绝对抢占能力，门限值将随优先级的下降而降低，最大和最小竞争窗口也随之增大。
2.3 PWRC算法本算法运行的前提是网络与用户之间建立了QoS约定，即不同业务被赋予了不同的优先级及权重值 (weight)。业务优先级越高，其抢占信道资源的能力越大；业务权值越高，其获得的信道资源就越多。
算法的优先级设定沿用航空Ad hoc网络的基于信道负载统计的MAC协议中的优先级设定，并使用其优先级门限作为是否启用退避的依据，以保证不同业务的接入优先率。
算法的权重公平性则源于公平队列调度算法中的发送最小结束时间标签的分组，同时使用自时钟公平队列 (self-clock fair queue，SCFQ) 算法[14]中更新系统虚拟时间的方法。
节点间确定最小结束时间标签的分组则依据航空Ad hoc网络中优先级退避时长来完成。具体方法是建立结束时间标签与退避时长的映射关系。
每个节点维护自己本地的系统虚拟时间vi(t)，且vi(0)=0。Pi, k表示节点i的业务流中第k个数据分组。
其开始时间可由式 (1) 计算，分组结束时间标签则是在节点i将数据分组发送出去后，该分组才打上结束时间标签Fi, k。当节点i在时间t收到或发送了数据分组后，根据分组的结束时间标签F，更新系统虚拟时间vi(t) 为max (vi(t), F)。
由于分组在接入信道发送前，需先判断信道负载状态，依据优先级进行退避等待，其实际结束时间标签可表示为
| ${F_{i,k}} = {S_{i,k}} + \gamma \frac{{{L_{i,k}}}}{{{w_i}}}.$ | (1) |
则分组的实际退避时长表示为
| ${T_b} = \left| {{F_{i,k}} - {S_{i,k}}} \right| = \gamma \frac{{{L_{i,k}}}}{{{w_i}}}.$ | (2) |
式 (2) 表明，当退避时长引入权重值wi调整时，即可满足不同节点的不同权重值业务对信道占用量的比例分配使用。
同时，为了避免信道过载，节点将根据统计到的信道负载信息与A_THpj比较的结果来判断是否进入退避状态。当节点进入退避状态时，分组的退避时长越大，其接入信道越慢，即退避时长直接控制了分组的接入速率。本算法从接入速率控制入手，给出了不同优先级，不同权重的退避时长具体计算方法。
现有航空Ad hoc网络的基于信道负载统计的MAC协议，优先级为pj的业务最大信道利用率为βpj时，其优先级接入门限值A_THpj由下式确定：
| ${\rm{A\_T}}{{\rm{H}}_{{p_j}}} = {\beta _{{p_j}}}{\rm{Max\_NL}}{\rm{.}}$ | (3) |
| ${\rho _{ij}} = \frac{{{R_{{\rm{max}}}}\frac{{{w_i}}}{{{\rm{max}}\{ {w_i},{\rm{ }}i \in \mathit{\Omega }\} }}}}{{{\rm{Max\_NL}} - {\rm{A\_T}}{{\rm{H}}_{{p_j}}}}}.$ | (4) |
| ${R_{ij}} = {\rho _{ij}}({\rm{Snet - }}A{\rm{\_T}}{{\rm{H}}_{{p_j}}}).$ | (5) |
退避时长表示为
| ${T_b} = \left\{ {\begin{array}{*{20}{l}}{0,}&{{\rm{Snet}} < {\rm{A\_T}}{{\rm{H}}_{{p_j}}};}\\{\frac{{L_i^k}}{{{R_{ij}}}} - \Delta ,}&{{\rm{Snet}} \ge {\rm{A\_T}}{{\rm{H}}_{{p_j}}}.}\end{array}} \right.$ | (6) |
节点依据统计的网络负载值Snet计算出对应优先级为pj权重值为wi的分组的退避时长，以达到对分组接入速率的调整控制，进而实现多节点的多种业务对共享无线信道带宽的动态分配。不同系统中权重值的设定依据不同，与系统承载的业务种类相关，本文不对权重值的具体数值设置进行讨论。
3 仿真分析本文采用了OPNET网络仿真软件对提出的PWRC算法进行仿真分析。仿真场景中，节点均匀分布于150 km×150 km的平面范围内。业务产生模式采用Poisson业务模式，数据分组长度固定为1 024 bit。具体仿真参数设置见表 1。
表 1 仿真参数表
| 参数 | 数量 |
| 节点最大信息发送速率 | 2 Mb/s |
| 同时接入信道用户数量 | 5个 |
| Max_NL | 10 Mb/s |
| 数据分组长度 | 1 024 bit |
| 分组拆分脉冲数量 | 32个 |
| 跳频频点数量 | 16个 |
| 纠错编码 | 1/3Turbo码 |
| βpj | 60%, 70%, 80%, 90% |
表选项
将本文提出的方法与基于优先级的MAC协议进行比较。现有基于优先级的MAC协议中基于优先级 (priority-based) 的二进制退避参数采用了802.11EDCF中的参数设置[12]，本文同样使用了该项参数设置。后续仿真说明中p1~p4代表优先级1~4，且优先级依次降低。
3.1 PWRC算法的公平性本文使用公平指数 (fairness index，FI) 作为评价公平性的标准。FI提供了一个计算公式，可计算公平的程度，定义[15]为
| ${\rm{FI}} = \frac{{{{(\sum\limits_f {{T_f}/{w_f}} )}^2}}}{{N[\sum\limits_f {{{({T_f}/{w_f})}^2}} ]}}$ |
在进行公平性比较时，对相同优先级业务的公平性指数进行比较。此仿真场景中，源节点均产生相同优先级业务数据，其平均速率为1 Mb/s。仿真结果为最低优先级业务，其接入门限值根据式 (5) 可知为6 Mb/s。每2个节点为一对通信节点，故当场景中节点数量为n时，业务流数量为n/2。源节点i的业务权重值设置为2/i。
节点数量取值分别在8、32、64、96、112时，如图 2所示，采用指数退避的优先级MAC协议随着节点数量增大时，业务FI降低。这是由于节点数量增加时待发送业务量增大，分组在接入信道发送前需进行退避等待。由于退避时长的随机性，导致每个节点接入信道发送分组等待的时长无法协调，更无法根据业务的权重调整其退避时长。反观PWRC算法的FI接近于1，说明各权重业务对信道的使用可实现近似公平。
 |
| 图 2 优先级p4业务FI |
| 图选项 |
图 3为优先级p4业务在不同节点数量条件下的平均吞吐量变化曲线。PWRC算法的吞吐量明显高于使用指数退避的优先级MAC协议的吞吐量。这是由于，现有基于优先级的MAC协议采用的是对低优先级进行截留，为高优先级预留带宽的方法。故该方法出现了图 4中即使没有其他优先级业务，低优先级业务仍然只能使用部分信道带宽的现象。与本文算法相比，在无其他优先级业务时，业务可独享全部信道资源，其总吞吐量接近了信道最大可用带宽，此时对信道利用率的提升达到最大，约为40%。
 |
| 图 3 优先级p4业务总吞吐量 |
| 图选项 |
 |
| 图 4 基于优先级退避参数的吞吐量 |
| 图选项 |
3.2 PWRC算法的优先级性能在进行优先级性能分析时，不考虑业务权重值，故所有业务权重值均设置为1。主要比较2种方法的各优先级业务量等比例增加时，各优先级业务的吞吐量的变化情况，即对信道的使用情况。此仿真场景中，节点数量为50个，均为源节点。节点同时产生4种优先级业务数据，平均速率相同，由0.01 Mb/s递增至0.25 Mb/s。由此，系统的总业务量将由2 Mb/s增至50 Mb/s。
图 4为基于优先级的MAC协议中4个优先级业务的吞吐量随系统的总业务负载增长时的变化情况。由于各优先级配合接入门限值使用二进制退避机制，当总业务量大于6 Mb/s时，优先级p4的业务吞吐量只能维持在约1.5 Mb/s，直至总业务量达到约13.3 Mb/s时，由于实际信道的业务量已饱和，优先级p4因退避窗口大于其他业务优先级，故其吞吐量开始下降，系统优先级保证其他高优先级业务。对于优先级p2和优先级p3的业务，其吞吐量变化趋势相同。采用这种方法，虽然可以实现对高优先级的信道带宽保证，但各优先级业务未实现对信道带宽的充分利用。
图 5为场景中节点使用了本文提出的PWRC算法时，各优先级业务的吞吐量及总吞吐量 (各优先级业务吞吐量之和) 随系统总业务负载增长时的变化。对比图 5，各优先级的最大吞吐量均有提升，在本仿真条件下，优先级p1、p2、p3、p4业务依次提升了约10%、17%、25%、33%。同时，本方法仍遵守了系统对高优先级业务优先级保证的原则且满足了总吞吐量不高于信道最大负载量10 Mb/s的要求。
 |
| 图 5 PWRC算法的吞吐量 |
| 图选项 |
表 3为总业务量均为20 Mb/s时，各优先级业务平均端到端延时及延时抖动仿真数据比较。数据表明，PWRC算法在保证各类优先级业务较低平均延时的同时，还降低了延时抖动。
表 3 平均延时、延时抖动
| 优先级 | 优先级 | PWRC | |||
| 延时/ms | 抖动/ms | 延时/ms | 抖动/ms | ||
| 4 | 20.3 | 700 | 10.81 | 6.90 | |
| 3 | 13.87 | 230.65 | 8.56 | 4.13 | |
| 2 | 4.32 | 50.89 | 2.82 | 3.76 | |
| 1 | 2.56 | 20.56 | 1.34 | 1.09 | |
表选项
4 结论本文针对航空Ad hoc网络现有MAC协议无法实现对信道带宽的公平分配问题，提出了一种PWRC算法。该算法通过在MAC层上采用加权队列模型，以业务的优先级及权重值共同控制降速因子实现调度接入控制。仿真结果表明，使用本方法时相同优先级业务的公平性指数接近理论上限1，同时，对信道带宽的利用率最大可提升40%；在多优先级条件下，本方法在实现多优先级、多带宽分配需求的同时还降低了平均端到端延时及抖动。相比现有航空Ad hoc网络MAC协议，该方法增强了对QoS的支持能力。
参考文献
| [1] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Karras K, Kyritsis T, Amirfeiz M, et al. Aeronautical mobile ad hoc networks[C]//Proceedings of the 14th European Wireless Conference. New York, NY, USA:IEEE Computer Society, 2008:1-6. |
| [2] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Wang Y, Zhao Y J. Fundamental issues in systematic design of airborne networks for aviation[C]//Proceedings of IEEE Aerospace Conference. New York, NY, USA:IEEE Computer Society, 2006:1-8. http://ieeexplore.ieee.org/abstract/document/1655882/ |
| [3] | Journal of Central South University(Science and Technology), 41(2):649-654.--> IEEE. IEEE Std.802.11e-2005.Part Ⅱ:Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications Amendment 8:Medium Access Control (MAC) Quality of Service Enhancements[S]. New York:IEEE Computer Society, 2005. |
| [4] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Banchs A, Perez X. Distributed weighted fair queuing in 802. 11 wireless LAN[C]//Proceedings of IEEE International Conference on Communications. New York, NY, USA:IEEE Computer Society, 2002:3121-3127. http://ieeexplore.ieee.org/abstract/document/997412/ |
| [5] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Vaidya N, Dugar A, Gupta S, et al. Distributed fair scheduling in a wireless LAN[J]. IEEE Computer Society, 2005, 4(6): 616–629. |
| [6] | Journal of Central South University(Science and Technology), 41(2):649-654.--> He D J, Shen C Q. Simulation study of IEEE 802. 11e EDCF[C]//Proceedings of the 57th IEEE Semiannual. New York, NY, USA:IEEE Computer Society, 2003:685-689. |
| [7] | Journal of Central South University(Science and Technology), 41(2):649-654.-->XIAO Yang. IEEE 802. 11e:QoS provisioning at the MAC layer[J]. IEEE Personal Communications, 2004, 11(3): 72–79. |
| [8] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Stephen M C. Statistical priority-based multiple access and method. United States patent US 7680077 B1. 2010-03-16. |
| [9] | Journal of Central South University(Science and Technology), 41(2):649-654.--> ZHANG Hongmei, PENG Shasha, ZHAO Yuting, et al. An improved algorithm of slotted-ALOHA based on multichannel statistics[C]//Proceedings of the 5th International Symposium on Computational Intelligence and Design. New York, NY, USA:IEEE Computer Society, 2012:37-40. |
| [10] | Journal of Central South University(Science and Technology), 41(2):649-654.-->王叶群, 杨峰, 黄国策, 等. 一种航空自组网中带差分服务的跳频MAC协议建模[J]. 软件学报, 2013, 24(9): 2214–2225.WANG Yequn, YANG Feng, HUANG Guoce, et al. Media access control protocol with differential service in aeronautical frequency-hopping Ad hoc networks[J]. Journal of Software, 2013, 24(9): 2214–2225. (in Chinese) |
| [11] | Journal of Central South University(Science and Technology), 41(2):649-654.-->高晓琳, 晏坚, 陆建华. 一种支持QoS的航空自组织网络无反馈MAC协议建模[J]. 北京航空航天大学学报, 2016, 42(6): 1169–1175.GAO Xiaolin, YAN Jian, LU Jianhua. A collision model providing QoS guarantee for the feedback-free MAC in aeronautical Ad hoc networks[J]. Journal of Beijing University of Aeronautics and Astronautics, 2016, 42(6): 1169–1175. (in Chinese) |
| [12] | Journal of Central South University(Science and Technology), 41(2):649-654.-->张伟龙, 吕娜, 杜思深. 应用于航空Ad hoc网络的高负载优先级均衡MAC协议[J]. 电讯技术, 2014, 54(5): 656–661.ZHANG Weilong, Lü Na, DU Sishen. A balancing priority MAC protocol under high load for aviation Ad hoc network[J]. Telecommunication Engineering, 2014, 54(5): 656–661. (in Chinese) |
| [13] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Bensaou B, Wang Yu, Ko C C. Fair medium access in 802.11 based wireless Ad hoc networks[C]//Proceedings of 2000 First Annual Workshop on Mobile and Ad hoc Networking and Computing. New York, NY, USA:IEEE Computer Society, 2000:99-106. |
| [14] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Golestani S J. A self-clocked fair queueing scheme for broadband applications[C]//Proceedings of Networking for Global Communications. New York, NY, USA:IEEE Computer Society, 1994(2):636-646. |
| [15] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Jain R, Babic G, Nagendra B, et al. Fairness, Call Establishment Latency and Other Performance Metric[R]. Tech Rep ATM_Forum/96-1773, ATM Forum Document, 1996. |
