logo资料库

论文研究-针对RPL协议的改进Trickle算法 .pdf

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.43M 资料格式：pdf 举报 版权申诉
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
资料共8页，全文预览结束
    中国科技论文在线 http://www.paper.edu.cn 针对 RPL 协议的改进 Trickle 算法 田广东，叶鑫* （重庆邮电大学通信与信息工程学院，重庆 400065） 10 5 摘要：Trickle 算法被指存在短期监听问题，并可能会引起负载分布不均衡、收敛较慢及次 优路径的产生.本文针对这些问题提出一种改进的 Trickle 算法，即 Trickle-S。改进的动机有 三点：第一，针对节点发送消息不公平的问题，引入了一个 参数，根据节点被抑制发送的 次数来动态调整节点下一时间间隔发送消息的优先级；第二，针对短期监听问题，决定修改 计数器 的起始计时点，即只在第一个时间间隔和以后的每个间隔内的发送消息的时刻 才对 重置；第三，当节点接收到“不一致”的消息时，下一个间隔应从 之间来随机选取 。对 Trickle-S 的仿真表明，在其它性能不变的前提下能有效降低网络的收敛时间。 关键词：低功耗有损网络；低功耗有损网络路由协议；Trickle 中图分类号：TP393 15 Enhanced Trickle algorithm for RPL Tian Guangdong, Ye Xin 20 25 30 (School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China) Abstract: Trickle is shaped by the so-called listen-only period, and unsuitable configuration may lead to unfairness in term of load distribution, latency and generation of sub-optimal route. In this paper, en enhanced Trickle algorithm, namely Trickle-S is proposed to solve these problem. The modification of Trickle-S is threefold. Firstly, in order to provide broadcast fairness, each node keeps track of s(a newly parameter), the number of continuous communication intervals in which a message transmission has been suppressed, Trickle-S gives the node a priority to send its scheduled DIO depending on how many DIOs have been suppressed. Secondly, instead of setting the counter c to a value of 0 at the beginning of each interval, we set the c to a value of 0 only at the beginning of the first interval and also at the randomly chosen time t in order to eliminate the cumulative effect of the short-listen problem. Thirdly, if a new interval is started as a result of resetting I to (Trickle hears an inconsistent transmission), then choose the transmission time t from . The evaluation of Trickle-S shows that it can decrease the convergence time with other properties unchanged. Key words: LLN, RPL, Trickle 35 0 引言 RPL(Routing Protocols for Low Power and Lossy Network, RPL)设计之初就是针对含有上 千个资源受限节点的 LLN(Low-Power and Lossy Networks, LLN)网络，比如 AMI(Advanced Metering Infrastructure, AMI)网络，而它在大规模 AMI 网络中的实用性已经得到了认可[1]。 针对这种网络，RPL 定义了一些能耗感知的路由度量，以期将能耗因素作为路由性能考量 40 的重点。RPL 的一个核心设计原则就是最小化路由控制开销和信令数据的同时降低能量消 耗并提高协议的可靠性。为了达到这个目的，RPL 采用了 Trickle 算法机制，Trickle 算法可 以控制 DIO 等数据的传输，直接影响了 LLN 网络中 DODAG 拓扑的构建[2, 3]。利用 Trickle 算法可以管理路由信息在网络中的传播，它的宗旨就是在保证很低的路由收敛时间的前提 45 下，尽量最小化网络中路由更新信息的总量[4]。当网络中的路由广播消息显得冗余时，要尽 量抑制这些冗余消息的传播[3]。 作者简介：田广东（1968-），男，教授，主要研究方向：物联网. E-mail: jason2ye@163.com - 1 -
    中国科技论文在线 http://www.paper.edu.cn Trickle 算法是基于随机定时器及窗口加倍两个关键机制的，以此来均衡流量负载和响 应时间[5]。Trickle 算法把时间划分为大小可变的时间间隔，每个时间间隔内会随机分配一个 时间点以供节点发送数据。如果在一定时间内从它的邻居监听到了“一致性”的信息，节点就 应该抑制它的信息发送；相反，一旦监听到了“不一致”的数据，节点就应该加快发送数据的 50 频率以便尽快解析这个不一致的数据。而这些数据及消息的发送和调度是由 Trickle 算法的 一些参数来控制的。 1 Trickle 算法及其相关研究 Trickle 算法定义了 3 个全局变量：最大间隔长度 ，最小间隔长度 及冗余常量 ； 此外，Trickle 算法还定义了 3 个局部变量来维持节点当前的状态：当前时间间隔大小 ，从 55 当前时间间隔随机选择的发送时间点 以及用于计算当前间隔内累计听到的消息数量 。 Trickle 算法包含 6 个步骤： 1. Trickle 算法初始化，从 之间选择一个 值，开始执行第一个时间间隔； 2. 当时间间隔开始后，Trickle 将 和定时器都重置为 0，并将发送时间点 设为 之间的一个随机值； 60 3. 一旦收到一致性的消息，将计数器 加 1； 4. 在发送时间点 时刻，如果 大于或等于冗余常量 ，Trickle 就抑制本次消息的发 送，否则就允许发送消息； 5. 一旦 过期了，Trickle 就将 加倍，作为新的时间间隔，如果加倍后的大小超过了 ，就将当前时间间隔设为 ，并重新从第二步开始执行； 65 6. 如果 Trickle 监听到了不一致的消息，并且此时 大于 ，就重置定时器，将 设 为 并回到第 2 步开始执行，开始一个新的时间间隔；否则什么也不做。 Trickle 算法中 3 个主要的参数 、 及 都是由 RPL 中 DODAG 根节点发送的， 参数的值都被封装在 DIO 消息之中。因此，一旦收到这些 DIO 消息，这些参数值就会被根 节点的邻居节点获取到。与此同时，邻居节点也会将这些 DIO 消息发送出去，这个过程会 70 一直进行，直到所有的节点都加入到了这个 DODAG，而最初由根节点通告的这些参数值最 终也传播到了整个 DODAG。因此，Trickle 算法对 RPL 网络的收敛性能扮演了一个很关键 的角色[6]。 除了网络收敛性能，Trickle 算法对路径质量、节点能耗、网络生存周期、端到端延时、 负载分布等因素均有很大影响。文献[7]的作者是第一个考虑冗余常量 及其他参数对 RPL 75 性能的影响的研究者，作者指出，如果参数配置不恰当，Trickle 的消息抑制机制会导致次 优路径，尤其是网络密度分布不均的网络，比如随机空间拓扑。分析指出这主要就是 Trickle 算法抑制机制的自身的不公平性导致的。为了保证节点能更公平的得到发送数据的机会，作 者提出了一个改进措施，根据节点最近发送数据的多少来给每个节点分配一个优先级。换句 话说，如果节点最近被抑制发送数据的次数越多，那么它在下一个时间间隔内发送数据的优 80 先级就越高。这个改进措施成功解决了负载均衡问题，然而，由于依然存在一个短期监听的 时间间隙，因此还是会影响网络的收敛性能。 文献[5]指出，Trickle 算法的内在机制会引起负载分布的不均衡，并着重分析了冗余常 量 对节点发送公平性的影响，指明了 Trickle 算法偏爱节点度低的节点，使这些节点发送 - 2 - maxIminIkItcminmax[,]IIIct[/2,]IIctckIImaxImaxIIminIIminIminImaxIkkk
    中国科技论文在线 http://www.paper.edu.cn 数据的机会更高，而节点度大于 的节点很少有机会发送数据，作者最终提出了一种根据节 85 点密度来动态调整 值的改进 Trickle 算法 adaptive-k，在保持比较低的控制开销下还能发现 最优路径。 文献[8]指出，如果始终使用一个固定的 值，会导致发送数据的不公平，因此从数学 角度上提出了一个概率模型，用于分析各节点发送数据的概率公平性。并建议根据节点的邻 居数量来设计一个关于 的函数，以此提升节点发送数据的公平性。 90 文献[9]的作者提出了一种动态调整 Trickle 参数的自适应 Trickle 机制，以此来减少节点 的能耗。每当节点的剩余能量低于一个预定义的阀值或网络很明显发生了变化的时候就会触 发这个动态调整参数的机制。然而调整的方式还是不够灵活，并且没能够规避短期监听的问 题。 为了克服短期监听导致网络收敛较慢的问题，文献[10]的作者提出了一种改进的 Trickle 95 算法：opt-Trickle。作者指出，节点如果收到不一致的消息时，应立即将定时器重置（回到 ），这样做可以在这些节点间实现一种隐式的同步机制。而这种同步机制将会消除第一 个时间间隔内短期监听的必要，并可以让相应的节点从 之间选择发送数据的时间点 。然而，这些改进的前提是假定 MAC 协议采用了 100%的占空比，而这既不合理也不现实。 并且，opt-Trickle 在后续的时间间隔内依然存在短期监听的问题，导致延时的增加。尤其是 100 在那种有损网络情况下，消除第一个时间间隔的短期监听时隙并不能保证发送的消息会达到 所有的目的地。 上述介绍 Trickle 算法相关研究的过程中，反复提到了一个短期监听的概念。短期监听 是指 Trickle 算法规定节点必须在 间的某个时间点发送数据，也就是节点必须先监 听 的时间后才开始发送数据。文献[11]指出，短期监听的时间会随着网络跳数的增加而 105 逐跳累加，最终导致延时的增加，并且还会给负载分布带来消极的影响。 2 改进的 Trickle 算法：Trickle-S 针对 Trickle 算法存在的不足之处，本文提出一种改进的 Trickle 算法，称其为 Trickle-S， 改进算法的动机主要有三个方面。首先，针对 Trickle 算法导致节点发送概率不公平并引起 负载不均，次优路径的问题[5],[7]，决定根据节点被抑制发送的次数来决定节点下一次发送的 110 优先顺序，如果节点没有发送数据的时间越长，那么它在下一次发送数据的优先级就越高。 为此，引入了一个新的参数 ，用来指明节点在一个时间间隔内被抑制发送数据的次数。在 时刻，如果 DIO 消息被发送了， 就重置为 0；否则， 就自增一次。此外，Trickle 算法 的时隙不再是平分成监听和发送两个时间段，而是根据 来动态调整监听和发送时隙的长 度。每当一个新的时间间隔开始，发送时刻 从 之间来随机选取。这样一来，节点 115 发送数据的优先级完全由过去一段时间被抑制发送的次数来决定，等待发送数据的时间越长 （也就是被抑制发送的次数越多）的节点，下一次得到发送数据的概率就越高。其次，针对 Trickle 算法的短期监听导致的延时和收敛性能不佳的问题，决定修改计数器 重置的时间 点。因为短期监听问题很大程度上来源于这个事实：Trickle 算法没有充分利用发送消息时 间点 到本次时间间隔的最终时刻这段时间的控制消息，并在每个新时间间隔内将计数器 120 重置了。因此，Trickle-S 决定改变 的时间跨度：仅在两种情况下重置 ，分别是第一个时 间间隔开始的时候及以后的每个间隔的 时刻。这样就可以尽量消除短期监听带来的累计延 时的影响。应该注意到，引入 参数一定程度上也降低了短期监听的时长。最后，为了进一 - 3 - kkkkminImin[0,]It[/2,]II/2Istssst122(,)ssIIctcccts
    中国科技论文在线 http://www.paper.edu.cn 步降低短期监听问题带来的延时，对原始 Trickle 算法第二步收到不一致消息时的处理规则 稍微做一些修改：一旦收到不一致的消息时，应从 之间来随机选取下一个间隔的 。 125 这样做的好处就是一旦监听到了不一致的消息时，可以使节点更快的发送消息，去掉了额外 的监听时间，以便尽快将这个不一致的消息传播出去。Trickle-S 的伪代码如表 1 所示，其中， “ ”和“ ”表示对原来 Trickle 算法的改动。“ ”表示在原来算法基础上增加的部分，而“ ” 则表示从原来算法删除的部分。 表 1 改进的 Trickle-S 算法 Algorithm Trickle-S function Initialization() function StartNewInterval() if NewIntervalBeginWithInconsitency then else if then end if end if function ReceivedConsistendTransmission() function RandomTimerExpires() if Transmit DIO then else end if 130 3 Trickle-S 算法的性能评估 为了评估Trickle-S算法的性能，对其同Trickle算法进行了仿真和实际环境的性能对比。 对比的主要性能参数有网络收敛时间、节点能耗及包投递率，仿真环境选择了Contiki系统， 仿 真 工 具 则 利 用 了 Contiki 自 带 的 COOJA[12] 网 络 仿 真 器 ， 而 能 量 测 量 工 具 则 用 到 了 Powertrace[13, 14]。ContikiRPL是RPL协议的具体实现，包含了Trickle算法。仿真过程中，选 择了均匀的网状拓扑，所有的节点在网格中等距放置，边界路由器放在网络的中间位置。为 135 了保证路径的稳定性，目标函数选取了MRHOF。对每个场景，仿真运行了15次试验，每次 试验取不同的随机种子，为了得到稳定可靠的统计学结果，每次试验运行了20分钟。仿真中 详细的配置参数如表2所示。 - 4 - min(0,)ItminII0s0cminIImin(0,)tI0c2II0cmaxIImaxII122(,)ssIItrandom22(,)IItrandom1cckc0s1ss0c
    中国科技论文在线 http://www.paper.edu.cn 140 表 2 仿真参数配置表 参数 节点个数 仿真时间 数据包速率 Mac/适配层 射频介质模型 损耗模型 损耗率 覆盖范围(m) 值 25,50,100,200 20 分钟 60s ContikiMac/6LoWPAN Unit Disk Graph Medium(UDGM) 距离损耗 0,10,30,50,70,90 30 图 1 收敛时间随节点密度的变化 145 图1表示两种算法的收敛时间随节点密度不同而变化的情况。从图中可以看出Trickle-S 能有效的降低收敛时间。收敛时间之所以改善明显，是因为尽量降低了节点的短期监听时长， 使得节点有更长的时间接入信道，并能有效降低碰撞概率。此外，另一个可能的原因就是 Trickle-S只在每个间隔的 时刻才重置计数器 ，而不是像Trickle算法那样在每个间隔的开 始重置 。 150 图 2 平均能耗随节点密度的变化 - 5 - minmax()/()ImsIms12202/2tcc
    中国科技论文在线 http://www.paper.edu.cn 155 图 3 投递率随节点密度的变化 图2、3分别是平均能耗、投递率随节点密度变化而变化的示意图。从图中可以看出，随 着节点密度的增大，这两种算法总体上的性能曲线表现出了相同的走势，Trickle-S的投递率 和能耗性能基本与原始Trickle算法相当。这表明Trickle-S可以像Trickle那样高效的发现路径， 160 而花费的时间却更少。随着网络密度的增大，平均能耗均会增加，而投递率则均呈下降趋势， 这个问题可以这样来解释：随着网络密度的增大，节点的邻居增多了，节点会接收到更多的 控制消息，有可能增加信道碰撞的概率，造成消息的多次重传，最终导致能耗的增大和投递 率的下降。 165 图 4 收敛时间随损耗率的变化 图4是两种算法的收敛时间在不同路径损耗率的对比图。图5、6则是投递率和平均能耗 在不同路径损耗下的性能对比图。其中，0%的损耗率表示网络没有损耗，不会由于信号衰 减而造成丢包，但应该注意丢包还是会因其他因素，比如碰撞等因素而发生。从图中可以看 170 出，Trickle-S对网络收敛性能的改善明显，这表明Trickle-S受短期监听问题的影响较小，因 为收敛性能改善的同时并没有造成能耗的增大，此外，Trickle-S在保证不增加能耗的同时稍 微提高了投递率。 - 6 -
    中国科技论文在线 http://www.paper.edu.cn 175 图 5 投递率随损耗率的变化 图 6 平均能耗随损耗率的变化 从图中还可以看出，路径损耗率越大，两种算法收敛的越慢。这是因为路径损耗率 180 越高，控制消息（比如 DIO）丢失的概率越高，因此延长了组网的进程。此外，随着路径损 耗的增加，平均能耗也会增加，投递率降低。这表明两种算法为了发现更优的路径，发送了 更多的控制消息，造成了能耗的增加。 4 结论 Trickle 算法对 RPL 性能有着很重要的影响，本文针对 Trickle 算法自身存在的一些 185 问题，做出了相应的改进措施，改进后的 Trickle 算法在保证同等性能的条件下能有效降低 网络收敛时间，对延时性能要求高的场合下有一定的参考价值。 [参考文献] (References) 190 Low Power and [1] D.Popa, J.Jetcheva, N.Dejean, R.Salazar, J.Hui, K.Monden. Applicability Statement for the Routing Protocol for Internet-Draft[OL]. http://tools.ietf.org/html/draft-ietf-rollapplicability-ami-06 [2] P.A.Levis, N.Patel, D.Culler, S.Shenker. Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor network[J]. Computer Science Division. 2003 Networks(RPL) Networks in AMI Lossy - 7 -
    中国科技论文在线 http://www.paper.edu.cn 195 200 205 210 215 [3] E.Ancillotti, R.Bruno, M.conti, E.Mingozzi, C.Vallati. Trickle-L2: Lightweight link quality estimation through Trickle in RPL networks[A]. in A World of Wireless, Mobile and Multimedia Networks(WoWMoM). 2014 IEEE 15th International Symposium on[C]. 2014. 1-9. [4] M.Becker, K.Kuladinithi, C.Grg. Modelling and simulating the trickle algorithm[J]. Social Informatics and Telecommunications Engineering, 2011, 97. [5] Thomas M.M.Meyfrovt, Milosh Stoliki, Johan J.Lukkien. Adaptive Broadcast Supperss for Tricikle-Based Protocols[A]. IEEE International Symposium on World of Wireless, Mobile & Multimedia Networks[C]. 2015.1-9. [6] K Hamidreza, G Carles. On the Network Convergence Process in RPL over IEEE 802.15.4 Multihop Networks[J]. Sensors, 2014, 14(7). [7] C.Vallati, E.Mingozzi. Trickle-F: Fair broadcast suppression to improve energy-efficient route formation with the RPL ruoting protocol[A]. in Sustainable Internet and ICT for Sustainability(SustainIT0[C]. 2013. 1-9. [8] T Coladon, M Vucinic, B Tourancheau. Multiple Redundancy Constants with Trickle[J]. axXiv.org, 2015. [9] Y.W.Lin, P.-H.Wang. Performance Study of an Adaptive Trickle Scheme for Wireless Sensor Networks[A]. J.J.Park, Y.Pan, H.C.Chao, G.Yi. in Ubiquitous Computing Application and Wireless Sensor[C]. Netherlands: Springer, 2015. 163-173. [10] B.Djanaa, M Richardson. Optimizing the Trickle Algorithm[J]. IEEE Communications Letters, 2015, 19(5): 819-822. [11] TMM Meyfroyt, SC Borst, OJ Boxma, D Denteneer. On the scalability and message count of Trickle-based broadcasting schemes[J]. Queueing Systems, 2015, 81(2-3): 1-28. [12] Contiki OS and cooja simulator[OL]. http://contiki-os.org [13] Adam Dunkels, J.Eriksson, N.Finne, N.Tsiftes. Powertrace: Network-level Power Profiling for Low-power Wireless Networks[J]. 2011. [14] A.Dunkels, F.Osterlind, N.Tsiftes, Z.He. Software-based on-line energy estimation for sensor nodes[A]. in Proceeding of the 4th workshop on Embedded network sensors[C]. New York: 2007. 28-32. - 8 -
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料