基于链路期望寿命的高效路由算法
来源:用户上传
作者:
摘要：随着物联网的不断发展，低功耗有损网络被广泛应用于各个领域。针对低功耗有损网络中移动节点链路频繁切换导致的较大切换时延问题，提出一种基于链路期望寿命的高效路由算法LLE-RPL。该算法在构建网络拓扑结构时，根据节点自身属性与无线链路的生存时问选出最优父节点，有效避免了路由判据单一对网络性能造成影响。理论分析和仿真结果表明，提出的LLE-RPL算法能够有效地提高網络吞吐量，延长网络生命周期。
关键词：低功耗有损网络;路由算法;生存时间;移动
中图分类号：TP311 文献标识码：A
文章编号：1009-3044（2020）20-0064-02
近年来，随着物联网的迅速发展，低功耗有损网络（LowPower and Lossy Network，LLN）被广泛应用于医疗保健、军事指挥以及智慧城市等领域，成为当前学者的研究热点。LLN是由大量存储能力、处理能力以及能量受限的无线传感器节点组成的网络。LLN的链路具有不稳定性和有损性，存在高丢包率、低带宽、链路不稳定等问题，传统路由算法难以应用于LLN。为解决这一问题，国际互联网任务工程组在2012年提出一种基于IPv6的低功耗有损网络路由协议（Routing Protocol f'or LowP㈣er and Lossy Network，RPL）[1-3]。RPL路由协议有效地满足了低功耗有损网络的要求，但在实际应用中仍有一些亟待改进的问题，尤其是在节点移动的环境中。
目前，国内外学者针对RPL路由协议的研究取得了大量成果，研究主要集中于网络负载均衡、拥塞控制以及路由修复等方面。但研究主要是针对LLN中节点静态的环境，对于LLN节点移动环境中的路由技术研究较少。当前，针对LLN节点移动环境的研究，在网络性能优化方面仍需进一步提升。文献[4]提出了一种基于移动节点位置跟踪的路由协议。该协议是通过设计一种Corona机制，将网络划分为以根节点最大发射距离为半径的圆形区域，节点根据自身与根节点的距离，从而计算节点的位置坐标。该协议在快速找到替代父节点作为下一跳方面得到增强，但未有效解决切换延迟和路径断开时间较长等问题。文献[5]通过改进RPL协议中的溪流计时器，使路由协议支持节点移动的环境。该协议根据节点的移动速度来发送面向目的地的有向无环图信息对象消息（DODAG Information Ob-ject，DIO），且在组网过程中采用期望传输次数作为路由度量，从而降低网络的控制开销。该协议中节点选择的父节点并非最优，且路由度量过于单一，容易出现节点频繁切换父节点的问题。
1 RPL路由协议
RPL路由协议是针对LLN设计的距离矢量路由协议。该协议通过目标函数和度量集合共同构建面向目的地的有向无环图DODAG（Destination Oriented Directed Acyclic Graph，DODAG），然后根据路由度量和约束条件选择最优路径完成路由过程。RPL定义了三种控制信息，DODAC请求信息DIS（ DODAG Inf'ormati。n SoliCitation），DODAG信息目的广播对象消息DAO（ Destination Advertisement Object）和DODAG信息对象消息DIO。DIS用于向邻居节点请求DODAG信息，DAO用于构建上行路由，DIO用于通知有关DODAG的参数。
在构建DODAG时，Sink节点向邻居节点广播DIO消息。邻居节点根据接收到的DlO消息决定是否加入DODAG。如果决定加入，将Sink节点添加到自身的父节点集中，并返回Sink节点一个DAO消息。如果决定不加入，则不进行任何操作。Sink节点接收到DAO消息后会更新自己的路由表。该邻居节点再广播更新后的DIO消息到其通信范围内的节点，接收到DIO消息的节点决定加入DODAG后返回一个DAO消息，并更新自身路由信息，继续广播。以此类推，节点通过DIO消息决定是否加入DODAG中。如果一个节点收到多个DIO消息，会选择使自己Rank值最小的DlO发送节点作为父节点。如果未收到DIO消息的节点想加入DODAG，会主动向邻居节点发送DIS消息，当邻居节点收到DIS消息后会发送DIO消息进行邀请。重复上述过程，最终通过三种控制信息完成DODAC的构建。
2 LLE-RPL路由算法
2.1问题分析
通过对现有移动节点环境中的路由算法研究发现，在构建网络拓扑结构的过程中，节点选择最优父节点时忽略了与其备选父节点之间的链路生存时间[6]。当无线链路生存时间较低的备选父节点被选为最优父节点时，会导致节点频繁地切换父节点从而引起网络震荡。针对这一问题，本文提出一种基于链路期望寿命的高效路由算法LLE-RPL，并对其性能进行仿真对比分析。
收稿日期：2020-03-25
基金项目：2019年重庆工商职业学院科学研究项目——面向物联网的低功耗有损网络路由技术研究（项目编号：NDYB2019-13）
作者简介：秦晓琴（1989-），女，讲师，工程师，硕士，主要研究方向为无线传感器网络、路由技术等。
LLE-RPL路由算法中根节点也被称之为Sink节点，主要用于汇聚子节点上传的数据信息。移动节点主要用于产生数据且将所产生的数据向上转发至Sink节点。
为了便于分析，在LLE-RPL路由算法中进行如下假设。
（1）网络中Sink节点不具有移动性，其他节点均可移动。
（2）网络中可移动节点均具有相同的感知覆盖半径、物理结构和特性，可感知自身位置信息。
（3）网络中可移动节点间相互独立，无相互十扰，速度和方向不会产生突变。
2.2算法设计
针对节点移动环境中LLN现有路由算法所存在的问题，LLE-RPL算法在选择最优父节点时，考虑了LLN中节点由于移动特性离开其邻居节点通信范围的时间，即两者之间无线链路生存时间（Link Expiration Time，LET），有效避免子节点因期望寿命过低引起的频繁切换，从而最大化延长网络的寿命。下面以节点m为例，其最优父节点选择的具体操作步骤如下： 步骤1：初始化网络后，节点m将自身的位置信息、移动速度等度量信息添加到DIO控制消息的选项字段中，并且向邻居节点广播该消息;
步骤2：节点收到邻居节点m广播的DIO控制消息后，获取消息中携带的相关路由信息，计算两节点之间的链路生存时间。该节点选择生存时间长的链路进行数据传输，从而有效降低网络延迟，减小路由维护成本。根据文献[6]，LET的计算步骤如下：
（1）假设当前时间为t，节点m的速度为Vm，位置为Sm，则经过时间△t后，节点m的位置可通过公式（1）得到：
Sm+（t+△t）=Sm（t）+Vm△t
（1）
（2）若是节点n的速度为Vn，位置为Sn，则m，n两节点的相对速度以及相对位置如公式（2）和公式（3）所示：
V（m，n）（t）=Vm（t）-Vn（t）
（2）
S（m，n）（t）=Sm（t）-Sn（t）
（3）
（3）通过公式（2），（3）计算出节点m，n位置后，则经过时间△t后，节点m，n的相对位置通过公式（4）可知：
D（m，n）（t+△t）=|S（m，n）（t）-V（m，n）（t）△t|
（4）
通過判断两点的相对位置D（m，n）（t+△t）是小于节点m的通信半径r，从而得出链路最大持续时间LET。
步骤3：节点n得到其邻居节点m的链路期望寿命后，通过公式（5）计算自身与邻居节点的路由度量值（metric）：
metric=α（ETX（m，n》+（1-α）LET（m，n）
（5）
式中，α为阈值，根据网络场景进行设定。ETX为两节点之间的重传次数，该值由特定的测试包获得。路由度量值越大则说明两节点之间的传输代价越大，反之越小。因此，选择路由度量值最小的邻居节点作为最优父节点。
3仿真分析
本文选用文献[4]和文献[5]所提路由算法进行对比分析。在300m*300m的仿真区域内，分别构建节点数为10、30、50、70和90的LLN且节点随机分布，其中根节点为静态节点，数量为1。仿真时间为3600s。
如图1所示，三种算法的网络平均寿命随着LLN网络规模的不断扩大而降低，但本文所提算法相较于其他两种算法较高。其主要原因在于，节点选择最优父节点时，综合考虑了节点间的期望传输次数和链路生存时间，避免了节点选择无线链路质量差和链路生存时间短的节点作为父节点。
图2表明，根节点的吞吐量随着节点数量的增加逐渐加大，而本文所提路由算法相较于其他两种路由算法，根节点的吞吐量较高。其主要原因在于：网络组网时，节点根据无线链路的期望寿命进行父节点的选择，从而使得网络能够最大限度地传输数据流量。
4结束语
针对低功耗有损网络中移动节点链路频繁切换导致的较大切换时延问题，提出一种基于链路期望寿命的高效路由算法。在构建网络拓扑时，综合节点属性与无线链路的生存时间选出最优父节点，使得网络平均寿命和根节点平均吞吐量得到提升。
参考文献：
[1] Winter T.RFC6550 RPL： routing protocol for low power andlossy networks[S].USA： Internet Engineering Task Force，2012.
[2] THUBERT P.Objective function zero for the routing protocolfor low-power and lossy net works： RFC 6552[S]. Geneva：IETF，2012：1-14.
[3] Liu X， Sheng Z， Yin C. et al. Performance analysis of RoutingProtocol for Low power and Lossy Networks （RPL） in largescale networks[J]. lEEE Intemet of Things Journal，2017，4（6）：2172-2185.
[4]O. Gaddour. A. Koubaa. R. Rangarajan， et al. Co-RPL： RPLrouting for mobile low pmver wireless sensor networks usingCorona mechanismLCl. 2014 9th lEEE International Sympo-sium on Industrial Embedded Systems. Pisa，2014：200-209.
[5] Fotouhi H，Moreira D，Alves Mario. mRPL： Boosting mobilityin the Internet of Things[J]. Ad Hoc Networks. 2015. 26：17-35.
[6]钟声.基于分簇的无线光通信网络动态拓扑控制算法研究[D].西安电子科技大学，2018.
【通联编辑：代影】
转载注明来源:https://www.xzbu.com/8/view-15300108.htm
