本发明涉及车辆网通信技术领域，尤其是一种基于谱聚类的车联网车辆节点分簇方法。
背景技术：
车联网作为一种特殊的ad-hoc网络，其由可以彼此通信的移动车辆构成。它不仅可以支持娱乐消息广播，自动紧急呼叫，在线导航，远程诊断和交通信息，还可以通过车辆之间的视频消息交换来提高道路交通安全性和交通效率。近年来，许多研究人员对该领域给予了极大的关注。
近年来，围绕车辆分簇众多学者展开了大量研究。由于vanet中车辆快速地运动和其特殊的信道状况，传统的移动自组织网络manet和传感器网络等领域的分簇算法在vanet中并不适用。vanet中的分簇算法逐渐发展，并呈现区别于manet的新特质。具体地，vanet中的分簇算法所涉及到的技术主要包括信道监测、运动预测、机器学习、安全评估等。vanet的研究已经逐渐独立于manet，车辆的分簇算法也日益增多。最早的分簇算法可以追溯到dappa在1987年提出的基于manet的自主分簇技术。s.basagni在1999年提出了利用节点id进行分簇的方法。这类方法被证明可以应用至vanet环境中，并形成不同的分簇方法。文献即实现了基于前述方法的mobic算法。然而这类方法主要的不足之处在于仅仅使用车辆的id，而没有考虑到网络的拓扑结构中所包含的信息。此外，相关研究成果也提出了一些基于数据挖掘的车辆分簇算法，例如c.shea在2009年提出的临近传播分簇算法，但事实证明在实际的vanet环境中难以实现。m.ni在2011年提出的分簇算法虽然考虑了车辆的运动特性，但是却忽略了车辆的主观意图，即车主的特定行驶意图才是车辆沿某特定路线运动的根本原因。为了保证节点之间稳定可靠的通信，liu等提出一种基于聚类和概率广播(cpb)的新型数据传播方案。首先根据车辆的行驶方向呈现聚类算法，通过该算法，车辆可以以具有足够连接持续时间的聚类方式交换其数据。qureshi，kn等提出了一种基于群集的稀疏和密集网络路由，以处理动态拓扑，即车辆节点的高移动性。dutta，c等提出一种利用簇头机制和人工神经网络(ann)来增强数据传输机制的新型聚类概念。使用均方误差和分组传递率来评估所提出的算法的性能。joshua，cj等提出了基于信誉的加权聚类协议(rwcp)。rwcp通过考虑车辆的方向，位置，速度，附近车辆的数量，车道id以及每个节点的声誉来构建，以稳定vanet拓扑，但算法过于复杂化，难以在实际中应用。此外，现有算法的泛用性也存在不足：有些算法仅针对于公路场景；而有些算法仅适用于城市街道场景。
总的来说，现有的车辆分簇算法主要存在以下问题：1)不能同时适用于公路与城市街道等不同环境；2)没有利用车辆簇网络自身的拓扑结构；3)关注焦点集中在簇头的选择上，忽略了整个集群的稳定性。因此，需要一种泛用性强并能够增强整个集群稳定性的分簇方法。
技术实现要素：
发明目的：为解决上述技术问题，本发明提出一种基于谱聚类的车联网车辆节点分簇方法。
技术方案：本发明提出的技术方案为：
一种基于谱聚类的车联网车辆节点分簇方法，包括步骤：
(1)基于车辆节点相对运动特性，采用力导向算法构建车辆节点间相互作用力公式，记车辆节点i和j之间的相互作用力为fij；
(2)创建同时满足以下两个条件的邻接矩阵w：
条件1：车辆节点i与车辆节点j间的距离大于通信半径r时，wij＝0，wij为邻接矩阵w中第i行第j列的元素；
条件2：当车辆节点i与车辆节点j互为对方的k最近邻，且k的值等于期望的簇大小e时，wij＝fij；否则wij＝0；
(4)根据邻接矩阵w构建度矩阵d：
其中，
(5)根据邻接矩阵w和度矩阵d得到拉普拉斯矩阵l＝d-w；
(6)根据邻接矩阵w、度矩阵d和拉普拉斯矩阵l，采用谱聚类算法对无向加权图进行切图，每一个子图为一个分簇；
(7)设置反应式机制对整个系统进行重新聚类：当存在空闲车辆节点时，获取空闲节车辆点周围一跳邻居节点，将邻居节点所在簇中的所有节点和空闲节点都归为重新聚类节点集合，对重新聚类节点集合中的车辆节点执行步骤(1)至(6)。
进一步的，所述采用力导向算法构建车辆节点间相互作用力公式的具体步骤包括：
s1、构建地面坐标系，设置原点、x轴、y轴；
s2、计算t时刻车辆节点i和j之间的相对距离在x轴、y轴上的分量：
dc，ij，x(t)＝xi(t)-xj(t)
dc，ij，y(t)＝yi(t)-yj(t)
其中，(xi(t)，yi(t))为t时刻车辆节点i在地面坐标系内的坐标，(xj(t)，yj(t))为t时刻车辆节点j在地面坐标系内的坐标；
s3、计算t δt时刻车辆节点i和j之间的相对距离在x轴、y轴上的分量：
df，ij，x(t dt)＝xi(t dt)-xj(t dt)
df，ij，y(t dt)＝yi(t dt)-yj(t dt)
其中，δt为预设的时间增量；
s4：计算车辆节点i和j在x轴、y轴上的相对移动特性：
其中，ax＝|dc，ij，x(t)-df，ij，x(t dt)|，ay＝|dc，ij，y(t)-df，ij，y(t dt)|，λ＝1表示车辆节点i和j做相对距离逐渐减小的运动，λ＝-1表示车辆节点i和j做相对距离逐渐增大的运动；
s5、计算车辆节点i和j在x轴、y轴上的相对作用力：
其中，
进一步的，所述采用谱聚类算法对无向加权图进行切图的具体步骤包括：
构建车联网聚类问题的切图模型：
其中，
构建切图模型的优化模型：
argmintr(ftd-1/2ld-1/2f)
s.t.ftf＝i
其中，tr(ftd-1/2ld-1/2f)表示矩阵的迹，f＝d-1/2ld-1/2；
对优化模型进行求解：对拉普拉斯矩阵l进行特征值分解，取值最小的k个n维特征值，计算k个特征值的特征向量u1，u2，..，uk，将k个特征向量组成特征矩阵：u＝{u1，u2，...，uk}，u∈rn*k；将u中的每一行作为一个样本si，共计n个样本；用k-means算法将n个样本聚类为k个簇：c1，c2，...ck；根据c1，c2，...ck得到a1，a2，...，ak，ak＝{q|sq∈ck}。
有益效果：与现有技术相比，本发明具有以下优势：
本发明通过利用力导向算法将车联网聚类问题构建为一张图，进而将聚类问题转化为切图优化问题，通过求解这一切图优化问题并应用反应机制对系统重新聚类可以增强整个系统的稳定性，延长簇的平均维持时间，并且可适用于不同的场景。
附图说明
图1为本发明涉及的一种基于谱聚类的车联网车辆节点分簇方法的流程图；
图2为不同情况下平均集群生命周期随通信距离r的变化图；
图3为不同情况下平均集群大小随通信距离r的变化图；
图4为通信距离为150m时不同情况下的平均集群生命周期随车辆到达速率的变化图。
具体实施方式
下面将结合附图和具体实施例对本发明作更进一步的说明。但应当理解的是，本发明可以以各种形式实施，以下在附图中出示并且在下文中描述的一些示例性和非限制性实施例，并不意图将本发明限制于所说明的具体实施例。
图1示出了本发明涉及的一种基于谱聚类的车联网车辆节点分簇方法的流程图，该方法包括以下步骤：
(1)基于车辆节点相对运动特性，采用力导向算法构建车辆节点间相互作用力公式，记车辆节点i和j之间的相互作用力为fij；
(2)创建同时满足以下两个条件的邻接矩阵w：
条件1：车辆节点i与车辆节点j间的距离大于通信半径r时，wij＝0，wij为邻接矩阵w中第i行第j列的元素；
条件2：当车辆节点i与车辆节点j互为对方的k最近邻，且k的值等于期望的簇大小e时，wij＝fij；否则wij＝0；
(4)根据邻接矩阵w构建度矩阵d：
其中，
(5)根据邻接矩阵w和度矩阵d得到拉普拉斯矩阵l＝d-w；
(6)根据邻接矩阵w、度矩阵d和拉普拉斯矩阵l，采用谱聚类算法对无向加权图进行切图，每一个子图为一个分簇；
(7)设置反应式机制对整个系统进行重新聚类：当存在空闲车辆节点时，获取空闲节车辆点周围一跳邻居节点，将邻居节点所在簇中的所有节点和空闲节点都归为重新聚类节点集合，对重新聚类节点集合中的车辆节点执行步骤(1)至(6)。
在步骤(1)中，基于车辆节点相对运动特性，采用力导向算法构建车辆节点间相互作用力公式。具体地说，应用力导向算法计算无向加权图顶点之间的相对作用力的原理是：力导向算法将顶点看作带电粒子，然后计算这些带电粒子之间的相互作用力，这些相互作用力被当做边之间的权重，这样整个网络就好像是一个物理系统，施加在顶点上的力将它们拉得更近或将它们推得更远，这与车联网聚类的目地是一致的，即鼓励具有相似位置和速度的车辆形成集群。采用力导向算法构建车辆节点间相互作用力公式的具体步骤包括：
s1、构建地面坐标系，设置原点、x轴、y轴；
s2、计算t时刻车辆节点i和j之间的相对距离在x轴、y轴上的分量：
dc，ij，x(t)＝xi(t)-xj(t)
dc，ij，y(t)＝yi(t)-yj(t)
其中，(xi(t)，yi(t))为t时刻车辆节点i在地面坐标系内的坐标，(xj(t)，yj(t))为t时刻车辆节点j在地面坐标系内的坐标；
s3、计算t δt时刻车辆节点i和j之间的相对距离在x轴、y轴上的分量：
df，ij，x(t dt)＝xi(t dt)-xj(t dt)
df，ij，y(t dt)＝yi(t dt)-yj(t dt)
其中，δt为预设的时间增量；
s4：计算车辆节点i和j在x轴、y轴上的相对移动特性：
其中，ax＝|dc，ij，x(t)-df，ij，x(t dt)|，ay＝|dc，ij，y(t)-df，ij，y(t dt)|，λ＝1表示车辆节点i和j做相对距离逐渐减小的运动，λ＝-1表示车辆节点i和j做相对距离逐渐增大的运动；
s5、计算车辆节点i和j在x轴、y轴上的相对作用力：
其中，
在步骤(2)中，创建邻接矩阵w，具体地说，谱聚类将一整张图形切割成子图，使子图内的权重尽可能高，子图之间的权重尽可能低，这与车联网聚类的目标是一致的，即鼓励具有相似位置和速度的车辆形成集群，反之则不要形成集群。由于将车联网系统中的车辆建模为带电粒子，这些相互作用力被当做边之间的权重，则整个系统就可以被看做一个无向加权图。同时在所得顶点间的相互作用力的基础上，按照一定规则创建谱聚类求解所需的邻接矩阵w，那么就可以通过切图的方式进行对车联网聚问题求解。
创建邻接矩阵w要遵循以下两个条件：
条件1：车辆节点i与车辆节点j间的距离大于通信半径r时，wij＝0，wij为邻接矩阵w中第i行第j列的元素；
条件2：当车辆节点i与车辆节点j互为对方的k最近邻，且k的值等于期望的簇大小e时，wij＝fij；否则wij＝0。
在步骤(6)中，采用谱聚类算法对无向加权图进行切图，具体地说，包括以下步骤：
构建车联网聚类问题的切图模型：
其中，
构建切图模型的优化模型：
argmintr(ftd-1/2ld-1/2f)
s.t.ftf＝i
其中，tr(ftd-1/2ld-1/2f)表示矩阵的迹，f＝d-1/2ld-1/2；
对优化模型进行求解：对拉普拉斯矩阵l进行特征值分解，取值最小的k个n维特征值，计算k个特征值的特征向量u1，u2，...，uk，将k个特征向量组成特征矩阵：u＝u1，u2，...，uk}，u∈rn*k；将u中的每一行作为一个样本si，共计n个样本；用k-means算法将n个样本聚类为k个簇：c1，c2，...ck；根据c1，c2，...ck得到a1，a2，...，ak，ak＝{q|sq∈ck}。
其中，k-means算法实现聚类的步骤为：
a)选取k个聚类中心，
b)对与数据集s中的每个数据点，按照距离k个中心点的距离，将其与距离最近的中心点关联起来，与同一中心点关联的所有点聚成一类；
c)计算每一组的均值，将该组所关联的中心点移动到平均值的位置；
d)重复执行步骤b)到c)，直至中心点不再变化，得到聚类c1，c2，...ck，输出a1，a2，...，ak其中ak＝{q|sq∈ck}。
下面通过具体仿真数据阐述本发明能够取得的技术效果。
给定具体应用背景如下：
交通仿真是通过应用城市交通仿真(sumo)来进行的，sumo是一个非常优秀的模拟vanet的微交通模拟器。此外，move软件用于生成逼真的移动轨迹。仿真环境设置基于120km长度的双向4车道直线路段。在仿真中，500辆车从固定的十字路口出发。车辆平均分为20组，每组具有不同的速度和加速度，车辆属于哪一组取决于其到达时间，车辆的到达出发路口的速率遵循参数为λ的泊松过程。模拟的主要参数值如表i所示：
表1
图2至图4为本发明与直接按照距离聚类和sp-cl(springclustering)聚类方法相比的仿真效果示意图，其中，图2为不同情况下平均集群生命周期随通信距离r的变化图，图3为不同情况下平均集群大小随通信距离r的变化图，图4为通信距离为150m时不同情况下的平均集群生命周期随车辆到达速率的变化图。
图2显示了车辆到出发路口遵循泊松参数λ＝1时通信半径对簇的平均生命周期的影响，平均集群生命周期越长，集群就越稳定。可以清楚地看到，集群维持时间随着通信半径的增加而增加，这是因为成员将花费更多时间才能从具有较大传输范围的群集中离开，
图3示出了车辆到出发路口遵循泊松参数λ＝1时通信半径对平均簇大小的影响。可以看出簇大小随着传输范围而增加。这是因为当传输范围变大时，节点倾向于形成更大的簇。同时，可以发现本发明所提的方法中期望的聚类大小改变会导致平均聚类大小的变化。这表明e的初始化值对得到的平均聚类大小有影响，这带来另一个好处，可以通过改变期望的集群大小来改变最终的集群大小。
图6示出了当传输范围等于150时到车辆到达出发λ对平均簇寿命的影响，可以看到提出的方法导致最长的平均寿命集群。
应当理解的是，在技术上可行的情况下，以上针对不同实施例所列举的技术特征可以相互组合，从而形成本发明范围内的另外的实施例。此外，本发明所述的特定示例和实施例是非限制性的，并且可以对以上所阐述的结构、步骤、顺序做出相应修改而不脱离本发明的保护范围。
上述实施例，特别是任何“优选”实施例，是实施方式的可能示例，并且仅仅为了清楚理解本发明的原理而提出。在基本上不脱离本发明描述的技术的精神和原理的情况下，可以对上述实施例做出许多变化和修改，这些变化和修改也应视为本发明的保护范围。
1.一种基于谱聚类的车联网车辆节点分簇方法，其特征在于，包括步骤：
(1)基于车辆节点相对运动特性，采用力导向算法构建车辆节点间相互作用力公式，记车辆节点i和j之间的相互作用力为fij；
(2)创建同时满足以下两个条件的邻接矩阵w：
条件1：车辆节点i与车辆节点j间的距离大于通信半径r时，wij＝0，wij为邻接矩阵w中第i行第j列的元素；
条件2：当车辆节点i与车辆节点j互为对方的k最近邻，且k的值等于期望的簇大小e时，wij＝fij；否则wij＝0；
(4)根据邻接矩阵w构建度矩阵d：
其中，
(5)根据邻接矩阵w和度矩阵d得到拉普拉斯矩阵l＝d-w；
(6)根据邻接矩阵w、度矩阵d和拉普拉斯矩阵l，采用谱聚类算法对无向加权图进行切图，每一个子图为一个分簇；
(7)设置反应式机制对整个系统进行重新聚类：当存在空闲车辆节点时，获取空闲节车辆点周围一跳邻居节点，将邻居节点所在簇中的所有节点和空闲节点都归为重新聚类节点集合，对重新聚类节点集合中的车辆节点执行步骤(1)至(6)。
2.根据权利要求1所述的一种基于谱聚类的车联网车辆节点分簇方法，其特征在于，所述采用力导向算法构建车辆节点间相互作用力公式的具体步骤包括：
s1、构建地面坐标系，设置原点、x轴、y轴；
s2、计算t时刻车辆节点i和j之间的相对距离在x轴、y轴上的分量：
dc，ij，x(t)＝xi(t)-xj(t)
dc，ij，y(t)＝yi(t)-yj(t)
其中，(xi(t)，yi(t))为t时刻车辆节点i在地面坐标系内的坐标，(xj(t)，yj(t))为t时刻车辆节点j在地面坐标系内的坐标；
s3、计算t δt时刻车辆节点i和j之间的相对距离在x轴、y轴上的分量：
df，ij，x(t dt)＝xi(t dt)-xj(t dt)
df，ij，y(t dt)＝yi(t dt)-yj(t dt)
其中，δt为预设的时间增量；
s4：计算车辆节点i和j在x轴、y轴上的相对移动特性：
其中，ax＝|dc，ij，x(i)-df，ij，x(t dt)|，ay＝|dc，ij，y(t)-df，ij，y(t dt)|，λ＝1表示车辆节点i和j做相对距离逐渐减小的运动，λ＝-1表示车辆节点i和j做相对距离逐渐增大的运动；
s5、计算车辆节点i和j在x轴、y轴上的相对作用力：
其中，
3.根据权利要求2所述的一种基于谱聚类的车联网车辆节点分簇方法，其特征在于，所述采用谱聚类算法对无向加权图进行切图的具体步骤包括：
构建车联网聚类问题的切图模型：
其中，
构建切图模型的优化模型：
argmintr(ftd-1/2ld-1/2f)
s.t.ftf＝i
其中，tr(ftd-1/2ld-1/2f)表示矩阵的迹，f＝d-1/2ld-1/2；
对优化模型进行求解：对拉普拉斯矩阵l进行特征值分解，取值最小的k个n维特征值，计算k个特征值的特征向量u1，u2，…，uk，将k个特征向量组成特征矩阵：u＝{u1，u2，...，uk}，u∈rn*k；将u中的每一行作为一个样本si，共计n个样本；用k-means算法将n个样本聚类为k个簇：c1，c2，...ck；根据c1，c2，...ck得到a1，a2，...，ak，ak＝{q|sq∈ck}。
技术总结