机会网络应用在偏远地区的仿真研究

龚丁海，黄晓航，谭松鹤

(河池学院 1.数学与统计学院;2.计算机与信息工程学院，广西 宜州 546300)

0 引言

机会网络［1］是一种不需要源节点和目的节点之间存在完整路径，利用节点移动带来的相遇机会实现网络通信的、时延和分裂可容忍的自组织网络［1－2］。机会网络以“存储－携带－转发”的机制进行消息的传送，主要应用于缺少通信基础设施、网络环境恶劣等场合，如袖珍型交换网络，偏远地区互联网无线接入等［2］。DakNet项目［3］是在印度偏远地区部署机会网络，以便为乡村地区提供通信连接;类似的还有Saami-NetworkConnectivity项目［4］，Tier项目［5］和 Wizzy系统［6］。基于机会网络的特性和机会网络在偏远地区应用的潜力，本文通过设定一个类似于偏远地区特性的网络场景，对机会网络几种典型的路由协议在该场景中的性能、特点进行分析比较，以评价各路由算法在该场景的应用。

1 机会网络路由协议

1.1 直接传输协议(DirectDelivery)

DirectDelivery［7］是典型的单副本路由协议，也是最简单的路由机制。该路由协议由源节点携带消息移动，直到遇到目的节点，将消息转发给目的节点。

1.2 传染转发协议(Epidemic)

Epidemic［8］本质上是一种洪泛，其基本思想是网络中两个相遇的节点均会交换相互没有的消息。节点间足够的交换，理论上让每个非孤立的节点将收到所有的数据包，能最大化数据包传输的成功率，减少传输延迟［8］。但在网络资源受限的实际网络中，会由于洪泛而导致网络中消息副本数量增多而消耗网络资源。

1.3 FirstContact协议

FirstContact［9］是一种单副本路由协议，源节点将消息转发给第一个遇到的节点，携带该消息的节点继续将消息转发给它第一个遇到的节点，如此反复，直到消息转发给目的节点。

1.4 MaxProp算法

Maxprop［10］协议在Epidemic的基础上进行了改进，改进之处在于:源节点为消息设定有效期TTL，在转发过程中，当消息的有效期到了，或者节点收到一个ack消息，或者节点的数据缓存区被装满时，节点将丢弃该消息。Maxprop能够避免每个消息都被泛洪到全网，减少了开销;但消息有效期的合理设置有一定难度［2］。

1.5 Prophet协议

Prophet［11］是基于概率的路由协议，每个节点估计到达其他节点的相遇概率，概率值随节点间相遇而升高，不相遇时则随时间递减，节点利用概率传递性来更新与其他节点之间的可达概率，从而获取与目标节点的相遇概率。

1.6 SprayAndWait协议

SprayAndWait［12］协议通过设定每个消息在网络中的副本数来控制洪泛的程度。该协议分为两个阶段，在Spray阶段，源节点将在网络中产生L份副本扩散到L(L＞1)个中继节点;在Wait阶段，若在Spray阶段没有发现目的节点，那么包含消息的节点通过直接传输的方式把信息传送到目的节点。SprayAndWait协议包含有Binary模式和非Binary模式。在Binary模式下，源节点将一半数据包发送给遇到的中继节点，自己留下一半数据包;随后源节点和中继节点重复进行上述过程，直到所有节点中只有一个数据包时，节点转入Wait阶段，采用直接传输给目的节点。

2 仿真场景设置

本文选用ONE仿真器(The Opportunistic Network Environment Simulator)［13］进行仿真。在仿真过程中使用ONE仿真器自带的芬兰首都赫尔辛基地图场景［14］。仿真时间为12 h，区域范围为4 500×3 400，数据包大小为(10 kB，1 MB)，数据包产生频率为(25，35)s。仿真模拟携带蓝牙设备的行人、摩托车、小汽车和公共汽车等四种类型共310个节点的移动场景，其中行人270，摩托车20，小汽车8，公共汽车12。各移动节点的特征如表1所示。

表1 各移动节点特征

各移动节点的移动模型中，行人1的移动选择RWP(Random Waypoint)模型随机生成目标位置坐标;摩托车、小汽车、公共汽车使用基于地图的MRM(Map Route Movement)模型;行人2使用基于地图的最短路径移动模型SPMBM(Shortest Path Map－BasedMovement)模型。

3 仿真结果分析

仿真以网络中消息的生存期和消息数量即网络流量为可变参数，分析以上两个可变参数对各路由算法传输成功率、路由开销、传输延迟和缓存时间等4个特性。

3.1 消息生存期对路由协议的影响

3.1.1 传输成功率

图1显示，当消息TTL较小时，各协议传输成功率较低，随着消息TTL的增长，各路由算法的传输成功率均有增长，其中MaxProp和SprayAndWait协议增加尤为显著，而DirectDelivery和FirstContact由于是单副本消息传递，消息TTL对传输成功率的影响不大，且消息传输成功率不高［15］。当消息TTL增长到一定程度后，各路由协议传输成功率增长趋缓，这说明在一定场景下，提高消息TTL到一定值后并不能显著提高消息的传输成功率。当消息TTL到300 min后，Epidemic和Prophet协议随消息TTL值增长，其传输成功率呈现下降趋势，这是因为当消息TTL增长到一定值时，由洪泛引起冗余的消息副本长时间占据网络节点的内存空间，使节点无法存储自身生成的或从其他节点接收到的消息，导致消息传输成功率开始下降［16］。

3.1.2 路由开销

路由开销反映了消息转发过程中对网络的负担，开销率越大越容易造成网络拥塞［17］。图2显示了各路由协议消息TTL对路由开销的影响。由于DirectDelivery协议，只有当携带消息的源节点遇到目的节点时，消息才会的转发，因此其开销率总是为0。除此外，随着消息TTL的变化，各协议中的路由开销也随之发生变化。其中MaxProp和Spray And Wait协议的路由开销会随消息TTL的增加而降低并趋向于维持一个相对稳定的范围。当消息TTL到达300min后，Epidemic和Prophet协议由于消息副本数的增加导致开销显著增加。

图1 消息生存期对传输成功率的影响

图2 消息生存期对路由开销的影响

图3 消息生存期对平均传输延迟的影响

3.1.3 平均传输延迟

图3表明消息的TTL对消息的平均传输延迟产生的影响较大。当消息的TTL达到一定值后，消息传输延迟的增长趋于缓和，以MaxProp为例，当消息的TTL值达到500 min时，其消息平均传输延迟基本上没有变化，已经保持相对稳定的平均传输延迟。因为MaxProp协议在消息的TTL到了，或者节点收到一个ack消息，或者节点的数据缓存区被装满时，节点将丢弃该消息。因此当消息的TTL值到达一定值后，其对Max-Prop协议中的消息传输延迟影响很小。

3.1.4 平均缓存时间

图4表明，消息的TTL对各路由协议中消息的平均缓存时间影响各异。其中影响较大的是 DirectDelivery和SprayAndWait，后者是因为在Wait阶段会采取与前者一致的转发策略，携带消息的节点会等待目的节点的出现，直到遇到目的节点。Epidemic和Prophet协议中，当消息的TTL增加时，消息在节点上的存储时间也相应地增加。但当消息的TTL继续增加时，由于洪泛产生的消息副本增多，节点因存储空间不足而删除大量的数据报文，使得数据报文平均存储时间下降。FirstContact协议总是将消息转发给第一个遇到的节点，因此其消息的平均缓存时间维持在一个相对较低且稳定的范围，消息的TTL对其平均缓存时间影响不显著。

3.2 网络流量对路由协议的影响

在表1设定的场景中，以不同的网络流量进行仿真，分析网络流量对各路由协议的影响。根据消息生存期对各路由算法影响的分析，仿真中选定300 min作为消息的生存期。仿真表明，网络流量的增大对各路由算法的4个特性的影响各异。

网络流量对单副本机制路由算法的传输成功率DirectDelivery和FirstContact影响不大;而对其他算法影响较大。网络流量较小时，MaxProp的传输成功率要好于其他协议;当网络流量增大时，Epidemic、MaxProp、Prophet和SprayAndWait的传输成功率逐渐降低，网络流量增大到一定程度时，四个协议的传输成功率的差距逐渐缩小。

SprayAndWait和DirectDelivery的路由开销保持在一个相对稳定的范围，变化不大，这说明以上两个协议的路由开销与网络流量基本无关，这是因为SprayAndWait协议在Wait阶段采取与DirectDelivery类似的转发机制:等待与目的节点相遇，然后转发消息。Prophet由于采用的是有限制的多路由复制，网络流量增大时，消息转发的次数会增大，其路由开销与Epidemic协议逐渐接近。

网络中的流量对各路由协议平均延迟均有影响，但影响不明显。协议中是采用多副本的复制转发还是单副本的转发影响消息的传输延迟。

DirectDelivery和FirstContact算法的平均缓存时间与网络流量无关，其他算法随网络流量增大而逐渐趋于稳定。

以网络流量为可变因素的仿真说明:是否采用多副本的路由转发，对传输成功率和传输延迟的影响较大;是采用单跳转发和还是多跳的转发策略，会对路由开销有影响。

图4 消息生存期对平均缓存时间的影响

4 结束语

为探索机会网络在偏远地区的应用，本文通过设定特定的网络场景，对机会网络中几种典型的路由协议进行仿真，分析各路由协议在该场景中随消息TTL和网络流量的变化情况，综合各路由算法在消息传输成功率、路由开销、平均传输延迟、平均缓存时间的表现，得出如下结论:

(1)MaxProp和SprayAndWait协议随消息生存期的增加具有较高的传输成功率和较低的路由开销;网络流量较大时，SprayAndWait协议要优于MaxProp协议;当网络中节点的缓存空间有限时，则MaxProp协议要优于SprayAndWait协议。

(2)多副本的路由机制在传输成功率和传输延迟方面要优于单副本的路由机制。

在以后工作中，将深入研究对SprayAndWait协议和MaxProp协议的改进，进一步提高机会网络在该类场景中的传输成功率、减少消息传输的延迟。

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

［2］任智，黄勇，陈前斌.机会网络路由协议［J］.计算机应用，2010，30(3):723－728.

［3］Pentland A，Fletcher R，Hasson A.DakNet:Rethinking c0nnectivity in developing nations［J］.Computer，2004，37(1):78 －83.

［4］Avri D，Mana U，Durga PP.Providing connectivity to the Saami nomadic community［C］//In Proc.of the 2nd Int＇l Conf on Open Collaborative Design for Sustainable Innovation，Bangalore:IEEE press，2002.

［5］Brewer E Tier project.2006.［DB/OL］［2014 －05 －10］http://tier.cs.berkeley.edu/wiki/Home.

［6］Wizzy Project.［EB/OL］［2014 －08 －01］http://www.wizzy.org.za/.

［7］PELUSI L，PASSARELLA A，CONTI M.Opportunistic netuorking:data fornarding in disconnected mobile Ad Hecnetworks［J］.Communicatins，2006，44(1):134 －141.

［8］Apoorva J，Konstantinos P.Perfomance Analysis of Epidemic Routing Under Contention［C］//Proc.of the 2006 International Conference on Wireless Communications and Mobile Computing，Vancouver:ACM Press，2006:539 －544.

［9］Sushant Jain，Kevin Fall，Rabin Patra.Routing in a delay tolerant network［C］//In SIGCOMM ＇04:Proceedings of the 2004 conference on Applications，technologies，architectures，and protocols for computer communications，New York:ACM，2004:145－ 158.

［10］Burgess J，Gallagher B，Jensen D，et al.Maxprop:routing for vehicle－ based disruption tolerant networks［C］.Washington:Proc IEEE Infocom，2006:1－11.

［11］Lindgren，Doria A，Schelèn O.Probabilistic routing in intermittently connected networks［J］.ACM SIGMOBILE Mobile Computing and Communications，2003，7(3):19 －20.

［12］Spyropoulos T，Psounis K，Raghavendra C S.Spray and Wait:An Efficient Routing Scheme for Intermittently Connected Mobile Networks［C］//Proc.of the 2005 ACM SIGCOMM Workshop on Delay Tolerant Networking，Phiatelphia:ACM Press，2005:252 －259.

［13］KER NEN A，OTT J，K RKK INEN T.The ONE simulator for DTN protocol evaluation［C］ //Simutools ＇09:Proceedings of the 2nd International Conference on Simulation Tools and Techniques，Rome:Acm Press，2009:1 －10.

［14］CAO Y，SUN Z L，AHMAD N，et al.A mobility vector based routing algorithm for delay tolerant networks using history geographic information［C］//Proceedings of the International Conference on Wireless Communications and Networking.Washington DC:IEEE Communications Society，2012:2 757 －2 762.

［15］吴大鹏，杨正川，刘乔寿，等.带有相遇预测的自适应路由机制［J］.重庆邮电大学学报(自然科学版)，2013，25(3):368－371.

［16］王蓬.机会网络中带有确认机制的多副本路由协议的研究与实现［D］.上海:华东师范大学，2010.

［17］钱景辉.一种机会网络中节点转发策略的改进［J］.微电子学与计算机.2013，30(1):5－7.