《電子技術應用》
您所在的位置:首頁 > 其他 > 設計應用 > 適用于車載自組織網絡的穩定成簇算法
NI-LabVIEW 2025
適用于車載自組織網絡的穩定成簇算法
來源:電子技術應用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網站原創,未經授權禁止轉載。
主站蜘蛛池模板: 国产91精品高跟丝袜在线 | 中文字幕日韩欧美一区二区三区 | 午夜寂寞网 | 国产自产自拍 | 国产一级成人毛片 | 欧美图片在线视频 | 老司机69精品成免费视频 | 国产在线精品成人一区二区三区 | 亚洲欧洲视频 | 欧美视频免费在线 | 丰满大胸五十路免费 | 国产欧美日韩精品a在线观看高清 | 福利精品视频 | 俄罗斯高清freexxxx性 | 免费无遮挡十八污污网站 | 丁香网五月 | 伊人网国产 | 亚洲欧美日韩成人网 | 亚洲精品线在线观看 | 99re视频在线观看 | 全免费午夜一级毛片真人 | 中文精品北条麻妃中文 | 人人搞人人爽 | 中国女人hd| 欧美综合中文字幕久久 | 欧美三级成人理伦 | 天堂中文资源在线观看 | 欧美在线中文字幕 | 黄色片一级黄色片 | 日韩视频免费一区二区三区 | 日韩毛片在线观看 | 国产成人精品综合久久久软件 | 久久精选视频 | 三级网站| 舔舔射| 日韩.欧美.国产.无需播放器 | 午夜视频体验区 | 亚洲国产剧情在线 | a级毛片毛片免费观看永久 a级毛片黄色 | 99资源在线 | 国产区精品一区二区不卡中文 |