一种实用的传感器网络拥塞控制算法

1、一种实用的传感器网络拥塞控制算法doi:10.3969/j.issn.1001-3695.2009.06.072PracticalcongestioncontrolalgorithmforsensornetworksWANGYan-mei,QINShao-hua,HUANGYong-ping,CAOJian(SchoolofComputerScience&InformationEngineering,GuangxiNormalUniversity,GuilinGuangxi541004,China)Congestioninsensornetworksnotonlycausespacke

2、tloss,butalsoleadstoexcessiveenergyconsumption.Thereforecongestionneedstobecontrolledinordertoprolongsystemlifetime.Thispaperproposedacongestioncontrolmechanismbasedoncongestionstateforsensornetwork(CMCS).Unlikeexistingwork,CMCSinnovativelymeasuredcongestiondegreebasedonqueuelengthandcongestionincre

3、asingcoefficientinintermediatenodes.CMCSutilizedabandwidthallocationstrategybasedonbufferincreasingspaceandimposedapacket-discardingschemebasedonpacketsurplusvaluetocontrolcongestion.TheresultofexperimentshowsthatCMCSachievesefficientcongestioncontrol,asaresult,itleadstohigherenergyefficiencyandbett

4、erQoSintermsofbothpacketlossrateandnetworkvaluethroughput.传感器网络能广泛应用于监测、监控等领域，它由大量具有感知能力、计算能力和通信能力的传感器节点组成，相互协作地感知、采集和处理监测区域中感知对象的数据，并将数据沿着多跳无线链路传输到基站(sink节点)，形成传感器节点到sink节点的多对一通信模式。由于传感器网络带宽受限，这种通信模式使得大量分组聚集在汇聚区域，造成信道竞争和冲突增加，从而引发拥塞。而拥塞会造成网络传输能力的下降和传输时延的增加以及数据的丢失，由此产生的重传又会进一步增加网络流量和节点的能耗。因此，需要对无线传感器

5、网络实施有效的拥塞控制，以保证网络可靠的数据传输。1 问题描述?，尴叽？感器节点处理、存储和通信能力相对较弱，且通常使用能量有限的电池供电。通信链路具有随机损耗以及易受环境的影响，所以在设计拥塞控制协议时需要考虑以下问题1：a)能量有效性。节点的拥塞控制操作要尽可能简单，开销少，占用节点的存储空间要小。b)及时性。拥塞产生后，可能在极短的时间内造成大量的数据丢失，很快扩散，所以需要预测或及时发现网络拥塞，并在较短时间内解除拥塞，避免拥塞扩散。c)保证网络传输的质量，如网络延时、网络吞吐量和分组丢失率等。d)公平性。需要保证网络中的节点有均等的机会发送数据。?亡等？检测方法主要包括基于缓存长度的

6、检测24和基于信道采样4,5的检测。基于缓存长度的检测方法认为，缓存数据队列占用越长，说明节点发送数据的机会越少。由于邻居节点竞争使用共享的无线信道，这将导致附近区域需要发送的数据越多，就越有可能发生拥塞。它通常设定一个阈值，如果瞬时的缓存队列占用长度超过这个阈值，就认为发生了拥塞。这种方法的优点是实现非常简单，几乎没有额外的开销。但若检测阈值设置较大，那么当数据占用缓冲区的大部分时才检测到拥塞状态，不利于及时解除拥塞。此外缓存中数据队列长度只能反映节点的接收分组速率与发送分组速率的关系，间接地刻画网络的流量状况。Wan人4指出，单独的缓冲区占用情况不是一个可靠的拥塞检测指示。?七？于信道采样

7、的检测方法依据的是如果出现拥塞，拥塞区域内的节点忙于竞争无线信道发送分组，无线信道连续处于忙状态。信道采样的目标是获得当前信道利用率的一个估计，这个估计作为拥塞的指示。但是，信道利用率与拥塞的关系依赖于MAC协议，如使用TDMA言道可以在几乎饱和的情况下不影响吞吐量；而CDMA、议存在最大的信道利用率，网络流量过大引起信道冲突，造成网络的吞吐量减少。当信道利用率在最大利用率附近时认为网络出现了拥塞。为了准确及时地发现无线信道的忙闲，需要连续采样信道状态，因而会消耗节点较多的能量,且需要底层通信协议的支持1。?匕陨狭街旨毅修际醵济挥锌悸堑秸皮？一个事实，为了最大限度地利用带宽资源，提高网络的吞吐

8、量，网络工作在轻度拥塞状态应该是较为理想的6，尤其在传感器网络中，节点的资源非常珍贵。如何利用有限的带宽资源来最大化网络的吞吐量，但又不导致拥塞崩溃现象，这是本文关注的主要问题。基于此，本文提出了一种新的拥塞控制机制（congestioncontrolmechanismbasedoncongestionstate,CMCS,采用基于节点缓冲器占有率和拥塞增长系数来判断拥塞的变化趋势。当检测到拥塞会造成节点传输性能下降时，则以拥塞节点为中心进行拥塞反馈和带宽分配；并在丢包策略中，综合考虑分组的服务质量和节点发送数据的公平性。2 CMCSM塞控制算法?夕悸怯？Nj随机部署的无线传感器节点形成的网络

9、，具应用场景为基站模式。该模式是传感器网络应用最为广泛的情形，传感器节点随机部署在一个方形区域内并保持静止，数据汇聚节点（sink节点）位于方形观测区域的外侧。所有传感器节点是同构的并具有相同的初始能量。每个节点的通信半径为r，任意两个节点的平面距离如果小于等于r，那么它们可以直接通信。CMC电含三个部分：基于节点缓存占有率和拥塞增长系数的拥塞检测、拥塞区域反馈及速率分配算法和节点丢包策略。当节点缓存队列长度超过一个阈值时，启动拥塞检测，若节点在一个时段内持续出现过载行为，则认为节点出现了拥塞，然后拥塞节点通告拥塞并降低共享信道内活跃邻居节点的发送速率来增大其可用的带宽，同时启动丢包策略来丢失

10、剩余价值最小的分组。2.1 拥塞检测?亡等？是一种持续过载的网络状态，即在一时间段内节点接收到的分组个数持续大于节点发送分组的个数。为了最大限度地利用资源，节点工作在轻度拥塞状态时应该是允许的，此时资源达到充分利用的程度，网络的吞吐量也处于最佳状态。但这也增加了滑向拥塞崩溃的可能性，所以需要一定的拥塞控制机制来加以区别和约束。本文设置缓存队列阈值Lsys，当缓存队列瞬时长度小于等于Lsys，认为节点处于轻度拥塞状态，利用节点的缓冲空间暂时缓存等候服务的分组，当节点负载减少时，拥塞可以自动恢复；当缓存队列瞬时长度大于Lsys，认为节点有可能滑向拥塞崩溃状态，此时CMC啰用拥塞检测技术来判断这一变

11、化趋势。CMC亲用节点的接收速率与发送速率之比来定义节点的拥塞增长系数：CN=Vr/Vs。其中：Vr为节点的接收速率；Vs为节点的发送速率。拥塞增长系数作为对节点负载情况的近似度量能较好地刻画节点的拥塞情况，拥塞增长系数同样也反映了缓存队列的变化趋势。如果CN>1就表示缓存队列变长，拥塞程度增加。本文采用缓存队列长度超过Lsys、且拥塞增长系数CN>1来标志节点发生拥塞，采用CNLsys,则启动定时器T,收集在T时段内发送的分组Ps和接收的分组Pr,计算拥塞增长系数CN=Pr/Ps（CN默认值等于1）。如果CN>1,则认为拥塞状态具有一定的持续性，很可能导致缓存溢出，并趋向拥

12、塞崩溃，所以需加以控制。2.2 拥塞反馈及速率控制算法?斤疚拇恿礁龊矫婵悸侨绢谓饰鱼占等？问题：a）增加网络资源；b）降低服务质量。增加网络资源是通过限制共享信道上通信节点的发送速率来增加拥塞节点的可用带宽，并在邻居节点的路由表中标记拥塞节点；在T时段内拥塞节点不再参与路由，即降低活跃邻居节点的服务质量来增加拥塞节点的网络资源，目的是缓解拥塞，将数据流量降低到节点能力范围之内，防止继续丢包。CMC亲用拥塞增长系数CN与缓存队列瞬时长度Lnow的乘积定义了节点的缓存增长空间：Bis=CNXLnow,缓存增长空间反映了节点的负载情况，间接表示节点的拥塞程度。为了减少控制消息的开销、降低算法的复杂性

13、，拥塞节点通过在分组中捎带节点的缓存增长空间Bis和发送速率rate的信息来通告拥塞并进行速率调节。活跃邻居节点监听到拥塞节点的分组后，根据控制信息和自己的Bis来调整自己的发送速率，即对于任一活跃邻居节点i，缓存增长空间为Bisi，其最大速率ratei<Bisi/Bisxrate。?干俣？节点i在调整前的速率大于新计算的速率ratei,则将自己的发送速率调整为新的ratei，否则维持原值。为防止速率抖动，同时最大限度利用带宽，节点i采用保守逐增的方式来调整发送速率，每隔时段T若没有接收到速率控制的消息，则根据Bisi，利用式(1)增加发送速率ratei。通过多轮调整，直到实际速率比期望

14、速率的差值小于给定的£。ratei=ratei+Bisi/Bisx|rate/ratei-1|xratei(1)2.3 丢包策略?廿苯诘愕母涸爻？过其服务能力时，节点上的缓存为等候服务的分组提供一定的保护。然而，若此超载状况具有一定的持续性，当缓存空间被耗尽时，节点只能丢弃分组。表面上，增大缓存空间可以防止由于拥塞引起的分组丢弃，但随着缓存的增加，端到端的时延也相应增大，而分组的生存期是有限的，超时的分组同样需要重传。因此，过大的缓存空间倒有可能妨碍拥塞的恢复，因为过时分组白白浪费了网络的可用带宽。所以当检测到拥塞时，CMCSB动丢包策略，丢弃过时分组以充分利用有限带宽，最大程度地确

15、保重要数据的及时可靠传输。本文依据系统预先设定的缓存队列参数Lmin、Lmax及节点拥塞增长系数CN结合Blue7算法来标志丢包概率，当计算的丢包概率大于系统阈值，根据剩余价值来丢弃价值最小的分组，提高网络的价值吞吐量。1)丢包概率计算每隔时间freeze_time计算节点拥塞增长系数CNN并获取缓冲器瞬时长度L来计算丢包概率Pd,丢包概率计算如算法1所示。其中：Llen表示缓存队列的容量；Si表示当发生拥塞且CN>1时Pd的增加量；52表示当信道空闲或CNC1时Pd的减少量。一般来说，51要比52大很多，这主要是因为当拥塞控制太保守或太激进时，均会导致信道使用率很低；而丢包只发生在拥塞

16、控制太保守时。通过赋予丢包事件更大的比重因子，丢包策略能够对突发流量作出及时的响应。?二惴？1丢包概率计算算法uponpacketloss(orL>Lmin)event:if(now-last_updatte)>freeze_time&&CN>1)if(L>Lmax)Pd=Pd+81*(1+(L-Lmax)/Llen);elsePd=Pd=Pd+81*(1-(Lmax-L)/Llen)；last_update=now;uponlinkidle(orCN<1)event:if(now-last_update)>freeze_time)Pd=Pd

17、-52;last_update=now;2)数据分组的剩余价值计算传感器网络缺少有效的时钟同步机制，本文采用在分组中携带剩余生存期的方法来实现分组的实时传输。在传输过程中，每个分组进入节点时打上时间戳，离开时通过计算在该节点上服务时间来更新分组的剩余生存期，如式(2)所示：ttl=ttl-(toff-ton)(2)其中：toff为分组离开节点时的时间戳；ton为分组进入节点打上的时间戳；ttl为分组的剩余生存期。分组的剩余价值随着剩余生存期的减少呈线性递减，当分组的ttlWO时，表示分组已过时，直接丢弃分组。?斤疚目悸欠肿？p的剩余生存期、可靠性和传输跳数来计算分组的剩余价值。根据剩余价值来决

18、定分组的丢弃顺序，其计算方法如式(3)所示：value=hopxreliablex(ttl-(toff-ton)(3)其中：hop为分组p的传输跳数，传输跳数越大，其重传的成本也就越高，相应价值也就越高；reliable为分组p的可靠性，可靠性越高，其价值也越高。3 仿真结果?十褂？OMNeT+.28作为仿真工具，这是一款面向对象的网络仿真软件。仿真平台在Linux下搭建，实验在1000X1000的区域内随机分布了100个node节点，节点的通信范围为190m在相同的节点分布条件下，对CMCS口CODAffi行对比分析实验。网络应用的底层支撑算法采用类似802.11DCF的MAC算法和AODV路由算法。为了模拟拥塞情况，每个源节点产生分组的速率为100pkt/s，分组长度为512Byte，仿真时间为100s。主要从三个方面评估CMCST法的性能，即网络的吞吐量、平均丢