黃德玲，邱忠權(quán)，彭大芹

(1.西南交通大學 信息科學與技術學院，成都 610031; 2.重慶郵電大學 軟件工程學院，重慶 400065；3.西南交通大學 交通運輸與物流學院，成都 610031)

0 引 言

21世紀以來，車輛自組織網(wǎng)絡(vehicular ad-hoc networks,VANET)區(qū)別于普通的移動自組織網(wǎng)絡，開始受到廣泛的關注[1]。隨著VANET的日益成熟，網(wǎng)絡的接入層已形成802.11p等國際標準，然而相關的路由協(xié)議卻因其網(wǎng)絡拓撲的快速變化，面臨很大的挑戰(zhàn)。

文獻[2]采用了基于地理位置的眾包方式來轉(zhuǎn)發(fā)數(shù)據(jù)分組，采用合作眾包的方式獲取信息外包任務，該算法需要建設路邊單元來輔助完成任務。文獻[3]采用偏愛組播的方式廣播數(shù)據(jù)包，在組播過程發(fā)現(xiàn)的路徑中選擇代價最小的一條作為算法所確定的路由，該算法采用改進的貪婪轉(zhuǎn)發(fā)方式轉(zhuǎn)發(fā)數(shù)據(jù)分組。Shukla[4]利用GPS反饋的交通實時信息建立基于道路的包轉(zhuǎn)發(fā)路徑，并篩選出最優(yōu)的轉(zhuǎn)發(fā)節(jié)點。Bilal[5]對基于地理位置的VANET路由協(xié)議進行了分析比較研究?，F(xiàn)有城市環(huán)境下基于地理位置的車聯(lián)網(wǎng)路由協(xié)議多是基于GPSR(greedy perimeter stateless routing)協(xié)議的貪婪轉(zhuǎn)發(fā)思想來實現(xiàn)的。貪婪轉(zhuǎn)發(fā)算法選擇的轉(zhuǎn)發(fā)節(jié)點是距離發(fā)送點最遠的節(jié)點，這些節(jié)點往往處于無線傳輸半徑的邊緣。由于無線傳輸衰減和車輛高速移動，這種節(jié)點在轉(zhuǎn)發(fā)過程中與源節(jié)點之間的連接斷開的可能性較大，從而導致路由中斷，降低路由性能。本文提出一種能感知交通密度的機會轉(zhuǎn)發(fā)路由協(xié)議(traffic aware opportunistic routing protocol,TAO)，該協(xié)議將機會轉(zhuǎn)發(fā)的思想引入到車載自組織網(wǎng)絡中，根據(jù)節(jié)點的實時地理位置等信息，動態(tài)地確定收到數(shù)據(jù)包的節(jié)點作為下一跳中繼節(jié)點的優(yōu)先權(quán)，能在較少增加數(shù)據(jù)通信量的前提下，選拔出優(yōu)秀的中繼節(jié)點。在提出的算法中，結(jié)合車輛的運動特征預估車輛節(jié)點的位置信息，同時也考慮了道路上的車流量密度對數(shù)據(jù)轉(zhuǎn)發(fā)可靠性的影響，結(jié)合交通流量密度來選擇數(shù)據(jù)傳輸路徑，并在此基礎上實時地機會地選擇中繼節(jié)點。實驗驗證過程中，我們采用TIGER地圖作為背景，選擇真實的道路進行仿真實驗，并隨機選擇網(wǎng)絡中多對節(jié)點同時進行通信，研究TAO在傳輸時延、包投遞成功率和路由開銷等方面相對于其他幾種主流路由協(xié)議的性能。

1 問題分析與系統(tǒng)環(huán)境

1.1 問題分析

1.1.1 建立靜態(tài)路徑不適合動態(tài)的拓撲變換

得益于車載電子地圖，車輛自組織網(wǎng)絡的路由協(xié)議可以依據(jù)地圖信息計算出地圖上2個通信節(jié)點之間沿道路形態(tài)的最短路徑。傳統(tǒng)的車載自組織網(wǎng)絡的路由協(xié)議在產(chǎn)生數(shù)據(jù)包時，利用諸如Dijkstra之類的最短路徑算法，計算出從數(shù)據(jù)包源節(jié)點到目的節(jié)點的最短路徑[6]。因為車聯(lián)網(wǎng)絡中，車輛的行駛路線是受限的，必須按照道路的形態(tài)來移動，這種利用電子地圖來計算最短路徑的策略廣為研究路由協(xié)議的學者們所用。然而，在車聯(lián)網(wǎng)絡中一個不可忽略的特點是，車輛并非是均勻分布在地圖范圍內(nèi)的，一些道路上分布的車輛密度較小，不足以形成無線傳輸?shù)耐罚沟眠@類協(xié)議具有理論路由實際并不可用的風險。

1.1.2 貪婪轉(zhuǎn)發(fā)限制包投遞率

依據(jù)無線通信的特點，信號隨著傳輸距離的增加會發(fā)生衰減，其衰減率取決于衰減參數(shù)的值。研究發(fā)現(xiàn)在通信范圍內(nèi)的節(jié)點不一定都能成功地收到數(shù)據(jù)包，而在通信范圍之外的節(jié)點也不一定都不能收到數(shù)據(jù)包。然而，在采用貪婪轉(zhuǎn)發(fā)的路由算法中，每一次轉(zhuǎn)發(fā)，節(jié)點總是選擇最遠卻具有較高傳輸失敗率的鄰居，這直接導致了丟包率增加。改進的貪婪轉(zhuǎn)發(fā)算法中，一般會考慮速度與方向等因素，避免選擇距離最遠的鄰居來確保較高的轉(zhuǎn)發(fā)成功率，而那些能帶來更長單跳步進長度的節(jié)點卻也因此失去了轉(zhuǎn)發(fā)的可能性，進而轉(zhuǎn)發(fā)次數(shù)與時延隨之增加。因此，在路口節(jié)點之間，采用何種方式傳遞數(shù)據(jù)包才能有效提高數(shù)據(jù)包的投遞成功率，是急需解決的一個問題。

1.1.3 路由控制信息開銷過大

在選擇路口節(jié)點時候，動態(tài)的選擇算法可以考慮交通密度在內(nèi)的多種實時交通狀態(tài)，但交通密度感知的準確度和計算開銷有待嚴格控制?，F(xiàn)有的很多路由算法在實現(xiàn)過程中，需要大量的附加信息輔以計算，這些信息均需要通過選擇周期性地網(wǎng)絡廣播來實現(xiàn)共享，產(chǎn)生較大的路由開銷[7]。同時，這些由于路由策略的計算需求而產(chǎn)生的路由控制開銷，會大量消耗有限的無線網(wǎng)絡資源，路由性能也受較大影響。因此，合理控制路由協(xié)議開銷，是本方案要解決的又一個關鍵問題。

1.2 系統(tǒng)環(huán)境

本文討論的VANET路由協(xié)議主要適用于城市環(huán)境，隨著GPS系統(tǒng)和電子地圖的普及，加之車輛節(jié)點幾乎不受限的能源供給和充足的計算處理能力，我們?yōu)楸疚挠懻摰穆酚蓞f(xié)議采用如下假設。

1)網(wǎng)絡中的每一個車輛節(jié)點均配有短距離通信模塊(DSRC設備)，并能通過GPS車載設備獲取到自己的地理位置信息

2)每個節(jié)點能通過諸如網(wǎng)格位置服務(grid location service，GLS)[8]的位置服務獲取其通信目的節(jié)點的位置。

3)每個節(jié)點可以通過預先植入的電子地圖獲取到街道的詳細信息，包括與其所在路段鄰接的路口的地理位置等信息。(目前許多車輛都預置了這樣的信息，市面上也存在很多商用的電子地圖。)

4)每個節(jié)點可以通過分布式部署的無需基礎設施的交通信息系統(tǒng)(infrastructure-free traffic information system，IFTIS)[9]獲取到實時的交通密度信息(2個相鄰路口之間的車輛節(jié)點個數(shù))?；蛘咭部梢酝ㄟ^車輛節(jié)點或部署在路口的傳感器節(jié)點實現(xiàn)一個簡單的分布式機制以提供此類交通密度信息，并隨路由數(shù)據(jù)包一同擴散。

2 協(xié)議設計

在城市環(huán)境中進行路由選擇的2個關鍵問題是：①如何在路口或數(shù)據(jù)包最初的產(chǎn)生源為數(shù)據(jù)包選擇合適的轉(zhuǎn)發(fā)方向，即確定途經(jīng)路口序列；②如何在確定路口后為數(shù)據(jù)包選擇最優(yōu)的下一跳中繼節(jié)點。以下從這2方面來介紹本文提出的TAO算法的基本設計思路。

2.1 密度感知的路口選擇策略

把路口選擇設計成動態(tài)的決策過程，而非預先靜態(tài)計算，以此適應VANET變化的動態(tài)拓撲結(jié)構(gòu)。動態(tài)的路口選擇發(fā)生在產(chǎn)生數(shù)據(jù)包的源節(jié)點和位于路口的轉(zhuǎn)發(fā)節(jié)點。設D是目標節(jié)點，Jc是當前交叉路口，需要選擇路口的節(jié)點對相鄰的所有路口Ji,i=1,2,3,…按公式(1)進行計算得分。

(1)

(1)式中：Dcd是當前計算節(jié)點與D之間的歐幾里得距離；Dci是從Jc到Ji的沿道路形態(tài)的路徑長度；Navg是平均車輛密度；Did是從Ji到D的沿道路形態(tài)的路徑長度；Ncon是能提供節(jié)點之間良好連接度的理想車輛密度；α是路口位置離最終目的節(jié)點距離的權(quán)重因子；β是所選道路密度的權(quán)重因子，且α+β=1。通過公式(1)計算的路口得分由2個部分組成：①由待選路口與目標節(jié)點間基于道路形態(tài)的距離確定；②由連接待選路口的道路車輛密度確定，通過調(diào)節(jié)α與β的值，可以控制距離和車輛密度對路口判分過程的影響。通過公式(1)計算出的得分最高路口，被選為下一個數(shù)據(jù)包必經(jīng)的交叉路口。

通過計算評估，使數(shù)據(jù)包的預置傳輸路徑最短，同時考慮到了該路段的交通密度，路口的選擇隨數(shù)據(jù)包的傳輸動態(tài)地逐次確定，確保所選路段有足夠多的車輛以形成無線通信通路。這種兼顧距離和實時交通密度的方法，使得路口選擇更合理，算法也具有更好的魯棒性。

2.2 直路數(shù)據(jù)轉(zhuǎn)發(fā)策略

2.2.1 確定候選轉(zhuǎn)發(fā)集

當確定了數(shù)據(jù)包的下一個必經(jīng)路口之后，TAO采用機會轉(zhuǎn)發(fā)的方式來完成數(shù)據(jù)包從當前節(jié)點到下一個路口的轉(zhuǎn)發(fā)工作。

機會轉(zhuǎn)發(fā)的第一個任務是確定轉(zhuǎn)發(fā)集?，F(xiàn)有的機會路由協(xié)議，轉(zhuǎn)發(fā)集的計算都是由當前執(zhí)行轉(zhuǎn)發(fā)任務的節(jié)點確定，并將該集合中的轉(zhuǎn)發(fā)節(jié)點按優(yōu)先順序排好形成列表，然后把該列表附加在待發(fā)送數(shù)據(jù)包中，一起發(fā)送出去。收到該數(shù)據(jù)包的節(jié)點，從數(shù)據(jù)包頭部查看列表，確定自己是否處于轉(zhuǎn)發(fā)集列表中，從而確定是否參與數(shù)據(jù)包轉(zhuǎn)發(fā)。

TAO去掉了會帶來較大路由開銷的轉(zhuǎn)發(fā)集字段。當前節(jié)點只需要查詢自己的鄰居節(jié)點表，把其中離最終目的節(jié)點最近的一個鄰居選做最佳轉(zhuǎn)發(fā)節(jié)點BestFor，將其ID附加于數(shù)據(jù)包的首部轉(zhuǎn)發(fā)出去即可，TAO的數(shù)據(jù)包的頭部如圖1所示。

圖1 TAO數(shù)據(jù)分組頭部結(jié)構(gòu)Fig.1 Packet Header of TAO

圖1中，Dest是數(shù)據(jù)的最終目的ID，TarJun是通過公式(1)計算出來的最佳下一路口ID，BestFor是距離目的節(jié)點最近的鄰居節(jié)點，Tag標志了節(jié)點的位置特性，如果是路口節(jié)點，該域被置為 1，否則被置為 0，Source是產(chǎn)生數(shù)據(jù)包的始源節(jié)點，ThisHop是當前節(jié)點，PayloadLen是數(shù)據(jù)部分的長度，SerNum是當前數(shù)據(jù)包的序列號。

設消息是從源點S到目的節(jié)點D，每個節(jié)點與D的近似度用ω(i)表示，可以通過測量i和D之間的距離來確定。則每個節(jié)點可以增加階整數(shù)索引，且ω(1)<ω(2)<…<ω(n)，其中，n是節(jié)點數(shù)。設i的鄰居節(jié)點集由Bi表示，節(jié)點i的候選轉(zhuǎn)發(fā)集由Fi表示，則Fi中的節(jié)點必須滿足以下2個條件：①Fi?Bi;②?j∈Fi，ω(j)<ω(i)。

在直路段上收到數(shù)據(jù)包的節(jié)點，首先使用公式(2)，通過BestFor的位置信息和自己的位置信息計算自己是否位于節(jié)點i的轉(zhuǎn)發(fā)集Fi中。

(2)

(2)式中：long和lat是節(jié)點自己的經(jīng)度和緯度;long_B和lat_B分別是離目標節(jié)點最近的鄰居節(jié)點BestFor的經(jīng)緯度;r是無線傳輸?shù)男盘柛采w范圍。通過公式(2)確定的候選節(jié)點轉(zhuǎn)發(fā)集為圖2所示的陰影部分，圖2為候選轉(zhuǎn)發(fā)集的確定，其中，C是當前節(jié)點；B是其鄰居節(jié)點中離目標節(jié)點D最近的節(jié)點。

圖2 候選轉(zhuǎn)發(fā)集的確定Fig.2 Constructing the candidate forward list

在候選轉(zhuǎn)發(fā)集中，TAO僅允許一個節(jié)點成為下一跳中繼節(jié)點，轉(zhuǎn)發(fā)集中的所有節(jié)點都會暫存收到的數(shù)據(jù)包，直到發(fā)現(xiàn)有其它節(jié)點轉(zhuǎn)發(fā)了該數(shù)據(jù)包，或轉(zhuǎn)發(fā)定時器觸發(fā)其轉(zhuǎn)發(fā)該數(shù)據(jù)包。因為只有優(yōu)先權(quán)最高的節(jié)點會轉(zhuǎn)發(fā)數(shù)據(jù)包，所以，設Pdi,j為節(jié)點j轉(zhuǎn)發(fā)所接收到的來自i的數(shù)據(jù)包的概率，則有

(3)

(3)式中，Pti,j是數(shù)據(jù)包直接從i成功轉(zhuǎn)發(fā)到j的概率。這是該時隙中的唯一轉(zhuǎn)發(fā)節(jié)點，我們用具有單一吸收態(tài)的馬爾科夫鏈描述這個過程，如圖3所示。

圖3 具有單一吸收態(tài)的馬爾科夫鏈Fig.3 Markov chain with single absorbed states

在狀態(tài)轉(zhuǎn)換圖中，每個狀態(tài)表示當前接收節(jié)點，每2個狀態(tài)之間的轉(zhuǎn)換指的是這2個節(jié)點之間的成功傳輸，而吸收態(tài)指的是目的節(jié)點。如果數(shù)據(jù)包成功傳輸，則狀態(tài)轉(zhuǎn)移到下一個狀態(tài)，否則，將保持在當前狀態(tài)。如此循環(huán)，直至到達狀態(tài)N(即目標節(jié)點)為止。因此，停留在當前狀態(tài)的概率可以表示為

(4)

為之建立了一個N×N的上三角矩陣，其中元素為所有節(jié)點i到下一跳轉(zhuǎn)發(fā)節(jié)點j的轉(zhuǎn)移概率Pdi,j。

(5)

方便起見，把DS,D表示為

(6)

(6)式中：Q是到達目的節(jié)點之前的傳輸概率；R=[Pd1,NPd2,N…PdN-1,N]T表示從節(jié)點1,2，…，N-1直接發(fā)送數(shù)據(jù)包到N的概率。通過這個矩陣，我們給出在有N個節(jié)點參與轉(zhuǎn)發(fā)的VANET中，確定傳輸次數(shù)期望值的方法如定理1，在具體應用中予以預估路由性能。

定理1在一次具有N個節(jié)點參與的轉(zhuǎn)發(fā)中，從源節(jié)點到目的節(jié)點的轉(zhuǎn)發(fā)次數(shù)的期望值是向量F1的第一個元素的值。其中，F(xiàn)=(I+Q+Q2+…)=(I-Q)-1,I是單位矩陣，l是長度為N-1的列向量，其中元素值為1。

(7)

(7)式中，從節(jié)點i經(jīng)k步轉(zhuǎn)移傳輸?shù)焦?jié)點j的概率是Qk的第i行第j列的元素值。

(8)

如此，矩陣F的第i行第j列的元素便是從狀態(tài)i到狀態(tài)j時的轉(zhuǎn)發(fā)次數(shù)期望值。令e=FI，則e的第一個元素值便是從源節(jié)點到目的節(jié)點的轉(zhuǎn)發(fā)次數(shù)期望值。

2.2.2 確定轉(zhuǎn)發(fā)優(yōu)先權(quán)

在機會轉(zhuǎn)發(fā)方式中，轉(zhuǎn)發(fā)集的構(gòu)成是影響路由性能的一個重要因素。持有數(shù)據(jù)包的節(jié)點在轉(zhuǎn)發(fā)時廣播數(shù)據(jù)包，僅有處于當前節(jié)點轉(zhuǎn)發(fā)集中的車輛節(jié)點才有可能成為下一跳中繼節(jié)點，因此，一個較大的轉(zhuǎn)發(fā)集可以增加轉(zhuǎn)發(fā)的成功率。然而為了擴大轉(zhuǎn)發(fā)集，將部分轉(zhuǎn)發(fā)成功率雖高但單跳步進長度短的節(jié)點選入是得不償失的。因此，為了最優(yōu)化路由協(xié)議，需要對轉(zhuǎn)發(fā)集中的節(jié)點進一步設置競爭機制，確保在增加轉(zhuǎn)發(fā)成功率的同時獲取更大的單跳步進長度。TAO為此設置了一個轉(zhuǎn)發(fā)定時器，這個定時器使得離目標節(jié)點越近的鄰居，具有越高的轉(zhuǎn)發(fā)優(yōu)先權(quán)，轉(zhuǎn)發(fā)集中的節(jié)點按優(yōu)先級的高低來啟動轉(zhuǎn)發(fā)，只有在優(yōu)先權(quán)較高的節(jié)點未成功轉(zhuǎn)發(fā)的前提下，優(yōu)先級較低的節(jié)點才啟動轉(zhuǎn)發(fā)。為此，圖2中的轉(zhuǎn)發(fā)集中節(jié)點N在收到數(shù)據(jù)包時啟動一個按公式(9)設定的發(fā)送定時器。

(9)

(9)式中：CB是節(jié)點C和最佳轉(zhuǎn)發(fā)節(jié)點B之間的距離；CN是節(jié)點C和鄰居N之間的距離；BN是節(jié)點B和鄰居N之間的距離，max{BNi+CNi}表示BNi與CNi距離之和的最大值；Ni表示候選節(jié)點集中的任意一個節(jié)點；Tr是重傳定時器，設置為2×Prop+D，其中，Prop是廣播數(shù)據(jù)包到達目的節(jié)點并返回的傳輸時延,D是媒體接入層采用的隨傳輸速率和處理時間變化的最大轉(zhuǎn)發(fā)時延。節(jié)點只有在定時器時間結(jié)束但仍未收到重復數(shù)據(jù)包時，才需啟動轉(zhuǎn)發(fā)。通過(9)式設置的延遲轉(zhuǎn)發(fā)定時器，使得B在成功收到數(shù)據(jù)包后能立刻轉(zhuǎn)發(fā)，獲得最高轉(zhuǎn)發(fā)優(yōu)先權(quán)；同時使得其他節(jié)點的定時器時間隨距離最佳轉(zhuǎn)發(fā)節(jié)點之間距離的遞增而遞增，相應的轉(zhuǎn)發(fā)優(yōu)先權(quán)逐次遞減，以此控制轉(zhuǎn)發(fā)集中的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包的優(yōu)先順序。與此同時，每個轉(zhuǎn)發(fā)集中的節(jié)點在轉(zhuǎn)發(fā)數(shù)據(jù)包之前，還需要判斷自己是否處于路口范圍內(nèi)，如果是路口節(jié)點，則設置Tag域為1，否則為0。當數(shù)據(jù)包的Tag域是由0變?yōu)?的時候，說明數(shù)據(jù)包從直路段抵達路口，此時需要啟動2.1節(jié)的路口選擇算法來選擇數(shù)據(jù)包的下一個最佳路口，并將計算結(jié)果用于更新TarJun字段。

2.2.3 轉(zhuǎn)發(fā)性能

雖然設置了轉(zhuǎn)發(fā)優(yōu)先權(quán)，但轉(zhuǎn)發(fā)集中的節(jié)點彼此都在對方的傳輸范圍內(nèi)，且無法排除某些相距甚短的節(jié)點因存在定時器值相同或相差無幾而同時發(fā)送數(shù)據(jù)包的情況。

假設車輛節(jié)點按泊松分布于道路上，網(wǎng)絡密度為β，也即是在長度為l的道路上有k輛車的概率P(k,l)為

(10)

設無線傳輸范圍為R，則道路上一個車輛節(jié)點傳輸范圍內(nèi)鄰居節(jié)點期望個數(shù)為2βR，每個車輛節(jié)點收到數(shù)據(jù)包服從到達率為γ的泊松過程。用p0表示每個車輛節(jié)點至少有一個數(shù)據(jù)包準備發(fā)送的概率，則車輛在一個時隙內(nèi)會發(fā)送數(shù)據(jù)包的概率可表示為

(11)

因此，一個即將發(fā)送數(shù)據(jù)包的節(jié)點探測到信道被占用的概率可表示為

(12)

假設轉(zhuǎn)發(fā)集中的節(jié)點S和U均同時探測到系統(tǒng)信道是空閑的，S與U之間的距離為x，若S發(fā)送數(shù)據(jù)包給U，為了不影響U接收，則當前時隙在[-(R-x),R]都不能有數(shù)據(jù)傳輸。當前時隙在[0,R]的平均節(jié)點個數(shù)為βRγ，設節(jié)點V離S的距離為z，-(R-x)

Ps(z,x)=τ(1-βzγT(1-(1-e-βRτ)/2))

(13)

如此，在該時隙內(nèi)發(fā)送數(shù)據(jù)包從而與節(jié)點S發(fā)出的數(shù)據(jù)包發(fā)生沖突的平均節(jié)點數(shù)為

則

(14)

因此，在泊松分布下節(jié)點U的接收范圍內(nèi)無節(jié)點在該時隙發(fā)送數(shù)據(jù)導致與S節(jié)點發(fā)送的數(shù)據(jù)沖突的概率可表示為

(15)

2.3 恢復策略

數(shù)據(jù)包在遭遇鏈接中斷，即候選轉(zhuǎn)發(fā)集為空的時候，立刻啟動恢復策略，采用公式(16)為當前節(jié)點的鄰居節(jié)點評分，包括其自身。

score(N)=m×[γ(1-d/L)+λ(v/vmax)]

(16)

(16)式中：d是被評分的節(jié)點與目標路口之間的距離；v是被評分節(jié)點的行駛速度；L是當前路段的長度，vmax是當前路段的限速；γ是長度權(quán)重因子；λ是速度權(quán)重因子，且γ+λ=1；m是方向因子，朝向目標路口行駛時設置為1，反之設置為-1。如果通過計算發(fā)現(xiàn)自己得分最高，則放棄該數(shù)據(jù)包的投遞。

3 實驗與分析

3.1 實驗環(huán)境

仿真實驗將TAO與GSR[10]，GyTAR[11]和E-GyTAR[12]3種針對VANET設計的路由協(xié)議對比研究。選擇GSR和GyTAR是因為其較為廣泛地被作為研究基于地理位置的VANET路由協(xié)議的基準參考，特別是穩(wěn)定性較好的GyTAR，許多研究者都對其進行了改進和完善[13]，以設計出更可靠的高效的車載自組織網(wǎng)絡路由協(xié)議，E-GyTAR便是其中一個對其進行改進的路由協(xié)議，而本文的工作也有部分是建立在GyTAR提出的思想理念的基礎上的。

實驗采用NS-2仿真器來仿真網(wǎng)絡協(xié)議，選用VANetMobiSim的移動模型IDM_IM來產(chǎn)生車輛的運動軌跡，媒體控制協(xié)議采用802.11p，同時在其中實現(xiàn)了概率性信道衰減模型Nakagami。每一次仿真運行都隨機選擇網(wǎng)絡中20%的節(jié)點作為發(fā)送和接收的通信節(jié)點對。仿真參數(shù)設置如表1所示。

表1 仿真參數(shù)設置

實驗評測的性能指標包括包投遞率、平均傳輸延遲和歸一化路由開銷，分別定義如下。

1)包投遞率。成功到達目的節(jié)點的數(shù)據(jù)包個數(shù)和源節(jié)點產(chǎn)生的數(shù)據(jù)包個數(shù)的比值。

2)平均傳輸延遲。從源節(jié)點成功到達目的節(jié)點的數(shù)據(jù)包的平均端到端延遲。這個延遲包括在路由發(fā)現(xiàn)時的計算處理時延、接口隊列排隊時延、MAC層重傳的時延、傳播時延和發(fā)送時延。

3)歸一化路由開銷。控制分組的總流量和成功到達目的節(jié)點的數(shù)據(jù)分組的總流量的比值。對于經(jīng)過多跳的控制分組，每一跳傳輸計算一次。

3.2 實驗分析

3.2.1 包投遞率的影響

在實驗環(huán)境下，針對每一種協(xié)議，改變網(wǎng)絡中車輛節(jié)點的個數(shù)，記錄了每一次通信的包投遞結(jié)果，計算出包投遞成功率如圖4所示。在所比較的4種路由機制下，包投遞成功率都會隨節(jié)點密度的增加而增加，這是因為密度越大，網(wǎng)絡的聯(lián)通性越好，節(jié)點之間的連接斷開的可能性越小。因為TAO采用了機會的數(shù)據(jù)包轉(zhuǎn)發(fā)方式，較好地利用了所有連接可能性，增大了包投遞成功率，用實現(xiàn)數(shù)據(jù)驗證了2.2小節(jié)分析的轉(zhuǎn)發(fā)效率。TAO的包投遞成功率明顯優(yōu)于GSR，是因為其摒棄了GSR的靜態(tài)地路徑選擇機制，采用動態(tài)選擇機制在包轉(zhuǎn)發(fā)過程中，依據(jù)實時的網(wǎng)絡情況來動態(tài)地逐次地確定數(shù)據(jù)包即將經(jīng)歷的下一條道路，確保所選路段的交通密度足以完成數(shù)據(jù)包的轉(zhuǎn)發(fā)，從而大大降低了丟包率。

另外，雖然GyTAR和E-GyTAR采用了改進的貪婪轉(zhuǎn)發(fā)機制，包投遞成功率相比GSR有顯著提高，但仍低于本文提出的TAO協(xié)議。這是因為TAO不要求所有數(shù)據(jù)包均要在交叉路口轉(zhuǎn)發(fā)，交叉路口的通信流量不會隨數(shù)據(jù)包總量增加而顯著增加，轉(zhuǎn)發(fā)沖突和因此帶來的丟包率都得以有效控制。

圖4 包投遞成功率vs車輛節(jié)點數(shù)Fig.4 PDR vs number of vehicles

3.2.2 平均傳輸延遲的影響

在實驗過程中，我們同時記錄了4種協(xié)議運作下的平均傳輸時延。由于GSR對變化拓撲的適應性較差，每一次拓撲變化都會導致觸發(fā)一次新的路由發(fā)現(xiàn)與計算過程，耗費大量計算時間。同時GSR沒有考慮交通密度的因素，選路結(jié)果不能確保連接成功建立，而連接斷開時導致的攜帶轉(zhuǎn)發(fā)過程也增加了端到端時延。相比之下，GyTAR和E-GyTAR采用了改進的貪婪轉(zhuǎn)發(fā)機制，能夠較好地適應動態(tài)變化的拓撲，及時修正路由，減少端到端傳輸時延。然而數(shù)據(jù)包轉(zhuǎn)發(fā)選擇機制設置不當，使數(shù)據(jù)包容易陷入局部最優(yōu)，之后不啟用適當?shù)幕謴筒呗?，盲目采用DTN的“攜帶-伺機轉(zhuǎn)發(fā)”恢復機制使得大量數(shù)據(jù)包經(jīng)歷不適宜的攜帶，大大增加了端到端時延。TAO基于交通密度，精確計算轉(zhuǎn)發(fā)節(jié)點，改進機會轉(zhuǎn)發(fā)機制，雖然在轉(zhuǎn)發(fā)過程中的計算開銷較大，但是在路徑選擇上的優(yōu)勢彌補了這塊時間開銷。實驗結(jié)果證實，在包投遞率大大增加的情況下，端到端時延仍與GyTAR和E-GyTAR保持基本相當?shù)乃?，如圖5所示。

圖5 端到端時延vs車輛節(jié)點個數(shù)Fig.5 End-to-end delay vs number of vehicles

3.2.3 路由開銷的影響

實驗過程中記錄了每一種協(xié)議的路由開銷隨網(wǎng)絡密度的變化，并計算出相應的歸一化路由開銷，結(jié)果如圖6所示。由圖6可見，TAO雖然使用了機會轉(zhuǎn)發(fā)的方式，但是由于將轉(zhuǎn)發(fā)集的計算交由接收到數(shù)據(jù)包的節(jié)點自己去完成，而非由數(shù)據(jù)包攜帶整個轉(zhuǎn)發(fā)集，其路由開銷比SRPMT小許多。GSR對變化拓撲的適應性較差，每一次拓撲變化都會導致觸發(fā)一次新的路由發(fā)現(xiàn)與計算過程，因此帶來相應的路由開銷。GyTAR表現(xiàn)出較好的歸一化路由開銷，是因為其僅使用基于地理位置的路由信息做轉(zhuǎn)發(fā)選擇，不涉及轉(zhuǎn)發(fā)集合的確定。

圖6 歸一化路由開銷vs車輛節(jié)點Fig.6 Normalized routing overhead vs number of vehicles

4 結(jié) 論

針對地理位置路由協(xié)議采用的貪婪轉(zhuǎn)發(fā)方式，在高動態(tài)拓撲的VANET中丟包率較高的問題，本文提出采用機會轉(zhuǎn)發(fā)方式來轉(zhuǎn)發(fā)數(shù)據(jù)，采用機會轉(zhuǎn)發(fā)適合無線傳輸介質(zhì)的特性，有效利用數(shù)據(jù)成功接收的每一個機會，在大多數(shù)情況下，數(shù)據(jù)包投遞成功率增幅超過10%。文章證明了所提出的轉(zhuǎn)發(fā)集的構(gòu)成方案，分析了通信過程中沖突發(fā)生的概率，證實了轉(zhuǎn)發(fā)集選擇和轉(zhuǎn)發(fā)定時器設置的數(shù)學依據(jù)。針對傳統(tǒng)的數(shù)據(jù)包攜帶轉(zhuǎn)發(fā)集的做法，TAO重新設計了轉(zhuǎn)發(fā)集形成機制，重構(gòu)了數(shù)據(jù)包頭部，在大多數(shù)情況下，歸一化路由開銷較傳統(tǒng)機會轉(zhuǎn)發(fā)方式降低幅度超過5%，進一步提高了路由協(xié)議的性能。

基于車輛節(jié)點固有的性質(zhì)，本文沒有對能量消耗進行專門的討論，在今后的工作中，可以在能量消耗上做進一步的分析研究，改進算法不僅適應于車輛自組織網(wǎng)絡，也可以用于其他一些能量受限的自組織網(wǎng)絡，增加路由協(xié)議的可擴展性。