基于數據引流的無線傳感器網絡能量空洞避免研究

王施雨， 劉 唐

(1. 東北師范大學 物理學院, 吉林 長春 130024； 2. 四川師范大學 基礎教學學院, 四川 成都 610066)

近年來,隨著無線通信技術與微電子技術的持續發展,無線傳感器網絡(WSN)[1]得到越來越廣泛的應用.傳感器網絡中的節點通常由能量有限的電池供電,這些節點在部署后難以更換電池,所以無線傳感器網絡有著嚴重的能量約束問題[2].

在采用多跳數據傳輸的無線傳感器網絡中,如果某些節點承擔了更大的數據轉發任務,它們的能量消耗速度會明顯快于其他節點,因而這些節點會首先死亡.在這些節點死亡后,它們負責轉發的數據將很難再有效傳輸至sink,此時網絡壽命結束,而網絡中其他節點內大量的剩余能量被浪費,這種現象被稱為“能量空洞”[3-4].文獻[5]的實驗結果表明當網絡中出現能量空洞,網絡壽命結束時,網絡中還剩余高達90%的能量被浪費.

在無線傳感器網絡的真實應用場景下,傳感器節點的數據產生量會根據環境實時發生變化.例如,對用于面向人群監控任務的傳感器網絡,節點的數據產生速率與被監控的人員數量密切相關.由于人類出行的時空規律性[6],在不同時間被某個節點監控的人員數量會有所不同,這使得該節點的數據產生速率會呈現有規律的動態變化.因此,網絡中的節點的能耗負載也呈現出動態變化的特點.

近年來,盡管能量空洞現象已經引起了研究者們的廣泛關注,并取得了一定的研究成果,但是還沒有面向由真實場景下節點的數據產生速率動態變化造成的能量空洞問題的解決方案.

在對前人工作進行總結的基礎上,為有效避免由節點數據產生速率動態發生變化造成的節點能量空洞現象,提出了一種數據引流的非均勻分簇算法FRUC.本文主要工作如下：

1) 利用分簇進行數據收集與傳輸,但與傳統的非均勻分簇不同,FRUC算法在網絡初始階段對網絡進行分層,每層網絡層高不等,簇的范圍限制在層內；

2) 考慮所有節點的數據平均產生率,給出網絡各層內的簇頭節點完成一次簇內、簇間數據處理所消耗能量的計算方法,并讓網絡各層的層高取值滿足各層之間的所有簇頭節點的能耗均衡；

3) 考慮節點數據產生率的動態變化對路由負載的影響,引入基于數據引流的數據傳輸方法,讓一個簇的發送數據量發生變化時,數據不再只發送給一個固定的簇頭,而是動態地將數據引流到多個簇頭.

1 相關工作

目前,能量空洞作為無線傳感器網絡中一個瓶頸性的問題,國內外許多研究者進行了大量研究.

為了有效均衡網絡內節點能耗,解決能量空洞問題,研究者們提出了許多不同的策略來緩解能量空洞現象造成的影響.其中,研究者利用的技術包括：部署移動sink、利用非均勻分簇算法、采用不同的傳輸策略、傳感器節點的非均勻分布等.下面介紹與本文研究相關的非均勻分簇算法研究.

與LEACH[7]、HEED[8]這樣的傳統分簇算法不同,非均勻分簇算法讓網絡中的各個簇具有不等的簇規模,以使有更大能耗的區域簇規模減小,有更小能耗的區域簇規模增大,從而均衡網絡內各區域的節點負載,延遲能量空洞的出現并延長網絡壽命.

文獻[9]提出了一種分布式分簇路由協議DEBUC,該協議采用基于時間的簇頭競爭算法,節點的廣播時間由其鄰居節點和候選簇頭的當前剩余能量決定.同時,通過控制不同網絡區域的候選簇頭的競爭半徑,使得距離sink較近的簇規模較小.與之相類似的還包括文獻[10]提出的EEUC算法,該算法通過控制簇頭的競爭半徑來調整簇的規模,使靠近sink的簇比遠離sink的簇擁有更小的簇半徑.

文獻[11]將非均勻分簇引入節點非均勻分布的網絡,以避免能量空洞問題，并提出了一個最小化網絡內所有節點能耗的最優簇結構方法，還設計了一個簡單的分布式路由協議以實現所有節點能耗均衡.

文獻[12]提出了ACT分簇路由協議.該協議將網絡分層,簇的規模限制在層內.文獻[12]計算了簇頭節點的能耗,并讓網絡各層的大小滿足在一個簇周期,各層內的單個簇頭節點的能耗相等.但是,由于各層規模不同,各層內的簇頭節點數目也不同.因此該算法并沒有保證在一個簇周期內各層中所有的節點能耗之和相等,因而該協議并不能真正均衡各層的能耗.

文獻[6]研究了異構網絡中如何避免能量空洞.針對異構環境下各個簇產生的數據量不等且未知的條件,文獻[6]提出了一種基于反饋機制的分均勻成簇算法.

文獻[13]的研究針對由初始能量較大節點擔任簇頭、初始能量較小的節點作為簇內成員節點的異構傳感器網絡,提出了基于不等簇半徑的能量空洞避免策略.文獻[13]從理論上推導出距離sink不同距離處簇半徑的大小,并給出了不等簇半徑的取值與優化方法.

文獻[14]提出了一個能量有效的分布式成簇算法,該算法根據與sink節點的數據轉發距離確定適當的簇半徑,以實現節點壽命的大致均衡.文獻[14]還提出了一個簡單的高效節能多跳數據收集協議來對成簇算法進行評價,并計算出該協議的能耗.

文獻[15]提出了一個模糊能量感知的非均勻分簇算法EAUCF.該算法為降低靠近sink的簇頭節點和低剩余能量簇頭節點的工作負載,引入模糊邏輯方法以處理簇頭半徑估計的不確定性.

文獻[16]提出了一種流量均衡路由算法FBR.與已有的路由算法不同,FBR的骨干網絡構造算法構建了一種新的多層次骨干網絡,該網絡不同于傳統樹形的簇頭通信拓撲結構,而是每個簇頭擁有多個父節點.簇頭間進行數據傳遞時,簇頭將待發送數據分發給多個父節點,以平衡父節點的能耗,延長網絡壽命.但是該分簇算法讓每個簇的簇半徑相等,因此各簇能耗很難實現完全均衡.同時,該算法并未讓所有的節點輪流擔當簇頭,因此簇頭節點能耗速度明顯快于普通節點.

2 網絡模型

2.1網絡模型本文定義W×L(m)的矩形網絡中分布著N個傳感器節點.圖1給出了網絡模型示意圖,表1為相關符號說明.設該傳感器網絡性質如下：

1) 唯一的sink節點位于網絡邊緣,sink以基站形式部署；

2) 網絡中所有的傳感器節點滿足隨機分布,節點的發射功率可調,且在部署后靜止不動；

3) 傳感器節點被組織成簇的形式,各簇的范圍限制在網絡分層內,簇頭節點在完成簇內數據收集后,以簇間多跳形式將數據發送到sink節點；

4) 傳感器節點在不同時刻的數據產生率動態變化,根據監控區域的歷史數據,在網絡生命周期內的節點平均數據產生率可知.

2.2能耗模型本文采用典型的能量消耗模型[17],在數據傳輸過程中,傳感器節點傳輸lbit數據經過距離d,產生的能耗為

ETx(l,d)=ETx_elec(k)+ETTx_amp(l,d)=

(1)

接收端所產生的能耗為

ERx(l)=ERx_elec(l)=lEelec，

(2)

其中,d0為一閾值,當數據傳輸距離小于d0時,發送方的能耗與距離的平方成正比,否則與距離的4次方成正比.Eelec表示發送或接收1 bit數據時的能量消耗,εfsd2和εmpd4是發送1 bit數據放大器的能量消耗.

圖 1 網絡模型結構

符號含義W網絡寬度L網絡長度Li第i層網絡Hi第i層網絡的層高Ci第i層網絡中的簇‖Ci‖簇Ci的面積r(Cj)簇Ci的半徑ρ網絡中的節點密度ECHi簇Ci的簇頭節點在一個簇周期內的能耗Eini簇Ci的簇頭節點一個簇周期內用于完成簇內數據處理的能耗Eiti簇Ci的簇頭節點一個簇周期內用于完成簇間數據處理的能耗Ei第i層網絡中所有簇頭節點在一個簇周期的總能耗

3 網絡能耗分析與非均勻分層

在多跳傳感器網絡中,靠近sink的簇頭節點由于承擔更多的數據轉發任務,因而有著更大的能耗.通過傳感器節點的平均數據產生率,建立網絡各簇頭節點的能耗計算模型,提出基于網絡層次劃分的非均勻分簇模型,讓靠近sink的網絡分層內的簇規模更小,讓遠離sink的網絡分層內的簇規模更大.

π(r(Ci))2ρlEelec.

(3)

因此,簇頭節點CHi接收外層網絡的數據所消耗的能量為

簇頭節點CHi發送到內層網絡的數據包括接收的外層網絡數據及簇內節點發送到簇頭的數據,因此CHi需要發送到內層網絡的數據總量為

根據能量消耗模型,簇頭節點CHi發送所有數據所消耗的能量為

根據(5)和(7)式能得出簇頭節點CHi在一個簇周期完成簇間數據處理所消耗的能量為

傳感器網絡中,簇頭節點承擔了數據收集和轉發任務,它們的能耗遠大于簇內普通節點.為避免能量空洞現象的出現,應著重考察在一個簇周期內,簇內節點的能耗.由于網絡各層的簇頭節點數量不等,因而僅僅比較網絡各層內單個簇頭節點的能耗,并不能有效平衡網絡各層的總能耗.因此,為避免能量空洞現象的出現,平衡網絡各層的能耗,在一個簇周期內網絡各層內的所有簇頭節點的能耗之和應相等.

對第i層網絡,其所有簇頭節點的總能耗為

(9)

(10)式給出了為平衡網絡各層的能耗,各層層高應滿足的條件

(10)

4 基于數據引流的路由算法描述

下面首先討論如何選擇簇頭,進一步給出基于數據引流的路由算法.

4.1簇頭選擇在網絡首輪成簇前,網絡內的所有節點使用一定的傳輸能量進行全網廣播,利用信號強度在傳輸過程中的衰減,節點可以感知相互之間的距離.文獻[17]給出了節點通過信號發送強度和接收強度之間的關系得出節點間相互距離的計算方法

(11)

sink在網絡初始階段以覆蓋全網絡范圍的廣播強度進行一次廣播,網絡中的各節點在收到sink的廣播后根據(11)式得到自身與sink的距離,確定所屬網絡層次.進一步,各節點在所屬網絡分層內廣播包含自身當前剩余能量信息的簇頭競爭消息.如果某節點發現自身的當前剩余能量大于收到廣播的其他節點能量,該節點就發布成為簇頭的廣播.

4.2數據引流簇頭節點在每個簇周期收到簇內各節點的數據后,需要將這些數據在網絡分層中進行轉發,以最終發送至sink.在傳統的多跳傳感器網絡中,一個數據包到sink之間只有一條固定的簇間路由路徑,如圖2所示.

圖 2 固定路由示意圖

這種固定簇間路由存在的問題如下：

1) 由于網絡各層的層高不等,各層內的簇頭數量也不等,因而在簇頭數量較多的內層網絡中,各簇頭的負載必然不均衡,會出現某些簇頭承擔了較多的數據轉發任務而某些簇頭沒有承擔轉發任務.如圖2所示,越靠近sink的簇頭節點會呈現更大的路由負載不均衡現象.以最內層網絡為例,路由負載最大的節點,承擔了來自5個簇的數據轉發量,而該層網絡中有的簇頭并未承擔外層網絡的數據轉發.

2) 難以適應節點的數據產生率隨網絡環境變化的動態場景.在節點數據產生率動態變化的場景下,每個簇頭節點在每個簇周期接收到的簇內成員產生的數據量也會隨之改變.如果采用傳統的固定簇間路由方法,數據轉發量的動態變化會加重同層內的各個簇頭間的能耗負載不均現象,從而更快的導致節點的死亡并出現能量空洞.

為解決上述問題,平衡網絡內各簇簇頭的路由負載,本文提出一種基于數據引流的路由方法,讓一個簇的數據轉發到下一層時,不再只轉發到一個簇頭,而是根據各個簇當前需要轉發的數據量,實時將數據引流到多個簇頭.數據引流的思想如下：

1) 每個簇頭進行數據轉發時,將本簇產生的數據和收到的來自外層簇頭發送來的數據,引流到內層網絡中的多個簇頭；

2) 為實現避免個別節點提前死亡的目的,讓有更多剩余能量的簇頭承擔更大的數據轉發任務.在每個簇周期,各個簇產生的數據量會動態變化,因此在每個簇周期開始簇間數據傳輸時,考察每個簇頭的剩余能量和每個簇頭所在簇內的數據產生量.在某個簇頭有數據需要轉發時,將更多的數據引流到剩余能量更多、簇內數據量更少的簇頭,以平衡下層網絡內的各個簇頭的能耗.

對Li(i≠1)層網絡中的第j個簇頭節點CHi,j,設當前簇周期需傳輸至下一層網絡的數據量為li,j,CHi,j首先啟動路由發現過程,向下一層網絡中發出路由請求消息.Li-1層網絡中所有簇頭在收到請求后,以一定功率發出包含自身能量信息和當前簇周期所在簇的簇內數據量的應答消息.

簇頭節點CHi,j根據計算得出的引流值,將數據分為大小不等的若干份,發送至下一層的各個簇頭節點.當新一輪簇周期,各個簇產生的數據量和各個簇頭的剩余能量發生變化時,數據引流量也會動態更新.

圖 3 數據引流示意圖

圖3給出了在一個簇周期進行簇間路由時的數據引流示意圖.可以看出,各簇的數據被引流到下一層網絡的多個簇頭,以平衡每一層內的各簇之間的能量消耗,避免部分節點能量耗盡形成能量空洞.數據引流算法流程如下：

For 每一個簇周期

For 每一個簇

選舉能量最大的節點成為簇頭節點

End for

For 從外到內的每一層網絡

For 每一個簇頭節點

計算簇頭需要發送的數據量

啟動路由發現過程

收到下一層網絡的應答消息

計算引流到下一層每個簇頭節點的數據量

End for

End for

各個簇頭進行數據發送

End for

5 仿真實驗

將在Matlab仿真實驗平臺下,驗證提出的算法是否能有效避免.首先對網絡分均勻分層進行驗證,給出在默認網絡環境下,網絡各層層高的取值；其次,將討論在網絡非均勻分層的情況下,數據引流對網絡性能提升的影響；進一步,將對比LEACH、DEBUC、FBR和本文提出的FRUC4種算法不同的表現.選擇這3個算法進行對比的原因是LEACH是經典的分簇算法；DEBUC為了實現網絡內節點能量均勻消耗,通過給出每個簇頭不同的簇頭競爭半徑值以實現非均勻分簇；FBR則是首先提出數據引流思想的路由算法.

表 2 實驗參數

在仿真實驗中,網絡默認規模為250 m×150 m的矩形區域,唯一的sink位于網絡的邊緣位置.網絡帶寬為10 kbps,其他網絡參數以及相應的缺省值見表2.實驗結果若未特別說明,均為100次獨立實驗結果的均值.

5.1網絡分層性能首先,在節點的數據產生率不變的條件下,考察網絡分層的情況,并對網絡最優分層時各層內的簇頭節點的能耗情況進行分析.

表3給出了每個節點產生的數據消息大小為1 000 bit時,由(10)式得出的網絡各層規模.

表 3 分層高度

從表3可以看出,在250 m×150 m的網絡分為了4層,越靠近sink的網絡分層層高越小,越遠離sink的網絡分層層高越大.此時網絡壽命(第一個節點的死亡時間)為371輪.進一步,隨機選擇了10輪簇周期,分布考察每個網絡分層內的簇頭節點的總能耗.圖4給出了各網絡各層內的簇頭節點在隨機選擇的10個簇周期的總能耗.可以看出,網絡4層內的簇頭節點,在這10個簇周期的總能耗,一直處于相對均衡的狀態,能耗值基本上在39～52 mJ之間.這說明了,隨著網絡被劃分成了高度不等的分層,非均勻分簇能有效平衡網絡各區域節點的能耗.

圖 4 各層簇頭總能耗

進一步,圖5顯示了在這10個簇周期,網絡各層簇頭節點總能耗的標準差.可以看出,在隨機選取的10個簇周期中,除了2個簇周期以外,其他8個簇周期各層簇頭節點的總能耗差異都很小,其標準差都在3以內,而層間能耗差異較大的2個簇周期,標準差也在4.5以內.這表明了,FRUC算法能有效平衡層間的簇頭能耗.

圖6顯示了每個網絡分層內的簇頭節點在10個簇周期的總能耗標準差.可以看出,在更靠近sink的內層網絡內,各簇頭節點總能耗在各個簇周期差異很小,而在遠離sink的外層網絡,各個簇周期節點能耗差異較大.

圖 5 層間簇頭節點能耗標準差

圖 6 層內簇頭節點能耗標準差

5.2數據引流性能下面在對數據引流對網絡性能的影響進行分析.首先,比較在默認網絡環境下有無數據引流時的網絡壽命.

表 4 數據引流對網絡壽命的影響

從表4可以看出,數據引流能有效提升網絡壽命,延緩節點死亡時間.由于數據引流能有效平衡簇頭節點間的能耗負載,并能讓具有更多剩余能量和更小數據傳輸距離的簇頭節點承擔更多的數據轉發任務,因而更有利于節省數據路由過程中的能耗開銷.因此,在層間路由未進行負載引流時,網絡壽命僅為211輪,而采用數據引流后,網絡壽命提升到376輪.

圖7給出了未采用數據引流時,網絡各分層中的簇頭節點在一個簇周期的能耗.可以看出,在內層網絡中由于不同的簇頭節點承擔了不均衡的數據轉發任務,因而各簇頭節點間的能耗差異極大.以L1層網絡為例,能耗最高的一個簇頭節點在一個簇周期消耗了24.215 mJ能量,這是能耗最低的簇頭節點的20.875倍.

圖 7 無數據引流時簇頭節點能耗

圖8顯示了采用數據引流后,網絡各層中的簇頭節點在一個簇周期的能耗.顯然可以從圖8看出,與圖7相比，L1層和L2層網絡中的簇頭節點的能耗得到了相當大的平衡.這是因為通過引流,L1層和L2層網絡中的所有簇頭節點都承擔了數據轉發任務,因而有效均衡了所有簇頭節點的能耗負載,這也有助于避免某些簇頭節點因能耗過大提前死亡而造成的能量空洞現象.

圖 8 數據引流時簇頭節點能耗

5.34種算法對比通過實驗比較本文提出的基于數據引流的非均勻分簇算法FRUC、LEACH算法、DEBUC算法及FBR算法在網絡壽命和網絡首節點死亡時節點能量剩余率方面的性能.

圖9給出了在默認網絡環境下,4個算法所取得的網絡壽命.可以看出LEACH算法由于是簇間單跳路由,因此有著最低的網絡壽命.DEBUC算法作為一種典型的非均勻分簇算法,網絡壽命相對于LEACH算法得到了明顯提升.FBR算法由于引入了引流機制,網絡壽命高于LEACH和DEBUC,但是FBR由于讓固定的節點擔當簇頭,同時網絡內所有簇規模相等,因此靠近sink的簇頭節點的死亡時間會早于其他普通節點,從而使網絡壽命低于本文提出的FRUC算法.

圖 9 網絡壽命對比

圖10比較了4個算法在默認網絡參數下,首節點死亡時所有節點的平均剩余能量.可以看到,對于LEACH算法,在網絡壽命結束時所有節點平均剩余能量最高,達到了0.472 8 J,這也與文獻[5]的實驗結論相符.DEBUC算法和FBR算法的節點平均剩余能量分別為0.341 1 J和0.247 8 J.本文提出的FRUC算法能最好地利用節點能量,非均勻分簇保證了網絡各層之間簇頭節點能耗均衡,數據引流又保證了網絡各層內的簇頭節點能量均衡消耗,因此當網絡中出現第一個死亡節點時,網絡所有節點平均剩余能量僅為0.193 8 J.

圖 10 節點平均剩余能量對比

進一步,改變節點初始能量,對4個算法的網絡壽命進行比較,圖11給出了實驗結果.可以看到,隨著節點初始能量的增加,4個算法所取得的網絡壽命均得到了提升,其中FRUC、DEBUC、FRB等3個算法網絡壽命的提升明顯.而節點初始能量取值不同時,FRUC算法均有著最高的網絡壽命.

圖 11 不同節點初始能量下的網絡壽命

圖12給出了改變網絡中的節點密度,4個算法所取得的網絡壽命.可以看到,隨著節點數目的增加,LEACH和DEBUC算法的網路壽命均下降明顯,這是因為節點數目越多,網絡內產生的監控數據也隨之增加,節點消耗了更多的能量進行數據傳輸,從而降低了網絡壽命.FBR算法由于數據引流的作用,網絡壽命在節點數目增加到350個以后,才出現下降,且下降趨勢明顯緩于DEBUC算法.本文提出的FRUC算法在網絡節點密度較低節點數目僅為300個時,網絡壽命略低于DEBUC和FBR算法.這是因為FRUC算法對網絡進行了分層,且越靠近sink的網絡分層規模越小,這樣在節點低密度狀態下,L1層網絡內節點數目很少,從而少量的節點承擔了簇頭節點的工作,影響了網絡壽命.而在其他節點密度下,FRUC算法均有著最高的網絡壽命，并且由于數據引流平衡了簇頭節點的能耗,因此在節點數目大于400個以后,網絡壽命才出現了下降.

圖 12 不同節點密度下的網絡壽命

6 結束語

本文對無線傳感器網絡的能量空洞問題進行了研究,提出了一種基于數據引流的非均勻分簇能量空洞避免策略FRUC.與已有工作相比,FRUC的主要貢獻表現在以下2個方面：

1) 不同于傳統的非均勻分簇算法DEBUC與EEUC,FRUC不再通過計算不同節點的不同簇頭競爭半徑，從而實現非均勻分簇.FRUC在網絡初始階段對網絡進行非均勻分層,并讓簇的范圍限制在層內,以實現非均勻分簇,從而保證了網絡各層之間簇頭節點的能耗均衡；

2) FRUC算法引入了數據引流,讓一個簇的數據發送給下一層時,不再只發送給一個簇頭,而是將數據引流到多個簇頭,這樣平衡了網絡各層內各個簇頭節點的能耗均衡.

仿真實驗結果表明,FRUC算法能夠獲得比LEACH、DEBUC、FBR等主要數據傳輸算法更均衡的節點能耗負載、更長的網絡壽命,并能有效避免能量空洞現象的出現.