一種基于自適應(yīng)競(jìng)爭(zhēng)窗口的無線傳感器網(wǎng)絡(luò)擁塞緩解策略

方晨 劉昊 時(shí)龍興

(東南大學(xué)國(guó)家專用集成電路系統(tǒng)工程技術(shù)研究中心，南京 210096)

無線傳感器網(wǎng)絡(luò)在商業(yè)和軍事上具有廣泛的應(yīng)用，如環(huán)境監(jiān)測(cè)、工業(yè)傳感、戰(zhàn)場(chǎng)情報(bào)等［1-2］.該網(wǎng)絡(luò)通常由樹形匯聚的數(shù)據(jù)流組成，而并非獨(dú)立的點(diǎn)對(duì)點(diǎn)數(shù)據(jù)傳輸.隨著周期性、離散、突發(fā)的事件發(fā)生，無線傳感器網(wǎng)絡(luò)表現(xiàn)出獨(dú)特的匯聚特性，即數(shù)據(jù)包產(chǎn)生并迅速向一個(gè)或多個(gè)匯聚節(jié)點(diǎn)移動(dòng)［3］.

在傳統(tǒng)的Ad hoc無線網(wǎng)絡(luò)中，節(jié)點(diǎn)需要保持工作狀態(tài)以偵聽可能到達(dá)的數(shù)據(jù)包，其中空閑偵聽浪費(fèi)了大量的能量.而在無線傳感器網(wǎng)絡(luò)中，路由及媒體訪問控制層(media access control，MAC)的能效是無線傳感器網(wǎng)絡(luò)通信協(xié)議一個(gè)基本的設(shè)計(jì)要點(diǎn)［4-5］.近年來的研究發(fā)現(xiàn)，在無線傳感器網(wǎng)絡(luò)協(xié)議設(shè)計(jì)中，首選的節(jié)能方法是使節(jié)點(diǎn)周期性睡眠以節(jié)省能耗［6-11］.

數(shù)據(jù)包匯聚特性和周期性睡眠帶來了很多負(fù)面效應(yīng).例如，在匯聚的網(wǎng)絡(luò)中，數(shù)據(jù)包經(jīng)過多跳接力向匯聚節(jié)點(diǎn)集中，導(dǎo)致離匯聚節(jié)點(diǎn)越近數(shù)據(jù)密度越大；在周期睡眠的MAC協(xié)議中，數(shù)據(jù)包經(jīng)過多跳傳輸，大幅增加了數(shù)據(jù)包傳遞延遲；傳感器節(jié)點(diǎn)同步喚醒，增加了碰撞的概率.當(dāng)網(wǎng)絡(luò)載荷增加時(shí)，這些負(fù)面效應(yīng)加劇了網(wǎng)絡(luò)擁塞，導(dǎo)致網(wǎng)絡(luò)中數(shù)據(jù)包延遲及丟失.盡管傳感器節(jié)點(diǎn)可以采用上層擁塞緩解協(xié)議進(jìn)行擁塞控制［12-14］，但是離開MAC層的幫助，它們不能對(duì)網(wǎng)絡(luò)擁塞進(jìn)行快速反應(yīng)，以避免由于緩存溢出導(dǎo)致數(shù)據(jù)包的丟失.

針對(duì)上述問題，本文提出了一種適用于大多數(shù)傳感器網(wǎng)絡(luò)MAC協(xié)議的擁塞減輕策略，即自適應(yīng)競(jìng)爭(zhēng)窗口策略(adaptivecontentionwindow，ACW).該策略包括擁塞探測(cè)和擁塞減輕2個(gè)部分，原理是使緩存較多數(shù)據(jù)包的節(jié)點(diǎn)獲得較高的成功競(jìng)爭(zhēng)信道的概率，進(jìn)行數(shù)據(jù)包的發(fā)送，以緩解網(wǎng)絡(luò)擁塞引起的數(shù)據(jù)包丟失問題.

1 ACW策略設(shè)計(jì)

1.1 擁塞

在一個(gè)典型的傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)探測(cè)到事件發(fā)生，產(chǎn)生數(shù)據(jù)包；隨后，數(shù)據(jù)包被節(jié)點(diǎn)以接力方式向匯聚節(jié)點(diǎn)傳輸(見圖1).圖中，節(jié)點(diǎn)0，1，2為子節(jié)點(diǎn)，節(jié)點(diǎn)3為父節(jié)點(diǎn)，節(jié)點(diǎn)4為爺節(jié)點(diǎn).假設(shè)對(duì)于節(jié)點(diǎn)i，數(shù)據(jù)包的到達(dá)率和發(fā)送率分別為λi和 μi，則在時(shí)間 t內(nèi)，在子節(jié)點(diǎn)(i=0，1，2)聚集的數(shù)據(jù)包數(shù)目為(λi－μi)t，而父節(jié)點(diǎn)在t時(shí)間內(nèi)聚集的數(shù)據(jù)包數(shù)目為 (+λ3)t.可以預(yù)見，子節(jié)點(diǎn)數(shù)目增加時(shí)，父節(jié)點(diǎn)會(huì)聚集更多的數(shù)據(jù)包.同時(shí)，子節(jié)點(diǎn)和父節(jié)點(diǎn)均需競(jìng)爭(zhēng)媒體訪問信道.圖1中，子節(jié)點(diǎn)和父節(jié)點(diǎn)共享通信信道，且其信道競(jìng)爭(zhēng)能力相同.隨著子節(jié)點(diǎn)數(shù)目的增加，父節(jié)點(diǎn)成功競(jìng)爭(zhēng)信道的概率下降，不能有效地將子節(jié)點(diǎn)傳輸來的數(shù)據(jù)包傳遞至爺節(jié)點(diǎn)，父節(jié)點(diǎn)緩存越來越多的數(shù)據(jù)包，直至其緩存溢出，網(wǎng)絡(luò)發(fā)生嚴(yán)重?fù)砣?，整個(gè)網(wǎng)絡(luò)性能下降.因此，若父節(jié)點(diǎn)能夠探測(cè)擁塞并提升自身競(jìng)爭(zhēng)信道能力，盡快將數(shù)據(jù)包傳遞至爺節(jié)點(diǎn)，則可以達(dá)到緩解擁塞的目的.

1.2 擁塞探測(cè)

目前，擁塞探測(cè)方法主要有2種:① 基于隊(duì)列長(zhǎng)度的擁塞探測(cè)方法；② 基于信道采樣的擁塞探測(cè)方法.前者的性能弱于后者［12］.在基于隊(duì)列長(zhǎng)度的擁塞探測(cè)方法中，節(jié)點(diǎn)監(jiān)測(cè)發(fā)送隊(duì)列的緩存空置比率，當(dāng)緩存空置比率低于某個(gè)閾值時(shí)，節(jié)點(diǎn)判斷網(wǎng)絡(luò)發(fā)生了擁塞.在基于信道采樣的擁塞探測(cè)方法中，有數(shù)據(jù)包需要發(fā)送前，需要對(duì)傳感器節(jié)點(diǎn)進(jìn)行信道采樣，再根據(jù)信道繁忙狀態(tài)，計(jì)算利用率因子，如果其高于某閾值，則節(jié)點(diǎn)判斷網(wǎng)絡(luò)發(fā)生了擁塞；然而，信道采樣屬于空閑偵聽，會(huì)浪費(fèi)能量［13］.無線傳感器網(wǎng)絡(luò)需要節(jié)省能量，以使節(jié)點(diǎn)工作時(shí)間更長(zhǎng)，故在ACW策略中，采用第1種方法進(jìn)行擁塞探測(cè).

1.3 擁塞緩解

節(jié)點(diǎn)探測(cè)到擁塞后，開始調(diào)用自適應(yīng)競(jìng)爭(zhēng)窗口算法，使緩存較多數(shù)據(jù)包的節(jié)點(diǎn)獲得較高的進(jìn)行數(shù)據(jù)包發(fā)送的概率.自適應(yīng)競(jìng)爭(zhēng)窗口算法將當(dāng)前周期節(jié)點(diǎn)的隨機(jī)競(jìng)爭(zhēng)窗口尺寸Wran∈(1，Wm)與其緩存隊(duì)列長(zhǎng)度l∈(1，lm)進(jìn)行反比例映射，其中Wm表示當(dāng)前周期中可選取競(jìng)爭(zhēng)窗口尺寸的最大值，lm表示節(jié)點(diǎn)最大隊(duì)列長(zhǎng)度，由節(jié)點(diǎn)緩存空間決定.

該競(jìng)爭(zhēng)窗口自適應(yīng)過程是一個(gè)閉環(huán)反饋控制過程，流程圖見圖2.節(jié)點(diǎn)監(jiān)測(cè)發(fā)送隊(duì)列的長(zhǎng)度，發(fā)現(xiàn)緩存空置比率上升時(shí)，預(yù)測(cè)本節(jié)點(diǎn)會(huì)聚集更多的數(shù)據(jù)包，故縮小競(jìng)爭(zhēng)窗口尺寸，提高成功競(jìng)爭(zhēng)信道、進(jìn)行數(shù)據(jù)包發(fā)送的概率；反之，則增大競(jìng)爭(zhēng)窗口的尺寸.

圖2 自適應(yīng)競(jìng)爭(zhēng)窗口調(diào)整

當(dāng)前周期節(jié)點(diǎn)隨機(jī)選擇的競(jìng)爭(zhēng)窗口尺寸Wc為

式中，α=l/lm表示緩存的占用比率.

此外，當(dāng)網(wǎng)絡(luò)嚴(yán)重?fù)砣麜r(shí)，相鄰節(jié)點(diǎn)緩存隊(duì)列長(zhǎng)度均較長(zhǎng)，各節(jié)點(diǎn)經(jīng)過映射計(jì)算得出的Wran較小，導(dǎo)致隨機(jī)選擇競(jìng)爭(zhēng)窗口的范圍縮小，相鄰節(jié)點(diǎn)競(jìng)爭(zhēng)信道時(shí)碰撞概率上升.因此，設(shè)Wlit為隨機(jī)選擇競(jìng)爭(zhēng)窗口范圍的下限，若經(jīng)過映射計(jì)算得出的Wran小于 Wlit，則 Wran=Wlit，以減小競(jìng)爭(zhēng)窗口選擇范圍縮小后引起的碰撞概率.

實(shí)際應(yīng)用中，不同節(jié)點(diǎn)的緩存大小及競(jìng)爭(zhēng)窗口的初始值不盡相同，但ACW策略采用的反比例映射算法可使其具有較廣泛的適用性.

前人關(guān)于 IEEE 802.11可變競(jìng)爭(zhēng)窗口的研究［4-5］并不適用于低占空比工作周期的無線傳感器網(wǎng)絡(luò)［15］.因此，本文從無線傳感器網(wǎng)絡(luò)自身的特性及存在的問題出發(fā)，展開研究.

2 仿真環(huán)境

將ACW策略在仿真軟件NS-2 V2.29中實(shí)現(xiàn)，并采用NOAH路由協(xié)議.仿真中，每個(gè)節(jié)點(diǎn)都加載載荷，載荷為固定比特率數(shù)據(jù)流，所有數(shù)據(jù)包大小為50 B.假設(shè)中繼節(jié)點(diǎn)不改變數(shù)據(jù)包的長(zhǎng)度，且節(jié)點(diǎn)對(duì)數(shù)據(jù)的處理可以在射頻收發(fā)轉(zhuǎn)換時(shí)間內(nèi)完成，故數(shù)據(jù)處理不會(huì)引入新的延遲.不同類型數(shù)據(jù)包的傳輸延遲見表1.

表1 傳輸延時(shí)表

簇狀樹形網(wǎng)絡(luò)拓?fù)浜?jiǎn)單實(shí)用，在眾多無線傳感器網(wǎng)絡(luò)應(yīng)用中被大量采用［16-17］.因此，本文采用一個(gè)8節(jié)點(diǎn)的樹形網(wǎng)絡(luò)進(jìn)行仿真評(píng)估，其網(wǎng)絡(luò)拓?fù)鋱D見圖3.為了證明ACW策略的有效性，在SMAC協(xié)議［6］上加載ACW策略，并與原協(xié)議進(jìn)行性能對(duì)比.節(jié)點(diǎn)參數(shù)設(shè)置見表2.

圖3 樹形拓?fù)?/p>

表2 節(jié)點(diǎn)參數(shù)設(shè)置表

3 結(jié)果分析

3.1 ACW策略效果

采用SMAC協(xié)議時(shí)，節(jié)點(diǎn)1～節(jié)點(diǎn)7的緩存隊(duì)列長(zhǎng)度與仿真時(shí)間的變化關(guān)系見圖4.由圖可知，離匯聚節(jié)點(diǎn)較近的節(jié)點(diǎn)1～節(jié)點(diǎn)3的隊(duì)列在仿真過程中長(zhǎng)期處于飽和狀態(tài)，其余各節(jié)點(diǎn)的緩存隊(duì)列在仿真開始后迅速進(jìn)入飽和狀態(tài)，且隊(duì)列被逐漸排空.該仿真過程持續(xù)1200 s.仿真中，外圍節(jié)點(diǎn)將數(shù)據(jù)包推送至離匯聚節(jié)點(diǎn)較近的節(jié)點(diǎn)，而離匯聚節(jié)點(diǎn)較近的節(jié)點(diǎn)來不及排空緩存的數(shù)據(jù)包，發(fā)生緩存溢出，導(dǎo)致節(jié)點(diǎn)1～節(jié)點(diǎn)3處大量數(shù)據(jù)包被丟棄.

圖4 SMAC各節(jié)點(diǎn)隊(duì)列長(zhǎng)度變化曲線

采用ACW策略后，節(jié)點(diǎn)1～節(jié)點(diǎn)7的緩存隊(duì)列長(zhǎng)度與仿真時(shí)間的變化關(guān)系見圖5.由圖可知，離匯聚節(jié)點(diǎn)較近的節(jié)點(diǎn)1～節(jié)點(diǎn)3的隊(duì)列于仿真開始時(shí)便迅速進(jìn)入飽和狀態(tài)，隨后各節(jié)點(diǎn)的緩存隊(duì)列被逐漸排空，仿真持續(xù)1800 s.其原因在于，當(dāng)網(wǎng)絡(luò)發(fā)生擁塞時(shí)，ACW策略提高了節(jié)點(diǎn)1～節(jié)點(diǎn)3成功競(jìng)爭(zhēng)信道的概率，同時(shí)，迫使外圍緩存數(shù)據(jù)包較少節(jié)點(diǎn)的競(jìng)爭(zhēng)信道成功率大幅降低，延緩了外圍節(jié)點(diǎn)向節(jié)點(diǎn)1～節(jié)點(diǎn)3推送數(shù)據(jù)包的速度，縮短了緩存隊(duì)列的長(zhǎng)度，外圍節(jié)點(diǎn)逐漸恢復(fù)競(jìng)爭(zhēng)信道能力，從而繼續(xù)進(jìn)行數(shù)據(jù)包的傳遞.ACW策略極大地避免了由于擁塞導(dǎo)致的數(shù)據(jù)包丟失.

圖5 ACW各節(jié)點(diǎn)隊(duì)列長(zhǎng)度變化曲線

由此可知，ACW策略的效果主要體現(xiàn)在2個(gè)方面:①幫助緩存隊(duì)列較長(zhǎng)的節(jié)點(diǎn)提高競(jìng)爭(zhēng)信道能力，獲得較高的數(shù)據(jù)包發(fā)送概率，以減輕擁塞，減少數(shù)據(jù)包的丟失；②在緩存隊(duì)列較短的節(jié)點(diǎn)處，緩存數(shù)據(jù)包.當(dāng)擁塞發(fā)生時(shí)，網(wǎng)絡(luò)中的數(shù)據(jù)包在網(wǎng)絡(luò)的外圍節(jié)點(diǎn)進(jìn)行緩存，避免了數(shù)據(jù)包的迅速匯聚.

3.2 數(shù)據(jù)包傳遞率及能耗評(píng)估

數(shù)據(jù)包傳遞率是指成功到達(dá)匯聚節(jié)點(diǎn)的數(shù)據(jù)包數(shù)目與產(chǎn)生于所有源節(jié)點(diǎn)的數(shù)據(jù)包總數(shù)目的比值.源節(jié)點(diǎn)數(shù)據(jù)包的產(chǎn)生間隔時(shí)間與數(shù)據(jù)包傳遞率之間的關(guān)系見圖6.由圖可知，隨著源節(jié)點(diǎn)向網(wǎng)絡(luò)中注入數(shù)據(jù)包的頻率增加，ACW策略大幅提高了SMAC協(xié)議的數(shù)據(jù)包傳遞率.當(dāng)數(shù)據(jù)包的產(chǎn)生間隔時(shí)間小于10 s時(shí)，ACW策略使數(shù)據(jù)包傳遞率提高了25%～30%.

圖6 數(shù)據(jù)包傳遞率與源節(jié)點(diǎn)數(shù)據(jù)包產(chǎn)生時(shí)間間隔的關(guān)系

平均能耗是指仿真過程中各節(jié)點(diǎn)耗能的平均值.由圖7可知，由于SMAC協(xié)議采用周期性睡眠策略，其平均能耗較低.ACW策略大幅提高數(shù)據(jù)包傳遞率的同時(shí)，相對(duì)于SMAC協(xié)議，其能耗略微增加.增加的能耗源于對(duì)更多數(shù)據(jù)包的傳輸.

圖7 平均能耗與源節(jié)點(diǎn)數(shù)據(jù)包產(chǎn)生時(shí)間間隔的關(guān)系

4 結(jié)論

1)設(shè)計(jì)了一種自適應(yīng)競(jìng)爭(zhēng)窗口調(diào)整算法.將緩存較多數(shù)據(jù)包的節(jié)點(diǎn)賦予較高的成功競(jìng)爭(zhēng)信道概率，從而提高了數(shù)據(jù)包的傳遞率.當(dāng)擁塞發(fā)生時(shí)，數(shù)據(jù)包在網(wǎng)絡(luò)外圍被節(jié)點(diǎn)緩存，避免了數(shù)據(jù)包的迅速匯聚.本質(zhì)上，通過平衡網(wǎng)絡(luò)中載荷分布，大幅減少了網(wǎng)絡(luò)中數(shù)據(jù)包的丟失.

2)在仿真軟件NS-2 V2.29中進(jìn)行了ACW 策略設(shè)計(jì)及仿真.結(jié)果表明，該策略提高了數(shù)據(jù)包的傳遞率，緩解了無線傳感器網(wǎng)絡(luò)擁塞所帶來的副作用.

References)

［1］Yick J，Mukherjee B，Ghosal D.Wireless sensor network survey［J］.Computer Networks，2008，52(12):2292-2330.

［2］Potdar V，Sharif A，Chang E.Wireless sensor networks:a survey［C］//Proceedings of 2009 Advanced Information Networking and Applications Workshops.Bradford，England，2009:636-641.

［3］Wan C Y，Eisenman S B，Campbell A T，et al.Overload traffic management for sensor networks［J］.ACM Transactions on Sensor Networks，2007，3(4):18-22.

［4］Pries R，Menth S，Staehle D，et al.Dynamic contention window adaptation(DCWA)in IEEE 802.11e wireless local area networks［C］//Proceedings of 2008 International Conference on Communications and Electronics.Hoi An，Vietnam，2008:92-97.

［5］Lv J，Zhang X M，Han X J，et al.A novel adaptively dynamic tuning of the contention window(CW)for distributed coordination function in IEEE 802.11 ad hoc networks［C］//Proceedings of 2007 International Conference on Convergence Information Technology.Gyeongju，Korea，2007:290-294.

［6］Ye W，Heidemann J，Estrin D.An energy-efficient MAC protocol for wireless sensor networks［C］//Proceedings of 2002 IEEE INFOCOM.New York，USA，2002:1567-1576.

［7］Ringwald M，Romer K.BitMAC:a deterministic，collision-free，and robust MAC protocol for sensor networks［C］//Proceedings of the 2nd European Workshop on Wireless Sensor Networks.Istanbul，Turkey，2005:57-69.

［8］Yu F，Wu T，Biswas S.Toward in-band self-organization in energy-efficient MAC protocols for sensor networks［J］.IEEE Transactions on Mobile Computing，2008，7(2):156-170.

［9］Liu S，F(xiàn)an K，Sinha P.CMAC:an energy-efficient MAC layer protocol using convergent packet forwarding for wireless sensor networks［J］.ACM Transactions on Sensor Networks，2009，5(4):1-34.

［10］Hurni P，Braun T.MaxMAC:a maximally traffic-adaptive MAC protocol for wireless sensor networks［C］//Proceedings of 2010 European Conference on Wireless Sensor Networks.Coimbra，Portugal，2010:289-305.

［11］Fang C，Liu H，Qian L.LC-MAC:an efficient mac protocol for the long-chain wireless sensor networks［C］//Proceedings of 2011 International Conference on Communications and Mobile Computing.Qingdao，China，2011:495-500.

［12］Hull B，Jamieson K，Balakrishnan H.Mitigating congestion in wireless sensor networks［C］//Proceedings of 2004 International Conference on Embedded Networked Sensor Systems.Baltimore，Maryland，USA，2004:134-147.

［13］Wan C Y，Eisenman S B，Campbell A T.Coda:congestion detection and avoidance in sensor networks［C］//Proceedings of 2003 International Conference on Embedded Networked Sensor Systems.Los Angeles，CA，USA，2003:266-279.

［14］Zhai H，F(xiàn)ang U.Distributed flow control and medium access in multihop ad hoc networks［J］.IEEE Transactions on Mobile Computing，2006，5(11):1503-1514.

［15］Intanagonwiwat C，Govindan R，Estrin D.Directed diffusion:a scalable and robust communication paradigm for sensor networks［C］//Proceedings of 2000 International Conference on Mobile Computing and Networking.Boston，USA，2000:56-67.

［16］Jonhnstone I，Nicholson J，Shehzad B，et al.Experiences from a wireless sensor network deployment in a petroleum environment［C］//Proceedings of 2007 International Conference on Wireless Communications and Mobile Computing.New York，USA，2007:382-387.

［17］Wan Y D，Li L，He J.Anshan:wireless sensor networks for equipment fault diagnosis in the process industry［C］//Proceedings of 2008 Sensor，Mesh and Ad Hoc Communications and Networks.San Francisco，CA，USA，2008:314-322.