一种基于轮转优先级的机会路由算法

杨 磊，谢师丹，曹 歌，高学健

(哈尔滨工程大学 信息与通信工程学院，哈尔滨 150001)

近年来，随着对海洋的探索研究和传感器技术的发展，水下无线传感器网络(UWSN)技术应运而生[1].UWSN由可变数量的传感器节点、通信链路及目的节点组成，节点可协同组网并以声通信方式进行通信，广泛应用于污染监控、海洋信息采集、军事监测等众多水下场景[2].路由技术作为传感器网络进行数据分组传输的基础，是传感器网络工作的关键之一，但由于水下通信环境的复杂性，机会路由被提出作为一种方法[3]，以减轻一些使其不可靠的声学信道特性，如高衰减和高延迟.水下网络中的节点使用不易更换且充电的电池来提供电力能源[4]，所以节约能耗、延长网络生存周期是设计UWSN路由协议的主要关注点.

然而，鉴于静态网络拓扑和当前机会路由协议没有任何机制来轮转候选节点的优先级[5]，一些节点被高度使用，能耗不均衡，缩短了网络生命周期，如DBR[6]、VBF[7]和VAPR[8]等路由算法；此外，未采用合理的传输协调机制，会降低数据分组传递率，影响网络可靠性.综上所述，对UWSN的机会路由技术进行研究具有很大实际意义.针对以上问题，从节能和传递率的角度对机会路由的候选节点集的选择和协调展开研究，结合节点的剩余能量和距离源节点深度差构建评估最优转发节点的适度值函数，以此来判断邻居节点是否作为候选节点，均衡了节点能耗，延长网络生存时间，采用ACK传输确认机制来协调分组转发，避免多个节点同时转发分组而出现冗余和碰撞，提高分组传输率，增强了传输可靠性.

1 传感器网络模型

1.1 传感器结构

图1所示的是EDOR算法网络模型示意图，主要包括水下传感器节点、汇聚节点，可将节点集定义为N={n1,n2,…,nN}.水面部署多个声纳浮标，其作为汇聚节点进行水下节点数据收集，最终通过无线电信道将信息发送到接收基站[9].水下区域随机部署若干个水下传感器，最大传输距离R，节点随机部署在所监控的范围，将其监测获取到的信息通过与邻居节点协作转发到汇聚节点或水面浮标.与水声定位技术相比，深度信息的获取要容易得多，从本身到水面的垂直距离，用水下传感器压力表而测得.

图1 EDOR算法网络模型示意图Figure 1 Schematic diagram of EDOR algorithm network model

1.2 水下信道模型

在水下声信号的通信过程中，假设不考虑水下多径效应的影响，传输距离为d，传输频率是f的路径衰落可以表示为：

A(d,f)=A0dka(f)d

(1)

其中：A0是标准化常数，k作为扩频因子用来描述扩散的几何形状，对大多数情况而言，圆柱形扩散k取值为1，球形扩散k取值为2，实际场景中k=1.5.a(f)是声波吸收因子，可通过经验公式定义为：

2.75×10-4f2+0.003

(2)

式(1)路径损耗可以表示为：

10 logA(d,f)/A0=k×10 logd+d×10 loga(f)

(3)

式(3)中k×10 logd表示扩散损耗，d×10 loga(f)表示吸收损耗.d单位是km，f单位是kHz，故a(f)单位是dB/km

传输距离为l的信道中平均信噪比RSN(Signal to Noise)估计为:

(4)

其中：Eb为单位比特的平均传输能量，N0是高斯白噪声功率谱密度.通过瑞利衰落表征尺度衰落[10]，则信噪比满足下面的概率分布：

(5)

则误码率为：

(6)

其中：pe(X)是信噪比下的误码率.

我们使用广泛应用于声学调制解调器的BPSK(二进位相移键控)调制[11].在二进位相移键控中，每个符号携带1bit[12].如果传输距离是d时，出现一个误比特的概率pe(d)表示为：

(7)

最后，我们可以估计任意一对距离为l的节点传输一个m比特数据分组的传递概率p(d,m)为：

p(d,m)=[1-pe(d)]m

(8)

2 多因子候选集构建策略

2.1 局部网络信息获取

信标机制作为局部网络信息获取方式，是建立候选节点集的重要技术[13]，通过信标机制得到建立候选节点集的所需信息.为了及时得到传感器节点的相关信息，每个水下传感器节点周期性地广播信标分组.信标消息的分组格式如图2所示，主要包括发送节点的相关信息.消息类型字段用来区分信标数据包是信标信息还是数据信息.

图2 信标消息分组格式

2.2 候选节点预处理机制

候选节点预处理机制是先从源节点的邻居节点中选择一个合适的子集作为准候选节点集并对其中的节点定义转发优先级.如i为一个传感器节点，Ni为它的相邻表即邻居节点集，浮标作为目的节点接近于水面，源节点从邻居节点集Ni中选择距离水面更近的一跳邻居节点来建立准候选节点集φ.

假设节点j∈Ni，将它的水压值表示为depth(j).对应地，节点i的水压值表示为depth(i).水压值与距离水面距离相关，距离水面越远水压值则越大.节点i与节点j∈Ni的水压差值Pj的计算由式(9)所示.当Pj>0，则节点j加入ψi集.

Pj=depth(i)-depth(j)

(9)

当准候选节点集建立完成后，结合节点剩余能量、传递率以及与源节点之间的深度差构建适度值Fit.节点j∈φ的适度值为Fitj，其定义为：

(10)

准候选节点集φ中的节点参考适度值大小进行优先级排序.如果适度值越高，转发优先级(ρ)就会越高.ρ值越小，优先级就会越高.

2.3 基于链路状态的候选集选择算法

将规定的数据分组传递率表示为γ，候选节点集ψi内全部节点保持的数据分组传递率为Pd，其定义为：

(11)

式(11)表示i节点数据分组传输成功的概率，其中|ψi|表示ψi内包含节点的个数，p(dk,m)表示从节点i到节点k∈ψi的数据分组传递率.则1-p(dk,m)为传输不成功的概率，则全部节点都传输不成功的概率可表示为：

(12)

最开始ψi为空，Pd设置为0.首先，在准候选节点集内选择第一个节点，也就是优先级ρ=1的节点，接着再计算Pd，同时判断其是否满足Pd>γ.假如不满足，该节点就被加入候选转发节点集ψi.然后继续更新Pd，并将ρ值加1，直到其满足条件Pd>γ，最后构建成ψi.

3 基于可靠性的中继算法

3.1 利用ACK的协调流程

候选集的传输协调是机会路由协议中的挑战性问题之一[14].通过基于可靠性的中继算法候选转发集来协调下一跳候选节点的数据分组转发操作.候选转发节点集构建ψi完成后，源节点确定了候选转发节点，将这些节点的ID和位置信息以及优先级顺序列表嵌入到分组头部，将数据分组进行广播发送.节点收到数据分组后检查其头部信息确定自身在转发节点列表中后，根据优先级排列顺序，确定比自身优先级高的节点并设置侦听定时器来侦听来自源节点的控制命令.

如图3所示是控制分组协调示意图，侦听定时器是候选转发节点负责监听源节点发送转发命令的等待时间.在侦听定时时间内，如果节点接收到来自上一跳节点的转发命令，则向上一跳节点回复一个ACK确认接收，同时立即将数据分组进行转发，上一跳转发节点收到ACK确认后则不再向其他节点发送转发命令；如果若上一跳转发节点未收到ACK确认，上一跳转发节点应重新发送一次转发命令，上一跳转发节点仍然没有ACK确认回复，则放弃此节点，向次优先级节点重复上述操作.如果直至侦听时间结束，候选转发节点未收到任何发送指令，则将自身持有的数据分组丢弃.

图3 控制分组协调示意图Figure 3 Schematic diagram of control group coordination

优先级为ρ的候选转发节点，侦听定时时间可定义为：

(13)

其中：υ为水下声传播速度，约1500 m/s，Dmax是当前节点距离转发候选节点集里全部节点的最远距离.

3.2 机会定向转发

机会定向转发负责将网络节点采集的信息进行转发，为减少冗余分组，采用贪婪转发方式.将转发所需要信息封装在数据分组头部，如图4所示，发送节点ID用来标识发送节点；发送时间是用来通过TOA技术计算发送节点与发送范围内节点的最远距离；下一跳节点ID包括进行贪婪转发所需要的所有节点ID，以数组的形式进行存储；目的节点地址表示最终接收数据分组的节点的物理地址，如水面汇聚节点和浮标节点.

图4 数据分组格式Figure 4 Data packet format

如图5所示为该协议进行数据分组转发的整体流程图.根据路由协议的转发示意图和整体工作流程图.

图5 协议数据分组转发流程图Figure 5 Flow chart of packet forwarding of protocol data

4 仿真结果与分析

4.1 仿真环境

本文基于离散事件仿真平台OMNeT++，通过搭建仿真环境对RPOR路由算法进行仿真验证，并与DBR算法进行对比分析.从在仿真实验中，水下监测区域为，将传感器节点随机放置在所用监测范围.为了部署声纳浮标，我们将监测范围表面积划分为四个正方形的网格，边长为500 m.在每个方格中，随机部署16个声纳浮标，设置节点数为150和350的两个场景，传输半径为250 m，带宽20 kbyte/s，分组产生率为0.01 packet/min，传输功率和接收功率分别为4W和0.65W，数据分组大小为100 byte，分组传递率设置为0.9，MAC层使用CSMA(Carrier-sense Multiple Access)多载波监听接入协议[15].

4.2 结果分析

本文主要从活动节点数率、分组传输率和平均端到端时延三个方面来验证算法的有效性.活动节点数率为网络中剩余能量不为零的节点个数和网络中总节点个数比值，用来衡量网络生存时间，值越高能耗就越低，生存时间越长.数据分组传输率指的是接收节点收到的数据分组数量与发送节点产生的数据分组数目的比值，反映了网络可靠性，体现了路由算法分组处理效率.平均端到端时延为数据分组从源节点的网络层到目的节点的网络层所需要的平均时间，体现了路由算法的有效性，从侧面反映网络拥塞程度.

4.2.1 活动节点数率

图6表示了节点数目不同的两个场景下不同时间段的活动节点数率.RPOR算法显著提高了活动节点数率，在节点数为350的场景下，当网络运行时间为25 h时，活动节点数量率提升最高，相比于DBR算法提高了一倍，延长了网络的生存周期.这是因为基于轮转优先级的机会路由协议RPOR在选择候选转发节点集时结合节点的深度、剩余能量和链路质量信息构建适度值函数来选择候选节点，通过适度值的大小来规定候选转发节点的优先级，每次转发都会考虑节点所剩余的能量，使得能量消耗比较均衡.

两图对比可知，节点数较多的场景下活动节点数率下降较快，表明在节点密度大时节点能耗增大.原因在于：数据分组转发过程中，路由协议算法采用广播传输，节点数增多时，为使邻居节点收到信息，便需要更大的发射功率即消耗更多的能量，同时出现冗余分组的概率增大，产生拥塞，则会导致网络能量的消耗加快.

4.2.2 数据分组传输率

如图7表示数据分组的传递率.随着时间的增长，数据分组传递率降低，这是因为网络运行时间越久，节点的剩余能量越少，活动节点数目减少，从而导致传递率降低.在高节点密度下，RPOR算法的数据分组传输率较DBR算法最高可提升1.2倍.原因为：一方面，RPOR选择候选转发节点时考虑节点的深度、剩余能量和链路质量信息，节点的能量消耗均衡，有助于多跳传输；另一方面，RPOR算法在协调候选解节点转发时采用了ACK确认机制改广播转发为单跳传输，减小了冗余分组，ACK机制的主要作用确保有效传输，提高可靠性，从而取得高的数据分组传递率.两图对比可以看出，在节点高密度环境下，RPOR算法传递率提高更多，这是由于每次传输考虑了节点的剩余能量，节点能量消耗均衡，节点数目越多利于多跳传输.

4.2.3 平均传输时延

图8显示了算法的平均传输时延.RPOR算法的传输时延性能不优于DBR算法，原因如下：首先，RPOR选择候选节点集时使用周期信标获得邻居节点的深度和剩余能量信息，增加了一次信标传输；其次，在协调候选转发节点时，通过发送REQ命令使转发节点进行分组发送，转发节点还要回复ACK确认，也增加了一次传输.这就使得RPOR算法的传输时延较大.两种算法的平均传输时延随着仿真时间变长而逐渐增加，这是因为随着仿真的进行，活动节点数减少.节点数目增多导致拥塞概率增大，则会导致花费更多的时间判断节点的优先级，从而增加了传输时延.

图6 活动节点数率Figure 6 Number rate of active nodes

图7 数据分组传输率Figure 7 Data packet transmission rate

图8 平均传输时延Figure 8 Average transmission delay

5 结 语

针对水下传感器网络中机会路由节点能量消耗不均衡、可靠性低的问题，提出了基于轮转优先级的机会路由算法，并通过OMNeT++仿真平台进行仿真验证.该算法在选择候选转发节点时，结合节点的剩余能量和距离源节点深度差构建评估最优转发节点的适度值函数，均衡了节点能耗，延长了网络生存时间，采用ACK传输确认机制来协调分组转发，避免了冗余和碰撞，增强了传输可靠性.仿真结果表明对比于DBR算法，基于轮转优先级的机会路由算法明显提高了活动节点率和分组传输率，但相对增加了平均传输时延，未来可以针对传输时延进行优化.