DTN路由研究现状概要课件.ppt

1、DTNDTN路由路由研究现状研究现状OUTLINEDTN介绍单拷贝路由多拷贝路由最新研究进展仍然存在问题DTN介绍在TCP/IP协议簇中，消息转发需要先寻路再转发前提是要存在端到端路径现有路由协议的研究都基于这一假设在挑战性网络环境下，这一前提不能得到保证军用Ad hoc网络、星际网络、灾难救援等端到端路径不再可靠，无法直接采用传统的路由方式DTNRG（Delay-Tolerant Network Research Group）星际网络延迟容忍网络体系结构、实现等DTN2平台美国国防部国防先进研究计划署（Defense Advanced Research Projects Agency，DAR

2、PA）军事网络中断容忍网络（ Disruption-Tolerant Network ）先存储后转发（Store and forward）机制STORE AND FORWARD类似于电子邮件的传递方式发email时不需要收件人在线通过邮件服务器中转如果节点能像邮件服务器一样保存消息，则可以为其它节点转发消息源节点-中间节点，中间节点-目的节点通过中间节点将消息逐跳向目的节点转发不需要存在从源节点到目的节点的端到端路径DTN路由分类按照是否有先验知识零知识路由部分知识路由全知识路由按照是否对消息进行复制单拷贝路由网络中只存在消息的一份拷贝多拷贝路由网络中存在同一消息的多份拷贝单拷贝路由直接传输直

3、接传输(Direct Transmission)是一种最简单的单拷贝路由方式由源节点持有消息，直到与目的节点相遇，才将消息转发给对方源节点必须要与目的节点相遇才能完成投递完全依赖于节点直接相遇投递成功率很低，延时也很大单拷贝路由首次联系首次联系(First Contact)算法持有消息的节点将消息传输给最先遇到的节点首次联系算法不再依赖于目的节点直接相遇，通过多次转发完成投递由于最先遇到的节点是无法预知的，首次联系算法的消息投递方式具有一定的盲目性，因此投递成功率也不高Sushant Jain, Kevin Fall, Rabin Patra. Routing in a Delay Toler

4、ant NetworkC. ACM SIGCOMM, Portland, Oregon, USA, 2004.单拷贝路由随机路由随机路由(Random Routing)算法并非只在遇到目的节点时才传输消息当节点A遇到节点B时，会以一定的概率（概率p0）将本节点所持有的消息发送给对方随机路由方式的投递成功率与概率p相关在没有任何先验知识的情况下，无法选取符合网络实际情况的概率p随机路由方式的投递成功率仍然很低T. Spyropoulos, K. Psounis, C. Raghavendra. Single-Copy Routing in Intermittently Connected Mob

5、ile NetworksC. IEEE Conference of Sensor and Ad Hoc Communications and Networks, Santa Clare, CA, USA, 2004.直接传输、首次相遇、随机路由都属于零知识路由算法为了进一步提高投递成功率，需要利用一定的先验知识节点与其它节点的联系机会（联系信息）节点的缓存占用情况（队列信息）消息的产生规律（流量需求）等如果路由算法需要以上所有的先验知识，则称为全知识路由，而如果只需部分先验知识，则称为部分知识路由全知识路由全知识路由的典型代表为线性规划（Linear Programming，LP）算法需要获知

6、节点间的联系信息、队列信息和网络中的流量需求根据线性方程求解转发决策由于利用了各种先验知识，能较为明显地提高投递成功率获取这些先验知识的开销过大，在实际网络中很难实现部分知识路由部分知识路由是全知识路由和零知识路由的折中典型部分知识路由算法最早投递（Earliest Delivery，ED）算法用加权图描述网络，利用Dijkstra算法求最短路径链路延时采用瞬时值最小期望延时（Minimum Expected Delay，MED）算法用链路延时的均值（等待时间的期望值）表示加权图中边的权值本地队列最早投递（ED with Local Queue，EDLQ）全网队列最早投递（ED with Al

7、l Queue，EDAQ）多拷贝路由网络分割现象频繁出现仅保持消息的一份拷贝，可能会出现消息到达分割网络的边缘而无法继续传递的情况即使采用先验知识对中间节点进行筛选，单拷贝路由的投递成功率仍然不高在完成消息转发后并不删除缓存中的数据，而是继续保持该消息的备份可以在遇到其它节点时继续将消息散发出去网络中可以同时存在同一消息的多份拷贝通过消息的复制来提高投递成功率多拷贝路由感染路由感染路由（Epidemic Routing）算法节点将消息复制给所有遇到的所有节点用更多的传输次数换取投递成功率网络开销极大，依赖于节点的缓存空间和通信带宽在网络规模和数据流量都不大时，感染路由能明显提高投递成功率随着网

8、络规模的扩大和数据流量的增加，消息数量将急剧上升由于节点的缓存空间和通信带宽有限，数据丢失现象将十分严重，导致投递成功率明显下降A. Vahdat and D. Becker, Epidemic Routing for Partially-Connected Ad Hoc Networks, Technical Report CS-2000-06, Duke University, 2000.多拷贝路由PROPHET基于概率的多拷贝路由算法PRoPHET减小泛洪开销当节点A与节点B相遇时，按照两个节点能将该消息投递到目的节点的概率来确定是否进行复制若p(b,d) p(a,d) ，则节点A将该消

9、息复制给节点B投递概率的计算节点相遇时更新A. Lindgren, A. Doria, and O. Schelen, Probabilistic Routing in Intermittently Connected Networks, ACM SIGMOBILE Mobile Computing and Communications Review, vol. 7, pp. 19-20, 2003.( , )( , )(1( , )oldoldinitp a dp a dp a dP多拷贝路由PROPHET投递概率的计算衰减节点A与D长时间不相遇传递( , )( , )koldp a dp

10、a d( , )( , )(1( , )( , )( , )oldoldp a dp a dp a dp a bp b dMaxProp算法同样采用控制复制概率的方式来改善消息的复制规模这类算法的主要思想通过对复制概率的控制来调节消息复制的规模，从而在投递成功率和开销之间达到均衡当网络规模增大时，消息复制的规模仍然会增加仍然是泛洪方式J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine, MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks, in IEEE INFO

11、COM Barcelona, Spain, 2006, pp. 1-11.多拷贝路由SPRAY AND WAIT基于拷贝配额的Spray and Wait算法消息投递分为喷射（Spray）和等待（Wait）两个阶段在喷射阶段，源节点将消息复制给一定数量L的节点在等待阶段，这些收到消息的节点等待与目的节点相遇，并将消息投递给对方网络中最多只能存在消息的L份拷贝配额消息的复制规模不会随着网络规模的变化而变化，因此可扩展性更好T. Spyropoulos, K. Psounis, and C. S. Raghavendra, Spray and Wait: An Efficient Routing

12、Scheme for Intermittently Connected Mobile Networks, in ACM SIGCOMM, Philadelphia, Pennsylvania, USA, 2005.源端喷射源节点每遇到一个节点，都将消息复制一份给对方，并将本节点中该消息的拷贝配额减1L份拷贝被发送给最先遇到的L个节点二分方案节点遇到其它节点后，将消息复制给对方并将拷贝配额的一半分给对方，直到拷贝配额减小到1SPAY AND FOCUS在Spray and Wait算法的第二个阶段，收到消息的节点只有在与目的节点相遇后才将该消息发送出去这一过程与直接传输（Direct Trans

13、mission）一样，严重依赖于节点的运动如果节点的运动范围过小，可能无法直接与目的节点相遇，导致消息传递无法完成Spray and Focus改变第二阶段的传输方式，节点不再等待与目的节点相遇，而是采用其它方式的单拷贝路由降低对节点运动性的依赖T. Spyropoulos, K. Psounis, and C. S. Raghavendra, Spray and Focus: Efficient Mobility-Assisted Routing for Heterogeneous and Correlated Mobility, in IEEE International Conferen

14、ce on Pervasive Computing and Communications Workshops, White Plains, NY, USA, 2007.问题开销和投递成功率的均衡拷贝配额的控制对节点运动特征的利用缓存管理多拷贝路由的特殊性质配额的影响拷贝配额的控制多阶段扩散对Spray and Wait的改进多阶段扩散的DTN路由算法，其目的是最小化平均拷贝数量第一次复制时，采用小于L的配额，过一段时间后继续复制关键问题在于怎样分阶段各阶段持续的时间各阶段的配额E. Bulut, Z. Wang, and B. K. Szymanski, Cost-Effective Mult

15、iperiod Spraying for Routing in Delay-Tolerant Networks, IEEE/ACM Transactions on Networking, 2010.利用节点运动特征社交图用于路由用本地收集的过去的联系信息汇集成一个社交图（Social Graph），利用社会图将信息投递到距离目的节点更近的位置节点行为信息来预测未来联系机会，从而做出转发决策顶点之间的边可以表示过去的相遇信息。社交图中的一条边表示这两个节点经常相遇。将社交图用于辅助信息投递SimBet节点自然地分布在移动性相关的社会中，例如班级、工作、家庭等“中心”或“有优越的社会关系”的节点被

16、选为消息的中继节点，直到到达一个与目的节点拥有很多邻居节点的节点T. Hossmann, T. Spyropoulos, F. Legendre. Know Thy Neighbor: Towards Optimal Mapping of Contacts to Social Graphs for DTN RoutingC. IEEE INFOCOM, San Diego, CA, USA, 2010.利用节点运动特征EBR多拷贝路由对消息进行复制是为了使消息能从多条路径同时传递，从而提高投递成功率在分配拷贝配额时，到目的节点的投递概率高的节点应该获得较大的拷贝配额Spray and Wait

17、的两种拷贝配额分配方案都没有考虑不同节点间投递概率的差别EBR在分配拷贝配额时考虑节点的活跃程度S. C. Nelson, M. Bakht, and R. Kravets, Encounter-Based Routing in DTNs, in IEEE INFOCOM, Rio de Janeiro, Brazil, 2009, pp. 846-854.活跃的节点（与其它节点相遇概率较大的节点）将获得较大的配额值CWC:当前时间单元内遇到的节点数量Mi:节点A对该消息的权值当节点A与节点B相遇时，分配给节点B的权值由于活跃的节点更有机会遇到其它节点，因此赋予活跃节点较大的拷贝配额有利于消息

18、投递利用节点运动特征进一步考虑使用节点的活跃程度有一定的局限性活跃的节点并不一定能遇到目的节点根据节点能投递到目的节点的概率分配当节点n向节点i复制消息时，分配给节点i的拷贝配额需要维护到其它节点的投递概率用一定的开销换取更高的投递成功率适用于规律运动节点较多的情况,( , )( , )nt nit nr T r FLpi jLpr jDTN多拷贝路由的缓存管理节点通信带宽和缓存空间有限传输顺序通信带宽限制丢包顺序缓存空间限制FIFO等传统的缓存管理方式不适用于多拷贝路由消息具有拷贝配额消息的重要程度与传统网络有所区别影响消息重要程度的因素拷贝配额生存时间在允许出现l份拷贝的情况下，在给定时间

19、t内，能达到的投递成功率在节点i不传输消息m的情况下，消息m的投递成功率的期望值节点i处的消息m能达到的投递成功率为增益1ltdpe ( ),( )1mL li Td ipme ( ),( )1mmli td ipme ,( ,)11( ) 1( )( )d id id ig i mpmpmpm 仍然存在的问题L的选择根据节点数量、流量选择L缓存溢出的预先避免在分配拷贝配额时，避免选择缓存紧缺的节点需要得到缓存的状态变化节点自私行为都希望其它节点转发自己的消息由于资源紧缺，这一问题更为严重Q. Li, S. Zhu, and G. Cao, “Routing in Socially Selfish Delay Tolerant Networks,” in IEEE INFOCOM, 2010B. B. Chen and M. C. Chan, MobiCent: a Credit-Based Incentive System for Disruption Tolerant Network, in IEEE INFOCOM, 2010.THE ENDTHANK YOU!