魏大堯

摘要：該文針對VANET的拓?fù)浣Y(jié)構(gòu)變化迅速而造成現(xiàn)有路由協(xié)議如DSDV、AODV等建立的路由鏈路有效期短的問題，提出一種基于車輛運動狀態(tài)的多路徑路由發(fā)現(xiàn)策略，該發(fā)現(xiàn)策略的目標(biāo)是根據(jù)車倆移動方向和車輛移動速度發(fā)現(xiàn)預(yù)計連接時長較長的路由路徑，該發(fā)現(xiàn)策略通過收集VANET中節(jié)點的運動信息，將路徑發(fā)現(xiàn)問題轉(zhuǎn)換為最短路徑問題，通過多階段決策來解決最短路徑問題來尋找最優(yōu)和次優(yōu)的路由路徑。

關(guān)鍵詞：車載自組網(wǎng)絡(luò)；視頻傳輸；路由協(xié)議；自適應(yīng)

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）11-0220-04

1 背景

車聯(lián)網(wǎng)（Internet of Vehicles）是由車輛位置、速度和路線等信息構(gòu)成的巨大交互網(wǎng)絡(luò)。車聯(lián)網(wǎng)主要由車載自組網(wǎng)絡(luò)和服務(wù)端計算平臺構(gòu)成，車載自組網(wǎng)絡(luò)負(fù)責(zé)數(shù)據(jù)收集，數(shù)據(jù)傳輸?shù)裙ぷ?，服?wù)端負(fù)責(zé)匯總信息，計算所需要的數(shù)據(jù)等。該文主要針對車載自組網(wǎng)絡(luò)進行研究。

相比于傳統(tǒng)有線視頻傳輸，基于VANET 的視頻傳輸具有成本低、靈活性大等特點，但是也面臨諸多的挑戰(zhàn)。一方面是視頻數(shù)據(jù)具有容量大、帶寬消耗大和實時性高、對時延抖動敏感等特點；另外一方面，雖然VANET 是MANET 的一種特殊應(yīng)用，但是VANET 有著其獨特的特點，比如VANET 中車輛有限傳輸范圍、高移動性以及由地理位置引起的網(wǎng)絡(luò)區(qū)域劃分等特點。

該文提出一種基于車輛運動狀態(tài)的多路徑路由發(fā)現(xiàn)協(xié)議策略，該路由協(xié)議通過收集VANET中節(jié)點的運動信息，預(yù)測未來節(jié)點狀態(tài)來尋找鏈路有效時長最長的兩條路由路徑，通過將路徑發(fā)現(xiàn)問題轉(zhuǎn)換為最短路徑問題，通過多階段決策來解決最短路徑問題來尋找最優(yōu)和次優(yōu)的路由路徑。

2 多路徑路由發(fā)現(xiàn)協(xié)議

在之前雖然有關(guān)于建立多路徑路由的研究，但是在尋找轉(zhuǎn)發(fā)節(jié)點時大多數(shù)以最近的鄰居作為轉(zhuǎn)發(fā)節(jié)點，通常情況下MANET中最近的鄰居節(jié)點即是連接最好的節(jié)點，但是在VANET中，由于節(jié)點位置的變動很快，可能當(dāng)前最好的下一個節(jié)點很快會在網(wǎng)絡(luò)拓?fù)渲邢?，該章將介紹一種VANET下基于高速公路場景的多路徑路由的發(fā)現(xiàn)協(xié)議，該協(xié)議將發(fā)現(xiàn)一條主要路徑和次要路徑，為視頻傳輸打下基礎(chǔ)。

2.1 轉(zhuǎn)發(fā)節(jié)點的優(yōu)劣

當(dāng)數(shù)據(jù)傳輸?shù)侥骋还?jié)點時，一般情況下有多個下一跳節(jié)點可供選擇，我們需要在其中選出最優(yōu)的節(jié)點，由于我們假設(shè)所有車輛之間的連接質(zhì)量相同，考慮到VANET下網(wǎng)絡(luò)環(huán)境波動最大的原因就是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化迅速，所以我們認(rèn)為可建立連接時間越長的下一跳節(jié)點是更優(yōu)的下一跳節(jié)點。為了尋找這樣的下一跳節(jié)點，我們主要考慮兩個參數(shù)的影響，行駛方向和行駛速度。

1）行駛方向

如圖1所示，上方節(jié)點都向右行駛，下方節(jié)點向左行駛，S為當(dāng)前節(jié)點，p和q為S的鄰居節(jié)點，S在p和q之間選擇下一跳節(jié)點，由于S和q行駛方向相反，在很快行駛速度下，S和q之間的連接在很短的時間內(nèi)將會失效，而對于p節(jié)點來說，如果S和p節(jié)點行駛速度相同，理論上來說它們之間的連接可以永久存在，即使實際情況下這種情況不存在，但很明顯S和p節(jié)點之間的連接優(yōu)于S和q節(jié)點之間的連接，p節(jié)點是相對于q節(jié)點更好的下一跳節(jié)點。

2）行駛速度

如圖2所示，圖中所有節(jié)點均向右行駛，S為當(dāng)前節(jié)點，p和q為S的鄰居節(jié)點，S在p和q之間選擇下一跳節(jié)點，S和q行駛速度為70km/h，p行駛速度為100km/h?？梢钥吹嚼硐肭闆r下S和q之間的連接會一直存在，而p節(jié)點將逐漸駛離S節(jié)點，S節(jié)點和p節(jié)點之間的連接將會失效，所以q節(jié)點是相對于p節(jié)點更好的下一跳節(jié)點。

2.2 理論描述

通過以上對較優(yōu)下一跳節(jié)點選擇的分析，我們可以將一個S節(jié)點到D節(jié)點之間的路由發(fā)現(xiàn)問題簡化為一個最短路徑發(fā)現(xiàn)問題。下面討論路由發(fā)現(xiàn)問題到最短路徑問題的轉(zhuǎn)換為了將路由發(fā)現(xiàn)問題轉(zhuǎn)為最短路徑問題，首先要根據(jù)當(dāng)前車聯(lián)網(wǎng)環(huán)境生成最短路徑問題中的頂點，邊和邊的長度。很明顯我們以車聯(lián)網(wǎng)中車輛節(jié)點作為最短路徑問題中的頂點。下面討論如何確定最短路徑問題中的邊和邊的長度。

為了敘述方便，我們以圖3為例，如圖3所示為一個VANET示意圖，我們要從S節(jié)點通過中間A-H節(jié)點將數(shù)據(jù)傳輸?shù)紻，為了尋找從S到D的兩條較優(yōu)的路徑，我們可以將這個VANET拓?fù)浣Y(jié)構(gòu)轉(zhuǎn)換為一個最短路徑問題。節(jié)點S的鄰居節(jié)點為A，B，C，所以應(yīng)該存在從節(jié)點S到節(jié)點A，B，C的三條邊，而節(jié)點A的鄰居節(jié)點應(yīng)該有節(jié)點B，C，D，E，F(xiàn)，但是由于節(jié)點B，節(jié)點C和節(jié)點A同是節(jié)點S的鄰居節(jié)點，所以這里不考慮節(jié)點B和節(jié)點C作為節(jié)點A的下一跳節(jié)點，所以應(yīng)該存在從節(jié)點A到節(jié)點D，E，F(xiàn)的三條邊，其他節(jié)點同理。

由于車輛移動速度很快，節(jié)點之間的距離在不斷變動，而且我們要尋找的鏈接時長最長的路徑，而大多數(shù)情況下車輛移動速度對鏈接時長的影響要大于車輛之間的距離。所以我們將兩車之間的相對移動速度而不是車輛之間的距離作為最短路徑問題中兩個頂點點之間的距離。設(shè)dij為從節(jié)點i到節(jié)點j的距離，

當(dāng)節(jié)點i和節(jié)點j同向行駛時，相對移動速度為|vi-vj|，而當(dāng)節(jié)點i和節(jié)點j逆向行駛時，相對速度為|vi+vj|。

通過公式1我們可以把圖3的VANET轉(zhuǎn)化為圖4這樣一個最短路徑問題。

其中值得注意的是由于可以獲取初始節(jié)點S和目標(biāo)節(jié)點D的位置，所以傳輸?shù)姆较蚴且阎?，我們可以避免環(huán)的出現(xiàn)，所以最終求解的是一個有向無環(huán)圖（DAG圖）的最短路徑問題，我們通過動態(tài)規(guī)劃法求解這個問題：

考慮任意節(jié)點i，到達(dá)節(jié)點i僅有的途徑是通過其直接前驅(qū)，如假設(shè)i的直接前驅(qū)有k個節(jié)點i1......ik，如果用dist（i）表示從原點S到節(jié)點i的最短路徑長度，則有如下狀態(tài)轉(zhuǎn)移方程：

dist（i）=min{dist（i1）+d（i1，i），dist（i2）+d（i2，i）......dist（ik）+d（ik，i）}

可以將該問題分為四個階段：

第一階段：

dist（A）=min{dist（S）+d（S，A）}=30

dist（B）=min{dist（S）+d（S，B）}=5

dist（C）=min{dist（S）+d（S，C）}=160

第二階段

dist（D）=min{dist（A）+d（A，D），dist（B）+d（B，D），dist（C）+d（C，D）}=10

dist（E）=min{dist（A）+d（A，E），dist（B）+d（B，E），dist（C）+d（C，E）}=9

dist（F）=min{dist（A）+d（A，F(xiàn)），dist（B）+d（B，F(xiàn)），dist（C）+d（C，F(xiàn)）}=150

第三階段

dist（G）=min{dist（D）+d（D，G），dist（E）+d（E，G），dist（F）+d（F，G）}=10

dist（H）=min{dist（H）+d（D，H），dist（E）+d（E，H），dist（F）+d（F，H）}=139

第四階段

dist（S）=min{dist（G）+d（G，S），dist（H）+d（H，S）}=20

由上面分析可得最短路徑為S-B-E-G-S，可得原VANET的最佳路由路徑。同時為了選擇出次于最佳路徑的次級路徑，在建立該最有路徑后，我們刪除其中最優(yōu)路徑中已經(jīng)出現(xiàn)的點，得到如圖5所示的另一個最短路徑問題，通過求解這個問題，我們可以得到一個點不想交的次級路由S-A-D-H-D

2.3 協(xié)議描述

1）鄰居表的建立和維護

為了建立多路徑路由，需要每一個節(jié)點維護一個鄰居節(jié)點表，其中保存該車輛在一跳范圍內(nèi)可到達(dá)的其他節(jié)點。每一個節(jié)點周期性地向周圍廣播一個hello報文，其中包括自身的位置信息等，報文結(jié)構(gòu)如圖6所示。

Type：報文類型；

Direction：運動方向，由于協(xié)議假設(shè)中設(shè)定所有車輛都在同一直線道路上行駛，所以運動方向可以簡單的由0和1表示；

Speed：行駛速度；

Lon，Lat：車輛經(jīng)緯度信息，用來計算兩車之間的距離；

ID：車輛的唯一標(biāo)識符。

鄰居節(jié)點表結(jié)構(gòu)如圖7所示：

其中Direction表示該鄰居節(jié)點與本節(jié)點的行駛方向是否相同，0表示不同，1表示相同，Distance表示兩節(jié)點間的距離，可以通過經(jīng)緯度信息計算。

2）發(fā)送請求報文

當(dāng)一個節(jié)點D請求一個視頻數(shù)據(jù)data時，節(jié)點D首先需要廣播一個請求報文，其中包括自身信息和需要請求的視頻數(shù)據(jù)信息，報文結(jié)構(gòu)如圖8所示。

當(dāng)任意節(jié)點接收到這個報文信息時，首先檢查自身存儲中是否擁有請求的視頻數(shù)據(jù)，如果沒有，則將這條報文信息轉(zhuǎn)發(fā)給鄰居節(jié)點，如果有，則該節(jié)點將作為源節(jié)點，準(zhǔn)備傳輸視頻數(shù)據(jù)給請求節(jié)點。

3）建立路由

當(dāng)源節(jié)點準(zhǔn)備傳輸數(shù)據(jù)前首先要建立從源節(jié)點到請求節(jié)點（目標(biāo)節(jié)點）的主要路由和次級路由，為了建立這個路由，源節(jié)點首先向目標(biāo)節(jié)點方向的鄰居節(jié)點發(fā)送一個建立路由報文信息，其中包括目標(biāo)節(jié)點ID和當(dāng)前節(jié)點和源節(jié)點的距離dist（該距離在2.2小節(jié)中給出）和從源節(jié)點到當(dāng)前節(jié)點的路徑，報文結(jié)構(gòu)如圖9所示。

當(dāng)鄰居節(jié)點接收到這個報文后，首先計算本節(jié)點和源節(jié)點的距離dist，如果當(dāng)前節(jié)點是目標(biāo)節(jié)點，則向源節(jié)點返回一個開始發(fā)送視頻信息的報文，如果當(dāng)前節(jié)點不是目標(biāo)節(jié)點，則首先廣播一個建立路由報文信息給目標(biāo)節(jié)點方向的鄰居節(jié)點，然后向源節(jié)點返回包含自身信息的報文。

通過以上步驟，當(dāng)目標(biāo)節(jié)點返回報文給源節(jié)點時，源節(jié)點已獲得源節(jié)點到目標(biāo)節(jié)點之間所有中間節(jié)點的信息，源節(jié)點通過2.2小節(jié)所描述的動態(tài)規(guī)劃算法可以得出兩條點不相交的路由。

3 仿真實驗

為了驗證上述多路由路徑發(fā)現(xiàn)協(xié)議的正確性和效率，我們使用SUMO+NS3對上述多通道視頻傳輸進行模擬。

我們設(shè)置了一條雙向四通道的直線道路，如圖10所示，我們在2km距離的道路上分別不同的車輛密度和平均車輛速度來觀察來觀察在不同車輛密度的情況下上述路由協(xié)議的表現(xiàn)。

通過修改車輛流的數(shù)量我們可以實現(xiàn)不同車輛密度下的實驗，同時通過設(shè)置車輛流中車輛的車輛類型中的平均速度可以實現(xiàn)不同車輛速度下的實驗。

首先我們測試不同車輛密度對視頻傳輸?shù)挠绊?，我們把車輛數(shù)分別設(shè)置為10、20、30、35、40來觀察在不同車輛密度下路由協(xié)議的效率。測試參數(shù)如表1。

從圖11中可以看到隨著車輛數(shù)的增加，三種路由協(xié)議的端到端延時都逐漸降低，這是由于當(dāng)車輛數(shù)增加時，可供選擇的中間節(jié)點也增多，都可以建立更優(yōu)質(zhì)的路由路徑，但是可以看到隨著車輛數(shù)的增加AODV和DSDV兩種路由協(xié)議比多路徑路由協(xié)議收斂得更快，這是因為AODV和DSDV在車輛數(shù)達(dá)到一定程度時已經(jīng)達(dá)到了自己的最好情況，無法再利用更多的資源，而在某一中間節(jié)點發(fā)生阻塞時可能影響所有后面數(shù)據(jù)包的傳輸，而多路徑路由可以盡可能地利用當(dāng)前的節(jié)點資源，可能在更穩(wěn)定的環(huán)境下獲得更好的效率。

相比于MERVS協(xié)議，雖然在車輛數(shù)較少時和該文協(xié)議有著相差不大的端到端延時，但是當(dāng)車輛數(shù)增多時該文提出的協(xié)議較MERVS有著較明顯的提升，這是由于在車輛數(shù)較少時，可供選擇的中間節(jié)點較少，兩種協(xié)議所選擇的中間節(jié)點的差距不大，但是當(dāng)中間節(jié)點增加時，該文協(xié)議可以選擇更優(yōu)質(zhì)的中間路徑以獲得更好的端到端延時。

從圖12中可以看出，當(dāng)車輛數(shù)較少時，多路徑路由協(xié)議比AODV和DSDV具有更高的丟包率，這是因為當(dāng)車輛數(shù)較少時，多路徑路由建立的次級路由可能非常不穩(wěn)定，這時使用這條次級路由傳輸?shù)臄?shù)據(jù)包的丟包率會較高，當(dāng)時當(dāng)車輛數(shù)增多時多路徑路由可以達(dá)到更低的丟包率，這是因為當(dāng)網(wǎng)絡(luò)環(huán)境穩(wěn)定時，使用多路徑路由可以更多地避免競爭引起的丟包。值得注意的是當(dāng)車輛數(shù)達(dá)到一定數(shù)量時，三種路由協(xié)議的丟包率都開始上升，這是因為當(dāng)車輛數(shù)增多時，三種路由協(xié)議建立時的中間節(jié)點可能更多，一個數(shù)據(jù)包從發(fā)送節(jié)點到達(dá)接收節(jié)點的中間節(jié)點增多，丟包的可能性也隨之增加。