一種基于自適應競爭窗口的無線傳感器網絡擁塞緩解策略

方晨 劉昊 時龍興

(東南大學國家專用集成電路系統工程技術研究中心，南京 210096)

無線傳感器網絡在商業和軍事上具有廣泛的應用，如環境監測、工業傳感、戰場情報等［1-2］.該網絡通常由樹形匯聚的數據流組成，而并非獨立的點對點數據傳輸.隨著周期性、離散、突發的事件發生，無線傳感器網絡表現出獨特的匯聚特性，即數據包產生并迅速向一個或多個匯聚節點移動［3］.

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

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

針對上述問題，本文提出了一種適用于大多數傳感器網絡MAC協議的擁塞減輕策略，即自適應競爭窗口策略(adaptivecontentionwindow，ACW).該策略包括擁塞探測和擁塞減輕2個部分，原理是使緩存較多數據包的節點獲得較高的成功競爭信道的概率，進行數據包的發送，以緩解網絡擁塞引起的數據包丟失問題.

1 ACW策略設計

1.1 擁塞

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

1.2 擁塞探測

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

1.3 擁塞緩解

節點探測到擁塞后，開始調用自適應競爭窗口算法，使緩存較多數據包的節點獲得較高的進行數據包發送的概率.自適應競爭窗口算法將當前周期節點的隨機競爭窗口尺寸Wran∈(1，Wm)與其緩存隊列長度l∈(1，lm)進行反比例映射，其中Wm表示當前周期中可選取競爭窗口尺寸的最大值，lm表示節點最大隊列長度，由節點緩存空間決定.

該競爭窗口自適應過程是一個閉環反饋控制過程，流程圖見圖2.節點監測發送隊列的長度，發現緩存空置比率上升時，預測本節點會聚集更多的數據包，故縮小競爭窗口尺寸，提高成功競爭信道、進行數據包發送的概率；反之，則增大競爭窗口的尺寸.

圖2 自適應競爭窗口調整

當前周期節點隨機選擇的競爭窗口尺寸Wc為

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

此外，當網絡嚴重擁塞時，相鄰節點緩存隊列長度均較長，各節點經過映射計算得出的Wran較小，導致隨機選擇競爭窗口的范圍縮小，相鄰節點競爭信道時碰撞概率上升.因此，設Wlit為隨機選擇競爭窗口范圍的下限，若經過映射計算得出的Wran小于 Wlit，則 Wran=Wlit，以減小競爭窗口選擇范圍縮小后引起的碰撞概率.

實際應用中，不同節點的緩存大小及競爭窗口的初始值不盡相同，但ACW策略采用的反比例映射算法可使其具有較廣泛的適用性.

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

2 仿真環境

將ACW策略在仿真軟件NS-2 V2.29中實現，并采用NOAH路由協議.仿真中，每個節點都加載載荷，載荷為固定比特率數據流，所有數據包大小為50 B.假設中繼節點不改變數據包的長度，且節點對數據的處理可以在射頻收發轉換時間內完成，故數據處理不會引入新的延遲.不同類型數據包的傳輸延遲見表1.

表1 傳輸延時表

簇狀樹形網絡拓撲簡單實用，在眾多無線傳感器網絡應用中被大量采用［16-17］.因此，本文采用一個8節點的樹形網絡進行仿真評估，其網絡拓撲圖見圖3.為了證明ACW策略的有效性，在SMAC協議［6］上加載ACW策略，并與原協議進行性能對比.節點參數設置見表2.

圖3 樹形拓撲

表2 節點參數設置表

3 結果分析

3.1 ACW策略效果

采用SMAC協議時，節點1～節點7的緩存隊列長度與仿真時間的變化關系見圖4.由圖可知，離匯聚節點較近的節點1～節點3的隊列在仿真過程中長期處于飽和狀態，其余各節點的緩存隊列在仿真開始后迅速進入飽和狀態，且隊列被逐漸排空.該仿真過程持續1200 s.仿真中，外圍節點將數據包推送至離匯聚節點較近的節點，而離匯聚節點較近的節點來不及排空緩存的數據包，發生緩存溢出，導致節點1～節點3處大量數據包被丟棄.

圖4 SMAC各節點隊列長度變化曲線

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

圖5 ACW各節點隊列長度變化曲線

由此可知，ACW策略的效果主要體現在2個方面:①幫助緩存隊列較長的節點提高競爭信道能力，獲得較高的數據包發送概率，以減輕擁塞，減少數據包的丟失；②在緩存隊列較短的節點處，緩存數據包.當擁塞發生時，網絡中的數據包在網絡的外圍節點進行緩存，避免了數據包的迅速匯聚.

3.2 數據包傳遞率及能耗評估

數據包傳遞率是指成功到達匯聚節點的數據包數目與產生于所有源節點的數據包總數目的比值.源節點數據包的產生間隔時間與數據包傳遞率之間的關系見圖6.由圖可知，隨著源節點向網絡中注入數據包的頻率增加，ACW策略大幅提高了SMAC協議的數據包傳遞率.當數據包的產生間隔時間小于10 s時，ACW策略使數據包傳遞率提高了25%～30%.

圖6 數據包傳遞率與源節點數據包產生時間間隔的關系

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

圖7 平均能耗與源節點數據包產生時間間隔的關系

4 結論

1)設計了一種自適應競爭窗口調整算法.將緩存較多數據包的節點賦予較高的成功競爭信道概率，從而提高了數據包的傳遞率.當擁塞發生時，數據包在網絡外圍被節點緩存，避免了數據包的迅速匯聚.本質上，通過平衡網絡中載荷分布，大幅減少了網絡中數據包的丟失.

2)在仿真軟件NS-2 V2.29中進行了ACW 策略設計及仿真.結果表明，該策略提高了數據包的傳遞率，緩解了無線傳感器網絡擁塞所帶來的副作用.

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，Fan 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，Fang 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.