文献标识码:A
文章编号: 0258-7998(2013)10-0095-04
车载自组网络(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.