避免路由循环和空洞节点的水下传感器网络深度路由算法*

蔡文郁，张铭坤，张美燕

(1.杭州电子科技大学电子信息学院，浙江 杭州 310018；2.浙江水利水电学院电气工程学院，浙江 杭州 310018)

随着陆地自然资源逐渐枯竭，越来越多的科学研究和新能源探索逐渐转移到水下环境，这使得水下无线传感器网络(UWSN)受到了世界各国的广泛关注[1]。水下无线传感器网络可以广泛应用于军事防御系统、海岸线监视与保护、海底资源勘探、海洋环境监测和辅助导航等场合。由于水体环境的无线电信号衰减非常严重，而水声信号却可以传播到较远的距离，因此在水下环境中水声通信是目前的主要技术方式[2]。然而，水声通信存在着传播速度低、带宽有限、动态性高、能量有限和部署成本高等问题[3]，并且水下信道具有多径衰落、噪声、路径损耗和多普勒扩频等特性，导致较高的丢包率和数据包传输时延等问题[4-5]。此外，节点移动性也是水下无线传感网络中一个不可忽视的重要影响因素。水下节点的移动特性导致传统的无线路由协议无法用于水下无线传感网络[6]。因此，针对UWSN 的可靠数据路由技术仍然是一个巨大的挑战。

现有的水下无线传感网络路由方法可以分为两类:基于地理信息的路由协议[7-8]和无地理信息的路由协议[9-10]。基于地理信息的路由协议需要获取水下传感器节点的位置信息，条件较为苛刻，很难进行实用，因此无地理信息的路由协议是目前的主要研究方向。基于深度信息的路由协议(DBR)[9]根据邻居节点的深度来选择下一跳节点:假设每个水下节点都能获知其邻居节点的深度信息，并选取深度最小的邻居节点作为下一跳转发节点。但是DBR 没有考虑转发节点的剩余能量和节点连通性，容易导致节点能量消耗的不均衡，也容易陷入局部最优的路由循环。能量优化的深度路由协议(EEDBR)[10]根据网络节点的剩余能量和深度信息计算转发权重，并更新数据包的保持时间，有效降低了节点能量消耗和端到端传输延迟，但是EEDBR 协议还存在着负荷分配不均衡的问题。基于深度的多跳路由协议(DBMR)[11]采用多跳转发的方式，减少了数据包冗余传输以及通信信道的占用。能量均衡、高效、可靠的路由协议(EBER2)[12]通过结合考虑下一跳节点的能量和潜在转发节点的数量来均衡网络能耗，提高网络寿命。但是EBER2 协议只是单纯的贪婪转发策略，存在较高的传输延迟，并且通过高速的光纤链路实现与海面Sink 节点的通信，部署成本非常昂贵。基于转发区域划分的加权深度路由协议(WDFAD-DBR)[13]在DBR 的基础上还考虑了2-Hop邻居节点的深度值，减少了空洞节点发生的概率，提高了网络的可靠性和数据包投递率。但是，WDDAD-DBR 协议在计算数据包转发权重时并没有考虑剩余能量，导致节点能量消耗不均衡，从而降低了网络整体生存周期。增强空洞避免路由协议(E-VAR)[14]可以实现对空洞节点的标记，优先选择非空洞节点作为下一跳转发节点。E-VAR 协议可以避免部分空洞节点，但是还可能存在路由循环现象，导致数据包的冗余传输。

针对现有路由协议存在的问题，提出了一种避免路由循环和空洞节点的深度路由协议PE-VAR，对节点是否属于空洞节点进行自我标记，以循环路径中节点的邻居数、能量、深度等参数综合计算正向推进距离值和替换优先值，遴选出需要替代或者避开的节点，从而抑制出现循环路径时的冗余传输。相比较E-VAR 协议，PE-VAR 协议无需获取网络节点的三维坐标，增加了节点的替换优先值计算以及对路由路径循环的监测环节，有效解决数据传输过程中出现的循环路由情况，减少数据包的冗余传输，提升整个网络的生命周期。

1 系统模型与假设

1.1 UWSN 网络模型

水下无线传感网络是由随机分布在三维空间内的众多水下传感器节点和随机分布在水面上的Sink节点组成，假设每个水下节点都配置了水压传感器，因此可以获取节点自身所处的深度值。源节点采集周围环境的感知数据并利用水声通信模块发送，中继节点接收到后进行优化转发，最后将感知数据传输到海面Sink 节点。假设水下无线传感网络中水下节点的内部时钟都可以保持同步状态，并具有相同的初始能量E0，由于水面Sink 节点的电能不限，因此假设所有水下节点都能收到水面Sink 节点的HELLO 数据包。综上所述，本文研究的UWSN 模型如图1 所示。

图1 UWSN 网络模型

1.2 水声传播衰减模型

水声传播过程中主要有两方面的衰减:①扩散损失，声波在不断扩散过程中引起声强衰减；②吸收损失，由于介质粘滞、热传导以及其他弛豫过程导致的衰减[11]。水声传播衰减模型的表达式如下:

式中，d为传播距离，n在浅海中取值为1.5，a为吸收系数，单位为dB/km，计算方法如式(2)所示[12]:

式中，f为声波频率，单位为kHz。

1.3 节点移动模型

水下传感器网络一般应用于浅水区域，水流速度相对较慢，水下传感器的节点运动较为缓慢。文献[6]提出了一种基于欧拉方法的节点移动模型，如下式所示:

式中，Vx表示的是节点x轴方向的速度，Vy表示的是节点y轴方向的速度。k1，k2，k3和λ与潮汐、深度等水体环境相关，k4，k5是两个随机变量。本文传感器节点的移动模型采用了上述移动模型，参数取值与文献[6]一致:k1，k2是服从N(π，0.1π)分布的随机数；k3是服从N(2π，0.2π)分布的随机数；k4，k5是服从N(1，0.1)分布的随机数；λ是服从N(3，0.3)分布的随机数。

1.4 能量消耗模型

本文采用文献[13]中的节点能量消耗模型，忽略数据接收所需的能量，发送数据的能耗公式如下所示:

式中，m表示传输数据的长度，Eelec表示节点发送(接收)1 bit 数据所消耗的能量，εfs表示自由空间模型信号放大倍数，εamp表示多径衰减模型信号放大倍数，d0表示功率距离阈值，d为数据收发两端之间的距离。

2 PE-VAR 路由协议

DBR 协议[9]的主要思想是贪婪转发策略，即让发送节点选择所有其邻居节点中深度最小的节点作为最优的下一跳转发节点。但是，DBR 协议容易陷入局部最优，遇到空洞节点后，会使得数据包在两个或多个节点间循环传输。根据节点在水下网络中的位置不同，可以分为普通节点(拥有正向推进邻居节点，即存在邻居节点深度小于当前节点深度的情况)、孤立节点(没有邻居节点)、空洞节点(没有正向推进的邻居节点，即所有邻居节点深度都不小于当前节点深度)、死亡节点(能量耗尽没有数据转发能力的节点)。图2 表示了三维水下无线传感网络中典型的路由循环场景:节点Ni没有发现比当前节点具有更小深度的邻居节点，而且节点Ni也无法与Sink 节点直接单跳通信，因此Ni为空洞节点。而且，节点Nj选择的下一跳节点为Ni，之后的数据包传递将会再次重复原路由路径，出现了无谓的路由循环情况，数据包无法可靠、及时地发送到水面Sink 节点。

图2 空洞节点和路由循环案例

E-VAR 协议[14]会对空洞节点的标记，优先选择非空洞节点作为下一跳转发节点，虽然能在传输时避免途径部分空洞节点，但依然可能存在路由循环现象，导致数据包的冗余传输。为此，PE-VAR 协议增设了节点的替换优先值计算以及对路由路径循环的监测环节，有效地解决了E-VAR 协议存在的问题。

针对以上路由循环和空洞节点问题，PE-VAR协议的主要思想如下:当水下节点启动或者定时器触发时，每个节点执行自我标记流程，完成后将自身信息广播给其邻居节点；然后，水下节点进行数据包的转发，若检测到当前路由路径中出现路由循环，则触发路由循环处理机制，更换转发节点；最终，避免路由循环陷阱，实现数据包的有效转发。PE-VAR协议主要分为以下三个阶段:自我标识定义、选择转发节点、避免路由循环。

2.1 自我标识定义

当节点启动开始工作或者达到预设的定时时间，启动自我标识过程:传感器节点Ni和Sink 节点都会广播HELLO 数据包，用来告知其邻居节点自身的信息，HELLO 数据包含如下信息:HELLO 标签、发送节点ID、剩余能量Ei、发送节点深度信息Hi、发送时间戳。网络中所有节点收到HELLO 数据包后通过统计计算，获取节点Ni的邻居节点集Gi、邻居节点集的长度｜Gi｜。节点Nj∈Gi(j＝1，2，…，｜Gi｜)收到HELLO 数据包后回复REPLY 数据包，包含以下字段信息:REPLY 标签、发送节点ID、剩余能量Ej、发送节点空洞标记Fj(若节点无正向推进邻居节点，则值为1，反之为0)、发送时间戳和邻居节点集信息，邻居节点集Gj数据包含如下信息:邻居节点ID、邻居节点剩余能量、邻居节点深度数据。水下传感器节点根据收发HELLO 数据包的时间戳差值，依据水声通信速率计算出与邻居节点间的欧氏距离。

节点Ni的自我标识流程如图3 所示:初始化时Ni的空洞标识为0，邻居节点集Gi为空。根据HELLO 包中的时间戳与自身内部时钟插值，来计算节点Ni与Sink 节点之间的欧式距离Dis，当Dis小于最大传输范围Rmax时，节点Ni与Sink 节点直接单跳通信；否则，节点Ni更新其邻居节点集Gi，并保存邻居节点Nj到离其最近Sink 的欧氏距离Djs。若Dis小于其所有邻居中最小的Djs，则表示节点Ni为空洞节点，并进行标记，即Fi＝1，否则Ni为正常节点，保持Fi＝0。

图3 节点Ni 的自我标识机制

2.2 选择转发节点

PE-VAR 协议的数据包转发策略如图4 所示，节点根据数据转发策略选择优化的下一跳节点。如图4 所示，数据发送节点Ni遍历邻居表Gi，若邻居表为空，则当前节点为孤立节点，丢弃数据包，等待下一次节点自我标识过程；若邻居表不为空，搜索邻居表中是否包含Sink 节点，若包含则直接将数据包传输给Sink 节点，否则对邻居节点集进行正向推进距离值计算，如果存在普通节点，则优先考虑邻居节点集中的正常节点，其次才考虑空洞节点。计算邻居节点的正向推进距离值Adv(即发送节点Ni离其最近Sink 节点的欧式距离Dis与其邻居节点Nj到其最近Sink 节点的欧式距离Djs之差)，如下式所示:

图4 数据包转发策略

如果邻居节点Nj为空洞节点(Fj＝1)，则要避免其被选为下一跳转发节点。由于(Dis-Djs)∈(0，2×Rmax]，若邻居节点Nj为空洞节点则要将其Dis与Djs的差值再减去2 倍最大传输半径Rmax，则可确保其被选择的概率低于所有非空洞邻居节点被选择的概率。最终选择Adv 值最大的邻居节点作为下一跳转发节点。

2.3 避免路由循环机制

当数据传输中出现循环路径时，PE-VAR 协议设计了一种路由循环避免机制。多跳传输的数据包中按序记录了转发节点的ID，如果下一跳转发节点ID 在当前路由路径中出现过，则可判断出现路由循环。节点Ni的替换优先级值Pi定义如下:

式中，｜Gi｜表示节点Ni邻居节点集的长度，Hi表示节点Ni的深度，表示节点Ni的邻居节点集中第k个节点的深度，表示当前节点Ni与其邻居节点Nk的欧氏距离，δ表示的系数，Rmax表示节点最大传输半径，Ei表示节点Ni的剩余能量，E0表示节点的初始能量。

替换优先级既考虑了当前节点与其所有邻居节点欧氏距离，又考虑了剩余能量率因素。而且，本文对替换优先级的影响因素采用了线性归一化处理，综合权衡了距离值与剩余能量率等因素。归一化后欧氏距离的差值越大，说明选择该下一跳节点能够传输更远，推进数据包的正向传输。归一化后的剩余能量率越小，则尽量不选择其为转发节点，防止该节点过早死亡，影响下一轮次的数据包传递。

如果检测发现了数据传输路由循环，PE-VAR协议根据路由循环中各节点的替换优先级值来选择合适的下一跳节点。如图5 所示，Ni根据邻居表中各邻居节点的Adv 值选择预转发节点Nj，发送节点遍历当前路径列表Rcur，若Nj未在Rcur中出现过，则直接确定下一跳节点为Nj；如果Nj已在Rcur中出现过，则截取记录当前循环路径。循环路径Sc截取方式:先找到重复节点Nj在Rcur中的位置，将该位置作为截取路径的起始位置，然后依次向后遍历Rcur直至尾部，并将所遍历到的节点按序存入循环路径Sc中。

图5 循环路径处理流程

综上所述，Pi值越大表示节点Ni具有更优的邻居节点可供选择。为了避免路由循环问题，在替换优先级最大节点的邻居节点中，将其当前的最优候选转发节点存入避选节点集中，以避免冗余循环传输。循环避免的示例如图6(a)所示:路由循环由3、4、20、6、7、8 节点组成，假设7 号节点的优先级最大，因此7 号节点的预选转发节点8 号节点将存入避选节点集中，避免其被选为下一跳节点。当数据包再次传输到7号节点时，选择其邻居节点中Adv 值最大的12 号节点作为下一跳转发节点，如图6(b)所示。因此，转发路径就不会按照原先的路径继续重复传输，避免了无谓的路由循环。

图6 路由循环处理

3 仿真结果

本文采用MATLAB R2020b 仿真平台对本文所研究的PE-VAR 算法进行性能验证，与现有的DBR、E-VAR 算法在数据包投递成功率(Packet Delivery Success Rate，SR)、数据包投递时延(Packet Delivery Delay，PD)、节点死亡率(Node Dead Rate，DR)、能量消耗(Energy Consumption，EC)等方面进行对比。DBR、E-VAR、PE-VAR 三种路由方式采用的网络仿真环境以及参数相同，主要参数如表1 所示。

表1 仿真参数

为了提高仿真结果的可靠性，每种仿真场景重复20 次实验，每次实验300 轮。每一轮仿真结束后，依照上文的水下节点运动模型改变传感器节点的位置。每次实验的数据源节点从当前网络中未死亡的节点中随机选择，最后取数据平均值作为最终结果。网络仿真场景如图7 所示，节点移动路径如图8 所示。

图7 UWSN 仿真模型

图8 水下节点移动路径

在相同的USNs 络模型和起始节点情况下，PE-VAR、DBR、E-VAR 三种算法获取的路径对比如图9 所示。在相同的仿真网络环境下，三种路由方法均以节点12 作为源节点进行数据包发送递，DBR方法在节点79 和节点45 之间出现双节点路由循环，导致一个节点死亡，另一节点没有邻居节点进行数据传递，最终路由失败；E-VAR 方法，出现节点79、11、3 之间的多节点循环，导致一个节点能量先耗尽，导致路由方向向下，最后失败于节点85 和节点57 造成的双节点循环；PE-VAR 避免了上述的路由循环问题，根据替换优先级，对造成这种情况影响较大的节点避免作为下一跳节点，最终成功将数据包传输给Sink 节点。

图9 路径对比结果

图10 和图11 比较了DBR、E-VAR、PE-VAR 三种路由在节点静态和节点动态两种仿真环境下性能对比。无论是节点静态还是节点动态情况，本文提出的PE-VAR 路由协议在四项性能指标上，在节点个数为100～300 时，均优于DBR 和E-VAR 协议，当节点数为300～400 时，由于节点密度过大，使得该区域网络负载过大，在迭代一定次数后节点死亡数量大，导致三种路由在节点死亡率与网络能耗性能差异不明显。仿真结果表明，PE-VAR 算法较DBR和E-VAR 算法而言，提高了数据包投递成功率，降低了数据包平均投递时延、节点死亡率以及网络总体能量消耗百分比，最终提升了整体网络的性能，延长了网络生命周期。

图10 节点静态时网络性能对比

图11 节点动态时网络性能对比

4 结语

通过考虑路由过程中出现的循环冗余传输情况，提出了一种避免路由循环和空洞节点的基于节点深度值的路由协议，通过比较路由循环中各节点的优先级，更换替换优先级值最大的节点的原转发节点，跳出循环并继续进行数据包的转发。仿真结果表明，PE-VAR 算法在数据包投递成功率、数据包投递平均时延、节点死亡率、平均能量消耗性能方面，相比较DBR 算法和E-VAR 算法，都有一定提升。