车联网协助下载传输规划方法

李春雷，刘建航

（1.中国石化股份有限公司胜利油田分公司地质科学研究院，山东 东营257000；2.中国石油大学 计算机与通信工程学院，山东 青岛266555）

0 引 言

由于路边接入点 （AP）通信范围有限，车载用户使用Wi－Fi方式接入互联网会导致间歇性连接。虽然Jorg Ott等提出了Disconnection－tolerant的方法在传输层保持连接，但仍然没有从根本上减少延迟，提高用户下载的数据量［1］。

为解决上述问题，Nanda等［2］第一次将协助下载方法引入车联网。这种方法的基本思想是用户进入AP通信区后发送下载请求，当用户离开AP通信区，AP根据与用户车相遇时间，在其通信区间内选择一组车辆携带用户所需数据。当协助车在盲区内与目标车相遇时，将携带的数据传送给目标车。显然，这种方法可以延伸AP的通信区域，以便用户收到更多的数据。

对于多用户的应用来说，一个关键的问题是当多辆协助车和目标车的通信区域重合时，谁将获取信道？显然，对于拓扑结构变化频繁的车联网来说，信道争用方法如CDMA／CA协议并不适合作为通信协议，这是由于协助下载中协助车和目标车通信时间较短，信道争用会占用通信时间，减少吞吐量。

基于上述原因，本文提出了一种名为TS－Coop的数据传输规划方法。TS－Coop建立了一个k级约束的路由规划算法用于定义数据量的路由；在此基础上，定义了一个基于动态规划算法的传输规划方法。通过分析测试车辆在2011年5月至2012年7月间G15运行期间获取的数据集，验证了使用本文提出的方法可以有效提高系统吞吐量，减少由于频繁碰撞所致的信道争用带来的影响。

相似的研究中［3］提出利用P2P的方式在车联网中寻找其它资源进行协助下载；文献 ［4］研究了高速公路环境下同向协助下载方法；A.Bal Subramanian等［5］提出了一种支持车内用户使用交互式应用程序的方法，其主要工作是利用AP点分布的差异来减少冲突；M.Fiore等［6］提出了针对城市的车联网协助下载方法，该方法通过将车速预测及其行驶路线和目标车相遇时间作为部署AP的依据来评估不同协助车选择算法及数据分块方案；R.Mahajan等［7］的研究成果是针对车联网特点提出了一种测量 Wi－Fi连通性的方法，从而决定节点连接时间；Y.Zhang等［8］车联网用户利用路边基础设施实现一种上传和下载方案；DTcoop［9］通过协助下载的方式减少高速情况下丢包率，解决的是单向的信息广播分发问题；DSRelay［10］提出了动态规划DA下载区域算法。

1 传输规划方法

为了满足高速车联网数据传输需求，满足移动节点数据传输的特点，首先建立高速车联网传输系统模型，并针对在该模型基础上建立k－约束路由树，根据树中的每个节点传输的数据量为其规划传输时间片，在此基础上提出相应的传输规划算法。在道路上行驶的车辆分为两类，一类是与目标车同向行驶的，另一类是与目标车对向行驶的。在两个AP之间 （AP一般被设置在路口或者加油站），对向行驶的车辆一定会相遇，而同向行驶的车辆由于车速的不同，会发生超越目标车或是被目标车超越。如果对向行驶的车辆相遇过程中将数据下载给目标车的过程称为ODCD （opposite direction cooperative downloading），而 在同向行驶过程中赶超或被赶超时的协助下载过程成为SDCD （same direction cooperative downloading）［10］。高速公路环境下对向行驶的车辆一定会发生ODCD过程，而同向行驶的SDCD过程发生的条件仅当协助车辆赶超目标车或者被赶超时才会发生。

1.1 系统模型

为了清晰的描述该方法，我们首先假定在t时刻车辆i的位置为

随着目标车和协助车辆不断移动，车辆i的行驶轨迹为

两辆车i和j进行通信的条件是其相对距离小于通信半径R.如果能够获取车辆的行驶轨迹，我们可以得到一个n个时间片的拓扑序列用于建立移动通信拓扑 （MCT）。MCT可以被定义为

式中：V——所有参与通信车辆的集合，L——所有通信链路的集合，｛i，j｜i，j∈V｝作为一个通信链路，即两辆车i和j的通信距离小于通信半径R.T是集合L中时间槽的集合。

在数据转发过程中，车辆的传输时间决定了是否会发生碰撞，用户是否会收到数据。因此，如果我们对每辆车的传输时间都进行规划，那么就可以避免传输冲突。对于任一车辆i，我们用Ti作为该辆车传输时间的集合，W作为车辆集合与传输时间的映射，C为所有用户的集合，则有

因此，每辆车的积累函数为

1.2 建立k－约束路由树

对于树结构来说，传输冲突分为两类。一类是树内冲突，即用户在同一时刻只能获取一辆协助车发过来的数据，如果多辆协助车同时发送数据，就会发生传输冲突。这意味着子节点不能同时给父节点传输数据。相反，父节点向子节点发送数据时则不会产生传输冲突。另一类是树间冲突，即一个节点在与其父节点或者子节点发送和接收数据的过程与其它分支的发送过程产生冲突。

为了避免上述两种冲突，本文提出将每个树内节点加上一个传输约束。每个节点i在式 （3）中的最大连接数小于信道数量。这就保证了节点在发送数据时可以不与其父节点和邻居节点的传输发生冲突。

我们使用αi作为节点i在移动通信拓扑中的约束级，使用βi作为节点i在树结构中的约束级，则

当节点被规划同时传输数据时，他们可以选择不同的信道传输数据。信道选择算法将在1.3中阐述。显然链路数是建立k－约束树的基本条件。

基于上述分析，本文提出式 （7）的建立约束树规则。其中式 （7）中的每个节点必须满足式 （6）的约束条件

建立约束树的算法要保证至少有min｛αi－k，0｝个邻居节点能够作为子节点。这就保证了每个节点的链路数小于k。按照式 （4）的条件，一个节点可以选择父节点，也就是集合中拥有最大值k的节点将被选择作为父节点。

具体算法如图1所示。

图1 建立k级约束树算法

首先设定节点集合和链路结合都为空，数据传输的最终用户作为树的根节点加入到节点的结合中。另外，对于每个新加入的节点i，比较其信道数量k和约束αi。如果k＞αi，任意选择k－αi个邻居节点作为其子节点。经过排序后将选中的k－αi个节点加入到临时集合V’中。对于其它未加入的节点，比较每个节点和已加入节点的链路数量，将链路数量小的节点替换出集合。循环该过程直到所有的节点都被计算。

1.3 传输规划

建立好k级约束的路由树，本节介绍在此结构上规划各个节点的传输时间。我们假定树结构为Т，节点i将要在时刻Т0发生数据di。则用户j能获取的数据最大值为式 （8）

当子节点和父节点同时需要发送数据时，子节点的发送时间片比父节点短，这样设置保证子节点可在父节点发送数据之前完成数据发送，因此传输规划必须满足式 （9）

另外一个约束条件是同一个父节点下的子节点不能同时发送数据，即满足式 （10）

基于上述分析，本文提出了基于动态规划算法的传输规划方法，如图2所示。

图2 TS－Coop算法

首先，根据树结构中子节点与父节点的关系，将节点分为不同的层，叶子节点为第0层，父节点的层数为子节点中最大层数值加1。然后，计算当每个子节点与父节点之间的链路是可用的前提下的最大传输数量。用D ［i，T］s代表节点i在T时刻发送数据的最大值。假定节点i的父节点为pi，节点i的子节点集为Ci＝ ｛c0，c1，c2…ck｝。则传输时间相对应的传输集合为T＝ ｛Tc0，Tc1，Tc2…，Tck｝。

2 实验验证

本文通过仿真实验对该方法的性能进行评估。车辆行驶数据一部分采用中国科学院电动汽车研发中心 （上海）在2010年9月～12月在高速公路G15上海段的测试数据，另一部分采用数据生成器自动生成的。实验场景设定AP通信范围d＝800m假设车辆间通信半径r＝250m。本实验将车辆间通信速率设为3.2Mbps［1］，AP下载速率为2.4 Mbps。用户车速在90km／h～120km／h随机产生，并且符合对数正态分布。

首先，我们使用两种方法TS－Coop与DSRelay［10］比较节点数量对传输效率的影响。如图3所示，随着节点数量增加，DSRelay方法的效率不断提高直到节点数量达到35，这是由于参与转发的节点的增加带来了信道利用率的提高。而当盲区资源达到饱和后，传输效率开始下降。节点数量从40增加到50个时，效率值下降到50%。

图3 两种方法中节点数量对效率的影响

相比较而言，由于对传输进行了规划，参与传输的节点数量越少，TS－Coop的传输效率越高，随着节点的增加，盲区中时空资源利用率提高的同时，碰撞概率不断提高，这导致使用传输效率不断下降。然而，虽然TS－Coop的效率一直处于一个下降的趋势，但是其效率值始终保持在70%以上，明显优于DSRelay方法。

相应的，我们使用两种方法测试了设置时延长度对效率的影响。图4展示了测试结果，使用TS－Coop和DSRelay方法，效率随时延长度的增加而不断提高，当时延长度小于3ms时，DSRelay的效率要高于TS－Coop。相比而言，当时延长度大于4ms时，TS－Coop的增量要明显高于DSRelay，这是由于建立k级约束路由树所占用的时间被更低的碰撞率抵消的结果。延时达到9ms时，使用TS－Coop方法可将效率值提高到80%，而DSRelay的效率不足60%。

为了验证使用TS－Coop方法，用户车速对下载总量的影响，我们分别测试了用户车速分别在90km／h、120km／h和150km／h时的下载吞吐量。

从图5显示的结果看，车速越快，用户下载吞吐量越高。用户车速快意味着用户会在更短的时间内与协助车相遇，因此可以在ODCD过程中获取更多的数据；然而，车辆运行速度快也意味着SDCD过程中更少的车辆能够赶超用户车辆，因此该过程获取的数据会减少。协助车数量决定建立约束树的成本与碰撞的发生率，因此用户车速越慢获取的数据量越多。

图4 两种方法中时延长度对效率的影响

图5 使用TS－Coop方法不同车速获取的数据量

3 结束语

为了有效利用高速公路环境下AP通信盲区的时空资源，减少传输冲突，在保证系统公平性的前提下尽可能提高用户下载总量。本文针对车联网协助下载方式提出了一种名为TS－Coop的传输规划方法，该方法根据链路数量建立k级约束树；然后根据每个节点的传输时间和任务为其规划传输数据，从而避免传输冲突。仿真实验结果表明了该方法可以有效地减少用户获取数据的延时，有效地提高了系统的吞吐量。该方法的提出将为解决车联网协助下载相关研究提供关键技术和理论支持。

［1］Ott J，Kutscher D.A disconnection－tolerant transport for drive－thru internet environments ［C］／／Proc of IEEE INFOCOM，2005.

［2］Trullols－Cruces O，Fiore M，Barcelo－Ordinas J.Cooperative download in vehicular environments ［J］.IEEE Transactions on Mobile Computing，2012，11 （4）：663－678.

［3］Liu Che－Liang，Wang Chih－Yu，Wei Hung－Yu.Mobile chord：Enhancing P2Papplication performance over vehicular Ad Hoc network ［C］／／Proceedings of IEEE GLOBECOM，2008：241－247.

［4］LIU Jianhang，BI Jingping，XU Peng.A method of cooperative downloading improving AP work efficiency ［J］.Science Technology and Engeering，2012，10 （26）：267－270 （in Chinese）.［刘建航，毕经平，徐鹏.高速公路环境下车联网同向协助下载方法研究 ［J］.科学技术与工程，2012，10 （26）：267－270.］

［5］Balasubramanian A，Mahajan R，Venkataramani A，et al.Interactive WiFi connectivity for moving vehicles ［C］／／Proceedings of SIGCOMM，2008：427－438.

［6］Fiore M，Barcelo－Ordinas JM.Cooperative download in urban vehicular networks ［C］／／Proceedings of IEEE MASS，2009：20－29.

［7］Mahajan R，Zahorjan J，Zill B.Understanding WiFi－based connectivity from moving vehicles ［C］／／Proceedings of IMC，2007.

［8］Zhang Y，Zhao J，Cao G.On scheduling vehicle－roadside data access ［C］／／Proceedings of VANET，2007：10－19.

［9］Liang Hao，Zhuang Weihua.DTcoop：Delay tolerant cooperative communications in DTN／WLAN integrated networks［C］／／Proceedings of Vehicular Technology Conference Fall，2010.

［10］LIU Jianhang，SUN Jiangming，BI Jingping，et al.VANET cooperative downloading approach study based on dynamic slot［J］.Tansaction on Computer，2011，34 （8）：1334－1344（in Chinese）.［刘建航，孙江明，毕经平，等.基于动态时槽的车联网协助下载方法研究 ［J］.计算机学报，2011，34（8）：1334－1344.］