基于REPBR跳数效用转发的改进路由算法

吴镜汝，袁 丁，严 清

(1.四川师范大学 计算机科学学院，四川 成都 610101；2.重庆移通学院 计算机学院，重庆 400000)

0 引 言

水下无线传感器网络(underwater wireless sensor networks，UWSNs)是一种复杂的、高效的、基于声学传感器的、可实现高速数据传输和高精度计算的水下监测系统[1-3]。

电磁波在水下网络环境的传播距离只有50 cm～100 cm，不能作为水下的传输介质。因此，目前主要采用声波作为传输方式，从无线电的3×108m/s降为1.5×103m/s，这意味着传输延迟更大，带宽更低[4]。再加上多普勒效应、多径效应、背景噪声等多种因素的干扰，进一步限制了传输带宽[5]。另外，水下节点面临能量问题，因为这些节点配备了电池作为唯一可用的电源。与地面无线传感器网络相比，由于使用声波作为通信介质，UWSNs中的传输和接收能耗有所增加[6]。因此，数据包的发送和接收消耗了水下传感器节点的大部分能量。水下传感器节点的路由是网络中负责转发和接收数据包的主要部分[7]，为保证路由算法的工作效率，降低能耗，减少时延，选择最节能、最可靠的节点进行数据转发，必须设计高效节能的路由算法。

DBR[8](depth-based routing for underwater sensor networks)路由协议是第一个无本地化的路由协议，它的优点是不需要完整的尺寸位置信息，考虑传感器节点的深度信息，从源节点中选择具有最小深度的节点作为转发器，但是它的缺点是深度小的节点更早死亡，导致路由网络寿命更短；EEDBR[9](energy-efficient depth-based routing protocol for underwater wireless sensor networks)路由协议主要分为信息获取阶段和数据转发阶段。在信息获取阶段，传感器节点基于较高的剩余能量和最小的深度找到邻居，并将其ID存储在路由表中。在转发阶段，选择路由表中剩余能量最高和深度最小的节点进行数据包转发，降低能量消耗，但它的缺点是没有考虑链路质量，导致不稳定链路带来更多的能量消耗。REPBR[10](reliable energy-efficient pressure-based routing protocol for underwater wireless sensor network)路由协议用三角形度量方法估计链路质量，考虑链路质量、深度和剩余能量3个参数，平衡能耗和可靠的数据传输，设计基于路由代价计算的多尺度数据转发算法，但其缺点是过长的路径转发提高了网络的延时，降低了数据包的转发效率。以上基于无定位路由协议对比见表1。

表1 基于无定位路由协议对比

1 REPBR路由算法研究

REPBR路由协议是一种无位置、可靠、节能的压力路由协议，它利用深度、剩余能量和链路质量3个参数来选择下一个转发节点。该协议由信息获取阶段和数据转发阶段构成。

信息获取阶段：在此阶段，每个节点在较小深度的节点之间交换特定的信息。首先，每个节点定期向它的单跳邻居广播一个Hello报文，Hello报文里面包括节点的ID、剩余能量和深度。每个节点收到Hello报文后，提取Hello报文的深度信息，并与邻居节点作比较，如果Hello报文的深度小于它的深度，它将节点保存在它的邻居信息表中，否则丢弃此报文，完成邻居信息表的更新。每个节点用链路质量算法计算每个邻居的距离，对链路质量进行估计，其Hello报文格式如图1所示。

图1 Hello报文格式

数据转发阶段：在此阶段，数据包从源节点转发到sink节点。源节点检索它的邻居信息表中的节点信息，并使用公式计算路由开销，然后选择路由开销最小的节点作为转发节点的最佳候选节点。然后发送方将所选节点的ID嵌入数据包进行广播，邻居节点只有收到与自己节点ID相同的才会接收数据包。路由开销计算用式(1)表示

(1)

式中：Ei和Einit分别为当前节点i的剩余能量和初始能量，d(x，y) 是发送节点和转发节点之间计算出的链路质量值，dmax是系统参数值，根据环境设置。

为减少不必要的数据转发，选择最可靠、最高效的节点，本文提出一种在超低通信速率环境下，基于REPBR跳数效用转发的改进路由算法(简称HUF)，在数据包传输阶段考虑最优最短路径节点的选择，跳数最少的路由可以保证任意节点的信息沿着最优路径发送到网关节点，同时综合链路质量、剩余能量选择最优的下一跳转发节点，使得整个信息传输过程消耗的总能量最小[11]，降低网络时延。

2 改进路由算法(HUF)

在进行海洋资源探索时，水下传感器网络可以采集海洋油气资源勘探所需的数据信息并经过水下节点层层传输，最后由基站接收[12]。REPBR路由协议通过加入链路质量的计算提高网络的生存时间，但是该协议没有考虑发送节点到接收节点之间的最短路径，导致时延增加，不能更快接收海洋数据信息。因此为降低网络时延，减少能量消耗，避免不必要的路径传输，本文改进路由算法引入效用函数策略(综合链路质量、剩余能量、节点间的跳数)选择最优的下一跳转发节点，降低网络时延，提高UWSNs网络性能。

2.1 效用函数模型

HUF路由算法建立了基于节点理性偏好特征的博弈模型来研究水下无线传感器网络中的路由问题。首先，将博弈模型的3个要素定义为一个三元组 (N，S，U)[13]。 其中，N代表博弈中的所有节点的集合；S代表博弈中各个节点到汇聚节点的路径集合；U代表博弈中各个节点的效用函数，在本文的博弈模型中根据节点的效用函数值确定最优转发节点，并结合该节点向基站转发数据时的跳数、当前剩余能量值和节点之间的链路质量给出效用函数，如式(2)所示

U=α(Mhcmax/Mhi)+β(Ei/Einit)+γ(LQ)

(2)

式中：Mhi表示当前节点向基站转发数据路径上的最小跳数，Mhcmax表示参与节点与基站的最大跳数，Ei和Einit分别为当前节点i的剩余能量和初始能量，LQ是发送节点和转发节点之间计算出的链路质量值。ɑ，β，γ为权重因子[14]，目的是根据网络的实际情况，调整各个参数对博弈结果的影响程度。

2.2 链路质量计算

在水下无线传感器网络中，传感器节点在数据传输时，容易受到周围环境的影响和干扰[15]。在已有的很多路由协议的设计与仿真中，很多都忽视了对通信链路的链路质量进行评估，而这种评估往往是建立在一个理想链路的基础上。然而，在实践中，通信链路具有随机的波动性[16]。这样的变化会带来诸如网络吞吐量下降和能耗上升等问题。在实际中，正确地评价链接质量，是保证可靠的网络通讯的前提，具有重要意义。

在本文中，链路质量的计算结合LQI[17]和RSSI[18]两个评估指标：RSSI是接收信号指示强度，是指无线传感器通信过程中的信号功率；LQI是链路质量指示器，在硬件设备的支持下，RSSI和LQI都可以实时测量，并且可以以较低的网络成本快速反映链路质量的变化，LQI和RSSI值之间存在相关性[19]，当节点i向节点j发送数据时，节点之间的链路质量表示为式(3)

(3)

2.3 最小跳数模型

最小跳数路由协议(LHR)是在定向扩散算法(directed diffulion，DD)[20]和洪泛算法[21](Flooding)的基础上，引入跳数的概念而发展起来。通过发布洪泛消息，将数据分组从全网各个节点发送至Sink节点，并以最短的跳数将其传输至目的地，这一过程包括梯度场构建、数据分组传输、查询分组传输以及路由维护4个步骤。通过采用最小跳数路由算法，可以有效降低开销，节省能源，同时还可以通过路由维护来提升算法的灵活性，从而更好地适应动态网络拓扑。

(1)梯度场建立阶段：

1)我们把汇聚节点的跳跃次数设定为0，而对于其它节点，则把它们的跳跃次数调整为255。

2)sink节点通过洪泛的方法向水下无线传感器网络传输数据检索信息，这些信息中包括了汇聚节点ID、节点深度以及最小跳跃数值HC等。

3)在接收到汇聚节点的相关信息之后，我们会把最小跳数HC+1的新HC值和汇聚节点内部的HC值做对照，若是新HC值低于原来的HC值，则用新的HC值替换报文中的HC值，替换原先的发送节点ID为代价节点ID，接着用广播的方式将修订过的查询信息传递给相邻的节点；若新的HC值超过了原有的值，那么就会舍弃查询包并不做任何处理。

4)在其它节点接收到查询信息后，再次执行之前的处理步骤，最后形成最小跳跃数梯度场如图2所示。

图2 梯度建立阶段

(2)数据传输阶段：

数据传输过程中，一旦接收端的设备收集了信息，它会通过Flooding的形式将其传送至汇总端。在这个过程中，每一次的HC值都会降低1，这样就能将来自接收端的信息传送至汇总端，并且这个过程会按照一个逐步降低的最低跳数值进行。如图3所示。

图3 数据传输阶段

通过以上初始化过程，每个节点均获得到sink节点的最小跳数，建立了到sink节点的多条最小跳数路径，为数据包的路由转发计算做好了准备。

2.4 HUF路由算法

2.4.1 数据获取阶段

在此阶段，每个节点在较小深度的节点之间交换特定的信息。首先，每个节点定期的向它的单跳邻居广播一个Hello报文，Hello报文里面包括节点的跳数、剩余能量和深度。每个节点收到Hello报文后，提取Hello报文的深度信息，并与邻居节点作比较，如果Hello报文的深度小于它的深度，它将节点保存在它的邻居信息表中。否则丢弃此报文，完成邻居信息表的更新，每个节点用链路质量算法计算节点邻居间的链路质量值，Hello报文如图4所示。

如算法1所示，信息获取阶段每个传感器节点在特定的时间间隔内生成一个新的Hello数据包，并将其广播给它的单跳邻居，接着调用了接收Hello数据包来检查信息，并调用链路质量算法。

算法1：信息获取阶段

// 生成Hello数据包

(1)生成Hello数据包

(2)将节点ID、深度、剩余能量和节点跳数加入数据包

(3)广播数据包

//接收Hello数据包

(4)if 节点i的深度大于数据包的节点深度 then

(5)if 节点ID不存在于节点i的NIT中 then

(6) 将数据包的节点加入节点i的NIT中

(7)else 更新节点i的NIT

(8)end if

(9) 计算节点i的链路质量

(10)else

(11) 丢弃Hello数据包

(12)end if

在水下无线传感器网络中，节点的位置是不断变化的，因此一些节点可能会进入另一个节点的范围，或者一些现有的邻居超出了节点的范围。所以在特定的时间间隔内周期性地调用信息获取阶段，以此更新每个传感器节点的NIT。

2.4.2 数据转发阶段

在此阶段，数据包从源节点转发到sink节点。源节点检索它的邻居信息表中的节点信息，并使用效用函数式(4)计算路由效益U，然后选择路由效益最优的节点作为转发节点的最佳候选节点。然后发送方将所选节点的ID嵌入数据包进行广播，邻居节点只有收到与自己节点ID相同的才会接收数据包，邻居信息表如图5所示

图5 邻居信息表

U=α(Mhcmax/Mhi)+β(Ei/Einit)+γ(LQ)

(4)

该方程基于3个不同的指标计算路由收益，在本文中，深度低于发送方的节点具有更高的剩余能量和更好的链路质量以及路径最优，从而使路由效益最大化体现。

如算法2所示，数据转发阶段发送方节点检索所有邻居节点的信息，并用式(4)计算路由效益。然后发送方节点选择路由效益最大的节点作为转发器节点的最佳候选节点。发送方将所选节点的ID嵌入数据包，并将数据包广播给其单跳邻居。在接收到分组时，接收节点将其ID与嵌入分组中的ID进行比较，只有找到与其ID和嵌入在数据包中的ID匹配的节点才会接收数据包，而所有其它相邻节点都会丢弃该数据包。该过程持续重复，直到数据包到达其中一个接收器节点。此外，发送方节点尝试以最优最短的路径传输数据包，在保证链路质量稳定的网络状态下选择最优的路径，减少了转发路径过程中的网络时延、能量消耗，提高了网络生命周期。

算法2：数据转发阶段

//判断节点ID是否匹配

(1)if 节点i的ID匹配数据包中的转发ID then

//计算邻居节点的路由效益

(2)U=α(Mhcmax/Mhi)+β(Ei/Einit)+γ(LQ)

(3)将节点的路由效益加入邻居信息表中

(4)else 丢弃数据包

(5)按照节点的跳数和路由效益对邻居节点进行排序

(6)end if 选择邻居节点中，路由效益最大的节点作为转发节点

3 实验仿真

3.1 仿真环境的建立

在本文中，使用MATLAB实验平台进行仿真，分析了针对UWSNs提出的跳数协议的性能，基于实验环境，给出了平台中的某些参数的假设，见表2。

表2 实验平台的参数设置

3.2 实验参数

对于实验中所用到的对比参数：端到端时延、数据包投递率、网络生命周期、能量消耗，进行如下的说明：

(1)端到端时延(end-to-end delay)：数据包在网络中从源节点到目的节点或者目的节点到源节点花费的时间，它是源节点到sink节点之间每个链路的传输延迟、传播延迟和处理延迟的叠加。

(2)数据包投递率(packet delivery ratio)：源节点生成的数据包数量与接收器的数据包数量之间的比率。

(3)网络生命周期(network life time)：网络与传感器节点保持活动状态的总持续时间，它是网络启动时间到网络最后一个节点停电时间之间的时间间隔。

(4)能量消耗(energy consumption)：数据传输后的初始能量与剩余能量之差。

3.3 仿真实验结果分析

如图6所示，分别测量了HUF、REPBR、DBR和EEDBR的网络寿命，并与之进行比较。可以看出DBR的生命周期比HUF、REPBR、EEDBR短，这是由于在DBR中没有考虑剩余能量度量，而是只依赖深度信息进行下一个节点的选择。因此较小深度的节点会更快地耗尽其能量，导致网络崩溃。相比之下，EEDBR的网络生存时间比DBR长，这是由于在EEDBR中利用剩余能量和深度信息，导致节点间能量消耗均衡。HUF和REPBR在网络生存方面的性能优于DBR和EEDBR，在REPBR中，每个发送节点都选择剩余能量更高、链路质量更好的转发节点，因此在网络拓扑中，网络生存时间都较长，但是HUF考虑了节点信息中跳数最小、剩余能量更高、链路质量更好的最优转发节点，所以网络生存周期比REPBR更长，同时跳数的选择计算也需要消耗一定的节点能量，所以HUF的生存时间略高于REPBR。DBR和EEDBR的网络生存时间都是随着节点数的增加而减少，DBR只利用深度信息来选择最短路径，而不考虑剩余能量，总是选择深度最大的节点，这样可以更快地耗尽节点的能量，减少网络的生存时间，EEDBR缺乏链路质量指标，导致跳数增加，进一步减少网络生存期。REPBR和HUF随着网络中节点数量的增加而获得更稳定的网络生存期，这是因为下一个转发节点的选择是基于路由效益的，REPBR路由效益通过链路质量和剩余能量计算，平衡能量消耗，HUF利用最小跳数、剩余能量和链路质量，减少跳数转发、平衡能量消耗，因此REPBR的网络生存时间比HUF略短。

图6 生命周期对比

如图7所示，本文测量DBR、EEDBR、REPBR和HUF的能量消耗，结果表明，算法的能量消耗随着节点数量的增加而增加。HUF的能耗明显比DBR、EEDBR低，略低于REPBR。DBR没有任何能量因子，只利用深度信息来选择下一个转发节点，是不断增加能量消耗的主要原因，此外，冗余报文在DBR中传输时，也会产生较高的能量消耗。EEDBR比DBR能耗低，这是因为EEDBR不仅利用剩余能量和深度信息来选择下一个转发节点，还减少了报文的传输数量，以此均衡节点间的能量消耗。REPBR和HUF都具有较好的能量平衡能力，都利用了剩余能量和链路质量度量，可以平衡节点之间的能量消耗和最佳的链路质量，所以在网络初始阶段节点数为100、150、200时，两者的能量消耗几乎持平，然后随着节点数量的增加，由于REPBR没有对下一转发节点的跳数进行处理，故传输路径的长度增加，而HUF根据协议选择跳数最小的转发节点，根据路由效益选择全局最优路径，减少节点之间的转发，从而减少能量消耗，所以在节点数逐渐增加时，HUF的能耗略低于REPBR，具有更低的能量消耗。

图7 能量消耗对比

如图8所示，可以看出，HUF的端到端时延比REPBR、EEDBR、DBR低。这是由于HUF减少了源节点到汇聚节点之间的转发跳数，结合剩余能量和链路质量，选择了全局最优最短路径，从而减少整个端到端网络时延，总体性能优于DBR和EEDBR，特别是在网络密集，即网络中节点数量较多的情况下。随着传输节点的增加，DBR只依赖深度信息转发数据，具有更高的端到端时延，EEDBR基于剩余能量的数据包保持时间，但是如果第一转发节点的数据包丢失，接下来的保持节点转发数据包会造成相当大的延迟。REPBR具有良好的链路质量，但是对于邻居节点之间的最短路径选择，它并没有给出任何解决方案，因此，加入转发过程的节点数量随着节点数增加而增加，导致转发路径繁杂，跳数增加，进而增加了端时延。

图8 端到端时延对比

如图9所示，随着网络中节点数量的增加，HUF的数据包投递率总体上比DBR、EEDBR和REPBR要高。DBR获得的数据包传递率几乎相同，这是因为节点数量的增加，缺乏链路质量指标，所以候选节点的数量也会增加。另外，DBR是基于深度信息，并且是基于接收者的路由方式，故增加了不必要的转发，导致丢包概率高。EEDBR根据剩余能量来选择下一个转发节点，导致跳数增加，进而降低了数据包的传递率。REPBR利用剩余能量和链路质量来选择最短路径，但在高密度网络中，选择最佳转发节点的效率较低，导致数据包传递率相对偏低。在节点数目设置为150时，HUF的数据包投递率略低于REPBR，但是随着节点数量的增加，HUF获得了更高的数据包投递率，这是因为HUF在路由效益中考虑了链路质量和可靠的节能最短路径选择，有效地实现了数据包的成功传递。例如，在路由效益计算中，选择剩余能量最高、链路质量最好、路径传输最短的节点，可以平衡能量消耗，获得稳定的链路，保证数据包的转发。HUF算法选择最短路径，抑制不必要的转发，从而在合理的数据包投递率下减少转发的数据包总数。如图所示，节点数为400时，HUF比DBR、EEDBR、REPBR分别提高了约3%、10%、2%。

图9 包投递率对比

4 结束语

为解决水下无线传感器网络在节点不断移动和增加的情况下，节点转发不是最优最短路径、能量消耗不均衡、端时延较高等问题，本文提出一种基于REPBR跳数效用转发的改进路由算法，该算法选择下一个最优转发节点进行数据转发，与目前最先进的技术相比，显著提高了UWSNs的性能。实验结果表明HUF算法提高了路由效益，数据包传递率更高、端到端时延更低、网络生存周期更长和能量消耗更低。在未来的工作中，将考虑通过结合预计期望传输次数选择更合适的转发节点，进一步优化路由协议的性能。