一种基于相邻车辆距离的VANET分簇维护方法

技术领域

本发明涉及，具体为一种基于相邻车辆距离的VANET分簇维护方法。

背景技术

车辆自组网络（Vehicular Ad-hoc NETwork）是一种特殊的移动自 组网络（Mobile Ad-hoc NETworks），它所处的运行环境稳定性差 、拓扑结构变化剧烈，无线信道又容易受街道建筑、车速、道路状况 的等因素的影响，会产生广播风暴或路由不稳定等问题。这些都直接 增加了VANET的路由协议设计的难度。而分簇作为解决车辆自组网络这 些问题的一个手段，具有很大的实际应用价值。

发明内容

本发明目的是提供一种基于相邻车辆距离的VANET分簇维护方法，以解 决车辆移动自组网中的路由成本高、广播风暴的问题。

为了达到上述目的，本发明所采用的技术方案为：

一种基于相邻车辆距离的VANET分簇维护方法，其特征在于：将整个V ANET网络抽象成为一个连通图，以构成VANET网络的车辆作为连通图中 各个节点，并以相邻车辆的安全距离作为依据来分簇，把彼此相邻且 相邻距离小于安全距离的车辆分成一簇；

在VANET网络中其中任意两个节点之间都有连接的边，任意两个节点之 间是可到达的，对给定节点的网络采用相邻节点安全距离作为依据进 行分簇，每个簇都是属于给定的网络节点集，分簇的数量不超过节点 的总数量；在已经划定的簇结构中，任意两个属于同一个簇的节点之 间的距离都是小于安全距离的；所有簇的合集是整个VANET网络的全部 节点，在簇与簇之间没有相同的节点，即任意两个簇间没有交集。

所述的一种基于相邻车辆距离的VANET分簇维护方法，其特征在于：只 考虑高速公路上一个方向的车辆，在安全距离远大于高速公路宽度的 条件下，在VANET线状网络的结构中，头结点和尾节点定义如下：将在 其前距离d内没有相临节点的节点作为头结点，将在其后距离d内没有 相临节点的节点作为尾结点；每个车辆节点广播自己的ID、位置、速 度信息，将回复信息的节点加入到自己的相邻节点列表中，并将两车 辆节点之间位置信息相减的绝对值作为两节点之间的距离；

当前节点在自己的相临节点列表中没有找到在其前距离d内的相临节点 ，在将该节点作为头节点的同时向自己的相临节点广播自己作为头节 点的信息；此时，若相临节点的列表包含头节点，则删除相临节点列 表的头节点之前的节点；各节点根据自己的相临节点信息，采用上述 方式进行头维护；

当前节点在自己的相临节点列表中没有找到在其后距离d的相临节点， 在将该节点作为尾节点的同时向自己的相临节点广播自己作为尾节点 的信息；此时，若相临节点的列表包含尾节点，则删除相临节点列表 的尾节点之后的节点；各节点根据自己的相临节点信息，采用上述方 式进行尾维护。

所述的一种基于相邻车辆距离的VANET分簇维护方法，其特征在于：当 某一节点变成头节点，但非尾节点，发送成为头节点的信息；成为尾 节点而非头节点时，发送成为尾节点信息；当相临节点收到头节点信 息时，将相临节点列表中的头节点降为普通节点，并进一步向相临节 点转发该头节点信息；当临接点收到尾节点信息时，将相临节点列表 中的尾节点降为普通节点，并进一步向相临节点转发该尾节点信息。

本发明结合车联网的固有特性，将车辆的行为建立相互之间关系，加 入评估参数，以车辆之间的安全相关距离作为车辆分簇的一个参考依 据，进行车辆分簇。将相关车辆作为同一簇的成员，具有更为实际的 应用效果。通过这样的分簇，可以将车辆之间的通信限制在具有相互 影响的车辆之间，而不是漫无目的的大范围广播。在有效控制通信范 围的同时，提高信息的有效性和实用性。

附图说明

图1为本发明基于相邻车辆安全距离d的分簇示意图。

具体实施方式

如图1所示。如果以相邻车辆距离作为标准来分簇，把彼此相邻且相邻 距离小于d的车辆分成一簇，则分簇结果就和车辆安全相关性一致：同 一簇内，相邻车辆距离小，车辆安全相关；不同簇中的车辆，距离大 ，安全相关性小。为此，本发明提出一种基于相邻车辆距离的分簇， 把彼此相邻且相邻距离小于d的车辆分成一簇。

本发明的应用场景主要是高速公路上行驶的车辆，且只考虑一个方向 的车辆。随着GPS系统在车辆上越来越普及，假定每辆车都可以提供自 己的位置信息，每辆车都有相关的传感器能获知自己的速度、加速度 信息等。

由于高速公路通常比较窄，在这样的条件下，VANET可以看成是线状网 络。 在这样的线状网络结构中，头节点和尾节点定义如下：

步骤一：如果在车辆前面距离d范围内没有相邻节点，则该车辆节点为 头节点。

步骤二： 如果在车辆后面距离d范围之内没有相邻节点，则该车辆节 点为尾节点。

一般的，无线传输的一跳距离大于车辆之间的安全距离d，故每个节点 可根据自己一跳范围内的邻居节点位置信息就可判断自己是否为头尾 节点：如果在其前（后）方d距离内，没有相相临节点，则为头（尾） 节点。

分簇算法思想为：每个车辆节点判断自己是否为头尾节点，一对头尾 节点就决定了一个基于相邻节点距离的分簇。如果簇较小，选取簇内 最大权值节点为簇头节点。如果簇较大，一个簇头节点不能覆盖，则 选取相关的子簇头节点。

随后在一个整簇的车队行驶过程中，引起簇的变化的原因主要是头尾 节点的改变和无线链路的的改变。头尾节点的改变引起簇的变化相关 维护方法如下：

车辆节点u变成头节点，并且其不是尾节点，发送ChangeHead(u)消息 ；车辆节点u变成尾节点并且不是头节点，发送ChangeTail(u)消息。

车辆节点收到ChangeHead(u)消息：如果其邻居列表中包含u，且状态 为头节点，则把u的状态改为普通。如果该节点为头节点，进一步向邻 居节点转发ChangeHead(u) 消息。

车辆节点收到ChangeTail(u)消息：如果其邻居列表中包含u，且状态 为尾节点，则把u的状态改为普通。如果该节点为尾节点，进一步向邻 居节点转发ChangeTail(u)消息。

无线链路的的改变引起簇的变化主要分发现新链路和已有的链路断开 两种情况考虑，相关维护方法如下：

在节点邻居列表中，当发现和u失去连接后，v检查自己的角色，根据 自己的角色作出不同的反应：

（1）如果车辆v是簇头，则在邻居列表中消去u；

（2）如果车辆v是普通节点，并且u是簇头，此时需进一步确定v的角 色：如果在车辆v的邻居中，有簇头并且权值大于车辆v，则发送Join (v,x)，车辆v加入该簇；否则车辆v成为簇头，发送ClusterHead (v )消息；

（3）如果车辆v和车辆u是普通节点，则对该消息不做任何处理。

v发现和u建立连接后，如果v邻居列表中包含头（尾）节点，u位置在 头 （尾）节点后（前），则把u加入到邻居列表中，进一步检查u是否为 簇头节点，如果u是簇头，且u的权值大于v的当前簇头权值，则v的簇 头改为u，发送Join(v,u)消息。

任意车辆节点收到ClusterHead (v)消息：当车辆u成为簇头，并且权 值大于v的簇头，则v的簇头改为u，发送Join(v,u)消息。

车辆节点收到Join(u,z)消息：如果车辆v是簇头节点，v=z,则加入u, 否则在列表中删除u；如果车辆v是普通节点，并且u是自己的簇头，v 需要决定自己的角色：如果在邻居节点中，存在最大权值的簇头，且 权值大于自己，则v加入该簇；否则，v成为簇头，发送ClusterHead  (v)消息。