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

?

基于能耗均衡的水下傳感器網(wǎng)絡(luò)分簇路由算法

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

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

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

水下傳感器網(wǎng)絡(luò)；能耗均衡；非均勻分簇；分簇路由

0 引言

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

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

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

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

(2) “遠(yuǎn)近”問題

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

(3) “熱點(diǎn)”問題

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

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

1 模型描述

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

本文考慮靜態(tài)二維水下傳感器網(wǎng)絡(luò)，對(duì)網(wǎng)絡(luò)模型作如下假設(shè)：

(1) 所有節(jié)點(diǎn)是同構(gòu)的，初始能量相同，具有唯一的節(jié)點(diǎn)編號(hào)；

(2) 節(jié)點(diǎn)可以根據(jù)通信距離調(diào)整發(fā)射功率等級(jí)來節(jié)約能耗；

(3) 鏈路具有對(duì)稱性，節(jié)點(diǎn)可根據(jù)接收到的信號(hào)強(qiáng)度與發(fā)射功率等級(jí)計(jì)算與發(fā)送方之間的距離；

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

1.2 能量消耗模型

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

(2)

接收機(jī)接收比特的數(shù)據(jù)包則接收機(jī)的能量消耗為

2 MUCECB算法

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

2.1 候選簇頭的生成

2.1.1網(wǎng)絡(luò)分層模型

為均衡水下傳感器網(wǎng)絡(luò)能耗，本文按文獻(xiàn)[9]的方法對(duì)水下傳感器網(wǎng)絡(luò)構(gòu)造非均勻分層模型?？拷鼌R聚節(jié)點(diǎn)的層內(nèi)節(jié)點(diǎn)較少，層次面積較??；遠(yuǎn)離匯聚節(jié)點(diǎn)的層中節(jié)點(diǎn)數(shù)較多，面積較大。圖1為網(wǎng)絡(luò)非均勻分層示意圖，其中第層上下邊界半徑分別為、，為第層的寬度，層中虛線為距離各層上下邊界距離相等的點(diǎn)連成的線，即某一分層的層中心線。

2.1.2節(jié)點(diǎn)綜合屬性值計(jì)算

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

2.1.3候選簇頭生成

(6)

2.2 簇的建立

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

2.3 簇間多跳路由

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

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

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

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

3 實(shí)驗(yàn)仿真及結(jié)果分析

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

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

在網(wǎng)絡(luò)拓?fù)湎鄬?duì)穩(wěn)定的條件下，一個(gè)好的分簇算法生成的簇頭數(shù)目相對(duì)穩(wěn)定所示。

圖3仿真結(jié)果可以看出，LEACH算法生成的簇頭數(shù)目波動(dòng)較大，范圍為[2,13]，其它三種算法生成的簇頭數(shù)目較穩(wěn)定，EEUC為[3,8]，EEMUC為[4,8]，MUCECB為[5,7]?？梢奙UCECB算法生成的簇頭個(gè)數(shù)波動(dòng)較小，算法比較穩(wěn)定。

表1 仿真參數(shù)

3.2 算法能耗

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

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

3.3 網(wǎng)絡(luò)生存時(shí)間

網(wǎng)絡(luò)生存時(shí)間是衡量一個(gè)分簇算法能量效率的重要指標(biāo)。本文設(shè)定節(jié)點(diǎn)能量少于初始能量的20%時(shí)，節(jié)點(diǎn)死亡；網(wǎng)絡(luò)中有80%節(jié)點(diǎn)死亡時(shí)，網(wǎng)絡(luò)失效。對(duì)上述四種算法分別進(jìn)行10次獨(dú)立實(shí)驗(yàn)，記錄其網(wǎng)絡(luò)生存時(shí)間，實(shí)驗(yàn)結(jié)果如表2所示。

表2 四種算法網(wǎng)絡(luò)生存時(shí)間實(shí)驗(yàn)結(jié)果

由表2可以看出，MUCECB的網(wǎng)絡(luò)生存時(shí)間最長(zhǎng)，平均為1435輪，而LEACH、EEUC和EEMUC分別為837輪、1191輪和1330輪。即在網(wǎng)絡(luò)生存周期上，本文提出的MUCECB算法比LEACH、EEUC和EEMUC算法分別延長(zhǎng)了71.45%、20.49%和7.89%?？梢奙UCECB算法能有效延長(zhǎng)網(wǎng)絡(luò)生命周期。

4 結(jié)語

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

[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é)省能量的水聲傳感器網(wǎng)絡(luò)組織結(jié)構(gòu)與協(xié)議[J]. 電路與系統(tǒng)學(xué)報(bào), 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] 李成法, 陳貴海, 葉懋, 等. 一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J]. 計(jì)算機(jī)學(xué)報(bào), 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)東, 郭勇. 能量高效的水聲傳感器網(wǎng)絡(luò)多跳非均勻分簇算法[J]. 計(jì)算機(jī)應(yīng)用, 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

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

姜衛(wèi)東(1972－), 男, 江蘇海門人, 博士, 副教授, 研究方向?yàn)樗曅盘?hào)處理、盲信號(hào)處理、水聲通信等。

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