论文摘要
与互联网（Internet）的倍受关注不同,许多工业用途的专用网络离人们的视线比较远,但是它们在人们生活中发挥的作用却非常重要,例如道路监测网络、灾难发生地的临时通信网络等。这类网络的绝大部分都有这些特征:以无线电波为载体、节点能力受限、节点移动频繁、通信环境恶劣等。在这类网络里,用于Internet的协议很难正常工作,于是人们提出延时容忍网络（DTN:Delay-Tolerant Network）的概念来描述这类网络,并努力为之建立一套协议标准。在本论文中,DTN被定义为一种抽象的网络模型,它不是针对某一个特定的网络的每个层面,相反,它关注具有延时容忍（Delay-Tolerant）特性的所有网络。延时容忍是指网络协议能够在某些极端情形下仍然能够工作而不至于崩溃;所谓极端（Challenging）情形是指节点之间信道非常不稳定、高不对称,节点处理能力多样,网络整体拓扑不稳定,经常出现长时间的分割,业务分布不可预测等,其中网络拓扑的不稳定是主要特征。从本质上说,DTN否定了传统网络模型中的一个根本前提——在路由期间或者数据包传递期间,存在一条或多条从源端到目的端的路径。这个前提隐含在传统路由协议中,即便是以节点动态性为主要背景的MANET（Mobile Ad hoc Network）的代表路由协议AODV（Ad-hoc On-demand DistanceVector）协议,其路由发现过程也必须在存在路径的条件下完成。和众多自组织类网络一样,DTN的核心问题是路由。DTN对传统路由中“路由期间存在从源端到目的端的路径”这一假设的否定,其实是重新定义了路径的概念。在传统网络中,甚至包括MANET,虽然考虑的拓扑的动态性,但是拓扑的稳态持续时间相对于数据包的RTT（Round Trip Time）来说还是还是要高很多;这样,在一次数据投递过程中,拓扑是静态的,路径是与时间无关的。而DTN下,数据包每转发一次之后,网络的拓扑可能已经改变,网络中有的链路已经不存在了,同时又有新的链路建立;这样,从整体看来,路径在时间的维度上是有纵深的,即DTN路径中的每一条链路只有在数据包位于该链路的两端的节点上时该链路依然存在时才是有效链路。在这个基础上,对于路由算法而言,其输入已经不再是一个静态的无向图了,而是一个随时间变化的图,其输出也变成以（链路,时间）二元组为基本元素的序列了。针对这个变化,人们提出了空-时图（Space-Time Graph）来描述DTN的拓扑。在空-时图中,网络中的节点处于很多个层中,每一层代表了一个时刻的拓扑,数据包可能的传递路径就是从第一层的源节点开始逐层往下（沿时间方向）直到遇到目的节点。本论文的研究重点是DTN的路由。就路由算法所需耍的路由信息的不同,DTN的路由协议可以分为两类:需要先验知识的的路由协议和不需要先验知识的家路由协议。先验知识的引入是DTN区别于传统网络模型的另一个重要标志。这里的先验知识是网络全局信息的一部分。在传统网络中,路由算法依赖于当前的网络状况,而DTN则还要依赖于将来的网络状况。因为网络状态相对稳定,传统网络中,当前的网络状况一般是通过路由信息交互协议获取的过去某个时刻的网络状况的预测得到的。DTN需要未来较长时间内的网络状况,仅仅通过对过去状况的简单预测并不准确,因此需要需要引入先验知识。在研究了MANET,WSN等网络路由协议的基础上,本文主要对DTN的路由研究作出了如下贡献:着眼于路由算法的信息集中最重要的参数——延时,建立了DTN中数据包的单跳延时模型。把延时作为选择最佳路径的标准可以减少数据包在网络中的驻留时间,减少网络缓存的消耗,反过来增加网络的容量。在DTN的研究中延时的构成以及其量化的分析还没有涉及。本文给出了单跳的范围,即链路上的延时模型,指出延时构成的几个基本量,即传输延时、排队延时、等待链路建立延时和传播延时。为了分析这几个参量的相互关系,把链路作为服务窗建立排队模型,提出了一种新的“带随机休假的非空竭排队系统”,利用排队论的分析方法,对队列长度、排队延时进行随机分解,最后得到队长和延时的分布函数,以及它们与业务分布等参数的数学期望之间的关系。最后通过仿真证实了实际测量值和计算值之间有很高的拟合度,在一定精度下本文的分析结果可以成立。在标准Earliest Delivery算法的基础上,把先验知识的准确性考虑进去,提出AED（Adaptive Earliest Delivery）算法。Earliest Delivery算法只具有理论上的意义,它给出了一种很好的描述DTN路由问题的方式;但是在实用性方面,它对先验知识过高的需求造成实现的困难。但是,从另一个方面来看,现实中存在这一些可以预先知道链路容量函数的场景,例如卫星通信;这时Earliest Delivery算法可以提供更好的路由效果,但是,现实中预知的链路容量函数总是存在误差,如何衡量这种误差,以及如何使Earliest Delivery算法在误差下也能够有较好的性能就成为了本文的一个研究内容。首先,建立误差模型,从理论上分析丢包概率与误差强度的关系,给出了表达式;然后,把误差的标准差作为参数去修正延时,就是AED算法。仿真表明新的算法对误差的容忍能力有明显提高。提出一种基于模板运算的运动模式识别框架PM3D,并提出基于运动模式的路由模型。运动模式是用来描述节点（群）的运动规律的概念,但是本文中的运动模式不关注物理的参数,而是宏观上的模式;这种模式可以从网络的空-时图的各元素（只考虑0和1,也就是通和断）之间的位置关系中反映出来。一种基于模板运算的机制PM3D被用来从空-时图中识别这些运动模式,并用一个统一的数据结构——访问列表（VL:Visit List）来存储。运动模式的引入并不依赖于具体的路由算法,但是需要在路由决策时加入对VL的应用,即需要一个接口让路由算法来访问VL,并从中获得必要的信息以辅助决定下一跳。仿真结果表明PM3D能够识别出运动模式,并且运动模式能够反映出网络拓扑的变化趋势,提高了数据投递率。