车载自组织网络中停放车辆合作的多媒体内容分发

朱金奇，孙华志，刘念伯，马春梅

(1.天津师范大学计算机与信息工程学院 天津 西青区 300387；2.电子科技大学计算机科学与工程学院 成都 611731)

车载自组织网络的数据分发分为简单、轻量级的文本消息和多媒体内容分发(简称内容分发)两类，后者主要针对可以图像化、多媒体化的交通安全信息、娱乐信息和商业信息。近年随着智能交通中对安全和舒适驾驶的需求逐渐提高，在VANETs中实现车辆之间的内容分发是非常必要的。如移动车辆可以把所经道路上发生的交通事故图片分发给附近车辆，使其提前避开交通问题路段；又如驾驶者可以通过内容分发在车辆行驶过程中下载相遇车辆中自己感兴趣的音视频信息，提高驾驶过程中的舒适度。然而由于车辆高速运动、网络拓扑结构变化快以及车辆的间歇连通性等问题，车辆间可用于数据传递的有效接触时间非常短暂，车辆间较大内容多媒体数据分发较其他自组织网络困难得多，如何在车辆之间进行高效内容分发成为研究挑战。针对这一问题，文献[1-2]采用P2P文件共享和网络编码技术提高内容分发性能，但车辆间内容分发效率仍然有限[3]。此外文献[4-5]提出增加路边基础设施的策略来协助车辆完成内容分发，然而存在如下问题：1)路边基础设施的传输范围有限。2)性能受基础设施节点影响大。当基础设施节点数目较多时车辆与路边节点的相遇概率较高，内容传输的性能就越好。相反则内容分发的性能越差。3)建设和维护基础设施需要额外开销，且多数路边设施并不是免费的。4)固定基础设施节点在灾害发生时容易失效。

基于城市范围内长期存在大量路边及非路边停放车辆这一事实，本文提出城市车载自组织网络中停放车辆合作的内容分发策略(CPVC)，不需要安装任何基础设施节点，而是把地面停放车辆作为天然基础设施和免费的数据中心来辅助VANETs中移动车辆完成内容分发。由于城市区域中停放车辆数目众多，分布广泛且平均停放时间较长[6]，停放车辆相互合作延长了与移动车辆的接触时间，从而使车辆间成功传输数据的概率大大增加。调查和仿真模拟验证，相比于现有的内容分发算法，CPVC具有较高内容分发成功率，尤其是在低交通流量密度及多下载请求的条件下。

1 相关工作

目前车辆间的内容分发研究可以分为以下3类：

1)基于车辆间的相遇：文献[7]认为移动车辆间的无线连接随机且不可靠，为此提出移动车辆间需要合作而进行数据传输。文献[8]提出基于布隆滤波器的分级算法(HBFR)来实现主动数据分发。HBFR基于地理位置把城市分为不同区域，之后内容分发按照区域序号进行。文献[9]提出实时动态的内容分发系统(RTAD)，每辆车辆根据所在道路的车辆密度和拓扑信息自动选择最佳的内容分发机制。

2)基于基础设施节点：文献[4]提出将多媒体数据存放到路边缓存节点的内容分发机制。文献[10]介绍了运行于基础设施接入点组成网络之上的CCDSV系统用于移动车辆之间相互协作发布多媒体内容。文献[11]提出基于类型的内容分发，内容首先发布给距离对此内容感兴趣车辆较近的RSUs节点，这些RSUs节点再周期性地把该内容广播给路过车辆。

3)基于地面停放车辆：该类思想的典型代表为Parkcast算法[6]。

相比Parkcast，CPVC算法的优越性为：

1)支持多用户下载。

2)支持剩余内容下载。CPVC通过建立车辆移动轨迹，结合移动预测选择车辆将要经过的停车簇继续剩余内容下载以提高内容分发的传输成功率。

3)强调了停车簇间的合作，为内容分发提供协同发布。

2 基于停车簇的内容分发

2.1 停车簇管理

把一条城市道路路边和非路边的停放车辆组织成停车簇。一个典型的停车簇如图1所示，其中H1和为该簇的两个簇头，M1～M10为成员节点。停车簇的建立过程如下：首先，位于道路最尽头的两个路边节点被选举为簇头，这样进入或离开该道路的移动车辆必会遇到其中的一个簇头。考虑到簇头随时都有可能离开，规定两个备用簇头如图中和备用簇头为同一停车簇中紧邻簇头的停放车辆，备用簇头始终保持簇头收集信息的副本。当簇头要离开停车簇时，会触发新簇头的选举以及旧簇头把收集的簇信息转发给新簇头。簇成立后簇成员周期性报告自己的位置、ID号、需求内容报告、拥有内容的名字和剩余存储空间到两个簇头，由簇头维护整个簇。

图1 停车簇结构

2.2 内容分发的方式

CPVC中基于停放车辆合作的多媒体内容分发具有3种分发方式：

1)上传：移动车辆驶过停车簇时，它与簇头交互携带的资源名称，若簇头发现移动车辆中有簇成员的需求信息时，移动车辆可以将携带的文件连续地发布给停车簇中的停放车辆。

2)下载：当移动车辆驶过停车簇时，如果停车簇中有该移动车辆感兴趣的资源，则停放车辆可以将存储的相应资源连续发布给行驶的移动车辆。

3)停车簇间交换优化存储资源：停车簇能够发送消息给邻居停车簇请求需要的资源，以优化自己的存储。

3 内容上传

通常移动车辆s与停车簇i的接触时长为：

式中，L为停车簇的长度；r为车辆的通信半径；Hloc为接收内容上传请求簇头的位置；Sloc和Vs分别是移动车辆s的当前位置和速度，可以从GPS获得。在接触时长内移动车辆s可以上传的总数据量满足：

式中，R是MAC层的数据吞吐量。若移动车辆s上传的内容大小C满足：

就能够在移动车辆与停车簇接触时间内完成上传，否则请求的内容不能被完全上传。对于上传的总数据量As，应把As分成若干文件块分发到多个停车簇成员车辆上，之后再经停车簇内部的数据传输把上传的文件块最终传输给需求车辆。

4 内容下载

4.1 源车辆到源停车簇的下载

多媒体内容以文件块的形式存储在停车簇成员中，当源车辆s与停车簇i相遇时，它首先发送包括部分的消息和停车簇的簇头进行信息交互，其中ID为车辆s的ID号，Sloc和分别为车辆s的当前位置和运动速度。Cn表示需求内容的名字，xs为车辆s与簇头交互的时间戳，是该车辆驶入各停车簇时间的历史记录。车辆s从源停车簇下载内容信息的时长分两种情况计算：若存放s请求下载内容的停车簇成员(设它们组成的集合为S)能够直接连通，即S中任意两个地理位置最近节点间的距离小于等于2r，则源车辆能够从停车簇i下载数据的时长为：

式中，L′是S中地理位置最远的两成员的距离。否则源车辆从停车簇i下载数据的时长为：

式中，n是S中满足距离大于2r的相邻两成员节点的对数；Maloc和Mbloc表示距离大于2r的相邻两成员节点的地理位置，可以从簇头获得。

CPVC中簇内停放车辆按照先来先服务原则为移动车辆提供内容下载服务。当初始簇空闲时，源车辆的真正有效内容传输时间等于它能够从源停车簇下载数据的时长。随着簇中下载请求的不断到来，对于新到来的下载请求：1)若它所请求的所有文件块所在的停放车辆与之前到达的请求没有重叠，真正有效内容分发时间也等于源车辆能够从源停车簇下载数据的时长，由式(4)或式(5)获得。2)若请求的文件块所在的簇成员被先到的请求占有，真正有效的内容传输时间等于车辆从源停车簇下载数据的时长减去等待之前下载请求完毕的等待时延。对于簇i的任一成员车辆Mk，假设车辆s下载请求Mk的次序为j，则它等待Mk提供服务的等待传输时延为：

式中，tj为无请求从Mk下载时车辆s的下载请求服务开始时间点；τj-1表示Mk有请求服务时前面所有请求结束服务的时间点。对于成员车辆Mk，tj和满足：

式中，t1是Mk第1个到达请求服务的开始时间，可以根据式(7)获得；Mkloc表示Mk的地理位置；设初始时τ0=0，jχ是第j个到达请求与停车簇i的簇头交互时的时间戳；分别是第1次、第2次直到第j-1次请求Mk内容的大小。把式(7)和式(8)代入式(6)即得分别求得源车辆等待S中每个停放车辆提供服务的等待传输延迟之后，真正有效的内容分发时间为：

式中，K为请求S中成员的数量；要求获得真正有效内容分发时间后带入式(2)即得从源停车簇下载的总数据量。计算真正有效内容分发时间的算法如算法1所示。

算法1 有效内容传输时间计算。

输入：源车辆的ID、速度Vs、当前位置Sloc和与停车簇i的交互时间戳jχ，车辆传输半径r，MAC层吞吐量R，集合S中所有成员的位置和ID号，本次的下载请求次序j，所有之前j-1次请求和停车簇i的交互时间戳

输出：源停车簇为车辆s提供的有效内容传输时间Tsreal。

1)根据S中成员车辆的位置关系，按照式(4)或式(5)计算源车辆从停车簇i下载数据的时长Ts；

4)else

6)根据式(7)计算前面无请求时本次请求的开始时间；

7)按照式(8)计算前面第j-1次请求结束传输的时间点；

9)End for

12)returnTsreal。

4.2 剩余内容的分发

当车辆s未能从源停车簇下载完请求的内容时，如果辅停车簇中没有未完成请求下载内容的存储，CPVD提出剩余下载内容分发给经过源停车簇的辅车辆，再由辅车辆利用移动车辆间的通信将这些内容转发到辅停车簇继续下载。令C为请求下载内容的大小，As为从源停车簇下载内容的数据量，则剩余内容表示为成功分发rs所需辅车辆的数量满足：

设t时间内到达源停车簇的停放车辆数目为N(t)，它服从参数为λ的泊松分布[12]。假设变量wi代表第i个辅车辆与源车辆到达源停车簇的时间间隔，根据泊松过程的性质，WN的概率密度函数为：

辅车辆到达概率如图2所示。第N个辅车辆能在时间(0,t]内到达源停车簇的概率为：

图2 辅车辆到达概率

4.3 辅停车簇的选择

为选择辅停车簇，本文利用车辆运动过程中遇到的停车簇历史记录描述车辆的移动轨迹。采用简化的方法将时间表示以周为单位的时间和以天为单位的时间。车辆移动过程中每遇到一个停车簇，车载设备就记录当前相遇时间和相遇停车簇的编号。为了减少数据量，便于存储和处理，车载设备定期合并相同的行车路线，并用均值和方差表示相遇时间的波动。如某车辆一段时间的移动轨迹记录如表1所示。设某车辆经过停车簇2的时间为8：10，为预测辅停车簇，以停车簇2为源节点建立有向图G(V,E)，如图3所示，其中顶点V为将来可能要经过的停车簇集合，E为路径上任一停车簇到下一跳停车簇边的集合，对于任意的权重wij表示通过停车簇i时下一时刻经过停车簇j的概率。

表1 车辆历史轨迹记录

式中，Ntotal为历史记录中源车辆将要经过的下一跳停车簇的总数量；是此剩余下载内容传输前t时间段内源停车簇及其邻居停车簇需要向外传输的剩余下载内容总量，用于衡量这段时间内停车簇间的网络开销；表示每个辅车辆最多能够从停车簇携带的内容大小；L′是源停车簇及其邻居停车簇的平均长度；v是车辆经过这几个停车簇的平均速度，根据交通流量统计数据获得。

图3 以停车簇2为源停车簇的移动预测

4.4 停车簇间的协作

停车簇协作是内容分发的主要部分，通过邻居停车簇间的协作：1)可以实现邻居簇的协同内容发布；2)各停车簇能够及时了解邻居停车簇的存储资源情况；3)邻居停车簇间能彼此交换热门存储内容，以优化存储。为此，每个停车簇首先发起一个邻居发现过程。如停车簇i的簇头把一个带有簇头地理位置、该簇ID号信息的Nei.REQ消息广播给簇外2跳或3跳内的停车簇。另一个停车簇收到此消息Nei.REQ后把停车簇i设为自己的邻居簇。经过一段时间的邻居发现，每个停车簇均知道自己周围一定范围内的邻居停车簇情况。之后各停车簇周期性的向自己的邻居簇广播ID号和拥有资源的名字。

邻居簇间实现协同内容发布的前提是邻居簇的资源一致性。为保证资源信息的一致性，首先簇内需要周期性维护更新存储资源，如定时删除不被车辆请求或较少有车辆请求的过时热门资源，通过定时维护更新，停车簇能够优化和管理自己的存储。其次，簇间周期性的对外内容广播通过设置一个超时限来保证广播内容的新鲜性。令该超时限等于簇内定时维护更新的周期加上邻居簇间的最大传输延迟。邻居簇间的移动车辆收到簇的内容广播消息时根据超时限判断资源的可用性，若超时限减为零，则丢弃该广播消息。

5 仿真实验与性能分析

5.1 调查

对中国成都的城市区域进行了为期6周的调查，如图4所示，该区域大小1 600 m×1 400 m，包含10个十字路口(图中编号为0～9)和14个长度总和为7 860 m的双行道，该区域拥有大量路边及非路边停车簇。对区域内所有路段于每周二、周四、周六的停车情况进行了调查，对所有沿路5 m内停放的车辆按16：00、18：00和22：00分时段进行统计的调查结果如表2所示。调查统计发现，在一天不同时段各路段的停车数量相对稳定，不同时间段的行驶车辆密度在300 辆/h和2 200 辆/h之间变化，区域内行驶车辆的数目在60～400之间。

图4 仿真采用的街道拓扑

表2 停车调查结果

5.2 辅停车簇预测分析

为分析辅停车簇选择的准确性，根据从家到学校的3条行驶路线进行实测。这3条行驶路线中路线①经过3个不同停车簇，路线②经过5个停车簇，路线③经过7个停车簇。令车速位于40～80 km/h之间，车辆行驶时同时打开手机GPS记录经过道路各簇的GPS坐标和相应时间。

实测中3条路线总共行驶30次，其中路线①10次，路线②12次和路线③8次。把20次行驶作为样本，另外10次行驶作为测试数据，得准确率随源停车簇及邻居停车簇向外传输的剩余下载内容总量变化如图5所示。可以看出辅停车簇预测准确率随着网络中剩余下载内容总量的增大而减小，这是因为当剩余下载内容总量较小时，选择的辅停车簇数量较多，能够保证剩余下载内容传输到辅停车簇及剩余下载内容不丢失。反之则选择的辅停车簇数量少，剩余内容易丢失。

图5 辅停车簇预测准确率变化

5.3 仿真环境

用NS-2.33实现仿真，使用开源软件VanetMobiSim-1.1[13]生成真实城市车辆移动轨迹。默认情况下在仿真地图上设置车辆的数量为200辆，车辆传输范围设为250 m，初始时车辆随机选择一个移动方向，且车辆的平均移动速度在40～80 km/h。底层的MAC协议采用2M的802.11。仿真开始对于分布在路边停车位的停放车辆，它们严格按照表2中的密度随机分布于各道路。每辆车的平均停放时间约为41.40 min，标准差为27.17，停车簇簇头广播消息周期为5 s。仿真过程中设置所有移动车辆中10%的车辆收到停车簇簇头广播消息后发送内容下载请求。假设停车簇在仿真之前已建立，并以60 s为周期进行维护。设置Nthred的时间段t=20 min，下载内容的大小为10 MB。把CPVC与Parkcast、CodeTorrentlike[14]及PC-based[15]进行分析对比。

5.4 交通流量密度对性能的影响

图6a显示随着车辆密度增大CodeTorrent-like传输成功率显著提高，这是因为CodeTorrent-like利用邻居车辆的相遇完成内容分发，而移动车辆密度增大可以使传输范围内遇到邻居车辆的概率增大。当车辆密度较大时Parkcast的传输成功率反而降低，原因是Parkcast仅依靠源车辆与源停车簇的接触完成内容分发。随着源停车簇收到内容下载请求数量增大，当停车簇正为某下载请求服务时会拒绝其他车辆的下载请求，导致Parkcast传输成功率降低。车辆密度变化过程中，CPVC的传输成功率始终高于其他3个协议，尤其是当车辆密度稀疏时，CPVC仍能保持较高的传输成功率，主要因为CPVC依靠城市范围内广泛且稳定分布的地面停放车辆合作进行内容分发。即使请求者数量较多，CPVC也不会拒绝下载请求。

图6 交通流量密度对性能的影响

图6b中车辆数量较多时会有更多的车辆协助内容分发，导致CodeTorrent-like平均下载延迟下降。Parkcast只在源停车与源停车簇接触时完成内容分发，因此车辆密度变化对Parkcast的传输延迟影响不大。CPVC和PC-based的传输延迟在车辆密度增加时增大，这是由于请求内容分发的车辆数量增多导致更多的下载请求只能在辅停车簇完成。图6c中由于CPVC只有在辅停车簇中没有存储剩余下载内容时才通过辅车辆往下递交剩余下载，一定程度上比PC-based降低了网络开销。

5.5 请求下载的车辆比例对性能的影响

图7 请求下载车辆比例的影响

图7a中各协议的传输成功率随请求下载内容车辆比例的增大而降低。因为对于CodeTorrent-like，当请求下载的车辆数量增多时，在有限的车辆相遇时间内未能完成下载的数量增多，这也同时加大了无线传输冲突的可能性。由于Parkcast在有限接触时间内无法完成请求下载的数量增多，因此Parkcast的传输成功率随着请求下载车辆的增多而下降。CPVC和PC-based在请求下载车辆比例增多时把未能在源停车簇完成的请求转移到辅停车簇，因此随着请求下载车辆的增多传输成功率变化不大。图7b中4种协议的平均传输延迟均随着请求下载车辆比例增大而提升，由于CPVC选择即将要通过的停车簇作为辅停车簇，且在辅停车簇中有剩余下载存储时无需辅车辆传输，因此相比于PC-based降低了内容分发的延迟。如图7c所示，随着请求下载车辆比例增加，CodeTorrent-like的传输开销增长最大，因为需要频繁的进行数据移交。由于CPVC需要进行源停车簇到辅停车簇的数据移交，所以传输开销的增长较PC-based和Parkcast大。

6 结束语

针对城市范围内天然存在、广泛分布且结构稳定的地面停车资源，本文提出停放车辆合作的内容分发思想，利用邻居停车簇间的协作发布和车辆与源停车簇及辅停车簇的接触提供高效的本地数据分发。通过现实的停车调查和大量仿真实验结果表明CPVC能够以相对较低的传输延迟和网络开销获得较高的传输成功率。