[發明專利]基于綜合加權的VANET分簇廣播方法

無效

• 申請號: 201110243485.3
• 申請日: 2011-08-23
• 公開（公告）號: CN102325306A
• 公開（公告）日: 2012-01-18
• 發明（設計）人: 崔剛;周連科;付忠傳;暴建民;朱東杰;王秀峰;莫毓昌;張策;張必英;劉永文
• 申請（專利權）人: 哈爾濱工業大學
• 主分類號: H04W4/06
• 分類號: H04W4/06;H04W84/18
• 代理公司: 哈爾濱市松花江專利商標事務所 23109
• 代理人: 牟永林

技術領域

本發明涉及車載無線自組網的廣播方法。

背景技術

在傳統的移動自組網中，為解決網絡的穩定和負載平衡問題，研究人員提出了一些分層廣播的方法。即把整個網絡劃分成若干個簇(Cluster)，每個簇由一個簇首和多個成員組成。簇與簇之間由網關(Gateway)連接。簇成員之間的通信通過簇首進行，簇之間的通信則可經過簇首或者網關轉發。其優點是可擴展性好，網絡規模不受限制。目前，網絡分簇的算法主要分別如下五類：

(1)基于節點ID的分簇算法

鏈路分簇算法(Link?Clustering?Algorithm，LCA)是一種基于最高節點ID的分簇算法。LCA算法中，鄰居節點具有最高ID的節點成為簇首，并且如果一個節點是其某個鄰居節點的ID最高的鄰居節點，此節點也可成為簇首。該分簇方法首先選擇ID最高的節點成為簇首。如果次高ID的節點所覆蓋的范圍內存在沒有被ID最高的簇首覆蓋的節點，那么次高ID的節點也成為簇首，否則繼續檢查下一個ID較高的節點，直到所有節點都屬于某個簇。這種分簇方法實現簡單，但是會產生過多的簇首，特別是當節點按ID遞增的順序線性排列時，此時除第一個節點外，其他節點都是簇首。另一種基于節點ID的分簇算法是最小ID(Lowest-ID，LID)分簇算法。在LID分簇算法中，為每個節點根本唯一的ID。節點定期期向其鄰居節點廣播自己的ID值。每個節點通過比較自己的ID值與其鄰居節點的ID大小來確定自己是的ID值是否為沒有確定狀態的節點中最小的。若本節點ID最小且鄰居中不存在簇首節點，則此節點聲明為簇首節點。一個節點收到一個簇首聲明，則加入該簇，并聲明自己為成員，同時收到兩個簇首聲明的節點為網關。此類基于節點ID的方法的主要缺點是節點一旦分配到小ID則其成為簇首的可能性要遠高于其他節點，會使這樣的節點經常被選舉為簇首，從而使其負載遠遠大于其它節點，使網絡的公平性降低，負載不平衡。

(2)最高節點度分簇算法

最高節點度(Max-Degree)分簇算法[通過比較的連通度(degree)，即節點鄰居數量來選擇簇首節點。實現方法與最小算法類似，節點通過廣播其鄰居個數，即連通度與其鄰節點比較連通度，選擇連通度最大的節點為簇首。在移動自組網中，尤其是拓撲變化快的網絡中，由于節點的連通度隨拓撲變化，所以其形成的簇結構的穩定性較差。

(3)最低移動性分簇算法

在分簇算法中，生成簇結構的穩定性對網絡性能影響最大。為了提高簇結構的穩定性，出現了最小移動速度(Lowest?speed)算法，該算法通過比較節點移動速度來選擇移動速度小的節點優先成為簇首節點。認為移動速度低的節點作為簇首形成的簇結構穩定，簇變化頻率低。但是這種算法只適合節點移動速率低的網絡，對于如VANET(車載無線自組網)的節點高速移動的網絡，尤其是節點的相對移動性高的網絡，其形成的簇結構不穩定，簇改變頻率高。

(4)基于位置預測的算法

Sivavakeesar和Pavlou提出了基于位置預測的簇首選擇算法。該算法中提出了“虛簇”的概念，將整個網絡覆蓋區域劃分成多個“虛簇”區域，將每個節點同與其在同一個“虛簇”內的其它節點進行比較，選擇所在“虛簇”概率最小或與當前“虛簇”中心的距離最短的節點作為簇首。節點可通過GPS或者其它定位方法獲取其地理信息，并確定所屬“虛簇”。該算法在節點移動性較弱時形成的簇結構穩定，且簇首數量較為固定，具有較好的性能。但是，在節點移動速度較高，拓撲變化快的網絡中形成的分簇結構不穩定，簇首變化頻率以及成員變化頻率較高。

在VANET中，節點規模大，密度變化大，尤其在某些時候車輛跟駛，自然分成簇狀，也適合采用分層的方法來進行數據廣播。但VANET是一種臨時性網絡，拓撲變化大，節點速度快，鏈路存在時間短，這些特點會影響到簇的結構。同時，簇的穩定性是分簇算法的一個重要問題，簇的變化不可避免，但應力求簇結構變化最小，算法應該能夠探測并應對拓撲結構的變化以保持合適的簇結構。此時若采用基于信息交換的方法來維護一個分層網絡需要通過定期廣播控制信息來維持，需要較大的控制開銷，從而增加了網絡負載。

傳統的VANET分簇算法一般針對影響分簇結構的連通性、穩定性、負載平衡等因素中的某一個因素來進行，而不考慮影響分簇的其它方面。

發明內容

本發明的目的是提供一種基于綜合加權的VANET分簇廣播方法，以解決車載無線自組網廣播方法中傳統的分簇算法針對影響分簇結構的連通性、穩定性、負載平衡等因素中的某一個因素來進行，而不考慮影響分簇的其它方面的缺點。

本發明包括下述步驟：