能量消耗均衡的水下傳感器網(wǎng)絡(luò)非均勻分簇算法

魏連鎖， 吳 迪， 李 華， 蘇 揚， 韓 建， 陳齊齊

( 齊齊哈爾大學(xué) 計算機與控制工程學(xué)院，黑龍江 齊齊哈爾 161006 )

0 引言

水下傳感器網(wǎng)絡(luò)是利用水下傳感器節(jié)點感知水下相關(guān)信息，通過水聲通信媒介將傳感器節(jié)點感知的數(shù)據(jù)信息傳送至數(shù)據(jù)處理中心[1-4]。水下傳感器網(wǎng)絡(luò)廣泛應(yīng)用于水下資源勘探、海洋地理數(shù)據(jù)收集、導(dǎo)航和控制、災(zāi)難預(yù)防、軍事安全等領(lǐng)域[5-8]。由于水下傳感器節(jié)點自帶電池能量有限，水聲信號的傳輸受水下復(fù)雜環(huán)境影響較大，水聲通信帶寬有限、多徑效應(yīng)嚴(yán)重，水聲信號易受非平穩(wěn)噪聲等因素的影響[9-11],將水下節(jié)點長時間部署后，有效的能量供給對于整個水下傳感器網(wǎng)絡(luò)至關(guān)重要[12-15]。

有關(guān)能量高效的傳感器網(wǎng)絡(luò)研究方面，HEINZELMAN W R等[16]提出自適應(yīng)低功耗的LEACH算法，使用基于輪的傳感器網(wǎng)絡(luò)進(jìn)行拓?fù)渲貥?gòu)，利用概率函數(shù)選擇簇頭。該算法未考慮簇頭分布不均及每簇的大小不同，易導(dǎo)致簇頭能量消耗不均而過早死亡。QING L等[17]將節(jié)點能量異構(gòu)與LEACH協(xié)議相結(jié)合，優(yōu)化改進(jìn)后提出DEEC算法，對簇頭閾值函數(shù)參數(shù)進(jìn)行動態(tài)調(diào)整，與LEACH算法相比，網(wǎng)絡(luò)的壽命較長，但節(jié)點的能量消耗很高。DOMINGO M C等[18]提出分布式水下聚類算法(DUCS)，不使用泛洪技術(shù)，最大限度減少節(jié)點之間的消息交換，降低節(jié)點的能量消耗。為了解決基站附近簇頭節(jié)點負(fù)載過重的“熱點”狀況，李成法等[19]提出高能效的非均勻分簇算法(EEUC),根據(jù)簇頭和基站之間的距離調(diào)整簇的大小，使網(wǎng)絡(luò)中接近基站的簇規(guī)模變小，提高簇頭能量消耗均衡的效果。雷輝等[20]提出水聲傳感器網(wǎng)絡(luò)多跳非均勻分簇算法(EEMUC)，根據(jù)節(jié)點和基站之間的距離，將整個網(wǎng)絡(luò)劃分為以基站為中心的不均勻弧形分層模型；每個層的節(jié)點根據(jù)綜合屬性值選擇簇頭，減小靠近基站的簇；簇之間采用多跳數(shù)據(jù)傳輸，有效均衡簇頭的能量消耗。WANG K等[21]提出用于數(shù)據(jù)傳輸?shù)姆执厮惴?EGRCs),將整個三維網(wǎng)絡(luò)分成若干網(wǎng)格, 每個網(wǎng)格組成一個簇，選擇剩余能量最大、到基站距離最短的節(jié)點作為簇頭，根據(jù)剩余能量、端到端延遲及節(jié)點到基站的距離，選擇下一跳簇頭節(jié)點。該算法能夠延長網(wǎng)絡(luò)壽命，提高能量使用效率，但未考慮節(jié)點分布不均對網(wǎng)絡(luò)生存時間的影響。蔣華等[22]提出基于改進(jìn)灰狼優(yōu)化的分簇算法，利用改進(jìn)適應(yīng)度函數(shù)的灰狼優(yōu)化算法進(jìn)行分簇，有效延長網(wǎng)絡(luò)的生存時間。李志華等[23]提出基于等級劃分的分簇算法(UCUBG)，根據(jù)節(jié)點剩余能量和節(jié)點密度選擇簇頭，再根據(jù)簇頭之間的位置關(guān)系劃分簇頭等級，最后節(jié)點選擇負(fù)載最小的簇頭入簇。該算法忽略簇頭剩余能量對簇頭等級劃分的影響，在選擇簇頭時僅考慮某一區(qū)域內(nèi)節(jié)點的鄰居節(jié)點個數(shù)，未考慮鄰居節(jié)點與該節(jié)點的距離對節(jié)點密集程度的影響。

筆者提出一種能量消耗均衡的水下傳感器網(wǎng)絡(luò)非均勻分簇算法(EBUC)，解決水下傳感器網(wǎng)絡(luò)節(jié)點分布不均導(dǎo)致各節(jié)點能量消耗不均的問題?？紤]節(jié)點數(shù)量及節(jié)點到鄰居節(jié)點距離，構(gòu)造節(jié)點密集度權(quán)重函數(shù)，使簇頭在網(wǎng)絡(luò)中分布更均勻，每輪選擇的簇頭個數(shù)變化較小，算法穩(wěn)定性更好；在劃分簇頭等級時，考慮簇頭的剩余能量和簇頭到基站的距離，選擇簇頭的通信半徑，更合理地劃分簇頭等級，減少簇頭的能量消耗；普通節(jié)點選擇簇頭建立成簇, 構(gòu)建一種能量消耗均衡、高效的水下傳感器網(wǎng)絡(luò)。該算法有效解決非均勻分簇方式下簇頭能量消耗不均的問題,節(jié)省網(wǎng)絡(luò)中每個節(jié)點的能量消耗，延長網(wǎng)絡(luò)使用壽命。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

應(yīng)用3D水下傳感器網(wǎng)絡(luò)作為網(wǎng)絡(luò)模型[24]。傳感器網(wǎng)絡(luò)G=(S,L)，其中S=(S1,S2,…,SN)，Si為網(wǎng)絡(luò)里的第i個節(jié)點，N為節(jié)點個數(shù)；L={L(i,j),Si∈S,Sj∈S,i≠j}，L(i,j)為節(jié)點Si至Sj的通訊線路。

1.2 能量消耗模型

應(yīng)用無線通信的能量衰減模型[25]，節(jié)點發(fā)送數(shù)據(jù)包的能量消耗Et(d)為

Et(d)=λtlA(d),

(1)

A(d)=dηad,

(2)

(3)

(4)

式(1-4)中：λt為發(fā)送能量消耗因數(shù)；l為數(shù)據(jù)包長度；d為發(fā)送節(jié)點到接收節(jié)點的距離；A(d)為發(fā)送距離為d時消耗的能量；η為能量衰減因數(shù)，且η=1.5；a(f)為吸收因數(shù)；f為信號頻率。

節(jié)點接收數(shù)據(jù)包的能量消耗Er為

Er=λrl,

(5)

式中：λr為接收能量消耗因數(shù)。

2 EBUC算法

2.1 節(jié)點密集度

傳感器網(wǎng)絡(luò)的節(jié)點隨機分布，網(wǎng)絡(luò)中各區(qū)域的節(jié)點密集度差別較大。若不考慮節(jié)點密集度，在選擇簇頭時，可能出現(xiàn)節(jié)點密集度大的區(qū)域簇頭個數(shù)較少的問題。簇頭不僅傳輸自身收集的數(shù)據(jù)，還要轉(zhuǎn)發(fā)其他簇頭的數(shù)據(jù)，簇頭較少導(dǎo)致簇頭能量消耗過高而過早死亡。因此，在選擇簇頭時，需要考慮節(jié)點密集度對能量消耗均衡的影響。節(jié)點密集度的決定因素：一是固定區(qū)域內(nèi)節(jié)點個數(shù)；二是節(jié)點與鄰居節(jié)點間的距離。引入節(jié)點密集度權(quán)重的概念，考慮兩個因素對節(jié)點密集度的影響，節(jié)點密集度權(quán)重Di為

(6)

式中：M為節(jié)點Si的鄰居節(jié)點數(shù)量；d(Si,Sm)為節(jié)點Si到鄰居節(jié)點Sm的距離。由式(6)可知，網(wǎng)絡(luò)中節(jié)點密集度由鄰居節(jié)點數(shù)量和鄰居節(jié)點到該節(jié)點的距離決定，鄰居節(jié)點數(shù)量越多、到該節(jié)點的距離越近，節(jié)點密集度越大。

2.2 分簇過程

分簇算法中簇頭轉(zhuǎn)發(fā)簇內(nèi)節(jié)點的數(shù)據(jù)，由于傳輸負(fù)載較大，需要由剩余能量較高的節(jié)點擔(dān)任簇頭。傳感器網(wǎng)絡(luò)的節(jié)點通常隨機分布，在選擇簇頭時要考慮不同區(qū)域的節(jié)點密集度。因此，應(yīng)考慮節(jié)點剩余能量、節(jié)點密集度、節(jié)點到基站的距離選擇簇頭，通過節(jié)點通信半徑調(diào)整優(yōu)化簇頭等級的劃分，根據(jù)簇頭的權(quán)值函數(shù)，節(jié)點選擇均衡簇間負(fù)載效果最好的簇頭入簇。

2.2.1 選擇候選簇頭

受洋流影響，水下隨機部署的節(jié)點位置發(fā)生變化，導(dǎo)致網(wǎng)絡(luò)中不同區(qū)域的節(jié)點密集度差異很大。選擇候選簇頭時，需要考慮節(jié)點附近鄰居節(jié)點的剩余能量和節(jié)點密集度對簇頭能量消耗的影響，構(gòu)造節(jié)點閾值函數(shù)T(i)為

(7)

式中：Er(i)為節(jié)點Si的剩余能量；Eav(i)為節(jié)點Si在通信半徑內(nèi)所有節(jié)點的平均剩余能量；Dmax為整個網(wǎng)絡(luò)中節(jié)點的最大密集度權(quán)重；a1、b1和c1為調(diào)節(jié)因數(shù),且a1+b1+c1=1。由式(7)可知,節(jié)點的剩余能量越多、節(jié)點密集度越高，節(jié)點閾值函數(shù)越大，選擇節(jié)點作為候選簇頭的概率越高。

2.2.2 確定簇頭

在多跳傳感器網(wǎng)絡(luò)中，靠近基站的簇頭需要傳輸其他較遠(yuǎn)簇頭的數(shù)據(jù)，因此靠近基站的簇頭能量過度消耗而過早死亡。同時，受洋流等因素影響，水中節(jié)點位置不固定，還要考慮某區(qū)域節(jié)點的密集度?？紤]候選簇頭到基站的距離和節(jié)點密集度調(diào)整競爭半徑，使距離基站近、節(jié)點密集度高的候選簇頭的競爭半徑變大。候選簇頭的競爭半徑Rc(i)為

(8)

式中：d(Si,ds)為節(jié)點Si到基站ds的距離；Rmax為最大通信半徑；dmax、dmin分別為網(wǎng)絡(luò)中節(jié)點與基站之間的最大距離和最小距離；a2、b2為調(diào)節(jié)因數(shù),且a2+b2=1。由式(8)可知，候選簇頭與基站距離越近、節(jié)點密集度越高，候選簇頭的競爭半徑越小，在節(jié)點入簇時其他節(jié)點加入該簇的數(shù)量越少。

計算競爭半徑后，候選簇頭根據(jù)剩余能量選擇何時向全網(wǎng)廣播競選為最終簇頭的消息。候選簇頭在競選簇頭失敗后退化為普通節(jié)點，與剩余的其他節(jié)點在節(jié)點入簇階段選擇合適的簇頭入簇。

2.2.3 劃分簇頭等級

為了使簇間的通信代價與通信時延最小，通常要劃分簇頭的等級。根據(jù)UCUBG算法[24]，劃分簇頭等級時考慮簇頭間的相對位置，使深度不同的簇頭始終保持等級差，避免深度相近的簇頭劃分為相同等級，使相同等級的簇頭傳輸負(fù)載差異過大。該算法在劃分簇頭等級時未給出如何選擇簇頭的通信半徑。

考慮簇頭到基站的距離和簇頭剩余能量的通信半徑函數(shù)調(diào)整簇頭的通信半徑，使距離基站較近且剩余能量較高的簇頭更容易成為高等級的簇頭，更合理劃分簇頭的等級。簇頭的通信半徑Ro(j)為

(9)

式中：d(Sj，ds)為簇頭Sj到基站ds的距離；E0(j)、Er(j)分別為簇頭初始能量和剩余能量；a3、b3為調(diào)節(jié)因數(shù),且a3+b3=1。由式(9)可知，簇頭的剩余能量越多、與基站的距離越近，簇頭的通信半徑越大，在劃分簇頭等級時成為較高等級簇頭的概率越大。

2.2.4 節(jié)點入簇

考慮節(jié)點到簇頭的距離、簇頭到基站的距離、簇頭的剩余能量、簇頭等級、簇的大小等因素，均衡各簇頭的能量消耗。構(gòu)造節(jié)點入簇的權(quán)值函數(shù)Wj(Si,Sj)，普通節(jié)點選擇均衡能量消耗效果最好的簇頭入簇。節(jié)點入簇公式為

(10)

式中：d(Si,Sj)為節(jié)點Si到簇頭Sj的距離；Ri為節(jié)點i的通信半徑；Gj為簇頭的等級；Gmax為簇頭的最高等級。a4、b4、c4和d4為調(diào)節(jié)因數(shù),且a4+b4+c4+d4=1。由式(10)可知,簇頭的權(quán)值函數(shù)越小,節(jié)點選擇該簇頭入簇的概率越大。

2.3 算法偽代碼

EBUC算法偽代碼見表1。

表1 EBUC算法偽代碼

選擇候選簇頭階段：網(wǎng)絡(luò)中所有節(jié)點在通信半徑R內(nèi)廣播自身的初始能量E0(i)、剩余能量Er(i)及節(jié)點位置坐標(biāo)(xi,yi,zi)，節(jié)點Si接收其他節(jié)點廣播的信息后，通過式(7)得到Si的閾值函數(shù)T(i)。每個節(jié)點選擇 (0,1)之間的隨機數(shù)μ。如果T(i)>μ，則選擇該節(jié)點作為候選簇頭。

確定簇頭階段：候選簇頭在通信半徑R內(nèi)廣播自己競選為候選簇頭的信息TEMPORARY_HEAD_MSG，信息內(nèi)容包含簇頭的競爭半徑Rc(i)、簇頭剩余能量Er(i)及簇頭的唯一標(biāo)識id。候選簇頭根據(jù)收到的信息建立鄰居簇頭集合Sch(i)，節(jié)點與鄰居簇頭集合中剩余能量更高的節(jié)點進(jìn)行比較，決定是否選為簇頭。若Si剩余能量高于鄰居簇頭集合中所有節(jié)點的剩余能量，則選擇該節(jié)點為最終簇頭，并廣播信息FINAL_HEAD_MSG通知鄰居簇頭；若Si接收到Sj競選為簇頭的信息，同時Sj在集合Sch(i)里, 那么Si退出選舉，并廣播信息QUIT_ELECTION_MSG通知鄰居簇頭；若Si接收到Sj發(fā)來的退出選舉的消息，同時Sj在集合Sch(i)里，則Si將Sj從集合Sch(i)中刪除。

節(jié)點入簇階段：由式(10)計算簇頭和未被選為簇頭的節(jié)點的權(quán)值，比較所有簇頭的權(quán)值，節(jié)點選擇權(quán)值最小的簇頭入簇。

3 算法仿真與分析

通過仿真實驗驗證EBUC算法的特性，在Python3.7平臺上，將EBUC算法與UCUBG、EEUC和LEACH算法進(jìn)行對比。仿真實驗參數(shù)見表2。

表2 仿真實驗參數(shù)

3.1 算法穩(wěn)定性

圖1 4種算法選出的簇頭數(shù)

非均勻分簇算法的穩(wěn)定性主要由每輪選出的簇頭數(shù)量決定，簇頭數(shù)量的變化范圍越小，網(wǎng)絡(luò)的穩(wěn)定性越高。選取100個初始節(jié)點進(jìn)行實驗，隨機選擇10輪，4種算法選出的簇頭數(shù)量變化見圖1。由圖1可知，各算法選出的簇頭數(shù)量的變化范圍為nLEACH=[4，18]，nEEUC=[4，8]，nUCUBG=[10，16],nEBUC=[11，15]。

與 LEACH 算法相比，EEUC、UCUBG和 EBUC算法穩(wěn)定性更好，尤其是 EBUC算法的穩(wěn)定性最為明顯。LEACH算法應(yīng)用概率函數(shù)選擇簇頭，不能保證簇頭數(shù)量的穩(wěn)定性；EEUC算法在選擇簇頭時考慮節(jié)點與基站的距離，比LEACH算法穩(wěn)定性更好，但未考慮平均剩余能量對簇頭選擇的影響，簇頭數(shù)量比UCUBG和 EBUC算法的少；UCUBG和 EBUC算法考慮更多因素的影響，有效延長網(wǎng)絡(luò)的生存時間，與 UCUBG算法相比，EBUC算法在選擇簇頭時，考慮鄰居節(jié)點數(shù)量、節(jié)點與鄰居節(jié)點距離及節(jié)點密集度權(quán)重函數(shù)，使網(wǎng)絡(luò)中簇頭的分布更均勻，算法穩(wěn)定性更好。

為了直觀對比不同算法簇頭數(shù)量的變化情況， 對4種算法每輪簇頭數(shù)量的標(biāo)準(zhǔn)差進(jìn)行對比(見圖2)。由圖2可知，LEACH算法的簇頭數(shù)量標(biāo)準(zhǔn)差比其他3種算法的大，EEUC、UCUBG和EBUC算法的簇頭數(shù)量標(biāo)準(zhǔn)差比較接近，說明LEACH算法的穩(wěn)定性最差，EEUC、UCUBG和EBUC算法的穩(wěn)定性比較接近，尤其是EBUC算法簇頭數(shù)量標(biāo)準(zhǔn)差最小，穩(wěn)定性最好。

3.2 能量消耗均衡性

數(shù)據(jù)傳輸時簇頭比其他節(jié)點消耗的能量更多，需要均衡簇頭的能量消耗，才能避免簇頭的過早死亡。隨機選擇10輪，4種算法的簇頭能量消耗標(biāo)準(zhǔn)差見圖3。由圖3可知，LEACH算法的簇頭能量消耗標(biāo)準(zhǔn)差最大，EEUC、UCUBG和EBUC算法的簇頭能量消耗標(biāo)準(zhǔn)差相似，尤其是EBUC算法的最小，表明LEACH算法均衡網(wǎng)絡(luò)能量消耗的效果最差，EBUC算法均衡網(wǎng)絡(luò)能量消耗的效果最好。

圖2 4種算法的簇頭數(shù)量標(biāo)準(zhǔn)差

圖3 4種算法的簇頭能量消耗標(biāo)準(zhǔn)差

網(wǎng)絡(luò)中節(jié)點的平均剩余能量可以有效反映網(wǎng)絡(luò)能量消耗的均衡性。前20輪4種算法節(jié)點的平均剩余能量變化見圖4。由圖4可知，EBUC算法節(jié)點的平均剩余能量最多，在均衡網(wǎng)絡(luò)能量消耗方面效果最佳。

3.3 網(wǎng)絡(luò)使用壽命

當(dāng)節(jié)點數(shù)為50、75、100、125、150、175和200個時，4種算法的首個死亡節(jié)點出現(xiàn)輪數(shù)見圖5。由圖5可知，EBUC算法的首個死亡節(jié)點出現(xiàn)的輪數(shù)大于其他3種算法的，可以有效延長網(wǎng)絡(luò)使用壽命。

圖4 4種算法節(jié)點的平均剩余能量

圖5 4種算法的首個死亡節(jié)點出現(xiàn)輪數(shù)

4種算法的存活節(jié)點數(shù)見圖6。由圖6可知，EBUC算法的首個死亡節(jié)點出現(xiàn)的輪數(shù)是LEACH算法的245%、EEUC算法的168%、UCUBG算法的112%，EBUC算法均衡能量消耗效果最好。 LEACH算法應(yīng)用概率函數(shù)選擇的簇頭分布不均勻且簇頭的能量損失差異大，導(dǎo)致死亡節(jié)點首先出現(xiàn)；EEUC算法在選擇簇頭時頻繁交換信息，使節(jié)點負(fù)載過大而過早死亡；UCUBG和EBUC算法在網(wǎng)絡(luò)接近死亡時，短時間內(nèi)節(jié)點基本同時死亡，表明UCUBG和EBUC算法節(jié)點能量消耗比較均衡，但EBUC算法網(wǎng)絡(luò)的生存時間比UCUBG算法的更長。

4種算法的網(wǎng)絡(luò)生命周期見圖7。由圖7可知, LEACH和EEUC算法的死亡節(jié)點數(shù)隨時間變化較大,UCUBG和EBUC算法的節(jié)點死亡規(guī)律基本一致、變化比較穩(wěn)定。EBUC算法的節(jié)點存活時間比其他3種算法的更長,表明EBUC算法有效延長網(wǎng)絡(luò)的生存時間。

圖6 4種算法的存活節(jié)點數(shù)

4 結(jié)論

(1)對于水下傳感器網(wǎng)絡(luò)節(jié)點分布不均導(dǎo)致節(jié)點能量消耗不均的問題，提出能量消耗均衡的水下傳感器網(wǎng)絡(luò)非均勻分簇算法(EBUC)。引入節(jié)點密集度權(quán)重函數(shù)，考慮節(jié)點剩余能量及節(jié)點到基站的距離選擇簇頭，使簇頭在網(wǎng)絡(luò)中分布更均勻；考慮簇頭的剩余能量和簇頭到基站的距離，選擇簇頭的通信半徑，更合理劃分簇頭等級。

(2)EBUC算法具有穩(wěn)定性和能量消耗均衡性，能夠有效均衡簇頭的能量消耗，減少網(wǎng)絡(luò)能量損失，延長網(wǎng)絡(luò)使用壽命。

(3)水下傳感器網(wǎng)絡(luò)能量消耗不均，相比陸地水下傳輸時延更大，對水下通信數(shù)據(jù)傳輸時延還需進(jìn)一步研究。