基于能耗均衡的水下传感器网络分簇路由算法

姜卫东，郭勇，刘胤祥



基于能耗均衡的水下传感器网络分簇路由算法

姜卫东1，郭勇2，刘胤祥1

(1. 海军指挥学院信息系，江苏南京211800；2. 海军91451部队河北邯郸 056107)

针对水下传感器网络能耗不均衡问题，提出一种能耗均衡的多跳非均匀分簇路由算法。算法在水下传感器网络非均匀分簇的基础上，通过改进节点簇头竞选的阈值计算方式，解决了网络后期簇头竞选阈值低导致的网络能耗激增；通过引入多跳路由选择公式，综合考虑节点剩余能量和链路能耗，延长网络生命周期。仿真表明，提出的算法生成簇头数目稳定，能耗较低，并且能有效延长水下传感器网络的生命周期。

水下传感器网络；能耗均衡；非均匀分簇；分簇路由

0 引言

水下传感器网络在海洋数据采集、污染监测、海洋勘探、灾难预警、辅助导航、战场监视和矿产探测等方面显现出重要作用[1]。与陆上无线传感器网络相比，海洋水文、地理和声场环境异常复杂，且存在水下传感器网络节点位置不固定，电池不易更换等不利因素，因此设计能量高效的水下传感器网络路由协议非常困难。

基于分簇的路由协议网络能耗小、易扩展，引起国内外专家学者的关注[2]。张宏滔[3]等提出一种节省能量的水声传感器网络的组织结构，网络节点以簇的形式组织起来，利用有限的时延，换取通信量的减少，从而延长网络的生命周期。Domingo[4]等学者提出了一种分布式水下分簇算法(Distributed Underwater Clustering Scheme, DUCS)，仿真结果表明DUCS算法有效降低了网络开销，具有较高的包投递率。虽然分簇路由算法在网络能耗上具有一定的优势，但仍存在以下三方面问题。

(1) 簇头选举随机，能耗不均衡

Heinzelman[5]最先提出一种低能耗自适应分簇路由算法(Low-Energy Adaptive Clustering Hierarchy, LEACH)，将网络分成大小均匀的簇，簇内节点通过单跳方式将数据传送给簇头，簇头再与基站单跳通信，降低了网络能耗。但该算法通过能量无关的簇头竞选公式进行簇头选举，导致簇头选举随机、能耗不均，部分节点易过早死亡出现“死区”问题。Handy[6]等提出了一种改进簇头竞选阈值的算法(Deterministic Cluster-Head Selection, DCHS)，簇头选举过程中考虑了节点剩余能量等因素，均衡了网络能耗。但随着网络运行时间增加，簇头选举的阈值降低，网络中簇头个数减少，能耗急剧增大。

(2) “远近”问题

“远近”问题是指，当簇头与基站单跳通信时，距离基站较远的节点由于消耗功率较大，会先于距离基站较近的节点耗尽能量，过早失效，导致网络不完整，进而影响网络性能。采用多跳传输方法可有效解决“远近”问题，多跳传输时，距基站较远的节点减少了发送功率，降低了能耗，但中继节点由于要转发其它节点的数据，能耗增加。

(3) “热点”问题

在多跳分簇网络中，靠近基站的簇头需要中继较远簇头的数据包，容易先耗尽能量，出现所谓的“热点”问题。李成法[7]提出了一种能量有效的非均匀分簇算法(Energy-Efficient Uneven Clustering, EEUC)，有效解决了热点问题，但算法在簇头的选举上仅考虑剩余能量，不能保证簇头的合理性。雷辉[8]提出的能量高效的多跳非均匀分簇算法(Energy Efficient Multi-hop Uneven Clustering, EEMUC)改进算法，虽提高了水声传感器网络的能量效率，延长了网络的生命周期，但随着网络运行时间增加，节点综合属性值随之减小，同样出现了DCHS算法中的能耗急剧增大的问题。

本文针对分簇算法中存在簇头选举不合理，后期簇头数目锐减等导致能耗不均衡的问题，提出一种基于能耗均衡的水下传感器多跳非均匀分簇路由算法(Multi-hop Uneven Clustering routing algorithm based on Energy Consumption Balance, MUCECB)。

1 模型描述

1.1 网络模型

本文考虑静态二维水下传感器网络，对网络模型作如下假设：

(1) 所有节点是同构的，初始能量相同，具有唯一的节点编号；

(2) 节点可以根据通信距离调整发射功率等级来节约能耗；

(3) 链路具有对称性，节点可根据接收到的信号强度与发射功率等级计算与发送方之间的距离；

(4) 基站部署在监测区域外，可与网络内任意节点通信，不考虑其能量消耗。

1.2 能量消耗模型

水声传感器节点能量消耗与无线传感器不同，随着距离的增加，其能耗是指数级增长，文献[8]对水声传感器节点能量消耗有合理描述，要发送比特的数据包，发射机的能量消耗为

(2)

接收机接收比特的数据包则接收机的能量消耗为

2 MUCECB算法

该算法的基本思路是：按照节点到基站的距离将节点进行非均匀分层，靠近基站的分层内网络节点数较少；根据节点距基站的远近得到不同的成簇半径，并按由剩余能量、节点在层中的位置和节点密度计算节点的综合属性值，将其归一化得到簇头竞选阈值，由阈值在层内产生候选簇头；每层的候选簇头按照综合属性值的大小在其成簇半径内竞选簇头，簇头产生后普通节点按距离簇头的远近入簇；簇头节点根据设计的路由选择公式建立多跳路由。

2.1 候选簇头的生成

2.1.1网络分层模型

为均衡水下传感器网络能耗，本文按文献[9]的方法对水下传感器网络构造非均匀分层模型。靠近汇聚节点的层内节点较少，层次面积较小；远离汇聚节点的层中节点数较多，面积较大。图1为网络非均匀分层示意图，其中第层上下边界半径分别为、，为第层的宽度，层中虚线为距离各层上下边界距离相等的点连成的线，即某一分层的层中心线。

2.1.2节点综合属性值计算

根据节点剩余能量、节点到所在分层中心线的距离、节点密度计算每个节点的综合属性值为

2.1.3候选簇头生成

(6)

2.2 簇的建立

候选簇头节点根据簇头竞选阈值，计算簇头广播的触发时间，每个候选簇头仅以自己竞争半径的最大功率广播。层内所有候选簇头都广播完毕后，开始选举簇头。若候选簇头与同层竞争范围内的其它候选簇头相比其综合属性值最高，则当选簇头，并广播当选信息。非最优值的候选簇头处于监听状态，收到同层内其它节点当选信息后，加入该簇，若未收到任何当选信息，则自己当选簇头，并广播当选信息。其它节点一旦收到同层簇头的当选信息，则加入该簇，若一直未收到当选信息，则选择距离最近的簇加入。

2.3 簇间多跳路由

簇间多跳路由的建立，既要考虑节点间的传输能耗，又要考虑前向路由节点的剩余能量。

(1) 建立簇头节点的前向路由备选集，簇头节点广播路由信息，包括节点ID、剩余能量、上一次作为簇头的能量消耗和所在层次等，簇头若接收到层次数比其小的路由信息则将其保存，建立前向路由备选集。

(2) 建立路由选择公式：

由式(7)得出，节点前向路由备选集中节点的剩余能量越大、上次作为簇头的能耗越小、距离节点的距离越小，则越大。图2是MUCECB的簇间路由示意图。

3 实验仿真及结果分析

对LEACH[5]、EEUC[7]、EEMUC[9]和本文提出的MUCECB四种算法进行仿真对比实验，分别从生成簇头数目的稳定性、能耗和网络生存时间比较算法性能，网络参数设置如表1所示。

3.1 算法生成簇头数目的稳定性

在网络拓扑相对稳定的条件下，一个好的分簇算法生成的簇头数目相对稳定所示。

图3仿真结果可以看出，LEACH算法生成的簇头数目波动较大，范围为[2,13]，其它三种算法生成的簇头数目较稳定，EEUC为[3,8]，EEMUC为[4,8]，MUCECB为[5,7]。可见MUCECB算法生成的簇头个数波动较小，算法比较稳定。

表1 仿真参数

3.2 算法能耗

图4是按轮数得到的四种算法的每轮能耗图。

LEACH算法每轮能耗不均，起伏大，平均能耗最高，这是由于其簇头是随机选取，没有考虑节点剩余能量造成的。EEUC、EEMUC、MUCECB平均能耗依次降低，MUCECB每轮能耗波动幅度均低于其它三种算法，可见MUCECB算法节能性更好。

3.3 网络生存时间

网络生存时间是衡量一个分簇算法能量效率的重要指标。本文设定节点能量少于初始能量的20%时，节点死亡；网络中有80%节点死亡时，网络失效。对上述四种算法分别进行10次独立实验，记录其网络生存时间，实验结果如表2所示。

表2 四种算法网络生存时间实验结果

由表2可以看出，MUCECB的网络生存时间最长，平均为1435轮，而LEACH、EEUC和EEMUC分别为837轮、1191轮和1330轮。即在网络生存周期上，本文提出的MUCECB算法比LEACH、EEUC和EEMUC算法分别延长了71.45%、20.49%和7.89%。可见MUCECB算法能有效延长网络生命周期。

4 结语

本文设计了一种基于能耗均衡的多跳非均匀分簇路由协议，簇头选举中综合考虑节点剩余能量、节点距层中心的距离、节点密度等因素；并将节点综合属性值归一化处理解决网络运行后期簇头较少、能耗激增等问题。根据建立的路由选择公式建立层间路由，选择节点剩余能量多并且链路能耗小的路由，进一步降低了能耗。

[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] 张宏滔, 陆佶人, 童峰. 一种节省能量的水声传感器网络组织结构与协议[J]. 电路与系统学报, 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] 李成法, 陈贵海, 叶懋, 等. 一种基于非均匀分簇的无线传感器网络路由协议[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] 雷辉, 姜卫东, 郭勇. 能量高效的水声传感器网络多跳非均匀分簇算法[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)

姜卫东(1972－), 男, 江苏海门人, 博士, 副教授, 研究方向为水声信号处理、盲信号处理、水声通信等。

姜卫东, E-mail: weidong_j@sina.com