黄 欣，余思东，赵志刚

(1.广西农业职业技术学院信息与机电工程系，广西南宁 530007; 2.广西大学计算机与电子信息学院,广西南宁 530004)

0 引言

车载自组织网(Vehicular Ad Hoc Networks，VANETs)是指由路边单元、车辆之间构成的一种移动自组织网络，旨在提高交通安全系数，是智能交通的重要组成成分[1]。VANETs具有车辆高速移动的动态变化特点，容易造成其通信链路断裂而通信质量不佳。可靠而稳定的成簇算法可以实时传输数据，减少网络通信延迟，为智能交通系统奠定技术基础。

为提高VANETs通信的可靠性以及稳定性，如何将VANETs更为准确地划分成簇，使得计算成本最小化和网络寿命周期最大化之间平衡，一些研究者将成簇算法用于VANETs中[2]。Gerla等[3]针对VANETs成簇的稳定性，提出一种基于节点的空间位置的最小ID成簇算法，给所有的节点标识唯一ID，将最小ID标识设置为簇头。该算法实现简单，计算成本低，但是牺牲了节点的负载均衡，不适用于高速移动的场景。Basu等[4]基于节点移动的差异提出最小相对移动成簇算法，该算法通过比较一个节点与其他节点的移动差异的方差来选择簇头，有效地提高了成簇的稳定性，但是也不适用于高速移动的场景。Chatterjee等[5]基于节点的移动特性、车辆流量以及节点能量提出一种按需加权的成簇算法，该算法较为全面地考虑了节点的特性，但是算法的计算成本也大大增加。许力文等[6]基于车辆的平均速度、位置和方向等信息，提出一种改进的K-means分簇算法，该算法利用改进的K-means算法划分成簇，再利用改进的Floyd-Warshall算法选择簇投，从而提高VANETs通信链路的稳定性。……