信息安全专业毕业学位论文-DTN网络拥塞控制策略研究.docxVIP

中国科学技术大学硕士学位论文DTN网络拥塞控制策略研究 作者姓名： 杨奇才学科专业： 信息安全导师姓名： 俞能海 教授 完成时间： 二一二年五月八日University of Science and Technology of ChinaA dissertation for masters degree Research on Congestion Control Strategies in Delay-Tolerant NetworkAuthors Name： Qicai YangSpeciality： Information SecuritySupervisor： Nenghai YuFinished time: May 8th, 2012中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名：_ 签字日期：_中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中国学位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。公开 保密（_年）作者签名：_ 导师签名：_签字日期：_ 签字日期：_摘要摘 要延迟容忍网络是一种信息在传递过程中会经历长时延或可变时延、间断连接性和高误码率的新型无线网络，主要应用于星际网络、传感器网络、战地网络、城市DTN网络等。延迟容忍网络的网络特性导致延迟容忍网络的路由和拥塞控制都面临新的挑战。延迟容忍网络研究组DTNRG提出了新的Bundle层协议以应对这些新的挑战。国内外对其路由算法研究的比较多，而拥塞控制策略的研究近几年研究也逐渐增多了。本论文主要研究DTN拥塞控制策略，论文的主要研究工作和创新点如下：1. 介绍延迟容忍网络的发展历程，研究国内外关于延迟容忍网络的相关项目，主要调研和分析延迟容忍网络的路由算法和拥塞控制策略。2. 提出了一种适用于稀疏Ad Hoc网络的DTN拥塞缓存管理策略GPE，其使用全局参数估算网络的平均延迟和平均跳数等参数，进而计算每个包的保存权值。在网络拥塞时，优先丢弃保存权值较小的数据包。实验结果表明，与传统的丢弃最早接收包的策略相比，GPE很好地提升了网络交付率。3. 提出了一种适用于稀疏Ad Hoc网络的DTN拥塞缓存管理策略APE，与GPE不同，APE完全利用节点自身信息计算数据包的保存权值，在网络拥塞时，优先丢弃保存权值较小的数据包。实验结果表明，与传统的丢弃最早接收包的策略相比，APE很好地提升了网络交付率。与GPE策略相比，APE策略具有更好的实用性和灵活性。4. 提出了新的适用于稀疏Ad Hoc网络的DTN拥塞避免策略GPEA和APEA。实验结果表明，这两种拥塞避免策略在保证其他网络性能参数良好的同时，大幅度降低了网络开销比率。与GPEA策略相比，APEA策略具有更好的实用性和灵活性。关键词：拥塞控制 丢包策略 拥塞避免 容断容延迟网络 94AbstractAbstractDelay Tolerant Network(DTN) is characterized by intermittent connectivity, long delays and often constrained bandwidth. DTN represents a broad class of networks such as interplanetary internets, under water sensor networks, and vehicular networks. The characteristics make routing and congestion control become challenges.The DTNRG developed the Bundle Protocol (BP) to meet these challenges. Then, more and more new routing protocols and congestion control strategies were studied by researchers. This dissertation focuses on congestion control strategies of DTN. The main content and the original techniques are as follows:1. Introduced the history of DTN, and presented some research projects on DTN. Then we researched the DTN routing algorithms and DTN congestion control strategies.2. Proposed a new congestion control strategy named Global Parameter Estimation based congestion control strategy (GPE). The GPE used global parameters to calculate the priority of every package. When network become congested, the package with the lowest priority would be dropped first. The experiments showed that the GPE can improve the delivery rate of network a lot.3. Proposed a new congestion control strategy named Adaptive Parameter Estimation based congestion control strategy (APE). Unlike the GPE, the APE just used the information contained in the node itself to calculate the priority. The experiments showed that the APE strategy can improve the delivery rate of network a lot. Compared to the GPE, the APE had better practicality and flexibility.4. Proposed two new congestion avoidance strategies, named Global Parameter Estimation based congestion Avoidance strategy (GPEA) and Adaptive Parameter Estimation based congestion Avoidance strategy (APEA). The experiments showed that they could reduce the overhead ratio of network a lot. Compared to the GPEA, the APEA had better practicality and flexibility.Key Words: congestion control，packet drop policy，congestion avoidance, delay and disruption-tolerant network目 录目 录第1章 绪论11.1 研究背景和研究意义11.1.1 延迟容忍网络的研究背景11.1.2 延迟容忍网络拥塞控制研究意义21.2 研究现状21.3 研究工作及结构安排61.3.1 主要研究工作61.3.2 本文的组织结构和安排7第2章 延迟容忍网络基础92.1 延迟容忍网络的协议架构92.1.1 延迟容忍网络的协议栈简述92.1.2 Bundle协议数据处理流程102.2 延迟容忍网络的路由研究112.2.1 单拷贝路由112.2.2 多拷贝路由122.2.3 路由对拥塞控制的影响162.3 ONE机会网络仿真平台162.3.1 ONE的组成模块172.3.2 ONE的运行模式182.3.3 ONE的实验结果参数202.4 本章小结21第3章 稀疏Ad Hoc网络场景的DTN拥塞缓存管理研究233.1 引言233.2 适于典型稀疏Ad Hoc场景的DTN拥塞控制策略GPE243.2.1 GPE拥塞控制策略设计243.2.2 GPE拥塞控制策略仿真实验263.3 自适应的稀疏Ad Hoc网络的DTN拥塞控制策略APE343.3.1 APE拥塞控制策略设计343.3.2 APE拥塞控制策略仿真实验363.4 本章小结51第4章 稀疏Ad Hoc网络场景的DTN拥塞避免策略研究534.1 引言534.2 适于典型稀疏Ad Hoc网络的DTN拥塞避免策略GPEA544.2.1 GPEA拥塞避免策略设计544.2.2 GPEA拥塞避免策略的仿真及结果554.3 自适应的稀疏Ad Hoc网络的DTN拥塞避免策略APEA654.3.1 APEA拥塞避免策略设计654.3.2 APEA拥塞避免策略的仿真和结果664.4 本章小结79第5章 总结和展望815.1 论文总结815.2 未来工作展望82参考文献83致 谢87在读期间发表的学术论文与取得的其它研究成果89图目录图 1. 1论文主要研究工作 7图 1. 2论文框架结构 7图 2. 1延迟容忍网络协议栈 9图 2. 2 Bundle层数据处理流程 10图 2. 3典型算法Epidemic路由扩散1 13图 2. 4典型算法Epidemic路由扩散2 13图 2. 5 典型算法Epidemic扩散路由消息传递过程 14图 2. 6 ONE图形界面 18图 2. 7 ONE批处理模式 19图 3. 1负指数函数 25图 3. 2 GPE和传统DropOld交付率对比 27图 3. 3 GPE和传统DropOld平均延迟对比 27图 3. 4 GPE和传统DropOld平均跳数对比 28图 3. 5 GPE和传统DropOld网络开销比率对比 28图 3. 6 对网络交付率的影响 29图 3. 7 对网络平均延迟的影响 30图 3. 8 对网络平均跳数的影响 30图 3. 9 对网络开销比率的影响 31图 3. 10节点稀疏程度对GPE交付率的影响 32图 3. 11节点稀疏程度对GPE平均延迟的影响 32图 3. 12节点稀疏程度对GPE平均跳数的影响 33图 3. 13节点稀疏程度对GPE网络开销比率的影响 33图 3. 14 APE和GPE、DropOld交付率对比 36图 3. 15 APE和GPE、DropOld平均延迟对比 37图 3. 16 APE和GPE、DropOld平均跳数对比 38图 3. 17 APE和GPE、DropOld网络开销对比 38图 3. 18 C1对交付率影响 39图 3. 19 C1对平均延迟影响 40图 3. 20 C1对平均跳数影响 40图 3. 21 C1对网络开销影响 41图 3. 22 C2对交付率影响 41图 3. 23 C2对平均延迟影响 42图 3. 24 C2对平均跳数影响 42图 3. 25 C2对网络开销影响 43图 3. 26 节点数对APE交付率的影响 44图 3. 27 节点数对APE平均延迟的影响 44图 3. 28 节点数对APE平均跳数的影响 45图 3. 29 节点数对APE网络开销的影响 45图 3. 30 场景大小对APE交付率的影响 46图 3. 31 场景大小对APE平均延迟的影响 47图 3. 32 场景大小对APE平均跳数的影响 47图 3. 33 场景大小对APE网络开销的影响 48图 3. 34 节点移速对APE交付率的影响 49图 3. 35 节点移速对APE平均延迟的影响 49图 3. 36 节点移速对APE平均跳数的影响 50图 3. 37 节点移速对APE网络开销的影响 50图 4. 1接收概率p示意图 55图 4. 2 GPEA和GPE、DropOld交付率对比 56图 4. 3 GPEA和GPE、DropOld平均延迟对比 57图 4. 4 GPEA和GPE、DropOld平均跳数对比 58图 4. 5 GPEA和GPE、DropOld网络开销对比 58图 4. 6拥塞门限对交付率的影响 60图 4. 7拥塞门限对平均延迟的影响 60图 4. 8拥塞门限对平均跳数的影响 61图 4. 9拥塞门限对网络开销的影响 61图 4. 10节点数对GPEA交付率的影响 62图 4. 11节点数对GPEA平均延迟的影响 63图 4. 12节点数对GPEA平均跳数的影响 63图 4. 13节点数对GPEA网络开销的影响 64图 4. 14 APEA和APE、DropOld交付率对比 66图 4. 15 APEA和APE、DropOld平均延迟对比 67图 4. 16 APEA和APE、DropOld平均跳数对比 67图 4. 17 APEA和APE、DropOld网络开销对比 68图 4. 18 APEA和GPEA交付率对比 69图 4. 19 APEA和GPEA平均延迟对比 69图 4. 20 APEA和GPEA平均跳数对比 70图 4. 21 APEA和GPEA网络开销对比 71图 4. 22节点数对APEA交付率的影响 72图 4. 23节点数对APEA平均延迟的影响 72图 4. 24节点数对APEA平均跳数的影响 73图 4. 25节点数对APEA网络开销的影响 73图 4. 26场景大小对APEA交付率的影响 74图 4. 27场景大小对APEA平均延迟的影响 75图 4. 28场景大小对APEA平均跳数的影响 75图 4. 29场景大小对APEA网络开销的影响 76图 4. 30节点移速对APEA交付率的影响 77图 4. 31节点移速对APEA平均延迟的影响 77图 4. 32节点移速对APEA平均跳数的影响 78图 4. 33节点移速对APEA网络开销的影响 78表目录表 1. 1 DTN发展历程表 1表 1. 2国家自然科学基金项目中DTN相关项目 3表 1. 3拥塞控制研究方向 4表 2. 1 ONE实验结果主要参数 21表 3. 1 GPE策略实验仿真参数 26表 4. 1 GPEA策略实验仿真参数 56第1章 绪论第1章 绪论随着移动通信网络和便携无线通信设备的发展，延迟容忍网络（Delay Tolerant Network,，DTN）具有越来越好的应用前景，其是未来网络形态发展的重要方向。DTN路由算法和拥塞控制策略都对其网络性能有重大影响，二者共同影响网络的交付率、端到端平均延迟、端到端平均跳数和网络平均开销等网络性能指标，本文主要关注拥塞控制策略的研究。DTN网络的拥塞控制与传统网络的有很大不同，DTN网络的网络拓扑容易改变，具有长或可变延迟，其泛洪路由算法会大大增加网络中数据包的转发次数和副本数，所以DTN网络拥塞控制要从能适应DTN网络特性的角度出发，来设计新的拥塞控制策略。本章1.1节介绍DTN网络的研究背景和意义，1.2节介绍DTN网络拥塞控制的国内外研究现状，1.3节介绍本文的研究工作和论文框架。1.1 研究背景和研究意义1.1.1 延迟容忍网络的研究背景上个世纪90年代起，随着无线网络协议的繁荣发展，移动自组织网络（Mobile Ad hoc network，MANET）逐渐成为网络方面研究的热点，与此同时，NASA实验室开始了星际网络（Interplanetary Internet，IPN）项目的研究，延迟容忍网络的研究就起源于移动自组织网络和星际网络的研究。延迟容忍网络具有网络间断连接、长或可变延迟、高误码率和节点资源有限等特征。延迟容忍网络研究的发展历程如表1.1描述：表 1. 1 DTN发展历程表时间DTN历史事件20世纪90年代无线网络协议被广泛应用，促进了移动自组织网络领域的发展1998年NASA实验室开始了星际网络IPN项目的研究，由于真正的星际网络成本极高，随后有很多研究人员将IPN的概念引入地面传感器网络，在传感器网络中可以比较容易地进行合乎实际的实验2002年延迟容忍网络研究组（Delay and Disruption-Tolerant interoperable Networking Research Group，DTNRG）成立，专门研究延迟容忍网络 2003年Kevin Fall在SIGCOMM03会议上发表文章，正式提出延迟容忍网络的概念 2004年美国国防部高级研究计划局（the Defense Advanced Research Projects Agency，DARPA）提出中断可容忍网络概念（Disruption-Tolerant Networking），让延迟容忍网络的概念变得更为广泛2007年IETF在2007年给出了延迟容忍网络体系架构的RFC 4838 ，同年又给出了关于延迟容忍网络协议数据单元Bundle协议规范的RFC 5050，Bundle层通过建立“存储-等待-转发”机制，使得延迟容忍网络中的节点在间断连接性的网络环境下可以通信 DTN协议架构虽然确立了，但架构内的路由算法、拥塞控制和安全问题仍需要进行大量的研究，所以DTN网络方向的发展一直受到各国研究人员的关注，其研究成果也在增多。随着国外对延迟容忍网络的重视，国内也有相关项目专门研究DTN网络的关键技术，比如在车载容迟网络场景下的DTN路由算法和其他关键技术研究的项目。1.1.2 延迟容忍网络拥塞控制研究意义随着移动通信网络和便携无线通信设备的发展，延迟容忍网络具有越来越好的应用前景，深空通信是开发太空资源必须保障，无线自组织网络和传感器网络对灾难预防、环境监测等方面有重要的作用，战地的实时自组织网络具有很大的灵活性和可变性，这些都是延迟容忍网络的前景之所在。由于DTN前景极佳，世界上的研究机构和人员对DTN的研究日益深入。路由算法和拥塞控制策略都是DTN网络的关键技术，二者共同影响网络的交付率、端到端平均延迟、端到端平均跳数和网络平均开销等网络性能指标，本文主要研究其拥塞控制策略。DTN网络的容断容延迟特性使得其拥塞控制策略与传统网络的有很大不同，因为DTN网络中经常不存在端到端的连接，所以传统的端到端的TCP拥塞控制策略不适用。所以研究新的适用于DTN网络的拥塞控制策略很有意义。1.2 研究现状随着DTN的应用前景越来越好，国内外很多研究机构都开展了DTN关键技术的研究项目，表1.2给出了近年来我国国家自然科学基金项目中与DTN相关的项目 。表 1. 2 国家自然科学基金项目中DTN相关项目批准号/代码项目名负责人依托单位起止时间60773168/f020303容延迟移动传感器网络中通信协议的研究周激流四川大学200801-20101260803009/f020206多策略的容迟移动网络端到端数据传输控制研究肖明军中国科学技术大学200901-20111260803159/f020808延迟容忍网络中基于移动代理的路由策略郭辉中国石油大学（北京）200901-20111260972021/F0102延迟容忍网络容量优化方法研究陆建华清华大学201001-20121260940031/F020809容延迟移动传感器网络中时钟同步机制的研究周激流四川大学201001-20101260903158/F020809延迟容忍移动传感器网络中信息收集协议的研究龚海刚电子科技大学201001-20121260903004/F020304基于容迟与容断网络的安全路由协议研究刘涛北京科技大学201001-20121260933011/F0208移动容迟网络理论与关键技术研究孙利民中国科学院软件研究所201001-20131261071128/F010104移动容迟网络中基于节点移动性的可靠混合多播路由李晖浙江大学201101-20131261003241/F020808容迟网络中的节能路由协议的研究刘聪中山大学201101-20131261072063/F010206车辆自组织网络中基于实时预报的容迟/容断路由理论与关键技术研究舒炎泰天津大学201101-20131261003220/F020802移动容迟网络的路由与拥塞控制方法研究余辰华中科技大学201101-20131261003218/F020805容迟网络的安全与激励机制的研究朱浩瑾上海交通大学201101-20131261171065/F010201车载移动容迟网络的连接、容量与延迟特性研究金德鹏清华大学201201-20151261100213/F020806容迟移动自组织网络中基于安全的自然协作技术研究王堃南京邮电大学201201-20141261170231/F020803具有延迟约束的无线网络资源控制机制研究卢汉成中国科学技术大学201201-20151261103245/F020809无线传感器网络中基于移动Sink的低能耗、低延迟数据收集协议研究梁俊斌广西大学201201-20141261103226/F020809面向城市环境的延迟容忍传感器网络数据分发与路由算法研究王晓敏电子科技大学201201-201412由表1.2可知国内对DTN网络的研究在逐渐增多，而且很多是正在进行的项目。DTN的拥塞控制策略的实现与传统网络不同，因为其连接不稳定，可能会断开。而且泛洪路由会导致网络中的数据副本数目爆发，路由算法也决定了拥塞控制策略的特殊性。国外研究机构和人员主要研究的DTN拥塞控制的相关内容如表1.3所示：表 1. 3 拥塞控制研究方向拥塞控制方向主要思想典型文献内容预防拥塞策略利用限制转发手段，控制网络中的消息转发，尽可能减轻网络的负荷2010年，E. Coe, C. Raghavendra 等人提出一个采用发放令牌方式的拥塞避免策略，整个网络拥有固定个数的令牌，预先给节点发相同数目的令牌，每转发一个数据包的同时要向接收方转交一个令牌。令牌数为零则不能发包，但可以向附近的节点借用令牌 。流量控制策略调整相邻节点传输的数据流在2008年， F. De Rango等人在深空通信的环境下，提出一种异步拥塞控制机制解决链路饱和、缓存溢出以及无用的重传问题，以提升网络整体的性能 。节点缓存管理在网络比较堵塞时，以不同的缓存管理策略，提高网络的传输性能。主要基于丢弃缓存队列中最早或最晚接收的包，丢弃生存时间最长或最短的包 A. Krifa提出一个联合调度和丢包策略，用以改善网络的数据包成功到达率和网络延迟性能 。L. Yun等人提出一种AFNER拥塞控制策略，其主要是基于每个数据包的转发次数决定缓存中的数据包的丢弃顺序 。国内对DTN网络的缓存管理和拥塞避免策略有不少的研究。2010年，国内Lei Yin和Hui-mei Lu等人对包含失当行为节点的DTN网络提出激励机制的拥塞控制策略IMRASFC，该算法首先初始化多路径路由以减轻链路负载，接着更新规则以激励失当行为节点存储转发消息，最后选择拥有可用空间的可选节点进行消息存储转发 。Daowen Hua 和Xuehui Du等人提出了一种新的基于路径避免的拥塞避免机制，该机制优化了节点存储的管理并将节点状态划分为正常状态、拥塞临近状态和拥塞状态，根据节点不同状态使用各自不同的策略以避免拥塞 。Daowen Hua 和Xuehui Du等人还提出了基于分布式存储的DTN拥塞控制机制，该机制在节点变得更拥塞时，拥塞节点只传输部分数据给其邻居，以利用DTN网络分布存储的能力，在拥塞问题解决时采用之前正常的传输方式以避免数据丢失 。刘期烈和潘英俊等人提出了一种在传染路由协议下基于复制率的拥塞控制算法，在拥塞时，节点估算每个数据包的复制率，优先丢弃复制率最大的数据包，以减轻网络堵塞 。王贵竹和王炳庭等人利用应答机制丢弃网络中已经有副本达到目的地的相同数据包副本，减少冗余数据包，在拥塞时其优先丢弃副本数目最小的数据包 。徐昌彪和王宇提出了一种基于服务等级的拥塞控制机制，其为后续高优先级的数据包预留缓存空间，以减轻网络拥塞 。陶勇和龚正虎在文献 中对DTN网络拥塞控制从基于节点级拥塞、链路级拥塞和区域级拥塞三个方面进行了总结。中国科学技术大学的马柯博士 在路由和包丢弃策略上都进行了相关的研究，其中在拥塞控制方面提出了HWDP（Historical based Weighted Dropping Protocol）丢包协议，其通过估算节点相遇时间间隔和网络中包副本数的方法决定拥塞时的丢包序列，其实验结果对数据包到达目的地的交付率有了显著的提升。王文柏硕士 对拥塞控制模型和丢包、发包策略都进行了详细的研究，其首先对城市DTN网络场景中的拥塞控制模型进行了研究和分析，提出了WDCCS（Weight and transfer Delay based Congestion Control Strategy）拥塞控制模型，利用包的剩余生存时间、包的大小、节点缓存的大小、转发包的耗时估计等参数，决定拥塞时的丢包策略和队列中发包优先序列，其模型对交付率和延迟都有一定程度的改善。其次，对稀疏Ad Hoc网络场景提出了基于副本数并结合节点相遇交付概率的拥塞控制包丢弃策略CWDS（Copies based Weighted Dropping Strategy），CWDS通过统计跳数来估算消息数据包在网络中的副本数并结合节点相遇交付概率确定包丢弃策略，显著提升了该DTN网络场景的包到达目的地的成功交付率，由于CWDS的延迟结果不佳，其又提出了改进的丢包策略TCWDS（TTL and Copies based Weighted Dropping Strategy），加入了对包生存时间和节点相遇时间的改进，其实验结果表明TCWDS的包到达目的地的成功交付率和平均延迟都比较好。本文主要关注于延迟容忍网络由于长延迟和泛洪路由等带来的队列堆积、网络交付率低、网络开销大等问题，调研现有的研究结果，分析延迟容忍网络的传输特性，提出新的拥塞控制策略。本文是在参考文献22的研究工作基础上，对拥塞控制策略做了进一步的研究，除了提出新的适应典型稀疏Ad Hoc网络场景的基于缓存管理的拥塞控制策略，还提出了适应Ad Hoc网络场景变化的自适应的拥塞管理策略，并提出了全新的DTN网络拥塞避免策略，该拥塞避免策略大大降低了网络开销，节省了很多的网络资源。1.3 研究工作及结构安排 本文主要分析延迟容忍网络的传输特性，根据传输特性设计适应DTN网络场景的拥塞控制策略，主要包括拥塞控制中的缓存管理和拥塞避免策略的研究和实验。本节介绍了论文的主要研究工作和本文的框架结构。1.3.1 主要研究工作论文主要对DTN网络拥塞控制的缓存管理和拥塞避免策略进行研究，研究流程见图 1.1，论文主要内容如下：l 具有DTN网络特性的Ad Hoc网络场景的拥塞缓存管理策略研究研究DTN网络拥塞控制策略，并分析其规律和特点，设计适用于典型稀疏Ad Hoc网络的新型拥塞控制策略，在仿真平台ONE上实现并验证其效率；研究稀疏Ad Hoc网络场景参数设置变化情况下拥塞控制策略效率的变化规律，设计适于场景变化自适应的拥塞控制策略，并进行实现和验证。 l 具有DTN网络特性的Ad Hoc网络场景的拥塞避免策略研究研究DTN网络拥塞避免策略，并分析其规律和特点，避免很大几率会被丢弃的包的传输，设计适用于典型稀疏Ad Hoc网络的新型拥塞控制策略，并设计自适应的DTN网络拥塞避免策略，在仿真平台ONE上实现并验证。 图 1. 1论文主要研究工作1.3.2 本文的组织结构和安排图 1. 2论文框架结构本论文框架结构如图1.2所示，后面章节主要内容如下：1) 第2章研究延迟容忍网络基础 ，2.1节介绍延迟容忍网络协议架构，分析基于Bundle协议的延迟容忍网络协议架构，2.2节介绍延迟容忍网络基本的路由算法，2.3节介绍仿真实验平台ONE的相关内容。2) 第3章主要研究具有DTN特性的Ad Hoc网络场景的拥塞缓存管理策略，首先提出新的典型场景下的基于全局估值的拥塞控制策略GPE（Global Parameter Estimation based congestion control strategy），改善数据包的成功交付率和转发跳数，接着提出适用性更广的自适应的拥塞控制策略APE（Adaptive Parameter Estimation based congestion control strategy）。3) 第4章主要研究具有DTN特性的Ad Hoc网络场景的拥塞避免策略，提出新的典型场景下的基于全局估值的拥塞避免策略GPEA（Global Parameter Estimation based congestion Avoidance strategy）和适用性更广的自适应的拥塞避免策略APEA（Adaptive Parameter Estimation based congestion Avoidance strategy），在保障网络交付率的同时，很大程度减少网络开销，节省网络资源。4) 最后第5章是本文研究工作的总结和展望。在参考文献之后，是本论文的致谢以及本人在攻读硕士期间参与的研究工作和成果。第2章 延迟容忍网络基础第2章 延迟容忍网络基础本章介绍延迟容忍网络的基础知识，首先在2.1节介绍延迟容忍网络的协议架构和其核心的Bundle协议。DTN网络拥塞控制和路由算法共同影响网络的传输性能，因此在2.2节中介绍现有的DTN网络路由算法。2.3节介绍论文采用的实验仿真平台ONE，介绍其组成模块和运行模式。2.1 延迟容忍网络的协议架构2.1.1 延迟容忍网络的协议栈简述在延迟容忍网络体系结构中，Bundle协议一般处在应用层和传输层之间。现有的Bundle层之下的传输层协议主要有TCP协议、UDP协议、Saratoga协议、LTP协议、TCP集中层协议。不同的传输层协议主要应用于不同的网络场景中。其中Saratoga协议、LTP协议主要应用于空间延迟容忍网络组网通信，而且适应的链路协议主要为空间链路协议。而TCP协议、UDP协议主要适用于地面延迟容忍网络组网通信。Bundle协议为不同类型的延迟容忍网络组网通信提供一个通用的解决办法。通过存储转发模式进行组网通信。Bundle协议具有逐跳的传输确认机制和可选的端到端的传输确认机制，并规定了一个简单但实用的安全模型。图2.1为现有延迟容忍网络的协议体系构架。图 2. 1延迟容忍网络协议栈DTN协议架构最特别的就是Bundle层的引入，这是与传统网络的不同。Bundle层就是用于处理数据包的存储转发的。由于Bundle层传输的特殊性，其还需要适应长或可变延迟的路由算法和拥塞控制策略。Bundle层之下的协议层与实际的DTN场景相关，由于场景的复杂性，在必要时，Bundle层也需具备一定的协议转换能力。2.1.2 Bundle协议数据处理流程图 2. 2 Bundle层数据处理流程图2.2为Bundle协议中的消息数据包处理流程。Bundle协议的工作原理为存储转发模式。在Bundle层，当有数据包到达时，Bundle层通常需要根据路由算法作出转发判断。如果数据包可以立即投递出去，则进行转发。否则就存储该包，等待合适机会再去投递。当数据包存储数目太多，填满了缓存空间时，若要再接受 数据包，必须丢弃缓存中部分数据包，直到空间足够接纳新数据包为止，这个由缓存管理策略决定。当相邻节点通信时，将根据路由算法转发相应的数据包。这就是Bundle层的数据流程。2.2 延迟容忍网络的路由研究延迟容忍网络路由算法是Bundle层的一部分，它负责确定将缓存中的数据包转发到哪一条传输链路。本节主要内容是介绍国内外已有延迟容忍网络路由技术，现有延迟容忍网络路由按照是否采用网络场景的先验知识可以分为：零知识路由、部分知识路由和全知识路由。如果按照是否对消息进行复制，路由算法可以分为单拷贝路由和多拷贝路由，单拷贝路由是指网络中只存在消息的一份拷贝的路由算法，而目前主流的是在网络中数据包存在多个副本的方式，即多拷贝路由，本小节按照单拷贝路由和多拷贝路由的划分，介绍现有的DTN路由算法。2.2.1 单拷贝路由单拷贝路由在转发数据包时，网络中只存在消息的一份拷贝，其路由算法按照是否采用网络场景的先验知识，可以分为三类：零知识单拷贝路由、部分知识单拷贝路由和全知识单拷贝路由 。零知识单拷贝路由包括三种路由方式，首先是最简单的直接传输（Direct Transmission）方式，源节点一直保存消息，随着节点不停地运动，直到和目的节点相遇，才将消息转发给对方。这种传输方式必须要源节点和目的节点相遇，才能完成消息投递，其消息转发完全依赖节点的相遇，消息投递的成功率很低，延迟也很大。其次是首次联系（First Contact）算法，持有消息的节点将消息转发给最先遇到的节点，这种算法是利用多次转发，将消息转发到目的节点。由于其最先遇到的节点是无法预知的，所以该算法消息转发的方式具有一定的盲目性，其投递成功率也比较低。第三种是随机路由（Random Routing）算法，持有消息的节点A遇到某一节点B时，会以一定的概率p（p0）将消息发送给节点B。随机路由方式的投递成功率依赖转发概率p，在没有网络先验知识的情况下，难以设置适应网络场景的概率p，所以该路由算法的投递成功率也比较低。为了进一步提高消息的成功投递率，需要利用一定的网络先验知识，可以利用的先验知识包括：节点与其他节点的联系机会（即联系信息）、节点的缓存占用情况（即队列信息）、消息的产生规律（决定网络中的流量需求）等。如果设计的路由算法需要这些全部的先验知识，那么就称之为全知识路由，如果只需要部分的先验知识，则称之为部分知识路由。全知识的单拷贝路由算法的典型代表是线性规划（Linear Programming，LP）算法，LP算法需要获知节点间的联系信息、队列信息和网络中的流量需求，然后根据线性方程求解转发决策。LP算法由于利用了很多先验知识，所以较为明显地提升了消息投递的成功率，然而实际网络中如果要获取这些先验知识，需要很大的额外开销，所以其实用性不够好。部分知识的单拷贝路由算法利用了部分的先验知识，实用性要优于全知识的路由算法。典型的有四种，第一种最早投递（Earliest Delivery，ED）算法，其用加权图描述网络，利用Dijkstra算法求最短路径，其链路延迟采用瞬时值。第二种是最小期望延时（Minimum Expected Delay，MED）算法，是对ED算法的改进，使用链路延迟的均值表示加权图中的边的权值，其能最大程度降低平均等待时间。第三种是本地队列最早投递（ED with Local Queue，EDLQ），也是对ED算法的改进，加入了结合本地队列的代价函数，其在路由的每一跳重新计算最佳路由。第四种是全网队列最早投递（ED with All Queue，EDAQ），其使用的是结合全网队列的代价函数，并且在消息的传输路径上为该消息保留存储空间，其在消息的路由选择以后不需要在每一跳都重新计算路由。2.2.2 多拷贝路由多拷贝路由算法是针对时断时连的Ad Hoc网络场景提出来的，在这种部分连接的网络场景中，如果仅有一份消息拷贝，消息可能会到达分割网络的边缘，出现无法继续投递消息的情况。在这种场景中，即使采用先验知识选择中间路由节点，上一节的单拷贝路由算法的投递成功率仍然不高。因此多拷贝路由就在部分连接、长延迟的Ad Hoc网络场景中得到了广泛的应用。多拷贝路由算法在完成消息转发后不会删除本节点缓存中的数据包，继续保存该消息，在遇到其他节点时，可以继续发送该消息，这样网络中就同时存在一个消息的多个副本，这类路由算法通过消息的复制提高投递成功率。下面介绍这些典型的多拷贝路由算法：Epidemic路由算法 、基于控制复制概率的PROPHET路由算法 和MaxProp算法 、基于拷贝配额的Spay and Wait路由算法 和利用节点运动特征的基于社交图的路 。Epidemic路由（1）路由思想Epidemic路由算法是源节点首先向其邻居转发消息数据包副本，接收到消息数据包的节点再向自己的邻居转发数据包副本，这样的转发过程会一直递归下去，直到数据包到达目的地为止。其中每个结点维护自己的摘要向量（Summary Vector，SV），摘要向量是对自己存储的所有数据包的摘要信息。相邻节点通信时互相通报各自的摘要向量，并在数据包转发后更新摘要向量。Epidemic路由的优势是路由过程不需要任何先验知识，递归转发简单也容易实现。然而其递归转发数据包副本的方式使得网络的数据包副本数目膨胀得很快。网络容易堵塞，所以需要好的缓存管理策略。（2）路由过程Epidemic 路由过程如下面两张图呈现，图2.3中，节点周围的圆圈代表节点通信范围，源节点S生成了消息数据包，目的地是较远处的节点D。由于节点分布比较分散，S和D之间没有可用的链路。因此S先后将消息数据包发给自己的邻居C1和C2。经过一段时间以后，如图2.4所示，C2运动到了C3附近，二者进入了可以通信的范围，C2将数据包转发给了C3。而C3正好也是目的节点D的邻居，之后C3将数据包转发给D，这样数据包就到达了目的地。图 2. 3典型算法Epidemic路由扩散1图 2. 4典型算法Epidemic路由扩散2Epidemic 路由中，相邻节点间的数据包转发不需要知道网络节点分布等先验知识，节点只要接收对方节点缓存中自己没有的数据包即可。每个结点维护自己拥有的数据包的摘要向量，摘要向量的通报和更新如图2.5所示，NodeA和NodeB通信时，NodeA将自己的摘要向量先发给NodeB，NodeB就将自己的摘要向量取非并和NodeA的摘要向量求与，这样得到NodeA拥有而NodeB没有的数据包列表，NodeB再向NodeA请求传输这些自己没有的数据包。然后NodeA将NodeB没有的数据包传输给NodeB，每成功传输一个数据包给NodeB，NodeB更新自己的消息摘要向量。图 2. 5 典型算法Epidemic扩散路由消息传递过程（3）优缺点Epidemic 路由不