基于帧服务时延的拥塞控制算法

马新华， 杨俊清

(西安航空学院 计算机工程系， 陕西 西安710077)

基于帧服务时延的拥塞控制算法

马新华， 杨俊清

(西安航空学院 计算机工程系， 陕西 西安710077)

针对无线传感器网络介质访问控制(MAC)层存在的拥塞问题，提出一种拥塞控制算法。利用IEEE802.15.4协议 MAC层帧服务时延对拥塞指示的有效性，在IEEE802.15.4协议的CSMA/CA算法中增加以帧服务时延为阀值的计时器，并根据计时器的值调整传感器节点的发射速率，可达到对MAC层拥塞进行控制的目的。仿真结果表明，与传统算法相比，网络中有40个节点时，新算法对网络拥塞大约有60%的改善。

介质访问控制;帧服务时延;拥塞控制;无线传感器网络

在现有的无线传感器网络拥塞控制算法中[1-6]，为了提前向下游节点通知拥塞，上游节点使用主动队列管理(Active Queue Management, AQM)[7]来检测拥塞，下游节点在接到拥塞通知后进行相应处理，虽然主动队列管理技术在有线网络中可以相对有效地解决网络拥塞，但在无线传感器网络环境下，网络的拥塞并不表现为队列长度的增长，更多的表现为由于大量节点竞争信道而造成的介质访问控制(Media Access Control, MAC)层拥塞，这种拥塞发生在网络层的拥塞之前，先于网络层拥塞对无线传感器网络的时延产生影响。因此，在有线网络中成熟的拥塞控制技术，在无线传感器网络中并不适用。

为了有效指示无线传感器网络拥塞，本文首先对IEEE802.15.4协议的MAC帧服务时延进行建模，研究MAC帧服务时延作为网络拥塞指示的可行性和有效性，并将结果用于IEEE802.15.4协议中载波监听多路访问/冲突检测(Carrier Sense Multiple Access/Collision Detect, CSMA/CA)算法的改进中。

1 MAC帧服务时延模型

IEEE802.15.4协议是众多无线传感器MAC层和物理层协议中最有影响力的标准[8]，工作在信标使能模式和非信标使能模式下，由于非信标使能模式不使用超帧和信标，信道接入使用非时隙模式的CSMA/CA来实现，这种方式和其他的竞争型MAC协议相同，并不能体现802.15.4特性。信标使能模式采用时隙CSMA/CA机制作为信道接入方式，采用竞争期(Contention Access Period, CAP)和无竞争期(Contention-Free Period, CFP)两种方式进行帧传输，CFP与传统的时分多址(Time Division Multiple Access, TDMA)方式相同，且在实际的应用中以CAP方式为主，因此本文只考虑信标使能模式下的CAP方式。

CAP是IEEE802.15.4信标使能模式下的基本MAC协议，用于超帧的竞争期，在进行帧传输时采用CSMA/CA+确认(Acknowledgement, ACK)方式，任何需要发送的帧都使用时隙的CSMA/CA机制访问信道，在帧传输后，如果在规定时间内未收到MAC层的确认帧，则发送方认为该帧冲突或丢失，该帧会按照二进制指数退避算法进行退避和重传。

图1 TD的时延构成

节点有数据发送时，首先对退避参数进行初始化，计算随机退避时间，退避时间结束后，进行消除信道评估，最后尝试发送数据。如果发生冲突，重新计算随机时间，在退避时间结束后，再次尝试发送数据，这样的过程一直达到最大重试次数C，或者传送此帧成功为止。所以传送的过程中，可能包含多次的冲突。

为计算帧服务时延，以随机变量N(0

(1)

TCRi=TCWN+D′ (0

(2)

TTP=TCWN+1+TL+D(N≤C),

(3)

其中

D=TCCA+TACK+TSIFS+TLIFS,
D′=TCCA+TL+TSIFS,

服务时延TD的数学期望为

(4)

将式(2)(3)代入式(4)，由于

(5)

于是有

(6)

当节点有数据发送时，IEEE802.15.4协议的CSMA/CA算法先按均匀分布规则从(0，Wi-1)中随机选取一个值作为退避时隙数，其中

Wi=2iWmin，i∈[0,m]，

而i为退避级数，m为最大退避级数，Wmin为最小退避窗口数。若退避级数到达最大时仍没有发送成功，则Wm将维持2mWmin，直到达到最大重试次数C或发送成功为止。

节点第一次接入信道时，平均退避时间为

其中TE表示等效的时隙长度。第i次接入信道时，平均退避时间为

(7)

因此，只需确定TE和P{N=n}的分布，就可以确定服务时延TD的数学期望E(TD)。

假设网络中有n个节点，除了当前节点传输外，其它节点至少有一个准备进行数据传输，每个节点发送帧的概率为τ，则发生冲突的概率

p=1- (1-τ)n-1，

(8)

于是节点发送帧时发生冲突的概率为[9]

(9)

从而节点传送帧成功的概率

(10)

当节点处于退避时期时，考虑到信道空闲、传输成功和失败的情况，一个等效的时隙长度为

TE=(1-p)δ+pTSPs+pTCPs,

(11)

其中δ为空闲时隙，表示系统固定时隙的长度,TS为成功发送数据包占用的平均时间,TC为发送数据失败浪费的平均时间。

从式(11)可得

TS=TH+TEL+TSIFS+γ+TACK+TLIFS,

(12)

TC=TH+TEL+TSIFS+γ,

(13)

其中TH表示传输数据包头的时间，包括MAC层包头和物理层(Physical Layer, PHL)包头，TEL表示每次冲突中传输平均最长负载的时间，γ表示数据传播延迟。

随机变量N服从几何分布[9]，即

综上可知，当m>C时，有

而当m

可见，TD与帧的发送时延TL、冲突概率p、系统参数m、C以及Wmin有关，而p则由节点发送数据的概率τ和饱和节点数量n决定,其中τ只与饱和节点的数量n以及参数最大退避级数m和最小退避窗口Wmin有关[8]，所以当系统参数一定时，平均帧服务时延TD只与帧的发送时延TL和饱和站的数量n有关。

2 服务模型仿真分析

当网络发生拥塞时，一般会出现数据丢失，时延加大，吞吐量下降等现象[10]。为了验证理论分析的有效性，分别对帧服务时间随τ的变化以及随饱和站点数的关系进行仿真。

所有节点均采用IEEE802.15.4协议，物理层采用直接序列扩频，每个从节点以CSMA/CA方式竞争信道，并且所有节点发送数据帧长度均为127字节，最大尝试次数C为4，最大退避级数m为5，仿真时间120 s。

帧服务时延随τ变化情况如图2所示，从中可见，相对于网络中各节点的临界发送概率τ*，当节点发送帧的概率τ≤τ*时，TD随发送概率的增加而缓慢增大，当τ≥τ*时，TD随τ的增加而急剧增大。若网络经常处于τ≥τ*时，将大大增加点到点时延，因而根据网络情况适当调整τ，可以获得较高吞吐量和较低时延的折中。

图2 帧服务时延随τ而变化

帧服务时延随饱和站点数的变化情况如图3所示，从中可见，当τ一定时，TD随饱和站数据的增大而增大。当系统维持较高的τ时，TD随饱和站的增加而快速增加，通常TD只与网络中饱和站的数量、系统的参数m和Wmin有关，当部署节点时，m和Wmin一般不会改变，因此为了获得较高吞吐量以及较低时延，另一个可行的方法是根据网络状况适当的减少同一时间饱和站的数量。

图3 帧服务时延随饱和站点数而变化

3 拥塞控制算法

基于上面的分析，帧服务时延对信道的拥塞很敏感，因此采用TD做为节点拥塞指示，对CSMA/CA进行改进，改进的思路是在CSMA/CA中设置计时器，并在随机退避开始阶段系统开始计时，当计时器数据大于TD值时，节点自动降低发射速率，从而降低同一时间饱和节点数量。

算法流程改进部分的伪代码如下。

Begin(算法开始)

{

……

随机退避开始；

计时器开始计时(T)；

if T>TDthen 节点减速；

……

}

End (算法结束)

以TD做为拥塞指示信号的平均时延较采用平均队长作为拥塞指示信号有了明显的下降，结果如图4所示。网络中节点数越多，则改善的程度越明显，当节点数为40时，时延大约减少60%。

图4 采用TD做为拥塞指示信号前后时延比较

4 结语

针对无线传感器网络在网络层拥塞发生之前由于大量节点竞争信道而造成的MAC层拥塞问题，建立了IEEE802.15.4协议帧服务时延TD模型，给出了TD与平均帧长、冲突概率以及饱和站数量之间的关系，当节点的传输概率大于临界概率时，平均TD随传输概率或饱和节点的数量的增大而急剧增大，显示其对网络拥塞较为敏感在网络中存在发射的临界概率。把TD作为拥塞信号指示，对CSMA/CA算法进行改进，仿真表明，TD作为无线传感器网络拥塞指示，在一定条件下能有效的减少网络时延，提高网络吞吐量。

[1] Hull B, Jamieson K, Balakrishnan H. Mitigating congestion in wireless sensor networks[C]//Proceeding of the 2nd ACM Conference on Embedded Networked Sensor Systems(SenSys). Baltimore: ACM Press, 2004:134-147.

[2] Wang Yunbo, Vuran M C, Goddard S. Cross-Layer Analysis of the End-to-End Delay Distribution in Wireless Sensor Networks[J]. IEEE/ACM Transactions on Networking,2012,20(1):305-318.

[3] Nath S, Gibbons P B. Communicating via fireflies: geographic routing on duty-cycled sensors[C]//International Conference on Information Processing in Sensor Networks (IPSN).Cambridge, MA:MIT Press,2007: 440-449.

[4] Gu Yu, He Tian. Data forwarding in extremely low duty-cycle sensor networks with unreliable communication links[C]∥The ACM Conference on Embedded Networked Sensor Systems (Sensys). Penn Plaza:ACM Press, 2007:321-334.

[5] Shifrin M, Cidon I. C3: Collective Congestion Control in Multi-hop Wireless Networks[C]//Wireless On-demand Network Systems and Services. Kranjska Gora: IEEE Press, 2010:31-38.

[6] Teo J Y, Ha Y, Tham C K. Interference-minimized multipath routing with congestion control in wireless sensor network for high-rate streaming[J]. IEEE Transactions on Mobile Computing, 2008, 7(9): 1124-1137.

[7] Tinnakornsrisuphap P, La R J. Characterization of queue fluctuations in probabilistic AQM mechanisms[J]. ACM Journal on IGMETRICS Performance Evaluation Review, 2004,32(1):283-294.

[8] Standard for part 802. 15.4. Wireless medium access control (MAC) and physical layer (PHY) specifications for low rate wireless personal area networks (WPAN)[S]. 2003 ed, New York, NY: IEEE,2003:166-192.

[9] Bianchi G. Performance Analysis of the IEEE 802.11 Distributed Coordination Function[J]. IEEE Journal on Selected Areas in Communications, 2000, 18(3):535-547.

[10] 马新华.基于区分服务的无线传感器网络性能研究[J].西安邮电学院学报，2011,16(1):29-31.

[责任编辑:王辉]

Congestion control algorithm based on frame service delay

MA Xinhua, YANG Junqing

(Department of Computer Engineering, Xi’an Aeronautical University, Xi’an 710077, China)

An improved congestion control algorithm is proposed to solve the MAC layer congestion in wireless sensors network. The algorithm adds a timer in the CSMA/CA algorithm of IEEE802.15.4 protocol with frame service delay as its threshold due to the effectiveness of IEEE802.15.4 MAC layer frame service delay on the congestion indication. The MAC layer congestion can be controlled by a sensor node which adjusts launch rate based on the value of timer. Simulation result shows that the revised protocol can better indicate network congestion compared with the conventional way. The congestion is reduced by 60% on a network with 40 nodes.

media access control(MAC), frame service delay, congestion control, wireless sensors network

10.13682/j.issn.2095-6533.2014.01.019

2013-09-13

陕西省教育厅科学研究计划基金资助项目(11JK1073)

马新华(1978-),女，硕士，讲师，从事无线传感器网络研究。E-mail:maxinhua922@163.com 杨俊清(1966-),男，教授，从事无线传感器网络研究。E-mail: yjqfive@163.com

TN915.04

A

2095-6533(2014)01-0086-04