论文部分内容阅读
摘 要：本文针对DTN中基于洪泛算法，提出了机遇节点活跃和消息副本数目的缓存策略，旨在少量增加消息平均传输延迟外，大大提高了消息交付比率，降低了开销比率。实验结果表明MC算法具有较优的性能。
关键词：洪泛算法；缓存策略；交付比率；开销比率
中图分类号：TN929.5
DTN（Delay Tolerant Network）路由是一个非常复杂的问题，其中一个极大问题就是DTN的节点资源有限，而且针对有限节点资源（如缓存、节点能量、带宽等）的研究工作很少。DTN中的各个节点收到新消息后，先将消息存储在自己的缓存空间中，然后等待，直到合适的下一跳节点到来才将该消息复制转发给下一跳节点，因此消息被缓存的时间非常长。当节点的存储空间有限、网络中的通信量较大时，缓存空间不足时如何丢弃消息以腾出空间给新来的消息很重要。当接收节点的缓存已满时，节点必须腾出空间来存储新消息，因此必须设计合适的缓存机制来解决该问题。
1 相关工作
常用的缓存管理策略有：先进先出（FIFO）、后进先出（LIFO）、随机（Random），这些策略在传统存在端到端路径的网络中运行效果良好，但是在DTN中缓存受限的情况下，路由协议的性能将受到很大的影响。Epidemic算法[1，2]在缓存受限情况下，延时性能将急剧下降。文献[2]中，Zhang等人评估了缓存受限情况下在Epidemic协议中使用的一些简单的丢弃策略。文献[3]利用网络全局信息提出了一种策略，并指出策略的不足之处，但是在DTN中能够及时掌握全局信息，是较为困难的事情。
基于洪泛的路由算法（如Epidemic）工作原理是：源节点产生一个消息之后，扩散给n个中继节点，中继节点以相同的方式进行进一步的复制扩散。其中n为所有源节点的邻居节点数。在一些改进算法中限制了n的取值为一个常数a。而这些算法均不能根据缓存动态调整消息副本数目。
2 基于消息副本的缓存算法（MC）
假设缓存队列中的存在一个消息，并且设n的值为某个常数b，则消息通过一跳后网络中消息m的副本数为1+b。这样传递下去，随着跳数的增加，消息副本数呈现出指数增长，然而跳数的增长和时间增长一致，因此消息的增长数随时间呈指数增长。文献[4]提出了路径爆发现象：在大多情况下，最优路径经过很长一段时间首先到达目的节点，紧接着许多路径会在相对较短的时间内相继到达目的节点，这些路径为次优路径，次优路径数随时间呈指数增长的趋势。
针对DTN中每个新生成的消息，同时记下它的副本数目num。当携带新生成消息的节点遇到下一个节点时，如果该节点没有携带消息，则把消息的num加1，再将该消息传给遇到的节点。根据各个小的num值，可以大致推断出来，num越大，该消息已经被复制多次，在网络中存有它的副本较多；否则反之。
文献[5]中指出根据消息副本数目值的大小，来决定删除何种消息。该算法是当一个节点的缓存不够的情况下，删除num值较大的那个消息。但没有考虑如果该节点的活跃度较强时，就意味着该节点遇到目的节点的可能性更大。这样盲目删除副本数大的消息，同时降低了更接近目的节点的概率。
故在本文算法MC设计中，在删除副本数目之前先判断一下节点j的活跃度，hj（即在单位时间内，一个节点邻居数目）相对上一跳节点i的活跃度hi的大小，如果比值大于1，同时节点j缓存空间不够，这时也只是按比例部分删除副本的数目，即保留众多消息中，删除副本数目最大的消息副本数目直至为numj*┌hi/，hj┐。
3 实验仿真
采用芬兰赫尔辛基理工大学开发的DTN仿真工具ONE，同样采用了文献[5]中，同样的环境配置：即4500m×3400m的城市地图，共设置了6组共126个节点，节点的运动模式都是采用基于地图的最短路径运动模式。其中前两组每组40个节点，其速度为0.5～1.5m/s，模拟行人的运动轨迹；第3组节点数目为40，其速度为2.7～13.9m/s，模拟汽车的运动轨迹；后3组每组2个节点，运行速度为7～10m/s，且只能在指定的轨道上运动，模拟有轨电车。每个节点的传输范围为10m，传输速度为250kBps。仿真时间设置为43000s，其间每隔25～35秒随机挑取节点对生成一个新的消息，消息大小为500kB～1MB，消息TTL为6h。我们在这个实验环境下分别运行了采取不同缓存丢弃策略的Epidemic协议。
3.1 采用不同缓存策略对Epidemic进行分析
同文献[5]一样设置节点缓存大小从5M变化到50M，观察各种缓存丢弃算法对Epidemic协议性能的影响。交付比率、开销比率和平均延时分别如图1、图2、图3所示。MC算法较之LIFO、FIFO，除了平均延时少有增加外，其他指标均有较好的性能。
4 结束语
本文中设计的MC算法由于考虑了节点活跃度和节点副本数，除了在延时方面比其他传统算法要略高之外，其他性能均优。
参考文献：
[1]Spyropoulos T，Psounis K，Raghavendra C S.Spray and wait：an efficient routing scheme for intermittently connected mobile networks.ACM SIGCOMM Workshop on Delay-Tolerant Networking （WDTN’05），2005：252-259.
[2]Zhang X，Neglia G，Kurose J F.Performance modeling of epidemic routing. Computer Networks，2006（51）：2867-2891.
[3]Krifa A，Barakat C，Spyropoulos T.Optimal buffer management policies for delay tolerant networks.IEEE SECON，2008：260-268.
[4]Erramilli V，Chaintreau A，Crovella M.Diversity of forwarding paths in pocket switched networks.ACM SIGCOMM IMC，2007：161-174.
[5]朱敬.延迟容忍网络路由协议的研究[D].中南大学，2009：43-44.
作者简介：赵红敏（1978-），女，河南郑州人，讲师，硕士，研究方向：无线网络协议分析。
作者单位：中南林业科技大学 计算机与信息工程学院，长沙 410004
基金项目：湖南省高等学校科学研究项目（项目编号：11C1306）。
关键词：洪泛算法；缓存策略；交付比率；开销比率
中图分类号：TN929.5
DTN（Delay Tolerant Network）路由是一个非常复杂的问题，其中一个极大问题就是DTN的节点资源有限，而且针对有限节点资源（如缓存、节点能量、带宽等）的研究工作很少。DTN中的各个节点收到新消息后，先将消息存储在自己的缓存空间中，然后等待，直到合适的下一跳节点到来才将该消息复制转发给下一跳节点，因此消息被缓存的时间非常长。当节点的存储空间有限、网络中的通信量较大时，缓存空间不足时如何丢弃消息以腾出空间给新来的消息很重要。当接收节点的缓存已满时，节点必须腾出空间来存储新消息，因此必须设计合适的缓存机制来解决该问题。
1 相关工作
常用的缓存管理策略有：先进先出（FIFO）、后进先出（LIFO）、随机（Random），这些策略在传统存在端到端路径的网络中运行效果良好，但是在DTN中缓存受限的情况下，路由协议的性能将受到很大的影响。Epidemic算法[1，2]在缓存受限情况下，延时性能将急剧下降。文献[2]中，Zhang等人评估了缓存受限情况下在Epidemic协议中使用的一些简单的丢弃策略。文献[3]利用网络全局信息提出了一种策略，并指出策略的不足之处，但是在DTN中能够及时掌握全局信息，是较为困难的事情。
基于洪泛的路由算法（如Epidemic）工作原理是：源节点产生一个消息之后，扩散给n个中继节点，中继节点以相同的方式进行进一步的复制扩散。其中n为所有源节点的邻居节点数。在一些改进算法中限制了n的取值为一个常数a。而这些算法均不能根据缓存动态调整消息副本数目。
2 基于消息副本的缓存算法（MC）
假设缓存队列中的存在一个消息，并且设n的值为某个常数b，则消息通过一跳后网络中消息m的副本数为1+b。这样传递下去，随着跳数的增加，消息副本数呈现出指数增长，然而跳数的增长和时间增长一致，因此消息的增长数随时间呈指数增长。文献[4]提出了路径爆发现象：在大多情况下，最优路径经过很长一段时间首先到达目的节点，紧接着许多路径会在相对较短的时间内相继到达目的节点，这些路径为次优路径，次优路径数随时间呈指数增长的趋势。
针对DTN中每个新生成的消息，同时记下它的副本数目num。当携带新生成消息的节点遇到下一个节点时，如果该节点没有携带消息，则把消息的num加1，再将该消息传给遇到的节点。根据各个小的num值，可以大致推断出来，num越大，该消息已经被复制多次，在网络中存有它的副本较多；否则反之。
文献[5]中指出根据消息副本数目值的大小，来决定删除何种消息。该算法是当一个节点的缓存不够的情况下，删除num值较大的那个消息。但没有考虑如果该节点的活跃度较强时，就意味着该节点遇到目的节点的可能性更大。这样盲目删除副本数大的消息，同时降低了更接近目的节点的概率。
故在本文算法MC设计中，在删除副本数目之前先判断一下节点j的活跃度，hj（即在单位时间内，一个节点邻居数目）相对上一跳节点i的活跃度hi的大小，如果比值大于1，同时节点j缓存空间不够，这时也只是按比例部分删除副本的数目，即保留众多消息中，删除副本数目最大的消息副本数目直至为numj*┌hi/，hj┐。
3 实验仿真
采用芬兰赫尔辛基理工大学开发的DTN仿真工具ONE，同样采用了文献[5]中，同样的环境配置：即4500m×3400m的城市地图，共设置了6组共126个节点，节点的运动模式都是采用基于地图的最短路径运动模式。其中前两组每组40个节点，其速度为0.5～1.5m/s，模拟行人的运动轨迹；第3组节点数目为40，其速度为2.7～13.9m/s，模拟汽车的运动轨迹；后3组每组2个节点，运行速度为7～10m/s，且只能在指定的轨道上运动，模拟有轨电车。每个节点的传输范围为10m，传输速度为250kBps。仿真时间设置为43000s，其间每隔25～35秒随机挑取节点对生成一个新的消息，消息大小为500kB～1MB，消息TTL为6h。我们在这个实验环境下分别运行了采取不同缓存丢弃策略的Epidemic协议。
3.1 采用不同缓存策略对Epidemic进行分析
同文献[5]一样设置节点缓存大小从5M变化到50M，观察各种缓存丢弃算法对Epidemic协议性能的影响。交付比率、开销比率和平均延时分别如图1、图2、图3所示。MC算法较之LIFO、FIFO，除了平均延时少有增加外，其他指标均有较好的性能。
4 结束语
本文中设计的MC算法由于考虑了节点活跃度和节点副本数，除了在延时方面比其他传统算法要略高之外，其他性能均优。
参考文献：
[1]Spyropoulos T，Psounis K，Raghavendra C S.Spray and wait：an efficient routing scheme for intermittently connected mobile networks.ACM SIGCOMM Workshop on Delay-Tolerant Networking （WDTN’05），2005：252-259.
[2]Zhang X，Neglia G，Kurose J F.Performance modeling of epidemic routing. Computer Networks，2006（51）：2867-2891.
[3]Krifa A，Barakat C，Spyropoulos T.Optimal buffer management policies for delay tolerant networks.IEEE SECON，2008：260-268.
[4]Erramilli V，Chaintreau A，Crovella M.Diversity of forwarding paths in pocket switched networks.ACM SIGCOMM IMC，2007：161-174.
[5]朱敬.延迟容忍网络路由协议的研究[D].中南大学，2009：43-44.
作者简介：赵红敏（1978-），女，河南郑州人，讲师，硕士，研究方向：无线网络协议分析。
作者单位：中南林业科技大学 计算机与信息工程学院，长沙 410004
基金项目：湖南省高等学校科学研究项目（项目编号：11C1306）。