带有时间约束的机载自组网自适应退避算法

赵玮, 郑博, 张衡阳, 刘炜伦

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

机载自组网(Airborne Ad hoc Network)是利用航空通信和移动Ad hoc网络技术,通过无线信道将一定空域内的各种飞行器互联互通,构成的一个分布式、无中心的信息传输网络,具有部署快速、组网灵活、抗毁性强等优势[1-4]。机载自组网存在网络拓扑快速动态变化、多优先级业务并存、信道资源有限等问题,随着网络负载持续增大,易造成信道中发生大量拥塞和冲突,导致网络性能急剧下降,无法保障指挥控制指令、武器协同信息等高优先级业务低时延、高可靠的服务质量(quality of service,QoS)[5-7]。针对这些问题,机载自组网的退避算法作为随机竞争类媒质接入控制(medium access control,MAC)协议的重要组成部分,要能够有效避免大业务量时信道中的分组冲突,并满足各优先级业务的不同QoS需求,保证信息传输的时效性、可靠性。因此,针对机载自组网MAC层设计一种合理、高效的退避算法是保证网络良好性能的前提。

目前Ad hoc网络MAC协议所采用的退避算法主要有以下3类。①二进制指数退避(binary exponential backoff,BEB)算法及增强型分布式信道访问(enhanced distributed channel access,EDCA)算法[8-9]。该类算法存在容易造成网络不公平、当负载变化时无法快速选取最佳竞争窗口,以及在饱和状态时网络性能下降严重等问题。②服务区分动态退避算法[10-11]。这类算法通过对不同优先级业务采用不同的退避方式,有效保障高优先级业务的传输,但该类算法的复杂程度会随着优先级数量的增加而指数上升。③自适应退避算法。文献[12]提出竞争窗口自适应调整的退避算法,根据分组冲突的概率来估计活跃节点数量,从而动态调整竞争窗口,有效提升了网络性能,但该算法无法实时准确估计活跃节点数量;文献[13]提出了一种区分业务优先级的自适应退避算法(PAB),通过实时调整节点相邻退避阶段的前后转移概率,为多种优先级业务提供不同的服务,但其转移概率的设定需要进一步优化。

为了实现机载自组网中多优先级业务的并存传输,以及保障高优先级业务低时延、高可靠的传输需求,本文提出了一种带有时间约束的多优先级自适应退避(time constraint based priority adaptive backoff,TC-PAB)算法。该算法一方面采用基于业务优先级和网络忙闲程度的竞争窗口自适应调整机制,通过动态调整不同优先级业务的竞争窗口大小,并在重负载时通过限制低优先级分组接入来保证高优先级业务的QoS传输需求;另一方面通过分组时间约束机制对各优先级分组设定相应的约束时间,对超过约束时间的分组直接丢弃,避免分组长时间占用发送队列,保障各优先级分组传输的实时性。

1　退避算法描述

由于机载自组网中各优先级业务具有不同的QoS需求,本文所提TC-PAB算法主要采用了退避阶段竞争窗口自适应调整机制和时间约束机制,实现不同优先级业务的区分服务。该算法的基本原理如图1所示,首先对上层产生的业务分组进行纠错编码,然后分组进入相应的优先级队列等待发送,当网络忙闲程度小于该优先级阈值时,分组立即接入信道,反之则进行退避等待,退避过程中首先判断其约束时间,对于未超出约束时间的分组执行自适应退避机制,反之则直接丢弃该分组。该算法主要包含以下2个核心机制。

(1)自适应退避机制。为保证最高优先级业务传输的实时性,对最高优先级分组不执行退避算法,生成即发送,而其他优先级业务则根据信道忙闲程度决定是否执行退避算法,为不同优先级业务设定不同的竞争窗口调整方式,其大小根据网络负载程度和优先级动态变化。

(2)分组时间约束机制。若分组经过长时间退避等待,其所包含的信息已经过时,失去传输的必要,所以TC-PAB算法针对不同优先级业务的QoS需求,设置相应时间约束长度,对超出时间约束值仍无法接入信道的分组不再执行退避。

图1　TC-PAB算法基本原理

定义突发占空比为R,表示发送拆分后的突发包所占用信道时间与发送原分组所占用信道时间的比值[14],l表示信道忙闲程度,设信道数为C,i(i=1,2,…,n)表示分组的优先级,j表示分组所处的退避阶段,网络中所有节点的总分组到达率为G。根据泊松分布原理并参考文献[14]的方法,l可由总分组到达率、信道数量和突发占空比来表示

(1)

根据TC-PAB算法思想,构造优先级i分组在第j个退避阶段的竞争窗口长度Wi,j表达式为

(2)

设定各优先级分组的时间约束值为Ti。若优先级i分组已经执行了mi次退避依然不能接入信道,此时分组退避时间大于约束时间,则该分组将被丢弃。

2　建模分析

2.1　退避过程的马尔科夫链模型

令pi表示优先级i的分组到达发送缓冲区队首时需执行退避的概率,ui表示优先级i的分组在约束时间内能够支持的最大重传次数,ψi,j表示优先级i的分组在完成j(j∈[mi,ui])个退避阶段后继续退避的概率。令si(t)表示优先级i的分组在t时刻所处的退避阶段,bi(t)表示优先级i的分组在t时刻退避计数器的值,则三维随机过程(i,si(t),bi(t))构成如图2所示的离散马尔科夫链,其各状态稳态概率为

(3)

由图2可得

(4)

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

qi=1-exp(-λiTu)

(5)

当k=0时,将j(j∈[0,ui-1])代入式(4)中,可得bi,j,0(j∈[1,ui])的表达式

(6)

令Bi表示优先级i的分组离开发送队列(接入信道或者被丢弃)的概率,根据图2中状态转移过程和式(6),可得

(7)

由式(4)中的第3式和式(7)可得

(8)

图2　优先级i分组退避状态的三维马尔科夫链模型

(9)

根据式(8)和式(9)可以求得图2中每个状态的取值。

2.2　阈值求解

对所有分组进行RS-turbo级联的纠错编码[15],使分组具有一定的容错能力。令Nb为分组拆分后的突发包个数,Mb为恢复原分组所需最少的突发包个数。

定义pb为单个突发包成功接收的概率,根据泊松分布公式易得

(10)

根据纠错编码机制原理,可得分组成功传输概率为

(11)

根据系统对各优先级业务最低分组成功传输概率的要求,并联立式(10)、(11)可得各优先级业务的阈值Gi。根据阈值Gi可得

(12)

2.3　时间约束参数求解

令Ti,j表示优先级i分组在经历了j个退避阶段后消耗的平均时长,易得

(13)

优先级i的分组从开始退避到经过j个退避阶段所消耗时间的概率密度函数为

(14)

其概率母函数为

(15)

优先级i的分组从开始退避到经历j个退避阶段时分组剩余约束时间大于0的概率可表示为

(16)

优先级i的分组在经过j(j∈[mi,ui])个退避阶段后依然不能接入信道,且在约束时间之内的概率为

ψi,j=piγi,j-1,j∈[mi,ui]

(17)

根据式(13)～(17),可以求得所有ψi,j值。

3　性能分析

令S为网络吞吐量,指单位时间内信道实际传输的总数据量,表示为

(18)

式中:L为数据包长度;piin表示优先级i分组经过退避和信道检测后接入信道的概率,表达式为

(19)

令E[Di]表示优先级i分组的平均MAC时延,其值为分组到达相应的优先级队列的队首到该分组接入信道所需的时间均值,表示为

E[Di]=E[Ti]Tσ

(20)

式中:E[Ti]表示优先级i的分组成功传输所需的平均时隙数,表示为

(21)

4　仿真分析

下面利用OMNeT++仿真平台对TC-PAB算法的性能进行仿真分析。根据机载自组网的实际需求,这里对TC-PAB算法设定4个优先级业务,其中优先级1为最高优先级,其分组到达率固定为50包/s,优先级2、3、4的分组到达率之比为1∶3∶6,综合考虑各优先级业务的QoS需求,设定优先级1、2、3的最低分组成功传输概率分别为99%、90%、80%,其他参数设置见表1。设置仿真场景大小为500 km×500 km×10 km,所有节点在该场景中的随机分布,每个节点随机选择目的节点通信,MAC层采用IEEE 802.11协议。其他主要仿真参数设置见表2。

首先对TC-PAB算法的性能和数学模型进行验证。不同网络负载下的竞争窗口数量、平均MAC时延,以及吞吐量的理论计算及仿真结果如图3所示。由图3a可以看出,在信道忙闲程度相同的情况下,由于优先级的不同,所选取的竞争窗口数

表1　各优先级参数设置

表2　仿真参数设置

呈现不同的梯度,从而为不同优先级的分组提供相适应的QoS支持。由图3b可知,当网络处于轻负载时各优先级的平均MAC时延均较低;在重负载时优先级1业务时延不变,平均MAC时延在5 ms以内,其余各优先级分组的时延随网络负载的增加而增加,最终趋于各优先级相应的约束时间。由图3c可以看出TC-PAB算法在负载增大时能够使吞吐量保持相对稳定。由图3可知,TC-PAB算法的理论值和仿真值基本一致,证明建模分析准确有效。

(a)网络负载对各优先级竞争窗口长度的影响

(b)网络负载对各优先级平均MAC时延的影响

(c)网络负载对吞吐量的影响图3　网络负载对TC-PAB算法性能的影响

下面通过仿真实验对TC-PAB算法、BEB算法、EDCA算法[10]和PAB算法[14]的性能进行对比,其中EDCA算法包含4种优先级业务类别,分别是语音(Voice,VO)、视频(Video,VI)、尽力而为(Best-effort,BE)以及背景(Back-ground,BK)业务,对PAB算法也设定4个优先级,仿真实验结果如图4、图5所示。由图4可知,相比PAB和EDCA,TC-PAB算法中虽然低优先级业务的QoS保障能力较差,但能够为高优先级业务提供严格的QoS服务。由图5可知,相比BEB、EDCA和PAB,TC-PAB算法在网络负载较大时能够使网络吞吐量保持相对稳定,具有明显的性能优势,原因在于该算法通过限制低优先级分组接入,把网络中的冲突降到可控程度。

(a)TC-PAB算法与BEB和EDCA算法的对比

(b)TC-PAB算法与PAB算法的对比图4　平均MAC时延性能分析及对比

图5　吞吐量性能对比

综合以上仿真结果,可以得到以下结论:①TC-PAB算法的理论和仿真结果吻合,证明了理论推导的正确性;②当网络处于轻负载时,TC-PAB算法中低优先级分组也可以获得较好的QoS;③当网络负载加重时,低优先级的分组进入退避阶段,限制其接入信道,将信道中的冲突维持在可控范围内,从而为高优先级的分组提供严格的服务;④对比BEB、EDCA和PAB,TC-PAB算法能够为高优先级业务提供更好的服务,并使得网络吞吐量性能保持稳定。

5　结　论

本文为机载自组网MAC协议设计了一种带有时间约束的多优先级自适应退避算法,针对机载自组网多优先级业务并存的特点,一方面对不同优先级业务设定不同的竞争窗口调整方式,在重负载时通过限制低优先级业务接入信道来保证高优先级业务的传输;另一方面为各优先级分组设定相应的时间约束机制,对于超出约束时间的分组直接进行丢弃,提高了分组传输的实时性。研究结果表明,本文算法能够使网络性能保持相对稳定,并且根据网络负载情况为不同优先级业务提供相适应的QoS保障。本文算法对机载自组网MAC协议的研究与应用具有一定的参考价值。

参考文献:

[1]KWAH K J, SAGDUYU Y, YACKOSKI J. Airborne network evaluation: challenges and high fidelity emulation solution [J]. IEEE Communications Magazine, 2014, 52(10): 30-36.

[2]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.

[3]梁一鑫, 程光, 郭晓军, 等. 机载自组网体系结构及其协议栈研究进展 [J]. 软件学报, 2016, 27(1): 96-111.

LIANG Yixin, CHENG Guang, GUO Xiaojun, et al. Research progress on architecture and protocol stack of the airborne network [J]. Journal of Software, 2016, 27(1): 96-111.

[4]CHENG B N, FREDERICK J. Design considerations for next-generation airborne tactical networks [J]. IEEE Communications Magazine, 2014, 52(5): 138-145.

[5]BUCHTER K D. Availability of airborne ad-hoc communication network in global air traffic simulation [C]∥2016 10th International Symposium on Communication Systems, Networks and Digital Signal Processing. Piscataway, NJ, USA: IEEE, 2016: 7573927.

[6]WAN Y, KAMESH N, ZHOU Y, et al. A smooth-turn mobility model for airborne networks [J]. IEEE Transactions on Vehicular Technology, 2013, 62(7): 3359-3370.

[7]XU D H, ZHANG H Y, ZHANG B, et al. A priority differentiated and multi-channel MAC protocol for airborne networks [C]∥Proceedings of 2016 8th IEEE International Conference on Communication Software and Networks. Piscataway, NJ, USA: IEEE, 2016: 64-70.

[8]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.

[9]毛建兵, 毛玉明, 冷鹏, 等. 支持QoS的IEEE 802.11 EDCA性能研究 [J]. 软件学报, 2010, 21(4): 750-770.

MAO Jianbing, MAO Yuming, LENG Peng, et al. Research of the QoS-supporting IEEE 802.11 EDCA performance [J]. Journal of Software, 2010, 21(4): 750-770.

[10] 李瑞芳, 罗娟, 李仁发. 适于无线多媒体传感器网络的MAC层退避算法 [J]. 通信学报, 2010, 31(11): 107-116.

LI Reifang, LUO Juan, LI Renfa. Backoff algorithm in MAC layer for wireless multimedia sensor networks [J]. Journal on Communications, 2010, 31(11): 107-116.

[11] 赵庆敏, 钱雷, 熊镝. 基于避免拥塞的优先级退避算法 [J]. 吉林大学学报, 2013, 43(6): 1072-1075.

ZHAO Qingmin, QIAN Lei, XIOANG Di. High priority backoff algorithm based on congestion avoidance [J]. Journal of Jilin University, 2013, 43(6): 1072-1075.

[12] SYED I, SHIN S H, ROH B H, et al. Performance improvement of QoS-enabled WLANs using adaptive contention window backoff algorithm [J]. IEEE Systems Journal, 2017, doi: 10.1109/JSYST. 2017. 2694859.

[13] 卓琨, 张衡阳, 郑博, 等. 一种优先级区分的机载无线网络MAC层自适应退避算法 [J]. 航空学报, 2016, 37(4): 1281-1291.

ZHUO Kun, ZHANG Hengyang, ZHENG Bo, 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.

[14] YANG T, GUO C X, ZHAO S W, et al. Channel occupancy cognition based adaptive channel access and back-off scheme for LTE system on unlicensed band [C]∥ IEEE Wireless Communications and Networking Conference.Piscataway, NJ USA: IEEE, 2016: 7565014.

[15] 肖雷蕾, 张衡阳, 毛玉泉, 等. 一种区分优先级自适应抖动的媒质接入控制协议 [J]. 西安交通大学学报, 2015, 49(10): 123-129.

XIAO Leilei, ZHANG Hengyang, MAO Yuquan, et al. An adaptive jitter based media access control with priorities [J]. Journal of Xi’an Jiaotong University, 2015, 49(10): 123-129.