基于能量的水聲傳感器網絡分簇算法優化

趙旦峰, 陳通,2

(1.哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150001; 2.北京長城電子裝備有限責任公司，北京 100082)

基于能量的水聲傳感器網絡分簇算法優化

趙旦峰1, 陳通1,2

(1.哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150001; 2.北京長城電子裝備有限責任公司，北京 100082)

針對分簇水聲傳感器網絡中簇頭分布不均和水聲信道時變特性等原因導致的節點能量分布不均的問題，以LEACH(low energy adaptive clustering hierarchy protocol )算法為基礎，提出了一種基于網絡能量狀態估計的分布式算法進行簇頭選舉，有效均衡網絡能耗。通過改進分布式簇頭選舉機制，每輪中簇頭選舉由一次選舉改為多次選舉，在不需要中心控制節點和增加節點間通信量的情況下，首次選舉通過設置能量閥值選舉出高能量節點擔任簇頭，通過第二次選舉保證每輪簇頭數目穩定。仿真結果表明，該改進算法能夠解決分簇水聲傳感器網絡時變信道條件下能量消耗不均衡的問題，均衡網絡能耗，延緩網絡首節點死亡時間。

水聲傳感器網絡；LEACH；分布式；簇頭；能量均衡

水聲傳感器網絡(underwater acoustic sensor networks, UASNs)是集數據采集、處理和傳輸為一體的綜合信息處理系統，可以對海洋信息進行有效監測[1-5]。在無人值守的情況下對海洋信息進行長時間監測需要消耗大量能量，然而UASNs的節點能量儲備有限且難以進行補給[6-8]，因此能夠延長水聲傳感器網絡生命周期的分簇拓撲控制技術成為了當前的研究熱點[9-13]。

LEACH[13](low energy adaptive clustering hierarchy)協議是麻省理工大學Heinzelman等[14]提出的一種自適應分簇拓撲控制協議，基本思想是通過周期、循環、隨機的方式來選擇簇頭節點，可以使整體網絡旳能量消耗均勻地分攤到每個傳感器節點上。與一般的平面拓撲控制協議相比，可以將網絡生命周期延長15%[15-16]。以陸上傳感器網絡LEACH協議研究為基礎，近年來陸續提出了一些可以應用于水聲傳感器網絡的LEACH改進協議。文獻[17]指出在水聲傳感器網絡監測區域確定的情況下，網絡中能量消耗的期望是關于簇覆蓋范圍的函數，可以通過調整網絡中簇的覆蓋范圍來降低網絡能耗。文獻[18]中提出了一種以節點與基站之間距離為主要參考指標的水聲傳感器網絡層次拓撲控制方法，簇頭節點距離sink節點越近，節點當選簇頭的概率越大，以此來均衡網絡能耗，降低簇頭節點和sink節點通信的能量損失，從而提高網絡的能量效率，延長網絡壽命。文獻[19]中對應用于水聲傳感器網絡的LEACH協議中簇結構建立階段廣播簇頭當選消息碰撞問題進行了分析，提出了降低廣播簇頭當選消息碰撞概率的改進協議，改進協議通過時隙劃分的方式有效降低了播簇頭消息的碰撞概率，避免了因為信息重傳造成的能量浪費。但上述研究沒有考慮水聲信道時變特性對網絡每輪能量消耗的影響。由于網絡中每輪能耗存在差異，節點周期性當選簇頭節點的輪換方法不能有效均衡網絡能耗。

針對水聲傳感器網絡每輪能量消耗不均衡的問題，本文提出了一種基于能量的水聲傳感器網絡分簇算法LEACH-ET。優化算法通過增加簇頭選舉過程中高能量節點簇頭當選概率均衡網絡能耗，通過增加每輪簇頭選舉次數保證網絡簇頭節點數目穩定。優化算法通過均衡網絡能耗，穩定簇頭節點數目，有效推遲了網絡首節點死亡時間，延長了網絡壽命。

1 水聲傳感器網絡能量模型

陸上傳感器網絡信號傳輸損耗與信號傳輸距離d相關，但由于水聲傳感器網絡情況特殊，信號傳輸損耗不僅與信號傳輸距離相關，同時還與信號頻率等傳輸條件相關。

根據Urick的數據和公式，Jurdak等人推導出下列模型：

SL=TL+85

(1)

式中：SL為聲源級,TL為傳輸損耗。式中物理量均以dB為單位，參考值1 μPa的量值為0.67×10-22W/cm2，由于水聲傳感器節點通常布放在海底，可以采用柱狀波傳輸損耗模型，信號傳輸損耗：

(2)

式中：d為聲信號發射機與接收機間的距離；α為與頻率相關的吸收系數。為了表示α與頻率之間的函數關系，可以將α寫成α(f)，通常情況下水聲傳感器網絡采用Thorp給出的水聲信號低頻段吸收損耗經驗公式[20]：

(3)

式中f表示信號的傳輸頻率。

為了得到在參考距離1m處的強度It，則水聲信號發射功率Pt：

(4)

式中H表示當前水深，It與SL關系：

(5)

則可以由式(1)～(5)可以導出聲信號發射功率Pt滿足：

pt=CHdeα(f)d

(6)

C為基于聲吶方程推導出的發射器處于最小發射功率時的系數，取值為2π×(0.67)×10-9；H表示節點下放深度；d為傳輸距離；f為水聲信號傳輸頻率；α(f)為頻率吸收系數。

因此水聲傳感器節點發送數據消耗能量Etx及接收數據消耗能量Erx的通用模型可以描述為

(7)

式中：l表示傳輸數據bit量，Eelec表示節點處理單位bit數據消耗能量，Tb表示單位bit數據傳輸時長。

2 LEACH-ET算法

由于水聲傳感器網絡中缺少中心控制節點，節點通信能力受限，水聲通信環境中難以通過中心控制或節點間大量信息交互的方式獲取全局網絡能量信息，只能采用分布式簇頭選舉算法，每輪簇頭節點數目存在差異，同時水聲信道時變特性將導致網絡能量消耗不均，部分節點可能過早死亡。為了均衡網絡能量分布，改進算法通過設定能量閥值Eth，規定只有能量高于Eth的節點才可以參加簇頭選舉，提高高能量節點擔任簇頭的概率。但是由于節點難以獲取全局網絡能量信息，難以使能量大于Eth的節點數目保持穩定，因此無法保證每輪簇頭節點數目的穩定性。為了保證簇頭節點數目的穩定性，每輪進行兩次簇頭選舉，首次選舉出部分高能量節點擔任簇頭，通過第二次選舉提高每輪簇頭節點數目穩定性。

首次簇頭選舉只有高能量節點參加，以概率ph當選為簇頭節點，高能量節點數目Nh應當滿足：

Nhph

(8)

式中：E(CH)為本輪簇頭數目期望，首次簇頭選舉中當選的節點在選舉結束后完成簇建立；剩余未加入簇的節點進行第二次簇頭選舉，節點以概率p當選簇頭節點，通過第二次選舉保證簇頭數目的穩定性。每輪簇頭節點數目期望可以表達為

(9)

閥值Eth的設定決定了參加首次選舉節點的數目Nh，在ph為定值情況下，Nhph的值是只與Nh有關的函數，因此能量閥值Eth的設定決定了協議性能。為了保證NhphE(CH)，需要通過增加Eth減少Nh，來滿足式(8)的條件；如果Nh較小，則簇頭節點中高能量節點數目較少，不能達到均衡網絡能耗的目的，需要降低Eth以增加高能量節點數目Nh，盡可能增加簇頭節點中高能量節點數目。

水聲傳感網絡中節點難以通過節點間信息交互或集中控制方式獲取高能量節點數目Nh的準確值，但每輪簇頭節點選舉過程中，簇頭節點會廣播當選信息，因此可以通過首次選舉中簇頭節點數目和第二次選舉中簇頭節點數目對Nh進行估計。在首次簇頭選舉中，高能量節點以概率ph當選簇頭節點，高能量節點是否當選簇頭節點滿足獨立同分布條件，則簇頭節點數目滿足二項分布條件, 則可以通過矩估計方法對Nh的值進行估計，表示為

(10)

(11)

每一輪中簇頭節點數目并不是一個固定的值，而是在期望值附近波動，可以通過二項分布均值方差來衡量簇頭節點數目穩定性。在均值一定時，簇頭節點數目方差越小，簇頭節點數目越穩定。根據上述網絡模型，在N=256，p=0.1，ph從0.05～0.5變化的條件下進行了十次仿真實驗，每次實驗分別對500輪仿真實驗中簇頭節點數目均值與方差進行統計。由圖1和圖2可知，改進算法中ph較小的情況簇頭數目均值與LEACH算法基本相同，但隨著ph的增加，導致Nhph>E(CH)，簇頭數目均值不斷增加。

圖1 簇頭節點數目均值Fig.1 Mean of cluster head node number

改進算法簇頭數目方差也隨著ph變化，ph較小時，首次選舉簇頭數目較少，二次選舉簇頭數目較多時簇頭數目方差與LEACH算法相近，隨著ph增加且滿足NhphE(CH)，簇頭數目方差只與第一選舉相關且簇頭數目均值較大，則簇頭數目方差開始不斷增加，并大于LEACH算法簇頭數目方差。

圖2 簇頭節點數目方差Fig.2 Variance of cluster head node number

3 算法仿真與分析

根據水聲傳感器網絡模型對改進算法與LEACH、LEACH-E算法進行比較，規定簇成員節點只能與簇頭節點通信，簇成員節點與簇頭通信采用TDMA協議，成員在規定時間內向簇頭傳輸數據，簇內通信不會產生干擾；簇頭節點在收集數據完成后直接傳給sink節點，sink節點與簇頭通信采用CDMA協議，簇頭與sink節點通信過程中不會干擾其它簇頭節點與sink節點通信，且簇內通信也不會對其他簇的任何通信產生干擾。仿真參數設置如表1所示[21]。

表1 仿真參數

為了驗證改進算法性能，模擬分簇水聲傳感器網絡中簇頭分布不均和信道時變特性等原因導致的節點能量異構，節點初始能量均勻的分布在0.5～0.35 J，在N=256，p=0.1的條件下驗證不同ph值對網絡性能影響，仿真如圖3所示。

圖3對不同ph值下網絡存活節點數目進行統計，在ph=0.05時，首次選舉簇頭節點數目過小，無法有效均衡網絡能耗；隨著ph的增加到0.25時，網絡能量均衡效果得到了有效改善，延遲了首節點死亡時間，在首節點死亡過后，其余節點均在短時間內死亡；但隨著ph增加至大于0.5時，由于首次選舉簇頭數目增加導致Nhph>E(CH)，本輪簇頭均為高能量簇頭節點，但網絡中簇頭節點數目大于本輪簇頭數目期望且方差不斷增加，這導致網絡能量均衡效果減弱，首節死亡時間比ph=0.25要早，且首節點死亡時間隨著ph的進一步增加而提前。

為了驗證改進算法的性能，在ph=0.25時對網絡中節點能量分布和存活節點數目進行統計，并與LEACH、LEACH-E兩種算法進行對比，仿真實驗結果如圖4～6所示。

圖3 ph對存活節點數目的影響Fig.3 Number of nodes alive of different ph

圖4 LEACH節點能量分布Fig.4 Node energy distribution of LEACH

圖5 LEACH-E節點能量分布Fig.5 Node energy distribution of LEACH-E

圖6 改進算法節點能量分布Fig.6 Node energy distribution of optimization algorithm

為了驗證算法能量均衡效果，分別對網絡第1輪，第200輪，第400輪和第600輪節點能量分布進行統計，將0～0.5J均勻分成20個能量區間，對能量處于相應區間的節點數目進行統計，在網絡運行過中，全部節點能量分布區間越小，分布范圍越集中，網絡能量均衡效果約好。

在水聲傳感器網絡中節點初始能量均勻分布在0.5～0.35J，LEACH算法在簇頭選舉過程中未考慮節點能量，在網絡運行過程中節點能量分布區間具有擴大趨勢，200輪時，節能量分布在0.15～0.4J，400輪時開始出現節點死亡，能量在0～0.3J，直至節點開始出現因能量耗盡死亡，節點能量分布區間變小，600輪時存活節點能量分布在0～0.225J，在水聲時變信道情況下僅通過節點周期性當選簇頭節點的輪換方法不能起到良好的網絡能耗均衡效果；由于LEACH-E算法以節點能量為參考選舉簇頭節點，因此與LEACH算法相比提高了節點能量分布集中程度，200輪時節點能量分布在0.175～0.4J，400輪時節點能量分布在0.05～0.3J，600輪時存活節點能量分布在0～0.125J，在相同時間內節點能量分布區間均小于LEACH算法，能量均衡效果得到了提升，同時避免了節點因能量耗盡而過早死亡；改進算法中節點能量分布集中程度優于上述兩種算法，在第200輪70%以上的節點分布在0.275～0.3J，第400輪75%以上的節點能量分布在0.125～0.15J，第600輪90%以上存活節點能量分布在0～0.025J，這證明改進算法在信道時變的水聲傳感器網絡中，通過提高高能量節點簇頭當選概率的方法可以有效的均衡網絡能耗。

圖7對三種算法存活節點數目進行了統計。LEACH算法最先出現節點死亡的情況，隨后節點開始緩慢死亡，LEACH算法在簇頭選舉過程中沒能考慮節點能量，簇頭節點能量消耗遠大于簇成員節點，在水聲通信環境中，水聲信道時變特性導致網絡每輪能量消耗存在差異，LEACH算法中節點通過周期性當選簇頭節點的輪換方法不能很好的均衡網絡能耗，部分節點能量消耗過快，死亡時間較早，節點死亡時間差異較大，影響網絡性能，網絡能量均衡效果較差；LEACH-E算法在簇頭選舉中考慮能量因素，由于水聲時變信道特性，每輪節點能量消耗存在差異，LEACH-E算法通過降低低能量節點簇頭當選概率來均衡網絡能耗，因此可以有效降低網絡首節點死亡時間，能量均衡效果優于LEACH算法，但簇頭選舉中低能量節點仍然有較大機會當選簇頭，節點間死亡時間差異也比較大，且需要收集網絡中全體節點能量信息，算法在水聲環境下實現難度較大；改進算法首節點死亡時間最晚，且網絡中節點死亡時間差異最小，由于改進算法每輪簇頭選舉分為兩次完成，首次簇頭選舉通過設置能量閥值，避免了低能量節點當選簇頭，可以有效均衡網絡能耗，為了避免每輪節點能量變化，能量閥值調整導致每輪網絡簇頭節點數目變化過大，通過第二次選舉使每輪簇頭數目保持穩定，低能量節點簇頭當選概率遠遠小于上述兩種算法，因此在信道時變的水聲傳感器網絡中改進算法首節點死亡時間最晚，存活節點數目曲線最陡峭，證明改進算法具有良好的能量均衡效果。

圖7 存活節點數目Fig.7 Number of nodes alive

4 結論

針對水聲信道時變特性導致網絡每輪能量消耗存在差異的問題，本文提出了一種基于能量的簇頭選舉算法，每輪簇頭選舉分為兩次完成，通過首次簇頭節點選舉中高能量簇頭數目可以有效估計網絡能量狀況，并合理設置首次簇頭選舉能量閥值，避免了低能量節點當選簇頭，通過第二次選舉保證了每輪選舉簇頭數目的穩定。通過仿真實驗與LEACH和LEACH-E算法進行對比，驗證了算法性能：

1) 在不增加節點間通信量和中心控制節點的情況下通過改進簇頭節點選舉策略，合理設置能量閥值Eth和高能量節點簇頭當選概率ph可以提高高能量節點簇頭當選概率和每輪簇頭節點數目的穩定性；

2) 在時變水聲通信環境下，改進算法有效的延緩了首節點死亡時間，提高了水聲傳感器網絡能量均衡效果。

水聲通信環境復雜多變，水聲傳感器網絡自適應設置高能量節點簇頭當選概率ph是下一步的研究重點。

[1]VERMA S. Communication architecture for underwater wireless sensor network[J]. Communication architecture for underwater wireless sensor network, 2015, 7(6): 67-74.

[2]AKYILDIZ I F, POMPILI D, MELODIA T. Underwater acoustic sensor networks: research challenges[J]. Ad Hoc network, 2005, 3(3): 257-79.

[3]GUANGYU F, HUIFANG C. An Improved CDMA-based MAC protocol for underwater acoustic wireless sensor networks[C]. Wireless Communications, Networking and Mobile Computing (WiCOM), Chengdu, China, 2011: 1-6.

[4]VERMA S. Communication architecture for underwater wireless sensor network[J]. Communication architecture for underwater wireless sensor network, 2015, 6: 67-74.

[5]孫力娟, 劉林峰, 杜曉玉, 等. 水聲傳感器網絡拓撲控制技術綜述[J]. 南京郵電大學學報: 自然科學版, 2012, 32(5): 20-25. SUN Lijuan, LIU Linfeng, DU Xiaoyu, et al. Overview of topology control techniques in underwater acoustic sensor networks[J]. Journal of Nanjing university of posts and telecommunications: natural science, 2012, 32(5): 20-25.

[6]WANG Yu, LIU Yingjian, GUO Zhongwen. Three-dimensional ocean sensor networks: a survey[J]. Journal of ocean university of China, 2012, 11(4): 436-450.

[7]WAHID A, KIM D. An energy efficient localization-free routing protocol for underwater wireless sensor networks[J]. International journal of distributed sensor networks, 2012, 8(4): 307246.

[8]PARTAN J, KUROSE J, LEVINE B N. A survey of practical issues in underwater networks[J]. Proc Acm Wuwnet, 2006, 11: 23-33.

[9]AZIZ A A, SEKERCIOGLU Y A, FITZPATRICK P, et al. A survey on distributed topology control techniques for extending the lifetime of battery powered wireless sensor networks[J]. IEEE communications surveys & tutorials, 2013, 15(1): 121-144.

[10]OVALIADIS K, SAVAGE N. Cluster protocols in underwater sensor networks: a research review[J]. Journal of engineering science and technology review, 2014, 7(3): 171-175.

[11]PUROHIT R, SIDHU N. Wireless sensor network: Routing protocols and attacks- a survey[C]. 2015 2nd International Conference on Computing for Sustainable Global Development (INDIACom), 2015.

[12]OVALIADIS K, SAVAGE N. Cluster protocols in underwater sensor networks: a research review[J]. Journal of engineering science and technology review, 2014, 7(3): 171-175.

[13]HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE transactions on wireless communications, 2002, 1(4): 660-670.

[14]劉壯, 馮欣, 王雁龍, 等. 基于雙簇頭聚類分簇和數據融合的無線傳感器網絡路由算法[J]. 吉林大學學報: 理學版, 2015, 53(5): 1013-1017. LIU Zhuang, FENG Xin, WANG Yanlong, et al. An improved clustering routing algorithm based on double-CH clustering and data fusion in WSN[J]. Journal of Jilin university: science edition, 2015, 53(5): 1013-1017.

[15]LIN Hongzhi, WEI Wei, ZHAO Ping, et al. Energy-efficient compressed data aggregation in underwater acoustic sensor networks[J]. Wireless networks, 2016, 22(6): 1985-1997.

[16]張瑞華, 程合友, 賈智平. 基于能量效率的無線傳感器網絡分簇算法[J]. 吉林大學學報: 工學版, 2010, 40(6): 1663-1667. ZHANG Ruihua, CHENG Heyou, JIA Zhiping. Energy-efficient clustering algorithm for wireless sensor net works[J]. Journal of Jilin university: engineering and technology edition, 2010, 40(6): 1663-1667.

[17]ZHAO Liang, LIANG Qilian. Optimum cluster size for underwater acoustic sensor networks[C]//Proceedings of IEEE Military Communications Conference. Washington, DC: IEEE, 2006: 1-5.

[18]YANG Guangsong, XIAO Mingbo, CHENG En, et al. A cluster-head selection scheme for underwater acoustic sensor networks[C]//Proceedings of 2010 International Conference on Communications and Mobile Computing. Shenzhen: IEEE, 2010: 188-191.

[19]LI Yongcui, WANG Ying, JU Yang, et al. Energy efficient cluster formulation protocols in clustered underwater acoustic sensor networks[C]//Proceedings of the 7th International Conference on Biomedical Engineering and Informatics (BMEI). Dalian: IEEE, 2014: 923-928

[20]JIANG Peng, LIU Jun, WU Feng. Node non-uniform deployment based on clustering algorithm for underwater sensor networks[J]. Sensors, 2015, 15(12): 29997-30010.

[21]卞金洪, 徐新洲, 魏昕, 等. 水聲通信網層次路由算法[J]. 哈爾濱工程大學學報, 2013, 34(3): 275-279. BIAN Jinhong, XU Xinzhou, WEI Xin, et al. Research on hierarchical routing algorithm for underwater acoustic communication networks[J]. Journal of Harbin engineering university, 2013, 34(3): 275-279.

Optimization of the cluster-head selection algorithm of an energy-based underwater acoustic sensor network

ZHAO Danfeng1,CHEN Tong1,2

( 1.College of Information and Communication Engineering, Harbin Engineering University,Harbin 150001,China; 2.Beijing Great Wall Electronic Equipment Co.,Ltd,Beijing 100082,China)

To solve the uneven energy consumption problem caused by the time-varying characteristics of underwater acoustic channels and non-uniform distribution of cluster heads in underwater acoustic sensor networks (UASNs), a novel distributed low-energy adaptive clustering hierarchy (LEACH) algorithm was developed. The number of elections was increased in each round, and an energy threshold for the first cluster-head elections was set. If the node energy is higher than the energy threshold, the former can take part in the first cycle of cluster-head election, and the second cycle of cluster-head election can maintain the stability of the cluster-head number. Simulation results showed that the improved algorithm can eliminate the problem of unbalanced energy consumption under the time-varying channel conditions of the clustered acoustic sensor network. It can also balance the energy consumption of the network and prolong the survival period of the network′s first node.

underwater acoustic sensor network; LEACH; cluster-head; distribution; energy consumption

2016-03-15.

日期：2016-11-16.

國家自然科學基金項目(61371099).

趙旦峰(1961-), 男, 教授,博士生導師.

趙旦峰,E-mail：zhaodanfeng@hrbeu.edu.cn.

10.11990/jheu.201603047

http://www.cnki.net/kcms/detail/23.1390.u.20161116.1613.008.html

TN929.3

A

1006-7043(2017)02-0282-06

趙旦峰, 陳通. 基于能量的水聲傳感器網絡分簇算法優化[J]. 哈爾濱工程大學學報， 2017, 38(2): 282-287. ZHAO Danfeng, CHEN Tong. Optimization of the cluster-head selection algorithm of an energy-based underwater acoustic sensor network[J]. Journal of Harbin Engineering University, 2017, 38(2): 282-287.