一种基于分簇的车联网对向协助下载方法*

赵征宇，张建军，3，刘征宇

(1.合肥工业大学 计算机与信息学院，安徽 合肥230009;2.合肥工业大学 机械与汽车工程学院，安徽 合肥230009;3.安全关键工业测控技术教育部工程研究中心，安徽 合肥230009)

0 引 言

车联网(vehicular Ad Hoc networks，VANET)环境下高速公路上的车辆可以通过路边AP 接入点接入互联网，由于在高速公路环境下，路边的AP 站点非常少，分布稀疏，一般设立在加油站或者服务区。然而汽车的行驶速度快，AP 的通信范围相对较小，导致汽车在AP 通信区域内的时间较短，而在相邻两个AP 之间，AP 通信范围以外的盲区(dead zone，DZ)行驶时间较长。当汽车节点在一个AP 区域不能完成下载任务时，只能等待较长的时间，车辆进入下一个AP 后，才能接着下载，因此，在高速公路上用户使用网络的延迟将非常的大。

为了解决等待延迟时间较长问题，国内外研究学者们提出了许多协助下载方法。文献［1］提出的SPAWN 协议采用结合位置感知的流言传播机制，其主要适合P2P 场景下车辆都下载同一资源。文献［2］提出了高速公路场景下的协助下载方法，同向协助下载时车辆的利用率较低，对向协助下载时没有提出确切的数据携带算法。文献［3］提出了一种高速公路下基于安全的协助下载方法，该方法主要考虑车辆从AP 获取资源的安全性。文献［4］提出了基于动态时槽协助下载方法，该方法采用单个车辆携带数据一次传输的数据较少。

为了有效利用协助车辆，本文提出了一种分簇算法用于判定车辆的分布情况，然后利用分簇的车辆为用户协助下载数据。

1 基于动态相邻节点间距的VANET 分簇算法

1.1 基于相邻节点间距的VANET 分簇算法的问题

文献［5］提出了一种基于相邻间距的分簇算法。该分簇算法规定如果节点v 的前方距离d 内没有节点，则规定v为头节点，并把头节点标志位HeadFlag 设为true。如果节点v 的后方距离d 范围内没有节点，则规定v 为尾节点，并把尾节点的标志位TailFlag 设为true。

每辆车辆周期性地广播信标信息，当节点v 收到节点u 的信标信息，节点v 将节点u 加入到自己的邻居列表并计算节点之间的距离|d(v，u)|，如果|d(v，u)|＜d，则表明二者在同一个簇内，更改相应的标志位。如果|d(v，u)|＞d，则表明二者已不在同一个簇，根据v 和u 的前后关系更改相应的标志位。

每个节点v 检查自己的标志位HeadFlag 和TailFlag，如果HeadFlag 为true，则v 为头节点;如果TailFlag 为true，则v 为尾节点。一对头尾节点确定了一个基于相邻节点间距d 的分簇。

由于车辆的一跳通信距离远远大于公路的路宽，故VANET 可看成线性网络结构。基于相邻节点间距的分簇算法很好地利用了此网络特性，但是此算法没有考虑到车流量对分簇算法的影响。在高速公路环境下，VANET 的拓扑结构和车辆的密度都是具有很高的变化率。如果还是采用固定的间距d 来分簇，当车辆密度变得很高时，同一个簇所包含的车辆也会变得很多。如果一个簇中的车辆过多，那么，簇中车辆竞争信道的几率将会大大提高，网络延时将会变得严重，从而影响整个网络的性能;当车辆密度变得很低时，同一个簇中的车辆数目将会降低，从而导致总的分簇过多，产生更多的簇头或孤立车辆(也作为一个特别的簇头)。簇头的增多将会导致簇头所包含的路由表项增加，增加了网络的负担。为此，本文提出了一种基于动态相邻节点间距的分簇算法，根据车辆的密度动态地调整间距d，使簇保持一个合适的大小。

1.2 基于动态相邻节点间距的VANET 分簇算法

车辆在道路上行驶，必须保持一个安全距离。所以，相邻节点距离d 的最小值dmin必须不小于车辆行驶的安全距离DL。为了让车辆节点能够根据一跳范围内的邻居节点位置信息就能判断出自己是否为头尾节点，故相邻节点距离d 的最大值dmax必须小于节点的通信半径R。

当车流量非常大时相邻节点距离随着车辆密度的增大而线性地减小，d 的实际值可按下式计算

其中，K 为车辆密度，dN和dc分别为新的邻居相邻间距和当前相邻距离，由文献［6］可知当K∈［0.8，1.0］时车流量是属于大的范畴，式(1)也是在K∈［0.8，1.0］内有效。当车流量不大，即K∈［0，0.8］时，随着车流量的减小相邻节点距离指数级增大

由于相邻节点距离在K=0.8 时是连续的，故将K=0.8分别带入式(1)和式(3)可求得

车辆首先根据当前的车辆密度计算出当前合适的相邻间距d，然后运用得到的d 采用相邻节点间距的VANET 分簇算法找到一对头尾节点形成一个簇，每个节点根据自己的邻居节点列表信息运用文献［7］中的簇头选择算法选择簇头。

车辆分簇完成以后，便进入簇的维护阶段。当单个头节点或尾节点离开簇或者有单个新成员加入簇时，不会对簇结构产生影响，只需要根据簇的形成过程更新相应的头节点或尾节点，并更新簇成员的邻居列表信息和簇头的成员列表信息，而不需要更新簇头和相邻间距d。

当两簇车辆合并或者一个簇分裂时，簇的大小和结构发生较大的改变，根据簇的形成过程，一对新的头节点和尾节点维护了一个新的簇，簇成员更新自己的邻居列表，根据邻居列表信息运用文献［7］更新新的簇头，簇头根据当前的车流量，重新计算出当前的相邻间距d，并广播给簇成员。簇成员收到广播后，更新自己的相邻间距d。

2 基于分簇的VANET 对向协助下载

2.1 协助车辆选择

汽车在高速路上行驶如图1 所示，可从路边单元APk下载数据，由于高速路上的AP 数量有限，不能覆盖全路段，导致车辆与AP 之间间断性连接。当车辆进入AP 通信范围后，注册自己车辆的idn，簇头车辆pidn，速度vn和进入此AP 的时间tn。AP 维护一个其通信范围内的所有汽车的速度和注册时间列表List={(id0，pid0，v0，t0)…(idn，pidn，vn，tn)}。当车辆在一个AP 区域内提出下载请求，而在AP区域内不能完成全部下载任务时，AP 通知沿着车辆行驶的方向的下一个AP，有车辆提出协助下载请求。

图1 高速公路场景Fig 1 Highway scenario

根据高速公路的特性，通常情况下，相邻AP 之间的车辆在对向行驶的过程中都会相遇，所以，本文考虑用对向行驶的一簇车辆作为协助车辆为单个目的车辆提供协助服务。当下一个AP 收到协助下载请求时，计算每一簇车辆与用户相遇的时间和结束时间，按照与用户相遇的时间顺序选取合适的簇，放入集合M={(pid0，v0，t0，B0，E0，T0)…(pidn，vn，tn，Bn，En，Tn)}，其中，Bn为相遇的时间，En为传输结束的时间，Tn为选车的时间。Bn和En可由式(5)和式(6)取得

其中，D 为盲区的长度，L 为AP 的通信范围，n 为簇中的车辆数，vs和ts分别为目的车辆的速度和向AP 注册的时间，vn和tn分别为簇头的速度和簇头向AP 注册的时间由于分簇车辆的簇比较稳定，而簇头车辆的速度变化率更小，本文选取簇头车辆的速度作为整个簇的速度。

为了防止选取的簇与簇之间在为目的车辆传输数据时重叠，因此，下一个协助簇车辆的传输开始时间必须晚于当前协助簇车辆的传输结束时间，假设当前的簇为m0=(pid0，v0，t0，B0，E0，T0)，则下一个簇mx=(pidx，vx，tx，Bx，Ex，Tx)必须要使选取的车辆满足式(7)

为了保证协助下载全在盲区进行，防止车辆在进入AP区域后仍然有车辆为其提供下载任务而导致与从AP 的下载冲突，则被选中的最后一个簇必须满足式(8)

根据簇的大小，AP 为不同的备选协助簇分配不同大小的数据，为了保证每簇车携带的数据量能够在车辆相遇时传完，则每簇车携带的数据量必须满足下式

2.2 协助车辆与目的车辆通信

当分簇的协助车辆进入盲区后，在与目的车辆相遇时，把携带的数据传输给目的车辆。其传输过程如下:

1)簇成员定时发送信标信息，为了能使目的车辆在和簇的通信范围内都能收到信标信息，簇成员同时发送相同的信标信息。信标内容包括簇头的pid，簇头车辆的速度v，车辆的位置loc，以及携带数据的目的车辆的id。

2)当目的车辆收到包含自身id 的信标信息时，表明分簇的协助车辆已经在通信范围内，此时目的车辆一跳范围内广播一个连接请求信息，信息内容包括自身的车辆id，速度v，位置loc。

3)当簇中车辆收到连接请求信息且包含的车辆id 与簇所携带数据的目的车辆id 相同时，簇中收到连接请求广播的每个车辆分别计算各自与目的车辆的的通信带宽wi和绝对距离Disi，如下式

其中，Data 为步骤(1)中簇成员广播的信标长度和步骤(2)中目的车辆广播的连接请求信息长度的和，ti为簇成员收到连接请求的时间，t 为簇成员发送信标的时间，loci为簇成员的位置，locs为目的车辆的位置。

簇头节点选取wi值最大的节点作为网关节点，簇中携带的数据通过网关节点传递给目的车辆，当簇中有两个wi值相同，并且都是最大值时，选取Disi值较小的车辆作为网关节点。如果wi值和Disi值均相等时，考虑到车辆的相对运动，故选取行驶方向上的后车和靠近尾节点的车辆作为网关节点。

3 网络仿真

本节通过NS2 仿真将本文提出的基于分簇的VANET对向协助下载方法和文献［4］中提出的对向行驶车辆协助下载(ODCD)方法以及不使用协助下载方法进行性能比较。假设高速公路上AP 站点的通信范围为800 m，两个相邻AP 间距8 km，和高速公路上一般AP 均设置在加油站或服务区的实际情况相符合。车辆的通信半径为250 m，AP区域车辆的下载速率设为150 kB/s，对向车辆协助下载速率设为50 kB/s，车速在90 ～150 km/h 之间随机产生，在车速变化上，假定车速变化的概率为p，变化的范围为90 ～150 km/h 之间，并且符合对数正态分布，假定用户车速为90 km/h。

图2 比较了在车速保持不变，车流在高速公路上服从泊松分布时，不采用协助下载方法、对向协助下载方法和分簇的对向协助下载方法的吞吐量情况。由图2 可知，在0 ～30 s 内车辆在AP 的通信范围内，车辆以150 kB/s 的速率下载数据;30 s 以后车辆离开AP 的通信范围，在不采用协助下载的情况下，车辆需要等待300 s 左右，等车辆到达下一个AP 区域才可以下载数据，延迟较大。在采用对向协助下载方法或者分簇协助下载方法情况下，车辆经过100 s 左后就可以接收到协助车辆携带的数据。采用对向协助下载方法，在盲区用户可从协助车辆上下载到7 MB 的数据，而采用分簇的协助下载方法，可以下载10 MB 的数据，该方法的吞吐量高于对向协助下载方法。显然，采用分簇的协助下载方式提高了车辆下载的吞吐量，减少了延迟。

图2 三种方法吞吐量比较Fig 2 Throughput comparison of three methods

为了比较分簇协助下载方法在下载实际文件时的延迟(delay，D)和平均带宽(average bandwidth，AB)，分别使用三种方法下载长度为8.1，27，55.3 MB 的文件。由表1 可知，在不采用协助下载的情况下，随着文件长度的增加平均带宽逐渐减少，并且平均带宽水平非常低。而使用对向协助下载方法和分簇协助下载方法时，随着文件长度的增加，平均带宽逐渐增大。当下载大于27 MB 文件时，采用分簇协助下载方法的平均带宽在48.3 kB/s 以上，明显高于对向协助下载方法的39.5 kB/s 和不采用协助下载方法的15.2 kB/s，这是由于采用分簇协助下载的方法利用了比对向协助下载方法更多的车辆，因此，采用分簇的对向协助下载方法性能优于对向协助下载方法。

表1 下载不同大小文件的延迟和平均带宽Tab 1 Delay and average bandwidth of downloading file of different size

4 结 论

为了充分利用车辆在行驶过程中的分块特性，本文提出了一种基于分簇的协助下载方法，利用该方法可以使更多的车辆参与协助下载，有效地提高了用户下载数据的吞吐量，降低了用户下载数据的延迟。对提出的方法进行仿真实验，验证了其有效性。由于环境设定在高速公路上，速度的变化率相对较低，因此，忽略了车速变化对方法的影响。另外，该方法只适合一簇车辆为单个目的车辆协助下载，这是下一步工作需要考虑的问题。

［1］ Nandan A，Das S，Pau G，et al.Cooperative downloading in vehicular Ad－Hoc wireless network［C］∥International Conference on Wireless on Demand Network Systems and Services，St Moritz，Switzerland，2005:32－41.

［2］ Trulhils－Cruces O，Morillo－Pozo J，Barcelo J M，et al.A cooperative vehicular network framework［C］∥IEEE ICC’09，Dresden，Germany，2009.

［3］ Hao Yong，Tang Jin，Cheng Yu.Secure cooperative data downloading in vehicular Ad Hoc network［J］.IEEE Journal on Selected Areas in Communications/Supplement，2013，31:523－537.

［4］ 刘建航，孙江明，毕经平，等.基于动态时槽的车联网协助下载方法研究［J］.计算机学报，2011，34(8):1378－1386.

［5］ 陈 振，韩江洪，刘征宇.基于VANET 分簇的车辆碰撞警告信息传输［J］.电子测量与仪器学报，2013，27(5):396－402.

［6］ Ameneh Daeinabi，Akbar Ghaffar Pour Rahbar，Ahmad Khademzadeh.VWCA:An efficient clustering algorithm in vehicular Ad Hoc networks［J］.Journal of Network and Computer Applications，2011(34):207－222.

［7］ Basagni S.Distributed clustering for Ad Hoc networks［C］∥1999 International Symposium on Parallel Architectures，Algorithms and Networks，ISPAN’99，1999:310－315.