0 引言

随着水声通讯技术的发展, 水下无线传感器网络(Underwater wireless sensor networks, UWSNs)逐步成为认识和了解海洋的有效工具, 帮助人们更充分地获取海洋信息, 以提高对海洋环境监控和预测的能力^[1-3].与陆地传感器网络相比, 水下传感器网络采用水声通信, 其信号衰减快, 通信时延高, 且节点能量有限, 充能更加困难^[4].因此, 延长网络生命周期, 降低通信时延一直是水下传感器网络的重点研究方面.

在无线传感器网络拓扑结构中, 分簇网络拓扑具有节省能量、均衡能耗以及降低时延的优点, 但依然存在着“能量热区”问题, 距基站较近区域以及节点密度较大区域的簇首节点传输负载重、能量消耗过快, 出现网络能耗不均的问题.而且, 若簇首选择过程未考虑实际监测区域的节点密度以及簇间传输负载和簇内传输负载分配不合理, 则也易造成网络能耗不均问题.此外, 水下传感器网络受环境和规模影响, 基站集中分簇困难, 水声传输速度慢, 时延过高.

针对上述问题, 本文提出一种基于等级划分的水下传感器网络非均匀分簇算法(Uneven clustering algorithm for UWSNs based on gradation, UCUBG).该算法仅利用节点通信范围内的邻居节点信息, 自适应地选择簇首, 划分簇首等级, 建立簇间传输路由, 构建一种节点能耗均衡、通信时延低的分簇网络.仿真结果表明, 所提出的算法不仅能均衡能耗, 延长网络寿命, 而且能够有效降低网络通信时延.

1 相关工作 1.1 无线传感器网络分簇算法研究

在传统无线传感器网络中, 网络分簇算法的相关研究已有很多. Heinzelman等^[5]提出了著名的LEACH算法, 该算法依据节点被选次数以轮寻机制竞选簇首, 并通过簇首将簇内成员数据单跳转发给基站, 虽然在一定程度上减少了节点能量消耗, 延长了网络生命周期, 但簇首分布不均, 易造成簇内成员过多且离基站较远的簇首过早死亡. LEACH-C算法^[6]和DEEC算法^[7]是LEACH算法的改进算法, 这两种算法在簇首选择过程中引入节点剩余能量, 增加剩余能量较高的节点成为簇首的概率, 从而进一步延长了网络生命周期, 但均未考虑节点密度对网络生命周期的影响, 且簇首都是单跳传输, 扩展性差, 不适用于大型无线传感器网络.为解决距基站距离较近簇首节点负载过重的“能量热区”问题, 李成法等^[8]提出了EEUC算法, 该算法是一种基于节点到基站距离的非均匀分簇算法, 算法中距离基站越近的簇规模越小, 能够改善距离基站较近的簇首转发任务过重产生的“能量热区”问题, 但未考虑节点分布不均和剩余能量对簇首能量消耗的影响, 导致出现簇间负载相近而簇内成员数目差别过大和剩余能量过小的节点易选为簇首等问题. EEDC算法^[9]在簇首选择过程中增加了与基站距离较近且剩余能量较多节点成为簇首的概率, 均衡了簇首传输能耗, 延长了网络寿命, 但同样未考虑节点分布不均对簇首能耗的影响, 簇首均衡能耗效果不佳.

1.2 水下传感器网络分簇算法研究

水下传感器网络分簇算法研究主要分为两个方面:

1) 先对网络进行分簇, 再利用水下机器人(Autonomous underwater vehicle, AUV)辅助收集数据.基于上述思想, 文献[10]提出一种基于网格的分簇算法EBECRP, 首先对网络进行网格化, 在每个网格中选择簇首; 然后利用AUV作为移动基站收集簇首数据, 缩短数据传输距离, 降低网络能耗, 但AUV成本较高, 且无法保证数据传输到水面基站的时效性.

2) 与传统无线传感器网络相似, 依靠网络节点向基站传输数据.如文献[11]提出了一种基于位置和能量信息的垂直分簇路由算法, 该算法在利用节点位置和能量信息构建多跳垂直簇、降低网络时延的同时, 通过反馈信息对网络空洞进行监测, 提高网络数据包投送率.文献[12]提出了一种综合能量有效性和传输时延的分簇算法EGRCs, 该算法首先将网络分为若干立方体, 然后基于节点位置和剩余能量选择簇首, 最后将下一跳节点到基站距离、剩余能量和传输时延共同作为簇首节点选择的依据, 以达到延长网络生命周期的同时降低通信时延的目的.但该算法的时延与立方体数量有关, 立方体数目增多将增加通信时延, 并且依然未考虑节点分布不均对网络生命周期的影响.

2 问题描述及网络模型 2.1 问题描述

无线传感器网络非均匀分簇算法在均衡网络能耗方面的研究已经非常丰富, 但在分簇过程中, 上述文献均未综合考虑节点分布不均以及簇首间转发任务不均对网络寿命的影响.而且, 相对于集中式分簇算法, 虽然分布式分簇算法无需频繁地与基站进行通信, 开销较小, 但是簇均衡负载效果较差^[13].因此, 本文对节点非均匀分布水下场景中存在的簇首能耗不均问题进行具体分析.

首先, 将簇首节点CH_i的能耗EC_i简化为以下两部分:转发簇间数据的能耗EC₁^d_i、处理和转发簇内数据的能耗EC₂ⁱ, 有

(1)

(2)

其中: d_i为簇首节点CH_i到基站的距离, n_i为簇首节点CH_i的簇内成员个数, E_inⁱ为簇首节点处理和转发一个簇成员数据的平均能耗.

利用簇首节点能耗的变异系数EC_C.V分析网络均衡能耗效果.由变异系数特性可知, 该方法可以有效降低能耗平均值不同对均衡能耗效果的影响.簇首节点能耗的变异系数表示为

(3)

(4)

(5)

(6)

其中: EC_average为簇首节点平均能耗, EC_SD为簇首节点能耗标准差, EC_all为全部簇首节点总能耗, N为整个网络的簇首节点个数.将式(1) ~ (6)整理, 得到

(7)

由式(7)可知, EC_C.V越小, 簇首节点转发簇间数据的能耗EC₁^d与处理和转发簇内数据的能耗n_iE_in之和与簇首平均能耗差值越小, 网络均衡能耗效果越好.但是, 水下无线传感器网络节点多为轮船或飞机进行随机投放, 节点分布不均, 易出现EC₁^d相近的不同簇内成员节点个数差别较大, 导致簇首能耗不均, 部分节点过早死亡等问题.而且, 在相同或相近水深范围内, 如果普通节点通过常用簇首选择标准(如簇首的剩余能量、节点到簇首距离、簇首到基站距离等)加入不同的簇首, 则会出现深度相似区域簇内成员个数相近, 而簇间转发任务不同的情况.转发任务过重的簇首节点能耗过快, 会出现节点过早死亡的问题.

2.2 网络模型

本文以静态三维水下传感器网络作为网络模型(见图 1), 并对该网络模型作如下假设:

1) 所有节点随机分布在一个三维立方体中;

2) 每个节点有唯一ID, 传输范围为球形且其他方面均是同构的;

3) 基站位于水面, 网络运行过程不考虑基站能量损耗;

4) 在通信半径内, 节点可以自由调整发射功率, 以节省能量消耗;

5) 链路具有对称性, 节点可以根据接收信号强弱判断双方之间的距离.

2.3 能耗模型

文献[14]给出了以声波为媒介的水下网络数据通信能耗模型.节点发射长度为l的数据包所消耗的能量E_t(d)可表示为

(8)

其中: λ_t为发射能耗系数; d为数据包需要传输的距离; A(d)为数据包在水下传输距离为d时的能量衰减, 有

(9)

(10)

(11)

a(f)为吸收系数, η为能量扩散因子, 一般情况下取η=1.5, f为载波频率.

节点接收长度为l的数据包消耗的能量为

(12)

其中λ_r为接收能耗系数.

2.4 时延模型

水下传感器网络的节点采用水声通信方式, 水声传播速度较慢, 因此在水下传感器网络中, 节点间进行数据传输所产生端到端的时延主要由以下3部分组成^[15]:

1) 发送和接收时间(Transmission and reception time, TR):节点发送和接收整个数据包时花费的时间;

2) 传播时间(Propagation time, Pr):数据包在水中传播过程中花费的时间;

3) 字符对齐时间(Byte alignment time, BA):节点对接收到的数据进行字节对齐时花费的时间.

节点间通信时延T_ij表示为

(13)

其中: TR_i为节点i进行数据发送和接收时间, Pr_ij为数据包在节点i与节点j之间传输的传播时间, BA_i为节点i的字符对齐时间.

3 UCUBG算法 3.1 算法思想

UCUBG算法运行过程采用拓扑重构机制, 每次重构分为簇的建立、簇间通信和数据传输3个过程.在簇的建立阶段, 节点自组织竞选成为簇首, 未成为簇首的节点适当地加入各个簇, 成为该簇的簇内节点; 每个簇中均有一个簇首节点, 且簇节点只与本簇的簇首节点进行通信.在簇间通信阶段, 簇首节点彼此通信, 组成骨干网络, 并对比不同路径的传输代价, 选择最佳通信路径.在数据传输阶段, 簇内成员节点直接传给簇首节点, 簇首间根据已选择的下一跳簇首节点进行传输.每隔一个周期, 拓扑进行重构, 直到网络达到最大生命周期.

3.2 簇的建立

簇的建立阶段分为选择候选簇首、确定簇首、划分簇首等级和普通节点入簇4个环节.

1) 选择候选簇首.

簇首节点需要由通信范围内剩余能量较多的节点担任, 而且需要依据局部区域节点密度自适应地调节簇首分布个数, 保证节点密度较大的区域存在较多的簇首节点.因此, 在候选簇首选择环节, 节点首先在通信范围内广播自身剩余能量、节点坐标等信息, 然后根据自身通信范围内的节点密度和节点剩余能量, 通过下式计算出簇首竞选阈值T(i):

(14)

其中: E_av(i)为节点i在其通信半径中所有节点剩余能量的平均值; n_i和n_max分别为节点i在其通信半径中的实际节点数和最大节点数; a₁、b₁和c₁为调节参数, 且a₁+b₁+c₁=1.每个节点随机产生一个0 ~ 1之间的数, 比较该随机数和T(i), 若其值小于T(i), 则节点被选为候选簇首.由式(14)可知, 节点剩余能量越多以及节点密度越大, 其阈值T(i)越大, 成为候选簇首的概率也越大.

2) 确定簇首.

在采用多跳传输的分簇网络中, 离基站越近的簇首节点能耗越大, 因此簇首到基站距离越近, 簇首竞争半径需越小, 减小簇规模, 使其剩余更多能量用于转发其他簇首节点的数据.在水下传感器网络中, 节点通常被随机布置; 并且由于洋流等作用, 常出现节点分布不均的情况, 单一地将距离基站的远近作为竞争半径的依据过于理想, 簇首节点能量因节点分布不均造成消耗差别大, 出现部分节点过早死亡等问题, 无法适应节点能量有限且充能困难的实际水下环境.针对该问题, 本文引入综合考虑节点到基站距离和节点密度的簇首竞争半径, 以减小距离基站近的簇规模和高节点密度区域的簇规模.竞争半径表示为

(15)

其中: d_{i_ds}为节点i到基站的距离; n_max为节点通信半径内最大节点数; R_c为最大竞争半径; d_min为到基站的最近距离; d_max为监测范围内到基站最远的距离; a₂和b₂为调节系数, 且a₂+b₂=1.

计算竞争半径后, 候选簇首节点根据下式产生的竞争时间t发出竞争消息:

(16)

其中: T_t为预先设定的最大竞争时间, E_r(i)为节点i的剩余能量.候选簇首的t越小, 越早进行广播.式(16)产生的竞争时间能够提高局部剩余能量多的候选簇首节点成为真正簇首节点的概率.

3) 划分簇首等级.

分簇算法常对网络进行等级划分, 如网格模型^{[12, 16]}、圆环模型^[17]和非均匀圆弧模型^[18].上述模型均根据节点到基站的欧氏距离进行等级划分, 并要求簇首节点与下一跳节点存在等级差的前提下, 进行多跳路由的选择, 以便数据更快传输到基站, 降低能耗和减小通信时延.但是, 未考虑相同等级簇首节点转发负载不均衡, 负载大的簇首节点会出现过早死亡的问题.

针对上述问题, 提出一种新型等级划分策略.该策略以簇首节点通信范围内水平下方α^o范围内簇首节点的存在情况进行等级划分.若该簇首水平下方α^o范围的S区域内无其他簇首节点, 则将该节点设置为1级簇头节点, 如图 2左图所示.若S区域内存在其他簇头节点, 则将节点A设为其S范围内其他簇头节点最高等级加1级的簇头节点, 如图 2右图所示.

为均衡簇首能耗, 由式(7)可知, 当EC₁^d较小时, 需增加处理和转发簇内数据的能耗, 增加簇内成员个数.在入簇过程中, 等级划分可以帮助普通节点预测簇首簇间传输负载, 增加簇间传输负载较小的簇内成员节点个数, 提高簇首均衡能耗效果; 同时, 在多跳路由选择过程中, 保持簇首节点需要与下一跳节点存在等级差这一措施, 降低深度相近范围内簇首节点相互转发数据的概率, 提高能量利用率.为便于理解等级划分过程, 给出其伪代码如下所示.

算法1  簇首等级划分算法.

Input: Cluster head set S_ch(i=1, 2, …, n) and Grade set Grade_ch(i=1, 2, …, n);

1) Initializes: Grade_ch=∅

2) while n＜length(S_ch) do

3) if t＜t_i then

4) Cluster head S_chⁱ receives Grade_MSG(j) from S_ch^j;

5) if S_ch^j satisfies the condition of S_chⁱ grade division then

6) S_ch^j ∈ Grade_chⁱ_set

7) end if

8) end if

9) if t=t_i, Grade_chⁱ_set ≠ ∅ then

10) Grade_chⁱ=max(Grade_chⁱ_set)+1, and cluster head S_chⁱ broadcasts Grade_MSG(i) which contains S_chⁱ location and grade at the maximum communication radius;

11) else if t=t_i, Grade_chⁱ_set=∅ then

12) Grade_chⁱ=1, and broadcasts Grade_MSG(i) at the maximum communication radius;

13) end if

14) n=n+1;

15) end while

Output: Grade_ch(i=1, 2…, n).

4) 普通节点入簇.

权值公式ω₁(i)综合了到簇首距离、簇首到基站距离、簇首剩余能量和簇首等级, 普通节点据此选取簇首, 权值公式如下:

(17)

其中: d_{i_chj}为节点i到簇首ch_j距离; d为节点通信半径; E_chj和E₀分别为簇首ch_j剩余能量和初始能量; G_chj为簇首ch_j的等级; a₃, b₃, c₃和d₃为调节系数, 且a₃+b₃+c₃+d₃=1.由式(17)可得, 簇首的ω₁(i)越小, 成员节点选择该簇首的概率越大, 而且在其他条件大致相同的情况下, 节点将选择等级较低的簇头节点, 减轻簇间负载较重的簇首节点的簇内传输能耗.

3.3 簇间路由选择

簇间通信直接利用节点通信范围内的信息选择下一跳, 易造成局部传输代价最小而整体传输代价过大的局部最优.并且水下环境复杂, 基站很难快速了解所有节点的当前信息, 无法集中控制网络通信, 如果通过节点间彼此通信去了解整个网络的信息则会浪费大量能耗和时间.因此, 本文将簇首等级和贪心算法相结合, 令高等级簇首节点向其通信范围内的低等级簇首节点发送其到基站的能耗代价和时延代价总和, 使低等级簇首节点依据自身到下一跳以及下一跳到基站的传输代价之和选择最优路径, 以达到在均衡网络能耗的同时减少能耗、降低时延的目的.具体措施如下:

1) 与基站直接通信的簇首节点ch_i利用综合考虑能耗和时延的代价函数ω₂(ch_{i_bs})计算自身到基站的代价, 并将其传输代价和位置信息存入Cost_MSG(ch_{i_bs})信息中, 发送给通信范围内低等级的簇首节点.

2) 接收到信息Cost_MSG(ch_{i_bs})的低等级节点ch_j利用代价函数ω₂(ch_{j_bs})分别计算自身到通信范围内高等级节点的传输代价, 并将与高等级簇首节点到基站的通信传输价叠加, 选择通信代价最小的高等级节点作为该簇首节点的下一跳, 并将包含自身到基站的传输代价和位置的信息Cost_MSG(ch_{j_bs})发送给通信范围内更低等级的簇首节点.

3) 以此类推, 直至所有1级簇首节点选路结束.通信代价函数ω₂表示为

(18)

其中: ω₂(ch_{i_bs})和ω₂(ch_{i_j})分别为簇首ch_i到基站以及簇首ch_i到ch_j的通信代价; G为节点等级; ω₂(ch_{i_j})表示为

(19)

d_{chi_chj}为簇首ch_i与ch_j间距离, T_{chi_chj}为簇首ch_i到ch_j的通信时延, T_max为最大通信时延, a₄和b₄为调节系数, 且a₄+b₄=1.

4 算法仿真

为验证和评价UCUBG算法的有效性, 在Matlab环境中将UCUBG算法分别与LEACH、EEUC和EGRCs算法进行对比.仿真过程假设以“轮”的形式进行, 每一轮分别由网络成簇过程和网络数据传输过程构成, 其中网络成簇过程主要完成簇的构成以及节点转发路径的建立; 网络数据传输过程包括网络中节点采集环境信息, 以及对其他节点数据的接收和转发.节点初始化能量E为最大能量E₀的50 % ~ 100 %, 使仿真更加符合节点能量各不相同的实际环境.其余仿真参数在表 1中列出.

为便于读者更好地理解仿真过程, 给出以下定义.

定义1(网络生命周期T_life)  从网络开始运行到存活节点数低于50 %总节点数为止的时间称为该网络的生命周期, 有

(20)

其中: T_begin为网络开始运行的时刻, T_50%为死亡节点数占总节点数50 %的轮数.

定义2(有效数据传输量L_all)  在网络生命周期内, 节点向基站发送的数据包为有效数据量, 有

(21)

其中: k为轮数, n_alive为在网络生命周期内存活的节点个数, l为每个节点每轮向基站发送数据量.

定义3(最远传输时延)  网络中最远节点发出的数据包到达基站的时延称为最远传输时延.

4.1 均衡能耗效果仿真分析

为分析算法均衡能耗的效果, 仿真对比UCUBG算法在不同等级角度α下的网络生命周期以及运行不同算法后网络中首个死亡节点出现的轮数、网络节点平均剩余能量和网络生命周期.

为对比簇首等级划分角度α对均衡能耗的影响, 在不同节点数目下, 对UCUBG算法的网络生命周期随α变化进行仿真, 结果如图 3所示.由图 3可见:网络生命周期随节点数目变化而变化的同时, 也随着α的不同发生变化, 其中α=30°的网络生命周期略长于其他角度, 且网络生命周期在α=30^o两侧成梯度下降趋势; 当簇首等级划分角度为30°时, UCUBG算法能够均衡能耗, 延长网络寿命效果优于0°、15°、45°和60°.为综合考虑网络寿命和通信时延, 在以下仿真中, 取α=45°, 使其在延长网络寿命效果相差不大的情况下, 进一步降低相近深度簇首节点之间转发信息的概率, 降低网络时延, 提高网络整体性能.

图 4为节点数目分别为50、75、100、125、150、175和200时, LEACH、EEUC、EGRCs和UCUBG算法出现网络首个死亡节点的轮数.在不同节点数目下, UCUBG算法出现首个死亡节点的轮数均大于其他3种算法, 因此UCUBG算法能够有效延长网络整体的运行时间.

如果网络中节点平均能耗过大, 则网络能耗均衡效果即使很好也容易出现节点过早死亡、网络寿命较短的问题.因此, 对比LEACH、EEUC、EGRCs和UCUBG算法运行前20轮中每一轮节点的平均剩余能量.如图 5所示, UCUBG算法每一轮的平均节点剩余能量均高于其他3种算法, UCUBG算法运行过程中网络能量消耗更低, 更利于延长网络寿命.

图 6为LEACH、EEUC、EGRCs和UCUBG算法中存活节点个数随轮数增多的变化情况.由图 6可见, LEACH算法最早出现节点死亡, 且最后一个节点死亡晚于其他3种算法, 这说明LEACH算法具有均衡网络能耗的效果差、造成节点能耗差异大、部分节点过早死亡的问题.而UCUBG算法出现第1个节点死亡的轮数分别是LEACH算法的218 %、EEUC算法的150 %、EGRCs算法的117 %, 并且最后一个节点的死亡时间早于其他算法, 表明该算法均衡能耗的效果优于其他3种算法.

图 7给出了LEACH、EEUC、EGRCs和UCUBG四种算法在网络生命周期内出现不同百分比节点死亡的轮数.由图 7可见, UCUBG算法节点死亡的时间明显晚于其他3种算法, 并且变化平缓, 即UCUBG算法节点死亡出现于短时间内, 表明均衡网络能耗和延长网络生命周期的效果更好.

4.2 有效数据传输量仿真分析

图 8为LEACH、EEUC、EGRCs和UCUBG算法基站收到节点数据包的个数.由图 8可见, 在节点未出现死亡前, LEACH、EEUC、EGRCs和UCUBG节点发送到基站的数据包数相同, 但由于UCUBG均衡能耗效果优于其他3种算法, 节点死亡轮数晚于其他3种算法, 网络生命周期长于其他3种算法, UCUBG基站接收的数据包数大于LEACH、EEUC和EGRCs.

4.3 数据传输时延仿真分析

网络数据传输时延是水下传感器网络需要重点考虑的因素, 因此本节进行了通信时延仿真. 图 9表示不同节点数目下LEACH、EEUC、EGRCs和UCUBG通信时延.由于LEACH算法的簇首节点与基站直接进行数据传输, 通信时延低于采用多跳簇间传输的EEUC、EGRCs和UCUBG算法.而簇间采用多跳方式向基站传输数据时, 由于UCUBG在簇间传输代价中同时考虑了通信能耗和通信时延, 从而使其通信时延小于EEUC、EGRCs算法, 可以有效降低网络通信时延.

5 结论

本文提出了一种均衡水下传感器网络能耗的非均匀分簇算法UCUBG.该算法在分簇过程中不仅改善了由于节点密度不均造成的簇首节点能耗不均问题, 而且设计了一种依据簇首相对于基站位置以及簇首分布的新型簇首等级划分策略, 使节点入簇更加合理, 进一步优化了簇首传输负载不均问题.同时, 将该簇首等级划分策略应用到簇间传输过程中, 结合贪心算法构造了一种综合考虑传输能耗和时延的路由传输方法, 降低了水下传感器网络数据传输延时.仿真结果表明, UCUBG能够有效均衡能耗, 降低网络传输时延.