kaiyun官方注册
您所在的位置: 首页> 其他> 设计应用> 适用于车载自组织网络的稳定成簇算法
适用于车载自组织网络的稳定成簇算法
来源:电子技术应用2013年第10期
徐 圳, 黄 琼, 唐 伦, 陈前斌
重庆邮电大学 移动通信技术重庆市市级重点实验室,重庆 400065
摘要:车载自组织网络中网络拓扑频繁变化、链路不稳定。若直接使用移动自组网的成簇算法,将会引起传输延时增大及丢包率上升等一系列问题。提出一种基于AP相似度改进的稳定成簇算法——SD成簇算法。本算法以节点之间的相似度(similarity)和周围节点度(degree)作为分簇依据,利用节点的地理位置信息和邻居拓扑信息进行簇头选举。NS2仿真结果表明,该算法能有效地改善车载自组织网络中簇结构的稳定性。
中图分类号:TN929
文献标识码:A
文章编号: 0258-7998(2013)10-0095-04
The stable clustering algorithm applying to VANET
Xu Zhen, Huang Qiong, Tang Lun, Chen Qianbin
Chongqing Key Lab of Mobile Communications Technology,Chongqing University of Post and Communications, Chongqing 400065, China
Abstract:In Vehicular Ad Hoc NETwork(VANET), network topology changes rapidly and link is not unstable. If the clustering algorithm of mobile ad hoc networks is directly used, a series of problems occur. For instance, transmission delay increases and package loss goes up. This paper presents a kind of improved and stabilized clustering algorithm based on AP similarity—SD clustering algorithm. The algorithm is based on similarity between nodes and node degree all round carries out cluster head elections, and takes advantage of geographical position information of nodes and neighbor topology information. The result of NS2 simulation shows that the algorithm could effectively improve the stability of cluster structure in VANET.
Key words :VANET; affinity propagation(AP) algorithm; cluster head geographical position; SD algorithm

车载自组网络(VANET)是移动自组网络(MANET)的延伸,是智能交通系统(ITS)的重要组成部分,能有效地提高道路安全性,改善交通拥塞状况,满足人们对驾驶安全性和舒适性的要求。

在MANET网络中,网络层次划分有拓扑管理方便、能量利用高效、数据融合简单等优点,成为当前重点研究的技术。在分级结构中,网络中的节点逻辑上被划分为簇,每个簇通常由1个簇头和多个普通节点组成,簇有利于降低路由开销、改善网络延迟。CBRP协议[1](Cluster Based Routing Protocol)是最早的Ad Hoc分簇路由协议之一,也是一种基于分簇结构的源路由按需路由协议。成簇算法是成簇路由的关键,好的成簇算法可以提高传输的投递率,减少路由的跳数。改善成簇算法、提高成簇的稳定性,是将MANET中的成簇路由引入VANET中关键技术。
1 几种典型成簇算法
最小ID算法[2]是最早的成簇算法,即在成簇范围内选择ID最小节点作为簇头。在VANET中,节点快速移动、网络拓扑频繁变化、链路不稳定,使用最小ID算法会造成簇不稳定、簇头变化快,从而影响传输的实时性,增大了网络的丢包率。
最高节点度分簇算法[3]借鉴了因特网中选择路由器的方法,尽可能减少路由器的数目,节点之间通过交互控制消息知道其他节点的邻居节点数目,拥有相邻节点最多的节点被选举为簇头。该算法的优点在于路由的跳数少,从而减少了网络中分组投递的平均时延。但是该算法不限制簇内的节点数,簇的资源按照轮询的方式共享,当簇内节点数量过多时,每个用户节点的吞吐量急剧下降,使得整个系统的性能也随之降低。当节点运动速度快时,簇头的更换频率也会急剧上升,导致大量的簇维护开销,不适用于高移动性的车载网路。
节点权重分簇算法[4-6]是在考虑多个因素的基础上,根据节点适合作为簇头的程度来为每个节点分配相应的权重,算法一般描述为:
W=a×mobility+b×degree+c×erengy+d×else (1)
其中a、b、c、d为权值系数。mobility表示节点的移动性,degree表示节点度,energy表示剩余能量,else表示其他影响因素。考虑车载网路中的独特因素,节点剩余能量可以不予考虑,重点考虑车辆的移动性。选举更稳定的节点作为簇头增加数据传输的投递率。此方法的缺点是考虑的因素多、簇头变化频率多,适合于节点移动性小的场景。
负载平衡算法[7]、最小ID算法和最高节点度分簇算法都倾向于选择某些节点作为簇头,使得这些节点的负担较重,很容易耗尽能量。为此,需要在簇头间实施负载平衡,使所有节点都可以较公平地充当簇头。这种算法簇头的负载分布特性较好,但是簇结构很不稳定,而且在车载自组织网络中的车辆有充足的能量可以不予考虑。
随着车载自组织网络的发展,越来越多的成簇算法适合在车载自组织网络场景中。参考文献[8]提出了一种新的成簇算法,专用于车载自组织网络,该算法把速度作为主要影响成簇的因素,并对速度采用模糊处理提高了成簇的稳定性。算法还选择一个权重第二优的节点作为临时簇头,当簇头突然失效时临时簇头就充当簇头直到选出新的簇头。虽然该算法用于高速移动的场景,但是当簇头速度变化较大时,簇头更换也较为频繁,由于网络拓扑变化快,临时簇头的性能不稳定会降低成簇的稳定性。
Affinity Propagation(AP)聚类算法[9]是近年来提出的较稳定的类聚算法之一。它根据N个数据点之间的相似度进行聚类,这些相似度可以是对称的,即两个数据点互相之间的相似度相同(如欧氏距离);也可以是不对称的,即两个数据点互相之间的相似度不等。相似度是AP算法中的重要因素,数据点i和点j的相似度记为S(i,j)。一般使用欧氏距离来计算,所有点与点的相似度值全部取为负值。参考文献[10]将AP类聚算法用于车载自组织网络中,大大提高了在高速多节点下成簇的稳定性。但是AP算法本身有自己的缺陷,AP算法是基于距离的成簇算法,当速度变化大时,簇头仍然更换较快,并且它需要大量的迭代循环算法,这增加了成簇的时延,并不能提高成簇路由的吞吐量和时延。
结合AP成簇算法和节点权重成簇算法的优缺点,本文提出了一种基于节点相似度和节点度的稳定成簇算法,该算法适合速度变化较大的场景。
2 SD算法描述
假设: (1)每个车辆都装有GPS设备,可以随时准确知道自己的位置坐标,速度表提供车辆速度信息;(2)每个节点配备一个半双工全向天线。可以接收各个方向发出的信号;(3)车辆的通信范围为250 m。



3 SD算法流程
SD算法的具体过程如下:
(1)初始化,每个节点都处于未分配状态。邻居数目N为0,相似度S=0,设置权值W为-1 000,设置自己的状态为U(未分配)。设置综合权值W为一个很低的负数,不设置为0,这是因为选择权值W最大的作为簇头,而相似度是一个负数,这样便于新节点的加入。
(2)节点进入网络,通过GPS获取自己的位置信息,通过速度表获得自己的速度信息和权值W。因为刚进入网络都参与簇头的竞争,设置自己的状态为CH,将获得信息加入hello包中广播给邻居节点。
(3)获得邻居节点hello包,提取邻居列表信息。通过式(2)计算自己与邻居节点的相似度,将邻居节点的信息与相似度存储到邻居列表中。当节点的状态为簇头存储两跳范围内的节点信息时,CM和GM分别存储。
(4)遍历邻居列表,获得邻居节点个数即节点度,计算出自己权值W并与邻居权值对比,如果自己的权值大于所有邻居节点的权值,设置自己的状态为CH,广播自己的位置、速度、状态以及W。否则设置自己的状态为CM,广播自己的位置、速度、状态、W以及邻居列表信息。
(5)当节点感知可达范围内有2个以上的簇头即收到多个簇头广播包,设置自己的状态为GM。广播自己的位置、速度、状态、W信息。
4 仿真结果分析
  为了验证SD算法的性能,使用NS2对算法性能进行评估。
4.1 算法性能衡量标准
(1)簇的数量
在相同的范围和相同的节点数量条件下,簇的数量直接影响了分簇算法的性能。簇的数量越多,意味着在相同距离内的平均跳数越多,从而信息传输的时延更大,并且投递率也会大大降低。簇头数量少虽然路由跳数少但是每个簇管理成员增多,这样给簇头造成很大的压力,从而影响路由性能。在分簇算法研究中,簇的数量是常用来衡量分簇算法性能的标准之一。
(2)簇的稳定性
簇的稳定性是所有衡量分簇算法性能的标准中最重要的一个。簇的稳定性越好,用来维护簇的开销就越小,路由的生存时间就越长,用于路由发现的开销也就越少,因此网络的吞吐量越大。因此在考虑VANET分簇算法时,簇的稳定性应该作为最重要的衡量标准。


节点个数不多的情况下,提高更为明显,非常适合于车载自组织网络的成簇路由中。
成簇路由在MANET网络中占有非常重要的地位,但是在VANET中网络拓扑非常不稳定,合理的成簇算法是成簇路由应用在车载自组织网络中的关键所在。本文提出的基于节点相似度和最大节点度的成簇算法,增加了车载自组织网络中成簇的稳定性,提高了成簇路由在车载自组织网络中的性能。
参考文献
[1] JIANG M, LI J, TAY Y. Cluster based routing protocol (CBRP) functional specification [Z]. IETF Internet-Draft, Aug 1998.
[2] LIN C R, GERLA M. Adaptive clustering for mobile wireless networks[J]. IEEE J. Select. Areas Communications, 1997,15(7):1265-1275.
[3] GERLA M, TSAI J T. Tsai. Multicluster, mobile, multimedia radionetwork[J]. Wirel. Netw., 1995(1):255-265.
[4] WU H, ZHONG Z, HANZO L. A cluster-head selection and updatealgorithm for ad hoc networks[C]. Proc. IEEE Globecomm Conf., 2010:1-5.
[5] CHATTERJEE M,DAS S K,TURGUT D. WCA:A weighted clusteringalgorithm for mobile ad hoc networks[J]. Cluster Computing, 2002(5):193-204.
[6] 杨卫东. 用于Ad Hoc 网络的分簇算法[J]. 北京邮电大学学报,2009,32(5):61-65.
[7] YOUNIS O, FAHMY S. Heed: a hybrid, energy-efficient, distributed clustering approach for ad-hoc sensor networks[J]. IEEE Trans. on Mobile Computing, 2004,3(4):660-669.
[8] HAFEEZ K A, Zhao Lian, LIAO Zaiyi. A fuzzy-logic-based cluster head selection algorithm in VANETs[C].IEEE Communications (ICC), 2012:203-207.
[9] FREY B J, DUECK D. Clustering by passing messages between datapoints[J]. Science, 2007,315:972-976.
[10] SHEA C, HASSANABADI B, VALAEE S. Mobility-based clustering in VANETs using affinity propagation[C]. IEEE "GLOBECOM" 2009.

此内容为AET网站原创,未经授权禁止转载。
Baidu
map