基于ONE平台的机会网络路由协议仿真分析

王文涛，郑 芳，王奇枫，郭 峰

(中南民族大学计算机科学学院，武汉430074)

机会网络是移动自组织网络(MANET)的一个子类［1］，但又具有不同于传统移动自组织网络的特点.传统的MANET在传输用户数据之前，需要预先建立完整的端到端的通信链路.这种路由机制隐含了一个重要的假设:网络大部分时候是连通的，任一节点对之间存在至少一条完整的通信链路.然而在实际自组织网络应用中，例如用来实时监测道路交通状况的车载网络、由手机等大量移动通信设备组成的手持设备自组织网络、安装无线传感器节点于野生动物身上的野生动物追踪网络等，节点的移动性、节点稀疏分布、射频信号关闭以及障碍物的存在等因素都会导致网络部分通信连接处于断开状态［2］.为解决这个问题，机会网络应运而生，其许多概念源于早期的延迟容忍网络(DTN)［3］，它不需要源节点和目的节点之间存在完整链路，而是利用节点移动带来的相遇机会实现网络通信.

机会网络以“存储－携带－转发”的路由机制实现节点间的通信［4］.这种路由机制不同于传统的“存储－转发”路由机制，它增加了数据携带部分，在节点需要发送报文或是接收到来自其它节点的报文后，由于节点连接的间歇性特点，节点不能立即将报文转发出去，于是存储在缓存队列中，并且携带这些报文信息移动，若遇到在彼此通信范围的节点，则将其转发，直到目的节点接收到该报文.正是由于这种不需要事先建立转发路径的路由机制的特点，机会网络能够满足恶劣条件下的网络通信需要，处理网络中通信断裂和延时等问题［5］.基于这种路由机制特点的路由协议也相继被提出.本文通过ONE仿真平台设计适合于机会网络的仿真场景，并且对机会网络中典型路由协议进行了仿真分析，通过传输成功率、平均传输延迟和路由开销比率等3个路由性能指标比较并分析了不同网络环境因素对路由算法的影响、各种路由算法的优缺点及适用场景.

1 机会网络中路由算法

随着机会网络的不断发展，人们提出许多机会网络路由算法.文献［2，3］分别从不同角度对机会网络路由算法进行了分类.根据每个消息在网络中传播的副本数量，机会网络路由算法可分为单副本路由和多副本路由两类.单副本路由算法有Direct Delivery［6，7］、First Contact［8］等，该类路由协议在网络中仅存在一个消息副本.单副本路由算法的开销很小，但通常交付延迟较高，可靠性相对较低.多副本路由算法很多，如 Epidemic［9］、Spray and Wait［10］、PRoPHET［11］、MaxProp［12］等.多副本路由算法在同一时间网络中有多个节点携带同一消息的副本.由于机会网络动态变化，多副本路由算法增加了消息到达目标节点的概率，降低了交付延迟，但消耗了大量网络资源.多副本路由算法主要包括基于复制的路由算法、基于社会属性的路由算法和基于编码的路由算法.可参见文献［13］.

2 仿真实验

2.1 仿真环境设置

本文使用机会网络环境仿真器(ONE)［14］模拟行人携带蓝牙通信设备行走于城市场景中，模拟实验地图选择ONE自带的赫尔辛基城市地图.仿真默认参数设置如表1所示.在未加说明情况下，采用默认参数设置.

表1 仿真默认参数设置Tab.1 Simulation default parameter configuration

2.2 机会网络路由算法性能评价指标

在以上仿真环境下，我们选取传输成功率、平均传输延迟和路由开销比率三个主要的指标来评价和分析机会网络路由算法性能.

(1)传输成功率，是指在一定时间内成功到达目的节点报文数量总数与源节点发出的报文总数之比.传输成功率标志着路由算法成功转发报文到目的节点的能力，是重要的性能评价指标.

(2)平均传输延迟，是指报文从产生到被目的节点接收所需的平均时间.平均传输延迟小意味着路由算法传输能力强，传输效率高，网络资源占用少，网络资源利用率高.

(3)路由开销比率，是指网络中成功转发报文数量与目的节点接收报文数量的差值同目的节点接收报文数量的比值，路由开销比率说明了网络中一个报文成功传输到目的节点所需的平均传输次数.

2.3 仿真结果分析

本文分别对 Direct Delivery、First Contact、Epidemic、PRoPHET、MaxProp、Spray and Wait等路由算法进行仿真，并分析比较了这些算法在不同的移动模型、节点密度、报文传输速率、报文TTL值下报文传输成功率、报文平均传输延迟、报文路由开销比率的变化情况.

2.3.1 移动模型对路由算法影响

图1、图2和图3分别给出了在随机路径移动模型(RWP)、基于地图的随机移动模型(MBM)、基于地图的最短路径移动模型(SPMBM)三种不同移动模型下，各路由算法传输成功率、平均传输延迟、路由开销比率的变化情况.

图1 移动模型对传输成功率的影响Fig.1 Impact of the movement model on delivery ratio

图2 移动模型对平均传输延迟的影响Fig.2 Impact of the movement model on average delivery delay

图3 移动模型对路由开销比率的影响Fig.3 Impact of the movement model on routing overhead ratio

从图1可以看出，在SPMBM移动模型下，各路由算法传输成功率最高，MBM次之，RWP最低.原因在于RWP是随机移动模型，节点随机选择移动的方向、目的地，这将导致节点相遇概率低，网络中转发的报文总数少，同时这种随机性使得多数报文没有在消息生存时间(TTL)内达到目的节点而被丢弃，因此报文传输成功率低.MBM是基于地图的移动模型，节点随机选择地图中的路径进行移动，节点相遇概率高于RWP移动模型.SPMBM是基于地图的最短路径移动模型，该模型使用Dijkstra算法依据地图中点和路径信息计算出源节点和目标节点之间的最短路径，并令节点沿该路径移动，因此使得成功到达目的节点报文增加，报文传输成功率提高.从图2可以看出，除Direct Delivery算法外，其他算法在SPMBM移动模型下的平均传输延迟最低，在MBM下略高，在RWP下最高.图3表明，节点移动模型对Direct Delivery、First Contact和MaxProp算法的路由开销比率影响较小，Epidemic和PRoPHET算法的路由开销比率明显上升，Spray and Wait算法的路由开销比率明显下降.

2.3.2 节点密度对路由算法的影响

图4、图5和图6分别给出了在节点数为20，40，60，100，200，400，600 个时，各路由算法传输成功率、平均传输延迟、路由开销比率的变化情况.

由图4可以看出，节点密度较低时，各路由算法传输成功率差别不大，随着节点密度的增大，节点间的通信机会也相应增加，各路由算法的传输成功率均有所增大.其中MaxProp和Spray and Wait算法传输成功率增加较为显著，且传输成功率明显高于其他路由算法，当节点数为600个时，二者传输成功率均在80%左右.其他路由算法的传输成功率均在30%以下.由图5可知，MaxProp算法节点密度较大时，传输延迟有所下降，而其他路由算法的传输延迟均随着节点密度的增大而增大.由图6可知，节点密度较小时，各路由算法路由开销比率较小且无明显差别，当节点数超过200个时，Epidemic算法和PRoPHET算法路由开销比率急剧增加，而Direct Delivery算法、Spray and Wait算法基本没有变化.

图4 节点密度对传输成功率的影响Fig.4 Impact of the density of nodes on delivery ratio

图5 节点密度对平均传输延迟的影响Fig.5 Impact of the density of nodes on average delivery delay

图6 节点密度对路由开销比率的影响Fig.6 Impact of the density of nodes on routing overhead ratio

2.3.3 报文传输速率对路由算法的影响

图7、图8和图9分别给出了在报文传输速率为20，50，100，150，200，250 kbit/s时，各路由算法传输成功率、平均传输延迟、路由开销比率的变化情况.

图7 报文传输速率对传输成功率的影响Fig.7 Impact of the packet transmit speed on delivery ratio

图8 报文传输速率对平均传输延迟的影响Fig.8 Impact of the packet transmit speed on average delivery delay

从图7中可以看出，随着报文传输速率的增加，各路由算法的传输成功率也随之增加，原因在于机会网络通过节点相遇带来的机会进行报文转发，而两个节点的相遇时间是有限的，节点报文传输速率越快，成功转发的报文也越多，报文到达目的节点的概率增大，因此传输成功率增加.当报文传输速率较小时，报文传输速率对各个路由算法传输成功率的影响较为显著，当报文传输速率趋于较大值时，各路由算法的传输成功率逐渐趋于稳定.从图8中可以看出，Direct Delivery算法在报文传输速率较低时，平均传输延迟随着报文传输速率的增加而有所增加，其他几种算法的平均传输延迟均随着报文传输速率的增加而减少.从图9 中可以看出，First Contact、Epidemic、PRoPHET和MaxProp算法的路由开销比率均随着报文传输速率的增加而增加，Spray and Wait算法的路由开销比率则有所下降.

图9 报文传输速率对路由开销比率的影响Fig.9 Impact of the packet transmit speed on routing overhead ratio

2.3.4 报文TTL值对路由算法的影响

图10、图11和图12分别给出了在报文TTL值为30，60，120，180，240，300min 时，各路由算法的传输成功率、平均传输延迟、路由开销比率的变化情况.

图10 报文TTL值对传输成功率的影响Fig.10 Impact of the value of packet TTL on delivery ratio

图11 报文TTL值对平均传输延迟的影响Fig.11 Impact of the value of packet TTL on average delivery delay

图12 报文TTL值对路由开销比率的影响Fig.12 Impact of the value of packet TTL on routing overhead ratio

TTL值指的是报文生存时间，在节点缓存空间充足的情况下，报文TTL值的增加使得在一定时间内网络中被丢弃的报文减少，成功到达目的节点的报文增加，报文传输成功率也随之增加，如图10所示，其中MaxProp和Spray and Wait算法传输成功率远大于其他算法.但是，当报文TTL值过大时，也会使得节点缓存队列中的报文太多而导致拥塞，我们可以看到Epidemic和PRoPHET算法在TTL值大于120min时，传输成功率有所下降.从图11可以看出，各路由算法的平均传输延迟均随着TTL的增大而增大.图12表明，TTL 值对 Direct Delivery、First Contact、MaxProp 和Spray and Wait算法的路由开销比率影响不明显.而Epidemic和PRoPHET算法的路由开销比率随着TTL的增大而增大.

3 结束语

本文利用ONE仿真平台，从传输成功率、平均传输延迟和路由开销比率三个路由性能评价指标入手，仿真并分析了节点移动模型、节点密度、报文传输速率、报文TTL值对6种机会网络路由算法的影响.实验结果表明:节点移动模型、节点密度、节点报文传输速率和报文TTL值对各路由算法均产生显著影响.相比于RWP和MBM，SPMBM移动模型下各算法的传输成功率最高.当节点密度稀疏时，各路由算法性能差异不大;但当节点密度较大时，Spray and Wait和MaxProp算法传输成功率明显高于其他算法，说明Spray and Wait和MaxProp算法更能适应节点密集的网络环境.在节点报文传输速率增大的情况下，各路由算法的传输成功率增大，平均传输延迟减小.当报文传输速率增大到一定值时，各路由算法性能趋于稳定.报文TTL值的增大使得各算法的传输成功率增大，但对于Epidemic和PRoPHET算法，在TTL值较大时，传输成功率有所下降.在各个仿真环境下，Spray and Wait和MaxProp算法都具有较高的传输成功率，但Spray and Wait的路由开销远低于MaxProp算法.PRoPHET算法相对于Epidemic算法做了改进，通过估计节点间的传输概率值来判断是否转发报文，而在本文的仿真场景下，两个路由算法性能表现差异不大，PRoPHET算法并没有表现出明显的优势.Direct Delivery算法传输成功率不高，但其路由开销比率始终为零.First Contact传输成功率在各仿真环境下传输成功率最低，且路由开销比率较大.通过上述分析，Spray and Wait算法在多数仿真场景下具有传输成功率高和路由开销低的特点，但节点密度大时传输延迟高，而MaxProp算法的传输延迟不会随节点密度的增加而增加，进一步研究工作将结合Spray and Wait算法和MaxProp算法的优点，提出一种适合各种节点密度的高效路由算法.

［1］Soelistijanto B，Howarth M P.Transfer reliability and congestion control strategies in opportunistic networks:a survey［J］.Communications Surveys ＆ Tutorials，IEEE，2014，16(1):538－555.

［2］熊永平，孙利民，牛建伟，等.机会网络［J］.软件学报，2009，20(1):124－137.

［3］胡四泉，汪红兵，王俊峰.机会型网络研究综述［J］.计算机科学，2009，36(10):32－37.

［4］Poonguzharselvi B，Vetriselvi V.Survey on routing algorithms in opportunistic networks［C］//IEEE.ICCCI.Piscataway，NJ:IEEE，2013:1－5.

［5］孙践知.机会网络路由算法［M］.北京:人民邮电出版社，2013:1－2.

［6］Spyropoulos T，Psounis K，Raghavendra C S.Single－copy routing in intermittently connected mobile network［C］//IEEE.Sensor and Ad Hoc Communications and Network.Piscataway，NJ:IEEE，2004:235－244.

［7］Spyropoulos T，Psounis K，Raghavendra C S.Efficient routing in intermittently connected mobile networks:the single－copy case［J］.IEEE/ACM Transactionson Networking，2008，16(1):63－76.

［8］Jain S，Fall K，Patra R.Routing in a delay tolerant network［C］//ACM.SIGCOMM.New York:ACM，2004:145－158.

［9］Vahdat A，Becker D.Epidemic routing for partiallyconnected Ad Hoc networks［R］.Technical Report CS－200006，Durham:Duke University，2000.

［10］Spyropoulos T，Psounis K，Raghavendra C S.Spray and wait:an efficientrouting scheme forintermittently connected mobile networks［C］//ACM.SIGCOMM.New York:ACM，2005:252－259.

［11］Lindgren A，Doria A，Schel'en O.Probabilistic routing in intermittently connected networks［J］.ACM SIGMOBILE MobileComputingandCommunications Review，2003，7(3):19－20.

［12］Burgess J，Gallagher B，Jensen D，et al.MaxProp:routing for vehicle－based disruption－tolerant networks［C］//IEEE.INFOCOM.Piscataway，NJ:IEEE，2006:1－11.

［13］Socievole A，De Rango F.Evaluation of routing schemes in opportunistic networks considering energy consumption［C］//IEEE.Performance Evaluation of Computer and Telecommunication Systems.Piscataway，NJ:IEEE，2012:41－47.

［14］Ari K，Jörg O，Teemu K.The ONE simulator for DTN protocol evaluation［C］//ICST.Proceedings of the 2nd InternationalConference on Simulation Tools and Techniques.Brussels:ICST，2009:55－64.