水下传感网络多目标优化机会路由

王 鑫，徐海涛，蒋 华，覃 琴

(1.桂林电子科技大学 计算机与信息安全学院，广西 桂林 541004； 2.桂林电子科技大学北海校区 海洋信息工程学院，广西 北海 541000)

0 引 言

水下传感网络(underwater sensor networks，UWSNs)的发展促进了各种应用的发展，包括海洋环境监测、海洋地质勘探、水下资源开发和灾难预警等[1,2]。由于水域环境特殊，水下声通信存在着巨大挑战。例如能见度跟踪能力差、声音的传播速度低，以及海水的高动态物理特性，如温度、压力和盐度使其具有多样性。因此，通过使用具有低带宽声学调制解调器的多个传感器来监视这种挑战性环境变得至关重要。由于海洋面积广阔并且占地球表面的四分之三，所以必须部署多个传感器来监测待测区域。目前，水下传感器网络的主要挑战是在整个网络生命周期内保持节点之间的能量水平平衡，有效的路由协议成为完成水域监测的必要条件。

近年来，一些科研机构和研究者提出了许多新的路由协议，文献[3]提到了一种基于深度的DBR(depth-based routing)路由协议，节点通过深度信息进行数据转发。文献[4]提出了多层路由协议MRP(multi-layer routing protocol)，通过超级节点解决了空间信息的需求，并通过不同的层转发数据包。文献[5]提到了DBR协议改进的路由协议EEDBR，EEDBR考虑了节点能量和深度信息来选择下一跳节点，将感测到的数据转发到浅深度并具有高能量的节点。文献[6]提出一种基于轮换转发优先级的机会路由RFP-OR(rotating forwarding priority-based OR)。通过考虑数据包传递率、能耗和水压值估计节点的适度值，以此来进行候选转发节点的选择，并设置各节点的转发优先级。节点转发优先级的轮换通过更新节点的适度值来实现。

为进一步均衡水下传感网络能耗，延长网络生命周期，本文提出一种多目标优化机会路由MOO-BA。仿真结果表明，与DBR和EEDBR相比，本协议在能量高效性、均衡性等方面均具有明显优势，有效地延长网络的使用寿命。

1 系统模型

1.1 网络架构

MOO-BA采用多Sink网络架构如图1所示，该架构由3个部分组成，即控制中心、汇聚节点和水下传感器，其中水下传感器包括锚定节点、中继节点。

图1 网络模型

锚定节点固定在海洋底部，只感知并收集数据。中继节点部署在不同的深度，不仅可以发送数据包，还可以转发接收到的数据包。控制中心放置在船舶或海滩上，并从汇聚节点接收数据包。

汇聚节点部署在水面上，配备无线电和声学调制解调器以及无限的能量。声学调制解调器用于水下传感器节点接收数据分组，而无线电波用于将收集的数据转发到岸上控制中心。

1.2 能量传播模型

水声信号传播模型采用Stojanovic[7]提出的水下信道设计模型。基于扩散损耗计算信号的总衰减，并考虑thorps模型用于信号吸收损耗。在给定频率f下，吸收损失α(f) 可以表示为

(1)

其中，α(f) 以dB/km为单位，f以kHz为单位。

通过式(1)吸收损失值α可以推导为α=10α(f)/10。总衰减量A(d,f) 可以通过组合吸收损耗和扩散损耗来获得，如式(2)所示，距离d上的声道衰减可表示为

10log(A(d,f))=k×10logd+d×10log(α(f))

(2)

其中，第一项是扩散损失，第二项是吸收损失，k代表扩散系数，它定义了传播的几何形状(即k=1是浅水区域的圆柱形扩展，k=2是深水区域球形扩展，k=1.5是实际的扩展)，α(f) 代表吸收系数。水下环境噪声[8]可表示为

N(f)=Nt(f)+Ns(f)+Nw(f)+Nth(f)

(3)

其中，Nt(f)、Ns(f)、Nw(f) 和Nth(f) 分别表示由湍流、运输、波浪和热能引起的噪声。对于频率为f的声学信号和水下环境中d的传播距离，接收机的信噪比可表示为

SNR(f,d)=P(f)-A(d,f)-N(f)+DI

(4)

其中，P(f) 是发送方的频率为f的发送功率。DI是指向性指数，是接收器方向灵敏度的函数或用于传感器节点引导其水听器以避免不必要噪声。在接收器处，如果SNR(f,d) 等于或大于DT(检测阈值)，则接收器可以正确地解码所接收的信号。

2 MOO-BA路由

2.1 问题描述

传统路由通过贪婪策略选择一跳邻居范围内的最佳转发节点，很容易陷入局部最优解决方案。同时，满足深度小于当前节点条件的节点都会参与到数据包的转发工作中，这会导致多个节点同时转发相同数据包，造成数据冗余和能耗。

本文针对传统协议能耗不均衡问题，提出一种多目标优化机会路由来均衡网络能耗。

2.2 MOO-BA中的分组结构和消息流

MOO-BA的路由分组类型和消息格式如图2和图3所示。任何数据包的数据包标题包含两个字段：发件人ID、数据包序列号。发件人ID是水下传感器节点的标识符；分组序列号是由水下传感器节点分配给分组的唯一序列号。发件人ID与数据包序列号相结合有助于避免路由过程中的重复。路由信息包括能量和深度。能量是信标节点的剩余能量；深度是当前转发器的深度信息，在信标发送阶段每个节点自动更新。

图2 数据包格式

图3 邀请请求接受消息格式

路由信息包括5种类型的请求，即邀请请求、邀请请求接受、邀请请求确认、邀请请求拒绝、选择另一个最佳转发器。邀请请求IR(invitation request)是发送给符合条件的一跳邻居的初始信标消息。在接收到邀请请求后，在动态寿命估计(DLE)之后发出邀请请求接受IRA(invitation request acceptance)。邀请请求确认IRC(invitation request confirmation)是数据传输之前的最终消息。邀请请求拒绝IRR(invitation request rejection)是在请求超过DLE时发出的拒绝消息。选择另一个最佳转发器SAOF(selected another optimal forwarder)是发送到所有节点的重定向消息。

2.3 初始信标

在初始信标期间，水下传感器节点在位于传输范围(Ni)之间验证身份，同时维护一张 [ENS(Ni)] 表，[ENS(Ni)] 将符合条件的邻居节点插入到接收器中，其深度小于已发起请求的节点的接收器。其中深度测量为必要条件，深度信息由深度传感器探测获得。

当传感器向上转发数据包时，就可以在符合条件的邻居节点选择列表 [ENS(Ni)] 中选择最佳转发器进行数据转发，防止传感器节点向所有邻居节点广播邀请请求。初始信标过程如下：①较深处传感器节点将邀请请求(IR)广播到 [ENS(Ni)] 中；②列出的浅深度节点。

2.4 动态寿命估计(DLE)

假设同质传感器由S={s1，s2，…sn} 表示，并且每个传感器节点都能够基于基本信息(如能量、深度)从该组转发器中选择最佳转发器。如式(5)所示，只有当节点的剩余能量高于εng(τth) 时，节点才能将自身声明为最优转发器。εng(τth) 定义为在距离t上发送k比特消息所需的最小能量

(5)

在通信的初始阶段，每个节点的剩余能量将近似等于初始能量。节点的剩余能量表示为

εng剩余=εng初始-εng消耗

(6)

每个节点消耗的能量表示为

εng消耗=εng传输+εng接收

(7)

网络中的所有节点能量估计DLE表示为

(8)

2.4.1 基于动态寿命估计的接受(DLEA)

DLEA根据DLE确定是否可以处理特定请求IR，并根据单个节点的DLE评估情况发出IRA或IRR令牌。接收到IR并发出IRA的浅深度节点充当父节点，而通过发送IRC确认IRA的深度节点充当子节点。网络中所有节点都维护两个名为LOA(list of acceptances)和LOC(list of confirmations)的表，LOA表包含父节点发出的IRA，LOC表包含子节点发出的IRC。当接收到IR时，父节点基于DLE来确定该请求是否在父节点的容量范围内。如式(9)所示，通过将LOAm、LOCm进行计数相加，如果当前请求的和值小于特定节点的DLEm，则发出IRA令牌，并在LOAm中添加一个条目。否则发出IRR令牌

(9)

其中，LOAm为接受请求条目列表，LOCm为确认请求条目列表，DLEm为特定节点的动态寿命估计。

2.4.2 基于动态寿命估计的确认(DLEC)

DLEC是用来确定是否可以确认收到的IRA。在此阶段，子节点有机会根据能量深度范围(EDR)信息确认最佳父节点之一。IRA由父节点在浅层发布。在接收到IRA令牌之后收到信息的子节点确认浅深度处的最佳转发器节点。轮询基于表中该节点维护的EDR信息。如果一个子节点收到一个或一个以上的IRA令牌，就有机会成为上层朝向接收器的最佳节点

Max{EDR={Em，Dm};m=1,2…n}

(10)

其中，Em和Dm是LOAm中从接收器到节点的能量和深度差异。

一旦深层节点通过基于式(10)中的条件发出IRC，则将此条目添加到在LOCm中，同时此节点向最先发送IRA请求的浅层节点发送通知消息SAOF(selected another optimal forwarder)。收到SAOF消息的浅层节点从LOAm中删除接受条目并更新DLEm。

2.5 初始路径

通过连接子节点和父节点，从源到目的地建立路径进行数据传输。在初始阶段，较高深度的节点n发出IRC到浅层节点m，将已启动传输的节点n添加到路径中，直到m等于sink。

2.6 标准蝙蝠算法

由Xin-She Yang开发的一种新的元启发式搜索算法称为蝙蝠算法[9]。通过模拟蝙蝠的回声定位能力，实现了群优化问题的求解。

fi=fmin+(fmax-fmin)β

(11)

(12)

(13)

其中，β∈[0,1] 是服从均匀分布的随机向量，x*是当前全局最佳位置(解)。

通过比较n个蝙蝠找到的最优解，每个蝙蝠开始时会被随机分配一个服从均匀分布 [fmin,fmax] 的频率。对于局部搜索部分，一旦从当前最佳解中选择了一个解，则使用随机游走对每个蝙蝠产生一个新解

xnew=xold+δA(t)

(14)

从实现的角度来看，最好能够提供一个缩放参数来控制步长。因此，可以将这个方程改写为

xnew=xold+σδtA(t)

(15)

其中，δt服从高斯正态分布N(0,1)，σ是缩放因子。响度Ai和脉冲发射率ri也随着迭代的进行而相应地更新。更新公式为

(16)

(17)

其中，α和γ是常数。对于任何0<α<1和γ>0，有

(18)

2.7 改进BA的路径优化

2.7.1 引入优化因子[9]

由于经典蝙蝠算法在进行迭代优化时会陷入局部优化性，因此引入优化因子λ来对MOO-BA算法的频率进行优化，以此来达到全局搜索和局部搜索的平衡。

将式(11)变更为式(19)

fi=(fmin+(fmax-fmin)β)λ

(19)

(20)

式中：t为当前迭代次数，由式(20)可以看出，λ的大小随着t的增长而减小。在迭代初期时，t值较小，λ值较大，因此蝙蝠发出的脉冲频率较高，加大了全局搜索的力度；而在迭代后期，随着t值的增大λ值变小，脉冲频率较低，加强了局部搜索的能力。

2.7.2 算法步骤

BA优化路径的具体过程如下：

步骤1 基于DLE初始化蝙蝠种群Xi和Vi(i=1,2,…,n) 初始化频率fi，脉冲发射率ri，响度Ai和最大迭代次数Nmax；

步骤3 根据式(11)～式(13)，对网络中的蝙蝠的速度和位置进行更新；

步骤4 生成随机数R1，假如R1大于ri时,从最佳解中选择一个BB(解)，围绕BB产生一个LBB(局部解)；

步骤5 生成随机数R2，假如R2小于Ai同时f(xi)

步骤6 经过一段时间运行，对新的蝙蝠群体进行评估判定,把网络中所有的蝙蝠适应度值按照从大到小顺序排列，找到最小值以及对应的位置，就是当前最优解和最优值；

步骤7 重复执行步骤2～步骤5，直到满足设定的最优解条件或达到最大迭代次数；

步骤8 输出全局最优值和最优解。

具体流程如图4所示。

图4 MOO-BA协议数据转发流程

通过上述步骤蝙蝠算法将蝙蝠行为捕获到适应度函数中。目标是建立具有最小延迟和最大输送比的优化路径。通过DLE改变Xi和Vi，在从源到目的地的初始填充期间填充机会路径。适应度函数 (fφ) 具有归一化的多目标权重，传递比mo1和延迟mo2由式(21)获得

fφ=Wmo1+Wmo2

(21)

其中，Wmo1=1-mo1，Wmo2=mo2。

针对最初填充的路径计算并且排名基于权重的适应度函数。具有最小适应度的路径被命名为最佳蝙蝠BB，如式(22)所示

最佳蝙蝠(BB)=min[fφ(pi)]
BB=P，P∈pi

(22)

其中，pi是最初填充的路径，P是最初填充的路径中的BA路径。

通过基于BB随机改变具有最佳个体来进一步获得LBB，如果LBB的适应度小于BB，则随机飞行后，将LBB的适应度更新为BB，蝙蝠BB被记录为最佳蝙蝠。最后选择与已获得的最佳蝙蝠相对应的路径进行数据传输。

3 实验结果与分析

在本节中，将提出的路由协议MOO-BA的性能与UWSNs中的现有路由协议DBR和EEDBR进行比较。

3.1 仿真环境

利用MATLABR2012b建立仿真平台。考虑200 m×200 m×200 m区域。蝙蝠算法参数设置：fmax=1，fmin=0，α=0.9，γ=0.9。种群个数设为30、最大迭代次数Nmax为100、最大惯性系数ωmax=1.2和最小惯性系数ωmin=0.1。传感器节点个数N在50～400变化，用不同组(即50、100、150等直到400)节点重复30次实验。具体的仿真参数见表1。

表1 仿真参数

3.2 结果与分析

3.2.1 网络生命周期

图5展示了不同算法的网络周期对比曲线，MOO-BA协议的网络生命周期明显高于EEDBR和DBR协议，在不同的节点下，比EEDBR高约500 s，比DBR高约800 s。原因是MOO-BA选择高剩余能量和靠近接收器的深度的节点进行数据转发。同时，蝙蝠算法参考最佳路径随机改变最佳转发器来动态优化初始填充的路径，防止同一节点因频繁转发数据耗尽能量，达到能耗均衡的目的，提高了网络生命周期。

图5 网络生命周期对比曲线

3.2.2 端到端延迟

图6展示了MOO-BA与DBR、EEDBR的端到端延迟变化曲线。如图6所示，随着时间的增加，MOO-BA的延迟明显低于其它两种协议，因为MOO-BA不计算保持时间，可以避免数据包碰撞。同时，蝙蝠算法通过参考最佳蝙蝠的适应性随机替换最佳节点来优化建立的路径，数据以机会路径转发到接收器，降低了延迟。而在DBR中，数据包从源推送到接收器时跳数增加，保持时间依次增加，这会导致端到端延迟增加。与DBR相比，EEDBR尽管消除了冗余，但分配优先级的保持时间会随着时间的增加而增加，延迟会越来越大。

图6 端到端延迟对比曲线

3.2.3 数据包传输量

图7显示了所有协议的数据包传输对比曲线。在DBR中，任何路径丢失的数据包都不能到达接收器，因为没有恢复机制。而EEDBR的数据包可以从不同路由到达接收器，所以EEDBR数据包传输量要比DBR好。而MOO-BA数据包传输量高于其它两种协议的原因是初始信标通过ENS(Ni)避免了不必要的节点参与进来，降低了无效数据包的传输。此外蝙蝠算法动态识别全局最佳路径，提高了有效数据包传输量。

图7 数据包传输对比曲线

4 结束语

本文针对水下传感网络能耗均衡的问题，提出了水下传感网络多目标优化机会路由MOO-BA。当节点需要转发数据包时，MOO-BA协议利用DLE进行节点动态寿命估计，符合条件的节点发放DLEA令牌充当最佳转发器并将消息发布出去。接着由DLEC再次确认最佳转发器的消息。最后使用改进的蝙蝠算法动态优化最初填充的路由。蝙蝠算法找到最初填充的路径的适合度并选择最佳的传输路径，同时使用其它填充路径迭代最佳蝙蝠，直到全局收敛获得数据传输最佳的路径。仿真结果表明，MOO-BA协议能够有效地降低端到端延迟，提高有效数据包传输量，延长网络寿命。另外，未来的研究工作可以考虑两点：一是研究移动水下传感网络的增强路由;二是研究具有适当恢复机制的水下传感网络机制。