一种DTN网络摆渡节点存储分配方案研究

从立钢，杨华民，王杨惠，底晓强

（1.长春理工大学 计算机科学技术学院，长春 130022；2.长春理工大学 化学与环境工程学院，长春 130022）

一种DTN网络摆渡节点存储分配方案研究

从立钢1，杨华民1，王杨惠2，底晓强1

（1.长春理工大学 计算机科学技术学院，长春 130022；2.长春理工大学 化学与环境工程学院，长春 130022）

为提高DTN网络性能，针对摆渡路由算法中摆渡节点存储资源分配存在的公平性问题，提出了一种基于加权最大最小公平原则的摆渡节点存储资源的优化分配方案。区别于现有摆渡节点存储资源分配所使用的先来先服务方式，加权最大最小公平原则可以在保证数据节点在获得公平的数据传输机会的同时，为重点任务提供更多的资源支持。仿真实验表明，经过存储资源优化的摆渡路由算法与现有摆渡路由算法相比较，在网路传输成功率、平均网络时延等方面性能均有显著提高。

延迟容忍网络；加权最大最小公平；摆渡路由算法

DTN［1］概念最早由DTNRG（Delay Tolerant Network Research Group，延迟容忍网络研究组）在2003年提出，试图通过DTN网络来解决星际网络频繁中断、时延大的问题。同年，在SIGCOMM国际会议上，Kevin Fall发表了著名论文“A Delay-Tolerant Network Architecture for Challenged In⁃ternets”，该文章成为了DTN网络研究领域的经典。目前，DTN被广泛应用在农业网络［4］、星际网络［5］、野生动物研究［6］等多方面。

做为一种新型的网络形式，DTN尚有很多方面并不完善，需要进行深入研究，其中路由技术是当前的研究热点之一。目前，经典的DTN路由算法有Epidemic算法、PROPHET算法、Spray and Wait算法以及MaxProp算法等。Epidemic传染机制算法中，每个节点都将消息副本复制给相遇节点，但由于节点能量和缓存受限，容易造成消息的大量重传和丢弃，网络开销大［9］；PROPHET算法根据节点运动的规律，利用历史相遇信息预测到达目的节点的概率，将消息复制给完成数据传递概率更大的节点，从而限制了消息副本的数量，降低了网络资源消耗［10］；Spray and Wait算法限制消息转发的上限数目n，这种机制避免产生过多的消息，从而造成网络开销的爆发式增长［11］；MaxProp路由算法引入了优先级对数据进行标记，优先级高的数据先发送，同样优先级低的数据先删除，这样大大提高了节点资源的利用率［12］。

除了以上DTN路由算法之外，还有一类路由算法被称为摆渡路由算法［8］或数据骡子路由算法［3］，该路由算法的基本模式为“存储-携带-转发”，在网络中专门设置一类节点负责接收数据，并携带数据到达目的节点附近转发，实现数据的传递，这类专门承担数据“存储-携带-转发”的节点被称为摆渡节点，对于此类算法，摆渡节点的状态对于路由过程的顺利进行至关重要。

本文针对DTN路由节点的存储分配方案展开研究，使用加权最小最大公平原则对存储空间进行分配，在满足资源分配公平性的要求同时提高了重点数据的保障水平，通过仿真实验表明：与先到先服务分配模型相比较，利用本方案优化后的摆渡路由算法在网络传输成功率、平均时延等方面均有提高，对提高DTN网络性能作用明显。

1 基于加权Max-Min的摆渡节点缓存分配模型

1.1 网络模型

如图1所示，摆渡节点在运动到当前位置时，在其通信范围内有多个数据节点需要发送数据，其中个别数据节点数据量过大，而当前摆渡节点的内存不足以保存所有数据发送要求，就需要考虑其内存资源的分配问题。如果对摆渡节点内存简单使用“先到先服务”模型进行分配，会导致部分数据节点等待时间过长问题，甚至会出现摆渡节点循环多次而个别重要数据仍未获得服务的情况。

图1 网络模型图

1.2 摆渡节点内存分配优化算法

加权最大最小公平算法［7］被广泛应用于网络路由、流量分配、资源调度等网络通信领域，针对上一节中描述的DTN网络模型及其遇到的实际问题，将从优化摆渡节点存储资源分配入手，使用加权最大最小公平原则优化存储分配方案，从而降低服务平均等待时间，提高网络服务质量。

如图1所示，在摆渡节点f到达当前位置时，通信范围内有多个节点等待摆渡节点提供数据转发服务，多个节点向百度节点提交服务请求数据包，经过解析后f获得区域内需要存储的数据总量，如果数据总量小于等于f的存储资源，则为所有节点提供正常数据存储转发服务；如果数据总量大于f的存储资源，则必须对内存空间的分配进行优化。

为提高该模型的一般性，假设在摆渡节点范围内有n个数据节点，数据节点集合D={d1,…,dn}，数据节点此次会话的数据存储需求为X={x1,…,xn}，其中x1＜=x1…＜=xn；假设当前摆渡节点f的剩余存储空间大小为s，且摆渡节点与相关数据节点接触时间足够长，足以完成相关操作。

假设n个数据节点此次会话的权重分别为W={w1,…,wn}，权重代表相关数据节点的重要程度，也可以理解为相关会话的服务质量需求，本文将权重划分为10个等级，用整数1到10表示，1表示最低级别，10表示最高级别。

基于以上假设，首先根据n个数据节点的权重对摆渡节点f剩余存储空间进行第一轮分配，则摆渡内存资源分配情况可以表示为B1={b11,…,b1n}，其中b1i可以用公式（1）表示。

完成第一轮存储空间分配后，将数据节点需求量xi与内存分配量bi相比较，如果bi等于xi，则节点ni获得存储空间bi；如果bi大于xi，则分配给节点ni存储空间xi，并收回超出部分；如果bi小于xi，则分得存储空间bi，同时节点ni参与下一轮存储空间分配，第一轮数据节点获得存储资源如公式（2）所示。

经过第一轮存储资源分配，假设此时摆渡节点内剩余的存储资源为s1，尚有k个节点未获得其所需的全部存储资源，接下来重复利用公式（1）和（2）进行第二轮存储资源分配，如果经过第二轮分配后尚未满足所有数据节点对存储资源的需求且摆渡节点剩余存储资源不为零，则继续重复以上步骤进行资源分配，直至资源分配结束或所有数据节点存储资源需求均被满足为止，具体过程如图2所示。

图2 摆渡节点存储资源分配流程图

2 算法仿真与分析

本文通过改变摆渡节点数量、摆渡节点存储空间，观察网络传输成功率、网络平均时延两项重要性能指标观察网络状态，对比分析加权最大最小存储分配方案与先到先服务分配方案的性能。

2.1 仿真设置

本文所使用的仿真工具为ONE［13］，该工具由芬兰赫尔辛基阿尔托大学的AriKeränen和Jörg Ott等人利用Java编程语言开发，可以在Windows、Linux等多平台上运行。

图3 仿真网络拓扑结构示意图

如图3所示，仿真环境中设置三组数据节点，每组40个节点围绕固定点为中心做随机运动。在三组数据节点之间设置三条路线，若干摆渡节点按照路线循环运动，提供数据存储转发服务，摆渡节点存储资源分配方案分别采用加权最大最小算法和先来先服务算法进行存储资源分配，其他主要仿真参数如表1所示。

2.2 仿真结果分析

本文通过修改摆渡节点存储资源大小、数据包大小、摆渡节点数量以及数据节点的数量，对比分析加权最大最小方案和先来先服务存储资源分配方案在不同情况下的性能。

（1）摆渡节点存储与存储分配方案性能关系

表1 主要仿真参数

本节研究摆渡节点存储资源与摆渡路由算法性能之间的关系问题。以表1仿真场景为基础，设定摆渡节点数量为5，通过修改摆渡节点存储资源的大小，考察摆渡节点存储资源大小对于不同储存分配方案性能的影响，实验结果如图4、5所示。

图4说明，随着摆渡节点存储资源的增加，网络传输成功率明显增加。在业务需求不变的情况下，当内存资源增加到一定程度后，网络传输成功率趋于稳定，不再提高。同时，对比两组曲线，采用加权最大最小存储资源分配方案的摆渡路由算法在成功率方面要明显优于先到先服务分配方案。

图4 摆渡节点存储与路由传输成功率关系图

图5说明，随着摆渡节点存储不断增大，采用不同存储分配方案的路由算法的网络平均延时均明显降低，其中采用加权最大最小分配储存资源的路由算法有明显优于先来先服务分配方法。

图5 摆渡节点存储与路由平均时延关系图

（2）摆渡节点数量与存储分配算法性能关系

本节研究摆渡节点数量对于加权最大最小分配和先到先服务两种分配算法之间的关系问题。以表1仿真场景为基础，设定摆渡节点存储资源为50Mb，通过修改摆渡节点数量，考察摆渡节点数量变化对于不同储存分配算法性能的影响，实验结果如图6、7所示。

图6说明，在网络传输成功率方面，摆渡节点数量与网络传输成功率成正比，随着摆渡节点的增加，网络传输成功率增长明显，同时，采用加权最大最小存储资源分配方案的摆渡路由算法在成功率方面要明显高于先到先服务分配方案。

图6 摆渡节点数量与路由传输成功率关系图

图7 摆渡节点数量与路由平均时延关系图

图7说明，摆渡节点的增多对于降低DTN网络平均时延十分有效，两种路由算法在网络平均延时均方面降低都很明显，其中采用加权最大最小算法优化后的路由算法延时降低更为显著。

产生以上结果的原因主要在于：①当摆渡节点数量一定时，较大的存储空间能够为更多的数据节点提供服务，提高网络传输成功率；②在相同的存储资源前提下，使用加权最大最小公平原则分配存储资源，可以为更多的节点提供服务，减少数据节点的平均服务等待时间，降低网络时延；③摆渡节点数量越多，数据节点获得服务的机会就越多，DTN网络的传输成功率和时延均会得到相应改善。

3 结论

为提高DTN网络中摆渡路由算法的性能，本文从优化摆渡节点存储资源分配入手，将加权最大最小公平原则应用于存储分配，与传统先到先服务分配方式相比，在网络传输成功率和平均网络时延方面均有改善，对于提高DTN网络性能作用明显，优化存储分配是改善网络服务质量的一种重要手段。

［1］ Burleigh S，Hooke A，Torgerson L，et al.Delay-toler⁃ant networking：an approach to interplanetary Internet［J］.Communications Magazine，IEEE，2003，41（6）：128-136.

［2］ Cerf V，Burleigh S，Hooke A，et al.RFC 4838：Delaytolerant networking architecture［S］.USA：IETF，2007.

［3］ Fall K.A delay-tolerant network architecture for chal⁃lenged internets，ACM SIGCOMM’03［C］.New York：ACM，2003.

［4］ Ochiai H，Ishizuka H，Kawakami Y，et al.A dtn-based sensor data gathering for agricultural applications［J］. IEEE Sensors Journal，2011，11（11）：2861-2868.

［5］ 于海洋，杨华民，姜会林，等.一种全球覆盖的多层星座链路分析［J］.长春理工大学学报：自然科学版，2014，37（3）：56-59.

［6］ Juang P，Oki H，Yong W，et al.Energy-efficient com⁃puting for wildlife tracking：design tradeoffs and early experiences with ZebraNet［J］.Acm Sigops Operating Systems Review，2002，36（5）：96-107.

［7］ Nace D，Pioro M.Max-min fairness and its applications to routing and load-balancing in communication net⁃works：a tutorial［J］.Communications Surveys&Tutori⁃als IEEE，2008，10（4）：4-17.

［8］ Zhao W.A message ferrying approach for data delivery in sparse mobile Ad Hoc networks［C］.In Proc.5th ACM，2004：187-198.

［9］ Vahdat A，Becker D.Epidemic routing for partially con⁃nected ad hoc networks［R］.Technical Report CS-200006，Duke University，2000.

［10］ Lindgren A，Doria A，Schel O.Probabilistic routing in intermittently connected networks［J］.SIGMOBILE Mob.Comput.Commun.Rev，2003，7（3）：19-20.

［11］ Spyropoulos T，Psounis K，Raghavendra C S.Spray and wait：an efficient routing scheme for intermittently connected mobile networks，ACM SIGCOMM 2005［C］.Philadelphia：ACM，2005.

［12］ Burgess J，Gallagher B，Jensen D，et al.MaxProp：Routing for vehicle-based disruption-tolerant net⁃works［C］.Proceedings-IEEE INFOCOM’15，Hong Kong：IEEE，2015.

［13］ Ari Keränen，Jörg Ott，Teemu Kärkkäinen.The ONE simulator for DTN protocol evaluation［C］.SIMU⁃Tools'09：2nd International Conference on Simulation Tools and Techniques.Rome：March 2009.

［14］ 从立钢，杨华民，王杨惠，等.基于复制的DTN网络路由算法研究［J］.长春理工大学学报：自然科学版，2016，39（4）：119-124.

Research on a Storage Allocation Schema for DTN Ferry Node

CONG Ligang1，YANG Huamin1，WANG Yanghui2，DI Xiaoqiang1
（1.School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022；2.School of Chemistry and Environmental Engineering，Changchun University of Science and Technology，Changchun 130022）

In order to improve the performance of DTN network and address the problem of fairness in the allocation of storage re⁃sources of ferry nodes in ferry routing algorithm.We propose an optimal allocation scheme based on the weighted max min fair⁃ness.Different from the existing ferry node storage resources allocation by using the first come first service，the weighted max min fairness principle can provide more resource support for the key tasks while ensuring the fair data transmission opportunities.The simulation results show that the performance of the proposed algorithm is better than that of the existing ferry routing algorithm，the network transmission success rate and average network delay and other aspects of performance have been significantly im⁃proved.

DTN；weighted max-min fairness；ferry routing algorithm

TP393

A

1672-9870（2017）03-0117-05

2017-04-11

“863”计划信息技术领域课题资助项目（2015AA015701）；吉林省教育厅资助项目（JJKH20170628KJ）

从立钢（1983-），男，博士，讲师，E-mail：clg_cust@126.com