一种基于联络历史的车载容迟网络路由算法

宋志华,暴建民,谢元发,周 雅

(南京邮电大学，江苏 南京 210023)

一种基于联络历史的车载容迟网络路由算法

宋志华,暴建民,谢元发,周 雅

(南京邮电大学，江苏 南京 210023)

移动车载容迟网络(VDTN)是一种特殊的容忍延迟网络，其消息从一端到另一端由移动的车辆节点携带转发。由于不同源节点和目的节点之间端到端通信路径不存在，因此，移动车载容迟网络中端到端的联系是松散的，且导致传递消息至目的节点的可能性大幅度减小。因此，在移动车载自组织网络下应用的一系列路由算法不能很好地应用于VDTN。所以在VDTN中，路由算法成为一项具有挑战性的任务。文中提出了一种基于节点之间的联络历史的路由算法(CONHR)，指的是通过已有联络历史记录的移动节点，比较中继计数区域中数值的大小，选择出最佳的移动节点，让其携带并转发消息至目的节点。这种历史记录包含每个移动节点过去遇到的中继节点的信息。结果显示，基于节点之间联络历史的路由算法(CONHR)与其他算法在消息投递率、平均时延、开销比上具有更好的表现。

移动车载容迟网络；联络历史；CONHR算法；容忍延迟网络

0 引 言

DTN网络是一种在其生存周期内不需要端到端联系的特殊网络，但该类型网络的缺点表现在较窄的传输范围、无线通信时的能耗限制、不同的网络分割等方面。但可以通过不均匀的数据传输率，间歇长短，较长或变化复杂的延迟以及传输过程中较高的出错率区别这些网络，比如星际网络[1](IPN)、水下传感器网[2]、无线移动传感器网络(WMSN)、手持设备网络、战术通信网[3]、移动车载容迟网络[4](VDTN)等。

VDTN作为新型的车辆通信网络，可以实现车辆与车辆之间(Vehicle to Vehicle,V2V)、车辆与路边基础设施之间(Vehicle to Infrastructure,V2I)的多跳无线通信。其中，车辆将被视为可移动节点，节点间利用中继节点相互传递消息，而中继节点是一种存储更多消息记录的缓存空间区域，并且散布在车辆行驶路径的道路交叉处，接收或发送消息给移动节点。

DSDV[5],DSR[6]以及AODV[7]是车载自组织网络(MANET)针对路由数据包的几个常见的路由协议。它们是通过在源节点与目的节点之间建立端到端的路径来传送数据。这一类协议都是为了找到最短传输路径，并在此路径基础上路由数据包。但在DTN网络中，不能直接找到源节点到目的节点的最短路径，只有通过一段时间不同网络分区中的子路径的叠加方式找到较优路径。正因如此，使得VDTN网络路由算法变得富有挑战性。所以在VDTN网络中，不是为了找到最短路径，更多的是确保消息到达目的节点。

DTN路由算法是大量的节点以存储-携带-转发的机制进行的，基本的路由算法是基于洪泛策略，有First Contact[8]算法、Spray-and-Wait算法[9]，以及基于节点历史的路由算法，比如Prophet[10]算法，节点利用节点间相遇的历史信息和传递性来估计到达目的节点的概率选择下一跳节点。

针对VDTN，文中提出一种路由算法—基于节点之间联络历史的路由算法(Contact History Routing)。

1 基于节点联络历史的路由算法-CONHR算法

1.1 算法背景

(1)视作移动节点的车辆高速运动，节点在很短的时间内彼此相遇，节点之间交换信息的时间非常短暂，所以传递的消息数目非常少。

(2)当节点以预计路线移动时，节点之间相遇的频率增加，比如出租车司机。节点会多次移动到同一位置，比如去公司的职员。与特定中继节点有相遇历史的移动节点会对以后转发消息的决策产生重大影响，例如一个节点在过去已经遇到该中继节点，在未来的时间点就有较大的概率会再次遇到。

针对上述VDTN移动节点的特征，文中提出了CONHR算法。它是基于联络历史的一种算法，该联络历史是由源节点与移动节点产生的，是关于在网络中与不同的中继节点相遇的联络历史记录。在该算法中，每个节点产生并存储这一相遇联络历史记录，并转发消息给网络中有较大可能与更多的中继节点相遇的移动节点(即中继计数较大的节点)，直至到达目的节点。

1.2 算法假设

1.2.1 总体假设

(1)网络中的每一个节点都有独特的识别标志，以至于网络中的其他节点都能够识别。

(2)假定网络中出现两种终止节点：源节点和目的节点。它们作为网络中的固定节点并且被安置在两个不同的终端上。

(3)具有手持设备的车辆(同构或异构)作为移动节点携带信息。移动模型[11]设置为基于地图的模型 MapBasedMovement。

(4)中继节点是固定节点，也称为路边单元，利用存储和转发机制，分布在网络中不同的道路交叉处来提高消息投递率。与ONE中所说的中继节点不同在于是否有中继计数区域。

1.2.2 消息生成与复制策略

消息只能由源节点产生；源节点、中继节点、移动节点秘密进行消息的转发，即双方通信时只有对方才能获知彼此的消息。

1.2.3 调度与丢弃策略

(1)调度策略是对队列中的随机消息进行调度。

(2)终止策略考虑到消息的生存周期TTL。如果消息时间达到了生存周期，将从队列中丢弃。

1.2.4 转发/限制的洪泛策略

基于限制的洪泛策略的消息转发：利用节点间的相遇进行消息的复制，然后通过中继节点进行消息的转发，直至目的节点。

1.3 算法过程

CONHR遵循两个过程：一是关于移动节点的历史创建与更新；二是消息的转发与传递。

1.3.1 移动节点的历史创建或更新

表1显示历史记录存储在VDTN不同类型的节点中。

表1 不同节点的历史存储

首先，源节点与移动节点的历史记录设置为NULL。当移动节点与中继节点第一次相遇时，移动节点在相应的中继计数区域存储这次相遇的历史记录。当移动节点M与源节点S相遇，源节点S从移动节点M传递的信息中寻找与中继节点相遇的信息，并存储这些记录：移动节点的编号为该移动节点相遇到的中继节点编号及其相遇过的节点编号。当移动节点相遇时，它们创建类似于与源节点相遇时的历史记录信息，并交换之间存储的信息。

当源节点与移动节点再次相遇时，便会更新相应的历史记录，移动节点之间再次相遇时，亦是如此。

1.3.2 消息转发与传递

无论何时源节点S相遇移动节点M，S都会检查M存储的历史信息是否已经存在于S的历史记录中。如果该历史记录对S通信范围内的所有移动节点有效，S节点则选择该范围内中继计数最高的移动节点作为下一节点进行消息转发。

当移动节点之间相遇时，也会检查彼此的历史记录信息，选择中继计数最高的移动节点作为下一节点进行消息转发。

在以下出现的两个场景中，如果移动节点之间具有相同的中继计数或中继计数均为0，那么随机选取范围内的移动节点作为下一节点进行消息转发。

2 仿真实验

2.1 模拟器

对网络环境的模拟主要靠网络模拟器。文中实验采用的是机会网络模拟器(Opportunistic Networks Environment，ONE)[12]。ONE仿真系统是在SINDTN和CATDTN项目资助下由芬兰Nokia研究中心开发的用于机会网络研究的仿真平台，专门用于研究DYN网络。它基于离散事件的模拟引擎，其扩展功能强大。

2.2 仿真环境与配置

文中将利用ONE[13]仿真平台对CONHR路由算法进行大量的仿真实验。首先对将要进行的场景参数进行设置(见表2)，中继节点设置为10，源节点、目的节点、移动节点、中继节点均在模拟场景中。

表2 环境模拟参数表

仿真中采用的评估指标有：消息投递率、平均时延、开销比。具体含义见表3。

表3 ONE仿真器评估指标

将CONHR算法与Prophet算法、Spray-and-Wait算法以及First Contact算法进行对比，对于Spray-and-Wait[14]算法，设置其最大副本数量为6。

2.3 模拟结果与分析

首先，通过改变节点数量，比较各个算法的消息投递率，评价CONHR的稳定性。

如图1所示，当节点数量由50到250变化时，发现所有算法的消息投递率都增加了。其中，CONHR算法消息投递率增长的最快。原因如下：

当节点数量增加时，节点之间与中继节点之间的联系增加，因此中继计数增加。CONHR算法的核心在于计算中继计数区域中的数值大小，从而决定消息的转发路径。因此，中继计数越大，消息投递率越大。

图1 消息投递率vs节点数量

其次，通过改变节点的数量，比较各个算法的平均时延，评价其性能。

如图2所示，对于所有的算法，当越来越多的节点进行消息转发与传递时，其平均时延会降低。相比较而言，CONHR算法较为稳定。

从图2中看到，当节点数量在50～90范围内变化时，其平均时延降低；当节点数量在90～130范围内变化时，其平均时延上升；当节点数量在130～170范围内变化时，平均时延又降低。这是由于越来越多的消息投递率并未增加的节点进行了消息转发。当越来越多的节点进行消息转发，网络将会变得拥塞，以及花费更多的时间来转发消息，因此传递时延也相应地增加，这也是CONHR算法在节点数量90～130范围变化时平均时延上升的原因。

图2 平均时延vs节点数量

最后，通过改变节点的数量，比较各个算法的开销比，评价其性能。

CONHR算法在开销比上优于Prophet算法和First Contact算法。相比之下，它具有更高的消息投递率和中继较少的信息。但Spray-and-Wait算法具有中继更少数量的消息，由于在Spray-and-Wait算法中，其中继节点直到遇见目的节点才会转发与传递消息，故导致其路由开销比比CONHR算法更小。

如图3所示，当节点数量增多，CONHR算法的路由开销比略有增加。这是由于节点数量越来越多，其中继节点的数量也会相应增加进行消息的转发。

3 结 论

通过ONE模拟器的模拟结果显示，CONHR算法在消息投递率、平均时延、开销比上的确比Prophet算法、First Contact算法效果好，尽管在开销比上比Spray-and-Wait算法略低。这是由于找到中继计数较大的节点时其增加了路由开销，但在另外两个方面上还是胜于Spray-and-Wait算法。因此CONHR算法在移动车载容迟网络中具有较好的性能表现。

4 结束语

在使用CONHR算法时，首先利用有限制的洪泛策略传递消息给具有历史记录的移动节点，被选择的移动节点的中继计数较高的优先，这样可能会导致额外的路由开销比，这点还是需要深入研究。

CONHR算法将中继节点视为储存历史记录的变量，在未来将包含与目的节点相遇计数，联系时间间隔以及剩余缓存空间，这样也会增加更多的变量来储存历史记录，也会导致节点需要额外的存储空间、额外的路由开销。今后，将基于这些变量找到一种更加高效的路由算法。

[1] Voyiatzis A.A survey of delayed-and disruption-tolerant networking applications[J].Journal of Internet Engineering,2012,5(1):331-334.

[2] Partan J,Kurose J,Levine B N.A survey of practical issues in underwater networks[J].SIGMOBILE Mobile Computing Communication Review,2007,11(4):23-33.

[3] Krishnan R,Basu P,Mikkelson J M,et al.The spindle disruption-tolerant networking system[C]//Proc of military communications conference.[s.l.]:IEEE,2007:1-7.

[4] Wu H,Fujimoto R,Hunter M,et al.MDDV:a mobility-centric data dissemination algorithm for vehicular network[C]//Proceedings of the first international workshop on vehicular ad hoc networks.Philadelphia,PA,USA:[s.n.],2004:47-56.

[5] Perkins C,Bhagwat P.Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers[J].ACM SIGCOMM Computer Communication Review,1994,24(4):234-244.

[6] Johnson D,Maltz D.Dynamic source routing in ad-hoc wireless networks[M]//Imielinski T,Korth H.Mobile computing.[s.l.]:Kluwer Academic Publishers,1996:153-181.

[7] Perkins C E,Royer E M.Ad hoc on-demand distance vector routing[C]//Proceedings of the 2nd IEEE workshop on mobile computing systems and applications.[s.l.]:IEEE,1999.

[8] Jain S,Fall K,Patra R.Routing in a delay tolerant network[C]//Proc of annual international conference of the special interest group on data communication.Portland,Oregon,USA:ACM,2004.

[9] Spyropoulos T,Psounis K,Raghavendra C S.Spray and wait:efficient routing in intermittently connected mobile networks[C]//Proceedings of ACM SIGCOMM workshop on delay tolerant networking.[s.l.]:ACM,2005.

[10] Lindgren A,Doria A,Schelen O.Probabilistic routing in intermittently connected networks[C]//Proc of lecture notes in computer science.[s.l.]:[s.n.],2004:239-254.

[11] 王 丰，暴建民，彭慧珺.延迟容忍网络中移动模型对路由算法的影响[J].计算机技术与发展，2015,25(10):127-130.

[12] Keränen A,Ott J,Kärkkäinen T.The ONE simulator for DTN protocol evaluation[C]//Proceedings of the 2nd international conference on simulation tools and techniques.Rome,Italy:[s.n.],2009.

[13] 孙践知.机会网络路由算法[M].北京：人民邮电出版社，2013.

[14] 孙践知，韩忠明，陈 丹,等.Wait and Spray：一种改进的机会网络路由算法[J].计算机工程与应用，2011,47(31):91-93.

A Routing Algorithm of Vehicular Delay Tolerant Network Based on Contact History

SONG Zhi-hua，BAO Jian-min，XIE Yuan-fa，ZHOU Ya

(Nanjing University of Posts and Telecommunications，Nanjing 210023，China)

VDTN is a special delayed tolerant network,where messages are carried by moving vehicles from one end to another.Because there is no existence in the communication path from end to end between different source nodes and destination nodes,the relation from end to end is loose,and the possibilities of transferring messages to destination nodes decreases at a large scale.So a series of routing algorithms applied in the vehicle Ad-Hoc network cannot apply in VDTN greatly,routing algorithm in VDTN has become a challenging task.A routing algorithm based on contact history of nodes is proposed,which chooses the best moving nodes by nodes with contact history,and makes moving nodes whose relayed count is the biggest carry messages to destination nodes.The contact history contains information of relayed nodes which met with each node.The result suggests the routing algorithm based on contact history performs better in delivery ratio,average latency,overhead ratio than other algorithms.

VDTN;contact history;CONHR;delayed tolerant network

2015-11-03

2016-02-23

时间：2016-06-22

江苏省大学生创新创业训练计划(SZDG2015043)

宋志华(1995-)，女，研究方向为容迟容断网络；暴建民，正高级工程师，硕士生导师，研究方向为物联网。

http://www.cnki.net/kcms/detail/61.1450.TP.20160622.0844.038.html

TP301.6

A

1673-629X(2016)07-0196-04

10.3969/j.issn.1673-629X.2016.07.042