文獻標識碼: 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.