节点缓冲区大小对城市部署的DTN网络的影响分析

李文藻等

摘 要：容延迟网络DTN（Delay Tolerant Networks）在基于城市部署下具有区域密度差别大，局部节点聚集停顿时间较长的特征，节点缓存大小对数据投递率具有较大的影响。文章利用工作日模型WDM（Working Day Movement）设置趋向于真实城市的场景，分析Prophet路由算法与Direct Delivery路由算法对移动节点的影响。实验结果表明，Prophet路由性能明显优于Direct Delivery路由性能，数据包大小在500k～1M的基础上，节点缓存在10M左右，DTN网络投递率与数据包时延均值获得最优效果。

关键词：容延迟网络；节点缓存；数据投递率；工作日模型； 路由算法

1 引言

容延迟网络是较为新型的网络结构，对延迟、中断有一定的容忍性，是未来移动通信领域发展的重要方向之一。容延迟网络与目前网络最大的区别在于不需要源节点与目的节点存在确定的路径，数据包的传输模式依靠移动节点的携带-存储-转发的模式，利用节点的移动来创造节点的相遇的机会并传输数据包[1]。容延迟网络目前讨论较多的应用于缺乏通信基础设施、网络环境及自然环境部署比较恶劣的挑战性网络中。主要的讨论集中在军事、野生动物研究、星际网络、陆地移动网络、车联网以及传感器网络等领域[2-3]。伴随着移动智能终端的普及以及大数据技术的不断发展，容延迟网络也将会在气象数据采集、大数据前端网络采集、数据挖掘等领域有更多的应用空间[4]。由于DTN网络在信息传输角色中的不可替代性，DTN网络中的路由算法，节点覆盖理论及传输安全都逐渐成为DTN研究中的热点[5-6]。

在城市环境部署DTN网络的研究仍然比较少，而在市政建设、车联网、电子眼数据采集以及大数据的数据挖掘源等方面，延迟容忍网络的应用也有广阔的市场空间，在移动智能终端的应用越来越多的情况下，在城市中的DTN网络研究不容忽视。来自Nielsen公司的市场研究报告《2013移动消费者报告》显示，中国在截止2013年3月，智能手机的普及率达到66%。这些都为DTN在城市中的部署创造了良好的条件与机遇。由于城市的场景与大多数挑战性网络特性有所区别，如节点密度区域集中性、POI（Point of Interest）区域可测性及特殊节点（如公交车，地铁）等路径明确性等，都与其余的DTN网络部署有一定的区别[7]。基于以上的场景特征，研究目前较为普遍的直接交付Direct Delivery路由算法与基于概率交付的Prophet路由算法中移动节点缓存对投递性能的影响，可以平衡移动节点资源与投递性能之间的矛盾，对研究适合城市部署的DTN路由算法具有重要的意义。

2 城市部署中的DTN路由算法

2.1 Direct Delivery算法原理

Direct Delivery算法基于转发的策略，在数据报文传输过程中，节点不会对报文生成副本，同一ID数据包只有唯一一个，算法要求在遇到目标节点时将报文直接交付给目的节点，也称之为Direct Transmission[8]。该算法优势在于由于网络中副本较少并不存在冗余数据包的情况，对节点的缓存要求相对较少。在Direct Delivery算法下的DTN网络负载参数较好。证明网络负载性能如下：假设其中 表示源节点数据包随时间均匀产生数据包集， 表示到达目的节点的数据包集，其网络负载β定义由式（1）所示：

其中 表示随时间节点数据成功建立链接并传输成功的数据包。在Direct Delivery算法中，节点相遇目标节点后才能进行数据包的发送，所以 。式（1）也趋近于0，证毕。

在这里考虑对Direct Delivery路由算法的分析，是由于Direct Delivery算法可以直观的观测到数据的投递概率，也可以观测到移动节点在对唯一缓存要求最少的路由算法中的缓存需求。其中数据包投递率表示数据包从源节点传送到目的节点的概率，是DTN网络中一个重要的指标。若设投递率w，其w的计算如式（2）所示：

2.2 Prophet路由算法

Prophet算法是基于概率的策略，该类路由算法对报文传输成功的概率进行报文传递的依据，与普通的泛洪式传染路由算法Epidemic相近，但是由于Epidemic泛洪算法数据包副本较多，对网络负载影响较大，这里对Epidemic协议不做考虑。在Prophet算法协议中，节点不盲目的转发信息与相遇节点，而是预先估计其传输到目的节点的概率，而判断是否应该传输数据包到相遇节点或存储数据包等待更好的传输机会，有效的节省了传输带宽资源[9]。

在这里算法核心思想引入了一个传输预测概率P（a，b），P（a，b）代表节点a能够发送信息到节点b的概率，当两个节点相遇时，节点a与节点b将会交换各自的预测向量表，表中包含自身到所有节点的传输预测概率值P（a，b），而P（a，b）随着时间的增加，会不断的更新到达其余节点的P（a，b）值。其P（a，b）由式（3）所示：

其中 的初始化常数， 为更新周期前的旧传输预测概率。在两个节点之间的传输预测概率随时间进行指数级变化，及设定该预测概率值的老化算法，其老化方程如式（4）所示：

其中 表示老化常数，k表示时间的单位数，通过老化常数的引入，保障在节点随着t的增加P（a，b）的值满足指数衰减，使节点传输过程中有效的降低网络数据包的副本数。由于城市部署中节点区域密度特征，与POI的可预测性，选择Prophet路由协议作为研究具有典型意义。

3 移动模型的设计

3.1 主要移动模型

在目标仿真场景中的实验结论价值的大小，与节点移动模型密切相关。其中在DTN中讨论比较多的主要包括以下几种：

⑴随机走动移动模型（Random Walk Mobility），节点移动选择随机方向与随机速度

⑵随机路径点移动模型（Random Waypoint Mobility），基于随机目标点选择，利用区间随机速率到达目的点，再重新下一目标点。

⑶随机方向移动模型（Random Direction Mobility Model），节点在移动到场景边缘时随机改变方向与速度。

⑷高斯-马尔科夫移动模型（Gauss-Markov Mobility Model），利用一个调整参数改变节点随机等级的移动模型。

⑸基于路径的移动模型（Pathway Mobility Model），利用地理条件事先设定移动路径限制节点的移动，如地图等。

3.2 WDM移动模型建立

在城市中部署DTN网络存在对移动模型高度真实的要求，才能够得到最接近真实情况的节点投递性能。所以在节点移动模型上选择了由Frans Ekman提出的工作日移动模型。选择该模型的优势在于充分考虑了节点的行为习惯特征、由公交移动模型（Bus submodel）、步行子模型（Waiking submodel）等多种子模型的组合使节点的移动特征更趋于真实情景，所以这里利用工作日模型模拟城市中的DTN部署场景。在城市场景中主要考虑到场景的真实性提高，考虑到节点在家区域、办公区域、傍晚商场区域与节点在源坐标与目的坐标之间的移动模式组建仿真场景。其模型建立如图1所示：

通过上述的移动模型建立流程，基本可以保障仿真场景移动模型接近真实的移动特征。该模型的构建可以很好的表现每个人在一天的生活现状，从早上到单位工作，晚上工作完后回家并购物的移动轨迹[10-11]。其中的数据文件由OPENJUMP软件进行绘制数据导入为可以表示矢量几何对象，空间参照系统的文本标记语言WKT（Well-Know Text）。

4 仿真与结果分析

4.1 仿真的参数条件

在移动模型建立后，利用Opportunistic Networking Environment simulator对仿真场景进行设置并仿真，采用赫尔辛基城市地图为真实场景地图文件，模拟在赫尔辛基城市下部署的DTN网络的移动模型特征与DTN下的Direct Delivery與Prophet算法中节点缓存大小对投递效率的影响。由于场景的设置目的是尽可能使仿真接近真实城市特征。场景中节点数目设置为100个，仿真目标为携带智能终端的行人，每个节点移动速率符合真实行人的移动速度，100节点随机选择0.8m/s与1.4m/s的速率，由于缓存的设计与数据包大小有关，根据普通的数据应用需求，设置数据包大小为500k～1M。其他参数如表1所示：

设置与真实场景近似的重要参数后，并设置工作地点停滞时间范围10s～100ks，下班购物时间1小时～2小时。

4.2 场景设置相遇概率分析

为了分析城市中以行人为主体的移动节点数据投递性能，其移动节点中的相遇次数与时间，在算法对投递率上有较大的影响。由于移动节点的移动特征，首先对移动节点的相遇次数进行统计分析。在DTN网络中，都是依靠节点的相遇机会进行数据的交换，通过设置每小时计数节点相遇次数，进行仿真分析在WDM下的相遇特征。其相遇的统计数据如图2所示：

通过图2分析可知，基于城市部署的行人移动节点，具有在时间条件下相遇概率非均匀性统计特征，由于行人在城市的生活规律性，导致节点密集相遇时段与稀疏相遇时段具有较大的差异。从结果也可以看到，节点相遇概率具有较强的周期性，周期大约为24小时，并且前24小时由于初始化节点，统计数据趋于不稳定状态。通过相遇概率分析，确定在工作日模型中，仿真时间应该大于48小时，为了充分考虑节点的缓存影响，仿真时间设定为5天。

4.3 节点缓存对Direct Delivery算法与Prophet算法的影响

仿真考虑目前移动智能终端缓存的大小设置5M～12M的合理范围区间进行仿真，投递率与缓存的变化情况如图3所示：

通过图3分析可以发现，伴随移动节点缓存的增加，其数据投递率增加。并且在投递指标上Prophet算法优于Direct Delivery算法较为明显。在10M缓存设置上Prophet算法投递性能达到相对较好的位置，优于Direct Delivery算法。其数据延迟特征如图4所示。

从图5可以分析，伴随着移动节点的缓存变大，其延迟也逐渐增加。主要的原因是由于伴随着节点缓存的增加，其覆盖半径不变的情况下，待投递数据包数量越来越多的情况下导致数据包的延迟增加。所以节点的缓存大小并不是越大越好。从图中可以到10M缓存的延迟与11M缓存的延迟有一个较大的跳变，综合分析图3，图4，当数据包设计大小为500k～1M的前提下，节点的缓冲区设置在10M是最优的性能。

5 结束语

通过设置城市中100余个移动节点，赋予节点的趋近于真实的移动特征，进行DTN的部署，在对节点的相遇概率统计与节点缓存变化对投递率与平均延迟的分析得出以下结论。⑴城市中行人移动节点具有一定的规律性，其相遇概率服具有周期性特征。⑵基于城市部署的DTN网络中，缓存的增加会导致投递率的增加。⑶在工作日移动模型WDM中，随着节点缓存的增加，由于传输半径一定，会导致传输的平均延迟增加。⑷在城市中部署的行人作为移动节点模式下，Prophet算法的投递性能明显高于Direct delivery算法。

[参考文献]

[1]Mundur P，Seligman M.Delay tolerant network routing：Beyond epidemic routing[C].Wireless Pervasive Computing，2008.ISWPC 2008.3rd International Symposium on.IEEE，2008：550-553.

[2]Lu Z，Fan J.Delay/disruption tolerant network and its application in military communications[C].Computer Design and Applications （ICCDA），2010 International Conference on.IEEE， 2010，5：231-234.

[3]C?mara D，Frangiadakis N，Filali F，et al.Vehicular delay tolerant networks[J].Handbook of Research on Mobility and Computing：Evolving Technologies and Ubiquitous Impacts，2011： 356-367.

[4]曹佩，钱江波，陈叶芳，等.基于合并的DTN订阅查询传输协议[J].电信科学.2013，29（3）：66-72.

[5]倪辰辰，李千目，姜怡，等.基于轻型机步野战场景的DTN通信策略设计与性能分析[J].电信科学.2013，29（10）：123-130.

[6]Johnson E，Cruickshank H，Sun Z.Providing Authentication in Delay/Disruption Tolerant Networking （DTN） Environment[M].Personal Satellite Services.Springer Berlin Heidelberg，2013： 189-196.

[7]Yasmeen F，Urushidani S，Yamada S.A probabilistic position-based routing scheme for delay-tolerant networks[C].Computers and Information Technology， 2009.ICCIT'09.12th International Conference on.IEEE，2009：88-93.

[8]孫践知，刘乃瑞，张迎新，等.机会网络典型路由算法性能分析[J].计算机工程.2011，37（16）.

[9]Santiago J，Casaca A，Pereira P R.Non-custodial multicast over the dtn-prophet protocol[M].Wireless Sensor and Actor Networks II.Springer US，2008：197-208.

[10]Chowell G，Hyman J M，Eubank S，et al.Scaling laws for the movement of people between locations in a large city[J]. Physical Review E，2003，68（6）：066102.

[11]Ekman F，Ker?nen A，Karvo J，et al.Working day movement model[C].Proceedings of the 1st ACM SIGMOBILE workshop on Mobility models.ACM，2008：33-40.