鄭洪江，王會鮮，鮑 娟，陳 偉

(1.武漢理工大學 信息工程學院，湖北 武漢 430070；2.武漢理工大學 自動化學院，湖北 武漢 430070)

?

基于QoS的VANETs網絡分布式協作路由算法

鄭洪江1，王會鮮2，鮑 娟2，陳 偉2

(1.武漢理工大學 信息工程學院，湖北 武漢 430070；2.武漢理工大學 自動化學院，湖北 武漢 430070)

針對VANETs中車輛節(jié)點的高速移動性導致網絡的拓撲結構頻繁變化、通信鏈路頻繁斷裂，嚴重破壞了數據傳輸的可靠性和穩(wěn)定性，極大降低了網絡性能的情況，提出一種適用于VANETs的QoS分布式協作路由算法(LETB-AODV算法)。該算法在AODV路由協議的基礎上進行擴展，用鏈路連接失效時間(LET)和有效帶寬來建立雙重約束，通過選用最大 LET的鏈路構建最優(yōu)通信路由路徑。仿真結果表明，LETB-AODV協議比AODV協議能夠更有效地降低鏈路斷鏈率、丟包率和路由開銷，從而提高通信鏈路的穩(wěn)定性，增強網絡可靠性。

協作通信；QoS路由；鏈路連接失效時間；有效帶寬；分布式算法

車載網(vehicular ad hoc networks，VANETs)是一種特殊的移動自組織網絡(mobile ad hoc networks，MANETs)，具有自身獨特的特性，如車輛節(jié)點的高速移動性和運行軌跡的有限性等。這些特性導致了網絡的拓撲結構頻繁變化、通信鏈路穩(wěn)定性差，限制了車輛間的直接通信距離及網絡信息傳輸的有效性。近年來，隨著車載應用需求的不斷升級和車載應用業(yè)務的不斷拓展，人們對車載網絡的通信性能也提出了更高的要求。現有VANETs性能研究多是針對節(jié)點間單跳通信性能展開，如考慮通信信道性能損失、節(jié)點間信道競爭機制，對基于WAVE協議的VANETs網絡通信性能研究等。為進一步提高網絡性能，人們提出在車載網絡中采用多跳傳輸方式增加網絡連通度，提高通信容量。在多跳VANETs中，數據經多跳傳遞到達目的節(jié)點，而隨著多跳通信數目的增加，網絡的性能快速下降。因此，需要提供穩(wěn)定、可靠的路由機制作為前提條件來實現VANETs中車輛的高效、實時通信。

不失一般性，自組織網絡中節(jié)點的高速移動，增加了網絡鏈路斷裂的機率，也導致控制開銷的劇增。控制開銷消息主要有RREQ(route request)和RERR(route error)。在高速的VANETs中，頻繁的鏈路斷裂導致路由請求消息劇增，給網絡添加額外流量負擔，極大降低了網絡性能，嚴重破壞了數據傳輸的可靠性和穩(wěn)定性。因此，傳統(tǒng)的路由算法不適用于VANETs。為此，研究者提出了不同的方案對現有路由協議算法進行補充、完善和改進，以適應VANETs網絡的性能需求，如基于鏈路預測移動模型的路由算法[1-2]，基于車輛的位置、方向、速度和交通狀況等參數選擇的高速環(huán)境下的路由算法[3-4]，基于鏈路穩(wěn)定度的路由算法[5-7]，基于QoS的路由算法[8]，基于協作跨層協議的路由算法[9-10]。上述方案在一定條件下表現出了較好的路由性能，然而都是基于某些特定的假設條件，如車輛速度的正態(tài)分布、車輛節(jié)點間等距分布，與真實的VANETs環(huán)境不符，且鏈路的信息交換與預測使控制開銷加大，降低了網絡吞吐量，普適性較差。

因此，為有效增強VANETs網絡車載終端間通信的可靠性和穩(wěn)定性，筆者提出一種適用于VANETs的QoS分布式協作路由方案。該方案在AODV路由協議基礎上進行擴展，構建基于LET和有效帶寬雙重約束的最佳路徑選擇策略(簡稱為LETB-AODV路由協議)，為VANETs網絡車載終端間通信選擇穩(wěn)定、可用持續(xù)時間長的路徑建立路由，有效降低了路徑的斷裂率，提高了網絡性能。

1 網絡模型及問題描述

筆者將VANETs網絡用網絡圖G(V,E)表示，其中V={v1,v2,…,vn}表示網絡中n個移動車輛節(jié)點集合，E={e1,e2,…,em}表示網絡中m條鏈路集合，V和E隨著網絡拓撲的動態(tài)變化而變化。筆者假定每個車輛節(jié)點具有相同的傳輸距離，當節(jié)點i位于節(jié)點j的傳輸范圍內時，i與j成為一對鄰居節(jié)點并且它們之間存在一條傳輸鏈路eij(i,j∈V,eij∈E)。

將VANETs網中的QoS路由問題定義為：給定一個網絡G(V,E)和一個QoS 路由請求R=(S,D,Bmin,LETmin)，在節(jié)點S與節(jié)點D之間尋找一個可行路徑集P*，使得BP(S,D)≥Bmin，LETP(S,D)≥LETmin。其中S為QoS 路由請求R的源節(jié)點；D為QoS 路由請求R的目的節(jié)點；Bmin、LETmin分別為QoS有效帶寬、LET的約束條件；BP(S,D)、LETP(S,D)分別為路徑P(S,D)上的可用帶寬、鏈路連接持續(xù)時間，且P(S,D)∈P*。

筆者的目的是在VANETs協作通信網絡中，設計路由機制進行路徑選擇，保證網絡節(jié)點之間的數據通信。具體做法是首先尋找滿足BP(S,D)≥Bmin的可行路徑；其次計算各條可行路徑的LET，由大到小排序；最后選擇LET最大的鏈路組建為主要路由，并得到備用路由，便于主路由中斷時進行最快速度的路徑替換和路由恢復，從而提高路由的穩(wěn)定性及通信容量。

2 LETB-AODV協議

路由路徑與場景示意圖如圖1所示，在雙向四車道的十字路口，車輛S欲將數據包傳送給目標車輛D。在S、D之間有若干輛車，如{A,B,C,E,F}。若S、D的間距大于彼此的通信距離，或S、D之間可通信但通信性能較差時，需要在S、D之間選擇輔助節(jié)點建立可靠的鏈路以有效傳遞數據，如路徑(S,A,D)、(S,B,D)、(S,A,C,D)等。考慮到網絡拓撲的復雜性，每條鏈路只通過一個輔助節(jié)點幫助傳輸。因此，選擇合適的輔助節(jié)點以獲得具有較好的可用帶寬、LET的最佳通信路徑，成為組建具有QoS保障路由協議的關鍵。

圖1 路由路徑與場景示意圖

2.1 有效帶寬

協作通信方式可有效降低系統(tǒng)中斷概率、增加分集增益和系統(tǒng)容量。研究表明，DF協作模式可以獲得比直接傳輸模式更高的帶寬[11]。如圖1所示，當S、B、D在彼此的通信范圍內，車輛B作為S、D間所選擇的輔助節(jié)點(Helper)，輔助節(jié)點組成的節(jié)點集記為H={H1,H2,…,Hn}。若通過解碼轉發(fā)(DF)協作機制來實現數據的協作傳輸，即假設每幀通過兩個時隙傳輸：第一時隙中，源節(jié)點S廣播消息至節(jié)點H和D，稱為數據包的廣播階段(如鏈路eSB、eSD)；第二時隙中，節(jié)點H將收到的信息重新編碼后傳輸到目標節(jié)點D，稱為數據包的協作傳輸階段(如鏈路eBD)。雙時隙DF協作傳輸和直接傳輸的信道容量分別為[12]：

Ccoop(S,H,D)=W×Icoop(S,H,D)

(1)

lb(1+SINRSD+SINRHD)}

(2)

Cdir(S,D)=W×lb(1+SINRSD)

(3)

(4)

式中：W為信號帶寬；N0為白噪聲；α為路徑損耗因子；dij為節(jié)點i與j之間的距離。

路徑P(S,D)的可用帶寬計算如下：

BP(S,D)=Ccoop(S,Hi,D)×ATF(S,Hi,D,R),

i∈F

(5)

式中：R為QoS路由請求；BP(S,D)為路徑P(S,D)的可用帶寬；Ccoop(S,Hi,D)為協作模式下將節(jié)點Hi作為輔助節(jié)點傳輸的鏈路eiD的信道容量；ATF(S,Hi,D,R)為相同條件下鏈路eiD的可用時隙(available time fraction，ATF)，其中節(jié)點Hi可以為空，表明對應鏈路為直接傳輸模式。

2.2 鏈路連接可持續(xù)時間(LET)

(6)

假定從t0到t這段時間內，車輛保持勻加速運動，則B與S、D與B間在時刻t的距離可表示為[13]：

dBS(t)=dB(t)-dS(t)=(vB(t0)-vS(t0))t+

0.5(aB(t0)-aS(t0))t2+d0

dDB(t)=dD(t)-dB(t)=(vD(t0)-vB(t0))t+

(7)

當dBS(t)<0或dDB(t)<0，則表示車輛S超越B，或B超越D，此時B已沒必要作為輔助節(jié)點參與S與D之間的協作通信，eSB、eBD鏈路斷裂；當dBS(t)>300或dDB(t)>300，則S與B或B與D之間因距離過遠，超出彼此的通信范圍，導致eSB、eBD鏈路斷裂。因此，eSB、eBD鏈路的可用持續(xù)時間LETtBS、tDB分別為方程dBS(t)=300和dDB(t)=300的解，這里假設在時刻t時車輛B仍能作為車輛S和D的輔助節(jié)點參與通信。令ΔvBS=vB(t0)-vS(t0)，ΔvDB=vD(t0)-vB(t0)，ΔaBS=aB(t0)-aS(t0)，ΔaDB=aD(t0)-aB(t0)，則可得：

(8)

其解即為eSB、eBD鏈路的可用持續(xù)時間：

(9)

(10)

則可得車輛S與D之間協作通路的可持續(xù)時間為：

LET(S,B,D)=min{tBS,tDB}

(11)

2.3 協作節(jié)點的選擇

采用協作方式來提高鏈路傳輸能力時，需要在多個節(jié)點中選擇最優(yōu)的輔助節(jié)點，在源節(jié)點與目標節(jié)點間建立一條通路。在筆者提出的協作式路由算法中，最優(yōu)輔助節(jié)點的選取基于以下3個條件：

(1)路徑P(S,D)的有效可用帶寬BP(S,D)滿足如下QoS約束條件：

BP(S,D)≥Bmin

(12)

(2)所選節(jié)點與源節(jié)點和目標節(jié)點屬同一個行駛方向，并在源節(jié)點和目標節(jié)點的通信范圍內，這樣的節(jié)點稱為邏輯輔助節(jié)點。

(3)源節(jié)點、目標節(jié)點與邏輯輔助節(jié)點可能形成的鏈路稱為邏輯鏈路，用LET(S,Hi,D)值的大小表示這條邏輯鏈路的可持續(xù)時間，Hi∈Log(S,D)。如圖1所示，節(jié)點S和D的邏輯鏈路有LET(S,A,D)和LET(S,B,D)等。具有最長的邏輯鏈路持續(xù)時間LET的節(jié)點成為輔助節(jié)點：

Hi∈Log(S,D) and max{LET(S,Hi,D)}

(13)

其中，Hi為節(jié)點S和D所選擇的輔助節(jié)點；{LET(S,Hi,D)}為節(jié)點S和D的邏輯鏈路的可持續(xù)時間。

依據上述原則選擇輔助節(jié)點，從邏輯鏈路中選用LET最長的鏈路，構成最穩(wěn)定的傳輸路徑。但是，具有最長的LET并不一定具有最大的有效帶寬，即不一定具有最大的信道容量。具有最大信道容量的路由路徑可通過式(14)計算：

(14)

2.4 算法設計與實現

在協作路由算法設計中，通常有集中式和分布式兩種方案。集中式方案雖可選出最優(yōu)協作式路由，但在實際網絡中的可行性卻很低，因此，筆者提出了分布式路由算法來解決協作式通信問題。根據網絡部署的實際情況，協作節(jié)點同時從源節(jié)點和目標節(jié)點的一跳鄰居節(jié)點間選取。

基于QoS的VANETs分布式協作路由算法具體描述如下：

輸入：網絡G(V,E)，每條鏈路的SINR和ATF，路由請求R=(S,D,Bmin,LETmin)及相應的帶寬和LET要求Bmin和LETmin。

輸出：協作路由路徑P(S,D)，發(fā)現路由帶寬BP(S,D)，鏈路可持續(xù)時間LET(S,D)。

(1)每個節(jié)點和一跳鄰居通過HELLO報文交換鏈路信息，HELLO報文幀格式如圖2所示，包括SINR和ATF；

(2)每個節(jié)點建立本地數據庫以存儲相鄰鏈路的信息；

(3)源節(jié)點S檢查路由表中是否有到達目的節(jié)點D的可用路由。若有，則直接發(fā)送；若無，則廣播RREQ消息，RREQ消息幀格式如圖3所示；

(4)如果節(jié)點Hi收到節(jié)點S發(fā)送過來的RREQ消息。則判斷節(jié)點Hi是否在S相同方向上，若不在同一方向，則丟棄該消息；若在，則節(jié)點Hi計算從S到Hi的最大可用帶寬BP(S,Hi)；

(5)若存在P(S,Hi)使得BP(S,Hi)≥Bmin，則Hi根據式(9)計算LET(S,Hi)=tSHi，若LET(S,Hi)≥LETmin，則繼續(xù)廣播RREQ消息，否則S將Hi從可選輔助節(jié)點列表中移除；

圖2 HELLO報文幀格式

圖3 RREQ消息幀格式示意圖

(6)如果目的節(jié)點D收到多份RREQ滿足BP(Hi,D)≥Bmin、LET(S,Hi)≥LETmin，則根據式(10)計算LET(Hi,D)=tHiD；

(7)如果LET(Hi,D)≥LETmin，則根據式(11)計算LET(S,Hi,D)，再根據條件(3)計算LET(S,D)=max{LET(S,Hi,D)}，并選取具有最大LET的路徑作為最終路由，同時返回RREP消息，RREP消息幀格式如圖4所示；否則拒絕該路由請求；

圖4 RREP消息幀格式示意圖

(8)節(jié)點S收到RREP，邀請節(jié)點Hi加入路由，更新路由表。

可用時間信息ATF根據MAC協議通過CSMA機制周期性地監(jiān)聽信道忙閑程度的歷史數據記錄統(tǒng)計值來計算，表示如下：

(15)

其中，信道忙的情況包括該節(jié)點及周圍鄰居在收、發(fā)數據的情況。

筆者參考了文獻[12]中新的HELLO報文幀格式，如圖2所示。報文攜帶了額外的鏈路信息：SINR和ATF，且只與一跳鄰居進行交互，即TTL為1。

其中，報文攜帶了額外的鏈路信息，如SINR和ATF；HELLO報文只與一跳鄰居進行交互，因此其TTL為1。

在當前路由表中沒有滿足需求或對應路由的路由時，當前節(jié)點需要發(fā)起一個RREQ。發(fā)送RREQ后在Life time時間內，若收到RREP，則表示路由發(fā)起成功；若在Life time內沒有收到任何RREP，則發(fā)送一個路由失敗消息給高層。為發(fā)現滿足帶寬和鏈路可持續(xù)時間的路徑，筆者對AODV中的RREQ和RREP進行了修改。在RREQ中增加了5個新的字段，在RREP中增加了一個新的字段。RREQ和RREP的幀格式分別如圖3和圖4所示。

在圖3中，RREQID為發(fā)送RREQ的節(jié)點序號；Speed、Location、Acceleration、Direction分別為節(jié)點在發(fā)送RREQ時的速度、位置、加速度和行駛方向；Life time為回復該RREQ的有效時間。節(jié)點S在一定時間Life time內接收來自多個邏輯節(jié)點發(fā)送的RREP消息；之后不再接收。這里LET表示上一跳鏈路的可持續(xù)時間，對于源節(jié)點來說，其值為鏈路構造初始值，設為0。這些信息隨著RREQ在每一跳節(jié)點的轉發(fā)而更新。在圖4中，RREPID為發(fā)送RREP的節(jié)點序號；這里LET為已選擇的與發(fā)送RREQ節(jié)點所形成的鏈路的可持續(xù)時間。

3 仿真和性能分析

3.1 實驗環(huán)境設置

筆者通過QualNet 7.0對所提出的QoS跨層協作式路由協議的性能進行評估，具體仿真場景參數設置如表1所示。為了更好地研究LETB-AODV算法的性能，筆者分別從丟包率(應用層目的節(jié)點未成功接收的數據包與源節(jié)點發(fā)送的所有數據包之比)、控制開銷(在仿真時間內，發(fā)送的路由控制報文總數)和鏈路可持續(xù)時間LET進行分析驗證。實驗結果分析中采用LETB-AODV協議與AODV路由協議對性能進行比較。

表1 仿真場景參數設置

3.2 仿真結果及分析

實驗仿真主要用來驗證車輛速度對QoS路由協議LETB-AODV的影響，仿真結果如圖5～圖7所示。

圖5 路由路徑可持續(xù)時間隨車輛速度變化情況

圖6 控制開銷隨車輛速度變化情況

圖7 丟包率隨車輛速度變化情況

圖5描述了AODV和LETB-AODV兩種路由方案路徑可持續(xù)時間的變化情況。由此可知，隨著車輛行駛速度的增加，兩者的鏈路路徑LET都隨之縮短。這是因為車輛速度的增加，導致車距擴大的機率提高，會使原本有效鏈路因斷裂而失效，從而引起整個路由路徑的斷裂，相應地縮短了路徑的持續(xù)時間，這與之前的理論分析吻合。LETB-AODV路由協議基于這一原理，充分考慮了車輛移動性，并選擇滿足帶寬需求且具有最大LET的鏈路組建路由路徑，提高路由路徑的穩(wěn)定性。由圖5可知，隨著車輛速度的增加，LETB-AODV路由協議所選擇的路由其鏈路的持續(xù)時間明顯高于AODV路由協議，提高幅度最低為3.16%(車輛速度為15 m/s)，最高可達40.9%(車輛速度為30 m/s)。

圖6描繪了控制開銷隨車輛速度變化情況。通常節(jié)點數目越多，移動速度越快，鏈路越容易發(fā)生斷裂，需要不斷重啟路由請求，導致控制報文擁堵，路由開銷增大。從圖6可知，LETB-AODV路由協議的控制開銷遠小于AODV協議。這主要是因為LETB-AODV路由協議中輔助節(jié)點的選擇是從同一個方向的車輛中選取，且該協議有QoS保障機制，基于滿足QoS帶寬要求和最長LET鏈路構建路由，這些均降低路徑的斷裂率，路由請求的次數相應減少，從而大大減少了控制開銷，保證了其優(yōu)于AODV路由協議的路由開銷性能。

圖7描述了丟包率隨車輛速度的變化情況。可以看出，LETB-AODV和AODV協議的丟包率均隨節(jié)點速度的增大而增大。這是因為車輛速度的增加，會使鏈路上節(jié)點因自身較快脫離鄰近節(jié)點的通信范圍而導致穩(wěn)定鏈路斷裂，丟包率上升。然而由于LETB-AODV協議的QoS保障機制，建立的多路徑路由穩(wěn)定性更高，丟包率隨著車輛速度的增大而上升得比較緩慢。該結果直觀地驗證了LETB-AODV協議的有效性。

4 結論

筆者充分考慮VANETs網絡中車輛高速移動、網絡拓撲不斷變化、路徑的穩(wěn)定性差和運行軌跡有限等屬性，提出一種適用于VANETs的QoS分布式協作路由算法(LETB-AODV算法)。該算法在AODV路由協議基礎上進行擴展，選取鏈路連接失效時間(LET)和有效帶寬這兩個最重要的通信指標作為服務質量度量參數來建立雙重約束，進行最優(yōu)路由路徑選擇。通過QualNet 7.0仿真模擬VANETs中傳統(tǒng)的AODV協議和LETB-AODV協議路由決策情況，驗證了LETB-AODV相比AODV 更能夠有效地降低鏈路斷鏈率、丟包率和路由開銷，從而提高通信鏈路的穩(wěn)定性，增強網絡的可靠性。

[1] NAMBOODIRI V, GAO L. Prediction-based routing for vehicular ad hoc networks[J]. IEEE Transactions on Vehicular Technology,2007,56(4):2332-2345.

[2] 夏梓峻,劉春鳳,趙增華,等.基于鏈路預測的VANET路由算法[J].計算機工程,2012,38(4):110-114.

[3] WEDDE H F, LEHNHOFF S, BONN B V. Highly dynamic and scalable VANET routing for avoiding traffic congestions[C]∥Proc. of the 4th ACM International Workshop on Vehicular Ad Hoc Networks. New York: ACM Press,2007:81-82.

[4] ABEDI O, FATHY M, TAGHILOO J. Enhancing aodv routing protocol using mobility parameters in vanet[C]∥Proc. of 2008 IEEE/ACS International Conference on Computer Systems and Applications. Washington: IEEE Computer Society,2008:229-235.

[5] PASSCOE-CHALKE M, GOMEZ J, RANGEL V, et al. Route duration modeling for mobile ad-hoc networks[J]. Wireless Networks,2010,16(3):743-757.

[6] EIZA M H, NI Q. A reliability-based routing scheme for vehicular ad hoc networks (VANETs) on highways[C]∥ Proc. of 2012 IEEE 11th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom). Liverpool :IEEE,2012:1578-1585.

[7] NIU Z Y, YAO W B, NI Q, et al. Dereq: a QoS routing algorithm for multimedia communications in vehicular ad hoc networks[C]∥Proc. of 2007 International Conference on Wireless Communications and Mobile Computing. New York: ACM Press,2007:393-398.

[8] MANE U, KULKARNI S A. QoS realization for routing protocol on VANETs using combinatorial optimization[C]∥ Proc. of 2013 Fourth International Conference on Computing, Communications and Networking Technologies (ICCCNT). Tiruchengode:IEEE,2013:1-5.

[9] DING Z, LEUNG K K. Cross-layer routing using cooperative transmission in vehicular ad hoc networks[J]. IEEE Journal on Selected Areas in Communications,2011,29(3):571-581.

[10] KATSAROS K, DIANATI M, TAFAZOLLI R, et al. CLWPR:a novel cross-layer optimized position based routing protocol for VANETs[C]∥ 2011 IEEE Vehicular Networking Conference (VNC). Amsterdam: IEEE,2011:139-146.

[11] ZHANG J, JIA J, ZHANG Q, et al. Implementation and evaluation of cooperative communication schemes in software-defined radio testbed[C]∥ 2010 Proceedings of IEEE INFOCOM.San Diego:IEEE,2010:1-9.

[12] 費寧,馮偉,陳春玲,等.多跳無線網絡跨層協作式路由協議實現和性能分析[J].計算機應用研究,2013, 30(9):2839-2842

[13] 徐會彬,夏超.車輛自組織網絡中基于穩(wěn)定路徑的路由協議[J].計算機工程,2013,39(12):60-64.

ZHENG Hongjiang:Doctorial Candidate; School of Information Engineering, WUT, Wuhan 430070, China.

[編輯：王志全]

Distributed Cooperative Routing Algorithm Based on QoS in VANETs

ZHENGHongjiang,WANGHuixian,BAOJuan,CHENWei

In VANETs, high-speed mobility of vehicles always lead the network topology to change dynamically and communication link to fracture frequently, which severely damaged the reliability and stability of data transmission and greatly reduced the network performance. In this paper, a kind of distributed cooperative routing algorithm based on QoS (LETB-AODV routing algorithm) for VANETs was proposed. This protocol, extended from AODV routing protocol, used link expiration time (LET) and available bandwidth to establish the double constraints, and chose the maximum LET link as the optimal routing path of communication. The simulation results show that the performances of LETB-AODV protocol are better than AODV protocol in packet loss rate, routing overhead, LET, consequently demonstrating the enhancement of path-routing link stability and network reliability with distinct superiority.

cooperative communications; QoS routing; link expiration time (LET); available bandwidth; distributed algorithm

2015-03-30.

鄭洪江(1980-)，男，湖北武漢人，武漢理工大學信息工程學院博士研究生.

國家自然科學基金資助項目(51268051)；國家高技術研究發(fā)展計劃基金資助項目 (2013AA122403).

2095-3852(2015)05-0542-06

A

TP393

10.3963/j.issn.2095-3852.2015.05.004