基于城市道路的穩(wěn)定車載網分簇路由的設計案例

1、基于城市道路的穩(wěn)定車載網分簇路由的設計案例1 引言車載自組網【1】（VANET，Vehicular Ad-Hoc Network）是一種特殊形式的移動自組網（MANET，Mobile Ad Hoc Networks），通過車輛裝載的無線通信設備，在車輛和車輛間、車輛與路邊基礎設施間有效地形成一種高動態(tài)的網絡系統。VANET具有節(jié)點移動速度快且分布不均勻、無線鏈路不穩(wěn)定、網絡拓撲變化頻繁等特點。根據文獻可知，由車載網絡轉發(fā)策略的不同，可以將車載網路由協議分為基于拓撲的路由協議（TBR）、基于地理位置的路由協議（PBR）以及分級路由協議（HRP）?；诜旨壍穆酚蓞f議可以將整個無中心控制的高動態(tài)網絡

2、轉變?yōu)橐粋€受中心控制的高動態(tài)網絡，能夠有效地增強網絡管理性，降低路由開銷；但在分級路由協議，高速移動車輛節(jié)點的簇結構比較不穩(wěn)定，需要頻繁地進行簇結構的維護，而這樣容易造成節(jié)點的數據傳輸受到嚴重影響。針對上述分層路由協議存在的問題，并結合文獻的觀點，本文提出了一種基于車輛運動方向和地理位置的穩(wěn)定的分簇路由協議（SCR）。SCR協議繼承了基于地理位置的路由協議和分級路由協議的優(yōu)點，通過改善成簇算法，增強了簇結構的穩(wěn)定性；利用相對速度理論，結合車輛位置服務系統，將車輛通過速度和方向估算聚集成簇，進而有效地提高整體網絡的性能。通過分析文獻中路由策略的可行性，發(fā)現其在一定道路條件受限，通過改進其路由算法

3、，有效地解決了岔路口路由冗余問題，使得SCR更好地適應于VANET。2 SCR協議假設條件：a：車輛均裝載GPS設備，可以隨時準確地知道自己的地理位置坐標；b：車輛均可快速地通過速度儀表確定當前行駛速度；c：車輛均裝載全向無線傳輸設備，可接受任何方向信號；d：車輛通信半徑為R。整個SCR協議由成簇路由協議和路由轉發(fā)協議這2部分構成，下面將對各部分進行具體論述。2.1 成簇路由協議在SCR協議中，節(jié)點包括：簇頭節(jié)點、輔簇頭節(jié)點、簇成員節(jié)點和網關。簇頭的職責在于對簇內成員的管理、簇間路由的維護以及簇間數據的傳輸；輔簇頭是簇內的備用簇頭節(jié)點，在簇頭有效期內發(fā)生突變或離簇時，主動廣播自身節(jié)點成為簇頭；

4、簇成員負責簇內路由的維護；不同簇的相交節(jié)點形成網關，實現簇間互連及通信。SCR的成簇路由協議具有2項工作：簇的構建和簇的維護。簇的構建主要負責簇頭、簇成員、網關的確定和簇的形成；簇的維護工作主要負責簇成員的入簇和離簇、簇頭突變時輔簇頭的選取建立以及簇內成員節(jié)點信息的管理。（1）簇的構建在道路環(huán)境下，為了提高簇結構的穩(wěn)定性，根據車輛節(jié)點的位置信息、行駛方向及速度將車輛節(jié)點分離聚合成多個簇。成簇模型如圖1所示：圖1 成簇模型由圖1可知，道路車輛節(jié)點被分隔為多個簇，簇內節(jié)點數量受限于車輛地理位置及行駛速度。在SCR協議中，臨時簇頭通過節(jié)點權值大小選擇，節(jié)點通過周期廣播節(jié)點信息得到鄰居節(jié)點狀態(tài)信息，若

5、節(jié)點自身行駛速度趨于最接近鄰居車輛節(jié)點的平均速度，則確認自己成為臨時簇頭；若同時存在多個相同狀態(tài)的節(jié)點，則最靠近鄰居車輛中心位置的車輛成為臨時簇頭（標記為CH0）。節(jié)點權值計算公式如下：（1）其中，vmax為車道車輛最大限速；vi為此節(jié)點速度；vj為鄰居節(jié)點速度；Ni為鄰居節(jié)點數量。（2）簇頭的選舉與維護選擇盡量遠離前進方向的岔路口節(jié)點作為簇頭的節(jié)點，避免簇頭的岔路口轉向造成簇的重組。整個選舉過程如下：1）臨時簇頭CH0向鄰居節(jié)點廣播Lead0（c，loc，D，V，）數據包，其中c表示簇標號，loc表示地理位置坐標，D表示行駛方向，V表示速度值，表示鄰居節(jié)點平均速度。2）時間t0內如果CH0收

6、到來自其它鄰居節(jié)點B的Reply（loc，D，V）數據包，則表示節(jié)點B更適合成為簇頭，CH0自動放棄簇頭競選，并記錄B信息到簇頭路由表中；否則，CH0向全網廣播自己成為簇頭CH，向全網廣播Lead（c，loc，D，V）數據包，此時簇頭的同向鄰居節(jié)點依據自身運動狀態(tài)加入到簇內成為簇成員，簇頭通過簇成員協調獲取鄰簇頭信息并記錄于簇頭路由表中。3）某節(jié)點A長時間未收到Lead數據包或Lead0數據包，則它向全網廣播Apply（locA，D，V）消息，時間t內如果收到任何簇頭CH的相應信息Lead（c，loc，D，V），則節(jié)點A加入到CH中，并將簇頭信息記錄路由表中；否則，它考慮自己成為臨簇頭，重復步

7、驟1）。4）當簇頭CH離開時，如果此時路段為非交叉路段，它將通過查詢路由表獲取式（1）中權值最優(yōu)節(jié)點ECH（輔簇頭），向ECH發(fā)送路由表信息，并向全網廣播Leave0（c，loc，D，V）消息。ECH收到消息后代替CH地位自動成為簇頭，并將收到的路由信息記錄自己路由表中；簇成員收到Leave0消息后自動更新路由信息，標記ECH為簇頭。如果此路段為交叉路段，則簇頭CH將直接廣播Leave（c，loc）信息，簇內節(jié)點收到消息后直接進行簇的重建。簇頭選舉結束后，每個簇頭均擁有自己所處簇信息、簇成員信息以及鄰居簇頭信息，簇成員節(jié)點記憶所屬簇信息及該簇內簇頭信息。2.2 路由轉發(fā)協議如果源節(jié)點S需要發(fā)送

8、數據包到目的節(jié)點D，S首先通過路由表查詢確認D是否為自己臨節(jié)點，如果是則S直接發(fā)送數據包到D；否則，S向自身所在簇內簇頭詢問節(jié)點D是否為簇內成員，如果是則通過簇頭轉發(fā)數據到D；否則，S進行簇間路由發(fā)現過程，發(fā)送RREQ請求數據包到簇頭，簇頭根據發(fā)送數據包方向定義方向矢量DSD，并根據DSD選擇最優(yōu)鄰簇頭，進行簇間數據轉發(fā)。在簇間數據轉發(fā)階段，為避免受道路周邊建筑影響在路由選擇中發(fā)生路由環(huán)路和路由冗余現象，簇首首先檢查自己的地理位置，如果位于岔路口，則通過改進的受限貪婪轉發(fā)算法進行下一跳鄰簇頭的選擇；否則，節(jié)點將根據矢量方向通過貪婪算法轉發(fā)數據。當下一跳簇頭接收到數據包后，檢查D是否為簇內節(jié)點，

9、如果是則直接將數據包轉發(fā)到D；否則，簇頭將數據包存儲路由中，并重復上述步驟尋找下一跳路由，直到TTL（路由轉發(fā)有效時間）為0時丟棄。在數據轉發(fā)過程中，由于車輛節(jié)點的高速運動，造成數據包轉發(fā)至目的節(jié)點所處地理位置時，目的節(jié)點可能已經離開源節(jié)點獲取的原有地理位置。假設目的節(jié)點前向簇頭節(jié)點（即路由最后一跳發(fā)起者）為a，此時a根據目的節(jié)點的移動方向，進行不大于2跳的小范圍洪泛。通過此方法，可使數據包有效地發(fā)送至目的節(jié)點。為了降低路由開銷，減少數據轉發(fā)所需時間，下一跳鄰簇頭的選擇十分重要，可利用路段場景和交叉路口場景下的不同特點，結合矢量DSD，通過分析貪婪算法，對貪婪轉發(fā)算法進行改進。具體如下：（1）

10、傳統的貪婪轉發(fā)算法傳統的貪婪轉發(fā)算法在一定場景模式下，容易造成路由路徑的冗余，如圖2所示。假設圖中節(jié)點均代表各個簇頭節(jié)點，當簇間信息轉發(fā)時，節(jié)點u需要將數據發(fā)送到節(jié)點d。由貪婪算法可得，節(jié)點u將選擇距離d較近的1a作為下一跳，之后1a又轉發(fā)給b，此時出現局部最優(yōu)現象，b發(fā)現相對鄰簇頭其距離目的節(jié)點更近，此時轉發(fā)模式轉換為周邊轉發(fā)，選擇節(jié)點2a作為下一跳，再次通過貪婪算法選擇節(jié)點c，最后轉發(fā)到目的節(jié)點d。如果源節(jié)點u直接選擇2a作為下一跳，將避免后續(xù)的冗余路由。（2）改進的貪婪轉發(fā)算法新協議中提出了一種受限的貪婪轉發(fā)算法，路段場景下仍采用傳統的貪婪算法，而岔路口場景下節(jié)點優(yōu)先選擇岔路中位置節(jié)點作

11、為下一跳，然后此節(jié)點優(yōu)先決定路由轉發(fā)的路段方向，再在此方向路段尋找最優(yōu)下一跳節(jié)點。下一跳節(jié)點收到轉發(fā)數據包，首先判斷其與目的節(jié)點的地理位置，若處于同一方向路段，則進行貪婪轉發(fā)，不再刻意選擇岔路口節(jié)點，如圖3（a）所示。假設圖中節(jié)點均代表簇頭節(jié)點，簇頭u向目的簇頭d轉發(fā)數據包，u根據位置服務可知其與d位于同一方向路段，此時直接跳過岔路口節(jié)點進行數據包轉發(fā)，通過貪婪轉發(fā)數據包至節(jié)點a，直到目的簇頭節(jié)點d收到信息；否則，優(yōu)先將數據包轉發(fā)到岔路中節(jié)點，在此節(jié)點先進行支路方向選擇，再選擇下一跳路由。在岔路口路由選擇時，考慮到車輛運動軌跡受限、行駛速度快、運動狀態(tài)可預判等因素，因此將方向作為路由選擇條件來

12、降低路由跳數，實際場景如圖3（b）所示。假設圖中節(jié)點均代表簇頭節(jié)點，簇頭u向目的簇頭d轉發(fā)數據包，u通過判斷發(fā)現與d不在同一方向路段，其簇頭路由表中存在a1、a2等節(jié)點，而a1為岔路口節(jié)點，此時即使a2距離目的簇頭節(jié)點更近，也不選擇其作為下一跳，而選擇岔路口節(jié)點a1作為下一跳，此時a1通過與目的節(jié)點坐標結合，在不同岔路方向映射節(jié)點a1和a1，通過位置服務判斷與d方向路段一致或距離更近的映射節(jié)點岔路方向為最優(yōu)路段，再通過貪婪算法在此路段進行下一跳節(jié)點選擇，重復上述步驟直到數據包轉發(fā)至d。新協議的完整路由策略是：當數據包轉發(fā)至岔路口節(jié)點時，先檢查目的節(jié)點是否存在其鄰居表內，如果存在則直接轉發(fā)目的節(jié)

13、點；否則，判斷目標節(jié)點是否與自己處于同一方向路段，如果處于同一方向路段，則直接通過貪婪轉發(fā)尋找距離目的節(jié)點最近節(jié)點作為下一跳；如果通過位置服務判斷自身節(jié)點與目的節(jié)點不在同一路段，則優(yōu)先將數據包轉發(fā)給岔路中節(jié)點，通過岔路中節(jié)點與目的節(jié)點的地理位置信息，在不同岔路口方向進行基于目的節(jié)點的節(jié)點位置映射，優(yōu)先選擇映射節(jié)點與目的節(jié)點在同一方向路段或距離最近的路段作為最優(yōu)轉發(fā)支路，然后在此支路方向選擇適當的下一跳路由，重復上述步驟直到數據包轉發(fā)至目的節(jié)點。當進行數據轉發(fā)節(jié)點在其通信范圍內找不到合適下一跳節(jié)點時，暫時緩存數據分組，發(fā)現合適下一跳節(jié)點后再將數據轉發(fā)。這一策略不同于其它路由策略，在岔路口必須優(yōu)先

14、進行最優(yōu)支路選擇，再進行最近節(jié)點選擇，這樣可有效地避免路由冗余，縮短路由跳數，提高路由效率。（a）直線路段轉發(fā)模式 （b）交叉路段轉發(fā)模式圖3 SCR路由轉發(fā)模式3 仿真結果及分析3.1 仿真環(huán)境該仿真由仿真軟件VanetMobiSim和NS-2.35組成，在4條縱橫交錯道路場景下進行，大小為2 400m*2 400m，各道路中車輛節(jié)點隨機分布，節(jié)點通信半徑為250m。3.2 仿真結果分析為了觀察SCR路由協議的性能，本仿真通過與AODV、GPRS這2種典型的車載網路由協議進行對比分析。為了評估SCR路由策略對車輛節(jié)點密度的適應性，在仿真場景分別設置3080個節(jié)點進行仿真。同樣地，為了評估SC

15、R路由策略對節(jié)點運行速度的適應性，節(jié)點速度選取2050m/s。所有實驗數據以10次重復仿真測試后的平均值為準。圖4展現了節(jié)點數量變化和網絡的分組投遞率的關系。節(jié)點數量的增加導致路由控制信息的大幅增加，這勢必造成大量數據分組因超時遭到丟棄，從而影響整個網絡的分組投遞率。在AODV協議中，受到節(jié)點周期的路由維護修復策略，一定程度可使得分組投遞率提高，但同時也造成網絡開銷的加劇。在GPSR協議中，由于路由選擇過程并不考慮路徑連通性，且在岔路口容易造成環(huán)路現象，所以分組投遞率較低。在SCR協議中，由于岔路口路由選擇會優(yōu)先進行最佳方向路段選擇，再選取下一跳節(jié)點，且節(jié)點的數據暫存有效解決了網絡局部優(yōu)化帶來

16、的問題，所以SCR協議的網絡分組投遞率相對其它2種路由協議有較好的效果。圖4 節(jié)點的分組投遞率（v=30m/s）圖5展現了節(jié)點速度變化與網絡的分組投遞率的關系。AODV協議通過修復和重新建立路由，一定程度可使得分組投遞率得到提升。GPSR協議的路由策略由貪婪算法、邊界轉發(fā)模式來傳輸數據分組，不完善的路由策略使得傳輸路徑斷裂狀況下，數據分組頻繁被拋棄，導致網絡分組投遞率下降。SCR協議岔路口路段方向預測和局部優(yōu)化時的數據暫存策略，增強了網絡連通性，提升了分組投遞率。圖6展現了節(jié)點數量變化對網絡的平均時延的影響。當節(jié)點數量較小時，網絡鏈路容易斷鏈，導致數據延時較高；當節(jié)點數量較多時，路由控制信息的

17、大幅增加影響數據傳輸效率，致使數據轉發(fā)時延增加。AODV協議中，需要進行路由發(fā)現和路由維護工作，確認路徑后才進行數據轉發(fā)，導致網絡的平均延時較高。GPSR路由協議與SCR路由協議中，節(jié)點只需要根據鄰節(jié)點和目的節(jié)點位置信息進行路由決策，邊發(fā)現邊轉發(fā)的路由策略可有效降低網絡時延。但是在岔路口路段，GPSR協議容易造成路由冗余，而SCR協議優(yōu)先進行方向路段選擇，再進行路由下一跳選擇，降低了路由冗余現象的發(fā)生概率，所以SCR路由性能更好。圖6 平均延時圖7展現了路由跳數隨著傳輸距離增加的變化情況。在傳輸距離較短時，由于SCR基于簇頭進行數據轉發(fā)，不同簇間需要經過簇頭傳輸后才能到達，路由跳數相對其它2種

18、協議較高。當傳輸距離增加時，3種路由協議的路由跳數均相應增加。隨著傳輸距離的增加，GPSR協議在岔路口數據轉發(fā)時容易造成路由冗余，導致路由跳數大幅增加。SCR協議通過新的路由策略降低了路由冗余，使得路由跳數相應降低。AODV協議中，在數據傳輸時才進行路由發(fā)現，并將第一條響應鏈路作為數據傳輸路徑來保證路由跳數最少，所以平均路由跳數較少。圖7 平均路由跳數4 結束語本文通過分析VANET一些典型路由協議存在的問題，結合城市道路特點，提出了一種新的適用于城市道路車載網的穩(wěn)定分簇路由策略SCR。SCR協議通過節(jié)點的運動特征進行分簇，并通過提出的輔簇頭設計理念，避免簇頭在有效期內離簇后簇重組帶來的數據傳

19、輸問題。根據節(jié)點的地理位置服務信息和運動可預測性，提出了一種適用于車載網中岔路口數據轉發(fā)的路由策略。通過實驗仿真表明，SCR協議可使得簇結構的穩(wěn)定性得到增強，局部優(yōu)化現象帶來的路由冗余問題得到有效減少，端到端平均時延得到降低，分組投遞率得到提升，并有效地控制了路由跳數，能較好地適應VANET，尤其適用于城市場景中岔路口較多的道路環(huán)境。參考文獻：【1】 王芳. 車載自織網路由算法的研究. 桂林： 廣西師范大學， 2012.【2】 Bijan Paul， Md Ibrahim. Md Abu Naser Bikas. VANET Routing Protocols： Pros and Cons.

20、International Journal of Computer Applications， 2011，20（3）： 28-34.【3】 王昭然，謝顯中，趙鼎新. 車載自組織網絡關鍵技術. 電信學報， 2011（1）： 44-51.【4】 Sherali Zeadally， Ray Hunt. Vehicular Ad-hoc Networks （VANETS）： Status， Results， and Challenges. Tele Communication Systems， 2012，50： 217-241.【5】 Chou Chenming， Lan Kunchan. On the Formation of Vehicle Clusters. 2012 12th International Conference on ITS Telecommunications. Piscataway： IEEE Press， 2012： 574-578.【6】 K Naveen， Komathy Karuppanan. Mob