容迟网络广义k选播路由资源分配模型

开篇：润墨网以专业的文秘视角，为您筛选了一篇容迟网络广义k选播路由资源分配模型范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：针对移动网络频繁中断和网络分割场景下的容迟网络（DTN）路由资源分配问题，提出广义k选播，其集合由接入路由器信息矩阵决定，以减弱DTN路由算法在接入时间上的概率不确定性，进而提出路由资源分配模型，据此在许可时间段内对k个接入路由器集合元素进行路由和资源分配，从而实现对未来k个目的地进行托管传送。NS2平台仿真实验表明，在业务流量过饱和区域，可获得延时和吞吐量等性能的近线性变化，总有效带宽利用率超过DTN多播路由方案的18%～20%，说明在拥塞环境下有较好的整体传输性能和鲁棒性。该模型适用于公共交通和物流等移动路径确定的车载网络环境，如搭配有效的路径预测算法，可扩展到一般环境。

关键词：容迟网络； 广义k选播； 移动互联网接入； DTN路由； QoS路由

中图分类号： TP393

文献标志码：A

Delay tolerant network routing resource allocation model on general k-anycast

ZHANG Yong-hui1， 2*， LIN Zhang-xi3， LIU Jian-hua1， LIANG Quan1

1.Key Laboratory for Automotive Electronics and Electric Drive of Fujian Province， Fujian University of Technology， Fuzhou Fujian 350118， China；

2.School of Information Science and Engineering， Central South University， Changsha Hunan 410083， China；

3.Rawls College of Business Administration， Texas Tech University， Lubbock Texas 79409-2101， USA

Abstract：

Concerning the routing resource allocation on Delay Tolerant Network （DTN）， general k-anycast was proposed for mobile network disruption and network segmentation scenarios. The access router information matrix was made to decide the general k-anycast sets in order to modify access time probabilistic uncertainty of DTN routing. Then routing resource allocation model was built. Whereby it can allocate routing and bandwidth resources between k eligible accesses routers in the access period， therefore， packets can be custody transferred simultaneously to multiple destinations. The platform simulation results on NS2 show that in the traffic supersaturated regions， its transmission performance such as delay and throughput can achieve nearly linear change， with more 18%-20% of the total effective bandwidth utilization than multicast DTN routing algorithm， which indicates that the model can achieve better transmission performance and robustness in congestion， and be applicable to the vehicle network environments with the regularly moving paths， such as public transportation and logistics. With effective path prediction algorithm， it can be further applied to the general environment.

英文关键词 Key words：

Delay Tolerant Network （DTN）； general k-anycast； mobile Internet access； DTN routing； Quality of Service （QoS） routing

0 引言

车载移动网络中网络中断和网络分割较常出现，而目前移动方案一般基于以网络连通性为前提的TCP/IP协议，在此场景中表现不佳[1]。容迟网络协议（Delay Tolerant Network， DTN）能较好地处理网络中断和较长时延造成的TCP丢包，从最先的深空网络，扩大到目前的车载移动网络[2]、无线传感器网络、口袋交换网络等应用。

DTN研究一开始以路由问题为主，使用网络资源无限性假定，资源分配不是其核心关注点，未能有效解决全网资源的使用效能问题[3]3605。其后资源分配慢慢得到重视，2007年Balasubramania等[4]提出DTN路由可以作为资源分配问题来解决，到目前为止，该文已被他引480次，相关研究达到980余篇，可见DTN的资源分配逐渐成为核心问题。

目前DTN资源分配机制按节点掌握的信息可分为随机性和确定性两种路由资源分配机制[5]。

随机性路由资源分配假定将来的移动和连接是动态和不确定的，主要策略有流行性（或传染性）分配、按经验或历史分配以及基于编码路由分配等。多数研究是根据各方面因素提出函数来决定传输概率，再按概率分配资源，通常实行多副本分配策略[6]，并建立有相应的丢弃制度。这类研究实际上是以空间换取时间[7]，由多处副本增加传输路径，最大化了消息传输的可能性。优点是无需详细的网络知识，缺点是较多占用了网络资源[8]。车载移动网络中快速移动节点的自由度有限，可视为路径可预测环境，未来的移动和主要连接是已知的，随机性路由资源分配无法充分利用这些条件，多副本的存储分配制度和副本丢弃制度会使得本来稀缺的移动接入资源过度消耗[9]。

确定性路由资源分配假定未来移动和连接是确定或可预测的，按可掌握的节点移动规律、通信机会、网络拓扑等先验知识的增加，可依次分为最小期望延迟算法（Min Expected Delay，MED）、最早分发算法（Earliest Delivery，ED）、带局部队列信息的最早分发算法（ED with Local Queue，EDLQ）、带全局队列信息的最早分发算法（ED with All Queue，EDAQ）、信息全知算法（Linear Program，LP）几类[10] 2559。具体来说，ED的先验知识为，节点已经对网络整体链接信息有统计上的了解（如延时平均值，连接建立和拆除时间的期望值，信道容量期望值等），而MED则能够获知各节点间的链接信息和通信机会，本文研究场景可获取的先验知识可以实现MED和ED类算法，如要实现EDLQ类以上的算法，则需要大量的实时信令传递先验知识，这对一般DTN几乎是不可能的，可以不用考虑。

基于组播和选播DTN路由可以是随机性的，也可以是确定性的，此类研究目前较少，但有发展潜力[10]2566。这是由于其资源分配空间从一个时间段的单条路径传输扩展到多条路径传输，模型要考虑的因素和相关信令增加，处理较为复杂。这方面的组播方案有，可扩展分级域间（Scalable Hierarchical Inter-domain Multicast，SHIM） 的DTN方案，基于网格的组播路由协议，考虑节点能量的容迟移动网络组播方案[11]等，或由于考虑的网络拓扑结构过于复杂，或因为网格计算尚未大面积应用，或考虑到车载电源无需考虑能量的节省，而无法适用于车载移动网络。而选播方案如期望多目标时延选播方案（Expected Multi-Destination Delay for Anycast， EMDDA）仅仅针对源节点与目的节点具有相同移动速度的集群移动节点之间的数据传输，机会网络的选播模型[12]给出了相关的框架结构，但没有涉及到细节，也都无法直接应用于本文环境。然而Nelson等[13]在比较了各种资源分配形式后，指出选播方案最有发展潜力。因此，考虑改进k选播作为解决方案。 

其他能适用于本文研究场景的方案不多，Santiago等[14]基于概率和移动信息的普适性DTN多播路由方案，以多条路径传输信息，使用一个字节的信令提供比链接的统计信息更精确的节点间移动信息，其先验知识需求在MED和EDLQ之间。然而在网络中断和网络分割出现频繁的快速移动环境下，其信令开销尽管不大，却很难克服DTN做到实时传送，无法保证提供实时先验知识。本文希望使用k选播和不确定规划模型，这样仅仅需要ED级别的统计级先验知识来进行网络决策，而无需实时的先验知识。

不确定规划模型的规划相当复杂，但是考虑到在k选播中资源将分为多个片段，多片段的时间不确定性相加，将趋向于平均值，有利于减少计算量。在确定性路由下，注意到k选播集合中的有效元素会不断减少，因此将k选播的概念扩展到集合元素按规律变化的广义k选播（General k-anycast，G-cast），从而进一步简化计算。

资源分配模型的量度不一，或重视网络资源利用，或取服务提供商或消费者的效用，或利用纳什均衡求得最优化指标，也有将DTN网络中的链路调度、路由协议与数据副本分发问题抽象为多目标优化问题求解的。但是取各因素综合形成总效用指标，以效用最大化作为资源分配的量度，是近年来的一种趋势。我们原有工作也采用这一方法[15]62-63，对占资源最大比重的下载类和视频传输类进行了优化，但是并没有考虑到达时间的概率不确定性。本文将拓展这一模型，增加不确定规划的约束条件，配合k选播，则可将计算所要求的MED级先验知识降低到ED级别，即只需对链接信息了解统计值。

2010年Lattanzi等[16]提出，可基于路径确定性前提在卫星网络和蜂窝网络组成的混合网络之间进行资源分配，我们在2010年底[15]61则采用WiFi网络（局部热点）和蜂窝网络（全覆盖环境）这种城乡道路间最常见的混合网络，同时提出将基于时间的先验知识转化为基于空间函数形式的接入路由器（Access Router，AR）信息矩阵[15]63，本文予以沿用并深化，进一步考虑了信息矩阵随时间变化的特点，以此缩小运算空间，从而减少概率不确定式的计算量。由此提出的不确定规划资源分配效用模型，实现了在动态减小的广义k选播路由器集合中选择路由器以实现最优带宽资源分配。此时k个中选路由器的群体起着DTN渡轮的作用。