劉 云，顧 群

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

在2003 年召開的汽車通信標(biāo)準(zhǔn)化會議上，一個全新的概念——車載Ad hoc 網(wǎng)絡(luò)（Vehicular Ad hoc Networks，簡稱VANETs）應(yīng)運(yùn)而生。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é)點(diǎn)在轉(zhuǎn)發(fā)data 數(shù)據(jù)包前，首先判斷是否存在最靠近目的地的下一跳鄰結(jié)點(diǎn)。遍歷鄰居列表，如果源結(jié)點(diǎn)可以查找到距離目的地結(jié)點(diǎn)最近的下一跳結(jié)點(diǎn)，則選擇貪婪轉(zhuǎn)發(fā)策略對數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，如圖1 所示，圖中結(jié)點(diǎn)S要向結(jié)點(diǎn)D發(fā)送數(shù)據(jù)包，以結(jié)點(diǎn)S為圓心的圓內(nèi)所有結(jié)點(diǎn)是結(jié)點(diǎn)S的下一跳鄰結(jié)點(diǎn)，通過計(jì)算可知下一跳結(jié)點(diǎn)K距目的結(jié)點(diǎn)D最近。

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

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

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

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

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

2 算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)仿真

3.1 仿真場景

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

3.2 測量參數(shù)

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

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

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

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

3.3.1 仿真設(shè)計(jì)

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

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

圖3 *.anf 分析文件

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

本文設(shè)計(jì)了一個基于地理位置和結(jié)點(diǎn)信任值的路由算法，路由算法在傳輸數(shù)據(jù)時，首先要通過信標(biāo)廣播獲得目的地結(jié)點(diǎn)的地理位置信息和鄰居結(jié)點(diǎn)的地理位置信息，然后結(jié)點(diǎn)按照收集到的地理位置信息調(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 框架中編寫并編譯本文提出的路由算法，通過實(shí)驗(yàn)仿真獲得特定情境下路由算法的平均端到端時延和丟包率。仿真結(jié)果表明，路由算法是有效可行的，且車輛結(jié)點(diǎn)數(shù)量和車輛結(jié)點(diǎn)最大速度對路由算法性能有影響。