能量消耗均衡的水下傳感器網絡非均勻分簇算法

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

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

0 引言

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

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

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

1 系統模型

1.1 網絡模型

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

1.2 能量消耗模型

應用無線通信的能量衰減模型[25]，節點發送數據包的能量消耗Et(d)為

Et(d)=λtlA(d),

(1)

A(d)=dηad,

(2)

(3)

(4)

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

節點接收數據包的能量消耗Er為

Er=λrl,

(5)

式中：λr為接收能量消耗因數。

2 EBUC算法

2.1 節點密集度

傳感器網絡的節點隨機分布，網絡中各區域的節點密集度差別較大。若不考慮節點密集度，在選擇簇頭時，可能出現節點密集度大的區域簇頭個數較少的問題。簇頭不僅傳輸自身收集的數據，還要轉發其他簇頭的數據，簇頭較少導致簇頭能量消耗過高而過早死亡。因此，在選擇簇頭時，需要考慮節點密集度對能量消耗均衡的影響。節點密集度的決定因素：一是固定區域內節點個數；二是節點與鄰居節點間的距離。引入節點密集度權重的概念，考慮兩個因素對節點密集度的影響，節點密集度權重Di為

(6)

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

2.2 分簇過程

分簇算法中簇頭轉發簇內節點的數據，由于傳輸負載較大，需要由剩余能量較高的節點擔任簇頭。傳感器網絡的節點通常隨機分布，在選擇簇頭時要考慮不同區域的節點密集度。因此，應考慮節點剩余能量、節點密集度、節點到基站的距離選擇簇頭，通過節點通信半徑調整優化簇頭等級的劃分，根據簇頭的權值函數，節點選擇均衡簇間負載效果最好的簇頭入簇。

2.2.1 選擇候選簇頭

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

(7)

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

2.2.2 確定簇頭

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

(8)

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

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

2.2.3 劃分簇頭等級

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

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

(9)

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

2.2.4 節點入簇

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

(10)

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

2.3 算法偽代碼

EBUC算法偽代碼見表1。

表1 EBUC算法偽代碼

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

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

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

3 算法仿真與分析

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

表2 仿真實驗參數

3.1 算法穩定性

圖1 4種算法選出的簇頭數

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

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

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

3.2 能量消耗均衡性

數據傳輸時簇頭比其他節點消耗的能量更多，需要均衡簇頭的能量消耗，才能避免簇頭的過早死亡。隨機選擇10輪，4種算法的簇頭能量消耗標準差見圖3。由圖3可知，LEACH算法的簇頭能量消耗標準差最大，EEUC、UCUBG和EBUC算法的簇頭能量消耗標準差相似，尤其是EBUC算法的最小，表明LEACH算法均衡網絡能量消耗的效果最差，EBUC算法均衡網絡能量消耗的效果最好。

圖2 4種算法的簇頭數量標準差

圖3 4種算法的簇頭能量消耗標準差

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

3.3 網絡使用壽命

當節點數為50、75、100、125、150、175和200個時，4種算法的首個死亡節點出現輪數見圖5。由圖5可知，EBUC算法的首個死亡節點出現的輪數大于其他3種算法的，可以有效延長網絡使用壽命。

圖4 4種算法節點的平均剩余能量

圖5 4種算法的首個死亡節點出現輪數

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

4種算法的網絡生命周期見圖7。由圖7可知, LEACH和EEUC算法的死亡節點數隨時間變化較大,UCUBG和EBUC算法的節點死亡規律基本一致、變化比較穩定。EBUC算法的節點存活時間比其他3種算法的更長,表明EBUC算法有效延長網絡的生存時間。

圖6 4種算法的存活節點數

4 結論

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

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

(3)水下傳感器網絡能量消耗不均，相比陸地水下傳輸時延更大，對水下通信數據傳輸時延還需進一步研究。