一種實用的傳感器網(wǎng)絡(luò)擁塞控制算法

摘 要：傳感器網(wǎng)絡(luò)的擁塞不僅導致丟包率增加，影響傳輸性能，還浪費寶貴的能量資源，因此，有效控制擁塞是傳感器網(wǎng)絡(luò)中需要解決的一個關(guān)鍵問題。提出了一種擁塞控制機制（CMCS）。與現(xiàn)有工作不同，CMCS采用基于節(jié)點的緩存隊列長度并結(jié)合擁塞增長系數(shù)來判斷擁塞的變化趨勢，以擁塞節(jié)點為中心的共享信道區(qū)域內(nèi)進行擁塞反饋和速率控制，并采用基于剩余價值的丟包策略。仿真結(jié)果表明，CMCS明顯降低了通信能耗，提高了網(wǎng)絡(luò)的價值吞吐量。

關(guān)鍵詞：傳感器網(wǎng)絡(luò)； 擁塞控制； 擁塞增長系數(shù)； 帶寬分配； 緩存增長空間

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2009)06-2238-03

doi:10.3969/j.issn.1001-3695.2009.06.072

Practical congestion control algorithm for sensor networks

WANG Yan-mei， QIN Shao-hua， HUANG Yong-ping， CAO Jian

(School of Computer Science Information Engineering， Guangxi Normal University， Guilin Guangxi 541004， China)

Abstract:

Congestion in sensor networks not only causes packet loss， but also leads to excessive energy consumption. Therefore congestion needs to be controlled in order to prolong system lifetime. This paper proposed a congestion control mechanism based on congestion state for sensor network (CMCS). Unlike existing work， CMCS innovatively measured congestion degree based on queue length and congestion increasing coefficient in intermediate nodes. CMCS utilized a bandwidth allocation strategy based on buffer increasing space and imposed a packet-discarding scheme based on packet surplus value to control congestion. The result of experiment shows that CMCS achieves efficient congestion control， as a result， it leads to higher energy efficiency and better QoS in terms of both packet loss rate and network value throughput.

Key words：sensor networks; congestion control; congestion increasing coefficient; bandwidth allocation; buffer increasing space

傳感器網(wǎng)絡(luò)能廣泛應用于監(jiān)測、監(jiān)控等領(lǐng)域，它由大量具有感知能力、計算能力和通信能力的傳感器節(jié)點組成，相互協(xié)作地感知、采集和處理監(jiān)測區(qū)域中感知對象的數(shù)據(jù)，并將數(shù)據(jù)沿著多跳無線鏈路傳輸?shù)交?sink節(jié)點)，形成傳感器節(jié)點到sink節(jié)點的多對一通信模式。由于傳感器網(wǎng)絡(luò)帶寬受限，這種通信模式使得大量分組聚集在匯聚區(qū)域，造成信道競爭和沖突增加，從而引發(fā)擁塞。而擁塞會造成網(wǎng)絡(luò)傳輸能力的下降和傳輸時延的增加以及數(shù)據(jù)的丟失，由此產(chǎn)生的重傳又會進一步增加網(wǎng)絡(luò)流量和節(jié)點的能耗。因此，需要對無線傳感器網(wǎng)絡(luò)實施有效的擁塞控制，以保證網(wǎng)絡(luò)可靠的數(shù)據(jù)傳輸。

1 問題描述

無線傳感器節(jié)點處理、存儲和通信能力相對較弱，且通常使用能量有限的電池供電。通信鏈路具有隨機損耗以及易受環(huán)境的影響，所以在設(shè)計擁塞控制協(xié)議時需要考慮以下問題^[1]：a）能量有效性。節(jié)點的擁塞控制操作要盡可能簡單，開銷少，占用節(jié)點的存儲空間要小。b）及時性。擁塞產(chǎn)生后，可能在極短的時間內(nèi)造成大量的數(shù)據(jù)丟失，很快擴散，所以需要預測或及時發(fā)現(xiàn)網(wǎng)絡(luò)擁塞，并在較短時間內(nèi)解除擁塞，避免擁塞擴散。c)保證網(wǎng)絡(luò)傳輸?shù)馁|(zhì)量，如網(wǎng)絡(luò)延時、網(wǎng)絡(luò)吞吐量和分組丟失率等。d)公平性。需要保證網(wǎng)絡(luò)中的節(jié)點有均等的機會發(fā)送數(shù)據(jù)。

擁塞檢測方法主要包括基于緩存長度的檢測^[2~4]和基于信道采樣^[4，5]的檢測。基于緩存長度的檢測方法認為，緩存數(shù)據(jù)隊列占用越長，說明節(jié)點發(fā)送數(shù)據(jù)的機會越少。由于鄰居節(jié)點競爭使用共享的無線信道，這將導致附近區(qū)域需要發(fā)送的數(shù)據(jù)越多，就越有可能發(fā)生擁塞。它通常設(shè)定一個閾值，如果瞬時的緩存隊列占用長度超過這個閾值，就認為發(fā)生了擁塞。這種方法的優(yōu)點是實現(xiàn)非常簡單，幾乎沒有額外的開銷。但若檢測閾值設(shè)置較大，那么當數(shù)據(jù)占用緩沖區(qū)的大部分時才檢測到擁塞狀態(tài)，不利于及時解除擁塞。此外緩存中數(shù)據(jù)隊列長度只能反映節(jié)點的接收分組速率與發(fā)送分組速率的關(guān)系，間接地刻畫網(wǎng)絡(luò)的流量狀況。Wan等人^[4]指出，單獨的緩沖區(qū)占用情況不是一個可靠的擁塞檢測指示。

基于信道采樣的檢測方法依據(jù)的是如果出現(xiàn)擁塞，擁塞區(qū)域內(nèi)的節(jié)點忙于競爭無線信道發(fā)送分組，無線信道連續(xù)處于忙狀態(tài)。信道采樣的目標是獲得當前信道利用率的一個估計，這個估計作為擁塞的指示。但是，信道利用率與擁塞的關(guān)系依賴于MAC協(xié)議，如使用TDMA信道可以在幾乎飽和的情況下不影響吞吐量；而CDMA協(xié)議存在最大的信道利用率，網(wǎng)絡(luò)流量過大引起信道沖突，造成網(wǎng)絡(luò)的吞吐量減少。當信道利用率在最大利用率附近時認為網(wǎng)絡(luò)出現(xiàn)了擁塞。為了準確及時地發(fā)現(xiàn)無線信道的忙閑，需要連續(xù)采樣信道狀態(tài)，因而會消耗節(jié)點較多的能量，且需要底層通信協(xié)議的支持^[1]。

以上兩種檢測技術(shù)都沒有考慮到這樣一個事實，為了最大限度地利用帶寬資源，提高網(wǎng)絡(luò)的吞吐量，網(wǎng)絡(luò)工作在輕度擁塞狀態(tài)應該是較為理想的^[6]，尤其在傳感器網(wǎng)絡(luò)中，節(jié)點的資源非常珍貴。如何利用有限的帶寬資源來最大化網(wǎng)絡(luò)的吞吐量，但又不導致?lián)砣罎F(xiàn)象，這是本文關(guān)注的主要問題。基于此，本文提出了一種新的擁塞控制機制（congestion control mechanism based on congestion state，CMCS），采用基于節(jié)點緩沖器占有率和擁塞增長系數(shù)來判斷擁塞的變化趨勢。當檢測到擁塞會造成節(jié)點傳輸性能下降時，則以擁塞節(jié)點為中心進行擁塞反饋和帶寬分配；并在丟包策略中，綜合考慮分組的服務(wù)質(zhì)量和節(jié)點發(fā)送數(shù)據(jù)的公平性。

2 CMCS擁塞控制算法

考慮由N個隨機部署的無線傳感器節(jié)點形成的網(wǎng)絡(luò)，其應用場景為基站模式。該模式是傳感器網(wǎng)絡(luò)應用最為廣泛的情形，傳感器節(jié)點隨機部署在一個方形區(qū)域內(nèi)并保持靜止，數(shù)據(jù)匯聚節(jié)點（sink節(jié)點）位于方形觀測區(qū)域的外側(cè)。所有傳感器節(jié)點是同構(gòu)的并具有相同的初始能量。每個節(jié)點的通信半徑為r，任意兩個節(jié)點的平面距離如果小于等于r，那么它們可以直接通信。

CMCS包含三個部分：基于節(jié)點緩存占有率和擁塞增長系數(shù)的擁塞檢測、擁塞區(qū)域反饋及速率分配算法和節(jié)點丟包策略。當節(jié)點緩存隊列長度超過一個閾值時，啟動擁塞檢測，若節(jié)點在一個時段內(nèi)持續(xù)出現(xiàn)過載行為，則認為節(jié)點出現(xiàn)了擁塞，然后擁塞節(jié)點通告擁塞并降低共享信道內(nèi)活躍鄰居節(jié)點的發(fā)送速率來增大其可用的帶寬，同時啟動丟包策略來丟失剩余價值最小的分組。

2.1 擁塞檢測

擁塞是一種持續(xù)過載的網(wǎng)絡(luò)狀態(tài)，即在一時間段內(nèi)節(jié)點接收到的分組個數(shù)持續(xù)大于節(jié)點發(fā)送分組的個數(shù)。為了最大限度地利用資源，節(jié)點工作在輕度擁塞狀態(tài)時應該是允許的，此時資源達到充分利用的程度，網(wǎng)絡(luò)的吞吐量也處于最佳狀態(tài)。但這也增加了滑向擁塞崩潰的可能性，所以需要一定的擁塞控制機制來加以區(qū)別和約束。本文設(shè)置緩存隊列閾值Lsys，當緩存隊列瞬時長度小于等于Lsys，認為節(jié)點處于輕度擁塞狀態(tài)，利用節(jié)點的緩沖空間暫時緩存等候服務(wù)的分組，當節(jié)點負載減少時，擁塞可以自動恢復；當緩存隊列瞬時長度大于Lsys，認為節(jié)點有可能滑向擁塞崩潰狀態(tài)，此時CMCS啟用擁塞檢測技術(shù)來判斷這一變化趨勢。

CMCS采用節(jié)點的接收速率與發(fā)送速率之比來定義節(jié)點的擁塞增長系數(shù)：CN=Vr/Vs。其中：Vr為節(jié)點的接收速率；Vs為節(jié)點的發(fā)送速率。擁塞增長系數(shù)作為對節(jié)點負載情況的近似度量能較好地刻畫節(jié)點的擁塞情況，擁塞增長系數(shù)同樣也反映了緩存隊列的變化趨勢。如果CN>1就表示緩存隊列變長，擁塞程度增加。本文采用緩存隊列長度超過Lsys、且擁塞增長系數(shù)CN>1來標志節(jié)點發(fā)生擁塞，采用CN<1來標志擁塞得到緩解。這種擁塞檢測方式幾乎不消耗額外的能源而且計算復雜度低，適合傳感器節(jié)點的特征。具體檢測過程：當緩存隊列瞬時長度Lnow>Lsys，則啟動定時器T，收集在T時段內(nèi)發(fā)送的分組Ps和接收的分組Pr ，計算擁塞增長系數(shù)CN=Pr/Ps(CN默認值等于1)。如果CN>1，則認為擁塞狀態(tài)具有一定的持續(xù)性，很可能導致緩存溢出，并趨向擁塞崩潰，所以需加以控制。

2.2 擁塞反饋及速率控制算法

本文從兩個方面考慮如何解決擁塞問題：a）增加網(wǎng)絡(luò)資源；b）降低服務(wù)質(zhì)量。增加網(wǎng)絡(luò)資源是通過限制共享信道上通信節(jié)點的發(fā)送速率來增加擁塞節(jié)點的可用帶寬，并在鄰居節(jié)點的路由表中標記擁塞節(jié)點；在T時段內(nèi)擁塞節(jié)點不再參與路由，即降低活躍鄰居節(jié)點的服務(wù)質(zhì)量來增加擁塞節(jié)點的網(wǎng)絡(luò)資源，目的是緩解擁塞，將數(shù)據(jù)流量降低到節(jié)點能力范圍之內(nèi)，防止繼續(xù)丟包。

CMCS采用擁塞增長系數(shù)CN與緩存隊列瞬時長度Lnow的乘積定義了節(jié)點的緩存增長空間：Bis=CN×Lnow。緩存增長空間反映了節(jié)點的負載情況，間接表示節(jié)點的擁塞程度。為了減少控制消息的開銷、降低算法的復雜性，擁塞節(jié)點通過在分組中捎帶節(jié)點的緩存增長空間Bis和發(fā)送速率rate的信息來通告擁塞并進行速率調(diào)節(jié)。活躍鄰居節(jié)點監(jiān)聽到擁塞節(jié)點的分組后，根據(jù)控制信息和自己的Bis來調(diào)整自己的發(fā)送速率，即對于任一活躍鄰居節(jié)點i，緩存增長空間為Bisi，其最大速率ratei≤Bisi/Bis×rate。

假定節(jié)點i在調(diào)整前的速率大于新計算的速率ratei，則將自己的發(fā)送速率調(diào)整為新的ratei，否則維持原值。為防止速率抖動，同時最大限度利用帶寬，節(jié)點i采用保守逐增的方式來調(diào)整發(fā)送速率，每隔時段T若沒有接收到速率控制的消息，則根據(jù)Bisi，利用式（1）增加發(fā)送速率ratei。通過多輪調(diào)整，直到實際速率比期望速率的差值小于給定的ε。

ratei=ratei+Bisi/Bis×|rate/ratei-1|×ratei（1）

2.3 丟包策略

當節(jié)點的負載超過其服務(wù)能力時，節(jié)點上的緩存為等候服務(wù)的分組提供一定的保護。然而，若此超載狀況具有一定的持續(xù)性，當緩存空間被耗盡時，節(jié)點只能丟棄分組。表面上，增大緩存空間可以防止由于擁塞引起的分組丟棄，但隨著緩存的增加，端到端的時延也相應增大，而分組的生存期是有限的，超時的分組同樣需要重傳。因此，過大的緩存空間倒有可能妨礙擁塞的恢復，因為過時分組白白浪費了網(wǎng)絡(luò)的可用帶寬。所以當檢測到擁塞時，CMCS啟動丟包策略，丟棄過時分組以充分利用有限帶寬，最大程度地確保重要數(shù)據(jù)的及時可靠傳輸。本文依據(jù)系統(tǒng)預先設(shè)定的緩存隊列參數(shù)Lmin、Lmax及節(jié)點擁塞增長系數(shù)CN，結(jié)合Blue^[7]算法來標志丟包概率，當計算的丟包概率大于系統(tǒng)閾值，根據(jù)剩余價值來丟棄價值最小的分組，提高網(wǎng)絡(luò)的價值吞吐量。

1)丟包概率計算 每隔時間freeze_time計算節(jié)點擁塞增長系數(shù)CN，并獲取緩沖器瞬時長度L來計算丟包概率Pd，丟包概率計算如算法1所示。其中：Llen表示緩存隊列的容量；δi表示當發(fā)生擁塞且CN>1時Pd的增加量；δ2表示當信道空閑或CN≤1時Pd的減少量。一般來說，δ1要比δ2大很多，這主要是因為當擁塞控制太保守或太激進時，均會導致信道使用率很低；而丟包只發(fā)生在擁塞控制太保守時。通過賦予丟包事件更大的比重因子，丟包策略能夠?qū)ν话l(fā)流量作出及時的響應。

算法1 丟包概率計算算法

upon packet loss(or L＞Lmin) event:

if ((now-last_updatte)>freeze_time CN>1){

 if(L＞Lmax) Pd=Pd+δ1*(1+(L-Lmax)/Llen);

 else Pd=Pd=Pd+δ1*(1-(Lmax-L)/Llen)；

 last_update = now;}

upon link idle (or CN≤1 ) event:

if ((now-last_update)>freeze_time){

 Pd=Pd-δ2;

 last_update = now;}

2)數(shù)據(jù)分組的剩余價值計算 傳感器網(wǎng)絡(luò)缺少有效的時鐘同步機制，本文采用在分組中攜帶剩余生存期的方法來實現(xiàn)分組的實時傳輸。在傳輸過程中，每個分組進入節(jié)點時打上時間戳，離開時通過計算在該節(jié)點上服務(wù)時間來更新分組的剩余生存期，如式（2）所示：

ttl=ttl-(toff-ton)（2）

其中：toff為分組離開節(jié)點時的時間戳； ton為分組進入節(jié)點打上的時間戳；ttl為分組的剩余生存期。分組的剩余價值隨著剩余生存期的減少呈線性遞減，當分組的ttl≤0時，表示分組已過時，直接丟棄分組。

本文考慮分組p的剩余生存期、可靠性和傳輸跳數(shù)來計算分組的剩余價值。根據(jù)剩余價值來決定分組的丟棄順序，其計算方法如式（3）所示：

value=hop×reliable×(ttl-(toff-ton))（3）

其中：hop為分組p的傳輸跳數(shù)，傳輸跳數(shù)越大，其重傳的成本也就越高，相應價值也就越高；reliable為分組p的可靠性，可靠性越高，其價值也越高。

3 仿真結(jié)果

使用OMNeT++ 3.2^[8]作為仿真工具，這是一款面向?qū)ο蟮木W(wǎng)絡(luò)仿真軟件。仿真平臺在Linux下搭建，實驗在1000×1000的區(qū)域內(nèi)隨機分布了100個node節(jié)點，節(jié)點的通信范圍為190 m。在相同的節(jié)點分布條件下，對CMCS和CODA進行對比分析實驗。網(wǎng)絡(luò)應用的底層支撐算法采用類似802.11 DCF 的MAC 算法和AODV 路由算法。為了模擬擁塞情況，每個源節(jié)點產(chǎn)生分組的速率為100 pkt/s，分組長度為512 Byte，仿真時間為100 s。主要從三個方面評估CMCS算法的性能，即網(wǎng)絡(luò)的吞吐量、平均丟包價值和通信能耗。

仿真結(jié)果如圖1~3所示，其中平均丟包價值是指丟棄分組的剩余價值平均值。隨著傳輸數(shù)據(jù)量的增加，由于傳感器網(wǎng)絡(luò)的通信模式，很容易造成熱區(qū)。CODA并不區(qū)分擁塞的變化趨勢，通過信道采樣來檢測擁塞；而CMCS通過判斷擁塞的變化趨勢來決定是否進行擁塞控制。若當前的網(wǎng)絡(luò)擁塞不是一種穩(wěn)定狀態(tài)，當負載減少時，擁塞可以自動恢復，那么就不需要進行擁塞控制。所以與CODA相比，CMCS能最大限度地利用系統(tǒng)資源，避免了不必要的擁塞處理，且提高了網(wǎng)絡(luò)的吞吐量。當檢測到網(wǎng)絡(luò)擁塞狀態(tài)具有一定的持續(xù)性時，CMCS采用以擁塞節(jié)點為中心的捎帶方式進行擁塞反饋和速率分配，不需要發(fā)送額外的控制消息，并根據(jù)剩余價值來丟棄價值最小的分組。與CODA相比降低了丟包價值，改善了網(wǎng)絡(luò)的價值吞吐量。



4 結(jié)束語

傳感器網(wǎng)絡(luò)的多對一通信方式、無線鏈路的相互干擾、網(wǎng)絡(luò)的動態(tài)變化和資源受限等特性，使得傳感器網(wǎng)絡(luò)容易出現(xiàn)擁塞，嚴重影響網(wǎng)絡(luò)的QoS傳輸性能和生存周期，因此擁塞控制成為傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量保障機制的關(guān)鍵技術(shù)之一。本文通過分析現(xiàn)有傳感器網(wǎng)絡(luò)中的擁塞檢測技術(shù)，提出了一種基于節(jié)點緩沖器占有率，并結(jié)合擁塞增長系數(shù)的方法判斷擁塞變化趨勢。當檢測到節(jié)點擁塞狀態(tài)具有一定持續(xù)性時，采用以擁塞節(jié)點為中心的捎帶方式進行擁塞反饋和速率分配，當擁塞的持續(xù)性導致數(shù)據(jù)傳輸性能下降時，采用基于剩余價值的丟包策略。仿真實驗表明，該算法在網(wǎng)絡(luò)的價值吞吐量和降低通信能耗方面均表現(xiàn)出很好的性能。

參考文獻：

[1]孫利民，李波，周新運. 無線傳感器網(wǎng)絡(luò)的擁塞控制技術(shù)[J]. 計算機研究與發(fā)展， 2008，45(1):63-72.

[2]AKAN O， AKYILDIZ I F. Event-to-sink reliable transport in wireless sensor networks[J]. IEEE/ACM Trans on Networking，2005，13(5):1003-1016.

[3]DRESSLER F. Locality driven congestion control in self-organizing wireless sensor networks[C]//Proc of the 3rd International Confe-rence on Pervasive Computing.2005.

[4]WAN C Y， EISENMAN S B， CAMPBELL A T. CODA: Congestion detection and avoidance in sensor networks[C]//Proc of the 1st ACM Conference on Embedded Networked Sensor Systems.New York: ACM Press，2003:266-279.

[5]KARENOS K， KALOGERAKI V， KRISHNAMURTHY S V. Cluster-based congestion control for supporting multiple classes of traffic in sensor networks[C]//Proc of the 2nd IEEE Workshop on Embedded Networked Sensors. 2005:107-114.

[6]林闖，單志廣，任豐原.計算機網(wǎng)絡(luò)的服務(wù)質(zhì)量(QoS)[M]. 北京:清華大學出版社， 2004:74.

[7]FENG W， SHIN K G， KANDLUR D D， et al. The blue active queue management algorithm[J]. IEEE/ACM Trans on Networking， 2002，10(4):513-528.

[8]VARGAR A. OMNeT++ object-oriented discrete event simulation system 3.2 version user manual [EB/OL].[2006]. http://www.omnetpp.org/doc/manual/usman.html.