尹鴻坦

(黃淮學(xué)院信息工程學(xué)院,河南 駐馬店 463000)

面向高速場景的基于路徑連通概率路由協(xié)議*

尹鴻坦*

(黃淮學(xué)院信息工程學(xué)院,河南 駐馬店 463000)

有效地傳輸數(shù)據(jù)是提高車聯(lián)網(wǎng)VANETs(Vehicular Ad Hoc Networks,)應(yīng)用性能的關(guān)鍵。而動態(tài)的拓?fù)浣Y(jié)構(gòu),給VANETs的數(shù)據(jù)傳輸提出了挑戰(zhàn)。為此,提出基于路徑連通概率的車聯(lián)網(wǎng)路由算法CPR(Connected Probability-Based Routing)。首先,依據(jù)高速公路場景,建立一維車輛移動模型,然后再計算鏈路的連通概率,最后,計算路徑的連通概率,并選擇連通概率最高的路徑傳輸數(shù)據(jù)。仿真結(jié)果表明,提出的CPB算法能夠有效地提高數(shù)據(jù)包傳遞率、端到端傳輸時延以及吞吐量性能。

連通概率;路由;移動模型;車聯(lián)網(wǎng)

目前,汽車已成為民眾出行的首選交通工具,汽車便捷民眾的日常出行。然而,隨著汽車數(shù)量的增加,道路擁塞、交通安全問題也日益突出。據(jù)不完全統(tǒng)計,交通事故已成第2大殺手。世界衛(wèi)生組織WMO指出每年約130萬人死于交通事故,約5 000萬人受傷[1]。據(jù)此,政府部門以及科研機(jī)構(gòu)開始商討、并提出利用智能交通概念,提高交通安全。作為智能交通系統(tǒng)的最有前景技術(shù),車聯(lián)網(wǎng) VANETs(Vehicular Ad Hoc Networks)受到廣泛關(guān)注。

典型的車聯(lián)網(wǎng)結(jié)構(gòu)如圖1所示。裝有OBU模塊的車輛能夠與其他車輛、路邊設(shè)施進(jìn)行通信。其中車與車之間的通信稱為車間通信V2V(Vehicle to Vehicle),而車與路旁設(shè)備通信稱為車-旁通信V2R(Vehicle to Roadside unit)。車輛間通過實(shí)時交互路狀信息,實(shí)現(xiàn)對事故的預(yù)警以及避讓,進(jìn)而提高交通管理效率以及交通安全。據(jù)美國交通局統(tǒng)計,通過車聯(lián)網(wǎng)技術(shù)平臺,能夠?qū)⒔煌ㄊ鹿事式档?2%。

圖1 VANET的網(wǎng)絡(luò)模型

從技術(shù)層面而言,車聯(lián)網(wǎng)VANETs屬于移動自組織網(wǎng)絡(luò),但VANETs具有鮮明的特性,如動態(tài)的拓?fù)?、受限的移動模型、車輛的高速移動。這些特性給VANETs的消息傳輸提出了挑戰(zhàn)。據(jù)此,眾多研究學(xué)者關(guān)注VANETs中的路由技術(shù)[2-5]。

值得注意得是,車輛移動受限于道路的拓?fù)浣Y(jié)構(gòu),并且道路的拓?fù)浣Y(jié)構(gòu)是靜態(tài),至少在短時間內(nèi)道路結(jié)構(gòu)是不會變化,這一特性給車輛移動預(yù)測提供了基礎(chǔ)。通過對車輛移動的預(yù)測,可有效地計算鏈路的連通特性,包括連通概率、連通持續(xù)時間等。

文獻(xiàn)[6]提出基于鏈路連接概率的路由協(xié)議。先計算鏈路連接概率,并由此估算鏈路連通時間,從而選擇最穩(wěn)定、可靠的路徑作為數(shù)據(jù)傳輸通道。文獻(xiàn)[7]提出面向高速道路場景的車輛移動預(yù)測模型。此外,文獻(xiàn)[8]也提出基于移動預(yù)測的MOPR路由協(xié)議。MOPR協(xié)議先預(yù)測車輛的下一時刻位置,然后再估算數(shù)據(jù)傳輸至此位置所需的時間。隨后,檢測鏈路在數(shù)據(jù)傳輸時間內(nèi)是否一直保持連接狀態(tài)。

本文基于上述文獻(xiàn)的分析,考慮到VANETs的移動區(qū)域局限性、移動信息的可預(yù)測性,提出基于路徑連通概率的VANETs路由算法CPB。CPB算法通過路徑連通概率決策路由,提高路由應(yīng)對動態(tài)拓?fù)涞聂敯粜浴?/p>

1 網(wǎng)絡(luò)模型

以高速公路為研究對象,并建立相應(yīng)的網(wǎng)絡(luò)模型。依據(jù)IEEE802.p的標(biāo)準(zhǔn),車輛的一跳通信半徑為300 m,其遠(yuǎn)大于道路寬度。據(jù)此,可將高速公路場景模擬成一維的網(wǎng)絡(luò)模型。

在高速公路的場景中,車輛駛?cè)牍贩牟此煞植糩9]。假定泊松分布的參數(shù)為λ,那么在時間[0,t]范圍內(nèi),有m輛車駛?cè)氲缆返母怕蔖r:

(1)

式中:N(t)在時間[0,t]駛?cè)牍返能囕v數(shù)。

當(dāng)公路上有多輛車時,車與車之間的間隔服從指數(shù)分布,且參數(shù)為α。假定第i個間隔為Ti,那么在時間[0,t]內(nèi)可容納的間隔數(shù)為M(t),且M(t)服從參數(shù)為αt的泊松分布。

對于個體車輛υk,它以vi,k速度在第i個間隔Ti,k內(nèi)移動。車輛υk所移動的距離Si,k=vi,k×Ti,k。因此,在時間[0,t]內(nèi),車輛υk移動的距離Sk(t):

(2)

依據(jù)統(tǒng)計學(xué)知識,Sk(t)服從復(fù)合泊松過程[10]。相應(yīng)地,它的均值、方差可依式(3)、(4)計算。

E[Sk(t)]=αtE[Si,k]=μt

(3)

(4)

為了簡化描述,根據(jù)中心極限定理[9],將Sk(t)分布視為正態(tài)分布。在道路中,車輛間的狀態(tài)可通過其觀察車輛進(jìn)入道路時間差進(jìn)行描述。仍假定車輛υk,其觀察車輛進(jìn)入道路的時間為t,并且它們進(jìn)入道路的時差為τ。

若τ大于零,則意味著觀察車輛先進(jìn)入道路,若τ小于零,則說明觀察車輛后進(jìn)入道路。據(jù)此,Sk(t+τ)等于在時間[0,t]內(nèi)車輛υk所移動的距離,且服從正態(tài)分布,其中均值、方差分別如式(5)、式(6)所示:

E[Sk(t+τ)]=μ(t+τ)

(5)

(6)

利用車輛υk與觀察車輛所移動距離差,表征它們的相對距離,即Dr=S(t+τ)-S(t)。它的均值、方差如式(7)、式(8)所示:

E[Dr]=μτ

(7)

(8)

(9)

2 CPB協(xié)議

CPB協(xié)議旨在提高網(wǎng)絡(luò)連通率,保證數(shù)據(jù)傳輸傳遞率。為此,CPB協(xié)議先計算節(jié)點(diǎn)間的連通率(鏈路連通率),然后再計算路徑連通率,最后選擇路徑連通率最高的路徑傳輸數(shù)據(jù)包。整個CPB協(xié)議工作流程如圖2所示。

圖2 CPB協(xié)議建立數(shù)據(jù)傳輸路徑

2.1 連通概率

當(dāng)源節(jié)點(diǎn)(車輛)需要向目的節(jié)點(diǎn)傳輸數(shù)據(jù)時,源節(jié)點(diǎn)首先需要計算自己與下一跳節(jié)點(diǎn)間連通概率,換而言之,選擇連通概率最高的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

圖3 在建立鏈路時期內(nèi)的兩跳間接通信

如圖3所示,源節(jié)點(diǎn)A與目的節(jié)點(diǎn)C均沿著左向右行駛。假定節(jié)點(diǎn)A、B和B、C間距離表示為dAB、dBC。相應(yīng)地,dAC表示節(jié)點(diǎn)A、C間的距離。如果距離dAC小于通信范圍R,則直接通信。反之,節(jié)點(diǎn)A需要選擇下一跳節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)。接下來,以圖3為例,分析選擇下一跳節(jié)點(diǎn)的過程。

若節(jié)點(diǎn)A在時刻t=0進(jìn)入系統(tǒng),而在時刻t=t1節(jié)點(diǎn)A的位置為x,且x∈[-2R,2R]。此時節(jié)點(diǎn)A與目的節(jié)點(diǎn)C構(gòu)建了數(shù)據(jù)傳輸路徑。由于它們彼此不在一跳鄰居通信范圍內(nèi),需要通過中間轉(zhuǎn)發(fā)節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)數(shù)據(jù)。轉(zhuǎn)發(fā)區(qū)域如圖3所示的陰影區(qū)域,即在[-R,x+R]區(qū)域?yàn)樗鼈兊霓D(zhuǎn)發(fā)區(qū)域[11]。若在該區(qū)域內(nèi)存在節(jié)點(diǎn),則這些節(jié)點(diǎn)可成為轉(zhuǎn)發(fā)節(jié)點(diǎn)。

接下來,估計轉(zhuǎn)發(fā)區(qū)域內(nèi)的節(jié)點(diǎn)(車輛)進(jìn)入[-R,x+R]區(qū)域的時間,與目的節(jié)點(diǎn)C的時間差為τ的概率Pτ1(x),即在t=t1時刻建立連通的概率。依據(jù)式(9),可計算Pτ1(x):

(10)

由于車輛駛?cè)霑r刻t服從(-t1/2,t1/2)區(qū)域的均勻分布。如果τ?(-t1/2,t1/2),則意味著車輛在時刻t=t1駛?cè)雲(yún)^(qū)域[-R,x+R]的概率太小,換而言之,區(qū)域[-R,x+R]內(nèi)沒有節(jié)點(diǎn)能與目的節(jié)點(diǎn)C建立連通。在這種情況,源節(jié)點(diǎn)A只能采取存儲-轉(zhuǎn)發(fā)策略,直至轉(zhuǎn)發(fā)區(qū)域內(nèi)有節(jié)點(diǎn)才進(jìn)行轉(zhuǎn)發(fā)。

當(dāng)然,或許在時刻t=t1有m輛車駛?cè)氲缆?。在這種情況下,任意一輛車出現(xiàn)在[-R,x+R]的區(qū)域的概率

(11)

依據(jù)式(11)可知,在區(qū)域[-R,x+R]內(nèi)無任何車輛的概率可表示為1-Pt1(x)。

(12)

exp(-λtPt1(x))

(13)

最后,將式(13)代入(12)便可計算連通概率:

(14)

2.2 路由決策

提出的CPB算法是以選擇連通概率最高的路徑為原則進(jìn)行路由決策。當(dāng)源節(jié)點(diǎn)需要傳輸數(shù)據(jù)時,首先計算每條通往目的節(jié)點(diǎn)路徑的連通概率[12],然后從中選擇概率最高的路徑作為數(shù)據(jù)傳輸通道。

對于每一條路徑(假定為路徑l),若該條路徑Pathl由n條鏈路組成。而每條鏈路的連通概率表示為Ph(h=1,2,…,n)。據(jù)此,整條路徑Pathl的連通概率:

(15)

最后,源節(jié)點(diǎn)選擇連通概率最大的路徑作為數(shù)據(jù)傳輸通道。

圖4 路由發(fā)現(xiàn)流程

2.3 路由發(fā)現(xiàn)流程

當(dāng)節(jié)點(diǎn)需要傳輸數(shù)據(jù)包時,節(jié)點(diǎn)就先鄰居廣播請求數(shù)據(jù)包RREQ。一旦接收了RREQ包,節(jié)點(diǎn)就先判斷是否之前已接收了RREQ,若是,則丟棄,否則,就依據(jù)式(14)計算連通概率,并加載到RREQ,再轉(zhuǎn)發(fā)。重復(fù)上述過程,直到目的節(jié)點(diǎn)接收了RREQ包。目的節(jié)點(diǎn)可能接收了來自多條路徑傳輸?shù)腞REQ包。為此,目的節(jié)點(diǎn)依據(jù)式(15)計算每條路徑的連通率,再選擇連通率最大的路徑作為數(shù)據(jù)傳輸通路。然后,目的節(jié)點(diǎn)依據(jù)所選擇的路徑回復(fù)ACK。當(dāng)源節(jié)點(diǎn)接收了ACK后,再依據(jù)此路徑向目的節(jié)點(diǎn)傳輸數(shù)據(jù)包。整個路由發(fā)現(xiàn)流程如圖4所示。

以圖5為例,描述CPB協(xié)議的路由決策過程。源節(jié)點(diǎn)A首先發(fā)送路徑請求消息Mes_req。接收節(jié)點(diǎn)B先計算與節(jié)點(diǎn)A的連接概率,再將此概率值載入Mes_req,并轉(zhuǎn)發(fā)。每個接收節(jié)點(diǎn)均重復(fù)上述過程,直到目的節(jié)點(diǎn)F接收到此消息Mes_req。

圖5 路由選擇過程

由圖5可知,由{A→B→C→E→F}、{A→B→D→E→F}兩條路徑到節(jié)點(diǎn)F,并且這兩條路徑的連通概率PPathl分別為0.028 8、0.048 0。這表明路徑{A→B→D→E→F}比路徑{A→B→C→E→F}的連接時間更短,路徑更趨于穩(wěn)定。因此,節(jié)點(diǎn)F選擇路徑{A→B→D→E→F},并沿著該路徑的反方向向源節(jié)點(diǎn)A回復(fù)ACK消息,如圖5(b)所示。

3 性能分析

3.2 仿真場景

為了更好地分析CPB路由性能,利用NS2.35建立仿真平臺?？紤]長為L=4 000 m的三車道的高速場景,車輛的通信半徑為300 m,如圖6所示。具體的仿真參數(shù)如表1所示。

圖6 高速公路仿真場景

參數(shù)數(shù)值公路長度4000m車道數(shù)3最小車速40km/h最大車速120km/h車輛通信范圍250m仿真時間100s

在仿真過程中,選擇VADD[13]和AODV[14]路由算法作為參考,并與CPB算法進(jìn)行比較。AODV路由是經(jīng)典的車聯(lián)網(wǎng)路由協(xié)議,而VADD路由也是以提高數(shù)據(jù)傳輸率為目的路由協(xié)議。這兩個路由與CPR路由具有可比性。此外,從吞吐量、數(shù)據(jù)傳輸?shù)亩说蕉藗鬏敃r延以及數(shù)據(jù)包傳遞率3方面分析路由算法的性能。

3.2 數(shù)值分析

接下來,分析車輛速度對端到端傳輸時延(E2E)、吞吐量(Throughput)以及數(shù)據(jù)包傳輸率的影響。其中,端到端傳輸時延是指數(shù)據(jù)包從源節(jié)點(diǎn)傳輸至目的節(jié)點(diǎn)的平均時延;而數(shù)據(jù)包傳輸率是指數(shù)據(jù)包傳輸成功率,其等于目的節(jié)點(diǎn)所接收的數(shù)據(jù)包數(shù);吞吐量是指單位時間內(nèi)網(wǎng)絡(luò)內(nèi)所傳輸?shù)臄?shù)據(jù)量。

實(shí)驗(yàn)以隨機(jī)方式產(chǎn)生數(shù)據(jù)包源節(jié)點(diǎn)(車輛)和目的節(jié)點(diǎn)(車輛),并考慮變化車速對路由協(xié)議性能的影響。

①端到端傳輸時延

平均速度越高,端到端時延越大。原因在于車速的提高,加劇了拓?fù)浣Y(jié)構(gòu)的動態(tài)變化,降低了路徑的連通率,使得路由不穩(wěn)定。最終,增加數(shù)據(jù)包傳輸時延。

從圖7可知,相比于AODV和VADD路由算法,CPB算法的時延得到有效地縮減。例如,當(dāng)平均車速在70 km/h時,CPB的端到端時延約為3 s,而VADD和AODV時延分別為3.5 s和4.75 s。這歸功于CPB算法依據(jù)路徑的連通率決策路由,避免了連通率低的路徑作為數(shù)據(jù)傳輸,提高了路由的穩(wěn)定性。而AODV和VADD發(fā)現(xiàn)路由時并沒有從路由穩(wěn)定性角度出發(fā)。對于拓?fù)渥兓能嚶?lián)網(wǎng)而言,路由的不穩(wěn)定性是制約路由性能的關(guān)鍵因素。

圖7 平均時延隨平均車速的影響

②數(shù)據(jù)包傳遞率

數(shù)據(jù)包傳遞率隨車速變化情況如圖8所示。平均車速越大,數(shù)據(jù)包傳遞率越低。原因在于,車速的提高了,加速了網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化性,最終導(dǎo)致路徑不穩(wěn)定,進(jìn)而降低了數(shù)據(jù)包傳輸率。與AODV和VADD路由相比,CPB路由數(shù)據(jù)包傳遞率得到有效地提高。例如,在平均車速在80 km/h時,CPB路由的所接收的數(shù)據(jù)包數(shù)達(dá)到43,而AODV協(xié)議只有32個。

圖8 數(shù)據(jù)包傳輸率隨車平均速度的變化

③吞吐量

最后,分析了車速對吞吐量的性能影響,實(shí)驗(yàn)數(shù)據(jù)如圖9所示。從圖9可知,吞吐量隨車速的增加而下降。這主要是因?yàn)檐囁俚奶岣?增加傳輸時延,降低了傳輸效率,同時,又減少了數(shù)據(jù)包傳遞率,最終導(dǎo)致數(shù)據(jù)吞吐量的下降。然而,由于CPB路由算法依據(jù)路徑連通率選擇路由,提高了應(yīng)對動態(tài)拓?fù)渥兓哪芰Α?/p>

圖9 吞吐量隨車平均速度的影響

圖10 平均路由開銷隨車平均速度的影響

④路由開銷

最后,利用路由開銷反映算法復(fù)雜性。路由開銷越大,說明路由算法越復(fù)雜。路由開銷是每接收一個數(shù)據(jù)包所產(chǎn)生的控制包個數(shù)。從圖10可知,CPB的路由開銷低于AODV路由協(xié)議,但高于VADD協(xié)議。原因在于:CPB路由協(xié)議在發(fā)現(xiàn)路由時,采用了請求包和控制包,這增加了路由開銷。

4 總結(jié)

本文針對車聯(lián)網(wǎng)的數(shù)據(jù)傳輸問題,提出基于路徑連通概率的路由算法CPB。CPB算法考慮了車輛的高速移動對路由穩(wěn)定性的影響。CPB算法計算鏈路的連通率,并估算路徑的連通概率。在決策路由時,總是選擇連通概率最高的路徑作為數(shù)據(jù)傳輸通道,進(jìn)而提高數(shù)據(jù)傳輸效率。仿真結(jié)果驗(yàn)證路由算法的性能。與AODV和VADD路由算法相比,CPB路由算法的端到端傳輸時延、吞吐量以及數(shù)據(jù)傳遞率性能均得到有效地提高。

[1]Casteigts A,Nayak A,Stojmenovic I. Communication Protocolsfor Vehicular Ad Hoc Networks[J]. Wireless Communication Mobile Computer,2011,11(5):567-582.

[2]Shafiee K,Leung V C M. Connectivity-Aware Minimum-Delay Geographic Routing with Vehicle Tracking in VANETs[J]. Ad Hoc Networks,2011,9(2):131-141.

[3]Biswas S,Morris R. ExOR:Opportunistic Routing in Multi-Hop Wireless Networks[C]//Proc ACM SIGCOMM,2012:133-144.

[4]徐子豪,張騰飛. 基于語音識別和無線傳感網(wǎng)絡(luò)的智能家居系統(tǒng)設(shè)計[J]. 計算機(jī)測量與控制,2012,12(1):12-18.

[5]周凱,孟利民,華驚宇. 基于Grover路由策略的無線傳感網(wǎng)絡(luò)剩余容量構(gòu)造與研究[J]. 傳感技術(shù)學(xué)報,2015,28(2):249-253.

[6]Li Y,Chen W,Zhang Z L. Optimal Forwarder List Selection in Opportunistic Routing[C]//Proc IEEE MeshTech,2010:670-675.

[7]Namboodiri V,Gao L. Prediction-Based Routing for Vehicular Ad Hoc Networks[J]. IEEE Transactions on Vehicular Technology,2012,56(4):2332-2345.

[8]Menouar H,Lenardi M,Filali F. A Movement Prediction Based Routing Protocol for Vehicle to Vehicle Communication[C]//Proc V2VCOM,San Diego,CA,Jul. 2015:75-82.

[9]Hafeez K,Zhao L,Liao Z,et al. Impact of Mobility on VANETs’ Safety Applications[C]//Global Telecommunications Conference(GLOBECOM 2010),2010 IEEE,Dec. 2010:1-5.

[10]Zhao M,Li Y,Wang W. Modeling and Analytical Study of Link Properties in Multi-Hop Wireless Networks[J]. IEEE Transactions on Communications,2012,60(2):445-455.

[11]王佩雪,羅菁. VANETs中基于鏈路的可持續(xù)時間路由方案[J]. 科學(xué)技術(shù)與工程,2014,14(25):267-272.

[12]張莉華,張得生. 基于連接概率的VANETs路由協(xié)議研究[J]. 現(xiàn)代電子技術(shù),2016,39(7):19-24.

[13]Zhao J,Cao G. VADD:Vehicle-Assisted Data Delivery in Vehicular Ad Hoc Networks[J]. IEEE Transactions Vehicular Technology,2011,57(3):1910-1922.

[14]Xia Zijun,Liu Chunfeng,Zhao Zenghua. Routing Algorithm in Vehicular Ad Hoc Network Based on Link Prediction[J]. Computer Engineering,2012,38(4):110-114.

Connected Probability-Based Routing for HighwayScenario Vehicular Ad Hoc Networks*

YINHongtan*

(College of Information Engineering,HuangHuai University,Zhumadian He’nan 463000,China)

To transmit effectively data is key issue of improving the application performance of Vehicular ad hoc networks(VANETs). However,dynamic topology is great challenge for transmitting data. Therefore,Connected Probability-Based routing(CPR)was proposed in this paper. Firstly,according to highway scenario,the one-dimension vehicle mobile model was established. Secondly,the connected probability of link was estimated. Finally,the connected probability of path was computed,and the path with maximum connected probability was selected to transmit data. Simulation results show that the proposed CPB algorithm has better performance in terms of packet delivery ratio,end-to-end delay and throughput.

connected probability;routing;mobility model;VANETs

尹鴻坦(1987-)，男，河南汝南人，碩士，研究方向?yàn)樵朴嬎?，大?shù)據(jù)。

項(xiàng)目來源:河南省科技廳項(xiàng)目(162102110119);國家自然科學(xué)基金項(xiàng)目(51406140)

2017-01-18 修改日期:2017-05-05

TP393

A

1004-1699(2017)08-1281-06

C:7230

10.3969/j.issn.1004-1699.2017.08.025