基于非均勻分環與最小通信代價的路由算法*

尚 靜,董增壽,康 琳

(太原科技大學電子信息工程學院,太原 030024)

無線傳感器網絡是由大量能量有限的傳感器節點組成,并且網絡一旦部署就不能人為的進行更換電池,所以能量受限是傳感器網絡面臨的主要問題之一[1]。利用分簇路由算法可以增加網絡的可擴展性和延長網絡的生存周期,故得到了廣泛的關注和研究。

LEACH[2]是第1個含有成簇思想的無線傳感器網絡路由協議。其主要思想是通過“輪”,隨機循環的進行簇頭的選舉和簇的重構,從而將網絡的能耗均衡的分配到每個節點上。LEACH能有效的提高網絡的生存周期,但是LEACH也可能會造成簇頭分布不均、能量空洞等問題[3-4]。文獻[5]中模擬實驗表明如果節點采用均勻分布策略,網絡中可能有高達90%的能量被浪費。文獻[6]中指出根據節點與Sink節點的距離不同,使節點擔任不同的負載是解決能量空洞的一種途徑,所以我們是以區域劃分的形式來分析網絡負載的,即引入了環狀分簇的方法。

劉志[7]等人提出了分環多跳的分簇路由算法RBMC,該算法將監測區域劃分為若干個均勻間隔的同心圓環,以各環簇頭能耗相等為目標得到各環的最優簇頭數,最終形成一個能耗均勻、簇大小異構的多跳WSN網絡。雖然RBMC算法在很大程度上均衡了節點能量消耗,延長了網絡的生存周期,但RBMC算法仍使用LEACH閾值公式來選擇簇頭,沒有考慮簇頭能量、地理位置等因素。針對RBMC的缺陷,Zhi Ren[8]等提出ERBMC算法,ERBMC通過在簇頭選舉概率公式中增加能量因素、引入了簇頭多輪選擇機制和提出由簇間權衡值來建立一個更加可靠的簇間多跳路由三方面的改進來提高網絡的生存周期,但ERBMC算法沒有解決可能會出現的簇頭分布不均等問題。劉生[9]等提出虛擬分塊非均勻分簇算法VBUC,該算法一方面通過對區域虛擬分塊來選擇簇頭,另一方面在簇頭選舉時考慮了能量和距離因素。但VBUC算法在選擇簇頭和簇間多跳路由選擇時,只考慮了距離因素,未考慮剩余能量的影響。Gong B[10]等提出能量異構的分簇方案EHCS,該算法通過使傳感器節點的初始能量隨著與Sink的距離不同而變化來避免能量空洞現象,即在不同的地理位置部署具有不同初始能量的節點。但傳感器節點一般都是隨機分布的,所以EHCS在現實中難以實現。Jiang J[11]等提出基于非均勻分簇算法UCRP,該算法在均勻環內分別放置3種不同能量的節點,并通過數學理論推導得到各環最優簇半徑來實現能量均衡的目標,但同樣在現實中難以實現。為解決簇頭能耗過大的問題,文獻[12]利用粒子群算法PSO選擇雙簇頭來實現非均勻分簇,以減少主簇頭能耗。文獻[13]設計了基于簇頭分級的非均勻分簇算法CHCI,通過為主簇頭設置重選因子和次要簇頭選擇最佳中繼路徑來降低節點能耗。

本文提出的URMC算法首先通過為各環分配不同的環寬度來均衡各環的能耗;其次通過通信代價公式來選擇簇頭和建立簇間路由傳輸方式,其中通信代價公式綜合考慮了距離與剩余能量因素。URMC算法避免了上述論文可能會出現的簇頭分布不均、考慮因素單一、難以操作等問題,有效的延長了網絡的生存周期。

本文的內容安排如下:第1節介紹網絡模型,第2節詳細介紹URMC算法的具體實現過程,第3節通過MATLAB仿真驗證算法的優越性,第4節是結束語。

1 網絡模型

1.1 系統模型

假設N個傳感器節點隨機分布在半徑為R的圓形監測區域中,將監測區域分為若干個寬度不同的同心圓環,Sink節點位于圓心位置。如圖1所示為網絡的系統模型,圖中將網絡分為3環,由內而外分別為首環C1、第2環C2和第3環C3。R1、R2、R3分別是3個同心圓的半徑,r1、r2、r3分別是各環之間的寬度。則第i個同心圓的半徑Ri和環寬度ri之間的關系式為:

R1=r1

(1)

Ri=Ri-1+ri

(2)

其他有關節點的假設如下:①所有節點(包括Sink節點)一旦部署就不再變化,即所有節點都是靜止的;②所有節點的初始能量都相同;③所有節點都沒有位置感知功能,可以通過接收消息的強度值RSSI來計算與消息發送者的距離;④傳感器節點的能量是有限的,而Sink節點的能量是無限的或是可以補充的;⑤每個節點都有不同的ID號。

圖1 系統模型

1.2 能耗模型

本文采用與文獻[7]相同的能耗模型,如圖2所示為能耗模型圖。

圖2 網絡能耗模型

如圖2所示,當節點Si將Lbits數據包發送到距離為d的節點Sj時,節點Si發送能耗ETx(l,d)為:

(3)

節點Sj的接收能耗ERx(l)為:

ERx(l)=lEelec

(4)

當數據的相關性較強時,節點首先對數據進行融合,再發送出去。融合能耗EDA(l)為:

EDA(l)=lEelec

(5)

式中:Eelec為接收或發送1bit數據時的能耗,εfs、εmp分別為自由空間模型衰減系數和多徑衰減系數,d0為距離閾值。d0表達式如下:

(6)

2 URMC算法描述

2.1 首環半徑

采用簇間多跳路由傳輸方式時,靠近Sink的節點轉發任務重,負載大,容易過早死亡。所以在此第1環的節點直接向Sink節點發送感知到的數據,而不經過簇頭的轉發,即第1環的簇頭只起到轉發外環簇頭數據的作用。

假設節點Si是首環簇成員節點,且節點Si到Sink節點的距離dtoSink

(7)

當節點Si經過簇頭CHi轉發給Sink節點時,假設節點Si到簇頭CHi的距離dtoCH

(8)

式中:α為融合系數。

本文中所提到的融合均為完全融合方式,即每個簇頭將自身簇成員節點的數據接收并融合成1單位的數據包向外傳送,所以融合系數α的表達式為:

α=1/Nc

(9)

式中:Nc為每簇的節點數。由于α很小,故將Eforward省略為:

(10)

當EtoSink≤Eforward時,節點Si選擇直接發送給Sink節點更節能,此時dtoSink需要滿足的條件為:

(11)

(12)

式中:m1為首環簇頭個數,r1為首環半徑。將式(12)代入式(11),可得:

(13)

解得首環半徑r1應滿足:

(14)

綜上理論分析,當首環半徑r1滿足式(14)時,首環簇成員節點將數據直接發送給Sink節點更加節能。所以本文利用式(14)可求得首環半徑r1的值。

2.2 各環簇頭數

無線傳感器網絡分簇路由所形成的簇結構需要包含網絡中所有的節點,并且每個簇中只有一個簇頭節點和若干個簇成員節點。如圖3所示,當簇與簇之間的重疊最多時,簇頭數最大;反之,如圖4所示,當簇與簇之間的重疊最少時,簇頭數最小。

圖3 最大簇頭數

圖4 最小簇頭數

根據文獻[10]中Gong B得出最大簇頭數與最小簇頭數的表達式,即若環Ci的面積為Si,且簇半徑為rc時,環Ci內最大簇頭數mmax為:

(15)

最小簇頭數mmin為:

(16)

本文中,我們假設環Ci中簇半徑均為ri,即環Ci的寬度。故環Ci中期望的簇頭數為:

(17)

由于首環簇頭負載較重,能耗較大,所以我們為其分配較多的簇頭數,即首環的簇頭數m1為式(18)所示,其余各環的簇頭數均為式(17)所示的mi。

(18)

2.3 各環環寬度

本節首先計算各環中節點的能耗,其次通過各環能耗均等為目標推出各環最優環寬度的表達式。

在每個簇頭周期中,簇頭能耗主要分為兩部分,一部分為接收、融合和發送自身簇成員的數據,我們稱之為本地能耗;另一部分為接收和發送外層簇頭的數據,我們稱之為轉發能耗。由于各環之間的數據相關性較小,所以對不同環的數據不進行融合,以此來節約能量。

假設將圓形區域分為S個非均勻圓環,則第i環節點數Ni為:

(19)

式中:ρ為網絡中的節點分布密度。

(20)

第i環中簇頭到Sink的距離的期望E[dCHi]為:

(21)

(22)

當i=1時,即首環節點能耗公式計算如下:

首環簇成員節點直接將數據發送給Sink節點,不需要經過簇頭的轉發。所以首環節點的能耗Etotal1為:

(23)

(24)

將式(25)代入式(23)得:

(25)

當i>1時,第i環節點的能耗計算如下:

(26)

式中:ρ(r,θ)為第i環中簇頭密度,r為簇成員節點與簇頭之間的最遠距離,即簇半徑。具體計算如下:

(27)

(28)

(29)

代入上式可得:

(30)

第i環中每個簇頭的本地能耗ECHlocal和轉發能耗ECHforward分別為:

(31)

(32)

第i環中每個簇成員節點的能耗ECM為:

ECM=ETx(L,dCMi)

(33)

則第i環中一個簇的能耗Ecluster為:

(34)

第i環中節點的能耗Etotali為:

Etotali=miEcluster

(35)

由于簇成員與簇頭之間的距離dCMi比較小,所以我們假設dCMi

①當dCMi

(36)

②當dCMi

(37)

綜上,當i>1時,第i環節點的能耗與第i環節點數Ni、簇頭數mi、簇頭與簇頭之間的距離dCHi,i-1、簇成員節點與簇頭之間的距離dCMi有關,而這些因素均只與環寬度ri有關,故第i環節點的能耗只與環寬度ri有關。

根據各環能耗均衡準則,即式(37),可得到各環寬度之間的關系。

Etotali=Etotali-1=…=Etotal1

(38)

網絡部署結束后,Sink節點向外廣播Sink-notify消息通知所有節點開始工作,并且每個節點通過計算RSSI值得到與Sink的距離,從而確定自己所屬環數。

2.4 簇形成階段

URMC采用和VBUC算法相同的方法來選擇候選簇頭,然后通過計算在不同區域編號中每個候選簇頭的通信代價值,最終選擇通信代價值最小的候選簇頭作為該區域編號的最終簇頭。

假設S(c)為區域編號k中所有候選簇頭的集合,則區域編號k的最終簇頭CH(k)由下列等式進行選擇:

CH(k)=CHj

(39)

CHj=argmin{cost(i),i∈S(c)}

(40)

(41)

式中:∑d(w,i)表示區域編號k中其他所有節點與候選簇頭i的距離之和,nk表示區域編號k中節點個數,d(i,Sink)表示候選簇頭i與Sink節點的距離,E(i)表示候選簇頭i的剩余能量,α、β、γ分別為各個影響因素的加權因子。

由于簇頭在簇內通信時,其他節點與其的距離為影響能耗的主要因素,簇頭的能量為次要因素,與Sink節點的距離為最小因素,所以分配值分別為:α=0.5、β=0.2、γ=0.3。

當選為最終簇頭的節點向外廣播CH_NOTIFY消息,消息包括節點ID、節點與Sink的距離、節點當前輪剩余能量。非簇頭節點通過計算接收到CH_NOTIFY消息強度值,選擇距離自己最近的簇頭作為自身簇頭,簇建立階段完成。

2.5 建立簇間路由樹

假設S(CHi-1)為第i-1環所有簇頭節點的集合,則第i環中簇頭CHi的下一跳簇頭節點Next(CHi)由下列等式進行選擇:

(42)

CHc=argmin{cost(CHf),CHf∈S(CHi-1)}

(43)

(44)

式中:d(CHi,CHf)為相鄰環兩個簇頭之間的距離,d(CHf,Sink)為簇頭CHf與Sink之間的距離,E(CHf)為簇頭CHf的剩余能量。在簇間路由傳輸時,簇頭與簇頭之間的距離為影響能耗的主要因素,簇頭的能量為次要因素,簇頭與Sink的距離為最小因素,所以分配加權因子分別為:α=0.5、β=0.2、γ=0.3。

第i環中簇頭CHi通過計算第i-1環中每個簇頭的通信代價值,選擇最小通信代價值的節點作為簇間路由傳輸的下一跳,從而簇間路由建立階段完成。

3 仿真結果分析

本節利用MATLAB仿真平臺對提出的算法URMC與LEACH、RBMC、VBUC算法進行性能比較。

3.1 仿真參數

假設監測區域R=180 m總分環數S=3;根據式(17)、式(18)和式(38),可得到各環簇頭數和寬度:m1=4、m2=16、m3=11、r1=81 m、r2=30 m、r3=69 m。其余仿真參數如表1所示。

表1 仿真參數

3.2 仿真結果分析

3.2.1 簇頭分布圖

如圖5所示,分別為LEACH、RBMC、VBUC及本文URMC算法的簇頭分布圖。

由于LEACH算法和RBMC算法隨機循環的進行簇頭選舉,所以會造成簇頭分布不均的情況;VBUC算法是在RBMC算法的基礎上每環根據最優簇頭數進行虛擬分區,簇頭在虛擬小區內進行選取,有效的改善了簇頭分布不均的情況,但VBUC算法無法確保在算法運行過程中每環的簇頭分布與理論得到的最優簇頭數一致,如圖首環的簇頭數為4,但根據理論計算得到的值為5;URMC算法對圓形區域進行非均勻分環,并在VBUC算法的基礎上對其調整,所以既提高了簇頭分布的均勻性,又保證了各環簇頭數與理論值一致。

圖5 4種算法的簇頭分布圖

圖6 網絡的生存節點數

3.2.2 網絡生存周期

在此定義50%節點死亡的輪數為網絡的生命周期。如圖6及表2所示,由于LEACH算法可能會出現能量較小的節點當選簇頭或者出現能量空洞現象,所以LEACH算法只運行到604輪時網絡生命周期就結束;RBMC算法在LEACH的基礎上對不同區域分配不同的簇頭概率來克服能量空洞現象,將網絡生命周期延長到了1 583輪;VBUC算法在RBMC基礎上對區域虛擬分區來提高簇頭分布的均勻性,將網絡生命周期延長到了1 730輪;本文的URMC算法既通過非均勻分環來克服能量空洞現象又比VBUC算法增加了能量因素,所以URMC算法將網絡生命周期延長到了2 006輪。

表2 死亡節點輪數比較

如圖7所示為基于最小通信值的簇頭選擇和簇間路由樹算法下,非均勻分環與均勻分環的生存節點數對比。從圖中可看出,隨著網絡運行時間的增長,節點的剩余能量越低,非均勻分環相比較于均勻分環網絡的生存節點數較多,性能較好。

圖7 非均勻分環與均勻分環

3.2.3 節點平均剩余能量

如圖8所示,由于URMC算法綜合考慮了節點的能量和距離,所以較其他3種算法節點平均剩余能量下降較緩慢。

圖8 節點平均剩余能量

4 結束語

本文提出了一種基于非均勻分環與最小通信代價的路由算法URMC,該算法通過非均勻分環來均衡節點負載,避免能量空洞現象,且綜合考慮能量和距離因素選擇簇頭和建立簇間路由樹。經仿真驗證,URMC算法的網絡生存周期較LEACH、RBMC及VBUC算法分別提高了232%、26.7%和15.9%。

[1] Kumar D. Performance Analysis of Energy Efficient Clustering Protocols for Maximising Lifetime of Wireless Sensor Networks[J]. Iet Wireless Sensor Systems,2013,4(1):9-16.

[2] Heinzelman W B,Chandrakasan A P,Balakrishnan H. An Application Specific Protocol Architecture for Wireless Microsensor Networks[C]//IEEE Transactions on Wireless Communication. 2002:660-670.

[3] Abo-Zahhad M,Ahmed S M,Sabor N,et al. Mobile Sink-Based Adaptive Immune Energy-Efficient Clustering Protocol for Improving the Lifetime and Stability Period of Wireless Sensor Networks[J]. IEEE Sensors Journal,2015,15(8):4576-4586.

[4] Ren J,Zhang Y,Zhang K,et al. Lifetime and Energy Hole Evolution Analysis in Data-Gathering Wireless Sensor Networks[J]. IEEE Transactions on Industrial Informatics,2016,12(2):788-800.

[5] Yuan H,Yang S,Xie J. Prolonging the Lifetime of Sensor Networks Using Non-Uniform Sensor Distribution[C]//Conference Anthology,IEEE. IEEE,2013:1-4.

[6] Olariu S,Stojmenovic I. Design Guidelines for Maximizing Lifetime and Avoiding Energy Holes in Sensor Networks with Uniform Distribution and Uniform Reporting[C]//INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings. IEEE,2006:1-12.

[7] 劉志,裘正定. 基于分環多跳的無線傳感網分簇路由算法[J]. 通信學報,2008,29(3):104-113.

[8] Ren Z,Chen Y,Yao Y,et al. Energy-Efficient Ring-Based Multi-Hop Clustering Routing for WSNs[C]//Fifth International Symposium on Computational Intelligence and Design. IEEE Computer Society,2012:14-17.

[8] 劉生. 無線傳感器網絡分簇路由算法研究[D]. 北京:華北電力大學,2012.

[9] Gong B,Jiang T,Xu S,et al. An Energy-Heterogeneous Clustering Scheme to Avoid Energy Holes in Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks,2013,10(22):1380-1383.

[10] Jiang J,Han G,Liu L,et al. An Unequal Cluster-Based Routing Protocol for Wireless Heterogeneous Sensor Networks[J]. Journal of Internet Technology,2015,16(6):945-955.

[11] 門順治,孫順遠,徐保國. 基于PSO的無線傳感器網絡非均勻分簇雙簇頭路由算法[J]. 傳感技術學報,2014,27(9):1281-1286.

[12] 康琳,董增壽. 基于簇頭分級的改進非均勻分簇算法[J]. 傳感技術學報,2015(12):1841-1845.