熊聰聰，吳 瓊

(天津科技大學(xué)計算機(jī)科學(xué)與信息工程學(xué)院，天津 300222)

隨著配備短距離無線通信接口(dedicated short range communications)車輛的增加，又新提出了一個針對車輛之間快速短距離的通信結(jié)構(gòu) Wave．相對于傳統(tǒng)無線自組網(wǎng)(mobile ad-hoc network，MANET)，車輛自組網(wǎng)(vehicular ad-hoc network，VANET)利用車載傳感器收集車輛信息，通過無線傳輸在節(jié)點之間進(jìn)行傳送，并廣泛應(yīng)用在城市交通信息數(shù)據(jù)的共享與傳輸，可以提高城市交通安全性和信息效率，在實現(xiàn)城市一體化交通方面有廣闊的發(fā)展前景．

在實際的城區(qū)場景中，由于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)快速變化、車輛節(jié)點分布密度不均勻和節(jié)點通信范圍的限制，通常造成鏈路的中斷，網(wǎng)絡(luò)被分割成多個不連通的子區(qū)域，傳統(tǒng)的 MANET路由交換機(jī)制不再適用．在上述間歇性連接的交通場景中，利用容遲網(wǎng)絡(luò)(delay-tolerant network，DTN)攜帶–存儲–轉(zhuǎn)發(fā)機(jī)制，節(jié)點隨機(jī)移動并攜帶通信消息，從而創(chuàng)造新的通信機(jī)會，最終期望以較高的成功連接率來實現(xiàn)移動節(jié)點之間的端到端通信[1]．DTN網(wǎng)絡(luò)中的路由通過對轉(zhuǎn)發(fā)消息的存貯攜帶以及優(yōu)先級來對接收到的數(shù)據(jù)包進(jìn)行處理，對存儲器和網(wǎng)絡(luò)延遲性能要求較高．為了在間歇性連接的 VANET中合理選擇低延遲路徑傳遞消息，Zhao等[2]提出VADD協(xié)議，利用車流量歷史統(tǒng)計信息計算消息在交通路口各方向上的傳遞概率以及消息通過各路段的傳輸延遲．在 VADD協(xié)議基礎(chǔ)上，Link等[3]提出 GeoDtn協(xié)議，利用車輛的交通軌跡信息來獲得更好的性能，然而其過于依賴導(dǎo)航系統(tǒng)，并不能在實際場景中準(zhǔn)確應(yīng)用．GeoOpp路由[4]是車載網(wǎng)絡(luò)中一種基于軌跡特性的機(jī)會路由協(xié)議，它結(jié)合了車輛交通模型特性和地理位置信息，但對車輛導(dǎo)航系統(tǒng)的依賴性較高．

針對上述問題，本文提出一種改進(jìn)的基于機(jī)會轉(zhuǎn)發(fā)策略的路由協(xié)議，適用于車載容遲網(wǎng)．該路由協(xié)議在 VADD的基礎(chǔ)上增加基于節(jié)點位置信息的機(jī)會路由轉(zhuǎn)發(fā)策略，選擇合適的消息轉(zhuǎn)發(fā)節(jié)點，動態(tài)選擇合適的路由．在Qualnet無線仿真平臺上結(jié)合VanetMobiSim設(shè)置城區(qū)交通場景，并與傳統(tǒng)VANET路由對比，進(jìn)行了仿真實驗．

1 車輛交通模型和DTN

1.1 城區(qū)傳播模型假設(shè)和場景描述

在VANET中，交通模型宏觀上包括城區(qū)傳播場景、節(jié)點移動模型以及網(wǎng)絡(luò)通信模型；微觀上包括路由設(shè)施、交換基站、終端傳感器等基礎(chǔ)設(shè)施．

對VANET城區(qū)通信場景作如下假設(shè)：

(1)移動車輛間通信通過 IEEE802.11無線信道進(jìn)行傳輸(有效距離為 100～250,m)，城區(qū)場景中的建筑設(shè)施和道撲變化造成通信的暫時中斷．車輛節(jié)點移動采用 Street Microcell Propagation 模型，即位于同一條道路上移動節(jié)點采用視距通信傳輸(line of sight propagation)，車輛節(jié)點之間使用Wi-Fi通信．VANET城區(qū)場景架構(gòu)如圖1所示．

圖1 VANET 城區(qū)場景架構(gòu)圖Fig.1 VANET urban scenario map

(3)假設(shè)節(jié)點都配備了基于 IEEE802.11的車載終端和 GPS通信功能，節(jié)點預(yù)先安裝了具有城區(qū)道路和流量統(tǒng)計信息的數(shù)字地圖．車輛行駛到交叉路口時，按照各路段的車流量確定轉(zhuǎn)向概率．

1.2 DTN和機(jī)會路由

DTN通信結(jié)構(gòu)適用于極端通信情況，利用中繼節(jié)點臨時存儲轉(zhuǎn)發(fā)分組來提高網(wǎng)絡(luò)容量．該體系在應(yīng)用層和傳輸層中新加入束層(bundle layer)，以便在間歇性連接的通信過程中實現(xiàn)鏈路的連通以及異步消息的可靠傳輸．束層中的底層逐條消息確認(rèn)機(jī)制及可選的端到端確認(rèn)策略減少了消息的傳輸延遲．

圖2 DTN的束層協(xié)議棧Fig.2 Bundle layer protocol stack of DTN

DTN中的機(jī)會路由針對的是延時時間較長的延遲，通常大于幾分鐘．?dāng)y帶–存儲–轉(zhuǎn)發(fā)機(jī)制傳輸過程如圖 3所示．在1T時刻源節(jié)點 S希望將消息傳輸給目標(biāo)節(jié)點 D，但 S和 D位于不同的連通域且沒有直接通信路徑．S首先將消息發(fā)送給檢測到的鄰居節(jié)點1，節(jié)點1暫時將消息在本地存儲并等待合適的傳輸機(jī)會[6]．

圖3 攜帶-存儲-轉(zhuǎn)發(fā)機(jī)制Fig.3 Carry-store-forwarding mechanism

在T1+ΔT時刻，節(jié)點1進(jìn)入到節(jié)點4的通信范圍并轉(zhuǎn)發(fā)消息．在 T3時刻，消息傳輸給目標(biāo)節(jié)點 D，完成數(shù)據(jù)傳輸，其中過程包括了消息副本數(shù)確定、數(shù)據(jù)傳輸、節(jié)點消息緩存管理等．

2 改進(jìn)的路由協(xié)議

綜上所述，VADD路由協(xié)議根據(jù)車流密度的歷史統(tǒng)計信息計算車輛在十字路口各路段的延遲，在轉(zhuǎn)發(fā)決策中并沒有綜合考慮多個車輛節(jié)點的位置信息．本文在 VADD協(xié)議的基礎(chǔ)上引入機(jī)會路由轉(zhuǎn)發(fā)策略，結(jié)合車輛的上下文信息，提出了一種改進(jìn)的車載容遲網(wǎng)絡(luò)路由算法．

2.1 路由設(shè)計和改進(jìn)

在VANET模型中，傳輸路徑j(luò)T上移動節(jié)點k的平均速度為,kjv ，在傳輸路徑長度上，λ為矯正系數(shù)[7]，鏈路傳輸延遲為

式中：c為基于先驗知識的常量．

若車輛節(jié)點k攜帶消息駛向路徑i所在的十字路口,ije ，j為路口,ije 處可選路徑，在當(dāng)前節(jié)點出現(xiàn)傳遞信息請求時，根據(jù)傳輸延遲計算消息沿著各路段傳輸?shù)膬?yōu)先級為

式中：ip為車輛k行駛至路口時選擇第i條道路的概率．將式(1)中的傳輸延遲,kjD 代入式(2)迭代計算，得到消息在路口,ije 的新路段方向優(yōu)先級,ijU ，從而使消息沿著具有最低延遲期望的路段傳遞．在十字路口時車輛節(jié)點檢測周圍的可轉(zhuǎn)發(fā)節(jié)點車輛，車輛節(jié)點不再自身攜帶信息，以便能盡快將剩余的消息副本數(shù)傳遞給相鄰節(jié)點，使消息傳遞出去．改進(jìn)算法結(jié)合了 VADD中的路段傳輸概率和機(jī)會轉(zhuǎn)發(fā)策略，進(jìn)而計算轉(zhuǎn)發(fā)節(jié)點和報文傳輸目標(biāo)的關(guān)系，轉(zhuǎn)發(fā)節(jié)點和報文傳輸?shù)哪繕?biāo)之間的距離計算公式為

算法流程如下：

(1)轉(zhuǎn)發(fā)節(jié)點廣播 Hello數(shù)據(jù)包，如果沒有發(fā)現(xiàn)鄰居節(jié)點，則直接攜帶消息駛向下一個路口．如果當(dāng)前節(jié)點在選擇的下一個十字路口沒有與其他節(jié)點相遇，則繼續(xù)攜帶信息行駛．

(2)如果下一路段為多個轉(zhuǎn)發(fā)節(jié)點，通過角度計算公式判斷各節(jié)點之間的轉(zhuǎn)發(fā)角度，選擇最小角度的節(jié)點執(zhí)行轉(zhuǎn)發(fā)過程．通過接受 Beacon消息，處于連通的各車輛可以交換效用值并更新位置方向．消息的傳輸規(guī)則是，消息總是傳遞至連通域內(nèi)的具有最低效用值的車輛．當(dāng)節(jié)點移動進(jìn)入彼此通信范圍時，節(jié)點之間須在連接時間內(nèi)交換信息．

2.2 路徑選擇和緩存管理

文中提出改進(jìn)的機(jī)會路由協(xié)議中，數(shù)據(jù)報文的傳輸發(fā)生在十字路口選擇階段，不再分為直路模式和路口模式[8]．?dāng)?shù)據(jù)報文的傳輸綜合考慮轉(zhuǎn)發(fā)節(jié)點的位置和路段延遲綜合評測，車輛節(jié)點行駛至十字路口時，周期性發(fā)送 Hello消息感知相鄰街道的節(jié)點，并計算節(jié)點角度，判斷是否存在合適的轉(zhuǎn)發(fā)機(jī)會．該算法盡可能有效地在低延遲路徑上將數(shù)據(jù)報文向前傳輸給距離終點最近的車輛．

考慮到城區(qū)環(huán)境中會突發(fā)如交通事故等緊急信息，為了均衡利用網(wǎng)絡(luò)資源和提高預(yù)警消息傳播速率，本文采用的緩存機(jī)制如下：根據(jù)消息的緊急程度決定消息在節(jié)點緩存隊列中的排序，以便在通信連接恢復(fù)時優(yōu)先發(fā)出．設(shè)消息傳輸路徑上的普通等級消息的轉(zhuǎn)發(fā)優(yōu)先級為 U，若緊急消息產(chǎn)生，則優(yōu)先級記為maxU ，排在隊列首位優(yōu)先發(fā)出，優(yōu)先級越高，則消息被優(yōu)先傳輸?shù)目赡苄栽酱螅⒕彺媸疽馊鐖D 4所示，優(yōu)先級 U和數(shù)據(jù)包KTTL依次進(jìn)入緩存隊列，在消息傳輸過程中KTTL值按遞減進(jìn)行傳遞．

圖4 消息緩存隊列Fig.4 Message buffer management

道路行駛中車輛節(jié)點攜帶信息轉(zhuǎn)發(fā)路徑如圖 5所示．

圖5 車輛信息轉(zhuǎn)發(fā)路徑示意圖Fig.5 Path of vehicle message forwarding

若攜帶信息車輛的運動方向與路由路徑期望方向相反時，車輛攜帶信息繼續(xù)前行，否則優(yōu)先選擇路由路徑上更接近于目標(biāo)的車輛．

若相遇車輛為多個且為同向行駛，則源節(jié)點S會先傳遞數(shù)據(jù)包到距離路口最近的節(jié)點IV，若鄰居中沒有節(jié)點比自己更接近目標(biāo)，則IV在路段 Ic會傳遞數(shù)據(jù)到行駛方向與期望方向相同的鄰居 A，而不是地理位置更接近的B，雖然A的位置沒有B優(yōu)越，但由于其同向的運動方向，隨著時間變化最終將超過B．

3 仿真實驗

3.1 網(wǎng)絡(luò)仿真平臺

VANET中車輛交通模型仿真是基于VanetMobiSim的節(jié)點運動模型和 Qualnet平臺的網(wǎng)絡(luò)性能仿真的結(jié)合．Vanetmobisim是對Canumobisim的擴(kuò)展，Canumobisim 是通用交通仿真器，能夠為不同的網(wǎng)絡(luò)仿真軟件產(chǎn)生移動跟蹤(trace)文件．采用不同的宏觀和微觀移動模型，聯(lián)合使用該平臺上所得到的 trace文件，可以通過定制場景來仿真不同的交通場景[9]．

Qualnet是 UCLA開發(fā)的離散事件仿真器，通過配置模型庫文件及相關(guān)各組件屬性可以對無線和有線通信網(wǎng)絡(luò)進(jìn)行建模，適用于大規(guī)模無線移動網(wǎng)絡(luò)節(jié)點的仿真[9]，仿真速度大幅度提高．

3.2 車輛交通模型與配置

VanetMobiSim使用 Tigereader.xml提取城區(qū)地圖模型信息，配置運動節(jié)點位置信息、采樣時間間隔和節(jié)點數(shù)目，仿真輸出.mobility和.nodes文件，作為模型的trace文件導(dǎo)入后者．

在 Qualnet中導(dǎo)入 trace文件，生成網(wǎng)絡(luò)模型和節(jié)點運動場景，鏈路匯聚區(qū)域為節(jié)點，其余為移動路線坐標(biāo)．

在Qualent中使用urban_grid.pl文件產(chǎn)生城區(qū)建筑物模型，配置場景文件 Node Placement：通過工具欄導(dǎo)入 Tiger地圖和地形文件，實現(xiàn)車輛運動軌跡的仿真．城區(qū)場景中的 Pathloss model配置為使用Street microcell模型．

Mobility And Placement配置如下：

Node-position-file Opportunity.nodes

Mobility files NONE

Mobility-position-granularity 1.0

節(jié)點無線子網(wǎng)和網(wǎng)絡(luò)接口參數(shù)格式配置如下：

Subnet N8-169.0.0.0 {0 thru 40} default

[N8-169.0.0.0] PHY-RX-model PHY802.11b

NETWORK-PROTOCOL IP

實驗中其他配置參數(shù)見表 1．仿真中還設(shè)置了緩沖器存貯容量和相遇時轉(zhuǎn)發(fā)的廣播包信息協(xié)議棧．

表1 仿真實驗參數(shù)Tab.1 Simulation parameters

3.3 結(jié)果分析

實驗仿真場景如圖6所示，節(jié)點移動所產(chǎn)生的路徑軌跡在圖中用旗幟符號標(biāo)識．

圖6 Qualnet實驗仿真圖Fig.6 Simulation scenario of Qualnet

向網(wǎng)絡(luò)中注入不同的節(jié)點數(shù)據(jù)，考察網(wǎng)絡(luò)中節(jié)點數(shù)據(jù)的變化對路由算法性能的影響，并與 AODV和GPSR協(xié)議比較，主要從分組投遞率和消息傳輸?shù)难舆t時間兩方面進(jìn)行評估．

從圖 7(a)可以看出，改進(jìn)協(xié)議的數(shù)據(jù)包分組投遞率高于 AODV和 GPSR協(xié)議．車輛速度較低時，AODV的分組投遞率表現(xiàn)最好．但車載自組網(wǎng)是一種間歇性連接的網(wǎng)絡(luò)，通過地理位置信息和節(jié)點移動形成的連接概率增加使得更多的節(jié)點參與消息的轉(zhuǎn)發(fā)，因此改進(jìn)機(jī)會路由協(xié)議和模型能夠達(dá)到較高的分組投遞率．AODV協(xié)議隨著車輛速度的增加會造成鏈路的頻繁中斷，導(dǎo)致重復(fù)路由修復(fù)．GPSR則因為位置信息的更新和車輛速度的增加不成比例，傳輸質(zhì)量下降．

從圖7(b)可以看出，3種協(xié)議的數(shù)據(jù)包的平均端到端傳輸延遲是車輛節(jié)點移動速度的相關(guān)函數(shù)．在相同數(shù)據(jù)包投遞率的情況下比較，本文路由協(xié)議表現(xiàn)出較好的性能，隨著車輛速度的增加，節(jié)點的運動加快，車輛之間帶來的通信機(jī)會增多，所以加快了數(shù)據(jù)包的傳遞，端到端延遲有遞減趨勢．GPSR在低速度時根據(jù)地理位置信息選擇最近節(jié)點作為數(shù)據(jù)分組的轉(zhuǎn)發(fā)節(jié)點，隨著車輛速度增大，其延遲時間的變化并不明顯．AODV在速度較高時，由于查找路由出現(xiàn)頻繁錯誤導(dǎo)致延遲增大．

圖7 車輛速度對投遞率和延遲的影響Fig.7 Packet delivery ratio and the delay of vehicle speed

4 結(jié) 語

本文對在城區(qū)環(huán)境中的車輛交通模型和傳播損耗模型進(jìn)行分析，結(jié)合 DTN的機(jī)會路由轉(zhuǎn)發(fā)機(jī)制改進(jìn)消息在十字路口的緩存和轉(zhuǎn)發(fā)機(jī)制，提高間歇性連接的車載網(wǎng)中的數(shù)據(jù)包傳遞率．仿真結(jié)果表明，相對于傳統(tǒng)的 AODV、GPSR協(xié)議，機(jī)會路由轉(zhuǎn)發(fā)策略VANET城區(qū)通信環(huán)境數(shù)據(jù)傳輸性能有較大提高，減少了端到端的延遲．

［1］ 宋超，劉明，龔海剛，等. 基于分布式實時信息的車載網(wǎng)絡(luò)路由協(xié)議[J]. 軟件學(xué)報，2011，22(3)：466–480.

［2］ Zhao Jing，Cao Guohong. VADD：Vehicle-assisted data delivery in vehicular Ad hoc networks[J]. IEEE Transactions on Vehicular Technology，2008，57(3)：1910–1922.

［3］ Link J A B，Schmitz D，Wehrle K. GeoDTN：Geographic routing in disruption tolerant networks[C]//Proceedings of 2011 IEEE Global Telecommunications Conference，GLOBECOM 2011. New York：IEEE Inc.，2011：1–5.

［4］ Leontiadis I，Mascolo C. GeOpps：Geographical opportunistic routing for vehicular networks[C]//2007 IEEE International Symposium on a World of Wireless，Mobile and Multimedia Networks，WOWMOM. Piscataway：IEEE Computer Society，2007：1-6.

［5］ Wisitpongphan N，Bai F，Mudalige P. Routing in sparse vehicular ad hoc wireless networks[J]. IEEE Journal on Selected Areas in Communication，2007，25(8)：1538–1566.

［6］ 張國慶，幕德俊，洪亮，等. 城市場景下VANET路由協(xié)議大規(guī)模仿真研究[J]. 計算機(jī)仿真，2009，26(8)：249–252.

［7］ 馬濤，單洪. 基于 Qualnet的移動自組網(wǎng)建模與仿真[J]. 電光與控制，2009，16(4)：60–64.

［8］ 姜飛. 車載 Ad-hoc網(wǎng)絡(luò)按需路由協(xié)議的改進(jìn)及仿真[D]. 北京：北京郵電大學(xué)，2010.

［9］ 杜昱宏，秦華標(biāo). 城市非連通車載自組網(wǎng)中低時延路由協(xié)議[J]. 計算機(jī)工程，2010，36(15)：111–113.