能量優先的無線傳感器網絡擁塞緩解機制

蔣 禧， 齊建東， 曹永潔， 趙燕東

(1.北京林業大學信息學院，北京100083；2.北京林業大學工學院，北京100083)

0 引 言

隨著無線傳感器網絡規模的不斷升級以及人們對圖像、視頻、語音等多媒體數據傳輸需求的增多，高密度、大規模部署的無線傳感器網絡和無線多媒體傳感器網絡(wirelessmultimedia sensor network，WMSN)應運而生[1]。較單純傳輸文本類型數據的“傳統”WSN而言，高密度、大規模部署的無線傳感器網絡和無線多媒體傳感器網絡關注點側重在網絡瞬時的大量數據以及圖像、視頻、音頻等多媒體數據的傳輸上。節點在大數據量傳輸的過程中，不可避免地會發生網絡擁塞，從而導致丟包率增加、時延加劇、能耗劇增等現象，影響網絡的穩定性和可靠性。所以，大規模無線傳感器網絡和無線多媒體傳感器網絡中如何緩解網絡擁塞、減少節點能耗、提高網絡生存壽命成為了當前研究中亟需解決的熱點問題之一。

無線傳感器網絡擁塞控制機制的引入就是為了保證網絡傳輸的可靠性、穩定性和時延性等特點，目前研究的算法已較多。ESRT[2]是一種基于節點本地緩沖監測的擁塞檢測機制，根據網絡的當前狀態調整節點傳輸速率，該算法的缺點在于需要Sink節點具有覆蓋整個網絡的通信能力，且對網絡所有節點采用全局統一的速率調整方案，故不適合WSN節點的大規模部署。由C.Wan等人提出的CODA[3]是一種能源有效的擁塞控制模式，節點通過周期性的查看信道負載以及緩沖區占用率來檢測擁塞，使用逐跳速率控制以及閉環的調節的方式來緩解擁塞。Fusion[4]采用了跨層的設計來應對擁塞，它包含了3種機制：Hop-by-Hop的流量控制、速率限制和帶優先級的MAC層處理，每個節點在發送數據包的包頭設置了一個擁塞位，通過檢查緩沖區隊列長度和信道采樣來監測擁塞，一旦節點監測到擁塞發生，就通過擁塞位廣播擁塞信息。Fusion采用令牌桶的方式進行速率限制，可以有效地保證各節點間發送速率的公平性。RCRT[5]是一種提供可靠保證和擁塞控制的傳輸協議，它讓整個網絡的擁塞檢測在Sink端進行，并由Sink端發送全網的速率調節信息。但是，在大范圍的網絡中，遠端節點到Sink節點的報文延時較大，當Sink節點接收到遠端的擁塞信息時再發回控制速率控制報文時，遠端節點的擁塞可能已經緩解或者進一步惡化，這種機制在擁塞控制的準確性和時效性上會大打折扣。

目前，大多數網絡擁塞控制機制主要集中于對源節點發射速率進行調節的思想。本文提出了一種能量優先的無線傳感器網絡擁塞緩解機制，通過對擁塞節點的前一跳節點進行路徑分流調節的思想以緩解網絡中的擁塞狀況。在路徑選擇的過程中，加入了對節點剩余能量狀況的考慮。它克服了速率調節機制運算復雜度較高及權值累加路徑分流機制無法統一單位化的缺點，采用擁塞度和剩余能量順序判斷的方法，降低節點能耗，延長網絡生存壽命。本文采用OMNET++仿真工具進行仿真研究，結果證明了該機制的有效性。

1 能量優先的擁塞緩解機制

本文提出一種能量優先的擁塞緩解機制(priorityofenergy congestion relief mechanism，PECR)，包含兩個部分：①擁塞檢測；②分流調節。過程如下：首先，節點周期性地計算本地緩沖區隊列使用情況，得出節點當前時間t的擁塞度Ct(i)(i為節點編號)，并將當前的擁塞度Ct(i)和剩余能量Pt(i)向其上游節點反饋，上游節點比較其所有可轉發數據包的下游節點的擁塞度Ct(i)和剩余能量Pt(i)值。比較擁塞度是為了避免新路徑建立以后形成新的擁塞，比較剩余能量值是為了避免新路徑建立以后該鏈路由于能量不足而失效。如果當前搜索到的節點滿足條件，即擁塞度C小于設定的閾值，剩余能量P大于設定的閾值，則可以作為新路徑的一跳。然后，從該節點開始按照同樣的方法繼續搜尋下一跳節點，直至建立起一條完整的從擁塞端前一節點到Sink節點的路徑。

1.1 擁塞檢測

有效的擁塞檢測策略是網絡擁塞控制機制的一個關鍵部分。當前比較普遍的檢測方法是基于信道采樣和緩沖區占用的方法[6]。信道采樣是指節點通過監聽信道是否空閑來判斷擁塞，該方法可以獲知信道的繁忙程度，但增加了能量的消耗，并可能導致對擁塞程度的不恰當估計，比如當節點緩沖區內只有幾個數據包待發送時，而信道采樣值卻超過了一定的閾值，此時的擁塞可能是暫時的或者根本不會發生，但是擁塞反饋機制卻可能引起上游節點的一系列速率調節或者分流傳輸操作，導致整個網絡的吞吐量發生頻繁的震蕩，不利于網絡的穩定傳輸。文獻[7]表明，當網絡負載增加時，基于節點緩沖區隊列使用情況的擁塞檢測要好于基于信道采樣的擁塞檢測。

考慮到節點擁塞檢測的有效性，本文提出的擁塞檢測的基本思想為：節點每隔的時間(為一個檢測周期)檢測本地緩沖隊列的使用情況，定義為

在網絡流量不發生異常變動的情況下，可以預測在下一時刻tk+1，節點緩沖區的增量

在本擁塞檢測機制中，通過上一檢測周期數據增量對下一周期的緩沖區占用進行預測的方式，在k時刻，節點檢測到的擁塞度就必須將此增量情況考慮在內，節點i在k時刻的擁塞度C定義為

則推測在第k+1個間隔內節點i將發生網絡擁塞。為緩沖區擁塞的閾值，取值范圍為0到1。

閾值 決定著無線傳感器網絡擁塞檢測的準確度和擁塞緩解的效率。如果 值過小，節點可能在緩沖區占用率還很低的情況下就報告擁塞，引起下一步的分流調節機制，影響對最佳路徑的使用，從而耗費網絡能量，降低網絡生存壽命；如果值過大，節點會對網絡的擁塞狀況無法做出迅速地反應，導致緩沖區隊列溢出，造成大量數據包不必要的丟失，影響網絡傳輸質量。在確定一個 優化值滿足一個特定目標之前，必須綜合考慮節點緩沖區隊列大小、網絡規模、數據傳輸速率以及擁塞檢測周期等復雜因素，本文通過仿真實驗給出對閾值 的測定。

1.2 分流調節機制

無線傳感器網絡的擁塞控制機制必須盡可能地降低節點運算的復雜度，減少擁塞控制報文數量。文獻[8]認為，在速率調節和路徑分流的機制選擇上，基于速率調節的擁塞控制機制對節點性能的要求普遍較高，不利于節點的能耗控制。同時，基于降低源節點發射速率的擁塞緩解機制將會使重要的信息無法及時地到達Sink節點，在多媒體數據傳輸的過程中，這一弊端尤為明顯。所以，在緩解擁塞的過程中，本文在基于路徑分流思想的基礎上，提出如下機制，具體流程如圖1所示。

圖1中無色框體部分為WSN網絡層路由選擇模塊，陰影框體為傳輸層擁塞緩解模塊。網絡層可選擇任意WSN路由協議來選擇最優路徑，擁塞緩解機制獨立于路由選擇模塊存在。

圖1 擁塞緩解機制流程

S1)節點周期性地檢測擁塞信息，并向其鄰居節點反饋擁塞信息報文，報文包含節點編號NodeID、擁塞度Ck(i)、剩余電量Pk(i)字段。

S2)節點接收到所有鄰居節點傳來的擁塞信息報文后，將報文存入鄰居擁塞信息表內，示例如表1所示。

表1 2號節點鄰居擁塞信息

S3)在路由選擇模塊部分，若網絡啟用擁塞緩解機制，則節點將根據鄰居擁塞信息表按擁塞度和剩余能量值順序判斷其選取的最佳下一跳節點i是否發生擁塞Ck(i)小于 ，剩余能量Pk(i)大于 ，若根據路由選擇的最優路徑下一跳節點i均滿足判斷條件，則該下一跳節點即為最優路徑，進而選取該節點轉發數據包。

S4)若根據上述判斷流程該節點未能滿足要求，則進入分流路徑選擇模塊。在鄰居擁塞信息表中將該節點刪除，構建出一個剩余能量滿足最低能量閾值要求的節點集合

在該集合中，選擇擁塞度最低的節點

即為根據擁塞緩解機制選取的臨時最佳路徑，轉發數據包。從下一跳路徑節點開始按照同樣的方法繼續搜尋下一跳節點，直至建立起新路徑。

S5)若節點在臨時備用路徑選取的過程中由于鄰居擁塞信息表中的節點數目過少，無法選取到在保證能量優先的前提下滿足擁塞度小于閾值 的節點，那么節點將轉換回網絡層路由選擇模塊選取其默認的最優路徑進行數據轉發。同時，由于鄰居信息的周期性更新，當原先最優路徑下一跳節點回到擁塞度在閾值 以下同時剩余能量大于閾值 的狀態，則網絡將切換回最佳路徑進行轉發，盡量避免選取臨時路徑。

假設某網絡中2號節點有4個鄰居節點，分別為3、4、5、6。在k時刻分別接收到4個節點的擁塞報文，存入其鄰居節點信息表中，如表1所示。經過路由模塊計算，節點2將選擇3號節點作為其下一跳的轉發路徑，但此時發現 Ck(3)=0.8>0.75(假定擁塞度閾值為0.75)，則判定此時節點3緩沖區內發生擁塞，故放棄該最佳轉發節點，進入分流路徑選取過程。將3號節點信息從鄰居擁塞表中刪除，判斷4、5、6這3個節點的剩余能量是否在0.2(假定剩余能量閾值為0.2)之上，構建出滿足條件的節點集合{4，5}。在該集合中，選擇節點擁塞度最低的節點，此時Ck(4)

在判斷節點擁塞度的同時，本機制引入了節點的剩余能量，與利用多權值累加的路徑分流機制[9]相比，該機制不單純地依賴于 (1 Ck(i))+Pk(i)的總和來選取臨時最佳路徑。①通過權值累加的方法在權值 、的選取上無法精確賦值，尤其是在擁塞度和剩余電量不是在同一單位化的情況下，難以判定兩者的具體權重；②假設在同一單位化條件下 、值均設定為1、1，C、P 對應有兩條路徑分別為 Ck(1)=0.6，Pk(1)=0.4；Ck(2)=0.2，Pk(2)=0.1，則根據該方法選擇的路徑必然為路徑2，但顯然，此時2號路徑節點的能量為0.1，到了瀕臨“死亡”的臨界值，若再選擇該節點轉發數據，該節點很快將會因為能量耗盡而“死亡”，造成路徑黑洞。本文所提方案采用了逐級判定的思想，首先比較擁塞度是否滿足在閾值之內，其次比較節點剩余能量是否在能量閾值范圍內，通過順序比較，避免了雖然節點的某一權值極低，但由于權值總和比其它節點高而被選的場景，貫徹了能量優先的擁塞檢測和緩解的思想。

本擁塞緩解機制的不足之處是當找不到滿足要求的節點時(比如擁塞發生在網絡的邊緣節點)，擁塞無法解除，同時在一定程度上還增加了整個網絡的能耗。但考慮到無線傳感器網絡節點高密度部署、節點大量冗余的特性，擁塞狀況往往集中發生在網絡的中心處，基于此分流機制的擁塞緩解機制具有較強的普遍實用性。

2 網絡仿真

2.1 擁塞閾值 的確定

擁塞閾值 的確定對于PECR協議的擁塞緩解效率、網絡生存時間起到決定性的因素。采用OMNET++仿真工具[10]，在100*100m的范圍內隨機播撒21個節點(其中Sink節點1個，普通節點 20個)，節點信號覆蓋范圍 15m，數據發送速率250kbps，初始能量值為300，網絡層采用最小跳數路由協議(min hop count，MHC)[11]，設置擁塞度 分別為 0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9，1.0，觀察節點能耗變化趨勢。網絡運行200s后各節點能耗損失迥異，現選取有代表性的3個狀態如圖2至圖4所示。

仿真圖示給出，當 =0.6時，整個網絡內各個節點的能量消耗最趨于一致，其它各個狀態下節點能耗不一，有些節點生存期長，而有些節點生存期過短。在該網絡仿真環境下，=0.6是一個經驗最優值，適合于該網絡整體能耗的控制和保證盡可能多節點的生存壽命。節點能量最低閾值 的選取，需要盡可能考慮滿足網絡最大生存時間的因素，一般可以采用10%*MaxPower[12]。

圖2 擁塞度閾值為0.3時的網絡中節點能耗曲線

圖3 擁塞度閾值為0.6時的網絡中節點能耗曲線

圖4 擁塞度閾值為0.9時的網絡中節點能耗曲線

2.2 協議性能對比

基于上述OMNET++仿真環境，從各個節點能耗損失和網絡總體壽命兩項指標上對比最小跳數路由協議、傳統多路徑擁塞控制機制 (ORSF)和本文提出的能量優先擁塞緩解機制(PECR)3項協議。網絡中20個節點的生存時間表現各異，選取位置具有典型代表性的3個節點狀況輸出，如圖5至圖7所示。

圖5 6號節點能耗對比

圖6 10號節點能耗對比

圖7 18號節點能耗對比

6號節點所處區域節點布置比較稀疏，在分流調節過程中無法找到多余的臨時備用節點，故采用了能量優先擁塞緩解模塊的節點生存壽命反而要短于未使用擁塞控制機制最小跳數路由和采用了權值相加路徑分流的傳統多路徑擁塞緩解機制；而10號和18號節點部署與節點密度較大的區域，采用PECR機制的節點的能量隨時間的衰減明顯慢于采用了其它機制的節點。由此我們可以得出，在節點高密度部署，冗余性較強的區域，本擁塞控制機制有著很好的性能表現，而在節點稀疏部署，而同時節點能量、擁塞又有著充分保證的網絡中，本機制的表現不是很盡如人意。

基于3種協議對比下的整個網絡的生存壽命如圖8所示。

圖8 網絡生存壽命比較

所有節點采用PECR擁塞控制機制的網絡生存壽命比不采用任何擁塞控制機制的網絡壽命延長了510.12%，比采用傳統多路徑機制的網絡壽命延長了141.18%。在大數據量傳輸的高密度無線傳感器網絡中，PRCR機制能夠減少節點能耗，提高網絡生存壽命。

3 結束語

本文根據當前無線傳感器網絡大數據量傳輸對性能的基本要求，提出了一種能量優先的擁塞檢測和緩解機制，并對該傳輸控制機制運行的各個階段和細節進行了具體描述和論證，重點討論了擁塞檢測和路徑分流調節兩個環節的具體實現步驟和流程。最后通過OMNET++仿真實驗，對比了分別采用無擁塞緩解、多路徑分流和PECR機制的網絡中節點能耗狀況和整個網絡的生存壽命，仿真結果表明在節點高密度部署的網絡中，PECR機制對無線傳感器網絡能量優先的原則有著很好的保證，顯著提高了網絡整體壽命。

[1] Akyildiz IF,Melodia T,Chowdhury K R.A survey on wireless multimedia sensor networks[J].Computer Netw(Elsevisr),2007,51(4):921-960.

[2] Sankarasubramaniam Y,Akan O,Akyildiz I.ESRT:Event-to-sink reliable transport in wireless sensor networks[C].Proc ACM MOBIHOC 2003,Association of Computing Machinery.Annapolis,Maryland:ACM Press,2003.

[3] Wan C,Eisenman S,Campbell A.CODA:Congestion detection andavoidancein sensornetworks[C].Procof the 1st Int'l Confon Embedded Networked Sensor Systems.Los Angeles:ACM Press,2003:266-279.

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

[5] Paek J,Govindan R.RCRT:Rate-controlled reliable transport for wireless sensor networks[C].Sydney,Australia:Proc 5th ACM International Conference on Embedded Networked Sensor Systems(SenSys'07),2007.

[6] Fang Weiwei,Qian Depei,Liu Yi.Transmission control protocols for wireless sensor networks[J].Journal of Software,2008,19(6):1439-1451.

[7] 孫利民,李波,周新運.無線傳感器網絡的擁塞控制技術[J].計算機研究與發展,2008,45(1):63-72.

[8] Jaewon Kang.Adaptive resource control seheme to alleviage congestion in sensor networks[C].San Jose,CA,USA:Proceedings of the First Workshop on Broadband Advanced Sensor Networks(BASENETS),2004.

[9] 羅娟,唐文勝,王威.一種自適應的無線傳感器網絡擁塞緩解機制[J].計算機工程,2008,34(5):92-94.

[10]OMNET++discrete event simulation system[EB/OL].http://www.omnetpp.org/,2006.

[11]鄭明才,張大方,趙小超.最小跳數路由無線傳感器網絡中的路由數估計[J].計算機工程與應用,2007,43(15):151-156.

[12]Akkaya K,Younis M.An energy-aware qos routing protocol for wireless sensor networks[C].Rhode Island:Proceedings of the IEEE Workshop on Mobile and Wireless Networks,2003.