应用于航空Ad Hoc网络的高负载优先级均衡MAC协议*

张伟龙，吕 娜，杜思深

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

1 引言

Ad Hoc网络多采用随机接入类MAC协议，以实现对网络拓扑变化的灵活适应，但其协议固有的竞争碰撞造成接入时延以及接入公平性问题，在高负载航空数据链环境中愈加突出［1－4］。通过改进RTS/CTS握手机制、载波侦听机制、退避机制、交互预约机制、多信道机制等方法，衍生出了大量的MAC协议，以解决网络负载逐渐提升带来的时延和公平性问题。

CSMA［5］在ALOHA基础上利用信道检测初步解决碰撞问题，减小了一定的时延，但高负载时碰撞率依然较高;BTMA［6］协议利用多信道忙音一定程度上解决了CSMA节点隐藏问题带来的接入时延问题，但会造成某些节点的饥饿问题，导致节点接入不公平;文献［7］在IEEE 802.11基础上引入博弈论思想，使用户流获取公平性的最优信道竞争参数CWmin，但是忽略了高优先级业务的高实时性要求，过分强调公平性。文献［8］在IEEE 802.11e基础上，不同优先级业务采用不同的信道竞争能力，保证高优先级业务低时延优先接入，但低优先级业务在高负载时将会出现高时延问题。

在业务高负载、节点高密度网络中，上述MAC协议虽然考虑了时延与公平性，但当流量超过网络容限时，冲突碰撞增加，网络会迅速拥塞，实时性能将会急剧下降，导致重要信息不能及时发送［3］。基于信道统计优先的多址接入协议(Statistical Priority－ based Multiple Access，SPMA)［9］在多信道统计机制下，利用优先级机制，在网络负载超过容限时对低优先级业务进行适时截流停发，维持网络通畅且不迅速恶化，保证高优先级业务低时延发送，但此时低优先级业务时延较大。

本文基于SPMA协议思想，改进信道占用统计及阈值－回退算法，提出一种多信道MAC协议——基于低时延的高负载优先级均衡(Priority Balancing based on Low Latency under High Load，PBLL/HL)，以改善航空环境下业务高负载、节点高密度的网络性能:网络流量未饱和时，提升网络吞吐量，保证高优先级业务低时延接入;网络流量饱和过载时，优化网络流量，尽可能维持最优网络吞吐量，维持高优先级业务低时延发送，降低低优先级业务由于截流带来的时延，使网络不会迅速拥塞恶化。

2 收发信机制

MAC协议的性能与物理层波形设计密切相关［10－12］，依据 SPMA 多信道机制，PBLL/HL 协议与收发机制进行联合设计。

首先将物理收发信道扩展为5个，在5个动态分配信道上同时进行发送或者接收，即同时1路发送、4路接收，从物理设备上提供减小碰撞机率和增加用户数量的性能改善基础。

其次，原业务数据包MES采用LDPC纠错扩展编码，分割成N个待发送的子数据块(SM)，SM在对应优先级队列排队等待，根据PBLL/HL选择信道发送，数据块时频分布如图1所示，从数据帧结构上减小数据碰撞概率。

图1 时间和频率上消息MES波形图Fig.1 Waveform of the MES in time and frequency

接收端多路接收子数据块，部分子数据块的碰撞丢失仍能依靠强纠错解码正确恢复。从编码机制上提升误码纠正能力，进而改善冲突分解能力。

通过上述收发信机制，数据碰撞概率大为减小，碰撞误码对接收数据正确恢复的影响大为减小，数据传输容错性增强。

3 PBLL/HL协议

传统的竞争类MAC协议随着负载的增加，吞吐量在过载时会急剧下降，如图2曲线A所示，然而理想需求的是曲线B所示的稳定性吞吐量，即需要对信道接入进行有效控制。

图2 负载－吞吐量趋势Fig.2 Trend of load － throughput

CSMA类接入控制，传播时延大于分组帧长时，会导致碰撞检测失真;TDMA类接入控制，由于固定时隙，造成不必要的时延和资源浪费;集中式控制类，由于节点数量和业务数量，使得成本高且难实现。

因此，PBLL/HL采用SPMA的分布式接入控制思想，利用多信道占用统计与优先级阈值判别，适时截流停发低优先级业务，尽可能实现理想曲线B的性能要求，确保高优先级业务的绝对实时发送(小于2 ms)［4］。由于SPMA截流机制使得低优先级业务接入时延较高，PBLL/HL设计了公平性优先级阈值和冲突回退算法(Priority Threshold and Conflict Back off Algorithm，PCA)，在高优先级业务低时延发送的前提下，改善低优先级业务的较高时延问题，提高网络吞吐量。

3.1 优先级发送判别机制

PBLL/HL将业务进行优先级分类，在网络过载时，通过优先级阈值和信道占用统计比较，使低优先级业务停发等待，优化网络流量，保证高优先级业务成功传输，网络状态良好时，再对低优先级业务进行处理发送。既保证了重要业务通信的顺畅，又不会使网络过载，维持了比较稳定的吞吐量。

优先级阈值是各优先级对应的发送判别门限;信道占用统计是预定周期内信道上脉冲数量的累计，在此预定周期结束时，信道占用统计清零，再去生成新的信道占用统计。如图3所示，PBLL/HL中T/R信道占用统计是对收发机数据在整个频率－时间有效空间进行计算，得到5个单信道的占用统计值。

图3 PBLL/HL协议流程Fig.3 Flow chart of PBLL/HL

SPMA只对接收机进行统计，由于节点自身业务量会导致信道占用统计失真，业务量较小节点信道占用统计偏大，下一时刻业务接入机率较小，业务量大节点反之，出现节点不公平现象，且有可能导致碰撞增加。

请求发送某优先级数据包时，PBLL/HL会将各信道占用统计与该优先级阈值进行比较，选择满足条件的信道进行数据发送。

协议判别如图3所示，检测优先级队列，无数据时持续检测，有数据时先从高优先级数据进行发送，将较高优先级队列数据包取出，判断是否期满，如果没有期满，将5个信道占用统计与对应优先级阈值比较，如果有满足条件的信道，即低于优先级阈值，则随机选择满足条件的信道发送;如果没有满足条件的信道，即都高于优先级阈值，节点将按照该优先级回退算法等待一个随机回退间隔，并再次检测信道占用统计。

如果在随机回退期间，比它低的优先级业务数据被排队等待发送，则将低优先级业务数据保存在对应优先级队列中，直到更高优先级队列数据发送为空;如果一个比它高的优先级业务数据在回退间隔期间被排队等待发送，则回退取消，立刻重新检测较高优先级业务阈值，与信道占用统计进行比较。随后再次进行以上过程，将允许发送的数据包从队列移除进行发送。

在预定周期内，由于局部突发性数据，会导致局部节点信道占用统计迅速增长并高于最高优先级阈值，所有业务数据将不能发送，造成接入时延增加、资源浪费。SPMA未考虑这种情况，此时，如果剩余预定周期大于其值的一半，PBLL/HL将使信道占用统计迅速归零，以应对突发数据带来的时延和资源浪费问题。

此优先级发送机制使得高优先级业务能够尽可能短时间地进行发送，保证重要数据的实时性，在网络高负载时可对低优先级进行截流控制，维持网络的通畅。

3.2 公平性PCA算法

信道占用统计失真、预定周期设置不合理、优先级阈值不匹配当前网络状态、网络的不确定性以及突发业务数据，都会使得信道占用统计达到一个门限，此时低优先级业务被禁止发送，造成时延加大，高优先级业务数量较小，造成信道资源的浪费，故而提出公平性的PCA算法。

各优先级阈值Fi按照优先级从高到低排列，高优先级业务阈值相对较大，同时每个阈值设置一个浮动窗口［FMIN，FMAX］，各浮动窗口没有交集，鉴于业务优先级越高对高负载时在传信息量影响越大，为了稳定吞吐量，增加低优先级业务接入机率，高优先级浮动窗口较小，低优先级浮动窗口较大，例如，优先级 0的初始值取1000，浮动窗口为［950，1050］，优先级 1的初始值取 800，浮动窗口为［700，900］。

Fi初始化为浮动窗口的中值，按照流量拥塞控制机制，当成功发送一个数据时，其对应优先级阈值在原有基础上进行一个增加，使得下次接入机率增加;当发送失败时，即进行回退等待的情况，优先级阈值直接降到浮动窗口最小值与当前优先级阈值的中间值，以减少业务发送，保证网络的通畅。Fi数值变化如式(1)所示:

在此基础上，回退等待机制也充分考虑低优先级问题。BEB退避算法，竞争窗口采用二进制指数，冲突时CW=min(2iCWMIN，CWMAX)，成功时直接让窗口减小为CWMIN，造成小时间尺度的不公平性现象，发送时延抖动性强，不适用实时业务。MILD退避算法，信息发送冲突回退时，竞争窗口的值增加为原来的1.5倍，直至CWMAX;发送成功时，竞争窗口CW值减1，局限于信息量较少的网络。MIMD退避算法，信息发送冲突回退时，竞争窗口的值增加为原来的2倍，直至CWMAX;发送成功时，竞争窗口CW变为原来的0.5倍，直至CWMIN，适用于节点多的场景，但没有考虑业务优先级问题［2－3］。

本文考虑到网络信息量大、实时性要求高，以及公平性原则，某优先级业务进行回退时，对应回退竞争窗口为［0，CWi］，［CWMIN，CWMAX］是 CWi对应的窗口范围，高优先级窗口最小值CWMIN较大，但窗口范围较小，低优先级反之;因为高优先级发生碰撞回退时，说明信道负载过重趋于拥塞，需要对数据进行大量遏制截流，回退时间应该较大，但考虑到低时延要求，回退时间抖动应该较小。

CWi初始化为CWMIN，在发送冲突回退或者发送成功时，CWi按照回退次数和优先级在窗口中进行优化选择。CWi数值变化如式(2)所示:

本文采用4个优先级的消息体制，分别为0、1、2、3 级，0代表最高级，式(2)中 PF［i］=COi+2+i×0.1，COi代表i级优先级业务在预定周期内的回退次数，回退次数越多则回退时间越长;MF［i］=(4－i)×0.2，i代表优先级数，优先级越低回退时间越低，保证低优先级业务尽快发送。

由于截流机制，网络实际在传流量很难达到饱和流量，高优先级业务回退的机率较小。考虑到公平性，PCA算法重点考虑低优先级业务，在信道允许的情况下，既不影响高优先级业务的实时发送，又充分利用信道资源，增加低优先级业务接入成功率，提升网络整体实时性。

4 仿真分析

利用Exata仿真平台对PBLL/HL协议性能进行仿真测试，场景及参数如图4所示，设置8组不同优先级业务流，分别为业务优先级为3的1～10、7～15数据流，业务优先级为2的2～8、12～14数据流，业务优先级为1的3～9、6～13数据流，业务优先级为0的4～11、5～16数据流，共用5个信道。

2Mb/s的信道速率满足大容量、高速率数据流传输，优先级数根据真实指令等级数确定，设置8组不同优先级的业务流，最大限度的逼近真实场景。为更加直观便捷地统计时延及吞吐量，每架飞机只有特定的优先级数据流，与真实场景有差异，但不影响性能参数的真实性、准确性。

图4 三维仿真场景Fig.43 D simulation scenes

4.1 时延

网络的业务量为0.5 Mb/s、1 Mb/s、1.5 Mb/s、2 Mb/s、2.5 Mb/s、3 Mb/s，依次增加进行时延统计，得到业务量由低负载到过载过程中的时延变化趋势。仿真中使用PBLL/HL、SPMA两种协议，后者按照优先级采用固定的优先级阈值和回退窗口，仿真中其值取PCA算法的初始值。

端到端时延仿真结果如图5所示，PBLL/HL协议时延大体分布在0～1 s之间。当网络流量不大、负载较轻时，各优先级业务的时延都接近于0;随着网络负载不断加重，高优先级业务时延变化不大，其他优先级业务时延增加幅度较大，如0优先级业务基本不变，4优先级业务时延上升明显，最高时达到了1.02 s，说明协议通过对低优先级业务的截流遏制，维持良好的网络负载，实现了对高优先级业务的低时延要求。

图5 多节点多优先级业务的时延性能Fig.5 The latency performance of multiple nodes with multiple priority data

从图5还可以看出，对于高优先级业务，两条仿真曲线基本重合，差值最大为0.002 s，说明PCA公平性算法基本不影响高优先级业务时延;而对于低优先级业务，SPMA时延明显高于PBLL/HL，而且优先级越低，两个协议时延差越大，例如3优先级业务在业务量为3 Mb/s时，PBLL/HL时延比SPMA时延要低0.11 s，而2优先级业务时延差0.08s，说明PCA算法对较低优先级业务作用明显;8条曲线对比说明采用PCA算法，既保证了高优先级业务的低时延发送，又降低了低优先级业务的接入时延，减小了网络平均时延，更好地保证了网络的实时性。

4.2 归一化吞吐量

网络业务量从0开始，以1为单位增加至30，进行吞吐量统计，得到PBLL/HL下业务量由低负载到严重过载过程中的吞吐量曲线，同时引入ALOHA、时隙 ALOHA 吞吐量曲线［3－13］，如图 6 所示。纯ALOHA当负载为0.5时，吞吐量最大达到18.4%;时隙ALOHA当负载为1时，吞吐量最大达到36.8%。由这两条曲线可看出，当吞吐量达到最大值后，随着负载继续增加，吞吐量急剧下降，说明过载时数据冲突急剧增加，协议碰撞回避机制弱，不适用高负载网络。

图6 负载与吞吐量曲线Fig.6 Performance curve of load － throughput

如图6所示，PBLL/HL仿真曲线随着负载增加快速升高，负载达到10时开始缓慢下滑，直至负载为30时，曲线仍未急剧下降，且趋于平滑，说明PBLL/HL协议碰撞回避机制优势明显，当网络超载时，不会迅速趋于拥塞，能够根据信道占用情况，遏制较低优先级业务数据发送，达到截流目的，保证较高优先级业务传输通畅，维持较稳定的吞吐量。PBLL/HL流量为10时，吞吐量最大达到88.1%，说明PBLL/HL的负载性能明显提升，吞吐量和信道利用率高。

5 结论

业务高负载、节点高密度的航空数据链网络中，PBLL/HL区分不同业务等级，通过公平性优先级截流机制，优化网络流量，使网络实际在传流量很难达到饱和，确保业务低时延发送的成功率;弱化甚至避免了流量过载带来的高时延和网络拥塞，维持了较为稳定的吞吐量。本文中预定周期长度直接关系到信道占用统计的时效性，如何寻找最优的预定周期将是后续工作研究的重点。

［1］Jurdak R，Lopes C V，Baldi P.A survey，classification and comparative analysis of medium access control protocols for ad hoc networks［J］.IEEE Communications Sur-veys ＆ Tutorials，2004，6(1):2 －16.

［2］张棋飞.无线自组织网络路由及MAC协议关键技术研究［M］.武汉:湖北人民出版社，2012.ZHANG Qi－fei.Key Techniques of Routing and MAC Protocal in the Wireless Self－organized Network［M］.Wuhan:Hubei People's Publishing House，2012.(in Chinese)

［3］吕娜，杜思深.数据链理论与系统［M］.北京:电子工业出版社，2011.LV Na，DU Si－ shen.Theory and System of Data Link［M］.Beijing:Publishing House of Electronics Industry，2011.(in Chinese)

［4］骆光明，杨斌.数据链——信息系统连接武器系统的捷径［M］.北京:国防工业出版社，2008.LUO Guang－ming，YANG Bin.Data Link——The Shorcut between Information System and Weapon System［M］.Beijing:National Defense Industry Press，2008.(in Chinese)

［5］Kleinrock L，Tobagi F A.Packet switching in radio channels:part I——carrier sense multiple － access modes and their throughput－ delay characteristics［J］.IEEE Transactions on Communications，1975，23(12):1400－1416.

［6］Tobagi F A，Kleinrock L.Packet switching in radio channels:part II——The hidden terminal problem in carrier sense multiple－access and the busy － tone solution［J］.IEEE Transactions on Communications，1975，23(12):1417－1433.

［7］张国鹏，张海林，赵力强.WLAN中基于协作博弈的比例公平性带宽分配机制［J］.西安电子科技大学学报(自然科学版)，2009，36(1):87 －93.ZHANG Guo － peng，ZHANG Hai－ lin，ZHAO Li－ qiang.Cooperative game theoretic bandwidth sharing scheme for proportional fairness in WLAN［J］.Journal of Xidian University(Natural Science)，2009，36(1):87 －93.(in Chinese)

［8］李楠，蔡跃明，程乃平.Ad Hoc网络中一种具有优先控制的自适应协同 MAC协议［J］.信号处理，2011，27(3):450－455.LI Nan，CAI Yue － ming，CHENG Nai－ ping.An adaptive cooperative MAC with priority for Ad Hoc networks［J］.Signal Processing，2011，27(3):450－455.(in Chinese)

［9］Stephen M C，Hoback K A，Scott J F.Statistical priority －based multiple access:US，768077B1［P］.2010－03－16.

［10］Weingarten H T L，Viswanath P.The capacity region of the degraded multi－input multi－output compound broadcast Channel［J］.IEEE Transactions on Information Theory，2009，55(11):5011 －5023.

［11］Ekrem E，Ulukus S.The secrecy capacity region of the gaussian MIMO multi － receiver wiretap channel［J］.IEEE Transactions on Information Theory，2011，57(4):2083－2114.

［12］宋煜，左德承，杨孝宗，等.一种用于多信道Ad Hoc网络MAC协议的匹配策略［J］.计算机学报，2012，35(5):1018－1030.SONG Yu，ZUO De － cheng，YANG Xiao － zong，et al.A matching algorithm for multichannel Ad Hoc medium access control protocol［J］.Chinese Journal of Computers，2012，35(5):1018 －1030.(in Chinese)

［13］Goldsmith A J，Wicker S B.Design challenges for energy － constrained ad hoc wireless networks［J］.IEEE Wireless Communications，2002，9(4):8 －27.