CN101808275B - 一种基于车辆移动趋势预测的车载网络数据转发方法 - Google Patents

Abstract

本发明公开了一种基于车辆移动趋势预测的车载网络数据转发方法，属于无线通信领域。本发明方法包括：在一段时间内，车辆记录其行驶时的轨迹数据，得到一数据集；之后，车辆之间相互靠近时，计算各自的移动趋势，车载数据按移动趋势由高到低转发，最终由移动趋势较低的车辆在经过基站时转发至基站；所述移动趋势按式(4)计算：其中，T_i ^(M)表示车辆的移动趋势；M表示设定的街道转移次数；S表示街道集合；p_ij ^(m)表示车辆由当前街道i经m步转移后到达另一街道j的概率，该值基于所述数据集计算；表示所述另一街道和距离最近的基站之间的欧氏距离。本发明可用于车载网络等技术应用。

Description

一种基于车辆移动趋势预测的车载网络数据转发方法

技术领域

本发明涉及车载网络，尤其涉及一种基于车辆移动轨迹预测的车载网络数据转发方法，属于无线通信领域。

背景技术

车载网络(VANET)利用车辆上普遍安装的无线通信设备，如802.11无线网卡，组成具有高移动性、覆盖面广的网络结构，利用车辆移动相互靠近形成的短暂的通信机会完成数据转发。近年来各研究机构研发了一系列有代表性的车载网络原型系统，例如CarTel(Bret Hull，Vladimir Bychkovsky，Kevin Chen，Michel Goraczko，Allen Miu，Eugene Shih，Yang Zhang，Hari Balakrishnan，and Samuel Madden，“CarTel：A Distributed Mobile SensorComputing System.”in Proc.ACM SenSys，2006)提出利用公交车收集路旁固定传感器网络的感知数据；Pothole Patrol(Jakob Eriksson，Lewis Girod，Bret Hull，Ryan Newton，SamuelMadden，Hari Balakrishnan，“The Pothole Patrol：Using a Mobile Sensor Network for RoadSurface Monitoring.”in MobiSys，2008)提出在车辆上部署加速度传感器采集路面状况信息。这些应用原型系统表明车载网络数据转发方法有重要的应用前景。

根据数据转发是否依赖车载导航系统(Navigation System)可以将现有的车载网络数据转发方法分为两大类：(1)基于地理位置的数据转发方法；(2)基于车载导航系统的数据转发方法。

在基于地理位置的数据转发方法中(C.Lochert，H.Hartenstein，J.Tian，H.Fuessler，D.Hermann，and M.Mauve，“A routing strategy for vehicular ad hoc networks in cityenvironments，”in In Proceedings of the IEEE Intelligent Vehicles Symposium，2003，pp.156-161.)，数据转发通常可以分为两个阶段，即数据转发阶段和转发恢复阶段。在数据转发阶段中，携带数据的车辆总是把数据转发给离基站距离更近的其它车辆，随着数据的逐跳转发，最终把数据转发到基站；如果车辆周围没有比自己距离基站更近的其它车辆，则进入转发恢复阶段，此时，车辆根据某种策略选择通信半径内的一个邻居进行数据转发，例如随机选择。这种方法适用于网络中节点分布密集的情况，对于大规模城市环境下，车辆分布较为稀疏的情况并不适合。

基于车载导航系统的数据转发方法包括Geopps等(I.Leontiadis and C.Mascolo，“Geopps：Geographical opportunistic routing for vehicular networks，”in World of Wireless，Mobile and Multimedia Networks，2007.WoWMoM 2007.IEEE International Symposium on a，2007，pp.1-6)，这些方法往往假设车辆上安装了车载导航系统，该系统能为车辆规划移动路线，并提供实时的路况信息。依据这些信息可以辅助车辆之间的数据转发，例如，Geopps中假设已知各个车辆的移动轨迹，那么车辆相遇时即可把数据转发给移动轨迹距离基站位置更近的车辆。这种方法严格依赖导航系统，存在以下缺陷：车载导航系统提供的路况信息往往难以做到实时精确，因此，依据这些信息作出的转发决策可能存在错误；目前，只有少数车辆装备车载导航系统，要求所有车辆安装导航系统的假设并不成立。

发明内容

本发明的目的在于克服现有技术中存在的问题，提供一种基于车辆移动轨迹预测的车载网络数据转发方法。

概括地说，本发明方法包括：

在一段时间内，车辆记录其行驶时的轨迹数据，得到一数据集；

之后，车辆之间相互靠近时，计算各自的移动趋势，车载数据按移动趋势由高到低转发，最终由移动趋势较低的车辆在经过基站时转发至基站；

所述移动趋势按式(4)计算：

$T_i^{\left(M\right)}=\underset{m\∈[\mathrm{1,2},...,M]}{\min }\underset{j\∈S}{\mathrm{\Σ}}(p_{\mathrm{ij}}^{\left(m\right)}\·u_{S_j})---\left(4\right),$

其中，T_i ^(M)表示车辆的移动趋势；M表示设定的街道转移次数；S表示街道集合；p_ij ^(m)表示车辆由当前街道i经m步转移后到达另一街道j的概率，该值基于所述数据集计算；

表示所述另一街道和距离最近的基站之间的欧氏距离。

下面详细说明上述方法。

本发明将城市模型看做由街道组成的网状结构，各条街道存在两个端点，端点是路口，如图1所示：

图中路口记作I，车辆在城市中行驶，总是从一个路口行驶到下一路口，如图中车辆当前处于I₁位置，在经过一段时间行驶后，下一个路口I₂可能处于I_1上，I_1下，I_1左，或I_1右。在上述模型中，可以把车辆的行驶轨迹视作一串由路口组成的序列。两个路口之间的部分称为一条街道，记作S。

由于人们日常生活往往具有一定规律性，例如，某人每天都驾车经过同样或相近的路线去工作地点，或者从工作地点回家，因此，可以利用这种移动路线上具有的规律性来辅助车辆之间数据的转发。

首先，车辆单独收集自身行驶轨迹数据，并依据这些数据利用2阶马尔可夫模型进行建模，得到车辆移动轨迹的预测概率。建模后得到如下转移概率信息：

P(I_i+1|I_i，I_i-1)                     (1)

公式(1)表示根据车辆前两个经过的路口I_i和I_i-1预测下一时刻经过的路口为I_i+1的概率。建模过程中，车辆首先收集车辆移动的轨迹信息，这些信息可以利用GPS和数字地图得到，得到的信息表示为由路口组成的序列，例如：I₁→I₂→I₃→...。经过一段时间的数据收集(如一周或一月时间)，可以得到车辆行驶轨迹数据集，统计该数据集中的轨迹信息，可以得到所有路口之间的2阶马尔可夫转移概率信息，即公式(1)。

根据前面讨论，一条街道是两个路口之间的部分。为了方便描述，记S_j＝(I_j，I_j-1)，之所以可以这样标记，是因为车辆总是沿着街道行驶，所以经过的路口也一定是连续的，因此，S_j可以表示I_j及其上一路口I_j-1之间的街道。需要注意的是，两个路口I_i和I_i-1之间的街道按照车辆移动顺序分为(I_i，I_i-1)和(I_i-1，I_i)两种情况，虽然从地理位置上看两者相同，但在转移概率计算时，由于车辆是沿相反方向移动的，转移概率是不相同的。这样，根据公式(1)可以将车辆的移动轨迹看做由P(S_i+1|S_i)确定1步转移概率的马尔可夫链。直观上P(S_i+1|S_i)表示车辆由街道S_i驶入街道S_i+1的转移概率。m步转移概率的chapman-Kolmogorove方程由公式(2)表示，其中p_ij＝P(S_i|S_j)，而p_ij ^(m)表示S_i经过m步转移后到达S_j的概率。该方程直观上的含义是将多步转移概率进行分解，即在起始状态i和结束状态j之间引入一个中间状态r(r表示从i到j的转移过程中经过的一个街道)，这样就能将多步转移的步数m逐渐降低，经过迭代计算后降低为多个1步转移以便于计算。

$P_{\mathrm{ij}}^{\left(m\right)}={\mathrm{\Σ}}_{r\∈S}(p_{\mathrm{ir}}^{\left(k\right)}\·p_{\mathrm{rj}}^{(m-k)})---\left(2\right)$

其中，k表示转移步数，k＝1，2，…(m-1)。

假设城市中部署了多个基站，那么对于某街道S_i，其效用值

表示其距离基站的远近，由于存在多个基站，所以把该效用值定义为S_i与最近的基站之间的欧氏距离，即：

$u_{S_i}=\underset{j\∈[1,n]}{\min }\mathrm{dis}\tan \mathrm{ce}(S_i,B_j)---\left(3\right)$

根据公式(2)和(3)，按下式4定义车辆的移动趋势：

$T_i^{\left(M\right)}=\underset{m\∈[\mathrm{1,2},...,M]}{\min }\underset{j\∈S}{\mathrm{\Σ}}(p_{\mathrm{ij}}^{\left(m\right)}\·u_{S_j})---\left(4\right)$

移动趋势T_i ^(M)从直观上看预测了该车辆从当前所在的街道S_i经过M个路口(即经过M次转移)后，它与基站之间的相对位置关系，如果车辆驶向基站，则该值变小，相反如果车辆驶离基站，则该值增大。车辆在行驶过程中，可能先朝基站方向移动，然后又背向基站移动，则在整个过程中，车辆与基站之间的距离先逐渐变小，后逐渐变大。公式(4)只取整个过程中车辆与基站之间的最小距离，作为车辆的移动趋势。图2为一个示例，图中虚线表示车辆的可能移动轨迹，由于车辆A相比车辆B从未来的移动轨迹上看距离基站位置更近，车辆A的移动趋势更小。

当两辆以上(≥2)车辆相遇时，每个车辆根据自身轨迹信息统计出上述移动趋势信息，车辆之间首先互换移动趋势信息，携带消息的车辆比较移动趋势的大小，如果携带数据的车辆的移动趋势较大，则该车辆将数据转发到移动趋势小的车辆，由它代替原车辆携带数据移动，进一步进行数据转发，直至最终由某一辆移动趋势较小的车辆在靠近基站时将数据发送给基站，从而完成一个数据转发操作。

尽管上面根据已有的车辆行驶轨迹信息通过移动趋势由高到低的机制使车载数据通过逐跳转发越来越靠近基站，但存在车辆临时改变路径或因其他原因而背离理想中的预测值从而不能按设定的机制实现数据转发的情况，为了提供一定的补偿机制，本发明进一步设定如下规则：

在一定时间内，如果载有数据的车辆未能将数据转发给另一车辆，或者将数据发送给基站，则该车辆将其载有的数据随机转发给靠近它的任意车辆，以免数据不能及时传递，甚至出现数据丢失的情况。

和现有技术相比，本发明的优势在于：

1、本发明提出基于历史数据建模的车辆移动趋势预测，不依赖于特定的车载导航系统，具有更普遍的适用性；

2、本发明相基于车辆在未来移动的趋势预测进行数据转发，相比已有的基于当前位置或移动方向的预测方式有显著优势。

附图说明

图1表示街道组成的网状结构示意图；

图2表示车辆的移动趋势示意图；

图3表示本发明实施例的数据转发流程示意图。

具体实施方式

下面通过一具体实施例结合附图对本发明作进一步说明。

本实施例按照附图3所示的数据转发流程实现车载网络中的数据转发。

1)车辆A和B经过一个月的行驶轨迹数据初始积累后，各得到一个初始数据集，此后，该数据集持续更新。

2)假设车辆A内部设置了数据采集器，则车辆A携带采集的数据行驶；假设车辆B未设置数据采集器，则车辆B未携带数据行驶。当然用于转发的原始数据可以是如上所述来自于数据采集器，也可以是来自其他数据源的数据，可根据情况具体设置。

3)车辆A与车辆B相遇后，各自根据当前所处的街道基于储存的上述数据集计算移动趋势T_i ^(M)，然后立即交换该移动趋势值。

4)车辆A比较车辆A与车辆B的移动趋势值，如果车辆A的移动趋势值大于车辆B的移动趋势值，则车辆A将携带数据转发给车辆B。

5)如果4)不成立则车辆A继续携带消息行驶，等待下一次的相遇，或者在经过基站或者满足其他向基站转发数据的条件时直接将数据转发到基站。如果两个小时内未能将数据转发给其他车辆或者基站，则自动将数据转发给两小时后经过车辆A的任何车辆，以保证数据的及时传递。

Claims (7)

1.一种基于车辆移动趋势预测的车载网络数据转发方法，包括：

在一段时间内，车辆记录其行驶时的轨迹数据，得到一数据集；

之后，车辆之间相互靠近时，计算各自的移动趋势

所述移动趋势

指车辆从当前所在的街道i经过M个路口后与基站之间的相对位置关系，按式(4)计算：

$T_i^{\left(M\right)}=\underset{m\∈[\mathrm{1,2},...,M]}{\min }\underset{j\∈S}{\mathrm{\Σ}}(p_{\mathrm{ij}}^{\left(m\right)}\·u_{S_j})---\left(4\right),$

其中，表示车辆的移动趋势；M表示设定的街道转移次数；S表示街道集合；

表示车辆由当前街道i经m步转移后到达另一街道j的概率，该值基于所述数据集计算；

表示所述另一街道和距离最近的基站之间的欧氏距离；

车载数据按移动趋势由高到低转发，最终由移动趋势较低的车辆在经过基站时转发至基站。

2.如权利要求1所述的基于车辆移动趋势预测的车载网络数据转发方法，其特征在于，所述一段时间之后，所述车辆继续记录其行驶时的轨迹数据并以此更新所述数据集。

3.如权利要求1所述的基于车辆移动趋势预测的车载网络数据转发方法，其特征在于，所述轨迹数据在所述数据集中以车辆驶经的路口序列的方式储存。

4.如权利要求1-3任意一项所述的基于车辆移动趋势预测的车载网络数据转发方法，其特征在于，所述一段时间的长度为一周或一月。

5.如权利要求1所述的基于车辆移动趋势预测的车载网络数据转发方法，其特征在于，M＝3。

6.如权利要求1所述的基于车辆移动趋势预测的车载网络数据转发方法，其特征在于，

按式(2)计算：

$p_{\mathrm{ij}}^{\left(m\right)}=\underset{r\∈S}{\mathrm{\Σ}}{p}_{\mathrm{ir}}^{\left(k\right)}\·p_{\mathrm{rj}}^{(m-k)}---\left(2\right)$

其中，k表示转移步数，k＝1，2，…(m-1)，r表示从i到j的转移过程中经过的一个街道。

7.如权利要求1所述的基于车辆移动趋势预测的车载网络数据转发方法，其特征在于，在设定时间长度内，若载有数据的车辆未能将数据转发给另一车辆，或将数据发送给基站，则该车辆将其载有的数据随机转发给靠近它的任意车辆。

Images