基于局部梯度場的VANET路由研究

馬 逍

(同濟大學 電子與信息工程學院，上海 201804)

0 引言

近年來為保證車輛安全行駛，在移動自組織網絡的基礎上出現了車輛自組織網絡。VANET中現有的安全消息傳播機制大都是在移動自組織網絡的基礎上演化而來的。但自組織網絡[1]沒有考慮網絡拓撲的動態高度變化，因此現有的自組織網絡路由機制無法很好地適應VANET安全消息傳播的要求。

現有的路由協議包括地理源路由協議、基于GPSR的廣播協議、限制洪泛區域的路由協議[2]和空間感知路由協議[3]等，但這些路由協議均依賴于準確的位置信息，一方面增加了路由成本，另一方面，路由性能也受限于位置信息準確性。

針對城市的應用場景，文獻[4]提出了一種全局狀態路由協議（GSR，Geographic Source Routing），該協議具有較好的包傳送率、低帶寬利用率，但沒有考慮在2個連續的交叉點之間車輛的連通性。基于概率的路由協議（PBR，Probability Based Routing）[5]能夠在密集的自組織網絡中提高包傳送率，但是在具有拓撲空洞的網絡中，其路由性能急劇下降。

目前研究中出現較多的是GPSR協議。GPSR協議在高速公路上有良好的性能，但是在城市交通場下，貪婪轉發經常受到道路拓撲的限制，信道質量也受到道路兩旁的建筑物等障礙物的影響，同時高動態網絡拓撲也會引起很多問題，其中典型的就是嬰兒步問題。針對VANET中的網絡割裂，研究人員通常借助于機會路由的方法來轉發安全消息。典型的機會路由協議都是采用單一指標作為選取最佳下一跳候選節點的評估參量，如以硬件地址作為評估參量的極端機會路由（ExOR，Extremely Opportunistic Routing）[6]。

1 基于LGFR的VANET安全消息傳播機制

1.1 梯度的概念

在向量微積分中，標量場的梯度是一個向量場。標量場中某一點上的梯度指向標量場增長最快的方向，梯度的數值是變化最快的變化率。梯度場構建后，數據沿著梯度場進行傳播。當遇到故障節點或是鏈路斷開時，數據將自動通過新的中繼點轉發。這種不依賴于某一特定鄰居節點為下一跳的傳輸方式，隱性地維持了所有可用路徑，因而顯示出健壯性，從而有效的改善了網絡能耗，延長了網絡生命周期，即使在網絡拓撲不斷變化的情況下仍然保有較高的包投遞率。

基于上述特點，引入局部梯度場的概念，通過多維度參量計算源節點周圍每個節點的梯度值，從而建立起源節點的局部梯度場，其中梯度值最大的節點即為下一跳的最佳轉發節點。安全消息就沿著梯度場轉發至目標節點。

1.2 基于LGFR的VANET安全消息傳播機制

為建立VANET中局部梯度場，在計算梯度值時綜合了多維度參量。梯度值越大意味著向該方向繼續搜索到達目的節點的幾率越大，以同樣的方式，在整個網絡中建立一個臨時的局部梯度場，安全消息沿梯度最大的方向傳播，這種方案稱為基于LGFR的VANET安全消息的多跳路由機制。

假設VANET中所有的節點可以通過全球定位系統和數字地圖獲得車輛坐標、運動速度和運動方向等信息。每個車輛知道自身的地理位置信息，并通過電子地圖可獲得自身所處城市區域內的相關道路拓撲情況; 同時每個車輛可輔助計算車輛周圍鄰居節點的密度；車輛本身還應具備記錄自身數據包處理負載情況。

由于源節點只需向同一車道方向的節點發送安全消息，源節點只收集與自己同方向的車輛的位置信息，如圖1所示，節點A收到的周圍鄰居節點B、C的廣播包后，從廣播包中提取鄰居節點B、C的移動方向信息與路段ID。如果鄰居節點的路段ID與自身的路段ID相同，則建立下一跳轉發鄰居關系，另一方面，節點B、C移動方向與節點A自身的移動方向相比較，在圖1的情景下，得到結果為節點B與節點A反方向行駛，且節點C與節點A移動方向相同，故A節點只接收C節點發送的位置信息，而忽略節點B發送的位置消息。

圖1 源節點定向接收位置消息示意

1.2.1 VANET中梯度場的構建

1.2.1.1 VANET中梯度場考慮的因素

（1）鄰居節點與目標節點的距離

在轉發過程中盡可能地將數據包傳輸至距離目標節點盡可能近的節點，以減少轉發次數。假設 di表示目標節點和鄰居節點的距離，則 di可由式（1）計算得到：

將當前節點CN與目標節點DN 的距離cd與id進行比較，當id小于cd的時候，即鄰居節點iN比當前節點CN離目標節點DN 更近時才進行數據轉發。

（2）鄰居節點當前數據處理負載狀況

假設iT為節點iN轉發數據包的處理時延，jTr是數據包j到達節點iN的時刻，jTs是節點iN將數據包j再次發送出去的時刻。則iT可由以下公式計算得到：

（3）鄰居節點移動速度以及移動方向

當一個節點高速向目標節點移動時，該節點將數據包成功地轉發到目標節點的可能性最大。如圖2所示，設定節點 Ni在t1時刻的位置為，在 t2時刻它移動到了位置。擁有數據包的節點 NC的位置是，目標節點 Nd的位置為。在該情況下，鄰居節點 Ni的移動速度，數據包轉發方向與節點移動方向之間的切角由式（3）和式（4）給出。

（4）鄰居節點周圍節點密度

在VANET中，下一跳轉發節點iN自身周圍的鄰居節點密度越高，則iN轉發數據包成功的概率越大。在實際轉發過程中，節點iN通過Beacon數據包周期性的廣播的形式采集周圍節點密度iρ，并將iρ通告至準備向其轉發數據包的節點。當iN的鄰居節點密度大于鄰居節點密度的閾值sρ時，iN才有可能成為下一跳轉發節點。

圖 2 節點移動速度與移動方向評估場景

1.2.1.2 梯度值的計算

梯度值就是在單獨計算所有的評估尺度參量后，通過聯合分析評估所有的尺度參量權值計算得出的，其中1C、2C、3C、4C、5C為加權系數，如式（5）所示：

滿足所有評估參量的節點都會根據以上公式計算得到自身的梯度值(Ni)。通過對梯度值的比較，梯度值最大的 Ni即被選擇為最佳轉發節點。由于梯度是個矢量，梯度值是由2.5式算出的標量值，而梯度的方向為從當前節點指向梯度值最大節點的方向。

1.2.2 LGFR協議

當前節點根據一跳內的節點的梯度值進行轉發，將數據包轉發至最佳轉發節點，并且通告周圍鄰居節點最佳轉發節點的控制信息。當最佳轉發節點成功接受數據包，完成校驗后，將成功接受數據包的控制信息，通告至本次轉發過程中的其他節點。如果在其他轉發候選節點在數據包過期前未收到該數據包已被成功接受的控制信息，系統會依次選擇在優先級隊列存儲起來的其他候選節點重復上述過程。如果所有節點都已完成這次轉發，但仍沒有成功收到數據包的通告，則判定此次轉發過程失敗，開始新一周期的轉發流程。接收到轉發包的節點重復上一節點的過程，選取自己的最佳下一跳轉發節點，直到傳播到第五跳節點停止繼續向前轉發，這是因為安全消息的特殊性，不需要一直向遠方車輛轉發，第五跳節點即為目的節點。通過基于LGFR的轉發方法最終在整個傳播過程中形成一條梯度值的最大路徑，這樣數據包就會沿著此條路徑傳輸。基于LGFR協議的路由建立過程的流程圖如圖3所示。

圖3 基于LGFR協議的路由建立過程

2 仿真實驗與結果分析

如表1所示，為了評估所提出的基于LGFR的VANET安全消息傳播機制的性能，采用Network Simulator 2.31[7-8]作為仿真平臺來驗證LGFR的性能。仿真場景采用曼哈頓移動模型，每次仿真隨機設定20對源節點與目標節點，通過運行200次仿真測試，最終的仿真結果取統計平均值。

表1 網絡仿真參數列表

如圖4所示，LGFR的丟包率最低，這是由于GPSR較少考慮道路拓撲對于路徑選擇的影響，而AODV必須頻繁修復中斷的轉發鏈路，LGFR在選擇數據包轉發鏈路上依據局部梯度場的策略，并不是僅僅依靠地理信息或者網絡拓撲的情況來判斷下一跳節點是否為最佳轉發節點，極大的提高了數據包在VANET中的轉發概率。如圖5所示，在轉發第五跳至第六跳的過程中，三種路由協議都有一個階段性的時延峰值出現，這是某一處的路口轉角造成的陰影信道衰弱，導致在這兩跳數據包轉發的丟包率急速上高。LGFR考慮到下一跳節點的移動速度與移動方向，可選擇新出現的鄰居節點作為最佳下一跳轉發節點，快速建立高可靠性的數據包轉發鏈路，并且從整個時延峰值變化區間來觀察，LGFR同樣具有更小的時延抖動。如圖6所示，隨著節點轉發跳數的增加，三種路由協議的全局數據吞吐量都呈下降趨勢。在此情況下，LGFR的全局數據吞吐量下降速率是三者中最慢的。

圖4 丟包率與轉發跳數

圖5 數據包端到端平均時延與轉發跳數

圖6 全局數據吞吐量與轉發跳數

對于AODV，城市交通環境下的復雜性決定了AODV必須頻繁修復中斷的轉發鏈路，建立新的路由。GPSR由于嬰兒步問題極大影響了路由轉發效率，導致吞吐量瓶頸。LGFR依靠最佳機會轉發節點機制，建立了高可靠性的轉發鏈路，因此其數據包轉發較少受到移動網絡拓撲的影響。

3 結語

在分析了典型的VANET路由協議后，提出了基于LGFR的VANET安全消息傳播機制。首先，提出基于距離、數據包處理時延、移動速度、移動方向、鄰居節點密度等參量生成局部場梯度值的策略。然后，根據梯度值大小進行安全消息轉發的優先級排序，從中選取最佳路由轉發節點。最后，選擇AODV和GPSR作為比較對象，利用NS2作為仿真平臺，以曼哈頓移動模型作為仿真城市道路場景，測試了三種協議在城市交通環境下的路由性能表現。仿真結果表明，LGFR相對其他兩種路由協議能更加好地適應城市道路應用場景，其各項網絡指標也在三種路由協議中擁有最佳的性能表現。

[1] 曹亮,蔣興浩. 一種改進型Ad hoc網絡安全路由協議[J].信息安全與通信保密,2008(06):112-114.

[2] KAREDAL J, CZINK N, PAIER A, et al. Pathloss Modeling for Vehicle-to-Vehicle Communications[J].IEEE Trans. Vehicular Technology,2011,60(01):323-328.

[3] FAN L, YU W. A Survey of Routing in Vehicular Ad Hoc Networks[J]. IEEE Vehicular Technology Magazine, 2007,2(02):12-22.

[4] ZHAO J, CAO G. VADD: Vehicle-assisted Data Delivery in Vehicular Ad hoc Networks[J]. IEEE Transaction On Vehicular Technology, 2008, 57(03): 1910-1922.

[5] JARUPAN B, EKICI E. A Survey of Cross-layer Design for Vanets[J]. Journal of Ad Hoc Networks, 2011(09):966-983.

[6] WU C, KUMEKAWA K, KATO T. A Novel Multi-hop Broadcast Protocol for Vehicular Safety Applications[J]. Journal of Information Processing, 2010(18):110-124.

[7] 陳春梅.基于NS2的網絡仿真與性能分析[J].通信技術,2010,43(08):48-50.

[8] 熊飚,張小橋.VANET網絡中小尺度衰落信道仿真[J].通信技術,2010,43(12):56-58.