基于城市道路的穩定車載網分簇路由策略

衛鵬偉++何加銘++曾興斌

1 引言

車載自組網[1]（VANET，Vehicular Ad-Hoc Network）是一種特殊形式的移動自組網（MANET，Mobile Ad Hoc Networks），通過車輛裝載的無線通信設備，在車輛和車輛間、車輛與路邊基礎設施間有效地形成一種高動態的網絡系統。

VANET具有節點移動速度快且分布不均勻、無線鏈路不穩定、網絡拓撲變化頻繁等特點。根據文獻[2-4]可知，由車載網絡轉發策略的不同，可以將車載網路由協議分為基于拓撲的路由協議（TBR）、基于地理位置的路由協議（PBR）以及分級路由協議（HRP）。基于分級的路由協議可以將整個無中心控制的高動態網絡轉變為一個受中心控制的高動態網絡，能夠有效地增強網絡管理性，降低路由開銷；但在分級路由協議，高速移動車輛節點的簇結構比較不穩定，需要頻繁地進行簇結構的維護，而這樣容易造成節點的數據傳輸受到嚴重影響。

針對上述分層路由協議存在的問題，并結合文獻[5-7]的觀點，本文提出了一種基于車輛運動方向和地理位置的穩定的分簇路由協議（SCR）。SCR協議繼承了基于地理位置的路由協議和分級路由協議的優點，通過改善成簇算法，增強了簇結構的穩定性；利用相對速度理論，結合車輛位置服務系統，將車輛通過速度和方向估算聚集成簇，進而有效地提高整體網絡的性能。通過分析文獻[8]中路由策略的可行性，發現其在一定道路條件受限，通過改進其路由算法，有效地解決了岔路口路由冗余問題，使得SCR更好地適應于VANET。

2 SCR協議

假設條件：

a：車輛均裝載GPS設備，可以隨時準確地知道自己的地理位置坐標；

b：車輛均可快速地通過速度儀表確定當前行駛速度；

c：車輛均裝載全向無線傳輸設備，可接受任何方向信號；

d：車輛通信半徑為R。

整個SCR協議由成簇路由協議和路由轉發協議這2部分構成，下面將對各部分進行具體論述。

2.1 成簇路由協議

在SCR協議中，節點包括：簇頭節點、輔簇頭節點、簇成員節點和網關。簇頭的職責在于對簇內成員的管理、簇間路由的維護以及簇間數據的傳輸；輔簇頭是簇內的備用簇頭節點，在簇頭有效期內發生突變或離簇時，主動廣播自身節點成為簇頭；簇成員負責簇內路由的維護；不同簇的相交節點形成網關，實現簇間互連及通信。

SCR的成簇路由協議具有2項工作：簇的構建和簇的維護。簇的構建主要負責簇頭、簇成員、網關的確定和簇的形成；簇的維護工作主要負責簇成員的入簇和離簇、簇頭突變時輔簇頭的選取建立以及簇內成員節點信息的管理。

（1）簇的構建

在道路環境下，為了提高簇結構的穩定性，根據車輛節點的位置信息、行駛方向及速度將車輛節點分離聚合成多個簇。成簇模型如圖1所示：

圖1 成簇模型

由圖1可知，道路車輛節點被分隔為多個簇，簇內節點數量受限于車輛地理位置及行駛速度。

在SCR協議中，臨時簇頭通過節點權值大小選擇，節點通過周期廣播節點信息得到鄰居節點狀態信息，若節點自身行駛速度趨于最接近鄰居車輛節點的平均速度，則確認自己成為臨時簇頭；若同時存在多個相同狀態的節點，則最靠近鄰居車輛中心位置的車輛成為臨時簇頭（標記為CH0）。節點權值計算公式如下：

（1）

其中，vmax為車道車輛最大限速；vi為此節點速度；vj為鄰居節點速度；Ni為鄰居節點數量。

（2）簇頭的選舉與維護

選擇盡量遠離前進方向的岔路口節點作為簇頭的節點，避免簇頭的岔路口轉向造成簇的重組。整個選舉過程如下：

1）臨時簇頭CH0向鄰居節點廣播Lead0（c，loc，D，V，

）數據包，其中c表示簇標號，loc表示地理位置坐標，D表示行駛方向，V表示速度值，表示鄰居節點平均速度。

2）時間t0內如果CH0收到來自其它鄰居節點B的Reply（loc，D，V）數據包，則表示節點B更適合成為簇頭，CH0自動放棄簇頭競選，并記錄B信息到簇頭路由表中；否則，CH0向全網廣播自己成為簇頭CH，向全網廣播Lead（c，loc，D，V）數據包，此時簇頭的同向鄰居節點依據自身運動狀態加入到簇內成為簇成員，簇頭通過簇成員協調獲取鄰簇頭信息并記錄于簇頭路由表中。

3）某節點A長時間未收到Lead數據包或Lead0數據包，則它向全網廣播Apply（locA，D，V）消息，時間t內如果收到任何簇頭CH的相應信息Lead（c，loc，D，V），則節點A加入到CH中，并將簇頭信息記錄路由表中；否則，它考慮自己成為臨簇頭，重復步驟1）。

4）當簇頭CH離開時，如果此時路段為非交叉路段，它將通過查詢路由表獲取式（1）中權值最優節點ECH（輔簇頭），向ECH發送路由表信息，并向全網廣播Leave0（c，loc，D，V）消息。ECH收到消息后代替CH地位自動成為簇頭，并將收到的路由信息記錄自己路由表中；簇成員收到Leave0消息后自動更新路由信息，標記ECH為簇頭。如果此路段為交叉路段，則簇頭CH將直接廣播Leave（c，loc）信息，簇內節點收到消息后直接進行簇的重建。

簇頭選舉結束后，每個簇頭均擁有自己所處簇信息、簇成員信息以及鄰居簇頭信息，簇成員節點記憶所屬簇信息及該簇內簇頭信息。

2.2 路由轉發協議

如果源節點S需要發送數據包到目的節點D，S首先通過路由表查詢確認D是否為自己臨節點，如果是則S直接發送數據包到D；否則，S向自身所在簇內簇頭詢問節點D是否為簇內成員，如果是則通過簇頭轉發數據到D；否則，S進行簇間路由發現過程，發送RREQ請求數據包到簇頭，簇頭根據發送數據包方向定義方向矢量DSD，并根據DSD選擇最優鄰簇頭，進行簇間數據轉發。endprint

在簇間數據轉發階段，為避免受道路周邊建筑影響在路由選擇中發生路由環路和路由冗余現象，簇首首先檢查自己的地理位置，如果位于岔路口，則通過改進的受限貪婪轉發算法進行下一跳鄰簇頭的選擇；否則，節點將根據矢量方向通過貪婪算法轉發數據。當下一跳簇頭接收到數據包后，檢查D是否為簇內節點，如果是則直接將數據包轉發到D；否則，簇頭將數據包存儲路由中，并重復上述步驟尋找下一跳路由，直到TTL（路由轉發有效時間）為0時丟棄。

在數據轉發過程中，由于車輛節點的高速運動，造成數據包轉發至目的節點所處地理位置時，目的節點可能已經離開源節點獲取的原有地理位置。假設目的節點前向簇頭節點（即路由最后一跳發起者）為a，此時a根據目的節點的移動方向，進行不大于2跳的小范圍洪泛。通過此方法，可使數據包有效地發送至目的節點。

為了降低路由開銷，減少數據轉發所需時間，下一跳鄰簇頭的選擇十分重要，可利用路段場景和交叉路口場景下的不同特點，結合矢量DSD，通過分析貪婪算法，對貪婪轉發算法進行改進。具體如下：

（1）傳統的貪婪轉發算法

傳統的貪婪轉發算法在一定場景模式下，容易造成路由路徑的冗余[8-9]，如圖2所示。假設圖中節點均代表各個簇頭節點，當簇間信息轉發時，節點u需要將數據發送到節點d。由貪婪算法可得，節點u將選擇距離d較近的1a作為下一跳，之后1a又轉發給b，此時出現局部最優現象，b發現相對鄰簇頭其距離目的節點更近，此時轉發模式轉換為周邊轉發，選擇節點2a作為下一跳，再次通過貪婪算法選擇節點c，最后轉發到目的節點d。如果源節點u直接選擇2a作為下一跳，將避免后續的冗余路由。

（2）改進的貪婪轉發算法

新協議中提出了一種受限的貪婪轉發算法，路段場景下仍采用傳統的貪婪算法，而岔路口場景下節點優先選擇岔路中位置節點作為下一跳，然后此節點優先決定路由轉發的路段方向，再在此方向路段尋找最優下一跳節點。

下一跳節點收到轉發數據包，首先判斷其與目的節點的地理位置，若處于同一方向路段，則進行貪婪轉發，不再刻意選擇岔路口節點，如圖3（a）所示。假設圖中節點均代表簇頭節點，簇頭u向目的簇頭d轉發數據包，u根據位置服務可知其與d位于同一方向路段，此時直接跳過岔路口節點進行數據包轉發，通過貪婪轉發數據包至節點a，直到目的簇頭節點d收到信息；否則，優先將數據包轉發到岔路中節點，在此節點先進行支路方向選擇，再選擇下一跳路由。

在岔路口路由選擇時，考慮到車輛運動軌跡受限、行駛速度快、運動狀態可預判等因素，因此將方向作為路由選擇條件來降低路由跳數，實際場景如圖3（b）所示。假設圖中節點均代表簇頭節點，簇頭u向目的簇頭d轉發數據包，u通過判斷發現與d不在同一方向路段，其簇頭路由表中存在a1、a2等節點，而a1為岔路口節點，此時即使a2距離目的簇頭節點更近，也不選擇其作為下一跳，而選擇岔路口節點a1作為下一跳，此時a1通過與目的節點坐標結合，在不同岔路方向映射節點a1和a1，通過位置服務判斷與d方向路段一致或距離更近的映射節點岔路方向為最優路段，再通過貪婪算法在此路段進行下一跳節點選擇，重復上述步驟直到數據包轉發至d。

新協議的完整路由策略是：當數據包轉發至岔路口節點時，先檢查目的節點是否存在其鄰居表內，如果存在則直接轉發目的節點；否則，判斷目標節點是否與自己處于同一方向路段，如果處于同一方向路段，則直接通過貪婪轉發尋找距離目的節點最近節點作為下一跳；如果通過位置服務判斷自身節點與目的節點不在同一路段，則優先將數據包轉發給岔路中節點，通過岔路中節點與目的節點的地理位置信息，在不同岔路口方向進行基于目的節點的節點位置映射，優先選擇映射節點與目的節點在同一方向路段或距離最近的路段作為最優轉發支路，然后在此支路方向選擇適當的下一跳路由，重復上述步驟直到數據包轉發至目的節點。當進行數據轉發節點在其通信范圍內找不到合適下一跳節點時，暫時緩存數據分組，發現合適下一跳節點后再將數據轉發。這一策略不同于其它路由策略，在岔路口必須優先進行最優支路選擇，再進行最近節點選擇，這樣可有效地避免路由冗余，縮短路由跳數，提高路由效率。

（a）直線路段轉發模式 （b）交叉路段轉發模式

圖3 SCR路由轉發模式

3 仿真結果及分析

3.1 仿真環境

該仿真由仿真軟件VanetMobiSim[10]和NS-2.35[11]組成，在4條縱橫交錯道路場景下進行，大小為2 400m*2 400m，各道路中車輛節點隨機分布，節點通信半徑為250m。

3.2 仿真結果分析

為了觀察SCR路由協議的性能，本仿真通過與AODV[12]、GPRS[13-14]這2種典型的車載網路由協議進行對比分析。為了評估SCR路由策略對車輛節點密度的適應性，在仿真場景分別設置30～80個節點進行仿真。同樣地，為了評估SCR路由策略對節點運行速度的適應性，節點速度選取20～50m/s。所有實驗數據以10次重復仿真測試后的平均值為準。

圖4展現了節點數量變化和網絡的分組投遞率的關系。節點數量的增加導致路由控制信息的大幅增加，這勢必造成大量數據分組因超時遭到丟棄，從而影響整個網絡的分組投遞率。在AODV協議中，受到節點周期的路由維護修復策略，一定程度可使得分組投遞率提高，但同時也造成網絡開銷的加劇。在GPSR協議中，由于路由選擇過程并不考慮路徑連通性，且在岔路口容易造成環路現象，所以分組投遞率較低。在SCR協議中，由于岔路口路由選擇會優先進行最佳方向路段選擇，再選取下一跳節點，且節點的數據暫存有效解決了網絡局部優化帶來的問題，所以SCR協議的網絡分組投遞率相對其它2種路由協議有較好的效果。

圖4 節點的分組投遞率（v=30m/s）

圖5展現了節點速度變化與網絡的分組投遞率的關系。AODV協議通過修復和重新建立路由，一定程度可使得分組投遞率得到提升。GPSR協議的路由策略由貪婪算法、邊界轉發模式來傳輸數據分組，不完善的路由策略使得傳輸路徑斷裂狀況下，數據分組頻繁被拋棄，導致網絡分組投遞率下降。SCR協議岔路口路段方向預測和局部優化時的數據暫存策略，增強了網絡連通性，提升了分組投遞率。endprint

圖5 50個節點分組投遞率

圖6展現了節點數量變化對網絡的平均時延的影響。當節點數量較小時，網絡鏈路容易斷鏈，導致數據延時較高；當節點數量較多時，路由控制信息的大幅增加影響數據傳輸效率，致使數據轉發時延增加。AODV協議中，需要進行路由發現和路由維護工作，確認路徑后才進行數據轉發，導致網絡的平均延時較高。GPSR路由協議與SCR路由協議中，節點只需要根據鄰節點和目的節點位置信息進行路由決策，邊發現邊轉發的路由策略可有效降低網絡時延。但是在岔路口路段，GPSR協議容易造成路由冗余，而SCR協議優先進行方向路段選擇，再進行路由下一跳選擇，降低了路由冗余現象的發生概率，所以SCR路由性能更好。

圖6 平均延時

圖7展現了路由跳數隨著傳輸距離增加的變化情況。在傳輸距離較短時，由于SCR基于簇頭進行數據轉發，不同簇間需要經過簇頭傳輸后才能到達，路由跳數相對其它2種協議較高。當傳輸距離增加時，3種路由協議的路由跳數均相應增加。隨著傳輸距離的增加，GPSR協議在岔路口數據轉發時容易造成路由冗余，導致路由跳數大幅增加。SCR協議通過新的路由策略降低了路由冗余，使得路由跳數相應降低。AODV協議中，在數據傳輸時才進行路由發現，并將第一條響應鏈路作為數據傳輸路徑來保證路由跳數最少，所以平均路由跳數較少。

圖7 平均路由跳數

4 結束語

本文通過分析VANET一些典型路由協議存在的問題，結合城市道路特點，提出了一種新的適用于城市道路車載網的穩定分簇路由策略SCR。SCR協議通過節點的運動特征進行分簇，并通過提出的輔簇頭設計理念，避免簇頭在有效期內離簇后簇重組帶來的數據傳輸問題。根據節點的地理位置服務信息和運動可預測性，提出了一種適用于車載網中岔路口數據轉發的路由策略。通過實驗仿真表明，SCR協議可使得簇結構的穩定性得到增強，局部優化現象帶來的路由冗余問題得到有效減少，端到端平均時延得到降低，分組投遞率得到提升，并有效地控制了路由跳數，能較好地適應VANET，尤其適用于城市場景中岔路口較多的道路環境。

參考文獻：

[1] 王芳. 車載自織網路由算法的研究[D]. 桂林： 廣西師范大學， 2012.

[2] Bijan Paul， Md Ibrahim. Md Abu Naser Bikas. VANET Routing Protocols： Pros and Cons[J]. International Journal of Computer Applications， 2011，20（3）： 28-34.

[3] 王昭然，謝顯中，趙鼎新. 車載自組織網絡關鍵技術[J]. 電信學報， 2011（1）： 44-51.

[4] Sherali Zeadally， Ray Hunt. Vehicular Ad-hoc Networks （VANETS）： Status， Results， and Challenges[J]. Tele Communication Systems， 2012，50： 217-241.

[5] Chou Chenming， Lan Kunchan. On the Formation of Vehicle Clusters[A]. 2012 12th International Conference on ITS Telecommunications[C]. Piscataway： IEEE Press， 2012： 574-578.

[6] K Naveen， Komathy Karuppanan. Mobile Cluster Assisted Routing for Urban VANET[A]. Chennai， Recent Trends in Information Technology （ICRTIT）， 2011 International Conference on[C]. Piscataway： IEEE Press， 2011： 296-300.

[7] Song TaoXia Weiwei. A Cluster-Based Directional Routing Protocol in VANET[A]. Nanjing， Communication Technology （ICCT）， 2010 12th IEEE International Conference on[C]. Piscataway： IEEE Press， 2010： 1172-1175.

[8] 陳軍，徐笛，李式巨，等. 一種穩健的城市場景車載Ad Hoc路由策略[J]. 電子與信息學報， 2007，29（11）： 2555-2559.

[9] 胡淼，李劍峰. 車載自組織網絡中基于貪婪算法的地理位置路由[J]. 中興通訊技術， 2011，17（3）： 24-28.

[10] Harri J， Filali F， Bonnet C. VanetMobiSim： Generating Realistic Mobility Patterns for VANETs[A]. Proceedings of the 3rd International Workshop on Vehicular Ad Hoc Networks[C]. 2006.

[11] 于斌，孫斌，溫暖，等. NS2與網絡模擬[M]. 北京： 人民郵電出版社， 2007.

[12] Yu Xi， Guo Huaqun， Wong Waichoong. A Reliable Routing Protocol for VANET Communications[A]. Istanbul， Wireless Communications and Mobile Computing Conference （IWCMC）， 2011 7th International[C]. Piscataway： IEEE Press， 2011： 1748-1753.

[13] Karp B， Kung H T. GPSR： Greedy Perimeter Stateless Routing for Wireless Networks[A]. Proe of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking[C]. 2000.

[14] Hu Lili， Ding Zhizhong， Shi Huijing. An Improved GPSR Routing Strategy in VANETs[A]. Shanghai， Wireless Communications， Networking and Mobile Computing （WiCOM）， 2012 8th International Conference on[C]. Piscataway： IEEE Press， 2012： 1-4.endprint