基于连通的水声网络节点路由分层方案*

韩多亮杜秀娟柳秀秀王丽娟张智学

(1.青海师范大学计算机学院，青海省物联网重点实验室，青海 西宁 810008；2.藏语智能信息处理及应用国家重点实验室，青海 西宁 810008；3.高原科学与可持续发展研究院，青海 西宁 810008)

水声网络(underwater acoustic networks，UANs)作为人类研究海洋等水下环境的主要手段，成为了各高校和科研院所的研究热点[1-5]。 UANs 应用的多样性包括环境监测、污染控制、自然灾害的预测和反应、生态系统分析、防御应用监测等。 目前，这些应用大多通过架设少量电缆或光缆提供网络基础设施服务并采用单跳传输的无线通信技术。 水下铺设电/光缆成本高昂，单跳无线传输难以提供灵活快捷部署和大范围监测，但是，UANs 能够实现在水下快速、大范围部署的自组多跳网络应用。 此外，UANs固有的长传播延迟、低带宽、通信能耗大、多径效应以及时空变化等特性给UANs 路由协议的设计带来了很大的挑战，UANs 路由受链路变化的影响很大，比陆地无线电信号链路的变化更不可预测和管理[6-9]。 设计可靠的UANs 路由机制至关重要，基于连通的UANs 节点路由分层方案是UANs 可靠路由设计的关键，因此，本文提出了基于连通的节点路由分层方案。

1 分层路由

UANs 路由协议通常可基于Sink 节点的数量、是否需要节点地理位置、是否分簇、按需或主动等进行分类。 UANs 具有定向通信特点，上行流量目的地为Sink 节点，下行流量源自Sink 节点，Sink 节点是UANs 的枢纽[10]。 那些靠近Sink 节点的水下节点，除了感知和产生数据之外，还负责中继和转发报文。 因此，Sink 节点及其附近的节点对整个UANs具有重要的影响。 为了表示节点的重要程度，提高数据交付率和传输可靠性，近年来UANs 逐渐出现了基于分层的路由机制。 因此，本文根据是否采用分层机制，将路由协议分为无层级路由协议和分层路由协议。

无层级路由协议是指通信过程中，所有节点均不配置层级，也不将层级作为节点的候选转发资格的条件。 无层级的路由协议有Vector-Based Forwarding(VBF)[11]、Depth based Routing(DBR)[12]、Position based Forwarding ( PBF )[13]、 Annular Compass Routing(ACR)[14]等。 分层路由协议中，一般分为两个阶段:分层阶段和数据转发阶段。 分层阶段每个节点根据相应信息和分层算法配置自身的层级。 通常来说，越靠近Sink 节点的节点层级越小，数据报文由层级大的节点传输至层级小的节点，转发节点在选择下一跳接收节点时，会将层级作为指标，选择层级比自身层级小1 的节点作为候选转发节点，逐层将数据传输至Sink 节点。

1.1 传统分层方案

近几年提出的路由分层方案有基于超级节点配置的分层方案、基于距离或深度的分层方案、基于能量探测的分层方案等。

基于超级节点配置的分层方案:水面的超级节点以不同的发送功率广播控制报文，其中包含与功率对应的层级信息、超级节点ID 等，直到发送功率(层级)达到最大，普通节点根据广播包中的层级信息确定自身的层级[15]。 基于距离或深度的分层方案:通过计算Sink 节点与普通节点的距离(或节点深度)和层间距将网络中的节点划分为N 层[16]。基于能量探测的分层方案:通过广播能量探测包将网络划分为L 层[17]。

基于转发节点传输范围的分层方案:根据网络中转发节点的传输范围将传输区域分为三层[18]。

基于超级节点配置分层的方案和基于距离或深度的分层方案均要求Sink 节点或超级节点不断调整发送功率发送控制报文。 这是因为根据水声信号衰减模型，当控制信号的强度在距离较远的接收节点处小于节点的最小接收功率时，节点无法正确接收该报文，此时Sink 节点或超级节点需要以更大的发送功率发送控制报文，从而扩大广播包的传输范围，但发送功率的不断增大会增加额外的能耗。 基于超级节点配置分层的方案，水下节点只要收到超级节点发出的广播信息，按照广播包中的层级信息即可确定自身的层级。 基于距离或深度的分层方案中，节点根据自身到Sink 节点的距离和层间距计算并更新自身的层级信息。 基于能量探测的分层方案中节点根据接收到的广播包中的能量信息更新自身的层级。 以上三种分层方案中，水下节点不必转发收到的广播报文，分层方案简单，分层过程无需消耗普通节点的能量，但对Sink 节点或超级节点的发送功率要求较高，不适用大规模UANs 部署。 此外，从三种分层方案中可以看出，水下节点的层级配置与到超级节点的距离密切相关，凡超级节点(以大的发送功率)一跳传输范围内的所有水下节点都能获取自身的层级，但该层级与自节点自身到Sink 节点的数据传输方向的连通性和跳数无关，因此容易形成上行路由“通信空区”问题，降低了该分层方案的上行路由的数据传输的可靠性。

1.2 “通信空区”问题

Yanhai 等提出了一种基于深度的路由协议DBR。 该协议是一种典型的多Sink 节点网络体系结构的路由协议，节点不需要知道自身的全方位位置信息，只需获取自己的深度信息[11]。 DBR 是UANs 中的典型路由协议，在此基础上，出现了许多改进版本。 传统分层路由协议与DBR 及其众多改进版协议在候选转发节点的选取方面采用类似的机制，因此我们以DBR 或传统分层路由为例分析“通信空区”问题。

在DBR 协议(或传统分层路由)中，当一个节点收到数据包时，将从数据包中查看上一跳节点的深度(或分层)信息，并与自己的深度(或分层)信息作对比，如果自身深度(或分层)小于上一跳节点的深度(或分层)，则说明其可以作为转发节点，否则，直接将数据包丢弃。 协议中根据深度(或分层)差选择转发节点，因此会出现多个转发节点，即会有冗余数据包产生。

DBR(或传统分层路由)协议根据深度(或分层)信息执行路由转发，在网络稀疏的情况下，会造成“通信空区”，如图1 所示。 根据DBR 协议，源节点S 将数据发送出去后，节点F 和节点N1将会收到该数据包，但是N1的深度(或分层)大于S，不能作为候选转发节点；只有节点F 会转发数据，但是在F的传输范围内没有比F 深度(或分层)更小的节点，所以本次数据将无法传输至Sink 节点，形成了“通信空区”，降低了包的交付率和传输可靠性。

图1 “通信空区”与有效分层问题示意图

在基于分层的路由机制中，数据的流向总是沿着从高层级节点向低层级节点传输，最终将数据传输至Sink 节点。 针对UANs 传统(分层)路由协议的“通信空区”问题，如果我们能够设计出有效的分层算法，给那些与Sink 节点连通的水下节点配置一个有限的层级，将会解决“通信空区”路由问题。 如图1，假设源节点S 的层级为L，N1的层级为L-1，则节点S 可将N1作为下一跳接收节点，直接将数据发送给N1，数据将沿着N1-N2-N3-N4-N5传输至Sink 节点，而不会将数据传输至F，如此，即解决了“通信空区”问题。

2 基于连通和最小跳数的路由分层

2.1 分层方案

为了解决传统分层路由的“通信空区”问题，我们提出一种基于节点与Sink 节点连通的最小跳数的路由分层方案，即:将距离Sink 节点的最小跳数定义为节点的层级。 在基于最小跳数的分层算法中，Sink节点以与水下节点相同的发送功率定期向网络泛洪包含其ID、层级(被Sink 节点初始化为0)和剩余能量等信息的Hello 报文，当水下节点第一次收到Hello报文时，提取报文头部的层级信息，即上一跳节点的层级Lpre，将Lpre+1 作为自己的层级。 之后节点用自己的ID、层级、剩余能量等更新并继续广播更新后的Hello 报文。 经过一段时间，收到Hello 报文的水下节点都能获取或更新自己的层级信息，获取了层级的节点会继续更新广播Hello 报文。

当一个已经获取了层级的接收节点收到Hello报文时，接收节点需要判断是否更新层级，具体规则如下:当一个已经获取自身层级且该层级信息老化时间未到期的水下传感器节点接收到一个Hello 报文时，它将比较自身层级L＿Rec 和报文中层级L＿Snd 的大小。 若L＿Rec＞L＿Snd+1 时，则更新自身层级为L＿Rec＝L＿Snd+1，并用节点自身层级信息和节点ID 来替换Hello 报文中的层级和发送节点ID 字段信息后，进而广播新的Hello 报文；否则丢弃该报文，将不会转发该报文。 当一个已经获取自身层级，但该层级信息老化时间已到期的水下传感器节点接收到一个Hello报文时，将直接更新自身层级为L＿Rec ＝L＿Snd+1，重新建立该节点的连通性。 如果节点始终收不到控制报文，则该节点与Sink 节点未连通，该节点为孤立节点，不能用于转发报文。 分层算法伪代码如算法1。

算法1 基于最小跳数的分层算法

如图2 所示，根据基于连通和最小跳数的路由分层方案，Sink 节点的层级为0，转发节点F1、F2、F的层级均为1，F 收到F1、F2转发的控制报文后也不再更新自身的层级，也即三个转发节点均为Sink 节点的一跳邻居。 通信时，数据由高层级节点往低层级自下往上传输。

图2 基于连通和最小跳数分层方案

在基于连通和最小跳数的分层方案中，如果水下节点与Sink 节点连通，无论经过多少跳的转发，总能收到控制报文并确定自身的层级。

2.2 “通信空区”问题避免

当水下节点向Sink 节点转发数据报文时，根据基于连通和最小跳数的路由分层方案，在分层阶段，由于节点层级的更新与上一跳节点的层级有关且每个节点均需转发Hello 报文，因此在分层阶段已经形成了到达Sink 节点的一条或者多条路径，即水下节点在更新层级后已与Sink 节点连通。 只要数据的源节点有一个有效的层级，则数据在转发的每一跳都会找到至少一个上层的邻居节点，因此数据不会被路由到“通信空区”，进而不会出现路由“通信空区”问题。 如图3 所示，图中L1表示层级1，L2表示层级2，N8表示节点8，N8的层级与N12层级均为L5，源节点N19发出的数据传输至节点N12时，N12不会将数据传输至N8，数据将沿着N12→N10→N7→N4→N1→Sink 节点的路径，成功将数据传输至Sink 节点。 因此采用基于连通和最小跳数的路由分层方案成功避免了传统分层(路由)节点N8的路由“通信空区”问题。

图3 路由“通信空区”避免

3 能耗模型

UANs 能量供应受限且通信能耗大，节能是UANs 设计的重要目标。 UANs 中除岸上基站中心外，普通节点处于水中且采用电池供电，一旦电量耗尽难以充电或更换。 UANs 通信中能量的消耗主要体现在发送数据和接收数据等通信状态。 2000 年Sozer 等人提出了UANs 中的能耗衰减模型[19]。

假设Pr(常量)是网络中节点的接收功率，则网络中节点的发送功率为PrA(d)，A(d)为衰减因子。

式中:d为两个节点间的通信距离，k是能量扩散因子，其取值由环境决定，圆柱体中取k＝1，长方体中是k＝1.5，球体中是k＝2，从吸收系数α(f)中得到的相关项为∂，

假设一次UANs 通信中，发送节点与下一跳接收节点之间的距离(由发送节点在转发之前计算自身至下一跳接收节点的距离)为r，则一跳转发中消耗的能量为:

式中:Ps为发送功率，Ps＝PrA(r)，Tp是源节点或转发节点发送一个数据包的传输时延，Pr为接收功率。

根据上述能耗衰减模型，数据传输中的能量消耗与传输距离有关，长距离传输会导致能量损耗较大，因此采用2.1 节的分层机制转发节点F 的能量损耗较快，其寿命会缩短，进而缩短了网络的整体寿命。

4 基于连通的节能路由分层方案

在基于连通和最小跳数的路由分层方案中，Sink 节点的层级为0，转发节点F1、F2、F 的层级均为1，F 收到F1、F2转发的控制报文后也不再更新自身的层级，也即三个转发节点均为Sink 节点的一跳邻居。 当F 收到来自于第二层节点的数据后，会直接将数据传输至Sink 节点，根据节3 的能耗衰减模型，数据传输中的能量消耗与传输距离有关，长距离传输会导致能量损耗较大，因此转发节点F 的能量损耗较快，其寿命会缩短，进而缩短了网络的整体寿命。

为了减小能量消耗，延长网络生存期，本节对2.1 节的分层方案进一步优化，提出一种基于连通的节能路由分层方案。

Sink 节点定期向网络泛洪包含其ID、层级(被Sink 节点初始化为0)和地理位置等信息的Hello 报文。 节点收到控制报文后，按以下步骤更新层级。

步骤1:提取报文头部发送节点的层级字段L＿Snd，判断层级老化时间是否已到，若老化时间已到，则自身层级L＿Rec 更新为L＿Snd+1，并立即转发更新后的控制报文；否则，执行步骤2；

步骤2:判断发送者层级L＿Snd 是否大于L＿Rec，若L＿Snd＞L＿Rec，说明报文来自下游节点，L＿Rec 保持不变；否则，执行步骤3；

步骤3:判断L＿Rec 是否等于255，若是，则L＿Rec ＝L＿Snd+1；否则，执行步骤4；

步骤4:判断L＿Rec 是否等于L＿Snd，若不是，则执行步骤6；否则，计算当前节点与当前发送节点和上一次更新层级时发送节点的距离Dc、Dp和夹角a，执行步骤5；

步骤5:判断a的大小、Dc和Dp的关系，若a＜30°(a阈值的得出在第4 节中给出)且Dc＜Dp，则L＿Rec ＝L＿Snd+1，否则，L＿Rec 保持不变。

步骤6:判断L＿Snd 是否等于L＿Rec-1，若是，则更新层级老化时间；否则，执行步骤7；

步骤7:判断L＿Snd 是否等于L＿Rec-2，若不是，则执行步骤9；否则，计算当前节点与当前发送节点和上一次更新层级时发送节点的距离Dc、Dp和夹角a，执行步骤8；

步骤8:判断a的大小、Dc和Dp的关系，若a＜30°且Dc＞Dp，则L＿Rec 保持不变；否则，L＿Rec ＝L＿Snd+1。

步骤9:判断L＿Snd 是否小于L＿Rec-2，若是，L＿Rec 保持不变；否则，层级保持不变。

如图4 所示，网络初始化完成后，Sink 节点周期性广播Hello 报文后，转发节点F1、F2、F 均将首次收到Hello 报文，提取Hello 报文头部Sink 节点的层级0，将自身的层级更新为1，将Hello 报文进行更新并立即转发。 转发节点F 将会收到F1、F2转发的Hello 报文(由于转发节点F1、F2的层级均是1，下面将不再区分收到由转发节点F1、F2转发Hello 报文的先后顺序)，由于转发节点F、F1和F2的层级均为1，发送节点的层级大于当前节点层级的条件不成立，因此，转发节点F 将计算自身到Sink 节点的距离和自身到转发节点F1、F2的距离并计算两者之间的夹角a，从图4 中可以看出，转发节点F 到F1、F2的距离较近且夹角a较小，因此，转发节点F 将提取Hello 报文头部F1、F2的层级1，加1 后作为自身的层级。

图4 基于连通的的节能分层方案拓扑

基于连通的节能路由分层方案继承了基于最小跳数的路由分层方案的优势，通过Hello 报文在整个网络的泛洪，形成水下节点到Sink 节点的有效路径，在数据传输时，转发节点总能找到有效的下一跳转发节点，解决了“通信空区”问题。 基于连通的节能分层方案也有其自身的优点，通信中，转发节点F收到数据后，先将数据转发至F1或F2，再转发至Sink 节点，构成了两跳传输，由于转发节点F 到F1或F2的距离较近，转发节点F 消耗的能量小于其直接将数据转发至Sink 节点的能量，即使F1或F2有能量消耗，但在一定条件下，两跳转发消耗的能量仍然会小于直接将数据传输至Sink 节点消耗的能量。如果采用基于最小跳数的分层方案，转发节点F 收到数据后，会直接将数据转发至至Sink 节点，一跳传输消耗的能量可能大于两跳传输消耗的能量。

节5 将利用能耗模型和MATLAB 仿真对基于最小跳数和基于连通节能的两种路由分层方案的能量消耗进行分析。

5 能耗分析

本节以图4 拓扑为例，利用能耗模型对基于最小跳数的路由分层方案与基于连通的节能路由分层方案进行对比分析。

假设转发节点F 至Sink 节点的距离是d，转发节点F 至F1、F1至Sink 节点的距离分别是d1、d2；数据由转发节点F 直接转发至Sink 节点消耗的能量为E，由转发节点F 转发至F1或F2再转发至Sink 节点消耗的能量为E′，则根据式(4)得

式中:A(d)＝dk∂d，Ps＝PrA(d)，k＝1.5。 由于传输时延Tp相同、所有节点的接收功率Pr均一致，因此，E和E′的计算公式如下:

假设d1与d之间的夹角是a，则根据余弦定理即得:

当a＝0°时，则:

用MATLAB 仿真比较分析了E和E′的大小关系，将E和E′称为相对能耗，仿真中，假设d的取值范围是(0，5)，单位:km，d1的取值在d的取值范围内取值，取值分别为:d/20、d/10、d/5、d/4、d/3、d/2、2d/3、3d/4、4d/5、5d/6，a的角度在(0°，90°)范围内变化，信道的中心频率为10 kHz，仿真结果如图5。

图5 a＝0°，d＝10 时，d1 与相对能耗的关系

如图5，当a＝0°，d＝10 时，从图中可以看到，一跳传输至Sink 节点的相对能耗保持不变，但是，随着d1的逐渐增大，两跳传输至Sink 节点的相对能耗逐渐减小。 当d1＝d2＝d/2 时，两跳传输至Sink节点的相对能耗达到最小值；由于a＝0°，d＝10 且d1的值一直小于d，一跳传输至Sink 节点的相对能耗总大于两跳传输至Sink 节点的相对能耗。

如图5～图10，当a逐渐增大时，通过两跳传输至Sink 节点的相对能耗逐渐大于通过一跳传输至Sink 节点的相对能耗。 当a＝90°时，d1的长度大于d，因此，通过两跳传输至Sink 节点的相对能耗完全大于通过一跳传输至Sink 节点的相对能耗。

图6 a＝0°，d、d1 与相对能耗的关系

图7 a＝30°，d、d1 与相对能耗的关系

图8 a＝45°，d、d1 与相对能耗的关系

图9 a＝60°，d、d1 与相对能耗的关系

图10 a＝90°，d、d1 与相对能耗的关系

综合图5 ～图10，当d1＞d时，通过两跳传输至Sink 节点的相对能耗大于通过一跳传输至Sink 节点的相对能耗；当d1＜d时，通过两跳传输至Sink 节点的相对能耗小于通过一跳传输至Sink 节点的相对能耗；且当d1＝d/2 时，通过两跳传输至Sink 节点的相对能耗达到最小值。

综合模型数学分析和MATLAB 仿真分析的结果，当d1＜d且a＜＝30°时，通过两跳传输至Sink 节点的相对能耗小于通过一跳传输至Sink 节点的相对能耗，因此，数据转发时采用基于连通的节能路由分层方案传输，有效减小了节点的能量消耗，从而提高了整个网络的寿命。

6 仿真实验

NS3 是一款由华盛顿大学设计开发的全新的网络模拟器，广泛汲取了NS2、GTNetS 等优秀模拟器的成功技术和经验，其性能更佳、扩展性更好，更加接近真实网络[20]。 因此，本节将用NS-3 仿真工具对分层方案进行性能评估。 仿真中，利用文献[6]中基于层级的自适应地理路由协议，分别采用基于最小跳数的路由分层方案和基于连通的节能路由分层方案进行路由传输仿真实验，并从数据包交付率、端到端的平均延时和平均能耗三个方面进行了对比分析，此外，还增加了和基于分层的能量均衡的路由协议(layerbased and energy-efficient routing，LEER)[21]的对比实验。 实验场景设置如下:15 个～45 个传感器节点随机部署在6 000 m×6 000 m×3 000 m 的长方体中，将一个Sink 节点部署在水面(长方体上表面中心)，一个源节点部署在水底(长方体下表面中心)，实验中的其他实验仿真参数如表1 所示。

表1 仿真参数表

本文进行性能评估指标的定义如下:

包交付率(packet delivery ratio，PDR):是指Sink 节点成功接收的数据包数量与源节点发送的数据包数量之比，PDR 计算公式如下:

式中:n是仿真实验的次数，Psend是源节点产生发送的数据包的数量，Prece为Sink 节点成功接收的数据包的数量。

平均能耗(average energy consumption，AEC):是指一次仿真实验中网络的总能耗与Sink 节点成功接收的数据包数量之比，计算公式如下:

式中:Etotal表示网络的总能耗；Psuccess表示Sink 节点成功接收的数据包的数量。

平均端到端的延时(average end-to-end delay，AEED):是指在一次仿真实验中，Sink 节点成功接收数据包的时刻与源节点发送数据时刻的差的总和和传输数据包次数的比值，AEED 的计算公式如下:

式中:Ntrans是一次仿真实验中传输数据包的次数，TSink和Tsource分别是Sink 节点成功接收数据包的时刻和源节点发送数据的时刻。

实验中，分别仿真测试了节点个数与数据包交付率、平均能耗和网络的平均端到端延时的关系，数据关系图分别如图11～图13 所示。

图11 节点个数与交付率

图13 节点个数与延时

如图11 中，随着节点数量的逐渐增多，两种分层方案的数据包交付率均保持在90%以上。 基于连通的节能路由分层方案的数据包交付率略低于基于最小跳数的路由分层方案，但是，交付率差值均保持在1%～3%之间。 同时，LEER 协议属于泛洪的路由协议，随着节点数的增加，会提高数据包的交付率，但同时会造成冲突，所以，交付率低于利用了两种路由分层方案的交付率。

如图12 中，随着部署的节点数量的增多，由于基于连通的节能路由分层方案实现了短距离多跳传输，因此，它的平均能耗明显小于基于最小跳数的路由分层方案的平均能耗。 文献[6]中的路由协议在数据转发前已确定了最佳下一跳转发节点，每一跳参与数据转发的节点只有一个，且只有最佳下一跳转发节点接收数据包；然而，LEER 协议属于泛洪的路由协议，随着节点数的增加，参与接收数据包的节点会增多，因此，提出的两种路由分层方案的平均能耗低于LEER 协议。

图12 节点个数和平均能耗

图13 中，随着部署的节点数量的增多，两种路由分层方案的平均端到端的延时基本保持不变，然而，由于基于连通的节能路由分层方案中，传输跳数的增加，其平均端到端的延时稍大于基于最小跳数的路由分层方案的平均端到端的延时。 同时，从图中可以看出，采用两种路由分层方案的路由协议的端到端的平均延时低于LEER 协议。

基于连通的节能路由分层方案中，为了均衡Sink 节点附近的节点的能量消耗，其附近节点的层级大于Sink 节点，可以实现多跳传输且其单跳传输的距离较短，通信中，可以利用较小的发送功率，因此附近节点的能量会有效减少。 同时，水下其他节点根据距离确定层级，层与层之间的距离可以缩短，即可以实现短距离多跳传输。 综合图11 ～图13，虽然基于连通的节能路由分层方案的延时稍有增加，但是其数据包交付率基本与基于最小跳数的路由分层方案的交付率保持一致且其能耗有效减少。 因此，基于连通的节能路由分层方案的性能优于基于最小跳数的路由分层方案。

7 结论

本文提出了两种基于连通的水下节点路由分层方案:基于最小跳数的节点路由分层方案和基于连通的节能路由分层方案，实现了分层多跳传输，通过数学模型、MATLAB 分析了基于连通的节能路由分层方案传输的优势，并用NS3 仿真对比分析了两种基于连通的路由分层方案，实验结果表明:①基于连通的节能路由分层方案能够有效节省能耗，从而能够提高网络的整体寿命；②两种基于连通的路由分层方案可以有效解决“通信空区”问题；③本文提出的节点路由分层方案可以及时更新层级、实现短距离多跳传输，交付率较高且平均能耗低于LEER 协议。

UANs 的应用环境为水中，能量供应困难，因此设计合适的传输机制至关重要，基于连通的节能路由分层方案虽然在交付率和能耗方面有很大优势，但在减小延时方面仍然存在不足，本文下一步的工作将全面考虑，提出性能更加优越的路由分层方案。