0 引言

    車輛自組織網絡(Vehicular Ad Hoc Networks，VANETs)是移動自組織網絡(Mobile Ad Hhoc Networks，MANETs）的一種，由移動的車輛作為節點進行組網并實現無線通信，在城市交通領域得到廣泛應用^[1]。由于車輛高速移動的特性，車輛自組織網絡的拓撲結構變化快，路由協議的設計值得深入研究。目前，車輛自組織網絡常用的路由協議可以分為三類：按需路由協議、主動路由協議和混合路由協議^[2-6]。按需路由協議是基于路由的需求來進行路由查找的路由協議，如AODV（Ad Hoc On-demand Distance Vector Routing）路由協議^[7]，這類路由協議開銷較小，但是存在輸出傳輸延遲大的問題。主動路由協議要求網絡中的每一個節點都參與維護路由表，可以降低數據傳輸延遲，但是路由開銷較大，如DSDV（Destination-Sequenced Distance Vector）路由協議^[8]。混合路由協議結合前兩類路由協議的優點，在區域內使用主動路由方式選擇路由，避免按需路由中的延遲問題；在區域間使用按需路由協議，降低主動路由的開銷。常用的區域路由協議由三部分組成：區域內路由協議（IntrA-zone Routing Protocol，IARP）、區域間路由協議（IntErzone Routing Protocol，IERP）和邊界廣播協議（Bordercast Resolution Protocol，BPR），其中IARP是一個跳數受限的主動路由協議，IERP是按需路由協議，BPR負責轉發IERP的路由請求到外圍節點。區域路由協議通過在兩種主動路由協議和按需路由協議之間進行切換，不僅可以減少控制開銷，還能最大限度地減少端到端延遲^[9-13]。因此，在大型城市交通應用場合，采用區域路由協議可以更好地利用有限的網絡資源和高效傳輸數據。文獻[14]將區域路由協議和公交車骨干網相結合，采用改進的區域路由協議實現數據傳輸，能有效降低車輛自組織網絡數據擁堵的問題。但是該路由協議在簇外路由發現部分還存在大量的冗余通信，增加了路由開銷。為了降低路由開銷，本文在文獻[14]所述路由協議的基礎上，提出了一種基于公交車骨干網的改進區域路由協議。設計思想是依據目的節點和簇頭節點的位置信息，構建簇外路由發現階段外圍節點的約束方程，剔除與目的節點不在同一側的外圍節點的冗余通信，降低路由開銷，改善路由性能。

1 面向公交車骨干網的區域路由協議

    文獻[14]提出一種面向公交車骨干網的區域路由協議，將城市交通環境中的所有公交車節點連接成一個骨干網，以公交車節點作為簇頭，其他車輛節點作為簇成員，采用改進的區域路由協議進行數據通信。首先，將分簇思想引入到區域路由協議中，以作為簇頭的公交車節點生成域，構建半徑為3跳的區域（即區域內外圍節點到中心節點的距離不超過3跳）。在區域內采用主動路由協議構建路由，區域內的每個節點維護一個公共的路由表。在區域外使用按需路由協議構建路由，根據路由請求建立路由，主要包括路由發現、路由優化和路由維護三部分。

    （1）路由發現

    路由發現分為三個層次，分別是自身區域內發現、簇區域內發現和簇外發現。源節點想要發送數據給目的節點時，首先在自身區域（也即1跳區域）內發現是否存在目的節點，如果存在，則直接建立源節點到目的節點的路由。如果不存在，且在簇區域內發現，也即源節點將路由請求信息發送給其所在區域的簇頭節點，由簇頭節點檢查其所在簇區域（也即以簇頭節點為中心的3跳區域）內是否存在目的節點。如果存在，則將響應信息返回給源節點。否則，再進行簇外發現，具體是由簇頭節點將源節點的路由請求信息發送給本區域的外圍節點，再由外圍節點將信息轉發給相交的簇區域的簇頭節點。由該簇頭節點繼續執行簇區域內發現過程，如果找多目標節點，則按原路向源節點返回路由響應消息。否則，繼續簇外發現過程，通過重復簇區域內發現和簇外發現兩個過程，直至找到目的節點，將路由響應消息返回給源節點。

    （2）路由優化

    文獻[14]所述的路由優化過程實質上是一種路由篩選過程。對于路由發現階段建立的路由，文獻[14]以路徑最短為選擇標準，從源節點到目的節點構建的多條路由中選擇最優的路由。針對路由發現階段的三個層次，路由優化也在三個層次上進行，示例如圖1所示。

    （3）路由維護

    考慮到車輛自組織網絡中節點移動速度塊，網絡的拓撲結構變化很快，路由斷裂現象頻繁，因此需要對路由進行維護。文獻[14]的路由維護：路由維護也與路由發現的三個層次相對應，對于源節點自身區域內構建的路由，維護時只需要從原路由中剔除失效的中繼節點，更新路由表，根據新路由表重建路由即可；對于簇區域內構建的路由，除了從原路由中剔除失效的中繼節點之外，還需要從簇內尋找一個新的中繼節點，構建新的路由；對于簇外構建的路由，路由斷裂由簇的外圍節點引發，需要從原路由中剔除失效的外圍節點，然后選擇新的外圍節點作為中繼節點，構建新的路由。

2 結合位置信息的改進區域路由協議

    文獻[14]提出的面向公交車骨干網的區域路由協議能有效降低車輛自組織網絡數據擁堵的問題。然而，在其路由發現的三個層次中，簇外發現階段存在較多的冗余通信，增加了路由開銷。為了解決這一問題，本文提出了一種結合位置信息的改進區域路由協議。設計思想是，在路由發現的簇外發現階段，依據目標節點和簇頭節點的相對位置信息，篩選用于數據轉發的簇外圍節點，降低冗余數據通信。

    如圖2所示，源節點為S，源節點所在簇的簇頭節點為C，該簇的區域為3跳半徑的一個圓。A、G、N、G為該區域的4個外圍節點，D為目的節點。源節點S想要傳輸數據給目的節點D，目的節點D既不在源節點S的1跳自身區域內，也不在源節點S所在的以節點C為簇頭的3跳簇區域內。因此，需要啟動簇外路由發現，文獻[14]的策略是由簇頭節點C將源節點S的路由請求信息發送給簇頭節點C所在簇的外圍節點，也即A、G、N、G 4個節點，然后再由這些節點向相交的其他簇轉發路由請求信息，直到找到目的節點D。圖2的示例中外圍節點只有4個，實際上可能有很多個。而且，與這些外圍節點相交的簇可能有很多個，每一個簇又有許多外圍節點。目的節點D與S之間又可能間隔許多簇。因此，簇外發現的路由開銷有可能很大。為了降低路由開銷，本文利用節點的位置信息，只朝向目的節點所在的方向進行簇外發現，而降低背對目的節點方向所進行的簇外發現產生的冗余路由開銷。如圖2所示，直線d將網絡中的節點劃分成兩個部分：一側含有目的節點D，而另一側沒有目的節點D。很明顯，朝向不含有目標節點D的一側發送數據包是冗余的。因此，當節點需要使用簇外發現來尋找目標節點D時，可以依據外圍節點屬于哪一側來決定哪些外圍節點需要接收和轉發路由請求信息。例如，在圖2中，簇頭節點C的外圍節點G和J與目的節點D在同一側，需要接收和轉發路由請求信息。而簇頭節點C的外圍節點A和N與目的節點D不在同一側，就不需要接收和轉發路由請求信息。這樣，在簇外發現過程中，每一個節點簇剔除的外圍節點數量越多，那么剔除的冗余通信越多，降低的路由開銷越大。很明顯，源節點與目標節點距離越遠，路由開銷的下降越大。

    通過上面的示例分析，可以看出本文改進的區域路由協議與文獻[14]所使用的區域路由協議的主要區別是：在簇外路由發現階段，文獻[14]所使用的區域路由協議由簇頭節點將路由請求信息轉發給其所在簇的所有外圍節點，而本文改進的區域路由協議由簇頭節點將路由請求信息轉發給其所在簇的與目的節點同側的外圍節點。在選擇外圍節點時增加了一個位置約束條件，即相對于簇頭節點，所選外圍節點應當與目的節點同側。那么，現在需要確定分割線d，由該直線將簇頭節點所在簇的外圍節點分成兩部分。分割線d滿足兩個條件：

    (1)d與直線CD垂直；

    (2)d通過簇頭節點C。

    在節點C和節點D的位置已知的情況下，直線CD很容易求出，可以表示為；

    本文改進的區域路由協議在簇外路由發現階段依據式(6)給出的位置約束方程，選擇合適的外圍節點用于轉發路由請求信息，從而降低路由開銷。為了實現改進的區域路由協議，還需要在傳統區域路由協議的鏈路狀態更新數據包中增加兩個字段，用于存放簇頭節點和目的節點的位置信息。修改后的鏈路狀態更新數據包格式如圖3所示。如文獻[14]所述，車輛自組織網絡中每一個車輛節點都裝配了GPS定位模塊，可以實時獲取自身的位置信息。在簇區域內路由發現階段，為每一個簇成員節點更新簇頭節點和目節點的位置信息。當需要進行簇外路由發現時，可以利用簇頭節點和目標節點的位置信息構建如式(6)所示的位置約束條件，依據約束條件篩選合適的外圍節點進行數據的轉發。

3 仿真實驗與分析

    本文是對文獻[14]所述的基于公交車骨干網的區域路由協議的改進，因此為了便于對比，本文的仿真實驗參考文獻[14]的實驗參數。其中，軟件平臺使用Network Simulator 2(簡稱NS2)，硬件平臺使用Intel I5 CPU、DDR3 16 GB RAM的計算機。NS2的仿真參數如表1所示。

    與文獻[14]一樣，本文實驗通過對比丟包率、端到端平均時延和路由開銷來評價不同路由協議的性能。除了對比本文改進的區域路由協議和文獻[14]所述的公交車骨干網區域路由協議之外，還對比常用的AODV^[7]和DSDV^[8]兩種路由協議。下面從丟包率、端到端平均時延和路由開銷3個方面進行實驗對比分析。

3.1 丟包率實驗結果對比分析

    丟包率是指一段時間內目的節點未成功接收的數據包數量與發送節點發出的數據包數量的比值，反映了路由協議所創建路由的可靠性。丟包率越低，說明路由協議創建的路由越可靠。圖4展示了4種路由協議的丟包率隨節點移動速度的變化曲線。可見，隨著節點移動速度的提升，4種路由協議的丟包率都呈現了上升趨勢，因為節點移動速度越快，網絡的拓撲結構變化越快，路由越不穩定，導致丟包率增加。通過對比，在節點移動速度相同的條件下，AODV路由協議的丟包率最小，因為該路由協議是一種單純的按需路由協議，所創建的路由非常穩定。本文的路由協議的丟包率僅次于AODV路由協議，略高于文獻[14]路由協議。主要原因是本文改進的路由協議降低了簇外路由發現階段轉發數據包的外圍節點數量，從而加快了路由發現的速度，這樣在節點移動速度加快的情況下可以快速轉發數據或者重建路由，進而降低了丟包率。DSDV路由協議的丟包率最大，原因是該協議依據距離度量制定的路由選擇策略受節點移動速度的影響較大。

3.2 端到端平均時延實驗結果對比分析

    端到端平均時延是指數據包從源節點發出到目地節點接收所花費的平均時間，反映了路由協議所創建路由的傳輸效率。端到端平均時延越小，說明路由協議創建的路由傳輸效率越高。圖5展示了4種路由協議的端到端平均時延隨節點移動速度的變化曲線。可見，隨著節點移動速度的提升，4種路由協議的端到端平均時延也都呈現了上升趨勢，原因同樣是由于節點的快速移動導致網絡拓撲結構的快速變化，影響了路由的穩定性，當路由斷裂時需要重啟路由發現進程，這樣就導致了端到端平均時延的增加。對比發現，在節點移動速度相同的條件下，本文改進的路由協議的端到端平均時延略高于DSDV路由協議，但低于文獻[14]路由協議以及AODV路由協議。DSDV路由協議選擇最短距離構建路由，端到端平均時延小。本文協議是在文獻[14]路由協議的基礎上進行改進的，通過減少簇外路由發現階段存在的冗余傳輸，提高了路由發現的速度，從而降低了數據包傳輸的端到端平均延時。

3.3 路由開銷實驗結果對比分析

    路由開銷是指成功傳送一個數據分組需要生成的路由控制分組的數量，反映了路由協議所創建路由的資源占用率。路由開銷越小，說明路由協議創建的路由資源占用率越低。圖6展示了4種路由協議的路由開銷隨節點移動速度的變化曲線。可見，隨著節點速度的提升，4種路由協議的路由開銷也都呈現了上升趨勢，這也是因為節點移動速度加快引發網絡拓撲結構快速變化，導致路由發現和維護的開銷增加。在節點移動速度相同的條件下，DSDV路由協議的路由開銷最大，文獻[14]路由協議與AODV路由協議的路由開銷相近，且節點移動速度較低時文獻[14]路由協議的路由開銷略高于AODV路由協議，節點移動速度較高時文獻[14]路由協議的路由開銷略低于AODV路由協議。而在這4種路由協議中，本文改進的路由協議的路由開銷是最小的，這是因為本文改進了文獻[14]的簇外路由發現部分，降低了這一階段外圍節點的冗余路由發現任務，從而大幅降低了路由開銷。

3.4 綜合評價

    綜合圖4、圖5和圖6的實驗結果以及前文實驗分析，本文改進的公交車骨干網區域路由協議的丟包率、端到端平均時延和路由開銷3個指標都優于文獻[14]所述的公交車骨干網區域路由協議，這說明本文對簇外路由發現階段的位置約束措施是行之有效的。另外，本文改進的路由協議的路由開銷指標優于AODV和DSDV路由協議，端到端平均時延指標與DSDV路由協議接近且明顯優于AODV路由協議，丟包率指標略低于AODV路由協議但明顯優于DSDV路由協議。因此，綜合評價本文改進的路由協議的性能指標優于所對比的3種路由協議。

4 結束語

    本文是對基于公交車骨干網的區域路由協議的改進，針對該路由協議的簇外路由發現階段存在的大量冗余通信進行優化，改進內容包括兩個方面：(1)在傳統區域路由協議的鏈路狀態更新數據包中增加兩個字段，用于存放簇頭節點和目的節點的位置信息；(2)在簇外路由發現階段，依據簇頭節點和目的節點的位置信息構建位置約束方程，只選擇與目的節點同側的外圍節點繼續進行數據轉發任務，而與目標節點不在同一側的外圍節點不再進行數據轉發任務，這樣不僅可以減少冗余通信，降低路由開銷，而且提高了路由發現效率。通過仿真實驗證實，本文改進路由協議的丟包率、端到端平均時延和路由開銷3個指標都優于傳統的基于公交車骨干網的區域路由協議，而且從綜合性能指標來看也優于常用的AODV和DSDV兩種區域路由協議。然而，改進的路由協議仍然沒有考慮數據的安全傳輸問題，這是后續需要深入研究的方向。

參考文獻

[1] SHAREF B T，ALSAQOUR R A，ISMAIL M.Comparative study of variant position-based VANET routing protocols[J].Procedia Technology，2013，11(1)：532-539.

[2] 文冠祺，王忠，張少磊，等.車載自組網中基于備用副本回退機制的路由優化算法[J].計算機工程，2017，43(1)：158-161.

[3] XIANG Y，LIU Z，LIU R，et al.GeoSVR：a map-based stateless VANET routing[J].Ad Hoc Networks，2013，11(7)：2125-2135.

[4] KUMAR N，DAVE M.BIIR：a beacon information independent VANET routing algorithm with low broadcast overhead[J].Wireless Personal Communications，2016，87(3)：869-895.

[5] KAMRAN K，AFZAL S，YAQOOB M M，et al.A comparative survey on vehicular ad-hoc network(VANET) routing protocol using heuristic and optimistic techniques[J].Research Journal of Information Technology，2015，6(2)：14-24.

[6] 陶樺，馮富琴，肖鵬，等.基于運行軌跡特征分析的車輛自組織網路由算法[J].通信學報，2016，37(6)：144-153.

[7] BHATT U R，DANGARH A，KASHYAP A，et al.Performance analysis of AODV & DSR routing protocols for MANET[C].Fourth International Conference on Communication Systems and Network Technologies.IEEE Computer Society，2014：254-258.

[8] KUMARSINGH M，THAKUR S N.Comparison of DSDV，DSR and ZRP routing protocols in manets[J].International Journal of Computer Applications，2014，108(13)：10-12.

[9] RANJAN R，XAVIER DAS A，JAISWAL A K，et al.Performance evaluation of FSR，LAR1 and ZRP routing protocols in MANET based on RWP mobility model[J].International Journal of Computer Applications，2013，71(3)：27-31.

[10] MAURYA P K，PAULUS R，JAISWAL A K，et al.Performance analysis of ZRP over AODV，DSR and DYMO for MANET under various network conditions using QualNet simulator[J].International Journal of Computer Applications，2013，66(17)：31-35.

[11] RAVI G.Energy aware zone routing protocol using power save technique AFECA[J].International Review on Computers & Software，2013，8(10)：2373-2379.

[12] RAVILLA D，PUTTA C S R.Performance of secured zone routing protocol due to the effect of malicious nodes in MANETs[C].Fourth International Conference on Computing，Communications and Networking Technologies.IEEE，2013：1-8.

[13] JAIN N，CHABA Y.Simulation based performance analysis of zone routing protocol in manet[J].International Journal of Computer Applications，2014，88(4)：47-52.

[14] 陶冰，李德敏，張光林，等.基于公交車骨干網的區域路由協議研究[J].計算機工程，2016，42(3)：7-12.

作者信息:

萬  航1，王學成2

(1.浙江經濟職業技術學院 物流技術學院，浙江 杭州310018；2.吉林大學 計算機科學與技術學院，吉林 長春130012)