考慮車輛交通特性的vanet分簇方法
2023-12-05 10:57:21 1
專利名稱：考慮車輛交通特性的vanet分簇方法
技術領域：
本發明涉及車載無線自組網的分簇方法。
背景技術：
在傳統的移動自組網中，為解決網絡的穩定和負載平衡問題，研究人員提出了一些分層廣播的方法。即把整個網絡劃分成若干個簇(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和I^avlou提出了基於位置預測的簇首選擇算法。該算法中提出了 「虛簇」的概念，將整個網絡覆蓋區域劃分成多個「虛簇」區域，將每個節點同與其在同一個 「虛簇」內的其它節點進行比較，選擇所在「虛簇」概率最小或與當前「虛簇」中心的距離最短的節點作為簇首。節點可通過GPS或者其它定位方法獲取其地理信息，並確定所屬「虛簇」。該算法在節點移動性較弱時形成的簇結構穩定，且簇首數量較為固定，具有較好的性能。但是，在節點移動速度較高，拓撲變化快的網絡中形成的分簇結構不穩定，簇首變化頻率以及成員變化頻率較高。在VANET中，節點規模大，密度變化大，尤其在某些時候車輛跟駛，自然分成簇狀， 也適合採用分層的方法來進行數據廣播。但VANET是一種臨時性網絡，拓撲變化大，節點速度快，鏈路存在時間短，這些特點會影響到簇的結構。同時，簇的穩定性是分簇算法的一個重要問題，簇的變化不可避免，但應力求簇結構變化最小，算法應該能夠探測並應對拓撲結構的變化以保持合適的簇結構。此時若採用基於信息交換的方法來維護一個分層網絡需要通過定期廣播控制信息來維持，需要較大的控制開銷，從而增加了網絡負載。傳統的VANET分簇算法一般針對影響分簇結構的連通性、穩定性、負載平衡等因素中的某一個因素來進行，而不考慮影響分簇的其它方面。
發明內容
本發明的目的是提供一種考慮車輛交通特性的VANET分簇方法，以解決車載無線自組網傳統的分簇算法針對影響分簇結構的連通性、穩定性、負載平衡等因素中的某一個因素來進行，而不考慮影響分簇的其它方面的缺點。本發明包括下述步驟一、車載無線自組網中的節點分為多個組，每個組內的所有節點構成一個簇；二、確定每個簇中的簇首節點；三、確定每兩個相鄰簇的網關節點；第二步驟中確定每個簇中簇首節點的方法如下綜合考慮節點的位置、速度、連通和行駛行為，選擇簇首節點的權計算公式如下Wi = w1Ci+w2Di+w3Vi+w4Li(4-2)式中Ci——連通度分量，用於表示節點的連通狀況；Di——距離分量，表示節點與鄰居節點距離的平均值；Vi——綜合權的速度分量，表示節點速度與其鄰居平均速度的差值；Li——節點i的行駛車道分量，即根據節點行駛規則設計的加權項，表示節點行駛車道與基準車道號差值；其中，取Ci= Ni-S |，其中，Ni為節點i的鄰居個數，即實際連通度，δ為理想連通度；S值按下面公式計算δ = 2RtX133Xm/1000(4-3)其中Rt——節點傳輸距離；m——公路的車道數；Di通過下面公式計算
權利要求
1.考慮車輛交通特性的VANET分簇方法，它包括下述步驟一、車載無線自組網中的節點分為多個組，每個組內的所有節點構成一個簇；二、確定每個簇中的簇首節點；三、確定每兩個相鄰簇的網關節點；其特徵在於第二步驟中確定每個簇中簇首節點的方法如下綜合考慮節點的位置、速度、連通和行駛行為，選擇簇首節點的權計算公式如下 Wi = w1Ci+w2Di+w3Vi+w4Li(4-2)式中Ci——連通度分量，用於表示節點的連通狀況； Di——距離分量，表示節點與鄰居節點距離的平均值； Vi——綜合權的速度分量，表示節點速度與其鄰居平均速度的差值； Li——節點i的行駛車道分量，即根據節點行駛規則設計的加權項，表示節點行駛車道與基準車道號差值；其中，取Ci= I Ni-δ I，其中，Ni為節點i的鄰居個數，即實際連通度，δ為理想連通度； δ值按下面公式計算δ = 2RtX133Xm/1000(4-3)其中Rt——節點傳輸距離； m——公路的車道數； Di通過下面公式計算D1 =^fjDistiiJ)(4-4)n M其中Dist (i，j)—節點i到節點j的距離； η——節點的鄰居數； Vi通過下面公式計算(4-5)其中Vi——節點i的速度； V——鄰節點平均速度，其值按公式(4-6)計算V=-YjVj(4-6)η產ι車道分量Li通過下面公式計算 Li=Ili-LsI(4-7)其中Ii——節點所行駛的車道號； Ls——基準車道號；通過Ii與Ls求差來確定節點處於正常車道的機會大小；W1 W4是每個分量的係數，用以調節每個分量在綜合權值中的比重，應滿足 w1+w2+w3+w4 = 1,0 ^ w1 w2, W3 W4 ^ 1。
2.根據權利要求1所述的考慮車輛交通特性的VANET分簇方法，其特徵在於步驟二中簇首節點不保存成員列表，只由成員記錄簇首ID，表示其與這個簇的歸屬性。
3.根據權利要求1所述的考慮車輛交通特性的VANET分簇方法，其特徵在於分簇過程中使用了七種數據包，具體如下廣播數據包指承載著實際廣播消息內容的數據包，由包頭和數據區組成，在包頭中定義包ID、發起節點ID、上一跳ID、頭ID和包生成時間；節點信息交換包用以在發起簇建立，交換節點信息的數據包，內容包括節點的速度、位置、車道號；簇首聲明包節點在認為自己具有較小權值時發此包向其鄰居聲明自己的權值，收到簇首聲明包的節點若具有更小的權值也發簇首聲明包表示異議；頭維持包節點在被選舉成頭節點後發送此包以表明自己為頭節點，並在監測自身狀態認為自己仍為簇首後定期發送；收到頭維持包的節點成為該簇的成員；網關維持包節點在成為網關後發送此包以告訴自己鄰居自己連接的二個簇首中間已有網關；收到網關維持包的節點收到二個簇首的頭維持包後也不競爭網關；網關辭職包網關節點無法輪流收到兩個簇首的頭維持包時，即認為自己不適合再作網關，此時發網關辭職包以告訴周圍節點可以競爭網關。分布式網關詢問包節點在需要建立分布式網關時發此包以尋找配對網關，其內容包括節點ID和頭ID。
4.根據權利要求3所述的考慮車輛交通特性的VANET分簇方法，其特徵在於第一步驟中簇建立可由任意節點發起，通過在鄰節點間發送節點信息交換包來交換速度、位置、車道信息計算本節點的綜合權，並以此進行簇首選舉；當節點計算自己的權後認為自己的權較小，則發簇首聲明包，每個收到簇首聲明包的節點從中提取聲明包裡的權值，並與自己權值進行比較，若自己權值更小，則發簇首聲明包以表示異議，否則不再發聲明包，等待其它節點發頭維持包；發出頭聲明包的節點等待一定時間後未收到異議聲明，則發頭維持包表示自己是簇首；收到此頭維持包的節點即為該簇的成員，並記該節點ID為自己的頭節點；第一個收到兩個簇首頭維持包的節點發網關維持包聲明自己為網關節點。
5.根據權利要求3所述的考慮車輛交通特性的VANET分簇方法，其特徵在於在一輪簇選舉結束後在某節點恰好未被任何簇首覆蓋，且其權值大於某些已成為成員的鄰節點，則在這些節點間重選簇首。
6.根據權利要求3所述的考慮車輛交通特性的VANET分簇方法，其特徵在於在一輪簇首選舉後形成的兩個相鄰簇首覆蓋無重疊區域或其重疊區域內無節點，則採用分布式網關來連接兩個簇；若節點在成為成員Tg時間後仍未收到任何有效的網關維持包聲明，即其周圍無網關，則發分布式網關詢問包包尋找配對網關，第一個聽到此消息的非同簇節點回應此網關維持包與之形成配對的分布式網關；其中Tg用來控制節點的等待時長，以使處於簇首節點覆蓋邊緣的節點發分布式網關詢問包，形成連通的網絡。
全文摘要
考慮車輛交通特性的VANET分簇方法，本發明涉及車載無線自組網的分簇方法。它解決了車載無線自組網傳統的分簇算法針對影響分簇結構的連通性、穩定性、負載平衡等因素中的某一個因素來進行，而不考慮影響分簇的其它方面的缺點。本發明包括下述步驟1、車載無線自組網中的節點分為多個組，每個組內的所有節點構成一個簇；2、確定每個簇中的簇首節點；3、確定每兩個相鄰簇的網關節點；第二步驟中確定每個簇中簇首節點的方法如下綜合考慮節點的位置、速度、連通和行駛行為，選擇簇首節點的權計算公式如下Wi＝w1Ci+w2Di+w3Vi+w4Li。
文檔編號H04W84/18GK102307373SQ20111024347
公開日2012年1月4日 申請日期2011年8月23日 優先權日2011年8月23日
發明者付忠傳, 劉永文, 周連科, 崔剛, 張必英, 張策, 暴建民, 朱東傑, 王秀峰, 莫毓昌 申請人:哈爾濱工業大學