尚 靜,董增壽,康 琳

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

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

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

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

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

本文的內(nèi)容安排如下:第1節(jié)介紹網(wǎng)絡模型,第2節(jié)詳細介紹URMC算法的具體實現(xiàn)過程,第3節(jié)通過MATLAB仿真驗證算法的優(yōu)越性,第4節(jié)是結(jié)束語。

1 網(wǎng)絡模型

1.1 系統(tǒng)模型

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

R1=r1

(1)

Ri=Ri-1+ri

(2)

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

圖1 系統(tǒng)模型

1.2 能耗模型

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

圖2 網(wǎng)絡能耗模型

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

(3)

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

ERx(l)=lEelec

(4)

當數(shù)據(jù)的相關(guān)性較強時,節(jié)點首先對數(shù)據(jù)進行融合,再發(fā)送出去。融合能耗EDA(l)為:

EDA(l)=lEelec

(5)

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

(6)

2 URMC算法描述

2.1 首環(huán)半徑

采用簇間多跳路由傳輸方式時,靠近Sink的節(jié)點轉(zhuǎn)發(fā)任務重,負載大,容易過早死亡。所以在此第1環(huán)的節(jié)點直接向Sink節(jié)點發(fā)送感知到的數(shù)據(jù),而不經(jīng)過簇頭的轉(zhuǎn)發(fā),即第1環(huán)的簇頭只起到轉(zhuǎn)發(fā)外環(huán)簇頭數(shù)據(jù)的作用。

假設節(jié)點Si是首環(huán)簇成員節(jié)點,且節(jié)點Si到Sink節(jié)點的距離dtoSink

(7)

當節(jié)點Si經(jīng)過簇頭CHi轉(zhuǎn)發(fā)給Sink節(jié)點時,假設節(jié)點Si到簇頭CHi的距離dtoCH

(8)

式中:α為融合系數(shù)。

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

α=1/Nc

(9)

式中:Nc為每簇的節(jié)點數(shù)。由于α很小,故將Eforward省略為:

(10)

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

(11)

(12)

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

(13)

解得首環(huán)半徑r1應滿足:

(14)

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

2.2 各環(huán)簇頭數(shù)

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

圖3 最大簇頭數(shù)

圖4 最小簇頭數(shù)

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

(15)

最小簇頭數(shù)mmin為:

(16)

本文中,我們假設環(huán)Ci中簇半徑均為ri,即環(huán)Ci的寬度。故環(huán)Ci中期望的簇頭數(shù)為:

(17)

由于首環(huán)簇頭負載較重,能耗較大,所以我們?yōu)槠浞峙漭^多的簇頭數(shù),即首環(huán)的簇頭數(shù)m1為式(18)所示,其余各環(huán)的簇頭數(shù)均為式(17)所示的mi。

(18)

2.3 各環(huán)環(huán)寬度

本節(jié)首先計算各環(huán)中節(jié)點的能耗,其次通過各環(huán)能耗均等為目標推出各環(huán)最優(yōu)環(huán)寬度的表達式。

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

假設將圓形區(qū)域分為S個非均勻圓環(huán),則第i環(huán)節(jié)點數(shù)Ni為:

(19)

式中:ρ為網(wǎng)絡中的節(jié)點分布密度。

(20)

第i環(huán)中簇頭到Sink的距離的期望E[dCHi]為:

(21)

(22)

當i=1時,即首環(huán)節(jié)點能耗公式計算如下:

首環(huán)簇成員節(jié)點直接將數(shù)據(jù)發(fā)送給Sink節(jié)點,不需要經(jīng)過簇頭的轉(zhuǎn)發(fā)。所以首環(huán)節(jié)點的能耗Etotal1為:

(23)

(24)

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

(25)

當i>1時,第i環(huán)節(jié)點的能耗計算如下:

(26)

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

(27)

(28)

(29)

代入上式可得:

(30)

第i環(huán)中每個簇頭的本地能耗ECHlocal和轉(zhuǎn)發(fā)能耗ECHforward分別為:

(31)

(32)

第i環(huán)中每個簇成員節(jié)點的能耗ECM為:

ECM=ETx(L,dCMi)

(33)

則第i環(huán)中一個簇的能耗Ecluster為:

(34)

第i環(huán)中節(jié)點的能耗Etotali為:

Etotali=miEcluster

(35)

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

①當dCMi

(36)

②當dCMi

(37)

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

根據(jù)各環(huán)能耗均衡準則,即式(37),可得到各環(huán)寬度之間的關(guān)系。

Etotali=Etotali-1=…=Etotal1

(38)

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

2.4 簇形成階段

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

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

CH(k)=CHj

(39)

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

(40)

(41)

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

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

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

2.5 建立簇間路由樹

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

(42)

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

(43)

(44)

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

第i環(huán)中簇頭CHi通過計算第i-1環(huán)中每個簇頭的通信代價值,選擇最小通信代價值的節(jié)點作為簇間路由傳輸?shù)南乱惶?從而簇間路由建立階段完成。

3 仿真結(jié)果分析

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

3.1 仿真參數(shù)

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

表1 仿真參數(shù)

3.2 仿真結(jié)果分析

3.2.1 簇頭分布圖

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

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

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

圖6 網(wǎng)絡的生存節(jié)點數(shù)

3.2.2 網(wǎng)絡生存周期

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

表2 死亡節(jié)點輪數(shù)比較

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

圖7 非均勻分環(huán)與均勻分環(huán)

3.2.3 節(jié)點平均剩余能量

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

圖8 節(jié)點平均剩余能量

4 結(jié)束語

本文提出了一種基于非均勻分環(huán)與最小通信代價的路由算法URMC,該算法通過非均勻分環(huán)來均衡節(jié)點負載,避免能量空洞現(xiàn)象,且綜合考慮能量和距離因素選擇簇頭和建立簇間路由樹。經(jīng)仿真驗證,URMC算法的網(wǎng)絡生存周期較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] 劉志,裘正定. 基于分環(huán)多跳的無線傳感網(wǎng)分簇路由算法[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] 劉生. 無線傳感器網(wǎng)絡分簇路由算法研究[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的無線傳感器網(wǎng)絡非均勻分簇雙簇頭路由算法[J]. 傳感技術(shù)學報,2014,27(9):1281-1286.

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