车载自组织网络(vehicular ad-hoc network,简称VANET)简称车载网络,是未来智能交通系统(intelligent transportation system,简称ITS)的重要组成部分.车载网络中的通信模式分为两种:车与车(vehicle-to-vehicle,简称V2V)之间的通信和车与基础设施(vehicle-to-infrastructure,简称V2I)之间的通信.V2V通信是移动车辆之间的点到点数据传输,而V2I通信是移动车辆与静态部署的基础设施之间的数据传输.在缺乏基础设施的环境或车辆稀疏的状况下,V2V通信能够以多跳的形式,为VANET提供最基本的车辆间通信手段.相对于V2I通信模式而言,V2V是一种更为灵活且廉价的通信方式.

本文只考虑不依赖于基础设施的车辆间通信,在这种情况下,局部范围内的一组车辆可能在短时间内维持相对稳定的传输路径,实现相互之间的即时消息传输.传统多跳自组织网络中的路由技术(如AODV^[1],DSR^[2]等)可以解决这种通信问题,而从比较宏观的角度来看,由于车辆移动具有自主性和差异性,系统中较远距离的消息源和目标之间的数据传输通路难以保证,甚至不存在,因而车辆之间需要充分利用偶然的相遇机会(contact)实现信息的传递与分发.以这种机会主义方式传输数据的VANET称为机会车载网络(opportunistic vehicularnetwork,简称OVN)或车载延迟容忍网络(vehicular delay tolerantnetwork,简称VDTN)^[3],其典型应用如城市环境中非实时数据的分享、重大灾害条件下的信息传输等.例如,考虑如下应用场景:在快速发展的城市环境中,道路网络因城市改造或扩展而变化迅速,但车载地图数据往往更新较慢,这种情况下,我们考虑一种分布式的车载地图数据自动更新应用,即:车辆根据其行驶路线判断是否有新增路段,并将新增路段的地理信息发布给其他车辆.采用机会主义方式传输这些数据,一方面使路网信息数据的更新速度以月为单位降低到以天为单位,另一方面节省了人为更新的技术成本和费用.此外,朋友之间共享自驾游驾驶路线和自定义地理标注信息,也可以采用机会主义的方式,借助于车辆之间的偶然相遇机会传输数据.

机会传输使用“携带-转发(carry-and-forward)”的消息发送方式^[4].消息携带者将消息保存在缓存区,直至遇到合适的转发机会才将数据传递给下一跳节点.消息可以由源节点等待相遇机会直接发送给目标节点,或者通过中间节点转发给目标节点.前者称为直接转发(direct forwarding),后者称为中继转发(relay forwarding).对任意一条“源-目标”数据流来说,由于节点相遇机会的不确定性,使用中继节点协助转发提供了降低直接转发端到端传输延迟的可能性.例如在图 1中,假设S→D的等待时间为T_SD,S→R的等待时间为T_SR,R→D的等待时间为T_RD,如果T_SR+T_RD+<T_SD,那么采用节点R进行中继转发可以提高S-D数据流的传输效率.另一方面,相遇机会的不确定性,导致中继选择策略的决策结果具有很大的偶然性^[5].例如,选定的中继节点是否能够降低消息携带者到目标节点的直接转发延迟,以及延迟降低(增加)的程度都是不确定的.除此之外,节点之间的相遇事件在时序上是离散、异步发生的,消息携带者无从确定哪个节点具有最佳的中继效果.

图 1(Fig.1)

Fig.1 Direct forwarding and relayforwarding 图 1 直接转发与中继转发

基于上述考虑,本文在机会车载网络环境中,研究机会传输中继节点选择与中继效率的问题.提出了剩余延迟估计算法RED(residual expected delay),该算法基于更新过程模型,根据历史相遇记录估计节点间的剩余相遇时间,作为直接转发的剩余延迟期望值.在此基础上,设计每次相遇时决策(per-contact decision)的单拷贝两跳转发策略RED-FMR,从统计学的角度研究中继选择策略的效率和性能:以直接转发延迟为基准,从延迟降低比例、有效中继比例等方面分析不同情况下的中继策略的效率.

本文第1节描述机会车载网络的相关概念和中继选择的问题定义.第2节介绍相关工作.第3节介绍基于剩余期望延迟(RED)的中继选择策略和RED-FMR机会转发算法.第4节介绍RED策略在基于大规模实际车辆运动轨迹的机会车载网络中的效率和性能测试结果.第5节总结全文,并展望未来工作.

本文关注车载网络中可以容忍一定传输延迟的异步通信应用.我们假设节点自身的消息缓存容量足够大,每次车辆相遇机会的通信带宽和连通时间能够充分满足双方的通信需求.消息的端到端传输延迟忽略在线发送延迟以及排队等待等时间,仅考虑等待发送机会的时间.为了使结论具有普遍意义,我们随机选定消息的源节点和目标节点,使用单副本(singlecopy)传输方式,即:消息携带者S将消息Msg发送给下一跳节点R之后,S将删除自身携带的Msg副本.为了简化问题,我们仅考虑一次中继(2跳)的传输性能.在基于相遇时决策的机会转发策略中,单副本、单中继传输是多拷贝、多跳(跳数大于2)传输的基础.

在机会网络中,节点的移动产生了终端之间的直接相遇机会,从而使节点之间可以实现点对点的数据通信.但这种通信链路建立的时间不够确定,链路生存时间短,中断时间长,通信能力受限.常用于描述和表征机会链路特征的术语如下:

·联系(contact):移动节点A和B运动到彼此的无线通信范围内时,能够建立直接通信链路实现数据交换的机会称为联系.一次联系机会也就是一对节点之间的一次相遇事件.

·联系持续时间(contactduration):从移动节点A和B运动到彼此的无线通信范围内,到其距离超出通信范围所持续的时间.联系持续时间即是链路的生存时间,记为D.

·联系间隔时间(inter-contacttime,简称ICT):一对移动节点连续两次联系机会之间的间隔时间,记为I.

·剩余联系间隔时间(residualinter contact time,简称RICT):从某个随机时刻起,到下次联系机会之前所剩余的时间,记为T_R.

·经历时间(elapsedtime,简称ET):从上次联系机会结束,到当前时刻所经历的时间,记为T_E.

考虑具有n个节点的机会车载网络N,随机配对源节点S和目标节点D进行通信,节点之间的数据传递利用“携带-转发”方式实现.假设S在遇到D之前,与其相遇的其他节点按照时间顺序排列为M={R₁,R₂,…,R_m}.集合M包含了当前S-D会话所有的潜在中继节点.如果S与D下次相遇的时刻为t₀,而对R_i∈M(i为自然数,且1≤i≤m),R_i与D未来相遇的时刻分别为t₁,t₂,…,t_m,我们定义:

定义1(有效中继节点). 对于任意R_i∈M,如果t₀-t_i>0,那么我们称中间节点R_i对当前S-D会话是一个有效中继节点.记有效中继节点集合为ε,显然有ε?M.节点R∈ε满足:使得当前S-D会话在数据传输路径S→R→D上的端到端延迟小于传输路径S→D上的端到端传输延迟.

定义2(合格中继节点).按照某种约束条件从潜在的中继节点集合M中选择出来的节点,称为合格中继节点.记约束条件为C,合格中继节点集合为Q,那么Q={R|R∈M,且R满足C}.同样地,合格中继节点集合Q?M.

如果以降低机会传输的端到端延迟为目标,机会中继转发的关键是:判断潜在的中继节点集合M中的元素R是否属于有效中继节点集合ε,即:对任意R∈M,是否R∈ε.判断依据即是约束条件C.基于节点间的相遇历史记录推测未来相遇时间,或者计算节点间相遇的概率,是中继判断常用的依据.受限于预测的准确性,满足C的合格中继集合Q与有效中继集合ε存在差异.也就是说,节点R∈Q不一定满足使得当前的S-D会话在数据传输路径S→R→D上的延迟小于传输路径S→D上的延迟.

针对这一问题,本文研究如何改进中继选择判断依据,提高约束条件C的判定准确率,使得满足条件C的合格中继节点集Q尽可能地接近于有效中继节点集ε,从而提高机会中继转发的效率和收益.我们利用合格有效节点比例因子a来度量Q相对ε的保真度,定义a=|ε∩Q|/|Q|.a的值越大,表明合格中继节点集合Q中的有效节点比例越高,根据C选择的中继节点具有较高的概率获得延迟降低收益.我们以延迟降低率β来描述中继节点的延迟降低收益.延迟降低率定义为中继节点R使会话S-D在传输路径S→R→D上的端到端延迟相对于在传输路径S→D上的端到端传输延迟降低的比例,即β=(T_SD-T_SR-T_RD)/T_SD.

如何选择有效中继节点,是机会传输的基本问题.Jain等人^[6]的研究表明,决策支持信息量和信息类型对中继选择策略的性能有直接影响.基于无决策信息的传染(epidemic)数据分发机制^[7]可以获得最优的消息传输性能,但消耗了大量的网络资源,因而不是一种实际可行的消息传输方式.利用移动节点的历史信息进行机会中继选择决策是一种更现实的策略^{[8, 9, 10]},可以实现较好性能的受控机会传输.

移动节点的历史相遇记录是被使用得最为普遍的历史信息.根据历史相遇记录估算出特定节点对之间的剩余延迟(相遇)时间,可以作为中继选择的判定指标,用于判断遇到的节点是否适合作为针对特定目标的中继节点.Jain等人^[6]提出最小期望延迟(minimum expected delay,简称MED)中继选择算法,这是一种理想化的多路径选择算法,可以反映出机会网络的最优延迟性能边界,但其前提是预知移动节点之间的未来连通状况,因此不能用于实际转发协议的设计.最小期望延迟估计(minimum estimated expecteddelay,简称MEED)^[11]对MED进行了改进,它以节点对在过去一段时间窗口内的平均相遇间隔为指标,预测消息通过不同中继路径传输到目标需要等待的时间,从中选择预测延迟最短的中继路径构建路由表,并在每次遇到一个节点后更新相遇记录和本地路由表.该算法直接以平均相遇间隔为指标,因此延迟预测误差大,而且相遇记录和路由表的更新开销过大.

如果考虑到上次相遇以来的经历时间(elapsed time,简称ET),那么可以从相遇历史记录中更精确地估计出剩余相遇时间.CREST^[12]提出条件剩余时间(conditional residual time)的估计算法,在已知节点对上次相遇以来的经历时间的条件下,根据节点对的ICT分布函数推断出节点的剩余相遇时间.该算法假设节点对ICT的CCDF服从独立同分布参数的对数正态(log-normal)衰减,但是现有工作表明^[13]:在城市车载网络环境中,车辆间的ICT更倾向于表现为指数衰减.另外,该算法要求针对节点对的ICT分布函数进行参数估计,根据拟合的函数和ET值计算剩余相遇时间.一方面,参数估计误差会放大剩余相遇时间的估计误差;另一方面,这需要移动终端具有较高的运算能力.文献^[14]提出最小期望相遇延迟(minimum expected meetingdelays,简称MEMD)指标,以相遇历史记录中大于ET的相遇间隔时间的平均值减去ET作为相遇延迟期望值,更新维护一个相遇延迟矩阵.在该矩阵中,利用Dijkstra算法找出延迟最小的多跳传输路径.本文借鉴了利用历史记录和经历时间预测剩余相遇延迟的思想,但重点是对基于不同剩余延迟指标的中继选择效率和性能的考察以及在普遍意义上对机会中继收益的分析.

假设节点S需要向目标D发送消息(Msg).在S与D相遇之前,S遇到的其他节点按照时间顺序表示为R₁, R₂,…,R_n,记为集合Ω.为了降低S-D的消息发送延迟,S可以从Ω中选择某个合适的节点作为中继,通过它将消息转发给目标D.在这种情况下,我们可以将Ω看作S-D通信的备选中继集合,中继转发的核心目标就是从Ω中选择出有效的中继节点.

平均相遇间隔时间(mean ICT,简称MICT)反映了一对节点的相遇频率和相遇等待时间的期望值,因而被看作是一种实际可行的重要中继选择指标.若MICT的值较小,表明节点对连续两次相遇之间的平均等待时间较短,直接转发的延迟期望较小.选择与目标节点之间的MICT值较小的节点转发数据,能够获得较好的中继转发性能.但平均相遇间隔忽略了中继转发决策的具体环境因素,例如上次相遇以来已经过的时间,因此并不一定能够准确地反映实际的传输延迟.

剩余相遇时间是一种更好的中继选择指标,它指的是从某时刻(如消息生成或中继决策时机)到下次相遇需要的等待时间.在直接转发中,剩余相遇时间即是消息传输的剩余延迟(residualdelay).图 2展示了利用直接转发剩余延迟选择中继节点的过程.图中显示了节点S,R,D在某段时间的运动轨迹以及它们在此期间的相遇状况.如图所示,t₀时刻移动节点S产生向目标D发送消息的请求,如果S与D相遇的预期时间是t₃时刻,而另一移动节点R与D的预期相遇时间是t₂时刻,那么从S和R相遇的t₁时刻起,二者与目标节点D相遇的等待时间分别为T_SD=t₃-t₁和T_RD=|t₂-t₁|.如果T_SD>T_RD,那么节点S选择R作为中继节点可以降低消息最终到达目标D的延迟.

图 2(Fig.2)

Fig.2 Example of relay selection basedon residual delay 图 2 基于剩余延迟的中继选择示例

基于剩余延迟的中继选择策略描述如下:假设${T_{{R_{XY}}}}$表示节点X与节点Y机会通信的直接转发延迟.Ω={R₁, R₂,…,R_n}是节点S遇到D之前相遇的中间节点集合.通过比较节点对S-D与R_i-D之间的剩余延迟期望值,判断R_i是否适合作为S-D的中继节点.

·基本策略:对R_i∈Ω,如果$E[{T_{{R_{SD}}}}] \ge E[{T_{{R_{{R_i}D}}}}],$则R_i适合作为S-D机会通信的中继节点.

·带阈值的中继选择决策策略:为了提高中继选择判断的准确度,我们引入一个差值阈值,以提高基于剩余延迟估计值的比较结果的置信度.对R_i∈Ω以及阈值T_S,如果$E[{T_{{R_{SD}}}}] - E[{T_{{R_{{R_i}D}}}}] \ge {T_S},$则R_i适合作为S-D机会通信的中继节点.

平均相遇间隔可以看作是剩余延迟的粗略估计,该方法忽略了具体机会中继选择场景中的一些重要影响因素.作为改进,我们考虑在已知上次相遇以来的经历时间的条件下,估计一对节点的剩余相遇时间,作为剩余延迟期望(residual expecteddelay,简称RED).该方法同样以节点间的历史联系记录为基础.经历时间可以很容易地从联系记录中获得,即为当前时间与最近联系时间的差值.我们利用更新理论(renewal theory)^{[15, 16]}对节点间的联系过程进行建模.

定义(更新过程). 假定{T_k}是非负的独立同分布随机变量序列,且其二阶矩有限.记E[T₁]=m,Var[T₁]=σ².再假定${a_0} \buildrel \Delta \over = P({T_1} = 0) < 1.$令:

即,N_t是{τ_n}的计数过程.t_n称为第n次更新时刻,随机序列{τ_n}称为更新流,T_n称为第n个更新间隔,N_t称为更新过程.图 3展示了一个典型的更新过程示例.

图 3(Fig.3)

Fig.3 Example of a renewal process 图 3 更新过程示例

更新过程与更新流之间由下面的关系联系起来:

记τ_n的分布函数为F_n(t)=P(τ_n≤t),更新过程N_t的分布为P(N_t=n)=F_n(t)-F_n+1(t).F_n(t)=P(t_n≤t)是n个与T₁独立同分布的随机变量之和的分布函数,一般不容易得到F_n(t)的解析表达式,但在应用中可以借助于随机模拟得到它的近似,例如多次(如m次)生成n个独立T₁随机数并求和,用这m次中其和不超过t的频率,作为F_n(t)的估计值.

定义(更新函数). 更新过程N_t的期望函数称为更新函数,它满足$m(t) \buildrel \Delta \over = E[{N_t}] < \infty ,$而且有:

定义(年龄与剩余寿命). 设τ_n为更新流,N_t为对应的更新过程.当t固定时,随机变量${\alpha _t} \buildrel \Delta \over = t - {\tau _{{N_t}}}$称为(第N_t个更新元的)年龄;而随机变量$\gamma = {\tau _{{N_t} + 1}} - t$称为(第N_t个更新元的)的剩余寿命.更新过程中的年龄和剩余寿命如图 4所示.

图 4(Fig.4)

Fig.4 Age and residual lifetime in renewal process 图 4 更新过程中的年龄与剩余寿命

将一对移动节点之间的联系(相遇)过程建模为更新过程,那么联系间隔时间对应于更新间隔,经历时间对应于更新元的年龄,剩余联系间隔时间对应于更新元的剩余寿命.定义节点对S-D的相遇间隔时间(ICT)序列为T₁,T₂,…,T_n,则随机序列{T_n}构成一个更新流,T_i为第i个更新间隔,N_k={k:T₁+T₂+…+T_k}为更新过程.假设对随机序列{T_n}由小到大排列后为η={I₁,I₂,…,I_n},S-D距上次相遇(即T_n结束)之后已经过去时间T_E,且I_i≤T_E≤I_i+1,则第N_t=n+1个更新元的年龄为α_n+1=T_E,剩余寿命γ_n+1=T_n+1-T_E.

由年龄α_n+1=T_E可知,更新间隔T_n+1>T_E.在此条件下,剩余寿命γ_n+1的期望为

由于T_E为已知常数,因而:

根据更新过程的定义,T_n+1与随机序列{I_n}独立同分布,可以得到:

从而有:

当经历时间T_E小于联系间隔时间{T_n}中的最小值,即T_E<I₁时,上式退化为以平均联系间隔时间作为剩余延迟期望.当T_E大于或等于{T_n}中记录的最大值时,即T_E≥I_n时,依据公式(1)估计剩余延迟期望的方法失效,因此,我们使用一般更新流剩余寿命的估计方法.根据更新理论,对于一般更新过程的剩余寿命γ_t有:

因而在上述相遇事件更新过程模型中,有:

其中,m(T_E)的含义是在时间T_E范围内更新次数的期望值,显然有m(T_E)=T_E/E[T_i].又因为{T_n}是非负独立同分布序列,因此有:

综合等式(1)和等式(2),得到剩余延迟估计公式如下:

为了评价基于RED的中继选择策略性能,我们设计了一种典型的单副本两跳机会转发策略.在这种策略下,网络中仅存在一份消息副本,当消息携带者将消息传递给下一跳节点后,其自身携带的消息副本会被删除.两跳的单拷贝机会传输只需要选择一个中继节点,这里,我们使用经典的首次相遇中继(first meet relay)策略^[6],即,消息携带者选择遇到的第1个合格节点作为中继.因此,我们称该机会转发算法为RED-FMR算法.它使用每次相遇时决策的中继选择机制,在消息发送者与一个潜在中继节点相遇时,判断是否应该将消息传递给当前遇到的节点.重复这一判断过程,直至消息被交付给下一跳节点或者目标节点.RED-FMR转发算法如算法1所述.

算法1. RED-FMR机会转发算法.

输入:消息的源节点S,目标节点D,S遇到的移动节点序列R₁,R₂,…,R_n(按照时间顺序排列).

FOR Rin R₁,R₂,…,R_n DO

IF R isD THEN

$S\xrightarrow{msg}D$

EXIT;

ELSE IF $E[{{T}_{{{R}_{SD}}}}]-E[{{T}_{{{R}_{RD}}}}]\ge {{T}_{S}}$THEN

$S\xrightarrow{msg}R$

BREAK;

END IF

END FOR

WHILE Rcarries the msg DO

IF Rmeets with D THEN

$R\xrightarrow{msg}D$

EXIT;

END IF

END WHILE

注:T_S为非负的判断阈值,可以取0值

RED-FMR算法在作中继选择决策时,需要交换的控制信息很少.每次决策在消息携带者遇到潜在中继节点时执行,所需要的信息包括目标节点信息以及当前相遇双方与目标的剩余延迟期望值.尽管RED-FMR是一种非常简单的中继转发算法,但它具有很强的适应性,并且易于实际实现.经过简单扩展,可以在RED-FMR的基础上实现多副本、多跳的机会转发算法.我们将在后续工作中讨论这一问题.

本节介绍对基于RED的中继选择策略的性能评价.不同于传统的基于移动模型的机会通信仿真,本文的测试基于大规模实际车辆运动轨迹构造的VDTN环境,因而具有一定的实证价值和现实启示意义.所使用的车辆轨迹来源于Cabspotting项目^{[17, 18]},该项目部署于美国旧金山市海湾区(bay area),车辆运行的核心覆盖区域面积约为13x11km².实验数据集由CRAWDAD^[19]开放平台提供,包含了536辆处于运行状态的出租车在大约25天内的移动轨迹.

实验设置如下:无线通信距离100m,忽略城市环境对无线信号传输的影响,车辆之间距离小于100m时可以建立通信链路;随机配对选取5 000个消息源与目标车辆组合S-D,生成测试集,每对S-D组合的消息产生时间(即S产生向D发送消息请求的时刻)随机分布在数据集中记录时间的前3天之内.

我们主要关注下列问题,以期望获得对车载网络中机会传输中继效率的基本认识:

·使用中继转发相对于直接转发可以降低多少端到端延迟?

·在随机选定的S-D会话中,可以获得多少可用(合格)中继节点与有效中继节点?

我们以上文中提到的基于平均相遇时间(MICT)的中继选择策略与基于RED的策略进行对比.

我们将满足中继选择条件的中间节点称为“合格节点”.S-D会话的合格节点集合用Q表示.显然,如果Q为空集,则没有满足条件的可供选择的节点.合格节点具有降低消息传输延迟的期望,但能否实现这样的期望是不确定的.为了加以区分,我们定义在实际中满足延迟降低期望的合格节点为“有效中继”.延迟降低比例与有效中继在合格节点中的比例,可以反映中继选择策略的效率.

以直接转发延迟为基准,采用统计的方法衡量中继效率.在实验场景中,如果节点S需要向目标D发送一条消息,在遇到D之前,S尝试从所遇到的其他节点中选择某个节点R作为中继,使得消息通过R转发到达D的时间早于S遇到D的时间.记S-D的直接转发延迟为T_DF,通过R中继转发的延迟为T_SRD,那么本文为所使用的机会转发策略性能评价指标定义如下.

延迟降低比例(delay reduced ratio,简称DRR). 延迟降低比例指的是对某次特定的S-D间消息传输请求以及中继节点R,中继转发所节省的延迟时间与直接转发延迟的比例.计算公式如下:

有效中继比例(effective relay ratio,简称ERR). 有效中继比例指的是对某次特定的S-D间消息传输请求,有效中继节点的数量与合格节点数量的比例.计算公式如下:

由于直接转发延迟对潜在的中继节点数量与延迟降低比例有直接影响,因此,我们以直接转发延迟为参考评测中继的效率.

图 5显示了机会中继转发的延迟降低比例.图中横轴表示直接转发延迟,纵轴表示延迟降低比例.为了反映不同水平的直接转发延迟对DRR的影响,我们将横轴以“天”为单位进行划分,统计对应每段时间内的平均延迟降低比例.例如,图中对应于10天的DRR值表示实验结果中直接转发延迟介于10~11天之间的所有S-D组合的平均延迟降低比例.图 5(a)分别展示了所有潜在中继节点(即S遇到D之前所遇到的所有节点)、基于MICT和基于RED的合格节点的平均延迟降低比例.图 5(b)展示了只考虑有效中继时的平均延迟降低比例.从图中可以看出:在大部分情况下,基于MICT的中继选择策略略优于所有潜在中继的平均情况,而基于RED的中继选择策略比基于MICT的策略有较高的平均DRR;特别是在直接延迟比较高时,基于RED的策略有更大的优势.这表明:在机会转发中继选择过程中引入对经历时间的考虑,能够提升中继转发的效率.

图 5(Fig.5)

Fig.5 Delay reduced ratio in average 图 5 平均延迟降低比例

另外,如果不考虑直接转发延迟水平,所有S-D会话的整体平均延迟降低率见表 1.在表中,所有潜在中继节点的整体平均延迟降低比例约为3.93%,而所有满足基于MICT和RED的中继选择条件的合格节点的平均DRR分别为10.25%和23.85%.当只考虑有效中继时,所有潜在的中继节点、基于MICT和RED的中继选择条件的DRR分别为27.79%,32.00%和44.88%.这一结果表明:从整体角度来看,选择合适的中继节点可以降低大约40%以上的直接转发延迟.

表 1(Table 1)

Table 1 Overall delay reducedratio (%)表 1 整体的平均延迟降低比例(%) 潜在中继 MICT合格中继 RED合格中继 所有中继 3.93 10.25 23.85 有效中继 27.79 32.00 44.88

Table 1 Overall delay reducedratio (%)表 1 整体的平均延迟降低比例(%)

由于相遇机会在时序上是离散的随机事件,因而从潜在中继节点集合中预先确定最优中继节点难以实现.选择最先遇到的合格节点作为中继可以避免错失中继机会,因此,首次相遇中继(FMR)是一种常用的基本策略.我们在从车辆轨迹中提取出的VDTN中考察基本的首次相遇中继、基于MICT和基于RED的首次相遇中继策略.图 6展示了3种FMR策略在不同直接转发延迟水平下的平均延迟降低比例.

图 6(Fig.6)

Fig.6 Delay reduced ratio with firstmeet relay 图 6 首次相遇中继(FMR)策略的延迟降低比例

与图 5中的结论相吻合,RED-FMR明显优于基本的FMR策略和基于MICT的FMR策略,这表明,基于RED的单副本机会转发算法能够获得较高的延迟降低收益.表 2给出了3种FMR策略的整体平均DRR.考虑在所有S-D会话的情况下,基本FMR、基于MICT的FMR和RED-FMR的平均延迟降低比例分别为6.77%,11.50%和15.20%;在只考虑首次相遇中继为有效中继的S-D会话时,三者的DRR分别为35.60%,37.22%和53.75%.

表 2(Table 2)

Table 2 Average delay reduced ratio for FMR (%)表 2 FMR策略的平均延迟降低比例(%) 潜在中继 MICT合格中继 RED合格中继 所有中继 6.77 11.50 15.20 有效中继 35.60 37.22 53.75

Table 2 Average delay reduced ratio for FMR (%)表 2 FMR策略的平均延迟降低比例(%)

通过上述对延迟降低比例的研究可以看出:当直接转发延迟较大时,基于RED的中继选择策略性能表现得更好;而在直接转发延迟比较小时,其优势相对较小.特别是在图 5(a)和图 6(a)中,当直接转发延迟小于1天时(对应于图中横轴0),这3种策略的平均延迟降低比例都是负值;而在图 5(b)和图 6(b)中,只考虑有效中继时,DRR在这些位置性能都很好.这表明:当直接转发延迟较小时,潜在中继集合里的有效中继数量较少,此时,使用直接转发相比选择中继转发可能会获得更好的传输性能.从另一方面来看,在这种情况下,仅仅利用历史联系记录信息的中继选择策略效率不高.处理这一缺陷,需要设计更为高效的中继选择算法.

有效中继比例(ERR)是反映中继选择策略效率的重要指标.图 7显示了在不同直接转发延迟水平下,3种策略对应的中继节点数量和有效中继比例.

图 7(Fig.7)

Fig.7 Average relay number can bequalified 图 7 平均合格节点数量与有效中继比例

从图 7(a)可以发现:当直接转发延迟小于5天时,基于RED得到的合格节点数量与MICT相近;而当直接转发延迟比较大时,RED合格节点数量远远小于MICT合格节点数量.直观来看,这种情形表明,使用基于RED的中继选择算法,S-D会话可能找不到一个满意的中继节点来辅助转发,但实际上,从图 7(b)可以看出:在对应的直接转发延迟范围内,RED合格节点中的有效中继比例远远高于MICT和平均情况.由有效中继节点的含义可知, RED策略有更高的概率能够降低延迟.这表明,RED策略的中继选择准确度比较高.另外,图 7也表现出:当直接转发延迟小于1天时,有效中继比例也比较低,大约为40%.这也进一步表明,从概率上讲,此时使用直接转发策略比中继转发策略更有效.

准确预测未来相遇时间很具有挑战性,但引入判断阈值可以提高中继选择的置信度.图 8显示了在设置0~24小时的不同判断阈值的情况下,两种策略的有效中继比例与延迟降低比例.图 8(a)显示了基于RED和MICT的合格节点中的有效中继比例,以及可以找到合格节点的S-D会话的比例(即,合格节点集合Q不为空,称为qualified ratio,简称QR).从图中可以发现:QR与判断阈值是负相关的,而ERR随着阈值的增大而平缓趋近于一个极限值.QR的下降对于中继选择是不利因素,因为这意味着会有更多的S-D会话找不到满足条件的中继节点.而另一方面,ERR随着阈值的增大而增大,表明引入阈值确实可以提高中继选择决策的置信度.但图 8(a)也表明,ERR的增长缓慢,因而对提升中继转发效率的作用有限.比较图 8(a)中RED策略和MICT策略的表现可以看出:在阈值为0时,MICT策略的QR要好于RED策略(分别为97.25%和87.72%);但随着阈值的增加,MICT的QR快速下降,而RED的QR下降相对缓慢.也就是说,RED策略受阈值增大产生的负效应比较小.如图 8(a)所示,在阈值小于5小时的情况下,至少有80%的S-D会话都可以找到RED合格节点,而此时,RED策略的ERR接近于70%.这种程度的效率折中可以接受,因为图 8(b)显示:在提高判断阈值的同时,延迟降低比例也随之有较大提高.

图 8(Fig.8)

Fig.8 Efficiency of RED and MICT with athreshold 图 8 带阈值的RED和MICT中继选择策略效率

本文对机会车载网络中的中继转发效率进行了实证性研究.首先,介绍了一种基于历史相遇记录的剩余延迟估计模型和算法RED,该算法考虑了上次相遇以来的经历时间.基于剩余延迟的估计值,提出一种每次相遇决策的中继选择策略.在基于大规模实际车辆轨迹数据的VDTN中,测试了一种简单的单副本两跳机会转发算法RED-FMR.以端到端传输延迟为出发点考虑中继效率,讨论了机会转发过程中的延迟降低比例和有效中继比例.实验结果表明,引入经历时间的RED中继选择策略效率有比较好的性能表现.如果引入合理的中继选择判断阈值,可以进一步获得中继转发效率的提升.

在后续工作中,我们将关注基于RED-FMR算法扩展多跳多中继和多副本多中继机会转发策略,并测试这些算法在不同城市环境的实际数据集中的中继效率与性能表现.另外,针对现有策略在直接转发延迟较小的情况下中继选择效率不高的问题,通过分析相遇间隔时间与经历时间之间的相关性,改进中继选择策略.