車聯網絡車輛結點路由算法研究

劉 云，顧 群

（1.南通大學杏林學院，江蘇啟東 226236；2.南通大學，江蘇南通 226019）

在2003 年召開的汽車通信標準化會議上，一個全新的概念——車載Ad hoc 網絡（Vehicular Ad hoc Networks，簡稱VANETs）應運而生。VANETs 技術在這個新興領域的相關研究稱為車聯網技術，路由協議作為車聯網技術中的關鍵技術得到了國內外研究人員的廣泛關注。國外對VANETs 的相關研究開始比較早，文獻[1] 改進了VANETs 路由協議中獲得相鄰位置的方法，研究了一種自適應更新策略。文獻[2]介紹了一種預測地理路由協議（PGRP），每輛車根據車輛的方向和角度為其鄰居賦予重量。文獻[3]介紹了一種在VANETs 城市場景中進行路由協議可靠仿真的方法。2004 年以后，我國各高校和研究機構開始對VANETs 及其關鍵技術展開研究。文獻[4]引入粒子群算法對VANET 網絡的GPSR 路由協議進行改進。文獻[5]分析了車載自組織網絡中GPSR 路由算法存在的缺陷，提出了改進措施。文獻[6]分別對通信半徑相同情況下和通信半徑不同情況下的GPSR 路由協議進行了改進，提高了服務質量。

1 路由算法理論基礎

1.1 貪婪轉發算法

源結點在轉發data 數據包前，首先判斷是否存在最靠近目的地的下一跳鄰結點。遍歷鄰居列表，如果源結點可以查找到距離目的地結點最近的下一跳結點，則選擇貪婪轉發策略對數據包進行轉發，如圖1 所示，圖中結點S要向結點D發送數據包，以結點S為圓心的圓內所有結點是結點S的下一跳鄰結點，通過計算可知下一跳結點K距目的結點D最近。

圖1 貪婪轉發情況

1.2 修正轉發算法

若源結點遍歷完鄰居結點列表后無法找到距離目的地結點最近的下一跳結點，則調用修正轉發算法。如圖2 所示，結點X在進行貪婪轉發時，結點W和結點Y到達目的結點D的距離都比結點X到結點D遠，不符合貪婪轉發規則，無法確定轉發數據包的下一跳結點，此時需要調用修正策略進行data 包轉發。

圖2 修正轉發情況

綜合考慮下一跳結點與目的地之間的距離和下一跳結點的信任值，選擇具有最大權重的下一跳結點進行數據轉發。結點的權重根據其與目的地的距離和結點信任值計算。

2 算法設計

基于地理位置和結點信任值的路由算法在傳輸數據時，首先要通過信標廣播獲得目的地結點的地理位置和鄰居結點的地理位置，然后結點根據收集到的地理位置信息選擇調用轉發算法進行數據包轉發。目的地結點定期廣播（sink）包，每個結點在收到sink 包后更新自己的目的地列表。當結點要發送數據時，就會去自己的目的地列表里進行查找目標結點的地理位置。源結點通過信標（beacon）包的周期性互傳可以得知其一跳通信范圍內所有鄰居結點的位置信息，每個結點在收到beacon 包后更新自己鄰居結點信息。若一個結點在一定的時間間隔內（本方案將此時間設為常量DEFAULT_GPSR_TIMEOUT）沒有接收到某一個鄰居結點的beacon 包信息，則結點會認為該鄰居結點已經移出了結點的通信范圍，把該鄰居結點的信息從鄰居列表中刪除。由于車輛結點始終處于高速運動中，在進行數據轉發時網絡拓撲中鄰居關系不穩定，這可能導致下一跳結點在收到發送結點發來的數據包之前先離開傳輸范圍，所以需要對未來鄰居結點的位置進行預測。假設存在一個最大允許距離λ×ds，d，當ds，b≤λ×ds，d時，下一跳在接收到發送結點發來的數據包之前一般不會超出其所在的傳輸范圍。其中，ds，b表示發送結點s（xs，ys）和下一跳結點B（xb，yb）之間的距離，ds，b計算公式如式（1）所示

式中：ds，b表示發送結點s（xs，ys）和目的結點D（xd，yd）之間的距離，ds，d計算公式如式（2）所示

λ 為常量。遍歷鄰居結點列表，將鄰居結點列表中處于最大允許范圍內的所有結點放入下一跳允許結點列表。

在進行data 數據包轉發時，路由算法使用兩種轉發策略，貪婪轉發策略和修正轉發策略。轉發的具體過程如下。

Step1：判斷當前結點是否是目的地結點，若不是則轉step2，否則算法終止。

Step2：判斷是否存在最靠近目的地的下一跳鄰結點，若存在則轉step3 進入，否則轉step4。

Step3：在自己的下一跳允許列表中尋找信任值最大的結點作為數據轉發的下一跳結點，下一跳結點接收到數據包后，轉step1。

Step4：在自己的鄰居列表中尋找具有最大權重的結點作為數據轉發的下一跳結點，下一跳結點接收到數據包后，轉step1。結點的權重根據其與目的地的距離和結點信任值計算。當這2 個因子結合時，這2 個因子的權重由w1和w2表示，且w1+w2=1。權重計算公式如式（3）所示

式中：dk，d表示下一跳k（xk，yk）和目的地D（xd，yd）之間的距離，dk，d計算公式如式（4）所示

tv表示下一跳結點的信任值信息。間隔一定時間后，源結點再次發送data 數據包，重復上述步驟。

3 實驗仿真

3.1 仿真場景

本文設計了一個基于地理位置和車輛信任值的車聯網絡路由算法，當存在最靠近目的地的鄰居結點時，選擇貪婪轉發，否則使用修正轉發。為了研究路由算法的可行性及算法性能，使用OMNeT++仿真工具、SUMO交通仿真器和veins 框架搭建仿真環境，并對得出的結果進行分析。其中，OMNeT++控制網絡模擬，SUMO 模擬實際交通場景，veins 協調OMNeT++和SUMO 一起工作。模擬的區域為5 000 m×5 000 m，SUMO 交通仿真器對實驗仿真場景的細節描述包括：道路、車輛數量、車輛行駛規則等。

3.2 測量參數

車聯網絡路由算法的性能指標主要包括：平均端到端時延和丟包率，這2 個性能指標可以反映路由算法在網絡中的性能。其定義如下。

平均端到端時延：源結點到目的結點的傳輸時延總和與成功接收的數據包數量之和的比值，這個性能指標反映路由有效性。

丟包率：丟失的數據包數量之和與發送的數據包數量之和的比值，這個性能指標反映路由可靠性。

3.3 仿真設計及結果分析

3.3.1 仿真設計

仿真結果包括矢量仿真結果、標量仿真結果、唯一的運行ID 和屬性。輸出的矢量仿真結果是時間序列數據，可以用來記錄任何對獲得模型在仿真期間運行的具體情況有幫助的數據。在omnetpp.ini 文件中加入語句“**.vector-recording = true”，啟用矢量記錄。標量結果記錄在recordScalar（）函數調用中，這種調用通常在finish 模塊中完成，若要啟用標量記錄則需在omnetpp.ini 文件中加入語句“**.scalar-recording =true”。

運行仿真程序，仿真結束后在results 文件夾下會保存新生成的結果文件*.sca 和*.vec。雙擊打開*.sca文件或*.vec 文件會生成一個*.anf 分析文件，如圖3所示。接下來就是對*.anf 文件獲得的數據進行分析，得到當前rou.xml 文件描述情景下路由算法的端到端時延和丟包率。

圖3 *.anf 分析文件

3.3.2 車輛結點數量對算法性能的影響

仿真參數配置：設置仿真區域為5 000 m×5 000 m，數據鏈路（MAC）層采用IEEE 802.11p 協議，數據流配置為車載通信仿真框架（Veins）生成的data 數據流，每間隔5 s 開始發送一次data 數據包，基于實際拓撲圖的車輛運動場景由SUMO 生成，仿真過程中依次隨機放入15、20、25、30、35、40 個結點進行仿真，設置結點的最大速度為14 m/s（50.4 km/h），配置仿真時間為2 000 s。在網絡內車輛結點最大速度相同的情況下，車輛結點數目不同，對每一種情況進行多次實驗，最后取多次實驗結果的平均值。

圖4 是車輛結點數目不同的情況下路由算法的平均端到端時延對比圖。從圖4 中可以發現隨著車輛結點數目的增加，平均端到端時延逐漸減小。這是因為隨著網絡內車輛結點數量的增加，結點的鄰居結點數量同時增多，結點之間的鄰居關系的穩定性顯著提高，通信鏈路穩定性增強，平均端到端時延自然就下降了。

圖4 數目不同時端到端時延的對比圖

圖5 是車輛結點數目不同的情況下路由算法的丟包率對比圖。從圖5 中可以發現，當前實驗仿真的各個場景下路由算法的丟包率均為0，這證明此路由算法是可行且可靠的。理想情況下，隨著車輛結點數量的增加，路由算法的丟包率應下降。而圖5 中路由算法的丟包率始終為0，這是因為SUMO 使用交通“流”方式“編寫”車流文件，車輛結點密度一直很高，路由算法較容易找到下一跳轉發結點。

圖5 數目不同丟包率的對比圖

3.3.3 車輛結點最大速度對算法性能的影響

仿真參數配置：設置仿真區域為5 000 m×5 000 m，MAC 層采用IEEE 802.11p 協議，數據流配置為Veins 生成的data 數據流，每間隔5 s 開始發送一次data 數據包，基于實際拓撲圖的車輛運動場景由SUMO生成，仿真實驗中結點的最大速度依次設置為4m/s（14.4 km/h）、9 m/s（32.4 km/h）、14 m/s（50.4 km/h）、19 m/s（68.4 km/h）、24 m/s（86.4 km/h）、29 m/s（104.4 km/h），結點的數量為25，仿真時間設置為2 000 s。在網絡中車輛結點數量相同的情況下，車輛結點最大速度不同，對每一種情況進行多次實驗，最后取多次實驗結果的平均值。

圖6 是車輛結點最大速度不同的情況下路由算法的平均端到端時延。從圖6 中可以看出，隨著網絡內車輛結點最大速度不斷提高，路由算法的平均端到端時延不斷增大。這是因為，隨著網絡內結點速度的變大，結點之間的地理位置關系變化更加頻繁，導致鄰居關系不穩定，造成平均時延增加。

圖6 最大速度不同時端到端時延對比圖

圖7 是車輛結點最大速度不同的情況下路由算法的丟包率。從圖7 中可以看出，當前實驗仿真場景下的路由算法丟包率均為0。理想情況下，隨著結點速度的增大，路由算法丟包率應上升。而圖7 中，路由算法始終為0，這是因為當前仿真場景下，使用flow 定義的車流中車輛結點始終“聚集”在一起，鄰居關系相對穩定，網絡通信鏈路穩定性較好。

圖7 最大速度不同時丟包率對比圖

4 結束語

本文設計了一個基于地理位置和結點信任值的路由算法，路由算法在傳輸數據時，首先要通過信標廣播獲得目的地結點的地理位置信息和鄰居結點的地理位置信息，然后結點按照收集到的地理位置信息調用貪婪轉發策略和修正轉發策略兩種路由轉發算法進行數據包轉發。使用SUMO、OMNeT++、veins 搭建車聯網仿真環境，在veins 框架中編寫并編譯本文提出的路由算法，通過實驗仿真獲得特定情境下路由算法的平均端到端時延和丟包率。仿真結果表明，路由算法是有效可行的，且車輛結點數量和車輛結點最大速度對路由算法性能有影響。