多优先级无时隙CSMA/ CA算法研究

李 亮，张君利，杨 侃

(中国兵器工业集团第214研究所，江苏 苏州 215163)

多优先级无时隙CSMA/ CA算法研究

李 亮，张君利，杨 侃

(中国兵器工业集团第214研究所，江苏 苏州 215163)

IEEE802.15.4的无时隙CSMA/CA算法没有对数据进行分流的能力，基于此，提出了一种针对带有多优先级数据处理的无时隙改进算法。改进后的算法会对高优先级数据采取减少退避计数器计数和碰撞窗宽的策略，对不同优先级的待发数据采取相应的处理方式。算法通过接入网络延时和网络吞吐量来反映数据在网络中的优先级别；同时引入数据发送的接入概率，提出接入-吞吐积概念作为评价算法优劣的标准。引用马尔可夫链模型对算法进行了分析，并使用MATLAB软件进行仿真。

接入-吞吐积；退避次数；退避指数；碰撞窗宽；无时隙

0 引言

无线传感器技术发展迅猛，标准CSMA/CA算法已不能满足数据多元化要求。CSMA/CA算法是IEEE802.15.4的MAC协议层核心算法。短距离无线通信协议为了避免信息碰撞，在MAC层设计了CSMA/CA算法，而有线通信协议则采用CSMA/CD算法，具体介绍可参见文献[1]。CSMA/CA算法全称为：带冲突避免的载波侦听多路访问。顾名思义，该算法的核心即在发送数据前延时一段时间再发送数据，以避让其它节点发送的数据，从而避免冲突，CSMA/CA的执行步骤和介绍详见文献[2]和文献[3]。

标准的CSMA/CA算法没有数据的优先级分区服务，网络节点对要发送的数据不分流，所以有学者提出了基于优先级的CSMA/CA算法作为对CSMA/CA算法的优化和改进。在CSMA/CA算法中有3个重要参数，分别为退避指数BE、退避次数NB和碰撞窗宽CW，参见文献[2]。对CSMA/CA算法的改进将从这3个参数入手，以实现多优先级的数据分流。每一种优先级都与它相应的参数BE、CW和最大退避次数相匹配，它们是一一映射的。本文引入了常用的马尔可夫链模型，引入两个重要的变量——吞吐量和接入延时。本文建立的模型放弃了汇聚节点概念，设定每个节点都是平等的，这两个物理量作为权衡数据优先级的重要依据，使用数学软件MATLAB对本文模型同标准CSMA/CA模型进行仿真验证，从而得出相应结论。

1 无时隙CSMA/CA算法

CSMA/CA算法分为时隙和无时隙两类，两种方式的根本区别在于是否有同步机制，有时隙的算法含有同步机制，参见文献[1]。本文对无时隙CSMA/CA算法进行研究。

无时隙CSMA/CA算法工作机理：当网络节点准备发送数据时，先会延时一段时间，检测信道是否空闲。若判断信道为空闲，则发出信号RTS，RTS信号包括发射端的地址、接收端的地址、下一笔数据将持续发送的时间等信息。接收端接收到RTS信号后，将响应短信号CTS，CTS信号包含RTS记录的持续发送时间。当发射端接收到CTS包后，随即开始发送数据包。接收端接收到数据包后，检测校验包中的CRC数值是否正确。若正确，接收端响应ACK包，告知发射端已成功接收数据。发射端长时间没有收到接收端的ACK包时，将认为包在传输过程中丢失，会重新发送包[1]。

CSMA/CA算法依赖的参数有BE、NB和CW，其中BE为退避指数，退避计数器的计数值由BE决定；NB为退避次数，用来记录待发送数据退避的次数；CW为碰撞窗宽，表明节点发送数据前监测信道(CCA)空闲的次数[2-3]。

如果有数据要发送，网络节点选择无时隙模式和非电池延长模式，参数初始化BE=MaxMinBE，CW=2，NB=0。由于没有时隙，所以算法不需要定位时隙边缘。节点一旦有数据要发送则立刻执行退避算法。节点延时一段时间再执行信道检测，等待的那段时间称为退避时间，退避时间由退避计数器确定，退避计数器的计数值backoffcounter从0到2BE-1之间的整数中随机选出。随后每隔一个单位时长退避计数器减1，直到退避计数器减至0则表示退避时间已满。开始执行CCA，如果CCA的结果表明信道空闲则判定CW是否为0，如果不为0，数据将再次延时一段时间后检测信道是否空闲。如果信道仍然空闲且此时CW为0时则发送数据；如果信道忙，则执行CW=0，NB=NB+1，即数据退避次数需要加1，BE=min{BE+1,macMaxBE}(下次退避时间就有可能长一些)。最后检测NB，如果NB已经大于最大退避次数，则舍弃发送该数据；否则就使用更新后的参数执行退避，检测信道后再次尝试发送数据，直到放弃数据发送或数据发送成功。时隙CSMA/CA算法流程如图1所示。

图1 时隙CSMA/CA算法流程

2 多优先级CSMA/CA算法

网络平均吞吐量和平均接入延时概念：吞吐量Sthr指网络中的所有节点单位时间成功发送的数据总数[4]，网络的平均吞吐量S则是总数据量除以网络的节点总数。

(1)

M表示整个网络中的发送节点数。

接入延时T指数据从发出到发送成功所用的时间[5]。平均接入时延Tave是所有已发送的数据包平均接入延时(单位为s/bit)。

(2)

网络节点发送数据时，总是期望高优先级数据能够先发送，低优先级数据避开高优先级数据。本文建立的多优先级无时隙CSMA/CA模型将对参数BE、NB和CW进行多选化处理，因而高优先级数据的接入延时更短，在宏观上反映为：如果网络中只有一种优先级别的数据传输，那么网络的平均数据吞吐量将会提高。标准的无时隙CSMA/CA算法参数CW为1，此算法却设定没有优先级的数据参数CW为2；而对于优先级更高的数据甚至可以将BE固定为一个常量，在统计学上表现为退避时长的期望值一定，优先级最高的数据是前面两种情形的叠加。第NB次退避时间的期望值Tbackoff为：

(3)

Tslot表示一个单位时长，BE是关于NB的函数，Tbackoff是关于BE的函数，且具有单调递增特性。图1为多优先级策略的CSMA/CA算法流程，设优先级1数值化为Q1，Q1=1表示数据具有优先级别1的属性，Q1=0表示数据不具有优先级别1的属性；优先级2可以数值化为Q2，Q2=0表示优先级别2的最低属性，Q2=k为优先级2的最高属性。所以数据总的优先级Q作如下定义：

(4)

由公式(4)可得Q={0,1,k,k+1…k2,k2+1}，其中Q=k2+1为最高级，Q=0为最低级。在节点要发送的前后两组数据时间间隔很长的情形下，最大退避次数将对数据发送成功率产生较大影响，而对网络吞吐量的影响则越来越小，所以本算法又提出了重要级概念。重要级旨在提高某些特定数据的发送成功率，设重要级P={0,1}。

多优先级策略的无时隙CSMA/CA算法流程如下：当有节点要发送数据时，首先确定待发送数据的优先级，若Q1=1，则执行优先级1(令CW=1)，若Q2=1，则执行优先级2(即BE=C固定)。如要发送的数据P=1，则使得MaxBackoffs+1，这样可以使得最大退避次数多1，以保证特定的数据有高于普通数据的发送成功概率。此处的1理解为一个偏移量，不一定为常数，可以设偏移量为IMP(函数)，而重要级别则可以反映在IMP上。不等式NB

对于CSMA/CA算法常常采用马尔可夫链模型来分析，图2为马尔可夫链模型[6]，前人对其进行了细致而严密的分析，在此处由于篇幅限制不作过多推导，只引用若干结论。

数据成功发送的概率(即接入概率)设为γ，第一次执行CCA信道为忙碌的概率为a，第二次执行CCA信道为忙碌的概率为b，节点个数为n，当数据能够退避的最大次数为m时，令G=1[7]。文献[6]指出网络吞吐量和接入延时成反比关系，即吞吐量越高接入延时就越短，数据的接入时延越短说明数据发送得越快[8]。所以从网络的数据吞吐量来看，在同等条件下希望高优先级数据的传输吞吐量越高越好。

图2 马尔可夫链模型

3 仿真结果

基于下面3个假设进行仿真：①发送的数据需要回复信息，在仿真时也将回复时间计算在内，且发送数据的时间为整数倍单位时长；②不存在暴露节点问题和隐藏节点问题，认为在一定范围内的所有节点都可以相互检测到；③每一个节点都有数据发送，数据长度和相邻数据之间的间隔满足泊松分布。

如图3(a)和图3(b)所示，BE遵循标准CSMA/CA算法规则，每一次退避后自加1，直至达到最大退避指数macMaxBE为止，保持不变，本文称为标准模式。MaxNB表示最大的退避次数，图3(a)中每条曲线对应一个参数CW值，图3(b)～图3(d)可以类比于图3(a)。图3(a)中参数MaxNB=1，图3(b)中参数MaxNB=2，在这两种情形下反映CW对于网络平均吞吐量的影响。图3(c)和图3(d)分别和图3(a)和图3(b)类似，不同之处只是将BE=C固定，在仿真中令BE=2固定，即BE值不会更新，图3(c)中参数MaxNB=1，图3(d)中参数MaxNB=2。

由此可知，在其它条件相同的情况下，CW越小，网络的平均吞吐量就越大，待发送数据的平均时延就越小。因为CW=1代表只要检测到信道空闲就立即发送数据，而CW=2则必须连续两次检测信道均为空闲才会发送数据。

如图4(a)～图4(d)所示，仿真在其它外部因素完全相同的条件下，对BE=2固定和标准CSMA/CA算法处理BE(下文称之为标准模式)这两种方式进行平均吞吐量对比。在节点数相同时，将BE=2固定，其网络的平均吞吐量得到了大幅提升。当然这样付出的代价就是会使得节点功耗加大，因为BE=2固定，会使待发送数据的平均退避时间缩短，节点执行CCA次数明显增加，从而导致节点功耗加大[9]。为兼顾功耗和网络平均吞吐量，直接的方法就是适当减少执行CCA的次数[10]。可以将BE=C中的参数C定高一些。注意参数C的值应该比标准模式下BE的平均值小。

图3 标准模式及BE固定模式

图4 平均吞吐量对比

图5为BE=C固定模式下的平均吞吐量与节点数仿真，不同的C值对应不同的函数曲线图，从图中可以看到网络的平均吞吐量随C的增大而减少，C越大则退避时间期望值越大，直接导致接入延时变长，其宏观表征为网络平均吞吐量降低。在标准模式下，BE的初始值越大则接入延时越大，平均吞吐量越小[11]，道理同BE=C的固定模式是相同的。

图6为不同的最大退避次数MaxNB的数据平均接入时延比较，由图可知，最大退避次数MaxNB越大则数据的平均接入时延越长，待发送数据的接入时延越长网络的平均吞吐量越低，所以最大退避次数越大网络平均吞吐量则越低。

图7(a)～图7(d)表示待发送数据发送成功率和节点数目之间的函数关系，为其它条件相同而最大退避次数MaxNB不同时进行的比较。从仿真图可以看出，最大退避次数MaxNB越大则待发送数据成功率越高；分别对图7(a)和图7(b)、图7(c)和图7(d)两组仿真图对比，可以发现此时CW对于待发送数据的成功率几乎没有影响，这一仿真结果可以理解。一旦检测到信道忙碌便丢掉数据，立刻准备发送新的数据；如果检测信道忙碌就执行退避过程，一次又一次执行，且每次的退避时间都会变长一些，这个数据就会滞留(仍然有发送出去的可能性)，导致网络的平均吞吐量不如前者，但是有利于提高数据发送的成功率。所以有些时候要权衡网络的平均吞吐量与数据接入概率之间的关系，使二者达到一个平衡。权衡的方法为：在不同的MaxNB下，使数据的接入概率和平均吞吐量减去一个特定值所得的结果相乘，称为接入-吞吐积，最大的那个接入-吞吐积对应的MaxNB即认为是最优的选择。

图5 固定BE=C吞吐量对比 图6 不同MaxNB平均接入时延

图7 发送成功率对比

4 结语

基于优先级的无时隙CSMA/CA算法主要特征为：依据多种优先级和重要级进行数据分区，经过分析和仿真可以看出，在发送数据速率和其它参数一定的情况下，参数BE越小，CW越小，网络吞吐能力越强，数据的平均延时就越短；数据优先级数值Q越大，对应的参数BE数值越小，参数CW越小。在相邻待发送数据间隔时间远远大于数据发送时间的情况下，评价平均接入概率和平均吞吐量的关系，确定最大退避次数MaxNB的方法为计算接入-吞吐积的值，最大接入-吞吐积对应的最大退避次数MaxNB则认为是最合适的。

[1] 谢希仁. 计算机网络 [M].第6版. 北京:电子工业出版社,2013：365-378.

[2]SHAHINFARAHANI.ZigBeewirelessnetworksandtransceivers[M].ElsevierLtd,2008： 47-79.

[3]IEEE-SASTANDARDSBOARD.Wirelessmediumaccesscontrol(MAC)andphysicallayer(PHY)SpecificationsforLow-RateWirelessPersonalAreaNetworks(LR-WPANs)，IEEE802 15.4 [S].IEEEstandardforInformationTechnology, 2006：166-200.

[4]ANISKOUBAA,MRIOALVES,EDUARDOTOVAR.AcomprehensivesimulationstudyofslottedCSMA/CAforIEEE802.15.4WirelessSensorNetworks[J].FactoryCommunicationSystems,IEEEInternationalWorkshopon，2006(5)：183-192.

[5]LKLEINROCK,FATOUBAGI.Packetswitchinginradiochannels:partI-carriersensemultipleaccessmodesandtheirthroughput-delaycharacteristics[J].IEEETransonCommunications, 1975，23(12)： 1400-1416.

[6]RAJAVARAPRASADY,RAJALAKSHMIPACHAMUTHU.AnalyticalmodelofadaptiveCSMA-CAMACforreliableandtimelyclusteredwirelessmulti-hopcommunication[C].InternetofThings(WF-IoT),IEEEWorldForumon，2014：212-217.

[7]HAOWEN,CHUANGLIN,ZHI-JIACHEN,etal.AnimprovedmarkovmodelforIEEE802.15.4slottedCSMA/CAmechanism[J].Journalofcomputerscienceandtechnology,2009,24(3):495-504.

[8]JNI，BTAN，RSRIKANT.Q-CSMA:queue-length-basedCSMA/CAalgorithmsforachievingmaximumthroughputandlowdelayinwirelessnetworks[J].IEEE/ACMTransactionsonNetworking,2012，20(3)： 825-836.

[9]APOORVAJINDAL,KONSTANTINOSPSOUNIS.OntheefficiencyofCSMA-CAschedulinginwirelessmultihopnetworks[J].IEEE/ACMTransactionsonNetworking，2013，21(5)：1392-1406.

[10]KLEE,PMITCHELL,DGRACE.Energyefficientdistributedreservationmultipleaccesswithadaptiveswitchingrequestsforwirelessnetworks[J].IEEETransactionsonWirelessCommunications,2014,13(1):259-267.

[11]RLAUFER,LKLEINROCK.OnthecapacityofwirelessCSMA/CAmultihopnetworks[C].INFOCOM,2013ProceedingsIEEE,2013:1312-1320.

(责任编辑：杜能钢)

李亮(1991-)，男，河北张家口人，中国兵器工业集团第214研究所硕士研究生，研究方向为无线传感器网络技术；张君利(1967-)，女，安徽阜阳人，中国兵器工业集团第214研究所研究员，研究方向为厚膜电路；杨侃(1979-)，男，江苏盐城人，中国兵器工业集团第214研究所高级工程师，研究方向为教学电路设计。

10.11907/rjdk.171022

TP312

A

1672-7800(2017)003-0030-04