車聯(lián)網(wǎng)絡(luò)車輛結(jié)點路由算法研究

劉 云，顧 群

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

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

1 路由算法理論基礎(chǔ)

1.1 貪婪轉(zhuǎn)發(fā)算法

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

圖1 貪婪轉(zhuǎn)發(fā)情況

1.2 修正轉(zhuǎn)發(fā)算法

若源結(jié)點遍歷完鄰居結(jié)點列表后無法找到距離目的地結(jié)點最近的下一跳結(jié)點，則調(diào)用修正轉(zhuǎn)發(fā)算法。如圖2 所示，結(jié)點X在進(jìn)行貪婪轉(zhuǎn)發(fā)時，結(jié)點W和結(jié)點Y到達(dá)目的結(jié)點D的距離都比結(jié)點X到結(jié)點D遠(yuǎn)，不符合貪婪轉(zhuǎn)發(fā)規(guī)則，無法確定轉(zhuǎn)發(fā)數(shù)據(jù)包的下一跳結(jié)點，此時需要調(diào)用修正策略進(jìn)行data 包轉(zhuǎn)發(fā)。

圖2 修正轉(zhuǎn)發(fā)情況

綜合考慮下一跳結(jié)點與目的地之間的距離和下一跳結(jié)點的信任值，選擇具有最大權(quán)重的下一跳結(jié)點進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。結(jié)點的權(quán)重根據(jù)其與目的地的距離和結(jié)點信任值計算。

2 算法設(shè)計

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

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

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

在進(jìn)行data 數(shù)據(jù)包轉(zhuǎn)發(fā)時，路由算法使用兩種轉(zhuǎn)發(fā)策略，貪婪轉(zhuǎn)發(fā)策略和修正轉(zhuǎn)發(fā)策略。轉(zhuǎn)發(fā)的具體過程如下。

Step1：判斷當(dāng)前結(jié)點是否是目的地結(jié)點，若不是則轉(zhuǎn)step2，否則算法終止。

Step2：判斷是否存在最靠近目的地的下一跳鄰結(jié)點，若存在則轉(zhuǎn)step3 進(jìn)入，否則轉(zhuǎn)step4。

Step3：在自己的下一跳允許列表中尋找信任值最大的結(jié)點作為數(shù)據(jù)轉(zhuǎn)發(fā)的下一跳結(jié)點，下一跳結(jié)點接收到數(shù)據(jù)包后，轉(zhuǎn)step1。

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

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

tv表示下一跳結(jié)點的信任值信息。間隔一定時間后，源結(jié)點再次發(fā)送data 數(shù)據(jù)包，重復(fù)上述步驟。

3 實驗仿真

3.1 仿真場景

本文設(shè)計了一個基于地理位置和車輛信任值的車聯(lián)網(wǎng)絡(luò)路由算法，當(dāng)存在最靠近目的地的鄰居結(jié)點時，選擇貪婪轉(zhuǎn)發(fā)，否則使用修正轉(zhuǎn)發(fā)。為了研究路由算法的可行性及算法性能，使用OMNeT++仿真工具、SUMO交通仿真器和veins 框架搭建仿真環(huán)境，并對得出的結(jié)果進(jìn)行分析。其中，OMNeT++控制網(wǎng)絡(luò)模擬，SUMO 模擬實際交通場景，veins 協(xié)調(diào)OMNeT++和SUMO 一起工作。模擬的區(qū)域為5 000 m×5 000 m，SUMO 交通仿真器對實驗仿真場景的細(xì)節(jié)描述包括：道路、車輛數(shù)量、車輛行駛規(guī)則等。

3.2 測量參數(shù)

車聯(lián)網(wǎng)絡(luò)路由算法的性能指標(biāo)主要包括：平均端到端時延和丟包率，這2 個性能指標(biāo)可以反映路由算法在網(wǎng)絡(luò)中的性能。其定義如下。

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

丟包率：丟失的數(shù)據(jù)包數(shù)量之和與發(fā)送的數(shù)據(jù)包數(shù)量之和的比值，這個性能指標(biāo)反映路由可靠性。

3.3 仿真設(shè)計及結(jié)果分析

3.3.1 仿真設(shè)計

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

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

圖3 *.anf 分析文件

3.3.2 車輛結(jié)點數(shù)量對算法性能的影響

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

圖4 是車輛結(jié)點數(shù)目不同的情況下路由算法的平均端到端時延對比圖。從圖4 中可以發(fā)現(xiàn)隨著車輛結(jié)點數(shù)目的增加，平均端到端時延逐漸減小。這是因為隨著網(wǎng)絡(luò)內(nèi)車輛結(jié)點數(shù)量的增加，結(jié)點的鄰居結(jié)點數(shù)量同時增多，結(jié)點之間的鄰居關(guān)系的穩(wěn)定性顯著提高，通信鏈路穩(wěn)定性增強(qiáng)，平均端到端時延自然就下降了。

圖4 數(shù)目不同時端到端時延的對比圖

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

圖5 數(shù)目不同丟包率的對比圖

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

仿真參數(shù)配置：設(shè)置仿真區(qū)域為5 000 m×5 000 m，MAC 層采用IEEE 802.11p 協(xié)議，數(shù)據(jù)流配置為Veins 生成的data 數(shù)據(jù)流，每間隔5 s 開始發(fā)送一次data 數(shù)據(jù)包，基于實際拓?fù)鋱D的車輛運動場景由SUMO生成，仿真實驗中結(jié)點的最大速度依次設(shè)置為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），結(jié)點的數(shù)量為25，仿真時間設(shè)置為2 000 s。在網(wǎng)絡(luò)中車輛結(jié)點數(shù)量相同的情況下，車輛結(jié)點最大速度不同，對每一種情況進(jìn)行多次實驗，最后取多次實驗結(jié)果的平均值。

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

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

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

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

4 結(jié)束語

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