魏大堯

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

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

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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ù)端計(jì)算平臺(tái)構(gòu)成，車載自組網(wǎng)絡(luò)負(fù)責(zé)數(shù)據(jù)收集，數(shù)據(jù)傳輸?shù)裙ぷ?，服?wù)端負(fù)責(zé)匯總信息，計(jì)算所需要的數(shù)據(jù)等。該文主要針對(duì)車載自組網(wǎng)絡(luò)進(jìn)行研究。

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

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

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

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

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

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

1）行駛方向

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

2）行駛速度

如圖2所示，圖中所有節(jié)點(diǎn)均向右行駛，S為當(dāng)前節(jié)點(diǎn)，p和q為S的鄰居節(jié)點(diǎn)，S在p和q之間選擇下一跳節(jié)點(diǎn)，S和q行駛速度為70km/h，p行駛速度為100km/h。可以看到理想情況下S和q之間的連接會(huì)一直存在，而p節(jié)點(diǎn)將逐漸駛離S節(jié)點(diǎn)，S節(jié)點(diǎn)和p節(jié)點(diǎn)之間的連接將會(huì)失效，所以q節(jié)點(diǎn)是相對(duì)于p節(jié)點(diǎn)更好的下一跳節(jié)點(diǎn)。

2.2 理論描述

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

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

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

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

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

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

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

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

可以將該問題分為四個(gè)階段：

第一階段：

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的最佳路由路徑。同時(shí)為了選擇出次于最佳路徑的次級(jí)路徑，在建立該最有路徑后，我們刪除其中最優(yōu)路徑中已經(jīng)出現(xiàn)的點(diǎn)，得到如圖5所示的另一個(gè)最短路徑問題，通過求解這個(gè)問題，我們可以得到一個(gè)點(diǎn)不想交的次級(jí)路由S-A-D-H-D

2.3 協(xié)議描述

1）鄰居表的建立和維護(hù)

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

Type：報(bào)文類型；

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

Speed：行駛速度；

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

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

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

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

2）發(fā)送請(qǐng)求報(bào)文

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

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

3）建立路由

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

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

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

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

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

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

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

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

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

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

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