能耗均衡与节能的自适应水下路由协议

赵德腾，王 敏，2+，刘 淳

(1.云南师范大学 信息学院，云南 昆明 650500；2.云南师范大学 民族教育信息化教育部重点实验室，云南 昆明 650500)

0 引 言

近些年，随着人类社会对海洋资源勘探和开发的兴趣越来越大，水下传感器网络(underwater sensor networks，UWSNs)作为一种新型的无线传感器网络，在诸多水下应用中发挥重要作用[1，2]。UWSNs是由大量传感器节点，包括普通节点和目的节点(又称sink节点)组成的无线自组网络，主要通过声波传输数据。相比于陆地环境，水下条件恶劣[3，4]，更换节点电池的难度很大[5，6]，均衡和降低节点能耗[7，8]以延长网络寿命[9]尤为重要。

为了降低网络能耗，Xie P等提出了VBF，该协议采用源节点到sink节点的路由管道限制可转发数据包的节点，有效减少了网络中的重复数据包，从而降低了网络能耗，但是提前预定的路由管道半径，不能很好地适应不同规模的网络。为了均衡节点能耗，Xiao X等提出了LE-VBF，通过感知相邻节点的能量信息，根据节点的剩余能量来决定是否参与传输，如果该节点的剩余能量超过其邻居节点的平均剩余能量，则转发数据包，否则，丢弃数据包，但是相邻节点间的频繁通信会产生较高的能耗和数据碰撞。Wei B等提出了ES-VBF，该协议按照节点剩余能量与原始能量的比值采用不同函数设置发包等待时间，比值较高的节点优先发包，以均衡节点能耗，但无法均衡采用同一函数设置发包等待时间的节点之间的能耗。为了降低能耗和提高投递率，文献[10]提出了依赖于环境大小、节点传输范围和节点总数的可变管道，根据网络密度按比例改变路由管道半径，从而在节点密集的网络中降低能耗，在节点稀疏的网络中提高投递率，但由于网络中的节点分布是不均匀的，可能无法达到较好的效果。Yu H等提出了AHH-VBF，通过逐跳改变路由管道的方向和半径，保证节点稀疏区域的传输可靠性，减少节点密集区域的重复数据包，但每一跳的计算量较大。ALRP[11]将节点通信范围内面向sink节点方向的区域作为候选转发区域，在候选转发区域内，越靠近sink节点的节点，被选为下一跳转发节点的可能性越大，ALRP不需要寻找最优管道半径，但是候选转发区域的大小固定，难以适应不同规模的网络。

为了增加协议的动态适应性，部分研究人员将强化学习(reinforcement learning，RL)应用到UWSNs[12-14]，利用Q学习算法，将网络中的状态与采取的行为构建成一张Q表来存储Q值，然后根据Q值来选取能够获得最大收益的动作，具有较强的适应性，但每次都需要更新和存储Q值，增加了复杂性，能耗较大[15]，这对计算能力和能量有限且难以更换电池的UWSNs来说是一个挑战。

为了进一步均衡和降低UWSNs的能耗，以延长网络寿命。本文提出能耗均衡与节能的自适应水下路由协议(energy consumption balanced and energy saving adaptive underwater routing protocol，ECBES)。首先，构建双区非均匀分层拓扑。其次，基于能耗均衡因子，利用拓扑和节点剩余能量计算出节点转发优先级，实现自适应转发节点选择。与此同时，利用策略迭代思想逐步确定最优候选转发区域。

1 网络模型

本文UWSNs由多个普通节点和单个sink节点组成。普通节点分为两种，一种固定在水底，另一种在监测区域中随机移动。普通节点具有唯一的ID号，可以感知自己的位置以及进行简单的信息处理。普通节点的计算能力、数据传输能力、原始能量大小完全相同。sink节点的能量看作无限，其位于水面，用来接收水下传来的数据包，并最终将数据包传递到陆地基站。sink节点配备了声学调制解调器和无线电调制解调器，声学链路用于水下通信，无线电链路用于地面通信。网络模型如图1所示。

图1 网络模型

2 ECBES的设计

2.1 问题描述

传统路由协议一般通过比较节点剩余能量的大小，选择高剩余能量的节点转发数据包，以此来均衡能耗，但是容易陷入局部最优，从而导致不同区域间节点的剩余能量相差较大。同时，节点的候选转发区域大小固定，难以适应不同规模的网络，若候选转发区域太大，不断运动的低优先级节点可能无法收到抑制发包的消息，从而产生大量的重复数据包，导致高能耗。

本文针对传统水下路由协议能耗不均衡和能量有限的问题，提出能耗均衡与节能的自适应水下路由协议ECBES。

2.2 数据包包头

ECBES的数据包包头包括数据包唯一标识(ID)、节点三维位置(position)、节点所处层次(layers)、节点剩余能量(residual energy)以及统计变量range(i)_count字段(仅存在于首轮数据包，在2.5.1节中具体介绍)。包头格式如图2所示。

图2 数据包包头

2.3 双区非均匀分层拓扑构建

为了从全局角度缓解能耗不均，减少部分节点因能量耗尽而提前死亡的情况，ECBES构建水下双区非均匀分层拓扑。图3是以sink节点为中心的拓扑纵向剖面图，图中的监测区域被纵向划分为主区和副区，水平方向上采用非均匀分层，其中主区用以sink节点为球心的若干球面进行划分，副区采用平行分层。

图3 拓扑纵向剖面

如图3所示，为避免数据转发集中于某些路径和区域，造成能耗不均，主区和副区节点采用不同的转发方向，主区节点优先朝sink节点方向转发，副区节点优先向副区的上层转发，并在接近水面时，改朝sink节点方向转发，以缓解纵向上的节点能耗不均。此外，靠近水面的层中参与转发的节点更易集中于sink节点附近，需要有更多节点参与数据转发，以缓解横向上的节点能耗不均，因此靠近水面的层，体积较大，则候选转发节点数多。同时考虑到主区和副区节点转发方向的特点，主区用以sink节点为球心的若干球面进行划分，副区采用平行分层。

2.4 基于能耗均衡因子的自适应转发节点选择

为了均衡网络能耗，ECBES从全局拓扑和节点剩余能量两方面计算节点转发优先级，并根据优先级和随机小数设置动态等待时间，以抑制低优先级节点转发数据包，并降低同等优先级节点的重复数据包。

2.4.1 节点转发优先级

ECBES的节点转发优先级取决于：①层次大小，使数据包往sink节点方向或较浅方向传输；②是否与上一跳节点同区，避免数据转发集中于某些路径和区域；③剩余能量大小，均衡局部节点间的能耗。在同一剩余能量情况下，所属分层的层次越小，转发优先级越高，在同一分层情况下，与上一跳节点同区的节点，转发优先级较高。

ECBES将节点通信范围内，面向sink节点的上半球区域作为节点的候选转发区域。如图4所示，节点A1和A2的候选转发区域为虚线半球区域，其被双区非均匀分层拓扑分割，其中的阿拉伯数字是不考虑节点剩余能量情况下，各区域节点的转发优先程度，数字越小，转发优先级越高。

图4 转发节点选择

计算出节点转发优先级Pselect之后，与一个随机数RN∈[β，1) 进行比较，β的最小取值为0，Pselect大则成为候选转发节点，否则丢弃。因此Pselect越大，成为转发节点的可能性越大，其值考虑能耗均衡，在ECBES中通过能耗均衡因子α1和α2来综合设置。Pselect的计算如式(1)所示

(1)

其中，α1考虑全局拓扑层面的能耗均衡，其值如式(2)所示，α2考虑局部节点间的能耗均衡，其值如式(3)所示。α1的取值考虑节点所属分层层次、与上一跳节点是否同区，α2的取值考虑上下两跳节点的剩余能量

(2)

其中，layer为候选转发节点所属的分层层次，layerlast为上一跳节点所属的分层层次，K为非负实数。特别地，当处于主区一层的节点收到来自副区二层节点传来的数据包时α1为1.0

(3)

其中，E为候选转发节点的剩余能量，Elast为上一跳节点的剩余能量，λ1和λ2为候选转发节点与上一跳节点剩余能量之比的阈值，剩余能量之比大于λ1的节点在局部区域相对于其它节点能量充足，小于λ2的节点则能量不足，放弃转发资格。

2.4.2 动态等待时间

为了抑制低优先级节点转发数据包，并降低同等优先级节点的重复数据包，ECBES根据节点转发优先级和随机小数设置动态等待时间T。优先级Pselect越大，动态等待时间T越小，同等优先级的节点通过随机小数Trn来区分。在动态等待时间T内，如果收到其它节点传来相同的数据包，则取消等待时间并丢弃该包，否则，时间T到期发包。动态等待时间T的计算如式(4)所示

(4)

此外，每一个转发节点建立已发送列表，将发送过的数据包ID写入已发送列表，每次收到数据包后进行对比，如果已发送过此包，则直接丢弃，以防止节点循环转发此包。

2.5 基于策略迭代思想的候选转发区域优化

候选转发区域的大小与网络规模以及网络中节点的分布情况有关，需要根据网络动态设置。ECBES基于策略迭代思想，通过有限次迭代确定最优候选转发区域。

ECBES将节点通信范围内，面向sink节点的上半球区域作为节点原始候选转发区域，如图5中平面S以上的半球区域，平面S称为原始候选转发平面。为了能够尽快找到最优候选转发区域，加速收敛，ECBES通过分析首轮数据包传递期间节点候选转发区域各分区域中节点参与转发数据包的比例，确定次优候选转发区域，并将其作为初始策略，通过多次迭代，确定最优候选转发区域，以较低的实现复杂度减少不同网络规模中重复转发的数据包，降低网络的整体能耗。

图5 节点转发模型

本节共有两个算法，分别为：次优候选转发区域确定算法和最优候选转发区域确定算法。表1对本节算法所用到的部分参数进行介绍。

表1 算法参数

2.5.1 次优候选转发区域确定

在原始候选转发区域的基础上，ECBES进一步确定次优候选转发区域。对于首轮数据包的传递，节点的转发优先级设定参考文献[11]，即在候选转发区域内越靠近sink节点的节点转发优先级越高(仅限首轮，其余轮次采用2.4.1节所计算的优先级)。

首轮数据包传递期间，range(i)_count字段用来统计原始候选转发区域各个分区域(range(i)区域)中的节点参与转发数据包的次数。range(i)区域划分如图5所示，每个range(i)代表一个区域范围，候选转发节点收到数据包后根据距离上一跳节点原始候选转发平面的距离d_initial确定自己处于哪一区域，并对数据包包头中对应的range(i)_count字段值加1。

首轮数据包传递结束后，sink节点利用收到的数据包中的range(i)_count信息，计算各个range(i)区域中节点参与转发数据包的比例，并与阈值TH∈[0，1) 进行比较，最终确定次优候选转发区域。range(i)区域节点转发比例的计算如式(5)所示

(5)

从range(n)_ratio开始向下对每个区域转发比例逐一进行累加，当累加值大于阈值TH时，参与累加的区域即为次优候选转发区域，如图5所示，以平面S’为底面的球冠区域即为次优候选转发区域。确定次优候选转发区域后，sink节点将此信息广播到网络中。算法1以图5为示例，给出次优候选转发区域确定的主要步骤。

算法1：次优候选转发区域确定

输入：(原始候选转发区域)

输出：(次优候选转发区域)

范围：(首轮数据包传递期间)

(1)/*候选转发节点收到数据包后的处理方案*/

(2)若候选转发节点C收到A发来的数据包, 如图5所示, 则计算节点C到节点A的原始候选转发平面的距离

(3)根据计算出的d_initialCA确定节点C所属的区域range(i)之后, 将数据包包头中对应的range(i)_count字段值加1

(4)/*sink节点收到数据包后的处理方案*/

(5)IF (condition1)

(6) 读取包中的range(i)_count信息并存储

(7)ELSE

(8) 丢弃数据包

(9)IF (condition2)

(10) 计算各range(i)区域中节点参与转发数据包的比例

(11) IF (range(n)_ratio>TH)

(12) range(n)为次优候选转发区域

(13) ELSE IF (range(n)_ratio+range(n-1)_ratio>TH)

(14) range(n)+range(n-1)为次优候选转发区域

(15) ……

(16) ELSE IF(range(n)_ratio+…+range(2)_ratio>TH)

(17) range(n)+…+range(2)为次优候选转发区域

(18) ELSE

(19)原始候选转发区域为次优候选转发区域

2.5.2 最优候选转发区域确定

策略迭代思想是通过不断迭代获得最优策略的一种思想。为了加快收敛，ECBES将上一节中确定的次优候选转发区域作为初始策略。

算法2：最优候选转发区域确定

输入：(次优候选转发区域)

输出：(最优候选转发区域)

范围：(第2轮及以后数据包传递期间)

(1) /*节点的候选转发区域设置方案*/

(3) /*sink节点收到数据包后的处理方案*/

(4)IF (condition1)

(5)pk_count本轮++

(6)ELSE

(7) 丢弃数据包

(8)IF (condition2)

(9) IF (pk_count本轮!

(10)pk_count上轮=pk_count本轮

(11)pk_count本轮=0

(12) ELSE

(13) 结束, 上一轮候选转发区域确定为最优候选转发区域

3 实验结果与分析

3.1 仿真设置

本文通过仿真软件OPNET 14.5对VBF、ES-VBF、ALRP和ECBES的节点死亡率、数据包投递率、网络能耗以及端到端时延进行实验分析。仿真物理层采用水声信道。发包节点固定在水底，每轮发包间隔15 s，总共发包15轮。移动节点分布在240m×240m×120m的监测区域内，随水流进行0～3 m/s的随机水平移动。主要实验参数见表2。

表2 仿真参数

本实验设置主区为一个底面半径60 m，高120 m的圆柱区域，监测区域其余部分为副区，主区分为4层，分别用半径60 m，90 m和120 m的同心球隔开。副区分层为以主区同心球分层与主副区边界交点为界限的平行分层，拓扑纵向剖面图如图3所示。候选转发区域分区数n=4， 分别为range(1)、range(2)、range(3)、range(4)，每个区域厚度为10 m，迭代步长H为2 m，最多迭代次数为4。

3.2 性能评估

在本小节中，将对UWSNs路由协议VBF、ES-VBF、ALRP和ECBES进行性能评估。评估指标包括节点死亡率、数据包投递率、网络能耗以及端到端时延。

3.2.1 节点死亡率

图6为VBF、ES-VBF、ALRP和ECBES仿真完成后的节点死亡率随节点个数增加的变化曲线。结果表明，ECBES在不同节点个数下均没有出现节点死亡。当节点个数低于500时，VBF、ES-VBF、ALRP的节点死亡率为0，当节点个数增加到500时，出现节点死亡，且随着节点个数的增加，节点死亡率也在增加。原因是节点的广播特性导致随着节点个数的增加，节点间通信的机会和次数也大大增加，从而导致部分节点因能量耗尽而死亡。

图6 不同节点个数下的节点死亡率

VBF和ES-VBF均采用源节点到sink节点的路由管道限制可转发数据包的节点，这导致管道内外节点能耗不均，管道内的节点能耗较大。虽然ES-VBF按照节点剩余能量与原始能量的比值采用两种不同函数设置发包等待时间，剩余能量超过原始能量60%的节点优先发包，但是无法均衡采用同一函数设置发包等待时间的节点间的能耗，而且剩余能量很低的节点虽然转发优先级低，但在动态网络中，可能无法抑制其转发数据包。ALRP中的节点根据其当前位置决定转发方向，始终面向sink节点方向传递数据包，导致网络各区域间能耗不均。

ECBES在不同节点个数下的节点死亡率均为0。主要原因是ECBES在全局利用双区非均匀分层拓扑均衡能耗，在局部节点间通过上下两跳节点剩余能量的大小关系均衡能耗，且为了缓解动态网络中可能无法抑制低能量节点转发数据包的情况，设定当候选转发节点与上一跳节点剩余能量的比值低于0.3时，主动放弃数据包的转发。

3.2.2 数据包投递率

图7为VBF、ES-VBF、ALRP和ECBES的数据包投递率随节点个数增加的变化曲线。结果表明，当节点个数增加时，4个协议的数据包投递率逐渐增加。从图7可知，节点个数在700～800时，ECBES的数据包投递率明显高于其它3个协议，主要是因为ECBES在数据包传递期间没有节点死亡，因此，所有节点都处于正常工作状态。

图7 不同节点个数下的数据包投递率

3.2.3 网络能耗

图8为VBF、ES-VBF、ALRP和ECBES的网络能耗随节点个数增加的变化曲线。结果表明，当节点个数增加时，4个协议的网络能耗逐渐增加。原因是节点的广播特性导致随着节点个数的增加，节点间通信的机会和次数也大大增加，从而导致能耗增加。

图8 不同节点个数下的网络能耗

VBF和ES-VBF均采用冗余传输，即允许有限多个节点转发数据包，这会产生不必要的能耗。ALRP虽然采用单个节点转发数据包，但每一跳节点的候选转发区域太大，占到了节点通信范围的一半，在动态网络中难以抑制部分重复数据包的转发，从而造成较高的能耗。

从图8可知，ECBES在不同节点个数下的网络能耗基本都低于其它3个协议。由图7与图8对比可知，ECBES在投递率基本不低于其它3个协议的同时，能耗大大降低。主要原因是ECBES利用策略迭代思想确定最优候选转发区域，保证投递率的同时减少了不同网络规模中重复数据包的转发，降低了网络的整体能耗。

3.2.4 端到端时延

图9是不同节点个数下4个协议的端到端时延。VBF、ES-VBF、ALRP和ECBES在节点个数为100～300时，sink节点未收到数据包，因此没有端到端时延数据。从图中可知，ECBES在4个协议中保持了不错的端到端时延。主要是因为ECBES将网络划分为双区非均匀分层拓扑，使得各个节点的负载相对均衡，从而降低了排队的可能性以及根据不同的情况对发包等待时间进行动态调整，去除了多余的等待时间。

图9 不同节点个数下的端到端时延

4 结束语

本文针对水下传感器网络(UWSNs)中节点能耗不均衡和能量有限的问题，提出了能耗均衡与节能的自适应水下路由协议ECBES。在双区非均匀分层拓扑的基础上，基于能耗均衡因子计算出节点转发优先级，实现自适应转发节点选择，均衡网络能耗。同时，利用策略迭代思想逐步确定最优候选转发区域，减少了重复数据包的转发，降低了网络的整体能耗。

本文基于OPNET分析对比了4个协议在不同节点数量下的节点死亡率、数据包投递率、网络能耗以及端到端时延。仿真结果表明，ECBES相比于VBF、ES-VBF和ALRP，在不同节点数量下，节点死亡率均最低，在保证数据包投递率的同时，能耗最少。

在未来的研究中，将尝试多sink节点的架构来进一步扩展和研究本文所提出的方案，以扩展使用场景。