自适应喷雾聚焦机会网络路由算法

【摘要】针对现有喷雾路由算法不能依据实际情况动态调整消息拷贝数，而导致资源浪费的问题，提出一种自适应喷雾聚焦路由算法ADPSF。ADPSF依据节点密度估算消息拷贝数，依据相遇概率历史信息选择中继节点和分配消息副本数。仿真试验表明，ADPSF算法在保证消息交付率和时延的情况下有效降低网络开销。

【关键词】机会网络；喷雾聚焦路由；节点密度；相遇概率

1.引言

机会网络[1]泛指由于结点稀疏、移动、能量限制或通信链路差等原因导致通信结点间可能在大部分时间内不存在完整的端到端的通信路径的移动自组网，在野生动物监测、车载网络、偏远乡村网络和手持设备网络等方面有广阔的应用前景，对实现普适计算有重大意义，成为近年来无线网络研究的一个热点[2]。

机会通信机制无法直接使用传统的路由技术，给机会网络路由带来巨大挑战。机会路由以“存储-携带-转发”的模式实现[1，2]，近年来已取得一些研究成果：在无法获取网络拓扑的情况下，洪泛类路由如Epidemic[3]是最简单有效的方法，端到端的时延较小，但在全网中广播消息增加了网络负载；PROPHET[4]算法改变了消息无目的的扩散，依据结点和其它结点的相遇概率选择中继；基于副本限制的洪泛方法Spray and wait[5]有效的减少了网络开销，但在等待阶段没有利用更可能接近目标结点的通信机会；Spray and focus[6]改变了文献[5]的被动等待，而是将消息不断的传向效用值较高的结点，从而提高了算法性能。

喷雾类算法不能依据实际情况动态调整消息拷贝数，导致消息转发具有一定的盲目性。算法ADPSF（Adaptive Density-based and Probabilistic Spray and Focus Routing）由中继节点依据当前节点密度动态设置消息副本数，并且依据节点相遇历史估计相遇节点与目的节点的相遇概率，选择概率值大于一定阈值的节点作为中继节点，该概率值也将作为两个节点在分配消息副本数时的依据。由于消息副本数依据网络情况动态设置，避免了消息冗余度，减少了网络负载，并且按照相遇概率选择中继和分配消息副本数，有效提高了消息投递率，减少了迟延。

2.网络模型

传统网络通信一般假设至少存在一条完整的端到端的链路，而机会网络允许出现网络分割，通信的源节点和目的节点可以是不连通的，利用节点间的移动带来的隐藏带宽使用“存储-携带-转发”的路由模型。

文章假定网络中有M个节点，节点通信半径为R，节点移动模型按照随机路点移动模型RWP(Random Way-Point mobility model)，并且节点移动服从独立同分布(IID)，节点相遇时间服从指数分布。

5.结论

ADPSF算法兼顾了喷雾算法的优越性，并且利用节点密度合理动态调整消息副本数，改进了喷雾类算法在消息源点设置固定消息副本的弊端，有效降低了消息的冗余的，降低了网络负载。算法利用节点相历史预测节点再次相遇的遇概率，并且以此为参数选择中继节点和进行消息副本数的分配，有效改善了消息转发的盲目性，充分利用了和目的节点相遇概率较高的节点，提高了投递率和减少了迟延。

参考文献

[1]Pelusi L,Passarella A,Conti M.Opportunistic networking:data forwarding in disconnected mobile ad hoc networks[J].Communications Magazine,2006,44(11):134-141.

[2]熊永平,孙利民,牛建伟等.机会网络[J].软件学报.2009,20 (1):124-137.

[3]Amin Vahdat,David Becker.Epidemic routing for partially connected ad hoc networks,CS-2000-06[R].Durham NC:Department of Computer Science,Duke University,2000.

[4]Lindgren A,Doria A,Schelén O.Probabilistic routing in intermittently connected networks[J].ACM SIGMOBILE Mobile Computing and Communications Review,2003,7(3):19-20.

[5]Spyropoulos T,Psounis K,Raghavendra CS.Spray and wait:An efficient routing scheme for intermittently connected mobile networks:Proc.of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking,2005[C].Philadelphia:ACM,2005:252-259.

[6]Spyropoulos T,Psounis K,Raghavendra CS.Spray and focus:Efficient mobility-assisted routing for heterogeneous and correlated mobility:Proc.of the IEEE PerCom Workshop on Intermittently Connected Mobile Ad Hoc Networks,2007[C].Washington:IEEE,2007.

[7]E.Hyyti?,et al.,"Spatial node distribution of the random waypoint mobility model with applications,"IEEE Transactions on Mobile Computing,pp.680-694,2006.

[8]A.Keranen,et al.,"The ONE Simulator for DTN Protocol Evaluation,"in SIMUTools'09:2nd International Conference on Simulation Tools and Techniques,Rome,2009.

作者简介：

刘艳玲（1980—），女，硕士，助理实验师，研究方向：计算机网络与通信。

姚建盛（1980—），男，在读博士研究生，讲师，主要研究方向：计算机网络与通信，移动计算。