洪昌建吴伟杰 唐平鹏

(武汉第二船舶设计研究所 武汉 430064)

动态分层的水下传感器网络分簇路由算法

洪昌建*吴伟杰 唐平鹏

(武汉第二船舶设计研究所 武汉 430064)

针对平面路由难以适应较大规模水下传感器网络的局限，该文提出一种能更好地适用于较大规模网络的分簇路由算法DLCR(Dynamic Layered Clustering Routing)。该算法将网络自上向下划分为多层，并选择层内与sink节点距离较近、剩余能量较高的节点作为簇头节点，从而降低簇头节点的通信能耗。为了避免同一节点连续被选举为簇头节点，提出一种动态分层机制，每一轮数据采集周期都将网络重新划分为多层。实验证明DLCR不仅具有良好的稳定性，还降低了网络的能耗，延长了网络的寿命。

水下传感器网络；动态分层机制；分簇路由

1 引言

随着世界各国对海洋权益的日益重视、发展海洋经济热潮的兴起和陆地无线传感器网络研究的迅速发展，水下传感器网络(Underwater Sensor Networks, USN)已经成为新的研究热点[1,2]。水下传感器网络将采集到的水下环境数据发送给用户来辅助决策，在环境监测、资源勘探、灾难预警和潜艇探测等民用和军用领域均具有广阔的应用前景[3,4]。

在实际应用中，由于水下传感器网络的特殊网络环境，无线电波在水中衰减迅速，不适合作长距离的数据传输，因而通常采用水声通信；由于GPS在水中无法使用，节点的位置信息未知；同时节点受水流的影响在一定范围内移动，造成了网络的间歇连通性。以上均为水下传感器网络的路由带来了极大的挑战。

关于水下传感器网络的路由策略已有大量研究。以DBR[5]算法为代表的平面路由算法为水下传感器网络的组网提供了良好的解决方案。然而平面路由算法常用于较小规模的网络，如果网络规模较大，靠近sink的节点会承担过多的数据转发而消耗大量的能量，导致这一部分节点提前死亡而形成能量空洞，这些节点死亡后又会加剧其周围节点的死亡，故延缓能量空洞的出现有助于延长网络的寿命。相对于平面路由算法，分簇路由能够使网络的能量负载更加均衡，因此为了适应大规模的网络环境，采用分簇路由算法则能够在一定程度上延缓能量空洞的出现，有效地延长网络的寿命。

目前，研究者对于分簇路由算法的研究主要集中在传统地面无线传感器网络上，其网络形态为2维平面网络，此类算法不能直接应用于3维水下传感器网络环境中。关于3维水下传感器网络分簇路由算法，国内外研究者也做了相应的理论研究，但大多数算法都建立在2维地面传感器网络分簇路由算法的基础上，将2维地面传感器网络的分簇路由算法移植到3维水下传感器网络环境中，没有考虑水下传感器网络节点的移动性、位置信息未知等特点，并不能真正地解决水下传感器网络的分簇路由问题。主要存在以下几点不足：(1)基于地理位置信息的分簇算法，如LCAD[6], MCCP[7]等。此类算法的簇头选举代价函数通常涉及到节点间距、位置等信息，采用水声通信的水下传感器网络无法利用GPS来定位。采用无线测距的方式则存在较大的误差，而且水下测距和节点定位已成为另一个研究的热点问题；(2)未充分考虑节点移动性给网络带来的影响，此类算法如UDA[8], E-PULRP[9]等多采用静态3维网络模型，忽略了节点移动给网络拓扑带来的影响；(3)引入其他移动数据采集装置或者引入特殊节点解决水下传感器网络特殊性带来的问题，此类算法如TCBR[10], UW-HSNs[11]等虽然能被很好应用，但额外的设备也增加了网络的成本；(4)其他分簇算法如DUCS[12], DEAR[13]等虽然为水下传感器网络分簇路由提供了解决方案并能够较好适应水下环境，但随着网络的运行，该算法最终会退化为随机成簇算法，因而其网络能量的利用率仍有较大的提升空间。在不依赖节点位置信息和考虑节点移动性的基础上，本文网络节点通信半径可以在数据采集周期的不同阶段进行自调整，从而保证网络的可靠性；并对网络进行初始分层，使簇头尽可能地位于层内偏上方，即与sink节点的距离较近，从而减少簇头节点的能耗。并且，每次数据采集周期开始前都要动态地调整网络分层，使簇头节点始终尽可能存在层内的偏上方，同时可以降低同一节点连续被选为簇头节点的概率。分层的引入不仅简化了网络模型，还能够使簇头分布得更加均匀，有助于均衡网络的负载。

2 相关模型和假定

2.1 网络拓扑模型

本文的研究对象为3维水下传感器网络，该网络是由固定在水底的静态节点、悬浮在水中的动态节点、和浮在水面的sink节点构成。

如图1所示，在网络的初始阶段，若干个水下传感器节点随机地部署在一个长方体监控区域内，若干个sink节点随机地分布在监控领域的水面上方。本文对水下传感器网络做了如下的假设：

(1)假定sink节点的数量足够多使sink节点的间距始终小于一个固定值ds；

图1 水下传感器网络模型

(2)所有节点均具有唯一的标志，节点采用水声通信的方式进行消息传递，消息被发送到任意的sink节点均表示被成功地接收；

(3)所有非sink节点具有可调的处理/通信能力，但无法通过水声信号来感知节点间距离；

(4)节点受水流的影响在一定范围内移动，假定具有最大的偏移距离r；

(5)节点周期性地进行数据采集，且始终有数据传送至sink；

(6)分别采用第1个节点死亡和10%节点死亡的时间[14]作为网络寿命的衡量参数。

2.2 水声通信能耗模型

本文算法采用与文献[15]相同的水声通信能耗模型。对于水下传感器节点，消息发送产生的能耗大约为消息接收和空闲侦听所消耗能量的几十倍，因而消息发送产生的能耗占据了网络总能耗的极大比例，降低消息发送产生的能耗就意味着降低了整个网络的总能耗[16]。本文算法将消息发送产生的能耗作为衡量整个网络总能耗的主要参数，即不考虑消息接收产生的能耗。

假定Po为节点能够正常接收消息所需的最低功率，若功率对传播距离x的衰减函数为A(x)，那么节点的发送功率至少应达到PoA(x)才能保证节点能接收到该消息。设节点发送l bit数据的发送时延为TP，则发送l bit数据消耗的能量Etr(l,x)为

其中A(x)是与水声传播模型和发送频率有关的函数变量，可表示为

其中k为水声传播模型的相关参数，k取1时为柱形传播模型，k取2时为球形传播模型，通常k取1.5代表实际水声传播模型。a与频率f有关，可由能量吸收系数∂(f)获得其中能量吸收系数为

2.3 节点运动模型

为了能够较为准确地模拟水中节点的运动状态，建立节点运动模型时需要考虑如下情况：首先由于节点被抛锚固定在水底，节点的深度可以通过调整锚链的长度来改变。这种状态下的节点受到水流的影响和锚链的牵引力作用，会在一定的范围内做受限的运动[17]。图2给出了水下环境中的节点受力图。

图2 节点受力图

如图2所示，对节点受力分析，节点受到水流的横向冲击力F、浮力f及锚链对节点的拉力T (忽略节点的自身重力)，这3种力构成了一组平衡力，并设锚链和垂直方向的最大夹角为β，其中tanβ =F/f 。本文不做流体力学相关研究，在实验仿真中做了定量处理，仅给出节点移动的最大偏移距离，在该偏移距离内节点做Random Waypoint运动[18]。

3 动态分层的分簇路由算法

3.1 问题描述

在网络分簇阶段，节点受水流的影响在一定范围内运动，节点与簇头的间距在不断地变化，且节点无法感知与簇头的间距。为了保证网络的可靠性，本文节点通信半径初始化为固定值。这样，在簇内成员节点通信半径都相同的情况下，不同簇形态具有相同的能耗nEtr, n为簇内成员节点的总数，Etr为成员节点与簇头节点通信的能耗，在不能改变成员节点能耗的情况下，如果能减少簇头节点的能耗，则减少网络的总能耗。然而如果始终选择距离sink节点较近的节点成为簇头，会导致这类节点能量消耗过大而提前死亡，形成能量空洞。本文引入了动态分层机制，每一轮数据采集周期网络分层都自动向下调整，动态分层避免了同一节点连续被选举为簇头节点，起到了平衡网络能耗的作用。图3和图4分别给出了网络簇头选取方法和动态分层机制的示意图。

3.2 节点通信半径

对式(2)求导处理后，当在最小接收功率为3 mW、消息发送频率为10 kHz的条件下，节点的通信距离小于540 m时，节点传输功耗增长率小于1，表明在540 m范围内，随着通信距离的增加，节点发送消息产生的能量增加得较缓慢。相反，当节点的通信距离大于540 m时，随着通信距离的增加，节点发送消息产生的能量增加得较快。因而，DLCR算法要求节点的通信半径不能超过540 m过多。

为了适应节点的移动性，保证网络的可靠性，本文算法要求节点的通信功率可调。在簇头选举阶段，被选为簇头的节点以通信半径R广播自己成为簇头的消息，成员节点选择加入最佳的簇。数据采集阶段，成员节点以通信半径R+2r就能保证消息能够发送给簇头节点，r为节点受水流影响的最大偏移距离。最后簇头节点采用多跳的方式将消息发送给sink节点。

3.3 动态分层机制

图3 簇头选取方法

图4 动态分层图

网络分层的目的是为了简化网络模型，分层又能够保证簇头节点更加均匀地分布在整个传感器网络中，有助于均衡网络的能耗。分层后的网络只有同一层内的节点进行成簇。DLCR算法的核心思想是为了让簇头节点更靠近网络的上方，即与sink节点的距离较近。因而为了保证分层边界上的节点能与正上方最远的簇头节点通信，要求簇头选举阶段节点的通信半径R不小于层间距Δd。DLCR算法取分层间距等于通信半径R。

DLCR算法要求在每一轮数据采集周期内，簇头节点位于网络层内的偏上方，每一轮数据采集周期结束后，相较于普通节点，簇头节点消耗较大的能耗。为了避免同一节点多次被选为簇头节点，又能保证所有的簇头都在层内的偏上方，因而要引入动态的网络分层。动态网络分层的核心思想为：每一轮数据采集结束之后，各网络分层都向下移动一个固定距离值d，这样经过R/d 轮后，网络又重新恢复到最初的分层状态。

假设网络被均匀的划分为多层，节点x的当前深度信息为hx,D为网络的最大深度。网络在初始阶段被划分为D/R层，之后由于动态分层机制，网络将被划分为D/R+1层，经过R/d轮后，网络又重新恢复到初始的分层网络。设网络分层编号从0开始采用自上而下递增的方式进行编号，网络初始阶段第0层是不存在的，网络编号从1开始。之后网络的第0层距离sink节点在通信范围内，所以要求第0层节点不成簇，直接将数据发送给sink节点。节点第1轮所在初始层次为L1x：

由于每一轮簇头都尽可能地位于层内偏上方，为了平衡网络的能耗，每一轮分簇结束之后，在上一轮分层的基础之上，各网络分层都向下调整距离d，节点x第n轮的所在网络层次为Lnx：

式(6)给出动态分层的计算方式，只要每一轮数据采集周期结束之后，节点都要重新计算自己所在的网络层次。这样，在动态分层机制的基础上，只要能给出合适的簇头选举机制，始终选择距离sink节点较近的节点作为簇头节点，就能够保证网络的能量均衡，延缓网络能量空洞的出现，有效地延长网络的寿命。

3.4 簇头的选举和路由

簇头选举的核心思想是建立在动态分层的基础之上，其中第0层距离sink节点较近，节点直接将消息发送给sink，而其他层内的簇头节点尽可能位于层内的偏上方。针对在同一深度的节点，簇头的选取还需要综合节点能耗因数，始终考虑能量较大的节点担任簇头节点。本算法要求簇头选举的代价函数依赖于深度因子和能量因子两个参数。由于簇头的选举在同一层内进行，深度因子H(x)的计算方式为当前节点位于层内的相对高度与层间距的比值，式(7)给出了深度因子的求解：

由于每一轮数据采集周期内，普通节点都要以通信半径R+2r将数据发送给簇头节点，因而节点每一轮都将至少消耗Etr(l,R+2r)的能量(若为担任簇头节点，则能耗较高)。第n轮时，节点最大剩余能量约为Eo−(n−1)×Etr(l,R+2r )，能量因子E(x)的计算方式为节点剩余能量与节点的最大剩余能量的比值，式(8)给出了能量因子的求解：

其中Eo为节点初始能量，Ex为节点剩余能量，n表示轮数，r为节点最大偏移距离。

在簇头选举过程中，簇头首先要计算深度因子H(x)，能量因子E(x)和簇头代价值T(x)；首先需要给出一个深度阈值Ho，只有深度因子H(x)大于深度阈值Ho的节点被选为候选簇头。要找出深度阈值Ho就得找出哪些节点被选为候选簇头。

根据动态分层机制，在新一轮簇头选举时，网络分层进行相应的调整，各层向下调整的距离为d 。其理论为：位于层内偏上方深度区间d内的那段区域的节点被当选为候选簇头。式(10)给出阈值Ho的计算方式：

簇头选举的代价函数T(x)可由深度因子与能量因子之积求得，式(9)给出了簇头选举的代价函数的求解：

簇头选举和路由的过程如下：

第1步 候选簇头选举阶段，每个节点计算自身的深度因子H(x)和成为簇头的权值T(x), H(x)若大于阈值Ho，则该节点成为候选簇头。

第2步 簇头选举阶段，每个候选簇头进行消息广播。候选簇头i收到来自其他候选簇头节点的广播消息后，将其他的簇头节点加入自己的竞选队列Qi。

第3步 如果竞选队列Qi内所有来自其他节点的簇头权值T(x)均小于自身权值，则宣布自己成为簇头，并广播自己成为簇头的消息。其他候选簇头节点收到该消息后就加入该簇，并广播退选消息，其他节点收到退选消息后，将该节点从自己的竞选队列里去除。然后重复第3步过程，经过多次迭代，直到所有簇头均被选举出来。

第4步 分簇阶段中，非簇头节点存在以下3种情况：

(1)第1类节点收到多个本层簇头节点的广播消息或同时收到若干来自下层簇头的广播消息，选择本层簇头节点中权值T(x)较大的加入；

(2)第2类节点只收到来自下层簇头节点的广播消息，随机选择簇头权值T(x)最大的簇头加入；

(3)第3类节点未收到任何簇头广播信息，自己成为一个簇头，并广播簇头消息，其他类似节点通过这种方式自主选择分簇。

第5步 数据收集阶段：簇头将成员节点的消息融合成一条消息后，通过多跳的方式发送给sink节点。

(1)每个簇头以半径R广播一个路由发现消息，选择来自上层的T(x)阈值最大的簇头节点作为下一跳节点；

(2)若通信范围内没找到簇头节点，则在通信半径增大R后，再广播路由发现消息，直到发现下一跳簇头节点。重复次，直到确定下一跳节点。否则直接将消息发送给sink节点。

4 实验与仿真

在matlab平台下，本文与采用相同网络模型的DUCS, DEAR算法以及LEACH经典成簇算法进行了对比实验。实验结果证明，DLCR算法的稳定性以及在控制网络负载均衡、延长网络寿命等方面都要优于DUCS, DEAR, LEACH等算法。表1给出了默认的仿真参数。

4.1 动态网络分层对网络寿命的影响

在500×500×600网络环境下部署1000个节点，节点初始能量为0.5 J，通信半径R为200 m，动态分层调整间距d分别取R, R/2, R/3, R/4, R/5；从图5可以看出在不同动态分层机制下，当调整值d为R时，即没有引入网络动态分层机制时，网络第1个节点的死亡时间最早，而且随着网络的运行，节点的死亡速率最高；当引入分层机制后，节点的死亡时间得到延迟，并且当调整间距为R/2时，网络最晚出现死亡节点。从图6可以看出，当调整值d取R值时，即在没有引入网络动态分层机制的情况下，网络的总能耗要高于引入动态分层机制后的网络。而引入动态分层机制后，网络总能耗均得到良好的控制，表明动态分层有助于提高网络能量的利用率。由于第1个节点死亡时，网络将开始变得不稳定，因而结合图5和图6的实验结果，当分层调整值d取R/2时，网络的性能较优。

表1 仿真参数

在保持网络节点密度、通信半径不变的情况下，通过改变网络的规模，进行多次实验后从图7可以看出最优网络寿命下的分层调整值d并没有随着网络的规模而改变。保持网络规模不变的情况下，通过改变节点的数量，进行多次实验后从图8可以看出当网络部署节点的增加严重影响了网络节点密度时，节点重复覆盖面积增大，此时分层调整间距减小更有利于均衡网络的能耗。

4.2 网络簇头的分布

在500×500×600网络环境下部署1000个节点，节点初始能量为1 J，通信半径为200 m。从图9可以看出相较于其他算法，DLCR簇头分布更接近正态分布，说明该算法下的簇头分布相对集中，算法的稳定性和稳健性较好。

4.3 不同算法的网络性能对比

在500×500×600的网络环境下，随机部署1000个节点，节点初始能量为1 J，通信半径为200 m。从图10可以看出，采用随机分簇且没有合理簇间路由的LEACH算法其簇头节点能耗较大，最早出现死亡节点；DUCS算法根据节点剩余能量选举簇头，而DEAR算法考虑了簇内节点的平均能量，但当节点能量较低时，DUCS和DEAR算法都会退化成随机成簇算法；本文DLCR算法考虑节点的相对剩余能量和相对深度，是更优的分簇算法，同时动态分层均衡了网络能耗，进一步延长了网络寿命。对比图11可以看出采用了动态分层的DLCR算法，由于网络簇头更加均匀，且距离sink较近，因而其网络能量的衰减最为缓慢。

5 结论

图5 动态网络分层对节点存亡的影响

图6 动态网络分层对网络能量的影响

图7 最优网络寿命下网络规模对应的调整值

图8 最优网络寿命下网络密度对应的调整值

图9 簇头分布

图10 节点死亡时间对比

图11 网络剩余能量

本文提出了一种动态分层的水下传感器网络分簇路由算法，该算法通过减少簇头节点与sink节点的距离来减少簇头的通信能耗，并通过建立动态的分层机制来平衡网络的能耗，实验证明该算法具有较好的稳定性，能够有效地均衡网络能量、延长网络寿命。

[1] 郭忠文, 罗汉江, 洪峰, 等. 水下传感器网络的研究进展[J].计算机研究与发展, 2010, 47(3): 377-389.

Guo Zhong-wen, Luo Han-jiang, Hong Feng, et al.. Current progress and research issues in underwater sensor networks[J]. Journal of Computer of Computer Research and Development, 2010, 47(3): 377-389.

[2] 洪峰, 张玉亮, 杨博真, 等. 水下传感器网络时间同步技术综述[J]. 电子学报, 2013, 41(5): 960-965.

Hong Feng, Zhang Yu-liang, Yang Bo-zhen, et al.. Review on time synchronization techniques in underwater acoustic sensor networks[J]. Acta Electronica Sinica, 2013, 41(5): 960-965.

[3] 郭瑛, 张震. 大规模水下传感器网络时间同步研究[J]. 电子与信息学报, 2014, 36(6): 1498-1503.

Guo Ying and Zhang Zhen. Clock synchronization study for large scale underwater sensor networks[J]. Journal of Electronics & Information Technology, 2014, 36(6): 1498-1503.

[4] 金志刚, 苏毅珊, 刘自鑫, 等. 基于运动预测的水下传感器网络MAC协议[J]. 电子与信息学报, 2013, 35(3): 728-734.

Jin Zhi-gang, Su Yi-shan, Liu Zi-xin, et al.. Prediction based MAC for underwater wireless sensor networks[J]. Journal of Electronics & Information Technology, 2013, 35(3): 728-734.

[5] Yan H and Cui J H. DBR: depth-based routing for underwater sensor networks[C]. Proceedings of the 7th International IFIP-TC6 Networking Conference, Singapore, 2008: 72-86.

[6] Anupama K R, Sasidharan A, and Vadlamani S. A location-based clustering algorithm for data gathering in 3D underwater wireless sensor networks[C]. Proceedings of the 2008 International Symposium on Telecommunications, Tehran, Iran, 2008: 343-348.

[7] Pu W, Cheng L, and Jun Z. Distributed minimum-cost clustering protocol for underwater sensor networks (UWSNs) [C]. Proceedings of the IEEE International Conference on Communications, Glasgow, UK, 2007: 3510-3515.

[8] Liu L F. A deployment algorithm for underwater sensor networks in ocean environment[J]. Journal of Circuits, Systems and Computers, 2011, 20(6): 1051-1066.

[9] Gopi S, Kannan G, Chander D, et al.. PULRP: path unawarelayer routing protocol for underwater sensor networks[C]. Proceedings of the IEEE International Conference on Communications, Beijing, China, 2008: 3141-3145.

[10] Ayaz M, Abdullah A, and Low Tang Jung. Temporary cluster based routing for underwater wireless sensor networks[C]. Proceedings of the International Symposium in Information Technology, Kuala Lumpur, Malaysia, 2010: 1009-1014.

[11] Ali K and Hassanein H. Underwater wireless hybrid sensor network[C]. Proceedings of the IEEE Symposium on Computers and Communications, Marrakech, Marocko, 2008: 1166-1171.

[12] Domingo M C and Prior R. A distributed clustering scheme for underwater wireless sensor networks in personal, indoor and mobile radio communications[C]. Proceedings of the IEEE 18th International Symposium on PIMRC, Athens, Greece, 2007: 1-5.

[13] Domingo M C. A distributed energy-aware routing protocol for underwater wireless sensor networks[J]. Wireless Personal Communications, 2011, 57(4): 607-627.

[14] 卿利, 朱清新, 王明文. 异构传感器网络的分布式能量有效分簇算法[J]. 软件学报, 2006, 17(3): 481-489.

Qing Li, Zhu Qing-xin, and Wang Ming-wen. A distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[J]. Journal of Software, 2006, 17(3): 481-489.

[15] Sozer E M, Stojanovic M, and Proakis J G. Underwater acoustic networks[J]. IEEE Journal of Oceanic Engineering, 2000, 25(1): 72-83.

[16] 彭舰, 洪昌建, 刘唐, 等. 基于分层的水下传感器网络路由策略[J]. 通信学报, 2014, 35(6): 25-31.

Peng Jian, Hong Chang-jian, Liu Tang, et al.. Strategy of routing based on layered for underwater wireless sensor networks[J]. Journal on Communications, 2014, 35(6): 25-31.

[17] Guo Y and Liu Y T. Localization for anchor-free underwater sensor networks[J]. Computers and Electrical Engineering, 2013, 39(6): 1812-1821.

[18] 刘唐, 彭舰, 杨进. 异构延迟容忍移动传感器网络中基于转发概率的数据传输[J]. 软件学报, 2013, 24(2): 215-229.

Liu Tang, Peng Jian, and Yang Jin. Data delivery for heterogeneous delay tolerant mobile sensor networks based on forwarding probability[J]. Journal of Software, 2013, 24(2): 215-229.

洪昌建： 男，1988年生，硕士，助理工程师，研究方向为无线传感器网络.

吴伟杰： 男，1980年生，硕士，高级工程师，研究方向为计算机网络.

唐平鹏： 男，1985年生，博士，工程师，研究方向为计算机网络.

Dynamic Layered Clustering Routing Algorithm in Underwater Sensor Networks

Hong Chang-jian Wu Wei-jie Tang Ping-peng
(Wuhan Second Ship Design and Research Institute, Wuhan 430064, China)

To deal with the limitation that flat routing can hardly be accustomed to large scale Underwater Sensor Networks (USN), a new clustering routing algorithm Dynamic Layered Clustering Routing (DLCR) is proposed, which can be accustomed to larger scale networks. This algorithm divides the networks into several layers from top to bottom, and selects the nodes which have more remaining energy and shorter distance to sink as the cluster head nodes, thus, clusters' communication energy consumption are reduced. In order to avoid the same nodes being elected to be cluster head nodes continuously, a dynamic layered mechanism that the networks are divided into different layers in each circle of data gathering is proposed. The experiment shows that DLCR not only has a better stability, but also reduces the energy consumption and prolongs the lifetime of the whole networks.

Underwater Sensor Networks (USN); Dynamic layered mechanism; Clustering routing

TP393

： A

：1009-5896(2015)06-1291-07

10.11999/JEIT141182

2014-09-10 收到，2014-12-23改回

*通信作者：洪昌建 hongcj@yeah.net