行之知识产权综合服务平台

技术领域

本发明涉及车际通信领域，尤其涉及一种车际通信传输延迟模型建立方 法及装置。

背景技术

车载自组织网络在道路安全和许多商业应用中有很大的潜在用途，比如： 提醒司机潜在的交通堵塞，向司机传播紧急警告避免碰撞事故。当前多数车 际通信的研究仅局限于单跳或短程多跳通信，但是由于广播范围有限，只有 接入点附近的车辆可以直接收到数据，然而这些数据可能对远处车辆里面的 人有用。数据请求可能从距离广播站点几英里或数十英里外发出，通过车载 自组织网络，请求者可以向广播站点发送查询并得到一个答复，只要有答复 某些应用可以容忍数秒甚至数分钟的延迟。尽管这样的服务目前可以通过无 线基础设施(如3G网络)实现，但服务提供商实现接入互联网的成本以及手 机用户访问数据的费用很高，或者当相应的基础设施不存在或者损坏时，这 种信息请求可能无法实现。

车辆的高移动性以及时间与空间维度上的车辆密度不均，导致多跳数据 传输很复杂。比如，农村和夜间交通密度很低，人口稠密区域和高峰期交通 密度很高。在稀疏连接的网络，端到端的连接很困难，而高移动性的车载网 络仍旧为移动车辆提供了移动时断断续续的连接机会。在高速公路模型中， 移动车辆建立一个几跳的、短的通信路径是极有可能的，一个移动的车辆可 以携带数据包并转发给下一个车辆。通过分程传递、携带和转发，某些允许 时延的应用就可以不通过端到端连接，而被传递到目的地。

车辆辅助的车际数据传输是基于携带和转发的想法，高效地将数据包路 由到目的地并在一个合理的延迟内接收应答。最重要的是通过最小的包转发 延迟选择转发路径。当路由不存在时，节点携带包；当新的接收器出现在它 的范围时，节点转发包。与现有的携带、转发方案不同的是，它会利用车载 网络的可预测以及特定交通模式和道路布局导致的移动特性。因此，需要在 实际交通模式和道路布局环境中，根据车辆移动性，建立有效的数据包转发 延迟的模型。

发明内容

为此，需要提供一种车际通信传输延迟模型，解决车际通信传输延迟计 算应用的问题。

为实现上述目的，发明人提供了一种车际通信传输延迟模型建立方法， 其特征在于，包括如下步骤，在路口m与n间传递数据包，根据下列公式计 算延迟D：

D m n = d m n + Σ j ∈ N ( n ) ( P n j × D n j ) ]]>

其中d为预期的数据包转发延迟，P_ij为在I_i通过r_ij转发包的概率；N(j)为 一组I_j的相邻路口，

d满足下列计算方式：

d i j = ( 1 - e - R · ρ i j ) · l i j · c R + e - R · ρ i j · l i j v i j ]]>

其中r_ij为从I_i到I_j的路径；l_ij为r_ij的欧式距离；ρ_ij为r_ij的车辆密度；v_ij为r_ij的车辆平均速度；d_ij为I_i到I_j预期的数据包转发延迟；R指的是无线传 输范围，c是指单跳数据包传输的平均延迟。

进一步地，还包括步骤，为每个相邻路口的延迟D排序，并沿着最小延 迟的路转发数据包，具体包括，在路口可用的通信范围内所有车辆中，向最 小延迟的路上的汽车发送数据包。

进一步地，P_ij的计算方法为：

P i j = Σ c ∈ N ( i ) Q i c × p ij p | ij c . ]]>

p ij p | ij c = P , ij p , ∀ p < c 1 - Σ s = 1 c - 1 P , ij s , p = c 0 , ∀ p > c ]]>

一种车际通信传输延迟模型建立装置，包括延迟计算模块，所述延迟计 算模块用于在路口m与n间传递数据包，根据下列公式计算延迟D：

D m n = d m n + Σ j ∈ N ( n ) ( P n j × D n j ) ]]>

其中d为预期的数据包转发延迟，P_ij为在I_i通过r_ij转发包的概率；N(j)为 一组I_j的相邻路口，

d满足下列计算方式：

d i j = ( 1 - e - R · ρ i j ) · l i j · c R + e - R · ρ i j · l i j v i j ]]>

其中r_ij为从I_i到I_j的路径；l_ij为r_ij的欧式距离；ρ_ij为r_ij的车辆密度；v_ij为r_ij的车辆平均速度；d_ij为I_i到I_j预期的数据包转发延迟；R指的是无线传 输范围，c是指单跳数据包传输的平均延迟。

进一步地，还包括数据包转发模块，

所述数据包转发模块用于为每个相邻路口的延迟D排序，并沿着最小延 迟的路转发数据包；

具体还用于，在路口可用的通信范围内所有车辆中，向最小延迟的路上 的汽车发送数据包。

进一步地，P_ij的计算方法为：

P i j = Σ c ∈ N ( i ) Q i c × p ij p | ij c . ]]>

p ij p | ij c = P , ij p , ∀ p < c 1 - Σ s = 1 c - 1 P , ij s , p = c 0 , ∀ p > c . ]]>

区别于现有技术，上述技术方案通过改进了车际通信传输延迟模型，能 够在车际通信的情景下计算较远距离外的传输延迟，通过估算传输延迟，决 定在交互时的数据包转发策略，提高了车际通信的效率。

附图说明

图1为本发明具体实施方式所述的车际通信传输延迟模型建立方法流程 图；

图2为本发明具体实施方式所述的车际通信传输延迟模型建立装置模块 图；

图3为本发明具体实施方式所述的车际通信传输延迟模型实例；

图4为本发明具体实施方式所述的三角形通路图；

图5为本发明具体实施方式所述的已知边界内传输示意图。

附图标记说明：

200、延迟计算模块；

202、数据包转发模块。

具体实施方式

为详细说明技术方案的技术内容、构造特征、所实现目的及效果，以下 结合具体实施例并配合附图详予说明。

总体思路

车载自组织网络中的车际通信，是基于携带和转发，高效地将数据包路 由到目的地并在一个合理的延迟内接收应答。当路由不存在时，节点携带包； 当新的接收器出现在它的范围时，节点转发包。

虽然地理转发方法的贪婪边界无状态路由(GPSR)，总是选择更接近目 的地的下一跳，在自组网中的数据传输相当高效，但可能不太适合稀疏连接 的车载网络。在稀疏网络，车辆应该尽量利用无线通信，无线通信明显比车 辆携带快得多；若必须携带传输，应尽可能采用移动速度更快的车辆；由于 车载自组织网络的不可预测性，不能希望数据包沿着预先计算的最优路径成 功转发，所以在整个数据包转发过程中路径选择须持续动态执行。

基于以上原则，车辆辅助数据的车际通信传输延迟的建模须对车辆间的 距离分布、源与目的之间的路径分布、路径选择概率等分别建模。

具体方法

A.前提条件

模型的建立前提要求车辆通过短程无线频道(100-250m)进行通信，并 在数据包报头携带特定的信息：如源ID、源位置、数据包生成时间、目的地 位置、过期时间等数据。车辆可以通过三角测量或GPS知道其位置，在周期 性信标中附上自己的物理位置、移动速度、方向信息，这些信息可以被它们 单跳的邻居节点获取。同时，要求车辆配有预加载的数字地图，提供街道地 图和交通统计数据如交通密度、道路上的车辆在不同时刻的速度和路口的交 通信号时间表(如红色信号间隔的长度)。

B.模型的构建

用以下符号定义数据包转发延迟：

1)r_ij：从I_i到I_j的路径；

2)l_ij:r_ij的欧式距离；

3)ρ_ij:r_ij的车辆密度；

4)v_ij:r_ij的车辆平均速度；

5)d_ij:I_i到I_j预期的数据包转发延迟。

假设车辆间的距离遵循指数分布，其平均距离等于1/ρ_ij。则

d i j = ( 1 - e - R · ρ i j ) · l i j · c R + e - R · ρ i j · l i j v i j - - - ( 1 ) ]]>

其中R指的是无线传输范围，c是指单跳数据包传输的平均延迟。等式(1) 指的是车辆间的距离小于R的部分的路，在这部分转发数据包采用 无线传输。其余的路上，车辆需要携带数据。显然，交通密度越大，车辆携 带的占比就越小。

查看车际通信传输延迟模型的一种方法是用一个有向图来表示车载网络， 其中节点代表路口，边指的是连接相邻路口的道路。每条边的方向是交通方 向。两个相邻路口之间的数据包转发延迟是边的权重，给定每个边上的权重， 传统的最优转发路径选择方案是通过应用Dijkstra算法计算从源到目的地的 最短路径。但是由于路口不能自由的选择转发包的向外的边，传统算法存在 缺点无法实现：只有那些有用来携带包的车辆的边，可以用来作为包转发的 候选路径，但是包在下一个路口将去哪个方向没办法知道，不可能计算出完 整的包转发路径。

改进的算法：采用一个随机模型来估计数据传输的延迟，从而用来选择 下一个路(路口)。

请参阅图1，为本发明车际通信传输延迟模型建立方法流程图，其特征在 于，包括步骤S100，在路口m与n间传递数据包，根据下列公式计算延迟D： 定义以下符号：

1)D_ij：包载体在I_i选择沿着路r_ij传递包，从I_i到目的地的预期的包传 递延迟；

2)P_ij：在I_i通过r_ij转发包的概率

3)N(j)：一组I_j的相邻路口

如图3所示的实施例中，展示了有限个路口中对车际通信传输延迟的计 算方法。对于在I_m的一个包，通过路r_mn转发包的预期延迟为：

D_mn＝d_mn+∑_j∈N(n)(P_nj×D_nj)(2)

图4显示了，如何将(2)应用到一个只包含三个路口I_a、I_b、I_c的简单三角 形路。假设一个数据包到达了I_a，并且终点在I_c。转发方案需要决定是否通过 路转发到I_c或I_b。这是通过计算D_ac和D_ab的值，并选者较小的。通过应用(2)， 得到以下线性方程：

D a c = d a c D a b = d a b + P b a · D b a + P b c · D b c D b a = d b a + P a b · D a b + P a c · D a c D b c = d b c D c b = 0 D c a = 0. - - - ( 3 ) ]]>

注意到d_cb和d_ca都为0，因为包已经到达了目的地I_c不再转发。可以很容 易地计算(3)，并得到D_ac和D_ab。

D_ac＝d_ac

D a b = 1 1 - P a b · P b a × ( d a b + P b a · d b a + P b a · P a c · d a c + P b c · d b c ) ]]>

在图5所示的实施例中，因为涉及到无限的未知的路口，在任意两个路 口间计算最小转发延迟是不可能的，但通过设定一个边界，包括源和目的地 的连接图，可以计算它们之间的预期最低转发延迟。图5显示了一个这样的 边界，包括发送者和目的地(热点)。假设使用的边界是一个圆，圆心位于目的 地。如果包与目的地之间的距离不足3000m，则圆半径设成4000m；否则， 圆半径是包与目的地之间的距离加上1000m。当然，也有很多其他设置边界 的方法，只要将目的地包括在其中。由于只有边界以内的路被用来当作计算 延迟的可用路径，一个包含更多高密度街道的边界，通常可以找到更接近最 优的路径，但需要更多的计算开销。因此，当选择边界时，需要在延迟估计 的计算复杂性和准确性之间的做一个权衡。

因为边界内的路口数量是有限的，可以推出(2)相对于边界内路口的每一 个向外的边[与推导(3)使用的方法类似]，可以得到一个n×n的线性方程组，n 表示边界内路的数目。

遵循线性方程系统的一般表示方法，将未知的D_ij重命名为x_ij，将d_ij和x_ij的下标ij对每对ij重命名为一个独一无二的数字，并将P_ij的下标按照它在方 程中的位置进行重命名，可以推出含有n个未知数x₁，x₂，…，x_n的n个线性 方程

x₁＝d₁+P₁₁x₁+P₁₂x₂+…+P_1nx_n

x₁＝d₂+P₁₁x₁+P₂₂x₂+…+P_2nx_n

·

·

·

x_n＝d_n+P_n1x₁+P_n2x₂+…+P_nnx_n

转换成以下的矩阵：

(P₁₁-1)x₁+P₁₂x₂+…+P_1nx_n＝-d₁

P₂₁x₁+(P₂₂-1)x₂+…+P_2nx_n＝-d₂

·

·

·

P_n1x₁+P_n2x₂+…+(P_nn-1)x_n＝-d_n

等价于(P-E)·X＝-D(4)

其中， X = x 1 x 2 · · · x n , ]]>以及 D = d 1 d 2 · · · d n . ]]>

这个线性方程组有唯一解，解这个方程的典型方法是使用高斯消去法， 它的时间复杂度是O(n³)。

通过求解(4)，得到当前路口I_i的D_ij。在图1所示的实施例中，还包括步 骤S102为每个相邻路口的延迟D排序，并沿着最小延迟的路转发数据包，具 体包括，在路口可用的通信范围内所有车辆中，向最小延迟的路上的汽车发 送数据包。具体地，包载体会为每个邻居路口I_j的D_ij排序，并沿着更低延迟的 路转发包。从而，在路口可用的通信范围内(叫做接触)的所有车辆中，包 会转发到拥有最小延迟的路上的汽车。如果没有可用的接触，或者所有接触 要走的路比包载体要走的路延迟更大，则包载体会带着包通过这个路口并寻 找下一次转发机会。

C.在I_i通过r_ij转发包的概率P_ij的计算

P_ij的计算方法非常重要。暂以方向优先探测作为数据传输协议(方向优 先探测协议严格遵循方向的优先级，对于选定的方向，包载体会选择朝着选 定方向移动的接触转发。也就是说，最接近选定方向的接触会被设成下一跳)。 其它协议可以通过类似方法建模计算。

假设每个路只有单向、双向通行，并且路口是信号灯路口或独立路口， 并且假设到达路口的车遵循泊松分布。

一个包载体停留在路口模式的预期时间，被称为接触时间。在一个信号 灯路口I_i的接触时间，记为t_i，只与I_i处的信号灯间隔长度有关，并且假设可 以从数字地图上得到。而在一个独立路口，所有方向的车辆都可以流畅地穿 过，不需要停下来。假设，穿过路口的平均车速与离开路口路上的平均车速 相同，并且设R_int为路口区域半径，路口区域是圆形区域且路口点是圆心。方 程(5)计算了进入路口I_i并向相邻路口I_i移动的包载体的接触时间(T_ij)。

只有当包载体至少遇到一个朝着路r_ij移动的接触时，包载体才能够在I_i处 朝着路r_ij转发包。当包载体进入路口区域时，计算它至少遇到一个路r_ij移动 的接触的概率(CP_ij)。设N(T_ij)表示在时间间隔T_ij内，路口区域可以看见多 少朝着路r_ij移动的接触，并设λ_ij表示离开I_i并朝着路r_ij移动的接触的平均率， 即λ_ij＝ρ_ij·v_ij(ρ_ij，v_ij在前面已定义)。根据泊松分布的定义：

CP i j = Pr o b ( N ( T i j ) ≥ 1 ) = 1 - Pr o b ( N ( T i j ) = 0 ) = 1 - e - λ i j T i j ( λ i j T i j ) 0 0 ! = 1 - e - ρ i j v i j T i j ]]>

如果路口I_i只有两个向外的路r_ia和r_ib，且满足D_ia<D_ib，其中接触概率CP_ia和CP_ib分别是接触朝着路r_ia和r_ib的接触概率。P_ia会等于CP_ia，P_ib会等于CP_ib- CP_ia·CP_ib。这是以为，当包载体通过路口I_i时，如果两个接触都可用，预期 的最小传输延迟的路径会被选择。因此，要计算I_i处的P_ij，我们需要首先根据 D_ij非递减顺序，对所有j∈N(i)的CP_ij进行排序。然而，D_ij在这一阶段不能得 到，我们使用路r_ij的方向与当前路口到目的地的矢量的夹角，记为θ_ij，用于 近似D_ij。这是因为一个有更小角度的路更可能会到达一个更接近目的地的位 置。CP_ij排序列表如下：

其中n＝|N(i)|

j_i的下标隐含了一个有意义的顺序

θ ij 1 ≤ θ ij 2 ≤ θ ij 3 ≤ ... ≤ θ ij n - - - ( 6 ) ]]>

使用基础的概率，可以计算一个包在I_i向路r_ij转发的概率。结果记为P’_ij。

P , ij 1 = CP ij 1 ]]>

P , ij 2 = CP ij 2 - CP ij 1 · CP ij 2 ]]>

P , ij 3 = CP ij 3 - ( CP ij 1 · CP ij 3 + CP ij 2 · CP ij 3 ) + CP ij 1 · CP ij 2 · CP ij 3 ]]>

·

·

·

假如一个包载体在通过I_i后会向路移动(直走或转弯)，包只会被转发 到更高或相等优先级的路上。也就是说，对于一个路如果k>c，等 于0，包载体会缓存数据而不是将它转发到一个更低优先级的路上。因此，包 载体离开I_i向移动，路将被选为包转发方向的概率，可以由以下条件概 率定义：

p ij p | ij c = P , ij p , ∀ p < c 1 - Σ s = 1 c - 1 P , ij s , p = c 0 , ∀ p > c - - - ( 7 ) ]]>

设Q_ic表示一个车辆从当前路口I_i移向下一个邻接路口I_c的概率(直行或 转弯)。P_ij可以通过以下计算：

P i j = Σ c ∈ N ( i ) Q i c × p ij p | ij c . - - - ( 8 ) ]]>

将计算结果代入(2)式，能够有效提高车际通信对传输延迟估计的准确 度，通过应用该传输概率计算方法，也进一步完善了车际通信传输延迟模型。

见图2所示，为一种车际通信传输延迟模型建立装置，包括延迟计算模 块200，所述延迟计算模块200用于在路口m与n间传递数据包，根据下列 公式计算延迟D：

D m n = d m n + Σ j ∈ N ( n ) ( P n j × D n j ) ]]>

其中d为预期的数据包转发延迟，P_ij为在I_i通过r_ij转发包的概率；N(j)为 一组I_j的相邻路口，

d满足下列计算方式：

d i j = ( 1 - e - R · ρ i j ) · l i j · c R + e - R · ρ i j · l i j v i j ]]>

其中r_ij为从I_i到I_j的路径；l_ij为r_ij的欧式距离；ρ_ij为r_ij的车辆密度；v_ij为r_ij的车辆平均速度；d_ij为I_i到I_j预期的数据包转发延迟；R指的是无线传 输范围，c是指单跳数据包传输的平均延迟。

在进一步的实施例中，装置还包括数据包转发模块202，

所述数据包转发模块202用于为每个相邻路口的延迟D排序，并沿着最 小延迟的路转发数据包；

具体还用于，在路口可用的通信范围内所有车辆中，向最小延迟的路上 的汽车发送数据包。

进一步地，P_ij的计算方法为：

P i j = Σ c ∈ N ( i ) Q i c × p ij p | ij c . ]]>

p ij p | ij c = P , ij p , ∀ p < c 1 - Σ s = 1 c - 1 P , ij s , p = c 0 , ∀ p > c . ]]>

区别于现有技术，上述装置通过改进了车际通信传输延迟模型，能够在 车际通信的情景下计算较远距离外的传输延迟，通过估算传输延迟，决定在 交互时的数据包转发策略，提高了车际通信的效率。

需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来 将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示 这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、 “包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系 列要素的过程、方法、物品或者终端设备不仅包括那些要素，而且还包括没 有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者终端设 备所固有的要素。在没有更多限制的情况下，由语句“包括……”或“包含……” 限定的要素，并不排除在包括所述要素的过程、方法、物品或者终端设备中 还存在另外的要素。此外，在本文中，“大于”、“小于”、“超过”等理解为不 包括本数；“以上”、“以下”、“以内”等理解为包括本数。

本领域内的技术人员应明白，上述各实施例可提供为方法、装置、或计 算机程序产品。这些实施例可采用完全硬件实施例、完全软件实施例、或结 合软件和硬件方面的实施例的形式。上述各实施例涉及的方法中的全部或部 分步骤可以通过程序来指令相关的硬件来完成，所述的程序可以存储于计算 机设备可读取的存储介质中，用于执行上述各实施例方法所述的全部或部分 步骤。所述计算机设备，包括但不限于：个人计算机、服务器、通用计算机、 专用计算机、网络设备、嵌入式设备、可编程设备、智能移动终端、智能家 居设备、穿戴式智能设备、车载智能设备等；所述的存储介质，包括但不限 于：RAM、ROM、磁碟、磁带、光盘、闪存、U盘、移动硬盘、存储卡、记 忆棒、网络服务器存储、网络云存储等。

上述各实施例是参照根据实施例所述的方法、设备(系统)、和计算机程序 产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程 图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流 程和/或方框的结合。可提供这些计算机程序指令到计算机设备的处理器以 产生一个机器，使得通过计算机设备的处理器执行的指令产生用于实现在流 程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的 装置。

这些计算机程序指令也可存储在能引导计算机设备以特定方式工作的计 算机设备可读存储器中，使得存储在该计算机设备可读存储器中的指令产生 包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/ 或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机设备上，使得在计算机设备上执 行一系列操作步骤以产生计算机实现的处理，从而在计算机设备上执行的指 令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个 方框中指定的功能的步骤。

尽管已经对上述各实施例进行了描述，但本领域内的技术人员一旦得知 了基本创造性概念，则可对这些实施例做出另外的变更和修改，所以以上所 述仅为本发明的实施例，并非因此限制本发明的专利保护范围，凡是利用本 发明说明书及附图内容所作的等效结构或等效流程变换，或直接或间接运用 在其他相关的技术领域，均同理包括在本发明的专利保护范围之内。