一种基于多层优先级和差分服务机制的CSMA/CA改进算法

陈 涛1，朱马锋

(1.成都理工大学，四川 成都 610000；2.重庆邮电大学，重庆 400065)

·计算机软件理论、技术与应用·

一种基于多层优先级和差分服务机制的CSMA/CA改进算法

陈 涛1，朱马锋2

(1.成都理工大学，四川 成都 610000；2.重庆邮电大学，重庆 400065)

针对CSMA/CA算法的回退指数变化固定、对第2次CCA检测信道为忙时的处理不当这2个不足，提出一种基于多层优先级和差分服务机制的时隙CSMA/CA算法。通过优先级设定不同的回退指数BE，采用CCA2失败时再执行1次CCA的方法来克服以上2个不足。OPNET仿真结果表明，该算法在吞吐量、网络时延、成功接入信道概率方面优于原CSMA/CA算法。

时隙CSMA/CA；多层优先级；差分服务机制；OPNET

IEEE802.15.4 标准定义了媒体访问层(MAC)和物理层[1]，CSMA/CA算法是媒体访问层的关键技术之一[2]。对于CSMA/CA算法，学者进行了不断地研究[3-9]。文献[3]对执行第2次CCA做了重大分析，增加了CW值，使得当第2次CCA检查信道为忙时，不是立即重新执行算法，而是再执行1次CCA，增大了信道的接入概率。文献[6]通过改变BE的值来提高接入概率。文献[7]采用帧裁剪和优先级调度策略，使高优先级的数据在执行CCA时只需要1次，而低优先级的数据需要2次，这有效地提高了包成功发送的概率。文献[8]采用竞争窗口和回退指数的差分思想来优化时隙CSMA/CA算法。

通过这些文献可知，现有的基于优先级和差分服务机制的CSMA/CA算法只是针对不同的数据类型的优先级，在同一个数据类型中，并没有再次引入优先级和差分服务机制。例如：文献[8]认为来自安全系统和医学设备的传感器节点的数据要比来自TV、冰箱等普通设备的数据具有高的优先级；文献[10]认为命令帧具有高优先级，数据帧为低优先级。这些优先级都是针对不同的帧类型，都是在执行CSMA/CA算法之前由上层指定，而不是在算法过程中动态分配。本文对执行CSMA/CA算法中发生碰撞的情况做了详细分析，并在此基础上引入优先级和差分思想以解决原CSMA/CA算法存在的2个主要缺陷。

1 时隙CSMA/CA机制

1.1时隙CSMA/CA机制

IEEE802.15.4定义了一种超帧结构，如图1所示。超帧结构包括信标帧、活跃部分和非活跃部分[1]。根据属性macBeaconframeOrder(BO)、macSuperframeOrder(SO)和aBaseSuperframeDuation的值按照式(1)来确定信标的周期BI(beacon interval)和超帧的活动部分长度SD(superframe duration)。

BI=aBaseSuperframeDuation×2BO;

SD=aBaseSuperframeDuation×2SO;

0≤SO≤BO≤14。

(1)

在活跃部分，IEEE802.15.4协议提供了一种GTS机制，在GTS内节点无须竞争，这些GTS有网络协调器分配。

图1 超帧结构简图

所有节点进行信息传输之前都要使用CSMA/CA算法进行信道的竞争。CSMA/CA算法涉及3个重要参数：竞争窗口CW、回退指数BE和回退次数NB。步骤1：对网络参数(NB、CW、BE)进行初始化。步骤2：在[0,2BE-1]之间随机选择几个作为退避周期数。步骤3：在退避周期边界处执行CCA。步骤4：如果这时信道为空，就将CW的值减1，判断其是否为0，若为0则竞争成功，若不为0返回步骤2；如果信道为忙，就将CW置2，NB和BE加1，但是必须保证BE为BE+1和最大回退指数aMaxBE中的最小者。步骤5：判断NB有没有达到最大重传次数，如果达到则竞争失败，如果没有则返回步骤2。流程如图2所示。

图2 CSMA/CA算法流程图

1.2 CSMA/CA机制的缺陷

时隙CSMA/CA算法受4个变量影响：最小回退指数(macMinBE)、最大回退指数(aMaxBE)、初始值CW和最大回退次数(macMaxCSMABackoffs)。这4个参数的改变会影响CSMA/CA算法的性能，例如平均网络时延会随着macMinBE的增大而变大[11]；因此，选取合适的参数可以优化算法的性能。其不足主要体现在以下2方面。

1)回退指数变化固定。在执行CSMA/CA算法的过程中回退指数成线性变化，每次检测到信道为忙就会将回退指数加1，但是这样往往不适应一些特殊情况；因为当网络状态已经很好时，随着回退次数的增加，仍需要回退过多的周期，这样无疑浪费了资源，增大了网络的时延。另外，对于本文提到的具有优先级的帧，回退指数仍按照线性变化，这样就不利于具有优先级帧的优先发送。

2)对第2次CCA检测信道为忙时的处理不当。在使用CSMA/CA算法中，CCA信道必须连续2次都为闲时才能发送数据，这2次CCA称为CCA1和CCA2。当出现CCA1信道为闲、CCA2信道为忙时，原算法就会重新开始执行，直到连续2次CCA检测为闲时才能发送数据，这无疑浪费了1次CCA信道为闲的机会，增加了执行CCA的次数。

CCA2检测为忙的情况主要由2个原因[12]造成。 1)CCA2检测与数据帧发送碰撞。当执行CCA2时，这时刚好有数据发送，所以信道检测为忙。2)CCA2检测与确认帧(ACK)的碰撞。当执行CCA1时，刚好有数据发送完毕正等待确认帧的到来，这时信道为空，当执行CCA2时，刚好确认帧开始发送，这时CCA2检测为忙。如图3所示，假设此时网络中有3个节点：Note1、Note2、Note3。Note1 连续执行2次CCA，检测信道都为闲，然后开始发送数据，在Note1发送数据期间，Note2 执行CCA，检测信道为忙。等Note1 发送完数据，要等待确认帧的发送，此时Note3 执行CCA1，检测信道为闲；但等Note3 执行CCA2时刚好确认帧开始发送，检测信道为忙。对于第1种情况因为不知道数据帧长度所以不确定接下来几个时隙后信道空闲；但是对于第2种情况，因为ACK只有1个时隙，所以只要等2个时隙后信道就为闲，此时就可以发送数据。

图3 由ACK 引起的CCA2 信道为忙的示意图

2 基于帧优先级、内部优先级和差分思想的CSMA/CA算法

优先级服务机制是指被网络标记的具有高优先级的数据帧优先发送。优先发送可以通过改变竞争窗口、回退指数来实现。优先级的大小由MAC层或者上层设置。

差分服务机制分为竞争窗口差分服务机制和回退指数差分服务机制[13]。竞争窗口服务机制是指对于不同的优先级采用不同的竞争窗口大小，即执行不同的CCA；回退指数差分服务机制是指对于不同的优先级采用不同的回退指数。

2.1差分服务机制

文献[10]以命令帧作为高优先级，本文称之为外部优先级，其参数用macMinBEHP、macMaxBEHP和CWHP表示；数据帧作为低优先级，本文称之为内部优先级，其参数用macMinBELP、macMaxBELP和CWLP表示。为表示数据帧内部的优先级，即执行CCA时第1次信道为空，第2次为忙的节点，本文用macMinBELHP、macMaxBELHP、CWLHP和macMinBELLP、macMaxBELLP、CWLLP分别表示内部高优先级和内部低优先级数据。对于数据帧内部的优先级并不是由MAC层或者上层指定，而是在运行CSMA/CA算法时，执行CCA2后由算法临时指定，其优先级作用时间仅仅为此节点传输信息结束，在以后的竞争中它并不一定具有内部高优先级；但是从CSMA/CA算法来看它好像和外部优先级的数据帧一样由MAC或者上层指定，如图4所示。

图4 优先级和差分服务机制

文献[10]设定了不同的仿真参数来验证它们对网络性能的影响，表明在没有隐藏节点的情况下，当macMinBEHP=macMinBELP=2，macMaxBEHP= macMaxBELP =5，CWHP=2，CWHP=3时较合理。文献[12]分析并验证了当执行1次CCA时对系统性能的提高。结合对内部优先级的考虑，本文对参数的设置如表1所示。对于竞争窗口CW，值越大表示优先级越高，值越小表示优先级越低，所以具有外部优先级的帧优先级最高，然后是具有临时内部优先级的帧，最后是普通帧。

表1 网络参数

2.2改进的CSMA/CA算法步骤

由以上分析可知，帧优先级由MAC层或者上层指定，对于外部优先级的帧来说，优先发送的权利可以通过改变竞争窗口次数，即改变CCA检测次数来达到，在此种情况下，只需要执行1次CCA，同时不减少退避周期，从而提高外部优先级帧的接入信道概率。对于内部优先级的数据帧，可以通过改变其原先的优先级来达到其优先竞争的目的，从而保证执行CCA1信道为空后，暂时赋予此节点有内部优先级。另外，改变回退指数BE可以改变其接入信道的概率，对于优先级高的可以减少回退指数，优先级低的可以增大回退指数，从而区分不同优先级的信道竞争情况。对于第2种缺陷，如果是和确认帧碰撞，因为已经知道ACK的长度，节点只需延时1个时隙周期即可；如果是和数据碰撞，因为无法确定数据的长度，所以只能随机延时几个时隙周期。算法流程图如图5所示。

步骤1：判断是否为优先级包。若是，执行步骤2，若不是执行步骤3。

步骤2：初始化NB=0，CW=1，然后执行步骤4。

步骤3：初始化NB=0，CW=3，然后执行步骤4。

步骤4：初始化BE=macMinBE，然后定位退避周期边界。

步骤5：在0～2BE-1之间随机选择几个作为退避周期。

步骤6：在退避边界进行信道检测CCA。如果信道为空闲，则进入步骤7；如果信道忙，则进行步骤8。

步骤7：将CW减1，然后判定CW是否为0。若为0，成功；否则回到步骤5。

步骤8：判断是否为优先级包。若是执行步骤12；若不是执行步骤9。

步骤9：判断CW值是否为2。若是执行步骤10；若不是执行步骤11。

步骤10：将CW值减1，然后退避1个周期，执行步骤6。

图5 改进算法流程图

步骤11：判断CW的值是否为1。若是执行步骤13；若不是执行步骤14。

步骤12：CW=1，NB值加1，BE不变，然后执行步骤15。

步骤13：CW=2，NB值加1，BE=min(BE+1,aMaxBE)，然后执行步骤15。

步骤14：CW=3，NB值加1，BE=min(BE+1,aMaxBE)，然后执行步骤15。

步骤15：判定NB是否大于最大退避次数macMax-CSMABackoff。如果大于，则失败；否则回到步骤5。

3 仿真

为比较方便，本文提出的基于外部优先级和内部优先级的差分CSMA/CA算法用PP-CSMA/CA表示，对于基于外部优先级的CSMA/CA算法用P-CSMA/CA表示。用OPNET[14-15]网络仿真软件进行仿真。

图6 吞吐量与普通节点的关系

图6显示的是网络节点数目对吞吐量的影响。可以看出，随着网络中节点数目的增多，吞吐量的变化并不明显。无论网络负载是由多少个节点产生，即10、20、30、50或者100个节点，网络的吞吐量仅与载荷G有关；但是，对于一个给定的网络负载G，每个节点产生的载荷与节点数成反比。如果网络中的载荷保持不变，节点个数对于网络的吞吐量几乎没有影响。增加了优先级机制的算法要优于原算法。

图7 成功接入信道的概率与网络负载G的关系

图7示出的是负载与成功接入信道概率的关系。可以看出，引入优先级机制的算法要优于原算法， PP-CSMA/CA算法的信道接入概率要优于P-CSMA/CA和原CSMA/CA算法。PP-CSMA/CA算法有效地考虑了发送碰撞的各种情况，特别是对CCA2发送碰撞的情况做了重点的分析，并对原算法出现的2个主要缺陷做了相应的改进，从而增加了节点接入信道的概率。当节点少的时候，成功接入概率相差不大，随着负载的增加，其相差增大。这是因为，当负载小的时候，网络还没有达到饱和状态，信道接入成功率都很高，当负载较大时，网络达到饱和状态，此时具有优先级的数据包因为其竞争窗口以及回退指数较小，就会优先竞争到信道，其成功接入信道的概率就会增大。

图8示出的是网络负载对平均网络时延的影响，其中虚线表示命令帧网络时延，实线表示数据帧网络时延。对于数据帧时延，原CSMA/CA和PCSMA/CA算法大致一样，这是因为外部优先级只是针对具有优先级的命令帧，并不对其他自身有影响。相同原因还表现在当引入内部优先级时对命令帧的影响很小上。另外，P-CSMA/CA算法在时延上要优于其他2种算法。当负载较小时，时延相差不是很大，当负载较大时，其相差会增大。

图8 平均时延与网络负载的关系

4 结论

本文在分析了已有的基于优先级和差分服务思想的CSMA/CA算法缺点的基础上，提出一种基于外部、内部优先级和差分服务的CSMA/CA算法，通过选取合适的网络参数、改变竞争窗口的大小和回退指数来区分不同的优先级，以达到良好的网络效果。仿真验证的结果表明，在吞吐量、网络时延和节点成功接入信道的概率方面，本文算法有很好表现。下一步研究重点是节点能耗和根据网络状况动态调整网络参数方面。

[1]IEEE-TG15.4.Part 15.4: Wireless Medium Access Control(MAC)and Physical Layer(PHY)Specification for Low Rate Wireless Personal Area Networks(LR-WPANs)[S].2006.

[2]RAMACHANDRAN I,DAS K A,ROY S. Analysis of the Contention Access Period of IEEE802.15.4 MAC[J].ACM Trans on Sensor Networks,2007,3(1):1-29.

[3]CHI-MING WONG,RUER-LUNG LAI , I-TING LAI. An Enhanced Carrier Sensing Algorithm for IEEE802.15.4 Low-Rate Wireless Sensor Networks[J].Industrial Electronics & Applications (ISIEA),2010,3(5):10-15.

[4]Jianhua He,Zuoyin Tang,Hsiao-Hwa Chen,et al. An Accurat and Scalable Analytical Model for IEEE802.15.4 Slotted CSMA/CA Networks[C]//IEEE Transactions on Wireless Communication. Singapore： IEEE, 2007:899-904.

[5]LEE B H , WU H-K . Study on a Delayed Backoff Algorithm for IEEE802.15.4 Low-Rate Wireless Personal Area Networks[J].The Institution of Engineering and Technology(IET)Communications,2009,3(7):1089-1096.

[6]吉城，徐友云，郑宝玉.基于IEEE802.15.4 退避算法的改进机制[J].信息技术,2008 (8):8-12.

[7]KIM T,CHOI S. Priotity-based Delay Mitigation for Event Monitoring IEEE802.15.4 LR-WPANs[J]. IEEE Communications Letters,2006,10(3):213-215.

[8]KIM M,KANG C H. Priotity-based Service-differention Scheme for IEEE802.15.4 Sensor Networks in Nonsaturation Environments[J]. IEEE Transations on Vehicular Technology,2010,59(7):3524-3535.

[9]NDIH E D N,K N De M G. An Analytical Model for the Contention Access Period of the Slotted IEEE802.15.4 with Service Differentiation[C]// Communications,2009(ICC’09),IEEE International Conference on. Dresden： IEEE, 2009:1-6.

[10]ANIS KOUBAA,MARIO ALVES,Bilel NEFZI,et al. Improving the IEEE802.15.4 Slotted CSMA/CA MAC for Time-Critical Events in Wireless Sensor Networks[C]//Proceedings of the Workshop of Real-time Networks. Shenzhen： IEEE, 2006:1-6.

[11]ALVER A K M, TOVAR E. A Comprehensive Simulation Study of Slotted CSMA/CA for IEEE802.15.4 Wireless Sensor Network[C]//The 6thIEEE International Workshop on Factory Communication Systems(WFCS2006). Torino： IEEE, 2006,183-192.

[12]PATRO R K, MANIK M, RAINA G V,et al. Analysis and Improvement of Contention Access Prtocol in IEEE802.15.4 Star Network[C]//Mobile Adhoc and Sensor Systems, IEEE Internatonal Conference on. Pisa： IEEE, 2007: 1-8.

[13]陈金，樊晓平，刘少强,等. 非饱和状态下时隙CSMA/CA机制改进与性能分析[J]. 计算机工程与应用, 2012,48(30):140-146.

[14]PETR JURCIK, ANIS KOUBAA,MARIO ALVES. A Simulation Model for the IEEE 802.15.4 Protocol: Delay/Throughput Evaluation of the GTS Mechanism[C]// The 07th IEEE International Symposium on Modeling,Analysis and Simulation of Computer and Telecommunication Systems(MASCOTS’07). Istanbul：IEEE，2007：109-116.

[15]吴志玲，靳鸿，冯彦君. 基于OPNET 的信道接入协议网络性能研究[J]. 伺服控制, 2012 (2):79-81.

(编校：饶莉)

AnImprovementAlgorithmofSlottedCSMA/CAwithServiceDifferentiationandPriorityMechanism

CHEN Tao1,ZHU Ma-feng2

(1.ChengduUniversityofTechnology，Chengdu610000China；2.ChongqingUniversityofPostsandTelecommunications,Chongqing400065China)

There are two shortages exiting in CSMA/CA: the backoff exponent(BE) increases linearly and it perform not well in the case of CAA2 detected being busy.In this paper, a kind of CSMA/CA algorithm with multi-level priority strategy and service differentiation mechanisms is proposed. Two problems are overcome with different BE based on priority strategy and performing the CAA again after the CCA2 failed slot. Results of experiment on OPNET platform show that the proposed algorithm performs better than the original one in aspects of the throughput, network delay and the probability of successfully access to channel.

slotted CSMA/CA; multi-level priority; service differentiation mechanism; OPNET

2014-04-19

国家自然科学基金“基于物联网技术的呼吸、脉搏异变及跌落的实时检测与报警的关键技术研究”(61171190)。

陈涛(1988—)男，硕士研究生，主要研究方向为网络通信。E-mail:1991920158@qq.com

TP212;TN929.5

：A

：1673-159X(2015)02-0016-6

10.3969/j.issn.1673-159X.2015.02.004