基于多目标的管道物联网无线路由算法

刘 苗, 姚 荣, 钟晓曦, 霍卓苗, 孙振兴,3

(1. 东北石油大学秦皇岛校区 电子信息工程系, 河北 秦皇岛 066004； 2. 东北石油大学 物理与电子工程学院, 黑龙江 大庆 163318； 3. 东北大学 计算机科学与工程学院, 沈阳 110006)

0 引 言

随着5G技术的日益成熟, 物联网在油气长输管道中的应用也在不断推广[1]。石油和天然气是各国重要的战略能源, 由于油气长输管道运输的距离较长, 面临恶劣环境的几率较大, 所以长距离运输原油、成品油和天然气出现泄漏的几率也很大[2-3]。在运输过程中, 一旦出现泄漏, 后果非常严重。目前石油天然气行业主要采用有线与无线通信相结合的方法对油气管道进行监测, 然而有线通信存在基础设施容易受到破坏以及安装成本高等问题, 难以在石油天然气管道监测中大范围应用[4-7]。油气管道物联网可以在恶劣环境下实现网络自组和重组, 可以铺设在环境较恶劣、 地区较偏远的输送管道, 全天不间断地实施监测, 对故障进行及时报警, 实现输油输气管道的泄漏监测。无线传感器网络作为物联网的底层信息获取系统, 具有很高的灵活性、 组织性以及成本低廉的特点, 其在监测油气管道泄漏领域应用价值巨大[8-9]。

认知无线电(CR： Cognitive Radio)是基于时空维度频谱可用性管理和配置其传输参数的最好候选技术。认知无线电在保证授权用户(主用户)频带不受非授权用户(次用户)干扰的条件下, 通过允许非授权用户共享授权用户频带可以使非授权用户获得新的频谱资源[10-12]。可以考虑引入认知无线电技术优化油气管道无线传感器网络性能。但由于油气管道物联网中传感器能量等自身限制, 油气管道物联网中路由协议变得至关重要, 关系整个网络的能耗以及端对端延时, 在一定程度上决定了网络的寿命。大多传统的无线传感器网络路由协议采用固定路由线路的方式进行数据路由, 即在每次传输前确定了传输路线[13]。但在无线环境中, 每条无线链路都具有不稳定性, 链路的质量随着时间和空间的变化而变化, 一旦在传输过程中路由线路中的无线链路发生变化, 很有可能造成网络中数据传输失败以及增加端对端延时。

针对上述问题, 机会路由协议被提出。机会路由协议通过在多个候选节点和路线中选择出最适合的传输中继节点。由于每一跳的转发节点的选择增加, 数据传输的链路的稳定性得到了保障, 从而提高了数据传输的成功率[14-15]。然而, 机会路由在油气管道物联网中的实际应用中还存在很多挑战, 包括如何选择候选转发节点, 以及如何对网络中能效与延时的优化等。

笔者根据油气管道物联网的能效和数据传输延时需求, 提出一种基于多目标优化的管道物联网路由算法。该算法解决了油气管道物联网中网络能量使用不均和延时的问题。综合考虑节点剩余能量和节点间距离, 尽可能均衡网络中的能量使用, 减小网络中能量使用不均现象, 同时保证网络中数据传输的端对端延时。利用笔者提出的协议能在不影响网络性能的情况下, 提高了油气管道物联网的寿命。

1 系统模型

网络模型中的每个节点都具有单独的编号j(j∈[1,m]), 并且节点单跳的传输距离为1～100 m。笔者以图论模型对网络进行描述, 即G=[U,K], 其中U表示网络中所有的节点集合,K表示网络中所有能直接连接的链路。令x,y∈U表示一个网络中任意两个能直接连接的节点, 则(x,y)∈K即表示网络中任意两个节点直接连接的链路。在每条链路上都具有一个加权值p, 表示节点间链路成功传输的概率, 并且由于信道衰减以及噪音干扰等原因, 成功传输的概率是可能发生变化的, 但在本文中假设每条链路成功发送的概率是固定的。对节点, 在初始时, 网络中每个节点的能量为初始值E0, 运行后节点的剩余能量为Eres, 而汇聚节点的剩余能量为无穷。每传输一次数据包消耗的能量为Et, 接收一次数据包消耗的能量为Er。

发送节点在传输中的通信过程为： 当有数据需要发送时, 发送节点向周围节点广播RTS(Ready to Send)信息, 等待周围节点的CTS(Clear to Send)回复确定候选转发节点的信息, 然后选择优先级最高的节点发送信息。当候选节点中有节点接收转发数据后, 会发送ACK(Acknowledgement)信息, 发送节点接收ACK信息后确定完成转发任务, 其能量消耗公式以及传输k字节消耗的能量计算公式如下[15]

Escum=NEt+Est+EACKr+SSUMEcr

(1)

Et=kεR2+εk

(2)

其中Escum为发送节点在单跳完整发送过程中的能量消耗；N为成功传输数据时发送包的次数；Et为发送一次数据所需的能量；Est为发送RTS消息消耗的能量；EACKr为接收ACK消息时消耗的能量；SSUM为备选转发节点的总数；Ecr为接收CTS信息的能量消耗；k为数据包大小,ε为每字节在单位面积传输消耗能量,R为传输距离。通过式(2)可得出在一跳传输的过程中发送节点消耗的能量。

候选转发节点根据能量消耗模式的不同可以分为3种类型, 这3类候选转发节点在传输中的通信过程描述如下。

1) 被选中为转发节点的候选节点。这类节点通信过程为： 首先是接收发送节点的RTS信息, 结合自身信息自动被选中为候选节点, 被选中后会向发送节点发送CTS信息, 信息内容为自身的信息, 一旦被发送节点确定为最高优先级候选节点, 开始接收转发数据, 接收成功后向周围广播ACK信息, 然后等待, 一旦接收到其他节点的ACK信息, 就将自己的优先级P和接收到的其他节点的ACK中的优先级P进行比较, 如果低于其他节点ACK中的优先级P, 则丢弃该数据包, 反之则确定自己为转发节点, 成为下一跳传输的发送节点。

对被选中转发数据的转发节点能量消耗计算如下

Ecumc=Er+Esr+Ect+EACKr+EACKt

(3)

Er=εk

(4)

其中Ecumc为被选中的转发节点能量消耗总和；Esr为接收RTS消息消耗的能量；Ect为发送CTS消息的能量消耗；EACKt为发送ACK消息的能量消耗。通过式(3)可知在完整的发送过程中转发节点的能量消耗。

2) 候选转发节点未被选中转发节点但却意外接收转发数据的节点。这类节点通信过程与被选中候选转发节点基本一致, 不同的是在完成一跳转发过程后丢弃转发数据, 不进行下一步动作。该类候选转发节点的能量消耗计算如下

EcumN1=Er+Esr+Ect+EACKr+EACKt

(5)

其中EcumN1为未被选中但接收转发数据的候选节点在转发过程中的能量消耗。

3) 候选转发节点未被选中为转发节点, 也没有接收到转发数据。这类节点在发送节点发送数据前与其他候选转发节点通信过程一致, 但在等待接收转发数据时, 一旦接收到被选中转发节点发送的ACK消息, 立即结束此次单跳通信的任务, 重新等待下一次任务。该类候选转发节点的能量消耗计算如下

EcumN2=Esr+Ect+EACKr

(6)

其中EcumN2为未被选中且没有接收转发数据的候选节点在转发过程中消耗的能量。

至此, 在一次完整的发送过程中各个位置节点的能量消耗确定, 通过该模型可以确定在每次传输数据后节点的剩余能量。

网络中一旦节点需要发送数据包, 则需要向周围节点发送RTS探测包, 探测包中包含当前节点到目标节点的距离Ds以及目标节点的位置。如果周围节点处于空闲状态, 接收到其他节点发送的RTS后, 需要确定自身的状态是否适合转发数据, 需要确定的参数是自身的剩余能量Eresi以及自身距离目标节点的距离Di, 当参数满足

Di

(7)

Eresi≥Eth

(8)

说明该节点适合转发数据。式(7)表示筛选出周围距离汇聚节点更近的节点, 保证数据向前发送； 式(8)是保证选中的节点不会因为剩余能量过少而导致传输失败, 式(8)中的Eth为至少完成接收和转发数据所需最小能量, 其由在数据发送过程中发送节点的最多发送次数所决定, 因此可由

Eth=CEt+Ecumc

(9)

计算得到。式(9)由两部分组成, 第1部分表示假设选中后在下次传输过程中传输数据所需的能量, 其中C为在通信过程中发送节点发送数据包的最大次数；Eth为发送一次数据所需的能量； 在发送了C次后如果还没有发送成功, 节点将自动丢弃该数据包, 该操作能减少节点的无效能量消耗; 第2部分Ecumc为在本次传输数据过程中接收数据所消耗的能量。

满足上述要求的节点向准备发送数据的节点发送一个CTS包, 该包中包含节点的地理位置、 节点当前剩余能量Eresi以及距离汇聚节点的距离Di。并且不再接收其他节点发送的RTS消息, 以此保证节点不会被多个节点选中作为预备的转发节点。发送节点在接收到各个备选转发节点回复的CTS消息后, 根据备选转发节点的信息, 将节点剩余能量以及节点与汇聚节点的距离进行归一化处理, 如下

(10)

(11)

将式(10),式(11)做差后加1可得

(12)

其中Pi为候选节点i的转发优先级。

2 基于多目标优化的管道物联网低能耗无线路由算法

2.1 发送数据策略

传统的发送策略是直接向优先级最高的节点发送数据, 直到多次传输失败后才改向优先级第2高的节点发送。这可能造成发送等待时间更长, 传输延时更大。为此, 笔者提出了一种新的发送策略, 具体描述如下。

1) 首先在发送前确定最多发送次数C, 设定发送节点在发送数据C次后, 如果还无法将数据成功发送, 节点将丢弃该数据包；

2) 根据不同节点优先级以及发送节点最大传输次数C, 计算发送节点向每个预备节点转发数据的次数。

发送节点向预备转发节点发送数据的次数如下

(13)

其中Ssum为被选中的备选中继节点的总数,Ni为发送节点在发送阶段向预备转发节点i的最大发送次数,Pi为候选节点i的转发优先级。通过式(13)可计算出发送节点针对各个预备转发节点的最大发送次数, 优先级越高的节点被发送节点发送数据的次数越多, 这不仅减少了额外转发次数, 而且减少了能量损耗, 同时还在一定程度上减少了端对端时延。

候选节点集选择算法。

步骤1) 设定集合M为候选转发节点集合,Ni为节点i的相邻节点集合, 候选转发节点优先级集合P, 初始时令Ni、M、P为Ø。

步骤2) 当源节点为i时, 对节点j, 当节点j距离节点i的距离D(i,j)≤R时, 则认为节点j为节点i的相邻节点, 添加入集合Ni。其中R为节点i最远传输距离。

步骤3) 对源节点i的相邻节点j, 如果其距离目标节点的距离Dj和当前剩余能量Eresj满足式(7),式(8)时, 节点j则被选中为候选转发节点, 并加入集合M。

步骤4) 对被选中为候选转发节点j, 利用式(12)计算出候选节点j转发优先级pj, 并将优先级pj加入优先级集合P中。

步骤5) 循环步骤2)～步骤4), 直至选出所有候选转发节点结束。

该算法中存在一个长度为所有相邻节点数量的循环, 并且最多保存所有的相邻节点, 所以通过分析可知算法的时间和空间复杂度均为O(M), 其中M是所有相邻节点的数量。

2.2 网络通信过程

先将网络初始化, 建立网络是通过汇聚节点向网络中的节点广播唤醒网络中节点, 并且告知其他节点汇聚节点的位置。而其他节点当收到汇聚节点的唤醒消息后, 将通过比较与汇聚节点位置, 将自身与汇聚节点的距离计算出后进行存储, 等待后续使用。此外, 网络中各个节点在初始化时还需要计算自身剩余能量并存储, 在每次完整的数据传输中, 参与的节点包括： 选入的预备转发节点、 选中的转发节点、 发送节点和接收节点, 这些节点都需重新更新计算自身的剩余能量。

3 算法仿真与分析

3.1 仿真参数

为了试验验证笔者提出的路由协议有效性, 采用Matlab 2018a版本作为仿真平台, 对所提协议的网络性能进行评估。网络搭建在长200 m, 宽20 m的区域内, 中继节点随机分布在20×200 m2的范围中, 每个节点都处于面积为1×1 m2小格的节点上, 保证每个节点的坐标已知。建立坐标系, 令区域左下角顶点为原点, 发送节点坐标位于(200,20), 汇聚节点坐标(0,20)。

3.2 节点出度对算法的影响

本次试验研究的重点是在相同的传输距离以及中继节点数量的情况下, 不同的节点出度对网络生存周期的影响, 根据改变网络传输距离作对比试验, 找出在不同传输距离的最优节点出度。将传输距离设定为30 m,35 m,40 m,45 m, 中继节点数设置为110。

从图1中可以看出, 节点出度的增加降低了在不同传输距离的中继节点的网络寿命。这是由于笔者提出的算法中候选传输节点的选择是通过优先级进行选择, 候选转发节点的优先级越高被选中作为转发节点的概率越大。而当扩大节点出度时, 增加的候选节点的优先级必定是小于未扩大前选择节点的优先级, 在一般情况下, 数据都是传输给优先级较大的节点, 新增加的节点是大概率不能参与传输过程, 所以无法提高网络寿命。

3.3 网络传输距离对算法的影响

实验是在相同节点出度以及中继节点数的情况下, 研究不同传输距离对网络寿命的影响。对比不同中继节点数量和传输距离对网络寿命的影响。中继节点数量分别被设置为100,110,120, 节点出度设置为4。

从图2中可以看出, 在传输距离小于40 m时, 随着传输距离的增加, 网络寿命先保持不变或增加, 而在传输距离大于40 m后, 网络寿命随着传输距离的增加而减少。这是由于在传输距离小于40 m时, 增加节点传输距离时, 减少传输跳数所减少的能量消耗大于增加由于传输距离而增加的传输能量消耗, 而传输距离大于40 m后, 减少传输跳数所减少的能量消耗小于增加由于传输距离而增加的传输能量消耗。通过分析图2中数据可以得出, 在传输距离为30～40 m之间得到了网络寿命的最大值。

3.4 平均端对端延时比较

将笔者提出的基于多目标优化的管道物联网低能耗路由算法与上述的经典的ExOR(Extremely Opportunistic Routing)算法和节能机会路由算法REOR(Residual Eenergy based Opportunitic Routing)进行在平均端对端延时的对比试验, 在相同的中继节点数量的情况下, 随着传输距离的增加, 对比各个协议平均端对端延时。本次试验的中继节点数量设置为110, 出度设置为4。

如图3所示, 单项比较可知, 网络端对端延时随着传输距离的增加而减少, 这是由于当传输距离增大时, 将大大减少网络传输跳数, 从而降低网络端对端延时。横向对比可以发现, 笔者提出的算法端对端平均延时远低于REOR协议, 高于ExOR协议。通过前文的实验可知在R=35 m时, 网络寿命最大, 此时笔者提出的协议比REOR协议延时大约低42%, 同时比ExOR协议延时高约28%。这是由于REOR协议仅考虑传输过程中节点剩余能量, 没有考虑网络端对端延时, 而相反ExOR协议仅考虑候选节点到目标节点的距离。实验表明, 笔者提出的算法端对端延时比ExOR协议略高, 但是对比REOR协议能发现笔者的协议能有效的降低网络的延时。

图3 平均端对端延时比较Fig.3 Average end-to-end delay comparison

4 结 语

笔者提出的多目标优化路由算法针对多管道线性传感器网络的应用场景进行设计, 并且路由算法能对网络的能量进行均衡, 延长网络的使用寿命, 此外, 本算法还能降低无线传输跳数, 在减少能量消耗的同时降低网络延时。下一步, 将尝试把认知无线电和能量采集技术引入油气管道物联网, 提高无线频谱利用率, 进一步提高油气管道物联网的可靠性, 保障国家战略资源的安全运输。