基于能耗均衡的水下傳感器網絡分簇路由算法

姜衛(wèi)東，郭勇，劉胤祥

?

基于能耗均衡的水下傳感器網絡分簇路由算法

姜衛(wèi)東1，郭勇2，劉胤祥1

(1. 海軍指揮學院信息系，江蘇南京211800；2. 海軍91451部隊河北邯鄲 056107)

針對水下傳感器網絡能耗不均衡問題，提出一種能耗均衡的多跳非均勻分簇路由算法。算法在水下傳感器網絡非均勻分簇的基礎上，通過改進節(jié)點簇頭競選的閾值計算方式，解決了網絡后期簇頭競選閾值低導致的網絡能耗激增；通過引入多跳路由選擇公式，綜合考慮節(jié)點剩余能量和鏈路能耗，延長網絡生命周期。仿真表明，提出的算法生成簇頭數目穩(wěn)定，能耗較低，并且能有效延長水下傳感器網絡的生命周期。

水下傳感器網絡；能耗均衡；非均勻分簇；分簇路由

0 引言

水下傳感器網絡在海洋數據采集、污染監(jiān)測、海洋勘探、災難預警、輔助導航、戰(zhàn)場監(jiān)視和礦產探測等方面顯現出重要作用[1]。與陸上無線傳感器網絡相比，海洋水文、地理和聲場環(huán)境異常復雜，且存在水下傳感器網絡節(jié)點位置不固定，電池不易更換等不利因素，因此設計能量高效的水下傳感器網絡路由協(xié)議非常困難。

基于分簇的路由協(xié)議網絡能耗小、易擴展，引起國內外專家學者的關注[2]。張宏滔[3]等提出一種節(jié)省能量的水聲傳感器網絡的組織結構，網絡節(jié)點以簇的形式組織起來，利用有限的時延，換取通信量的減少，從而延長網絡的生命周期。Domingo[4]等學者提出了一種分布式水下分簇算法(Distributed Underwater Clustering Scheme, DUCS)，仿真結果表明DUCS算法有效降低了網絡開銷，具有較高的包投遞率。雖然分簇路由算法在網絡能耗上具有一定的優(yōu)勢，但仍存在以下三方面問題。

(1) 簇頭選舉隨機，能耗不均衡

Heinzelman[5]最先提出一種低能耗自適應分簇路由算法(Low-Energy Adaptive Clustering Hierarchy, LEACH)，將網絡分成大小均勻的簇，簇內節(jié)點通過單跳方式將數據傳送給簇頭，簇頭再與基站單跳通信，降低了網絡能耗。但該算法通過能量無關的簇頭競選公式進行簇頭選舉，導致簇頭選舉隨機、能耗不均，部分節(jié)點易過早死亡出現“死區(qū)”問題。Handy[6]等提出了一種改進簇頭競選閾值的算法(Deterministic Cluster-Head Selection, DCHS)，簇頭選舉過程中考慮了節(jié)點剩余能量等因素，均衡了網絡能耗。但隨著網絡運行時間增加，簇頭選舉的閾值降低，網絡中簇頭個數減少，能耗急劇增大。

(2) “遠近”問題

“遠近”問題是指，當簇頭與基站單跳通信時，距離基站較遠的節(jié)點由于消耗功率較大，會先于距離基站較近的節(jié)點耗盡能量，過早失效，導致網絡不完整，進而影響網絡性能。采用多跳傳輸方法可有效解決“遠近”問題，多跳傳輸時，距基站較遠的節(jié)點減少了發(fā)送功率，降低了能耗，但中繼節(jié)點由于要轉發(fā)其它節(jié)點的數據，能耗增加。

(3) “熱點”問題

在多跳分簇網絡中，靠近基站的簇頭需要中繼較遠簇頭的數據包，容易先耗盡能量，出現所謂的“熱點”問題。李成法[7]提出了一種能量有效的非均勻分簇算法(Energy-Efficient Uneven Clustering, EEUC)，有效解決了熱點問題，但算法在簇頭的選舉上僅考慮剩余能量，不能保證簇頭的合理性。雷輝[8]提出的能量高效的多跳非均勻分簇算法(Energy Efficient Multi-hop Uneven Clustering, EEMUC)改進算法，雖提高了水聲傳感器網絡的能量效率，延長了網絡的生命周期，但隨著網絡運行時間增加，節(jié)點綜合屬性值隨之減小，同樣出現了DCHS算法中的能耗急劇增大的問題。

本文針對分簇算法中存在簇頭選舉不合理，后期簇頭數目銳減等導致能耗不均衡的問題，提出一種基于能耗均衡的水下傳感器多跳非均勻分簇路由算法(Multi-hop Uneven Clustering routing algorithm based on Energy Consumption Balance, MUCECB)。

1 模型描述

1.1 網絡模型

本文考慮靜態(tài)二維水下傳感器網絡，對網絡模型作如下假設：

(1) 所有節(jié)點是同構的，初始能量相同，具有唯一的節(jié)點編號；

(2) 節(jié)點可以根據通信距離調整發(fā)射功率等級來節(jié)約能耗；

(3) 鏈路具有對稱性，節(jié)點可根據接收到的信號強度與發(fā)射功率等級計算與發(fā)送方之間的距離；

(4) 基站部署在監(jiān)測區(qū)域外，可與網絡內任意節(jié)點通信，不考慮其能量消耗。

1.2 能量消耗模型

水聲傳感器節(jié)點能量消耗與無線傳感器不同，隨著距離的增加，其能耗是指數級增長，文獻[8]對水聲傳感器節(jié)點能量消耗有合理描述，要發(fā)送比特的數據包，發(fā)射機的能量消耗為

(2)

接收機接收比特的數據包則接收機的能量消耗為

2 MUCECB算法

該算法的基本思路是：按照節(jié)點到基站的距離將節(jié)點進行非均勻分層，靠近基站的分層內網絡節(jié)點數較少；根據節(jié)點距基站的遠近得到不同的成簇半徑，并按由剩余能量、節(jié)點在層中的位置和節(jié)點密度計算節(jié)點的綜合屬性值，將其歸一化得到簇頭競選閾值，由閾值在層內產生候選簇頭；每層的候選簇頭按照綜合屬性值的大小在其成簇半徑內競選簇頭，簇頭產生后普通節(jié)點按距離簇頭的遠近入簇；簇頭節(jié)點根據設計的路由選擇公式建立多跳路由。

2.1 候選簇頭的生成

2.1.1網絡分層模型

為均衡水下傳感器網絡能耗，本文按文獻[9]的方法對水下傳感器網絡構造非均勻分層模型。靠近匯聚節(jié)點的層內節(jié)點較少，層次面積較小；遠離匯聚節(jié)點的層中節(jié)點數較多，面積較大。圖1為網絡非均勻分層示意圖，其中第層上下邊界半徑分別為、，為第層的寬度，層中虛線為距離各層上下邊界距離相等的點連成的線，即某一分層的層中心線。

2.1.2節(jié)點綜合屬性值計算

根據節(jié)點剩余能量、節(jié)點到所在分層中心線的距離、節(jié)點密度計算每個節(jié)點的綜合屬性值為

2.1.3候選簇頭生成

(6)

2.2 簇的建立

候選簇頭節(jié)點根據簇頭競選閾值，計算簇頭廣播的觸發(fā)時間，每個候選簇頭僅以自己競爭半徑的最大功率廣播。層內所有候選簇頭都廣播完畢后，開始選舉簇頭。若候選簇頭與同層競爭范圍內的其它候選簇頭相比其綜合屬性值最高，則當選簇頭，并廣播當選信息。非最優(yōu)值的候選簇頭處于監(jiān)聽狀態(tài)，收到同層內其它節(jié)點當選信息后，加入該簇，若未收到任何當選信息，則自己當選簇頭，并廣播當選信息。其它節(jié)點一旦收到同層簇頭的當選信息，則加入該簇，若一直未收到當選信息，則選擇距離最近的簇加入。

2.3 簇間多跳路由

簇間多跳路由的建立，既要考慮節(jié)點間的傳輸能耗，又要考慮前向路由節(jié)點的剩余能量。

(1) 建立簇頭節(jié)點的前向路由備選集，簇頭節(jié)點廣播路由信息，包括節(jié)點ID、剩余能量、上一次作為簇頭的能量消耗和所在層次等，簇頭若接收到層次數比其小的路由信息則將其保存，建立前向路由備選集。

(2) 建立路由選擇公式：

由式(7)得出，節(jié)點前向路由備選集中節(jié)點的剩余能量越大、上次作為簇頭的能耗越小、距離節(jié)點的距離越小，則越大。圖2是MUCECB的簇間路由示意圖。

3 實驗仿真及結果分析

對LEACH[5]、EEUC[7]、EEMUC[9]和本文提出的MUCECB四種算法進行仿真對比實驗，分別從生成簇頭數目的穩(wěn)定性、能耗和網絡生存時間比較算法性能，網絡參數設置如表1所示。

3.1 算法生成簇頭數目的穩(wěn)定性

在網絡拓撲相對穩(wěn)定的條件下，一個好的分簇算法生成的簇頭數目相對穩(wěn)定所示。

圖3仿真結果可以看出，LEACH算法生成的簇頭數目波動較大，范圍為[2,13]，其它三種算法生成的簇頭數目較穩(wěn)定，EEUC為[3,8]，EEMUC為[4,8]，MUCECB為[5,7]。可見MUCECB算法生成的簇頭個數波動較小，算法比較穩(wěn)定。

表1 仿真參數

3.2 算法能耗

圖4是按輪數得到的四種算法的每輪能耗圖。

LEACH算法每輪能耗不均，起伏大，平均能耗最高，這是由于其簇頭是隨機選取，沒有考慮節(jié)點剩余能量造成的。EEUC、EEMUC、MUCECB平均能耗依次降低，MUCECB每輪能耗波動幅度均低于其它三種算法，可見MUCECB算法節(jié)能性更好。

3.3 網絡生存時間

網絡生存時間是衡量一個分簇算法能量效率的重要指標。本文設定節(jié)點能量少于初始能量的20%時，節(jié)點死亡；網絡中有80%節(jié)點死亡時，網絡失效。對上述四種算法分別進行10次獨立實驗，記錄其網絡生存時間，實驗結果如表2所示。

表2 四種算法網絡生存時間實驗結果

由表2可以看出，MUCECB的網絡生存時間最長，平均為1435輪，而LEACH、EEUC和EEMUC分別為837輪、1191輪和1330輪。即在網絡生存周期上，本文提出的MUCECB算法比LEACH、EEUC和EEMUC算法分別延長了71.45%、20.49%和7.89%。可見MUCECB算法能有效延長網絡生命周期。

4 結語

本文設計了一種基于能耗均衡的多跳非均勻分簇路由協(xié)議，簇頭選舉中綜合考慮節(jié)點剩余能量、節(jié)點距層中心的距離、節(jié)點密度等因素；并將節(jié)點綜合屬性值歸一化處理解決網絡運行后期簇頭較少、能耗激增等問題。根據建立的路由選擇公式建立層間路由，選擇節(jié)點剩余能量多并且鏈路能耗小的路由，進一步降低了能耗。

[1] DARIO POMPILI. Efficient Communication Protocols For Underwater Acoustic Sensor Networks[D]. Atlanta: Georgia Institute of Technology, 2007.

[2] KUMAR D, ASERI T C, PATEL R B．EEHC：Energy efficient heterogeneous clustered scheme for wireless sensor networks[J]. Computer Communications, 2009, 32(4): 662-667.

[3] 張宏滔, 陸佶人, 童峰. 一種節(jié)省能量的水聲傳感器網絡組織結構與協(xié)議[J]. 電路與系統(tǒng)學報, 2005, 10(3): 16-20.

ZHANG Hongtao, LU Jiren, TONG Feng. An energy-efficient framework and protocol for underwater acoustic sensor networks[J]. Journal of Circuits and Systems, 2005, 10(3): 16-20.

[4] Domingo M C, Prior R. A distributed clustering scheme for underwater wireless sensor networks[C]// The 18th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, Athens, Greece, 2007: 1-5.

[5] HEINZELMAN WR, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks[C]// Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Maui, Hawaii, IEEE Computer Society, 2000: 3005-3014.

[6] HANDY M J, HAASE M, TMMERMANN D. Low energy adaptive clustering hierarchy with deterministic cluster-head selection[C]// Proceedings of the 4th IEEE Conference on Mobile and Wireless Communications Networks Stockholm: IEEE Communications Society, 2002: 368-372.

[7] 李成法, 陳貴海, 葉懋, 等. 一種基于非均勻分簇的無線傳感器網絡路由協(xié)議[J]. 計算機學報, 2007, 30(1): 27-36.

LI Chengfa, CHEN Guihai, YE Mao, et al. An uneven cluster-based routing protocol for wireless sensor networks[J]. Chinese Journal of Computers, 2007, 30(1): 27-36.

[8] ZHAO Liang, LIANG Qilian. Optimum Cluster Size for Underwater Acoustic Sensor Networks[C]// Proceedings of the IEEE Military Communications Conference (MILCOM 2006). Washington: IEEE Press, 2006: 1-5.

[9] 雷輝, 姜衛(wèi)東, 郭勇. 能量高效的水聲傳感器網絡多跳非均勻分簇算法[J]. 計算機應用, 2013, 33(1): 124-126.

LEI Hui, JIANG Weidong, GUO Yong, Energy-efficient multi-hop uneven clustering algorithm for underwater acoustic sensor network[J]. Journal of Computer Applications, 2013, 33(1): 124-126.

A clustering routing algorithm based on energy consumption balance for underwater sensor networks

JIANG Wei-dong1, GUO Yong2, LIU Yin-xiang1

(1. Department of Information, Naval Command College, Nanjing 211800, Jiangsu, China;2. The Navy Unit 91451, Handan 056107,Hebei, China)

Concerning the problem of unbalanced energy consumption in the underwater sensor networks, a Multi-hop Uneven Clustering routing algorithm based on Energy Consumption Balance (MUCECB) is proposed. This algorithm modifies the threshold of selecting cluster head to reduce the sharp increase of the energy consumption, which is led by the reduction of nodes’ threshold during the end of the networks’ run time. In order to prolong the lifetime of networks, a multi-hop formula of forwarding selected routing is introduced, which considers not only the nodes’ rest energy, but also the energy consumption. Simulation results show that, the presented algorithm has stable numbers of cluster heads and low energy consumption and also prolongs the lifetime of the underwater sensor networks.

underwater sensor networks; energy consumption balance; uneven clustering; clustering routing

TN929.3

A

1000-3630(2015)-02-0134-05

10.16300/j.cnki.1000-3630.2015.02.006

2014-04-09;

2014-07-21

全軍軍事類研究生資助課題金項目(2013JY411)

姜衛(wèi)東(1972－), 男, 江蘇海門人, 博士, 副教授, 研究方向為水聲信號處理、盲信號處理、水聲通信等。

姜衛(wèi)東, E-mail: weidong_j@sina.com