一種基于GM(1,1)的分簇WSNs擁塞檢測與控制方案*

陳 輝,王 楓

(安徽理工大學計算機科學與工程學院,安徽 淮南 232001)

隨著無線傳感器網絡研究的逐步深入,其被廣泛地應用在軍事、環境監測、災害預警等方面,然而因網絡擁塞引起的延遲、死鎖等現象對網絡數據的傳輸具有很大威脅,因此擁塞控制成為大規模傳感器網絡應用研究的重點方向之一。無線傳感器網絡中節點位置分布、工作環境、拓撲變化等因素都有可能引發傳輸鏈路的擁塞,進而導致網絡響應時間變長、帶寬資源占用、節點能量消耗過快等負面影響[1-2]。

目前,分簇路由結構(Clustering structure)作為無線傳感器網絡發展的重要方向,具有機動性強和便于管理等眾多優勢[3],在分簇結構下網絡節點會根據一定規則自發聚類成眾多的子網絡,即形成多個簇(Cluster)。傳感器節點采集到的數據需要在簇首(Cluster Head)中轉后才能發送至匯聚節點(Sink)。在大規模網絡下簇首還要起到數據中繼的功能,即在各個簇首間采用“多跳”的方式將其中某個簇的數據發送給Sink[4-6]。由于這些簇首既是數據的發送者又是數據的轉發者,處在某些鏈路特殊位置的簇首可能會承擔過重的網絡負載,是潛在的網絡擁塞位置[7-8]。因此,在分簇網絡結構下對擁塞重點位置的流量控制是預防網絡擁塞的主要方法。

1 相關工作

針對無線傳感器網絡由擁塞造成網絡可靠性降低的問題,對擁塞的檢測是進行下一步擁塞控制的前提和基礎。目前網絡擁塞的檢測方法主要有:①隊列長度:判斷節點緩沖區占用率BO(Buffer Occupancy)是否超過某一閾值來確定擁塞情況,這種方式僅針對單個節點,缺少對信道負載和競爭程度的預測。②信道負載:節點監控信道內數據業務的繁忙度來判斷網絡擁塞情況。該方式準確度較高,但長時間的監控會大幅提高網絡開銷。③擁塞度:節點通過計算分組發送與接收率比值反映擁塞度[9-10],并為不同環境設定不同的擁塞準則,該方式靈活度較好。

在擁塞控制的研究方面國外學者先后提出了CODA、ESRT、Fusion等算法[11-13]。其中CODA(Congestion Detection and Avoidance in Sensor Networks)是用于端到端的擁塞控制算法,它采用基于接收者信道采樣的擁塞檢測、開環逐跳反向壓力和閉環多源調節機制進行擁塞控制,其缺點是沒有考慮鏈路的傳輸可靠性,且閉環多源調節機制易造成更大的時延。ESRT(Event-to-Sink Reliable Transport)是面向事件的算法,該算法根據網絡工作特征為節點設置5個不同狀態,并為其設定不同的調速規則。此算法擴展性較差,大規模部署時值得商榷。Fusion采用跨層設計應對擁塞,以清空父節點隊列為目標加速數據的流動,但只采用緩存占用率作為擁塞判斷依據,存在一定局限性。國內段文軒等人[14]提出的SCATP算法主要是采用分流的思想,在使用ARMA模型預測擁塞發生后尋找其他不易擁塞且代價小的路徑傳輸,多跳鏈路同時飽和時則開辟新路徑傳輸,此算法在存在多處擁塞時對鏈路的整體可靠性要求較高。

本文提出的擁塞預測及控制算法CMETR(Congestion Mitigation Base on EDGM and Throughput Rate,EDGM:Even Difference Grey Model)以簇為單位,在簇首建立均值GM(1,1)預測模型,通過監測簇首的實時數據吞吐量來預測其未來時刻的繁忙程度,并根據簇首忙閑程度自適應設置合適的簇內節點數據采集頻率。在簇頭空閑時,設置正常的理想采樣頻率,保證監測效果;在簇頭繁忙時則適當降低節點的數據采集頻率,從而減輕簇首所在簇的數據發送壓力,達到網絡負載與數據精度間的平衡。由于簇首在預測與處置過程中采用分布式自適應的解決機制,與其他簇相互獨立,所以該算法不受鏈路限制,具有良好的公平性和可擴展性。

2 基于GM(1,1)的擁塞檢測方法

2.1 網絡擁塞問題描述

分簇結構的無線傳感器網絡受組織結構和部署環境的限制,一旦發生監測事件,附近多個節點會將監測到的數據同時向Sink節點匯聚。隨著網絡流量的增大,數據包就會在中轉簇首的緩存中堆積,引起中轉節點傳輸效率的下降,當緩存發生溢出時就會出現丟包現象,進而發生網絡阻塞。

如圖1所示,簇1與Sink節點間的數據通信需要經過簇3和簇5中轉,而簇3和簇5本身也承擔著自身數據上傳的任務,一旦某一時刻數據大量經過這兩個簇,無疑會給中轉節點增加過重的負載,由過重負載引發的網絡擁塞則會給Sink成功接收原始節點發送的數據造成很大影響,所以如果能夠在擁塞發生前進行短期的流量預測,并且及時進行相應的負載緩和處置,這樣就能夠提前避免擁塞且能降低相應節點的能量開銷。

圖1 分簇結構下網絡的擁塞原理

2.2 擁塞檢測方法描述

為真實反映網絡的擁塞情況,我們將各簇首的實時吞吐量作為判斷擁塞的基本依據,主要方法是通過預測出未來一段時間內簇首需要處理的數據吞吐量來判斷未來網絡的擁塞程度。為減少簇首開銷,在簇首設置周期為T的循環擁塞檢測機制,簇首每隔一個周期T就選取等間隔t抓取n組(根據灰色模型的成立條件,n≥4)連續時刻t1,t2,…,tn的吞吐量作為預測下一時刻即tn+1時刻吞吐量的預測樣本,原理如圖2所示。在實際應用中先設定n值,然后導入流量預測模型預測出tn+1時刻簇首的吞吐量TR(Throughput Rate),并依據TR反映的節點繁忙度為接下來的擁塞控制提供依據。

圖2 擁塞預測基本原理

2.3 擁塞預測模型的建立

由于無線傳感器網絡輕量級的特點,這就要求所采用算法盡可能簡便高效。根據節點能夠提供數據的小樣本、貧信息特性以及網絡流量的線性特征和短期預測的實際需求,我們選擇鄧聚龍教授創立的GM(1,1)灰色預測模型[15],鑒于網絡流量序列平滑的特點和數據累加后指數率較強的特性選擇其EDGM(Even Difference Grey Model)均值差分形式[16]。擁塞預測模型建立過程如下:

Step 1 選取簇首檢測周期內抓取到的4個時刻吞吐量作為預測特征序列的觀察值:

X(0)={x(0)(1),x(0)(2),x(0)(3),x(0)(4)}

(1)

式中:x(0)(i)(i=1,2,3,4)為第i個數據吞吐量樣本,隨后計算其一次累加生成的序列(1-AGO):

X(1)={x(1)(1),x(1)(2),x(1)(3),x(1)(4)}

(2)

Step 2 根據累加算子的性質,X(1)近似服從指數增長規律,其X(1)的緊鄰均值生成序列為:

Z(1)={z(1)(2),z(1)(3),z(1)(4)}

(3)

Step 3 隨后建立均值形式的灰差分方程:

x(0)(k)+az(1)(k)=b(k=2,3,4)

(4)

式中:-a為發展系數,b為灰作用量,將x(0)(k)和z(1)(k)代入式(4)后,樣本預測灰差分方程化為:

(5)

Step 4 將離散差分方程(5)近似為連續的微分方程即可得到GM(1,1)模型的白化形式:

(6)

由式(4)可知Y=Bu,所以u=(BTB)-1BTY,用最小二乘法估計GM(1,1)的兩個參數a、b,隨后代入其白化方程,可得出時間響應函數,即預測函數:

(7)

Step 5 還原之前計算的累加算子,得到基于X(0)的TR預測公式(k=4):

(8)

Step 6 最后對樣本數據進行殘差檢驗,檢測模型的預測效果,令ε(i)為殘差,預測精度為P0:

(9)

P0=(1-εave)×100%

(10)

3 以簇為單位的擁塞控制方案

3.1 網絡擁塞度判斷

為了判斷未來網絡擁塞趨勢和進行提前處置,首先采用簇首數據吞吐量的預測值TR與提前設定的判斷閾值作比較來確定節點的負載壓力,隨后才能根據控制規則為簇內節點設置合適的數據采集頻率。為便于描述,定義如下幾個變量參數,如表1所示。

表1 變量參數定義

圖3 網絡擁塞變化特性

因為節點的吞吐量變化與數據業務的流量變化之間并不是簡單的正相關,實際情況下簇首的吞吐量與數據流量的變化特性如圖3所示。當某一時刻簇首的吞吐率上升至峰值閾值后網絡會發生“死鎖”現象,隨后其吞吐量會快速下降。所以判斷網絡擁塞趨勢不能單獨使用簇首數據吞吐量TR一個參考因子,但是簇首緩沖區的占用情況卻可以明確區別出TR

3.2 變頻采集規則

由于多數網絡體系中傳感器節點采用數據等間隔采集、周期性上傳的原則,如果采集間隔設置過大,則有可能漏掉重要數據;設置過小則會產生相應的數據冗余。所以綜合考慮吞吐量和節點緩存占用率,在進行節點擁塞度判斷后再執行控制策略,為此設簇內節點的數據采集頻率為f(次/min)。由于頻率參數在WSNs中不便直接調整,因此在實際應用時可通過在每輪預測后調整簇內節點的數據采集間隔時間(t=1/f)來實現。根據目前主流WSNs網絡主控芯片中定時器特點,采集間隔時間需精確到其定時器中斷溢出時間的整數倍。另外,設fmax為最佳精度節點采集頻率,即最高監測效果下的采集頻率,fmin為最小精度采集頻率,即確保網絡監測可靠性下可接受的最小數據采集頻率,BOmax為簇首緩存的最大臨界占用率。具體設定如下規則:

規則1 當簇首預測的未來吞吐量TR≤NTR,且此時BO≤BOmax時,判斷網絡為較空閑狀態,設置其簇內節點的采集頻率為最佳精度采集頻率fmax。

規則2 如果簇首預測的未來吞吐量TR≤NTR,且實時的BO>BOmax時,判斷網絡為嚴重擁塞,設置其簇內節點的采集頻率為最小精度采集頻率fmin。

規則3 如果簇首預測的未來吞吐量TR>NTR,且TR≤ PTR,實時的BO≤BOmax時,判斷網絡為較擁塞狀態,設置其簇內節點的采集頻率為f,其計算方法為式(11)所示。

f=fmax-δ(TR-NTR)2

(11)

式中:δ為采集頻率的幅度調節參數,由于fmin已知,對應的TR值即為PTR,即δ=(fmax-fmin)∕(PTR-NTR)2,代入式(11)可得:

(12)

規則4 如果簇首預測的未來吞吐量TR>NTR,且實時的BO>BOmax時,判斷網絡為嚴重擁塞,設置其簇內節點的采集頻率為最小精度采集頻率fmin。

規則5 執行TR預測后,在進行殘差檢驗時若樣本的誤差過大,判斷預測數據會出現失真,簇首不進行擁塞判斷。

綜上,簇首采用的CMETR擁塞檢測與控制算法的具體流程如圖4所示。

圖4 簇首擁塞檢測與控制流程

4 仿真及性能分析

本文采用MATLAB對CMETR算法進行仿真。首先在100×100的矩形區域內建立一個由仿真傳感器節點組成的網絡,所有節點隨機分布,基礎分簇路由協議選擇HEED協議[17],因為其簇首競選主要以節點剩余能量和通訊代價為依據,適用于大規模網絡的部署,而且其分簇速度更快,也能產生更合理的網絡拓撲。具體仿真實驗參數配置如表2所示。在分簇穩定后為簡化仿真過程,采用實時監測與上傳模式,且簇首采用多跳(Multihop)方式實時轉發給Sink。所有簇設置初始采集頻率為fmax。

表2 仿真實驗參數配置

4.1 基于GM(1,1)模型的預測性能

為了測試基于EDGM所建模型的擁塞預測效果,部署節點數量為150,實驗中簇首吞吐量的抓取間隔為2 s,由于仿真時間為600 s,周期T為60 s,所以實際產生了10輪預測TR值。

隨機選取14個生成簇首中的一個簇首,并截取其600 s仿真過程中前兩輪預測周期內實際預測情況,如圖5所示。從圖5可以看出預測效果整體穩定,能較準確的預測出簇首數據流量走勢。

圖5 前兩輪吞吐量實際預測效果

圖6 無擁塞控制和使用CMETR控制的HEED協議

4.2 CMETR擁塞控制性能

為驗證CMETR算法的擁塞控制效果,在同樣的150節點網絡中,我們加入原始HEED協議作為實驗對照。通過增大簇內節點的基礎數據包規模來模擬大數據流量下對網絡的沖擊,并觀察網絡節點的轉發熱度。從圖6(a)中可以看出在無任何擁塞控制算法下,大流量數據會使某些重點簇首數據吞吐量過大,形成擁塞熱區。但在圖6(b)中經過CMETR算法對網絡流量進行控制后,熱區內簇首數據壓力顯著減小,網絡擁塞程度明顯緩解。

為了進一步測試CMETR在不同規模網絡下的擁塞控制性能,我們增加網絡節點規模到300個。并選取端到端延遲作為衡量指標,端到端延遲即數據分組從源節點到達Sink節點的總時間,是源簇首發送等待時間、中轉簇首中轉等待時間和傳播時延之和。從圖7的對比結果發現當網絡規模從150節點擴大至300節點后其整體延遲增加了100 ms左右,主要原因是網絡規模擴大一倍,一些位置的簇首需要承擔更重的轉發任務。另外可以看出當數據吞吐量超過100 kbit/s的安全閾值后,網絡開始進行擁塞控制,隨著數據吞吐量繼續上升至峰值后節點的端到端延遲開始趨于無窮大,這主要是因為中轉節點出現了緩存溢出。綜合來看在節點數量相同的情況下,CMETR要比原生HEED協議多出90 kbit/s左右的網絡承載力。

綜上可知,CMETR算法在網絡發生死鎖前能明顯降低節點的傳輸延遲,在不同規模的網絡環境里都可在一定程度上提高中轉節點對大流量數據的承受能力。

圖7 網絡延遲對比

4.3 CMETR與CODA性能對比

CODA算法是經典的擁塞控制算法,其采用通過抑制源節點發送速率或者丟棄分組的方法,本質上也是基于對數據發送端的流量控制。所以我們對比CMETR和CODA算法的擁塞控制性能,并截取150節點網絡下600s仿真時間內的兩種算法BO占用率、網絡抖動率和網絡剩余能量作對比。其中網絡抖動率即網絡延遲的變化量,是反映網絡穩定性重要指標,具體如式(13)所示。

(13)

式中:ti和tj分別為數據包i和數據包j端到端包的延遲時間,i,j為包序號。

由圖8可知:網絡初始化后,面對大規模數據涌入,CMETR與CODA的緩存占用率都在80%以上,但CMETR要比后者整體偏低10%左右,存在更多數據空間;由圖9可看出CMETR算法由于采用了提前處置機制,可以提前調整網絡流量。因此,相同條件下其抖動率更小,網絡整體性能更穩定。即在應對突發擁塞時,CMETR對發送流量的控制比CODA算法更好。

圖8 簇首緩存占用率對比

圖9 網絡抖動率對比

為比較兩種算法的能耗特性,在600 s仿真結束后計算兩種算法下節點的能量剩余百分比,具體能耗模型采用一階無線電模型,收發l bit數據且距離為d的能耗ET(l,d)和ER(l)如式(14)和式(15):

(14)

ER(l)=ER-elec(l)=l·Eelec

(15)

圖10 節點剩余能量對比

當任意兩接收節點與發送節點間距離小于d0時使用自由空間模型,反之使用多路衰減模型,Eelec是發射和接收電路消耗能量為50 nJ/bit,εfs和εmp是兩種模型的功放能耗分別為50 pJ/(bit/m2)和0.001 3 pJ/(bit/m2),由圖10對比可知:CMETR算法相對CODA可以節約大約11%的能耗,有更好的節能特性。

5 結束語

本文針對分簇無線傳感器網絡的擁塞問題,提出了一種新型的網絡擁塞檢測與控制算法CMETR。該算法首先利用GM(1,1)灰色模型來短期預測簇首未來的流量情況,并根據預測結果自動調節簇內節點數據采集頻率對即將到來的網絡擁塞進行預先處置。由于算法獨立應用于各個簇首,所以局部降低節點數據采集頻率的方式并不會對全網的可靠性造成大的影響。仿真結果表明CMETR擁塞控制算法能夠對鏈路重點位置的擁塞進行提前控制,而且能在一定程度上降低節點開銷,延長網絡壽命。

[1] Sergiou C,Antoniou P,Vassiliou V. A Comprehensive Survey of Congestion Control Protocols in Wireless Sensor Networks[J]. IEEE Communications Surveys and Tutorials,2014,16(4):1839-1859.

[2] Kafi M A,Djenouri D,Ben-Othman J,et al. Congestion Control Protocols in Wireless Sensor Networks:A Survey[J]. IEEE Communications Surveys and Tutorials,2014,16(3):1369-1390.

[3] 尚鳳軍,任東海. 無線傳感器網絡中分布式多跳路由算法研究[J]. 傳感技術學報,2012,25(4):529-535.

[4] 陳炳才,么華卓,楊明川,等. 一種基于LEACH協議改進的簇間多跳路由協議[J]. 傳感技術學報,2014,27(3):373-377.

[5] 周冬鑫,金文光,容志能. 基于分層的無線傳感網絡多跳分簇路由算法[J]. 傳感技術學報,2011,24(1):73-78.

[6] 蔣暢江,石為人,唐賢倫,等. 能量均衡的無線傳感器網絡非均勻分簇路由協議[J]. 軟件學報,2012,34(5):1222-1232.

[7] Neamatollahi P,Taheri H,Naghibzadeh M,et al. DESC:Distributed Energy Efficient Scheme to Cluster Wireless Sensor Networks[C]//Wired/wireless Internet Communications-,Ifip Tc 6 International Conference,Wwic 2011,Vilanova I La Geltrú,Spain,June 15-17,2011. Proceedings. DBLP,2011:234-246.

[8] Kang J. Congestion Control in Wireless Sensor Networks[M]. Rutgers University,2007.

[9] Karenos K,Kalogeraki V,Krishnamurthy S V. Cluster-Based Congestion Control for Supporting Multiple Classes of Traffic in Sensor Networks[C]//IEEE Workshop on Embedded Networked Sensors. IEEE Computer Society,2005:107-114.

[10] Basaran C,Kang K D,Suzer M H. Hop-by-Hop Congestion Control and Load Balancing in Wireless Sensor Networks[C]//IEEE,Conference on Local Computer Networks. IEEE Computer Society,2010:448-455.

[11] Wan C Y,Eisenman S B,Campbell A T. CODA:Congestion Detection and Avoidance in Sensor Networks[C]//International Conference on Embedded Networked Sensor Systems. ACM,2003:266-279.

[12] Sankarasubramaniam Y,Akyildiz I F. ESRT:Event-to-Sink Reliable Transport in Wireless Sensor Networks[C]//ACM Interational Symposium on Mobile Ad Hoc NETWORKING and Computing,MOBIHOC 2003,Annapolis,Maryland,Usa,June. DBLP,2003:177-188.

[13] Kulik J,Heinzelman W,Balakrishnan H. Mitigating Congestion in Wireless Sensor Networks[C]//International Conference on Embedded Networked Sensor Systems,SENSYS 2004,Baltimore,Md,Usa,November. DBLP,2004:134-147.

[14] 段文軒,蔣文賢. 無線傳感器網絡中一種ARMA流量預測的擁塞控制算法[J]. 小型微型計算機系統,2012,33(5):188-193.

[15] 劉思峰,楊英杰. 灰色系統研究進展(2004-2014)[J]. 南京航空航天大學學報,2015,47(1):1-18.

[16] 劉思峰,曾波,劉解放,等. GM(1,1)模型的幾種基本形式及其適用范圍研究[J]. 系統工程與電子技術,2014,36(3):501-508.

[17] 尹安,汪秉文,戴志誠,等. 無線傳感器網絡HEED分簇協議的研究與改進[J]. 小型微型計算機系統,2010,31(10):2002-2006.