0 引言

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

1 面向公交車骨干網(wǎng)的區(qū)域路由協(xié)議

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

    （1）路由發(fā)現(xiàn)

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

    （2）路由優(yōu)化

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

    （3）路由維護

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

2 結合位置信息的改進區(qū)域路由協(xié)議

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

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

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

    (1)d與直線CD垂直；

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

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

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

3 仿真實驗與分析

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

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

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

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

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

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

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

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

3.4 綜合評價

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

4 結束語

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

參考文獻

[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] 文冠祺，王忠，張少磊，等.車載自組網(wǎng)中基于備用副本回退機制的路由優(yōu)化算法[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] 陶樺，馮富琴，肖鵬，等.基于運行軌跡特征分析的車輛自組織網(wǎng)路由算法[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] 陶冰，李德敏，張光林，等.基于公交車骨干網(wǎng)的區(qū)域路由協(xié)議研究[J].計算機工程，2016，42(3)：7-12.

作者信息:

萬  航1，王學成2

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