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

方 晨 劉 昊 時(shí)龍興

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

無(wú)線傳感器網(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ú)線傳感器網(wǎng)絡(luò)表現(xiàn)出獨(dú)特的匯聚特性,即數(shù)據(jù)包產(chǎn)生并迅速向一個(gè)或多個(gè)匯聚節(jié)點(diǎn)移動(dòng)[3]．

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

數(shù)據(jù)包匯聚特性和周期性睡眠帶來(lái)了很多負(fù)面效應(yīng)．例如,在匯聚的網(wǎng)絡(luò)中,數(shù)據(jù)包經(jīng)過(guò)多跳接力向匯聚節(jié)點(diǎn)集中,導(dǎo)致離匯聚節(jié)點(diǎn)越近數(shù)據(jù)密度越大;在周期睡眠的MAC協(xié)議中,數(shù)據(jù)包經(jīng)過(guò)多跳傳輸,大幅增加了數(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],但是離開(kāi)MAC層的幫助,它們不能對(duì)網(wǎng)絡(luò)擁塞進(jìn)行快速反應(yīng),以避免由于緩存溢出導(dǎo)致數(shù)據(jù)包的丟失．

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

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

1.1 擁塞

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ā)生了擁塞;然而,信道采樣屬于空閑偵聽(tīng),會(huì)浪費(fèi)能量[13]．無(wú)線傳感器網(wǎng)絡(luò)需要節(jié)省能量，以使節(jié)點(diǎn)工作時(shí)間更長(zhǎng),故在ACW策略中,采用第1種方法進(jìn)行擁塞探測(cè)．

1.3 擁塞緩解

節(jié)點(diǎn)探測(cè)到擁塞后,開(kāi)始調(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)過(guò)程是一個(gè)閉環(huán)反饋控制過(guò)程,流程圖見(jià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)信道、

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

進(jìn)行數(shù)據(jù)包發(fā)送的概率;反之,則增大競(jìng)爭(zhēng)窗口的尺寸．

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

Wc∈(1,Wran)Wran=Wm(1-α)

(1)

式中,α=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)過(guò)映射計(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)過(guò)映射計(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ú)線傳感器網(wǎng)絡(luò)[15]．因此,本文從無(wú)線傳感器網(wǎng)絡(luò)自身的特性及存在的問(wèn)題出發(fā)，展開(kāi)研究．

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ù)包的傳輸延遲見(jiàn)表1．

表1 傳輸延時(shí)表

簇狀樹形網(wǎng)絡(luò)拓?fù)浜?jiǎn)單實(shí)用，在眾多無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用中被大量采用[16-17].因此，本文采用一個(gè)8節(jié)點(diǎn)的樹形網(wǎng)絡(luò)進(jìn)行仿真評(píng)估,其網(wǎng)絡(luò)拓?fù)鋱D見(jiàn)圖3．為了證明ACW策略的有效性,在SMAC協(xié)議[6]上加載ACW策略,并與原協(xié)議進(jìn)行性能對(duì)比．節(jié)點(diǎn)參數(shù)設(shè)置見(jiàn)表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)系見(jiàn)圖4．由圖可知,離匯聚節(jié)點(diǎn)較近的節(jié)點(diǎn)1～節(jié)點(diǎn)3的隊(duì)列在仿真過(guò)程中長(zhǎng)期處于飽和狀態(tài),其余各節(jié)點(diǎn)的緩存隊(duì)列在仿真開(kāi)始后迅速進(jìn)入飽和狀態(tài),且隊(duì)列被逐漸排空．該仿真過(guò)程持續(xù)1 200 s．仿真中,外圍節(jié)點(diǎn)將數(shù)據(jù)包推送至離匯聚節(jié)點(diǎn)較近的節(jié)點(diǎn),而離匯聚節(jié)點(diǎn)較近的節(jié)點(diǎn)來(lái)不及排空緩存的數(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)系見(jiàn)圖5．由圖可知,離匯聚節(jié)點(diǎn)較近的節(jié)點(diǎn)1～節(jié)點(diǎn)3的隊(duì)列于仿真開(kāi)始時(shí)便迅速進(jìn)入飽和狀態(tài),隨后各節(jié)點(diǎn)的緩存隊(duì)列被逐漸排空,仿真持續(xù)1 800 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)系見(jià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)系

平均能耗是指仿真過(guò)程中各節(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ì)上,通過(guò)平衡網(wǎng)絡(luò)中載荷分布,大幅減少了網(wǎng)絡(luò)中數(shù)據(jù)包的丟失．

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

)

[1] Yick J,Mukherjee B,Ghosal D. Wireless sensor network survey[J].ComputerNetworks,2008,52(12): 2292-2330.

[2] Potdar V,Sharif A,Chang E. Wireless sensor networks: a survey[C]//Proceedingsof2009AdvancedInformationNetworkingandApplicationsWorkshops. Bradford,England,2009: 636-641.

[3] Wan C Y,Eisenman S B,Campbell A T,et al. Overload traffic management for sensor networks[J].ACMTransactionsonSensorNetworks,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]//Proceedingsof2008InternationalConferenceonCommunicationsandElectronics. 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]//Proceedingsof2007InternationalConferenceonConvergenceInformationTechnology. Gyeongju,Korea,2007: 290-294.

[6] Ye W,Heidemann J,Estrin D. An energy-efficient MAC protocol for wireless sensor networks[C]//Proceedingsof2002IEEEINFOCOM. New York,USA,2002: 1567-1576.

[7] Ringwald M,Romer K. BitMAC: a deterministic,collision-free,and robust MAC protocol for sensor networks[C]//Proceedingsofthe2ndEuropeanWorkshoponWirelessSensorNetworks. 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].IEEETransactionsonMobileComputing,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].ACMTransactionsonSensorNetworks,2009,5(4): 1-34.

[10] Hurni P,Braun T. MaxMAC: a maximally traffic-adaptive MAC protocol for wireless sensor networks[C]//Proceedingsof2010EuropeanConferenceonWirelessSensorNetworks. 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]//Proceedingsof2011InternationalConferenceonCommunicationsandMobileComputing. Qingdao,China,2011: 495-500.

[12] Hull B,Jamieson K,Balakrishnan H. Mitigating congestion in wireless sensor networks[C]//Proceedingsof2004InternationalConferenceonEmbeddedNetworkedSensorSystems. 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]//Proceedingsof2003InternationalConferenceonEmbeddedNetworkedSensorSystems. Los Angeles,CA,USA,2003: 266-279.

[14] Zhai H,Fang U. Distributed flow control and medium access in multihop ad hoc networks[J].IEEETransactionsonMobileComputing,2006,5(11): 1503-1514.

[15] Intanagonwiwat C,Govindan R,Estrin D. Directed diffusion: a scalable and robust communication paradigm for sensor networks[C]//Proceedingsof2000InternationalConferenceonMobileComputingandNetworking. 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]//Proceedingsof2007InternationalConferenceonWirelessCommunicationsandMobileComputing. 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]//Proceedingsof2008Sensor,MeshandAdHocCommunicationsandNetworks. San Francisco,CA,USA,2008: 314-322.