高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

用于物联网的RPL节能负载均衡方法

, 

上一篇

下一篇

张虫金, 余欣. 用于物联网的RPL节能负载均衡方法[J]. 西南大学学报（自然科学版）, 2022, 44(9): 156-167. doi: 10.13718/j.cnki.xdzk.2022.09.016
引用本文: 张虫金, 余欣. 用于物联网的RPL节能负载均衡方法[J]. 西南大学学报（自然科学版）, 2022, 44(9): 156-167. doi: 10.13718/j.cnki.xdzk.2022.09.016
shu
ZHANG Chongjin, YU Xin. A New Load Balancing Method of Routing Protocol for Low Power Lossy Network for IoT[J]. Journal of Southwest University Natural Science Edition, 2022, 44(9): 156-167. doi: 10.13718/j.cnki.xdzk.2022.09.016
Citation: ZHANG Chongjin, YU Xin. A New Load Balancing Method of Routing Protocol for Low Power Lossy Network for IoT[J]. Journal of Southwest University Natural Science Edition, 2022, 44(9): 156-167. doi: 10.13718/j.cnki.xdzk.2022.09.016
shu

用于物联网的RPL节能负载均衡方法

  • 电子科技大学成都学院，计算机学院，成都 611731

  • 基金项目: 四川省重点研发计划项目(2020YFG0287)
详细信息
    作者简介:

    张虫金，硕士，实验师，主要从事计算机科学与技术研究 .

  • 中图分类号: P391

A New Load Balancing Method of Routing Protocol for Low Power Lossy Network for IoT

  • School of Computing, Chengdu College of University of Electronic Science and Technology, Chengdu 611731, China

  • 摘要: 针对物联网中低功耗有损网络路由协议节点间能量不平衡问题，该文提出一种用于物联网的RPL节能负载均衡方法. 该方法包含5个步骤：DODAG构建、最优网格头选择、最优父节点选择、向下路由和数据转发. 构建DODAG，该过程从根节点向其他节点传输DIO消息. 并根据与根节点的距离构建网格，在每个网格中使用重启随机游走算法选择最优的网格头节点，并处理数据传输过程中的重载条件. 设计斑点鬣狗优化算法优化目标函数，并用适合度函数从多个指标进行估算，最终选择最佳父节点来路由数据包. 构建向下路由绘制网络内任何节点和根/宿之间的路径，并向根发送数据. 实验结果表明，该文所提方法能够实现物联网低功耗有损网络路由低丢包和高负载均衡的数据传输，且性能优于其他方法.
    Abstract: Aiming at the problem of energy imbalance between the nodes of network routing protocol caused by low power consumption in the Internet of Things, this paper proposed a RPL energy-saving load balancing method for the Internet of Things. This method consists of five parts: DODAG construction, optimal grid header selection, optimal parent node selection, downward routing and data forwarding. Firstly, the DODAG was built, and the process begins with the transmission of DIO messages from the root node to other nodes. Then the grid was constructed according to the distance from the root node, and the restart random walk algorithm was used to select the optimal grid head node in each grid, and the overload condition in the process of data transmission was processed. Then, the spotted hyena optimization algorithm was designed to optimize the objective function, and the fitness function was estimated from multiple indexes. Finally, the optimal parent node was selected to route the packet. Finally, a downward route was built to plot the path between any node in the network and the root/destination to prepare sending data to the root. Experimental results show that the proposed method can realize data transmission with low power consumption and low packet loss and high load balance, and the performance is better than other methods.
  • 加载中

  • 图 1  本文方法流程

    下载: 全尺寸图片 幻灯片

    图 2  DODAG的构建过程

    下载: 全尺寸图片 幻灯片

    图 3  DIO消息广播

    下载: 全尺寸图片 幻灯片

    图 4  DODAG构建后的网络

    下载: 全尺寸图片 幻灯片

    图 5  网格示意图

    下载: 全尺寸图片 幻灯片

    图 6  建立路由表和DAO-ACK传输

    下载: 全尺寸图片 幻灯片

    图 7  构建向下路由的流程图

    下载: 全尺寸图片 幻灯片

    图 8  不同方法的网络寿命性能对比

    下载: 全尺寸图片 幻灯片

    图 9  不同方法的负载均衡能力性能对比

    下载: 全尺寸图片 幻灯片

    图 10  不同方法的包传输率性能对比

    下载: 全尺寸图片 幻灯片

    图 11  不同方法的丢包率性能对比

    下载: 全尺寸图片 幻灯片

    图 12  不同方法的端到端时延性能对比

    下载: 全尺寸图片 幻灯片
    Require：Imin，Imax and Idoubing
    Ensure：I(new interval)
        1   I←Imin；
        2   Start new interval；
        3        if (interval I expires) then
        4         I←I*Idoubling
        5            if (Imax≤I) then
        6                   I←Imax；
        7            endif
        8      endif
        9   if (Trickle detects an inconsistent message) then
        10           I←Imin；
        11   endif
        12   retum I；
    下载: 导出CSV
  • [1] ABDEL-BASSET M, MANOGARAN G, GAMAL A, et al. A Novel Intelligent Medical Decision Support Model Based on Soft Computing and IoT[J]. IEEE Internet of Things Journal, 2020, 7(5): 4160-4170. doi: 10.1109/JIOT.2019.2931647
    [2] BISWAS R, WU J, LI X Q. A Capacity-Aware Distributed Denial-of-Service Attack in Low-Power and Lossy Networks[C] //2019 IEEE 40th Sarnoff Symposium. Newark: IEEE, 2019.
    [3] 任立胜, 陈红红, 郭艳光. 基于流量预测的低功耗有损网络节点缓存系统设计[J]. 现代电子技术, 2021, 44(19): 35-38. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-XDDJ202119007.htm
    [4] SANKAR S, SOMULA R, KUMAR R L, et al. Trust-Aware Routing Framework for Internet of Things[J]. International Journal of Knowledge and Systems Science, 2021, 12(1): 48-59. doi: 10.4018/IJKSS.2021010104
    [5] 李祝红, 杨安东, 杜炳, 等. 物联网路由协议中的能量和延迟感知数据聚合[J]. 信息技术, 2020, 44(12): 96-101. doi: 10.3969/j.issn.1674-2117.2020.12.036
    [6] Kim T J, Joung J. Node Balanced CNC Routing Protocol for Low Power and Lossy Networks[J]. The Journal of the Institute of Internet, Broadcasting and Communication, 2019, 19(5): 123-128.
    [7] 曹亚楠, 原豪. 基于低功耗有损网络路由协议的多路由度量评估算法[J]. 传感技术学报, 2021, 34(7): 968-978. doi: 10.3969/j.issn.1004-1699.2021.07.019
    [8] 姚玉坤, 满巧, 朱克兰. 移动场景下的节点高效寻路RPL路由算法优化[J]. 小型微型计算机系统, 2021, 42(2): 424-430. doi: 10.3969/j.issn.1000-1220.2021.02.035
    [9] SAFARA F, SOURI A, BAKER T, et al. PriNergy: a Priority-Based Energy-Efficient Routing Method for IoT Systems[J]. The Journal of Supercomputing, 2020, 76(11): 8609-8626. doi: 10.1007/s11227-020-03147-8
    [10] ROYAEE Z, MIRVAZIRI H, KHATIBI B A. Designing a Context-Aware Model for RPL Load Balancing of Low Power and Lossy Networks in the Internet of Things[J]. Journal of Ambient Intelligence and Humanized Computing, 2021, 12(2): 2449-2468. doi: 10.1007/s12652-020-02382-4
    [11] GANESH D R, PATIL K K, SURESH L. Q-FRPML: QoS-Centric Fault-Resilient Routing Protocol for Mobile-WSN Based Low Power Lossy Networks[J]. Wireless Personal Communications, 2019, 105(1): 267-292. doi: 10.1007/s11277-018-6112-8
    [12] 李明, 袁敏, 付康为, 等. 基于粒子群优化算法的RPL负载均衡研究[J]. 传感技术学报, 2020, 33(3): 429-435. doi: 10.3969/j.issn.1004-1699.2020.03.018
    [13] 刘东东, 李勇, 徐栋, 等. 一种负载均衡的RPL多路径数据传输机制[J]. 计算机工程, 2019, 45(1): 67-72, 77. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-JSJC201901012.htm
    [14] SAAIDAH A, ALMOMANI O, AL-QAISI L, et al. An Efficient Design of RPL Objective Function for Routing in Internet of Things Using Fuzzy Logic[J]. International Journal of Advanced Computer Science and Applications, 2019, 10(8): 184-190.
    [15] SANKAR S, SRINIVASAN P. Fuzzy Logic Based Energy Aware Routing Protocol for Internet of Things[J]. International Journal of Intelligent Systems and Applications, 2018, 10(10): 11-19. doi: 10.5815/ijisa.2018.10.02
    [16] GHALEB B, AL-DUBAI A, EKONOMOU E, et al. A New Load-Balancing Aware Objective Function for RPL'S IoT Networks[C] //2018 IEEE 20th International Conference on High Performance Computing and Communications; IEEE 16th International Conference on Smart City; IEEE 4th International Conference on Data Science and Systems. Exeter: IEEE, 2018.
    [17] SANSHI S, JAIDHAR C D. Mobility Aware Routing Protocol Based on DIO Message for Low Power and Lossy Networks[C] //Intelligent Systems Design and Applications. Vellore: Springer, Cham, 2020.
    [18] TAGHIZADEH S, BOBARSHAD H, ELBIAZE H. CLRPL: Context-Aware and Load Balancing RPL for Iot Networks under Heavy and Highly Dynamic Load[J]. IEEE Access, 2018, 6: 23277-23291. doi: 10.1109/ACCESS.2018.2817128
    [19] 秦峰, 曾浩, 林开东. 高负载场景下基于负载均衡的LLN路由协议[J]. 计算机工程与应用, 2020, 56(1): 121-126. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG202001016.htm
    [20] LAMAAZI H, BENAMAR N. OF-EC: a Novel Energy Consumption Aware Objective Function for RPL Based on Fuzzy Logic[J]. Journal of Network and Computer Applications, 2018, 117: 42-58. doi: 10.1016/j.jnca.2018.05.015
    [21] SAFAEI B, MONAZZAH A M H, EJLALI A. ELITE: an Elaborated Cross-Layer RPL Objective Function to Achieve Energy Efficiency in Internet-of-Things Devices[J]. IEEE Internet of Things Journal, 2021, 8(2): 1169-1182. doi: 10.1109/JIOT.2020.3011968
    [22] PAUL A, PILLAI A S. A Review on RPL Objective Function Improvements for IoT Applications[C] //2021 2nd International Conference on Advances in Computing, Communication, Embedded and Secure Systems (ACCESS). Ernakulam: IEEE, 2021.
    [23] PEREIRA H, MORITZ G L, SOUZA R D, et al. Increased Network Lifetime and Load Balancing Based on Network Interface Average Power Metric for RPL[J]. IEEE Access, 2020, 8: 48686-48696. doi: 10.1109/ACCESS.2020.2979834
    [24] SAHAY R, GEETHAKUMARI G, MITRA B, et al. Investigating Packet Dropping Attacks in RPL-DODAG in IoT[C] //2019 IEEE 5th International Conference for Convergence in Technology (I2CT). Bombay: IEEE, 2019.
    [25] ZHANG T C, ZHANG T M, JI X Y, et al. Cuckoo-RPL: Cuckoo Filter Based RPL for Defending AMI Network from Blackhole Attacks[C] //2019 Chinese Control Conference (CCC). Guangzhou: IEEE, 2019.
  • 加载中
图( 12) 表( 1)
计量
  • 文章访问数:  570
  • HTML全文浏览数:  570
  • PDF下载数:  47
  • 施引文献:  0
出版历程
  • 收稿日期:  2022-01-05
  • 刊出日期:  2022-09-20

用于物联网的RPL节能负载均衡方法

    作者简介: 张虫金，硕士，实验师，主要从事计算机科学与技术研究
  • 电子科技大学成都学院，计算机学院，成都 611731
  • 收稿日期:  2022-01-05
基金项目:  四川省重点研发计划项目(2020YFG0287)

摘要: 针对物联网中低功耗有损网络路由协议节点间能量不平衡问题，该文提出一种用于物联网的RPL节能负载均衡方法. 该方法包含5个步骤：DODAG构建、最优网格头选择、最优父节点选择、向下路由和数据转发. 构建DODAG，该过程从根节点向其他节点传输DIO消息. 并根据与根节点的距离构建网格，在每个网格中使用重启随机游走算法选择最优的网格头节点，并处理数据传输过程中的重载条件. 设计斑点鬣狗优化算法优化目标函数，并用适合度函数从多个指标进行估算，最终选择最佳父节点来路由数据包. 构建向下路由绘制网络内任何节点和根/宿之间的路径，并向根发送数据. 实验结果表明，该文所提方法能够实现物联网低功耗有损网络路由低丢包和高负载均衡的数据传输，且性能优于其他方法.

English Abstract

    全文HTML

  • 开放科学（资源服务）标志码（OSID）：

  • 物联网(Internet of Things，IoT)中低功耗有损网络(Low Power and Lossy Network，LLN)在智慧城市等领域被广泛应用[1-5]，但是LLN在内存、CPU、电池等方面受到限制. 低功耗有损网络路由协议(Routing Protocol For Low Power and Lossy Network，RPL)缓解了LLN的限制，为用户提供了工具，以描述各自的网络需求和指标路由策略[6-8]，IoT采用RPL进行路由任务，以最小能量消耗和最小数据包损失来引导流量. 但是，RPL也面临节点之间能量不平衡的问题，将导致能量消耗大幅增加，主要是因为网络中一些节点在流量过大的情况下需要通过网络[9-11].

    对于物联网中RPL的研究，文献[12]提出了基于粒子群优化算法的RPL负载均衡方法，该方法通过粒子群优化算法获得各子节点的最优父节点，从而实现了所有父节点的负载均衡. 文献[13]提出一种RPL多路径数据传输机制，结合无线链路质量等度量，设计一种数据流量分配度量标准和网络负载流量分配策略，从而得到最优数据传输方案. 文献[14]使用模糊逻辑组合的多个指标，并使用模糊目标函数定义最佳树路径. 文献[15]提出基于模糊逻辑的能量感知RPL路由协议，并利用模糊逻辑算法选择网络中最优父节点. 文献[16]提出新的基于负载均衡的目标函数，在一定程度上提高了协议在功耗方面的效率. 文献[17]提出一种低功耗有损网络中基于面向目标的有向无环图信息对象(Destination Oriented Directed Acyclic Graph Information Object，DIO)的移动感知路由协议，该协议在接收到DIO消息后立即更新首选父节点信息而无需等待路由到期时间. 文献[18]提出上下文的RPL负载均衡方法，设计了上下文感知目标函数，减少了数据包丢失. 文献[19]提出高负载场景下基于负载均衡的LLN路由协议(HSLB-RPL)方法，该方法对DIO控制消息的发送时间间隔进行调整，优化了最优父节点的选择. 文献[20]提出一种能耗意识目标函数(Energy Consumption aware Objective Function，ECOF) RPL方法，设计了基于模糊逻辑的目标函数，同时考虑了链路和节点度量标准.

    但是，现有物联网RPL方法最优父节点选择，负载均衡等方面考虑并不全面，为实现物联网低功耗有损网络路由低丢包和高负载均衡的数据传输，本文提出一种用于物联网的RPL节能负载均衡方法. 该方法将物联网网络划分为网格，每个网格中采用重启随机游走(Random Walk with Restart，RWR)算法选择最优网格头节点. 然后，通过花斑鬣狗算法(Spotted Hyena Optimizer，SHO)对多指标的度量进行优化，选择最佳父节点来进行数据包的路由. 实验结果表明，本文方法能够以较好的性能实现负载均衡.

1.   用于物联网的RPL节能负载均衡方法

  • RPL协议是一个动态的距离矢量协议，在寻找网络上节点之间路径的过程中能够适应复杂的通信环境，且能够对节点设备资源受限的低功耗路由做出优化，但是RPL协议中依然存在路由开销、数据包丢失和负载不平衡等问题. RPL一般有两个基本目标函数(Objective function，OF)[21-22]，即目标函数零和最小rank迟滞目标函数. 采用期望传输计数(Expected Transmission Count，ETX)度量来计算、选择路径成本和首选父节点[23]，最终确定节点的下一跳. RPL协议以最小能量消耗和最小数据包损失来引导数据流量. RPL协议针构建了树状拓扑结构，称为面向目标的有向无环图(Destination Oriented Directed Acyclic Graph，DODAG)[24-25]，其中每个节点都希望达到一个单一的目标. 在基于树的拓扑中，数据流由根到节点，每个节点在拓扑中的位置称为rank，节点在拓扑中的位置通过OF计算得到的.

    本文方法通过5个步骤实现RPL节能负载均衡，即DODAG构建、最优网格头选择、最优父节点选择、向下路由和数据转发. 最优网格头的选择首先根据网格不同等级来构建网络区域，平衡网络的负荷和能耗，然后使用重启随机游走算法选择最优网格头节点. 对于多个指标的度量，利用SHO算法为物联网数据选择最优父节点，并以均衡的负载来路由数据包. 本文方法的流程如图 1所示.

    • 1.1.   DODAG构建

  • 在DODAG的构建过程中，传输了DODAG信息征求(DODAGInformation Solicitation，DIS)、DODAG信息对象(DODAGInformation Object，DIO)和DODAG目标广告对象(DODAGDestination Advertisement Object，DAO)等多种控制消息. DODAG的构建分为上行和下行路由建立. 对于上行路由建立，根节点用来生成网络的配置信息，将配置信息中DIO报文向邻居进行广播，收到DIO的邻居节点根据配置信息来确定是否加入该DODAG，决定加入则将DIO原地址加入父节点list，并通过目标函数计算Rank值，DIO变动并继续向邻居节点进行广播，直至所有节点加入该DODAG. 如果有节点没有接收到信息对象DIO，则广播信息征求DIS用以请求DIO. 对于下行路由建立，DODAG中节点向父节点发送DAO，其中包含自身前缀信息，收到DAO后父节点更新路由信息.

    当RPL开始构造DODAG时，每个节点的排名由根节点决定，并向邻居发送DIO消息. 每一个邻居节点接收DIO消息，并进行节点的等级确定. RPL最重要的部分是OF，决定了RPL路由使用的度量，这些度量包括跳数、ETX、剩余能量、吞吐量和链路质量水平等.

    此阶段的所有节点都处于唤醒状态，并且它们的发送器处于侦听模式，目的是获取消息构建网络DIO. 构建DODAG的过程是从根节点向其他节点传输DIO消息开始(图 2).

    步骤1   sink/root初始化DODAG信息，root(sink)会广播第一个控制消息DIO，包含以下信息：RPLInstanceID、DODAG标识符、版本号、rank和RPL支持的OF，用于计算秩. 根通信范围内的所有节点都会收到一条DIO消息，然后决定是否加入该结构，而节点加入图 2的决定取决于满足要求的节点(如果它有足够的权力进入DODAG构建过程). 当节点满足条件时，加入取决于节点等级：即使用预定义的OF计算的增量值. 相关性要求节点秩不小于或等于图 2中的节点秩. 如果节点不满足条件，在这种情况下DIO控制消息将被忽略. 这些关联的节点会将发送方的前缀添加到其父节点列表中，并计算排名.

    计算出新的秩值后，接收到DIO消息的信息用自己的新秩更新，并广播给通信范围内的所有节点. 这仅适用于第一期，其他时间段将排除具有较低等级值的节点发送DIO消息. 本文采用基于标准协议的DIO消息的大小(128字节). 图 3显示了DIO消息广播.

    在第二个周期中，任何节点都将更新的DIO消息发送到通信范围内的所有节点，但父列表中的节点除外，这可以减少每个节点的控制消息数量，从而减少消耗能量，增加网络寿命.

    步骤2   当其他接地节点(链接到DODAG的节点)收到更新的DIO消息时，它将执行以下操作：接地节点将检查发送节点ID及其父节点列表中所有节点的ID. 如果它们存在于父列表中，则接地节点检查发送控制消息DIO的节点等级. 如果控制消息DIO中发送节点等级大于接地节点等级，则接收节点更新其等级并更新DIO消息的信息，然后将其广播给通信范围内所有邻居父母列表中的预期节点.

    如果控制消息DIO中发送的节点等级等于接地节点等级，则接收节点更新其等级并更新DIO消息的信息，然后将更新后的DIO消息广播到父列表中预期节点通信范围内的所有邻居. 如果控制消息DIO中发送节点等级小于接地节点等级，则接地节点丢弃DIO控制消息.

    步骤3   继续上述步骤，直到所有节点都设置了通往DODAG根的默认路径. 每个节点都与一个或多个节点相关联，并且它包含一个首选父列表(Preferred Parents，PP). 图 4显示了DODAG构建后的网络.

    完成第一阶段后，网络中所有节点都将至少有一个到其父节点的路由条目，该路由条目逐跳通向汇聚节点，代表了多点对点(Multi-Point to Point，MP2P)转发模型——向上路由，其中每个节点都可以到达接收器.

    • 1.2.   网格头选择

  • 物联网场景RPL可表示为图G={N，L}，N表示除根节点以外物联网节点的集合，L表示连接物联网节点的链接集合. DODAG构造过程从根节点开始，将DIO消息及等级广播给相邻节点，DODAG由根节点和网格头节点构成.

    本文采用基于网格的网络来提高网络生命周期，与网络中其他节点相比，靠近根节点的节点消耗的能量更多，为了平衡整个网络能量消耗，本文构造了不同网格，靠近根节点的网格比网络中的其他网格要小. 在图 5中，呈现了4个不同等级网格. 1级网格小于其他级别，因为更靠近根节点. 2级和3级网格大于1级网格，因为它们与根节点具有比1级网格更高的距离变化. 4级网格大于其他3级网格，减少了每个级别的网格数量. 当根节点级别网格之间的距离增加时，网格的大小增加.

    这种划分网络的方式也平衡了网络中节点之间的负载，因为靠近根节点的节点比其他节点承受更大的负载. 这些优点有效地提高了本文方法的网络寿命和负载均衡能力. 网格的构建过程从根节点向相邻节点广播其rank值和DIO消息包开始，每个层级都有自己的网格大小，由到根节点的距离决定. 这种分割网络的方式有效地减少了能量损失、负载不平衡和开销.

    在每个网格中选择最优网格头节点来保证更好的网络寿命，并处理数据传输过程中的重负载条件. 网格头选择过程从根节点接收到关于DODAG构造的控制消息之后开始. 根节点主要将DIO消息及等级广播到网络. 网格头节点使用RWR算法选择，该算法从图 5中的某一个节点出发，每一步随机选择相邻节点或返回开始节点，经过迭代到达平稳. 相较于最短距离等度量，RWR算法可以捕捉图 5中两个节点之间多方面的关系，得到整体结构信息.

    本文使用RWR通过3个度量(距离根节点的距离Dr、剩余能量R和选择重负载条件下工作的节点Sh)对网格中的每个节点进行排序. 距离根节点的距离Dr用于减少数据传输期间发生的时延，通过考虑网格节点和根节点之间的距离来度量.

    物联网设备是资源受限设备，因此在网格头选择时有必要考虑节点的剩余能量Re. Re用于避免频繁的网格头选择，并减少能量损失，可表示为Re=Te-Ce. 其中，Te为节点总能量，Ce为消耗能量. Sh用于选择在重负载条件下工作的节点，通过传输能力和缓冲区大小度量来计算，具体表述为Sh=∑(TaBz). 其中，Bz表示缓冲区大小，Ta=Nt/T表示传输能力，Nt表示随时间T传输的数据包数量.

    通过上述度量，用RWR算法估计每个节点的排名，排序最高的节点被选择为网格头节点. 通过3种度量得到RWR的边权重为wij=exp(DrReSh)，则相邻矩阵W由权重组成，对其进行标准化得到$\widetilde{\boldsymbol{W}}$. RWR算法定义为：

    其中，r是得分，表示两个节点的相关度得分，c是重启概率，e是初始向量.

    对于任一节点i，当以一定概率转移到相邻节点时，进行反复迭代，每次迭代重启概率c返回节点i. 当迭代稳定后，得到节点i和j的相关性得分rij，则有$\boldsymbol{r}=(1-c)(\boldsymbol{I}-c \widetilde{\boldsymbol{W}})^{-1} e$. 其中I为单位矩阵. 选择网格中得分最高的节点作为网格头节点，发送到每个网格内成员节点的选举信息，网格中成员节点通过网格节点将它们的数据传输到根节点. 这种传输方式提供了更好的网络寿命，并有效地减少了单个节点的能量消耗.

    • 1.3.   最佳父节点路径选择

  • 本文设计了SHO的最佳父节点路径选择，通过考虑父节点链对根节点的状态来选择最优父节点，这种选择传输父节点的方式在敏感数据路由中呈现了较好的效果. 该算法将斑点鬣狗种群初始化为网络中出现的网格头节点数量，通过对每条路径适应度函数的估计，选择最优父节点路径来有效地传递数据包. 本文适应度函数设计了6个指标来估计：时延、链路可靠性、父级、缓冲区大小、数据率和预期负载.

    在SHO算法中，斑点鬣狗(Spotted Hyena，SH)的行为分为搜索、包围、狩猎和攻击猎物过程. 黏性集群的建立可提高SH之间的有效合作及适应性. 随着猎物的移动，SH的位置不断进行更新.

    其中，D为SH与猎物的距离，n为当前的迭代，B为系数向量，E为系数向量，Pp为猎物的位置，P表示SH的位置，则B和E可表示为：

    其中，λd1和λd2表示属于(0，1)的随机向量，·表示向量乘法，对于最大迭代次数N，当迭代次数逐步增加到最大迭代次数时，|h|=5-(n*(5/N))由5降为0，||表示向量的绝对值.

    SH通过群居进行生活，这样可以使用同伴的信任关系和识别猎物位置的能力追捕猎物，将SH这种行为进行数学建模，假设猎物的位置对于SH组成的集群是已知的，集群中每只SH向猎物靠近，并保留目前最好的狩猎路径来更新位置，数学描述为：

    其中，Ph表示第一个SH的最优位置，Pk表示其他SH的随机位置，L表示SH总数，L=countnos(Ph，Ph+1，Ph+2，…，(Pn+Q))，Q是随机向量，介于[0.5，1]之间，nos用于定义解的个数. C表示L个最优解的集合.

    为了对攻击猎物进行数学建模，h在迭代过程中不断减少，由5降低到0. 迭代次数增加使得搜索更细致，E也会随之发生变化，当|E|≤1时，SH群攻击猎物，数学公式描述为：

    SH搜索更新位置并攻击猎物，式(5)为最佳解决方案，表示新的SH更新的位置.

    SH根据其他同类的位置进行猎物搜索，狗群散开选择和攻击猎物. 该算法使用一个绝对值大于1的系数向量E从远离猎物较远的位置移动，保证SHO进行全局搜索. 当系数向量绝对值大于1时，则表示SH群从远离猎物的地方进行搜索；当系数向量绝对值小于1，则表示确定目标并进行攻击猎物.

    另一个系数向量B则为算法提供了猎物随机权重的随机值. 针对式(3)中系数向量的表示内容，假设向量B大于1优于B小于1，这样假设的原因有助于避免局部最优. 根据SH群位置，B可以对猎物重量进行随机确定，使得SH难以接近猎物.

    • 1.4.   适应度函数

  • 对于SHO求解最优过程中适应度的计算，本文设计了多目标适应度函数，适应度函数使用6个指标来估计：时延、链路可靠性、父级rank、缓冲区大小、数据速率和预期负载.

    时延：将数据包传输到目的地所花费的时间，该指标用于RPL物联网网络减少路由过程中的端到端时延，定义为：

    其中，Psz表示数据包大小，t表示数据包传输所需的时间.

    链路可靠性：表示源节点和目标节点之间链接的强度，用于在敏感数据路由中保证无损传输. 定义为Lre.

    父级rank：此度量用于减少源节点和目标节点之间的跳数. 网络中每个节点的rank定义为：

    其中，Rp表示父级rank，ETX表示到达根节点所需的传输次数.

    缓冲区大小：为了避免路由路径上的拥塞，减少了父节点的负载，避免了丢包. 缓冲区大小被描述为父节点缓冲区中剩余的空间：

    其中，np表示数据包的个数，Tbl表示缓冲区的总长度.

    数据速率：为了在RPL路由中实现更好的数据传输，从而提高数据包投递率(Packet Delivery Ratio，PDR). 表示为：

    其中，B表示带宽，SNR表示信号噪声比.

    预期负载：在父节点之间平衡负载. 使用在路径上历史行为的负荷进行估计，在源节点和目标节点之间考虑路径的历史行为，这种估计路径预期负载的方法有效地平衡了不同父节点之间的负载.

    其中，Ndp，i表示在时间t期间路径i上传输的数据包数量.

    通过以上这些参数，将SHO算法对每个父节点路径进行适应度估计，从而选择最优路径. 适应度估计如下：

    通过式(6)，采用SHO估计每个父节点向根节点的适应度函数，在估计适应度函数后对最优解进行聚类，然后更新每个SH的位置. 此过程将一直执行，直到达到停止条件，最后输出最优解，为物联网数据选择通向根节点的最终最佳父节点路径. 这种路由选择方式既减少了丢包、时延，又平衡了父节点之间的负载.

    • 1.5.   构建向下路由

  • 物联网中需要下行路由来支持点对多点(P2MP)通信. 在此阶段，本文方法将构建向下路由来绘制网络内任何节点和根/宿之间的路径，并准备向根发送数据. 在下行路由中，RPL使用DAO数据包，这种类型的控制消息旨在维护下行路由和控制消息DAO(DAO-ACK).

    在这个阶段，每个已经加入DODAG的节点都向它的PP发送一个DAO消息，当PP接收到控制消息DAO时，将对该消息进行处理，控制消息DAO的处理取决于RPL支持的工作模式. 下行路径有两种操作模式，存储模式和非存储模式. 本文提出一种新的存储模式.

    如果PP收到来自其子节点之一的DAO消息，则通过返回状态为0的控制消息DAO(DAO-ACK)来确认状态为0的DAO发送者，以表示接受该前缀，此时PP将接受的前缀与发送节点控制消息DAO的地址作为下一跳. 图 6表示建立路由表和控制消息DAO(DAO-ACK)传输的流程.

    如果其中一个PP收到了DAO消息并且它不能传递这个DAO消息或者它没有足够的空间来存储这个前缀，它应该拒绝宣布的前缀并用状态为1的DAO-ACK确认DAO发送者表示拒绝此前缀. 在PP拒绝其子节点之一发送控制消息DAO的情况下，子节点应执行以下操作：

    1) 锁定通向这个PP的路径，这样DAO消息就不会被发送回这个PP.

    2) 从父列表中选择另一个PP并将DAO重新发送到这个新的PP.

    在本研究中，当绘制下行路由时采用了存储模式，每个节点接收到DAO消息，并发送给它的节点地址存储在一个路由表中，路由表是一个有两个字段的表. 第一个字段是节点索引；第二个字段是该节点的下一跳或PP，用于向目的地传递控制消息或数据包. 图 7为构建向下路由的流程图.

    • 1.6.   数据转发

  • 在完成上行路径和下行路径绘制两个阶段后，必须从路由沿线的节点验证RPLDODAG拓扑中的两个基本条件. 首先，DODAG拓扑中所有节点的等级值应该从DODAG根向下增加到叶子/主机节点，以及从叶子节点向上减少到DODAG根. 其次，考虑到DODAG内部节点秩值的增减基数，DODAG内部的数据包传输要么向上到DODAG根，要么向下到叶子节点，即当数据包节点处于发送状态时，发送节点的值等级必须小于接收点的值等级，此时节点向顶部发送数据包. 一旦子节点从其PP接收到状态为零的DAO-ACK，即为接受目的地. 在这种情况下，子节点通过中间PP向目的地(根)发送数据包. 本节确定了每个节点发送的数据包数量，每个周期一个数据包数据. 当子节点将数据包传递给它的PP时：

    1) 如果PP是目的地(DODAG根)，它提取数据包并根据需要的应用程序使用它.

    2) 如果PP不是目的地(DODAG根)，则PP将根据其通往目的地(DODAG根)的路由表将数据包作为下一跳传递给其他PP. 这个过程会一直持续，直到访问到根节点的数据包.

    Trickle算法. 一旦施工完成，就开始按照Trickle计时器进行维护. 该算法作为一个发光计时器，定期发送控制消息(DIO)，减少重复消息传输. 发送控制消息之间的间隔大大增加，直到达到固定速率(也称为最大周期(Imax)). 当DODAG结算时，发送的DIO消息更少. 如果检测到不一致，间隔将返回到其最低值Imin. 算法1显示了Trickle算法的步骤.

    算法1

    Require：Imin，Imax and Idoubing
    Ensure：I(new interval)
        1   I←Imin；
        2   Start new interval；
        3        if (interval I expires) then
        4         I←I*Idoubling
        5            if (Imax≤I) then
        6                   I←Imax；
        7            endif
        8      endif
        9   if (Trickle detects an inconsistent message) then
        10           I←Imin；
        11   endif
        12   retum I；

2.   实验分析

  • 为了评估本文所提算法的有效性，使用网络模拟器Ns3进行实验. Ns3是一个开源离散事件驱动网络模拟器，由C和Python语言编写形成. 实验参数设置：模拟时间为600 s，50个物联网节点部署在有一个根节点的500×500 m2区域，本文中根节点充当边界路由器节点，将网络区域划分为4层不同大小的网格. 网络参数设置：初始能量50 J，传输范围100 m，发射功率-18 dBm；包参数设置：封包格式IPV6，包总数1 000，数据包大小60字节，DIO和DAO包长度为17字节，DIS包长度2字节，数据包间隔0.5 s，1.5 s，2 s. 流量参数设置：流量类型恒定比特率，流量速率15，25，35，45，80 pkt/s.

    为了验证本文方法的有效性，将本文方法与其他现有方法进行比较. 现有方法有：文献[11]中的上下文感知和负载平衡RPL(Context-Aware and Load Balancing RPL，CLRPL)方法，文献[5]中基于粒子群优化算法(Particle Swarm Optimization，PSO)的RPL负载均衡方法，文献[12]中高负载场景下基于负载均衡的LLN路由协议(HSLB-RPL)方法，文献[13]中能耗意识目标函数(energy consumption aware objective function，ECOF) RPL方法.

    实验对比指标有：网络寿命、负载均衡能力、包传输率、丢包率及端到端时延. 网络寿命定义为物联网节点消耗其能量和死亡的持续时间.

    负载均衡能力(Load balancing capability，LBC)通过系统中存在的单个网格头节点的负载与网络负载的比值来测量，表示为：

    其中，Li表示第i个节点负载，Nl表示网络负载.

    包传输率定义为在目标节点接收的包数与在源节点传输的包数的比率；丢包率定义为在传输过程中丢包的数量.

    图 8给出了不同方法物联网网络寿命的性能对比. 从图 8中可以看出，与其他方法相比，本文方法的网络寿命更长，这是因为本文所提方法把网络分成不同层次的不相等网格，靠近根节点的网格比其他网格小，这种划分网络的方式降低了网络能耗，避免了靠近根节点的节点过早死亡，并通过向根节点传输大量数据包平衡了整个网络的能量. 相反，现有方法获得的NL(Network Lifetime)比本文所提方法少，且对于整个网络能量的平衡性较能差，不能通过调度来节省能源，数据传输时消耗的能量较大. 因此，在基于RPL的物联网网络中，本文所提方法得到的网络寿命更长.

    通过对比不同方法的负载均衡能力，可以看出本文方法的性能优于现有方法(图 9). 本文所提方法使用连接到根节点的历史行为来平衡父节点之间的负载，在物联网数据传输期间，基于多指标SHO的父节点选择过程中考虑预期的负载度量，可以平衡网络中不同父节点之间的负载. 此外，将网络划分为不同层次的不相等网格，靠近根节点的网格更小，利于处理来自网络其余部分的负载. 反之，远离根节点的网格较大，这种分割方式在网络之间提供了均衡负载，增强了物联网的负载均衡能力. CLRPL方法通过考虑队列利用率和子计数指标来实现负载平衡，但负载均衡能力效率较低；HSLB-RPL方法对备选父节点DIO控制消息的发送时间间隔进行调整，负载平衡效率较低；ECOF方法具有繁琐的父节点选择过程，导致整个负载均衡效率较低；而传统PSO优化方法虽然具有较好的鲁棒性和极快的搜索速度，但PSO更容易陷入局部最优解，输出不准确的最优解，所以负载均衡能力效率也较低.

    图 10给出了不同方法的包传输率. 由图 10可以看出，PDR(Packet Delivery Ratio)随着网络中节点数量的增加而增加，这是因为随着节点数量增加，数据传输能力也得到了提高. 与现有其他方法相比，本文所提方法利用了有效的目标函数. 目标函数根据后续指标时延、链路可靠性、父节点级别、缓冲区大小、数据速率和预期负载，通过多目标SHO算法选择最优父节点路径，从而提高数据包传输性能. 而现有其他方法利用跳数、ETX等传统参数来选择最优父节点，导致了实验中包传输率的减少.

    图 11将本文方法与现有的CLRPL，PSO，HSLB-RPL，ECOF方法进行比较. 由图 11中可以看出，随着节点数量增加，节点丢包的概率增加，丢包率也随之增加. 与现有方法相比，本文所提方法能够以较低的丢包率进行数据包传输. 本文通过多指标SHO方法进行最优父节点选择，并将数据传输到根节点，有效地减少了传输过程中的丢包. 相比之下，现有方法具有较高的丢包率，因为这些方法没有利用一种有效的机制来选择最优父节点，并将数据包传输到根节点，在数据包传输过程中造成更多的数据包丢失.

    为了验证本文方法时间性能的优越性，图 12给出了本文方法与其他方法的端到端时延. 由图 12可以看出，端到端的时延随着节点数的增加而增加，这是因为源和目标之间的节点数增加了. 另外，本文方法的端到端时延都小于其他方法，这是因为本文所提方法在数据传输期间的父代选择中执行得更快，将网络划分为不同层次的不相等网格，并在不同网格内选择网格头. 另外，SHO优化了最佳父节点路径选择，减少了数据传输期间的时延.

3.   结论

  • 为了解决基于RPL的IoT数据丢包和负载不均衡问题，本文提出一种新的IoT低功耗有损网络路由协议节能负载均衡方法. 首先构建了DODAG上行路由，然后在划分的不同层级网格中使用RWR算法选择最优的网格头节点，有效地从成员节点收集数据并在重负载条件下工作. 使用基于SHO的多指标目标函数优化算法选择最优父节点，以较低丢包率和较高负载均衡能力等性能进行数据包传输. 最后构建下行路由并实现数据转发. 将本文方法与现有方法进行比较，在网络寿命、负载均衡能力、数据包传输率、丢包率和端到端时延等方面，本文方法均体现出较好的性能. 未来工作是进一步减少基于RPL的动态IoT网络中的参数，同时保证物联网数据的安全路由.

参考文献 (25)

目录

版权所有：西南大学学报（自然科学版）

地址：重庆市北碚区西南大学 电话：023-68254576, 68252540, 68366165,68366917 电子邮箱：lkxb@swu.edu.cn

本系统由北京仁和汇智信息技术有限公司开发

/

返回文章
返回