车辆自组织网络中使用公交车辆协助的数据分发*

2014-09-13梁庆中胡成玉

计算机工程与科学 2014年11期

关键词：分片投递网络通信

姚宏，滕超，丛磊，梁庆中，胡成玉

(中国地质大学(武汉)计算机学院，湖北武汉 430074)

车辆自组织网络中使用公交车辆协助的数据分发*

姚宏，滕超，丛磊，梁庆中，胡成玉

(中国地质大学(武汉)计算机学院，湖北武汉 430074)

车辆间联网通信所组成的自组织网络，受到了学术界的广泛关注。由于车辆的动态性和信号覆盖范围的间断连接特性，这类网络的通信行为表现出时延容忍网络的特征。在城市街区中，车辆密度较大。观察到公交车辆行驶轨迹的规律特征，利用网络编码技术，结合携带转发，提出了一种基于公交车辆协助的导向性数据分发算法，实现了在城市街区场景中高效、可靠的协助式数据内容分享。实验表明，在降低网络通信开销的前提下，该方法有效地提高了城市街区中内容分享数据投递的成功率。

车辆自组织网络；网络编码；公交车协助

1 引言

在车辆间联网通信所构成的车辆自组织网络[1,2]中，由于车辆的动态性和信号覆盖范围的间断连接特性，这类网络的通信行为表现出时延容忍网络[3]的特征，受到了国内外学术界的广泛关注。本文着眼于城市主城区多条道路所构成的区域网络数据分享。在这一场景中，车辆密度较大。大部分路上行驶的车辆，其运动规律体现了随机性。观察到公交车辆运行轨迹严格遵循特殊的路线，成为车辆自组织网络中的一种特殊角色。本文提出了一种基于公交车辆结点协助式通信的数据分享传输优化策略，实现了城市街区场景中高效、可靠的协助式数据内容分享。通过网络模拟实验环境，对所提出的数据传输策略进行了测试评估。

2 问题提出及场景描述

在一些新兴的车载网络的应用程序(例如播客、广告推送、交通导航等)中，数据内容需要被分发到一系列目标车辆结点。对于这样的应用，目标车辆结点可能分布于多条街道之中。在城市街区中，车辆密度较大，网络通信需求随之上升。传统的基于传染路由的策略，其数据通信总开销会随着数据副本的增加而激增，在给网络传输带来极大负担的同时，无法提供成比例的性能提升。

本文研究的通信场景为：城市街区中，由若干条街道组成的城市区域，如图1所示。在该区域中存在多条互相联通贯穿的双向街道，即车辆结点能够依据各自具体目的地点，自由地在街区中行驶运动。其中，公交车辆由于必须按固定线路行驶，因而体现出了特殊的运动规律。

Figure 1 Urban streets topology图1 城区中的街道拓扑

如图2所示，将城市街区的各个街道根据地理位置信息可以划分为不同的街区网格。

Figure 2 Grid modeling of blocks图2 街区网格建模

当车辆自组织网络产生对若干临近街道的车辆结点数据分享需求时，街区划分的网格可以直接被抽象为本次数据分享网络通信的目标区域。城市街区的任一网格中，车辆结点双向行驶运动。在街区中的各个十字路口处，车辆结点依据自身目的地点可自由地行驶、转向或离开网络拓扑所定位的网格。同时，在网格边缘的街道路口处，也可能有新的车辆结点加入网络通信的拓扑中。本文不考虑路边基站的作用，仅通过车辆之间的携带转发，观察公交车辆作为数据携带者的作用。

3 基于公交车辆协助的数据分发算法

对于车辆自组织网络的数据路由[4,5]，中继车辆结点是否能依据原路由的方向规律行驶，对转发数据传输成功率有着直接的影响。在城市街区场景中，通常中继车辆结点的行驶轨迹是具有随机性的。在这种动态变化的数据路由下，传统的基于传染路由、机会主义路由的数据传输方案往往会产生大量的数据副本，导致最终被成功传输的数据比例下降，也增加了网络通信过程中的传输开销。并且，在某些带有数据时间有效性需求的数据分发应用中，传统的解决方案在数据成功投递率上也有待改进。

选择城市交通中行驶轨迹固定、运动速度呈现周期规律化的公交车辆，作为理想的数据路中继站点，可以避免由于车辆行驶路线的随机性而造成的中继失效。

对于任意一条带有方向性的数据路由，能否筛选出在第一时间内与目标结点交汇的(多跳)中继车辆结点，将直接影响到通信的传输延时。不失一般性地，可描述为：

假定要将数据包从车辆A传输至车辆B，并且已知车辆A现在所在位置〈T0,LA〉(表示在时间T0时A的位置)。

需要知道车辆B的行驶轨迹PathB={〈T0,L0〉,〈T1,L1〉,〈T2,L2〉,〈T3,L3〉,…}。

传输任务转化为：在PathB中找到一个最小值Tx，使数据包能在Tx内被携带至Lx。

基于上述利用公交车辆作为中继核心的思想，在场景中导入城市街区的实际街道拓扑图(如图3所示，图示为湖北省武汉市光谷一带的公路街道)，从中可提取出在此街区当中的公交线路图，覆盖到各个街道，并在公交路口交汇(如图3，709路公交车覆盖鲁磨路，755路公交车覆盖关山一街，二者轨迹在图中相交)。

Figure 3 A snapshot of route buses intersection in the urban blocks图3 城市街区中公交车辆路线的交汇快照

利用公交车辆的运动规律，提出路由中继的初步方案：

首先，找出PathB与公交覆盖图中的“碰撞”点，设为IntersectionB{〈T0,L0〉,〈T1,L1〉,〈T2,L2〉,〈T3,L3〉,…}，碰撞点不一定是相交点，还可以是“临近”点的概念。在多跳的数据传递中，最后一跳可以依靠其他移动的车辆结点来完成。由于此时数据传递已接近目标结点，所以延时和传输成功率都有保证。其次，在IntersectionB中，可得出从LA到达各个碰撞点Lx的时间tx(Lx本身在公交线路内，可通过使用google map API等工具获取)。在IntersectionB中找到一个Tx，使满足Tx>tx且任取〈Ty,Ly〉∈IntersectionB，Tx

然而，基于城市区域范围内的数据分享通信需求，由于IntersectionBus无法确保能够与所有数据分享的目标结点发生“轨迹碰撞”，因此，单纯的基于公交车辆中继转发，亦无法为基于城市区域范围内的数据分享通信需求给出有效的解决方案。所以，在数据分发的过程中，仍需要除公交车辆结点之外的其他中继结点。由于行驶线路的固定性、行驶速度的稳定性等诸多因素，公交车辆结点可以作为区域数据分发过程的核心路由结点。数据传输的过程可归结为三个子阶段：

(1) 通过当前数据所在地，选择从数据源至目标街区的公交车辆协助路径；

(2) 从数据源点将经过网络编码[6,7]的数据分片推送至公交车辆协助路径；

(3) 完成数据从公交车辆协助路径至目标车辆结点的数据推送。

第一阶段，选择从数据源所在地至目标街区所依赖的公交车辆协助路径，在给定的公交线路图中，首先通过数据内容的截止时间T进行筛选，即无法在数据有效期过期之前，从数据源点进入目标车辆结点所在网格的公交线路被排除。其次，通过截止时间T可以获取第i个公交车辆线路，即在截止时间T之前，在目标网格中行驶的距离ζi。当中继公交车辆在目标区域网格中携带数据行驶的范围增加时，其数据转发的路由收益也随之提升。

对于特定数量的目标车辆结点，本算法给出了一个推送覆盖阈值因子δ，即对于一定数量的目标车辆结点，公交车辆协助行驶范围在目标网格中至少需覆盖δ*N个交叉路口(N为当前路况中目标车辆的总数)。在所有的公交线路图中，依次筛选出当前数据推送范围最大的公交车辆协助路径，直至满足推送覆盖阈值(公交路线中交会路口不视为额外的范围覆盖)。

第二阶段，尝试将经过网络编码的数据分片，从数据源点推送至公交车辆协助路径。这一过程依据在阶段一中确立的不同公交车辆协助的推送覆盖范围，优先将数据分片路由至推送范围最大的公交车辆结点，并依次为选定的公交车辆协助线路中提供数据分片。此时，已知车辆A现在所在位置〈T0,LA〉。针对公交车B的行驶轨迹PathB= { 〈T0,L0〉 ,〈T1,L1〉, 〈T2,L2〉 , 〈T3,L3〉，…}，传输任务转化为：在PathB中找到一个最小值Tx，使数据包能在Tx内被经过数据原地的某一车辆携带至Lx。以此，完成数据内容从数据源到公交车辆协助路径的跳转。

第三阶段，通过车辆结点的携带转发，完成数据从公交车辆协助路径，到目标车辆结点的数据推送。在这一阶段中，公交车辆结点充当了移动的基站结点角色。在传染路由中，携带数据结点一段时间后将释放数据并获得“免疫”。而公交车辆结点在传染的过程中，直至数据分享完成，公交车辆结点一直持有所携带的数据分片。

算法描述如下：

算法1Bus assistance path selection

while current pushing corners less than theδ*Nthen

for all bus path do

select the path covering most corners in the target grid;

update current pushing corners;

end for

end while

for all bus assistance path do

push the data to assistance path with largest pushing cover;

end for

transfer the coded data packets with the bus assistance

manager the data distribution with MFA, each bus is regarded as a moving RSU

4 网络通信模拟实验

通过在模拟器中实现的城市街区场景中，对目标区域中多目标车辆结点的数据分享的网络通信模拟。主要工作分为两个部分，分别是车辆结点运动行为的模拟实现，以及车辆自组织网络中数据分享的模拟实现。

4.1 城市街区车辆结点运动行为模拟

在车辆自组织网络通信研究过程中，车辆结点的运动模型是数据传输路由的主要研究内容之一。区别于现今被普遍使用的随机点运动模型与随机方向运动模型，基于实际城区车辆的运行轨迹，对城市街区中的车辆结点运动进行了模拟实现。

由于缺乏武汉市城区的数据集，在实验验证环节，本文采用的车辆运动数据集来自文献[8]的相关数据。利用其车辆自组织网络部分的车辆运动轨迹数据，作为本文车辆运动模型的数据来源。实验数据来源为美国华盛顿州西雅图市。如图4所示：在所观测的城市街区中，分布总计750至850辆车辆结点，逐个记录了运动轨迹。利用读入其车辆行驶过程中的坐标更新，将车辆地理位置变化分割成细小的时间分片。当车辆结点运动到同一路点时，在当前时间分片中，车辆间所处的位置被视为相对静止的局部快照。直至下一个时间分片到来，车辆结点通过行驶运动改变自身所在的位置。

4.2 城市街区车辆结点网络通信模拟

已知作为数据分享目标车辆结点的行驶轨迹，试图利用未知地理位置的其余中继帮助车辆结点，设计公交车辅助的数据传输路由。

数据分享过程中，其数据内容长度依然大于车辆结点交会过程中的一次数据推送数据量。同时，数据分享的数据内容具有时效性。数据传输过程中优化目标为，在数据有效期截止前完成数据传递，并最小化网络通信负载开销。并且，最大可能地增加成功完成数据推送的目标车辆结点比例。

Figure 4 City street scene in Seattle图4 西雅图市城市街区场景

在实验过程中，以随机的一个固定结点作为数据传输源，并对目标区域的一部分目标结点分享定长的数据内容。如图4所示，将西雅图市中的网络通信场景依据等面积大小，切分为60个街道区域。当数据内容生成时，依据数据内容长度，可生成K个彼此线性无关的网络编码数据分片。数据的网络编码阶段发生在数据源点，而传输过程中，车辆结点携带着网络编码后的数据分片，并以携带-转发的方式，将数据分片传输至目标区域。随机生成需要推送的街区ID。

将公交车辆结点视为移动的基站结点，公交车辆结点能够直接与目标车辆结点直接相遇，并完成数据的推送(视为直接连接)，或是经过在目标区域中的机会主路由策略，最终经由帮助车辆结点，将数据推送至目标车辆结点(视为间接连接)。在目标结点收集K或K个以上网络分片数据分片后，即可通过解码，获取原数据内容。

4.3 性能评估

针对具体街区生成数据分享通信需求。观测了通过使用公交车辆协助对网络通信中的数据传输开销、目的车辆成功投递率等性能指标的影响。如图5所示，在测试过程中，针对不同长度的数据内容，以及不同的数据内容有效期，分别测试了通过公交车辆协助能够达到的目标车辆结点数据投递成功率。通过对比不同的数据内容有效截止时间T，可以观测到，随着有效时间的缩短，即从40分钟到100分钟之间，数据投递的成功率随着数据有效时间的增加而逐渐增加。这种变化是合理而直观的，即随着数据有效期的增加，无论是公交车辆结点或是普通的中继车辆结点，均有更长的时间完成数据的转发与投递。通过观测数据投递率的变化过程，其上升曲线在60分钟以下的过程中是陡峭的，直至当数据的有效期达到60分钟时，数据投递率的上升趋于平缓。从中可以分析出，在城市街区的网络通信场景中，难以在远距离数据投递情况下确保短时间内的数据分享成功率。

Figure 5 Network communication performance statistics图5 网络通信性能统计

伴随着数据有效截止时间的变化，数据投递率的变化先急后缓，其拐点处大致位于65分钟处，可以作为数据分享中内容有效期的参考基准。同时，能够观测得出，在时间截止期大于70分钟后，截止时间对数据投递的成功率影响逐渐减小，最后，当时间有效期达到100分钟时，各种不同长度的数据内容，都能够达到高于百分之五十的数据投递率。

关注不同的数据长度对城市街区中数据分享的投递成功率影响，可以发现：选取长度为四分片时，中继结点能够较好地完成数据投递的任务，确保始终具有较高的数据投递成功率。随着数据内容长度的增加，数据投递成功率开始明显。当数据长度超过六分片后，在一小时内的数据有效期甚至无法确保百分之三十的投递成功率。进一步分析，通过观测不同K值对应曲线的间隔宽度，能够反映出随着数据内容长度变化而映射出的投递率变化规律。K=6与K=7之间的曲线间隔明显小于其余曲线，说明当数据长度大于六分片时，数据投递成功率很大程度受到数据有效时间的制约，而随着数据长度的变化拐点出现，即当数据长度小于六分片后，大量的中继结点服务能力被释放出来。可以推测在城市街区中，中继车辆的路由服务能力本身存在一定阈值，对于多于一定数据量的携带转发任务，中继车辆的服务能力无法完成路由任务，因而始终保持在较低的数据投递成功率上。

5 结束语

鉴于车辆自组织网络在网络通信过程中高度的动态性，无法确保端到端连接等特性，本文利用公交车辆的行驶规律性，提出了一种基于公交车辆协助的数据分发算法。实验表明在降低网络通信开销的前提下，该方法可以有效地提高城市街区中数据投递的成功率。

[1] Lin Y W, Chen Y S, Lee S L. Routing protocols in vehicular ad hoc networks:A survey and future perspectives[J]. Journal of Information Science and Engineering, 2010,26(3):913-932.

[2] Kohli S, Kaur B, Bindra S. A comparative study of routing protocols in VANET[C]∥Proc of ISCET, 2010:1.

[3] Fall K. A delay-tolerant network architecture for challenged internets[C]∥Proc of the 2003 ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, 2003:27-34.

[4] Chen Y S, Lin Y W, Pan C Y. DIR:Diagonal-intersection-based routing protocol for vehicular ad hoc networks[J]. Telecommunication System, 2011,46(4):299-316.

[5] Skordylis A, Trigoni N. Delay-bounded routing in vehicular ad-hoc networks[C]∥Proc of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2008:341-350.

[6] Matsuda T, Noguchi T, Takine T. Survey of network coding and its applications[J]. IEICE Transactions on Communications, 2011, 94(3):698-717.

[7] Zhang J, Zhang Q. Cooperative network coding-aware routing for multi-rate wireless networks[C]∥Proc of IEEE INFOCOM 2009, 2009:181-189.

[8] Jetcheva J G, Hu Y C, PalChaudhuri S, et al. Design and evaluation of a metropolitan area multitier wireless ad hoc network architecture[C]∥Proc of the 5th IEEE Workshop on Mobile Computing Systems and Applications, 2003:32-43.

YAOHong,born in 1976,PhD,associate professor,CCF member(E200035380M)，his research interest includes computer networks.

DatadistributioninvehicleAd-hocnetworksusingbusassistance

YAO Hong,TENG Chao,CONG Lei,LIANG Qing-zhong,HU Cheng-yu

(School of Computer Science & Technology,China University of Geosciences(Wuhan),Wuhan 430074,China)

Inter-vehicle communications forms vehicle Ad-Hoc networks,which have attracted extensive attention in academia.Due to vehicles’ dynamic nature and the intermittent connection of the signal coverage, the communication behaviors of such networks exhibit the characteristics of the delay tolerant network. Observing the characteristics of buses’ running tracks in urban blocks where there is high density of vehicles, and using the network coding technology and the carry forward method, we propose a data distribution algorithm based on bus assistance to achieve efficient and reliable content sharing.Experiments show that,under the premise of reducing network traffic overhead, the algorithm can effectively improve the delivery success rate of the content sharing data in urban blocks.

vehicle Ad-Hoc networks;network coding;data transmission;bus assistance

1007-130X(2014)11-2114-05

2014-06-11;

：2014-08-20

国家自然科学基金资助项目(61272470,61305087)；中国地质大学(武汉)中央高校基本科研业务费专项资金资助项目(CUG140615,CUG120114)

TP393.09

：A

10.3969/j.issn.1007-130X.2014.11.010