一种车载机会网络文件调度与数据传输算法

龙 浩 张书奎 张 力

1(苏州大学计算机科学与技术学院 江苏 苏州 215006)2(徐州工业职业技术学院信息与电气工程学院 江苏 徐州 221140)

0 引 言

随着道路车辆的日益增多，车载机会网络成为当前研究的热点。但是它面临着诸多挑战，比如车辆节点高速变动、通信环境复杂多变、拓扑结构动态变化、传输节点密度不均等，这些都影响车载机会网络的通信性能和数据传输[1]。

车载机会网络的链路质量受到车辆频繁移动和网络拓扑结构改变的影响，链接质量不稳定，如果数据包在传输过程中丢失，则无法重新组建原始数据。在这种情况下，只能重传数据包，或者放弃整个文件。当数据包或文件传输所花费的时间大于链路持续时间，则无法成功传输文件，对当前链路资源造成浪费。因此，在节点传输文件时，应尽量避免传输在当前链接状态下无法完成传输的文件资源，尽量在链路持续时间内完成文件的传输[2]。

目前流行的机会网络路由算法Epidemic算法及其变异算法利用节点与节点间的相遇实现多副本的复制，从而提高了数据传输的成功率，但是数据的多次复制势必增加了节点缓存空间和带宽的占用，增大了网络资源的消耗[3]。另一个常用的算法是Spray and Wait算法，该算法严格控制消息副本的喷射次数，在提高数据传输成功率的同时降低了网络开销。但是消息在等待传输阶段与目标节点的通信机会也会错失，导致网络资源的利用率降低[4]。因此这两种路由算法都达不到最高的传输效率。

1 相关工作

在现实情况中，当前节点传输队列中多个不同大小文件一般采用先进先出的策略[5]。该策略看似比较公平，但在机会网络环境中，该策略无法根据当前的链路状态灵活调度文件，从而造成较多链路资源浪费。另外一种基于拥塞的机会调度算法OCCS[6]，车辆发送文件时指向目标接收车辆，发送车辆根据文件的拥塞程度按某种特定概率采用多拷贝方式发送文件，但是这种传输方法增加了网络资源的消耗。因此，发送原则限制了网络性能的进一步提升。

在目前的数据传输算法中，诸多路由算法通过历史信息来计算节点间的传输概率。当节点相遇时，消息被发送给传输概率高于其自身的节点或汇聚点。文献[7]提出了基于历史记录的数据转发算法，通过计算节点到基站的概率值，当节点和汇聚点相遇时，概率值增加，否则随时间减小。当节点相遇时，根据从低到高的概率值在节点之间传输文件。然而由于节点与基站之间的相遇次数较少，因此大多数节点到基站的概率值较小，传输可靠性较低。PROPHET算法[8]根据历史相遇信息计算节点间的传输概率。当节点相遇时，两者之间的传输概率增加，否则概率值随时间减小。然而由于持续时间非常短暂而引起的无效相遇，导致计算的相遇概率值偏离实际的概率值。HiBop算法[9，13]存储的节点附加属性信息(例如工作地点、住宅地址等)，并结合节点相遇历史计算节点间的传输概率。然而该算法需要增加空间存储附加信息，且相应的计算会增加网络资源的消耗。文献[10，14]根据历史相遇的持续时间确定直接传输概率，然后通过直接传输概率确定多跳传输概率。节点之间的传输概率被定义为多跳传输概率的加权和。然而，机会网络环境中多跳(n>2)传输几乎没有实际意义并且易于误差累积。

本文设计了一种车载机会网络文件调度与数据传输算法解决了车载机会网络中网络拓扑结果随时发生改变、链路持续时间短等问题。我们根据车辆的当前状态和历史记录估测出链路的持续时间，并计算出文件调度序列，从而完成节点间的数据传输。具体创新有4个方面：

(1) 基于链路状态估计，链路持续时间受车速和行驶方向等因素的影响。根据这些因素可以计算出链路的持续时间。

(2) 计算出链路持续时间后，尽量调度那些在当前链路持续时间能够完成传输的文件。根据文件的传输时耗和链路持续时间计算节点在发送队列中文件的传输顺序，改变先进先出传输机制。

(3) 通过节点间单跳交互式协作，每个节点可以根据节点间的共享信息完成算法的计算，避免了集中式的全网信息调度。

(4) 通过算法分析车辆的运行轨迹，计算车辆之间的相遇概率，得出车辆节点相遇的数据传输策略，避免消息副本过度复制的同时也提高了消息转发的机会。

2 文件调度算法设计

由于车载机会网络的局限性，无法实现节点之间全局信息共享，因此每个节点只能控制各自传输队列中发送文件的顺序，算法的输入是当前节点待传输的文件列表，同时预先计算当前t时刻文件的传输耗时集合T，算法的输出是优化后的文件传输调度序列。因此，算法需要解决的问题是使每个节点对自己的队列文件的传输顺序进行排序，并对其进行调度，以最小的网络负载获得最大的文件传输成功率。算法详细过程描述如下：

第一步每个节点维护自己的文件序列F，并且各自初始化一个列表S，将要发送的文件顺序放入S中，然后所有节点依次验证自己队列中的每个文件，计算每个文件的传输耗时，即文件的大小和传输速率的比值。

第二步每个节点列表S中的文件采用贪婪思想进行排序。根据传输耗时递增的原则对列表S中的文件进行重排序，然后根据计算的链路持续时间遍历序列，查找与该时间最相近的文件发送。

第三步根据链路持续时间发送文件。如果文件发送截至时间最接近链路持续时间，将列表S中的文件发送到序列Y中。如果文件发送截至时间大于链路持续时间，则延迟该文件的发送，等待下一个链路的建立。在这种传输机制下，每个节点将优先传输文件传输时耗与链路持续时间最接近的文件，那么将会有更多的文件传递成功。

算法伪代码如下：

1: function input(Fi, T, t)

//根据文件的传输耗时准备好发送文件序列

2: for file Fi(i from 1 to n) do

//n为文件序列F的长度

3: t=t+TFi, S= S U {Fi}

4: if t>EFithen

5: t=t-TFi, S=S-{Fi}

6: end if

7: end for

8: return S

9: S=input(Fi,T,t)

10: for file Fi(i from 1 to |S|) do

11: ifTFi

//根据链路持续时间对应发送文件

12： Y=Y U {Si}, i++

13： else

14: wait next C

15： end if

16： end for

算法的核心问题是如何计算链路持续时间集合C。在DSRC标准中规定，车辆节点要向自己的邻居节点周期性地广播自身状态信息，而自身状态信息包括：当前车辆位置、方向、行驶速度和加速度等。同时假设每个节点在发布状态信息时，一并发布自己在未来一段时间内的行驶路线，也就是说以上信息可以在邻居节点间实现共享[15]。因此每个节点能够估算出自身同邻居节点间的链路持续时间。具体方法如下：

以图1中节点运动情况为例，估测链路持续时间。由于未来的车辆行驶信息在节点间共享，在一定的时间周期内两车速度基本保持稳定，设其间距为d，并建立通信链路，车辆行驶可能有如图1所示的四种情况：两车一直在同一方向行驶之后链路断开，如图1(a)和图1(b)；拐入相反方向后链路断开如图1(c)，拐入垂直方向后链路断开如图1(d)。设在图1(c)和图1(d)中建立链路时，B车距离拐弯路口距离为s1，B车距离拐弯路口距离为s2。节点通信半径为r, A车在前，速度为v1, B车在后速度为v2。

图1 车辆相遇运行示意图

当v1>v2时，三种情况的链路持续时间C的计算公式为:

(1)

当v1

(2)

当v1=v2时,三种情况的链路持续时间C的计算公式为:

(3)

3 基于节点相遇概率的数据传输策略

文件调度到发送序列Y后，接下来我们主要研究如何与目标节点实现数据传输。在车载机会网络中传输性能与车辆和中间节点之间的通信距离r有着直接的关系。文献[8-9]通过仿真分析的方式在车载机会网络中研究通信距离r对数据传输性能的影响但并没有具体给出车辆和节点间通信距离的具体计算模型和公式[10]。本文通过大量的实测数据的验证，得出一个车辆间建立链路通信的通信距离计算公式，建立一个基于速度差和时间间隔的相遇概率数据传输的理论分析模型，为车辆和中间节点之间选择合适的通信距离完成数据传输提供有效的理论分析工具。图2描述的是车载机会网络中车辆和中间节点间的通信。

图2 车辆和中间节点的通信

图2中，由于在道路上行驶车辆运行速度差和车辆相距时间间隔是随机的，且其值并不能确定，因此车辆运行速度差和车辆相距时间间隔满足连续性随机变量概率分布。一段时间内车辆的行驶速度差为Δv，Δv的概率分布函数为FΔv(x)，概率密度函数为fV(t)。任意两辆相邻车辆进入某区域的时间间隔为Δt，Δt概率分布函数为FΔt(x)，概率密度函数为ft(t)。本文将得到一个通用的理论模型，对于不同实际道路情况，可以将车辆对应的Δv和Δt代入通用模型计算得到相应的概率分布函数值。

图1描述了两辆车A和B在道路中的行驶情况，设A车的速度为VA，B车的速度为VB，主要考虑VB和VA速度接近的情况，因为在这种情况下两车才能保持通信链路。由于节点在相遇时共享车辆行驶状态信息，且两车速度在一定时间内保持稳定，因此两车能够建立通信链路。

车辆进入某区域，从开始建立链路形成通信到链路断开，车辆在该区域道路行驶的交通状况都比较接近。因此在一段时间内，可以计算出车辆Δv和Δt对应的分布概率。tA和tB分别表示车辆A和车辆B进入该区域的时间，则Δt可以表示为：

Δt=tA-tB

(4)

由于道路上行驶车辆是相互独立的，且进入某区域的时间也是独立随机的，因此Δt的概率分布函数FΔt(t)可以表示为：

(5)

根据实测相邻车辆在道路行驶的时间间隔Δt为介于0～50 s之间的随机变量，其ft(t)函数为：

ft(t)=n×mt0

(6)

式中：n=0.28,m=0.83是仿真常量。

由于车辆速度是相互独立的，那么1/VA和1/VB也相互独立，令Δv=1/VA-1/VB，则其概率分布函数FΔv(x)为：

(7)

通过实测车辆通行的数据分析得到行驶速度差Δv介于0～60 km/h之间，其fV(v)函数为：

(8)

式中：常系数k=4.35，根据实测数据统计分析得到；μ=10.8为实测数据的统计均值；σ=5.19为统计方差。

由于车辆A和车辆B的速度分别为VA和VB，两车的间距为r，那么车辆B在该道路与车辆A进入通信链路需要满足的条件为：

(9)

转换后车辆间进行通信的距离r为：

(10)

基于节点相遇概率的数据传输策略判定两节点相遇的条件是：通过式(6)和式(8)分别计算车辆与目标车辆的基于时间间隔和速度差的相遇概率范围，并根据式(10)计算节点间通信距离r，首先根据时间间隔和速度差的概率分布判断车辆与节点间是否能达到通信距离r，并且计算链路的持续时间从而完成数据的传输。

4 仿真及性能分析

文件调度算法(TTLD)和数据传输策略(EPDT)相关性能采用ONE(Opportunistic Network Environment)仿真平台进行验证[11]，为了验证TTLD算法文件调度的效率，将TTLD算法与RSATA[12]与OCCS两种算法进行对比实验，并把三种算法应用于典型的机会网络路由协议Spray and Wait中。将EPDT分别应用于典型的机会网络Epidemic和Spray and Wait路由协议，并与这两种路由协议的传统方法进行对比实验。模拟车载网络中的车辆运动过程采用德国科隆市车辆轨迹数据集，随机选取了数据集中800 m×800 m方形区域内的车辆轨迹数据，时间段为5分钟，共包含 235 个节点的运动轨迹。为了不失一般性，文件的大小服从帕累托分布，文献[11]通过对网络流的统计分析可知，网络中文件的大小服从双帕累托对数正态分布，帕累托参数从1.2 增加到2.1。较低的帕累托参数表示文件分布广泛，差异性较大；反之则文件集中在平均值附近，差异性较小。文件的传输速率根据源节点和目的节点的距离以及环境的信噪比来确定[11]。通信半径在80～200 m之间，以20 m递增的方式变换。仿真参数设置如表1所示。

表1 仿真参数设置

车辆可传输的文件数量由车辆的缓存容量来决定，车载机会网络中的车辆缓存容量虽然日益增大，但是目前还很有限，目前车载机会网络文件传输策略的研究重点是如何利用有限的车辆缓存容量更有效地完成对文件的传输。因此本文主要分析车辆缓存容量的变化对TTLD文件调度算法的影响。

车辆缓存容量对TTLD、RSATA与OCCS三种算法消息成功投递率的影响如图3所示，消息投递成功率=成功传输的文件个数/文件总数。3种算法的文件传输成功率随着车辆缓存容量的逐渐增加而快速上升。缓存容量较为有限时，TTLD的文件发送成功率优于RSATA和OCCS，缓存容量为10 MB时TTLD算法的文件传输成功率提高15.8%以上，随着缓存容量的变大，TTLD算法的性能增益有所降低，三者的增速逐渐平稳。

图3 不同缓存容量的文件传输成功率

图4描述了不同缓存容量对文件传输平均时延的影响，可以看出，RSATA算法文件发送的平均时延随着车辆缓存容量的增加而迅速增大，而TTLD算法的时延增速较慢，其中，当缓存空间为10 MB时，TTLD算法的时延趋于稳定，TTLD较RSATA、OCCS的平均时延减少了14.8%。随着缓存容量的逐渐增大，文件传输数量和大小增加，OCCS的时延性能逐渐接近RSATA。最终TTLD与其他两个算法相比，平均时延性能提高15.5%。

图4 不同缓存容量的网络平均时延

图5描述了不同缓存容量对网络负载率的影响。网络负载率=(发送的文件数-成功发送的文件数)/成功发送的文件数。可以看出，网络负载率在缓存容量小于10 MB时，3种算法网络负载率都有较快下降，但是本文算法要远优于其他两种算法。当缓存容量逐渐增加10 MB以上时，车辆节点可以携带和发送的文件更多，可以排队等待的文件更多，网络负载率降低，但是当缓存容量持续增加的时候，3种算法的网络负载率都趋于平稳。TTLD算法中文件调度前有两个条件的判定，减少了无效的文件传递，相比其他两种算法网络负载率有明显降低，大约降低了13.8%。

图5 不同缓存容量的网络负载率

以表1参数设置为基础，采用150节点，2小时数据包生存期，通过与Epidemic和Spray and Wait算法的传统方法来进行算法性能评价，两种算法都是目前机会网络研究的热点，能够应用于各种不同的环境，在性能方面有明显的特点，具有较高的可比性。将EPDT算法应用于目前机会网络最流行的两种路由算法，更能在性能上比较其优越性。

图6仿真结果表明，在不同数据包数量下基于EPDT算法的Epidemic和Spray and Wait路由协议传输成功率均优于传统的Epidemic和Spray and Wait路由协议。当数据包达到1 200个时，EPDT-Epidemic克服Epidemic的弱势，传输成功率几乎接近Spray And Wait，平均传输成功率相比Epidemic高出16.2%。EPDT-Spray And Wait和Spray And Wait算法相比，平均传输成功率高出13.4%。

图6 不同数据包对传输成功率的影响

图7描述的是不同数据包对文件转发次数的影响，Epidemic和Spray and Wait路由协议对消息的多副本复制依赖较大，随着数据包数量的不断增加，其消息转发次数也有较明显的增加。尤其在数据包个数接近900个时，其转发次数增长较明显。由于Epidemic算法的特性，其转发消息的次数与消息的拷贝数量有关。而EPDT-Epidemic路由方法通过对节点的概率估计来进行消息拷贝，使得其转发次数明显降低，几乎与Spray and Wait路由协议的转发次数重合。EPDT-Spray and Wait路由协议通过寻找概率更优的节点，使得节点相遇概率增大，严格控制转发条件，所以在转发次数上明显优于其他算法，平均转发次数较传统方法降低了18.6%。

图7 不同数据包对文件转发次数的影响

图8描述的是不同的数据包对网络开销的影响。Epidemic算法由于数据包的增加，其消息副本数增加迅速，而真正投递成功的消息数却不多，网络开销自然增长明显。EPDT-Epidemic路由方法考虑到只要在合适的相遇概率下才向节点复制数据，大幅度降低了网络开销，平均网络开销较Epidemic算法降低了14.6%，几乎接近Spray and Wait路由算法网络开销。EPDT-Spray and Wait路由算法考虑到在数据喷射过程中，寻找最合适相遇概率的节点完成数据转发，在节点等待过程时也在寻找合适的节点，平均网络开销较其他算法降低了15.4%。

图8 不同数据包对网络开销的影响

5 结 语

本文提出一种车载机会网络文件调度与数据传输算法，与其他算法相比，避免了仅根据文件到达时间或文件大小发送文件，而是根据链路持续时间发送对应文件。数据传输策略根据节点相遇的概率密度函数转发消息，解决了传统算法消息副本的过度发送以及消息副本转发等待。仿真结果表明，所提方法在文件传输成功率、网络平均时延和网络负载率等方面表现出较好的性能。