王 博,哈力木拉提·買買提
(新疆大學(xué) 信息科學(xué)與工程學(xué)院,新疆 烏魯木齊 830046)
摘 要:當(dāng)信息源車輛與信息目標(biāo)車輛之間不能通過一跳來完成信息交互時,車輛間多跳路由連接的建立是保證車聯(lián)網(wǎng)WAVE中信息源車輛和信息目標(biāo)車輛之間能夠進(jìn)行信息傳遞的關(guān)鍵。通過研究和分析快速多跳路由算法FMHR得知,車聯(lián)網(wǎng)中各節(jié)點車輛之間建立起來的多跳路由連接會因各節(jié)點車輛之間的速度不匹配而時常發(fā)生通信中斷,針對這一問題,試著在原有算法中增加路由連接中斷的預(yù)測方法,并使用支持IEEE 802.11p的開源軟件NCTUns-6.0建立相關(guān)仿真實驗,結(jié)果表明,增加路由連接中斷的預(yù)測方法可改善車輛之間信息傳遞的效率。
關(guān)鍵詞:車聯(lián)網(wǎng)WAVE;多跳路由;路由連接
doi:10.3969/j.issn.1002-0802.2015.06.015
基于車聯(lián)網(wǎng)WAVE的多跳路由連接中斷預(yù)測算法
王博,哈力木拉提·買買提
(新疆大學(xué) 信息科學(xué)與工程學(xué)院,新疆 烏魯木齊 830046)
摘要:當(dāng)信息源車輛與信息目標(biāo)車輛之間不能通過一跳來完成信息交互時,車輛間多跳路由連接的建立是保證車聯(lián)網(wǎng)WAVE中信息源車輛和信息目標(biāo)車輛之間能夠進(jìn)行信息傳遞的關(guān)鍵。通過研究和分析快速多跳路由算法FMHR得知,車聯(lián)網(wǎng)中各節(jié)點車輛之間建立起來的多跳路由連接會因各節(jié)點車輛之間的速度不匹配而時常發(fā)生通信中斷,針對這一問題,試著在原有算法中增加路由連接中斷的預(yù)測方法,并使用支持IEEE 802.11p的開源軟件NCTUns-6.0建立相關(guān)仿真實驗,結(jié)果表明,增加路由連接中斷的預(yù)測方法可改善車輛之間信息傳遞的效率。
關(guān)鍵詞:車聯(lián)網(wǎng)WAVE;多跳路由;路由連接
doi:10.3969/j.issn.1002-0802.2015.06.015
收稿日期:2015-02-01;修回日期:2015-05-05Received date:2015-02-01;Revised date:2015-05-05
中圖分類號:TP316.8
文獻(xiàn)標(biāo)志碼:碼:A
文章編號:號:1002-0802(2015)06-0705-05
Abstract:When information source vehicle and target vehicle could not implement direct message exchange, the establishment of inter-vehicle multi-hop routing would become the key to ensuring information exchange of between source vehicle and target vehicle. Research and analysis on HMHR(Fast Multi-Hop Routing) algorithm shows that frequent communication interrupt would usually happen between these vehicles due to their mismatching velocities. In order to solve this problem, the prediction method is tried to add in the original algorithm, and the related simulation experiment with open source tool NCTUns-6.0 which supports IEEE 802.11p,indicates that this prediction method could effectively improve the information transfer of between the vehicles.
作者簡介:
Interrupt Prediction of Routing Connection based on
Wireless Access in Vehicular Environment
WANG Bo, Halmuratm
(School of Information Science and Engineering, Xinjiang University, Urumchi Xinjiang 830046, China)
Key words:WAVE (Wireless Access in the Vehicular Environment);multi-hop routing; routing connection
0引言
由于交通事故導(dǎo)致的逐年上升,世界各國越來越關(guān)注交通事故,研究智能交通以達(dá)到減少交通事故的目的。車聯(lián)網(wǎng)作為智能交通的核心,已經(jīng)成為世界上研究智能交通領(lǐng)域的熱點。與車聯(lián)網(wǎng)有關(guān)的新一代無線通信標(biāo)準(zhǔn)IEEE 802.11-2012[1]也亦2012年發(fā)布。從美國美國國家航空航天局官方網(wǎng)站得知[2],世界各大汽車廠商和各國政府也正在積極投入到智能交通各個領(lǐng)域的研究和開發(fā)當(dāng)中。作為新標(biāo)準(zhǔn)的車聯(lián)網(wǎng)WAVE網(wǎng)絡(luò)自然成為智能交通中研究的熱點問題,而作為車聯(lián)網(wǎng)核心功能的路由算法也備受到人們的極大關(guān)注。
1研究背景
車輛是車聯(lián)網(wǎng)WAVE的基本單元,具體分為車載單元(OBU)和路邊單元(RSU)[3],車輛在行駛的過程中因某些需求而進(jìn)行信息數(shù)據(jù)的交互,由于發(fā)送信息的車輛和接收對應(yīng)信息的車輛間距離較遠(yuǎn),發(fā)送信息的車輛不能直接把信息數(shù)據(jù)直接發(fā)送到接收該信息的目標(biāo)車輛,也就是發(fā)送信息的車輛與接收信息的車輛之間不能通過一跳直接完成所需信息的交互。此時,發(fā)送信息的車輛就需要其他的中間車輛作為傳遞信息的下一跳來進(jìn)行信息的傳遞,從而把需要發(fā)送的信息數(shù)據(jù)發(fā)送到接收該信息的目標(biāo)車輛,即發(fā)送信息的信息源車輛與接收該信息的目標(biāo)車輛之間是通過建立起來的路由連接進(jìn)行信息交互的。通過研究和分析發(fā)現(xiàn),路由連接中相互通信的節(jié)點車輛之間因時常發(fā)生中斷而影響到信息數(shù)據(jù)的傳遞效率。這一問題也存在于快速多跳路由算法FMHR[4-5]中,F(xiàn)MHR是針對802.11p的快速多跳路由算法,F(xiàn)MHR是通過減少信息傳遞過程中所需下一跳的個數(shù)來達(dá)到整體減少信息傳遞開銷和提高信息效率的目的。針對這一問題,文章試著給出一種預(yù)測路由中斷的方法,為了區(qū)分于FMHR算法,以FMHR-V表示在原有FMHR算法中加入預(yù)測路由中斷方法之后的算法名稱。
2FMHR算法要點
文獻(xiàn)[4-5]通過對Fastest Ferry Routing in DTN enabled VANET(FFRDV)算法的研究,假設(shè)①所有車輛上均帶有GPS定位系統(tǒng)②目標(biāo)車輛提前得知③仿真高速公路行車場景,且沒有設(shè)置障礙物等干擾因素?;谝陨霞僭O(shè),作者提出一種新的FMHR算法,結(jié)合文獻(xiàn)[6]對FMHR的理解,F(xiàn)MHR算法在選擇發(fā)送信息車輛的時,以時間和距離策略來決定選擇信息發(fā)送范圍內(nèi)哪個車輛來傳遞信息,即在發(fā)送信息范圍內(nèi)選擇速度最大和距離最短的那個車輛來傳遞信息,直到該信息被傳遞到目標(biāo)車輛為止??傮w來看,F(xiàn)MHR算法思想有三大步驟,具體如下。
2.1路由創(chuàng)建與保持
信息源車輛IV要向目標(biāo)車輛DV發(fā)送信息數(shù)據(jù),首先IV需要定位DV的位置,IV需要通過廣播形式向其信息發(fā)送范圍內(nèi)的所有周圍車輛發(fā)送信息傳遞的請求,每個中間傳遞信息的車輛都會通過其各自周圍車輛來傳遞信息,直到DV接收到IV發(fā)來的信息。當(dāng)DV接收到由IV發(fā)來的定位請求時,DV就利用中間車輛進(jìn)行應(yīng)答,直到把該應(yīng)答信息傳遞到IV為止。
作為中間車輛,其需要定期通過發(fā)送和接收信息數(shù)據(jù)與其通信的下一個中間車輛之間進(jìn)行信息交互,保持并不斷更新與其相鄰的下一個中間車輛的相關(guān)信息,比如中間車輛的ID號,只有這樣才能保證信息數(shù)據(jù)成功的在每一個中間車輛之間完成發(fā)送與接收。從而,才能保證信息數(shù)據(jù)從IV到DV。
當(dāng)車輛間的通信路由發(fā)生中斷時,都有前一跳的車輛負(fù)責(zé)路由創(chuàng)建與保持,并不斷實時更新路由信息,以此來確保信息數(shù)據(jù)在每個環(huán)節(jié)的發(fā)送與接收。
2.2下一跳車輛的選擇
FMHR通過式(1)來完成下一跳車輛的選擇,選擇的策略以時間和速度共同決定,式(1)中SNHV表示兩個車輛之間的實時距離,VNHV表示車輛之間的實時速度之差,即考慮距離與速度、時間三者之間的關(guān)系。比如IV在選擇其下一跳車輛NHV時,IV通過各個NHV發(fā)回來的ACK信息,提取位置和速度信息,計算出各個時間,如B= {TNHV1,TNHV2…,TNHVn},然后,比較各個時間值的大小,只選擇并保存與最小時間值對應(yīng)的那個車輛作為IV的下一跳車輛。以此類推,其它中間車輛計算出來的時間也是最小的,這樣信息數(shù)據(jù)從IV到DV的總體時間就可以達(dá)到最小。從這個角度講,信息從IV到DV減小了中間不必要的跳數(shù)。
TNHV=SNHV/VNHV
(1)
2.3與下一跳車輛的通信
選擇完下一跳NHV之后,接下來的任務(wù)就是和NHV之間進(jìn)行信息數(shù)據(jù)的交互。IV以最短的時間向NHV發(fā)送信息數(shù)據(jù),并接收返回信息數(shù)據(jù)。一旦被選擇的NHV接收到信息數(shù)據(jù)后,該NHV也將執(zhí)行相同的過程,選擇自己的NHV,并把信息數(shù)據(jù)傳遞出去,直到信息數(shù)據(jù)傳遞到目標(biāo)車輛DV為止。在與下一跳NHV進(jìn)行通信的時候,有以下情況需要考慮:
(a):如果DV在IV的發(fā)送信息范圍內(nèi),那么IV將不再執(zhí)行選擇下一跳的程序,直接把信息數(shù)據(jù)發(fā)送目標(biāo)車輛DV。當(dāng)DV接收到信息數(shù)據(jù)之后,會向IV發(fā)送ACK應(yīng)答信息。
(b): 如果IV在其發(fā)送信息范圍內(nèi)找不到DV,IV將向其所有周圍車輛發(fā)送得到它們位置和車輛速度的請求信息,然后,根據(jù)式(1)計算各自的時間T出來,并存放到IV的緩沖區(qū)中,進(jìn)而通過比較各個T大小,來選擇與對應(yīng)T值最小的那個車輛作為IV的NHV,IV把所要傳遞的信息數(shù)據(jù)傳遞給該NHV。由該HHV根據(jù)(a)(b)規(guī)則來進(jìn)行信息數(shù)據(jù)的傳遞,直到把信息數(shù)據(jù)傳遞到DV為止。
3路由連接中斷預(yù)測
3.1路由連接中斷預(yù)測的意義
車輛在實際的行車過程中,對于隨機(jī)分布在車道上任意兩個節(jié)點車輛的速度彼此相等的概率是很小的,當(dāng)兩個節(jié)點車輛的速度不一致時,路由連接中相互連接的兩個節(jié)點車輛之間的通信就有發(fā)生連接中斷的可能,研究路由連接中斷的可能性不僅可以提高兩個節(jié)點車輛之間信息傳遞的效率,而且對整個信息傳遞過程中涉及到路由選擇有重要作用,通過在路由選擇算法中增加路由連接中斷的預(yù)測策略可改善路由選擇算法的性能。
3.2路由連接中斷預(yù)測算法
路由連接中斷發(fā)生在各節(jié)點車輛之間進(jìn)行信息傳遞的過程中,車聯(lián)網(wǎng)中節(jié)點車輛之間進(jìn)行信息傳遞的模型如圖1所示。
圖1 WAVE中節(jié)點車輛之間的信息傳遞模型
圖1中t1,t2,t3分別表示三個連續(xù)發(fā)生且不同的時間點,D(t1),D(t2),D(t3),分別表示t1,t2,t3時間點處任意節(jié)點車輛A和車輛B之間的距離,且假定Va< Vb,意在說明車輛A和車輛B的速度不一樣,因此,車輛A和車輛B之間的距離將越來越大,即D(t1) T(21)=t2-t1 (2) T(32)=t3-t2 (3) (4) Rest(d)=R-D (5) T=Rest(d)/Vx-y (6) Vx-y=Vx-Vy (7) 通過對以上分析,結(jié)合FMHR算法思想,分別在信息源車輛A和其下一跳車輛B兩端增加路由連接中斷的預(yù)測,車輛A的偽代碼: 利用getcurrentposition函數(shù)分別獲取車輛A和車輛B的當(dāng)前坐標(biāo)(Xat3,Yat3)、(Xbt3,Ybt3)。 根據(jù)式(4)計算此時車輛A與車輛B之間的距離。 根據(jù)式(5)、式(6)、式(7)估算車輛B在其信息發(fā)送半徑R內(nèi)活動的剩余時間Tt3。 if T(32) > Tt3 //說明車輛B已經(jīng)不在R的范圍內(nèi)活動了,車輛A需要重新啟動選擇新的下一跳。 啟動選擇下一跳的程序。 else if Tt3/T(32) < 2 //車輛A計算得知,車輛B可以接收到自己所發(fā)送的信息,而自己將接收不到車輛B返回來的信息,此時,車輛A啟動選擇下一跳的程序。 啟動選擇下一跳的程序 else //認(rèn)為路由連接正常,正常接收和發(fā)送信息 sendWSM(mysockfd,send_wsmp, wsm_data); 當(dāng)車輛B接收到數(shù)據(jù)信息時,車輛B依然使用T(21)來估算數(shù)據(jù)在t2時間點時從車輛B發(fā)出到車輛A所需要的時間,通過車輛B的估算,如果這個時間滿足某些條件,車輛B認(rèn)為其發(fā)送的數(shù)據(jù)在沒有被車輛A接收到的情況下,車輛B本身已經(jīng)駛離了車輛發(fā)送半徑R的覆蓋范圍,因此,車輛B的偽代碼: if根據(jù)式(6)計算出來的時間T比值T(21)的值小于1 { sendWSM(mysockfd,send_wsmp,wsm_data);//車輛B將作為車輛A的下一跳向前發(fā)送信息數(shù)據(jù)。注意,此時,車輛B把時間T發(fā)送給車輛A作為參考,同時車輛B將盡其最大的努力以廣播形式告之車輛A,車輛A接收到這一信息之后將重新選擇新的下一跳來傳遞信息 } else if ( 1 <時間T/T(21)的值 < 2) {//此時,車輛B認(rèn)為其發(fā)送的應(yīng)答信息可以被車輛A所接收到,但是,車輛A再次發(fā)送的數(shù)據(jù)將不會被自己接收到 sendWSM(mysockfd,send_wsmp,wsm_data); Broadcast(); } else {//此時,車輛B對路由中斷不做任何預(yù)測,正常接收數(shù)據(jù)和發(fā)送數(shù)據(jù) sendWSM(mysockfd,send_wsmp,wsm_data); } 4實驗及結(jié)果分析 仿真過程中,信息從IV到DV的傳輸策略選擇FMHR算法,而預(yù)測路由中斷方法作用于選擇傳輸策略后路由節(jié)點車輛間通信的路由連接情況,可看作是對FMHR算法的補(bǔ)充。為了更好地驗證預(yù)測路由中斷方法有效,分別采用對802.11p支持較好的NCTUns-6.0[7-8]對FMHR和FMHR-V進(jìn)行仿真,仿真參數(shù)如下:車道長度為2.6 km×2.6 km,車輛個數(shù)150,發(fā)送范圍550 m、650 m、750 m,數(shù)據(jù)發(fā)送速率6 Mb/s,仿真時間100 s,包的大小為1 000 bytes,車輛類型CarAgent,車輛速度在15~45 m/s,由配置文件profile來隨意分配車輛速度。僅ID為1的路口有SignalAgent控制。通過AWK提取仿真的相關(guān)數(shù)據(jù)信息[9-10],并通過MATLAB繪制圖形以進(jìn)行實驗分析,見圖1,圖2。 圖1數(shù)據(jù)包延時與仿真時間關(guān)系 圖2 數(shù)據(jù)包丟失個數(shù)與仿真時間關(guān)系 通過分析可知,當(dāng)車輛的信息發(fā)送范圍設(shè)置在550 m時,算法在修改前和修改后的數(shù)據(jù)包丟失個數(shù)和數(shù)據(jù)包延時上區(qū)別幅度不是太大,當(dāng)車輛的信息發(fā)送范圍設(shè)置在650 m和750 m時,F(xiàn)MHR-V性能相對于原有算法FMHR的性能有所改善,經(jīng)分析得知,隨著發(fā)送半徑的范圍增大,當(dāng)發(fā)送信息的車輛和接收信息的車輛之間的速度不一致的時候,F(xiàn)MHR算法中發(fā)送信息的車輛無法提前得知其下一跳在未來某段時間內(nèi)已經(jīng)不在其信息的發(fā)送半徑范圍內(nèi),只有經(jīng)過某一段時間才會認(rèn)為通信中斷,這樣就造成無謂的等待時間;而在FMHR-V算法中,當(dāng)作為下一跳的車輛一旦離開或者將要離開發(fā)送信息車輛的發(fā)送信息半徑范圍時,作為下一跳的車輛和發(fā)送信息的車輛都可以盡自己最大努力對這一事件進(jìn)行預(yù)測。當(dāng)發(fā)送信息的車輛通過FMHR-V預(yù)測到這一事件時,即可選擇新的下一跳,一方面節(jié)省了無謂的等待時間,某種程度上增強(qiáng)了整個信息傳輸過程的實時性;另一方面也減少了不可能被接收到的數(shù)據(jù)包的發(fā)送,進(jìn)而,也減少了數(shù)據(jù)包被下一跳或者終端接收時丟失的可能性。 5結(jié)語 通過理論研究和相關(guān)實驗數(shù)據(jù)分析,在車聯(lián)網(wǎng)的各節(jié)點車輛快速移動過程中,各節(jié)點車輛與車輛之間通過建立起來的路由連接進(jìn)行通信,當(dāng)處在路由連接中的某兩個節(jié)點車輛之間的速度不一致時,節(jié)點車輛之間建立起來的路由連接會因此而處于不穩(wěn)定狀態(tài),發(fā)生路由連接中斷,通過預(yù)測該中斷發(fā)生的可能性,并在預(yù)測的基礎(chǔ)上采取相應(yīng)措施,可在一定程度上改善信息傳遞的性能。 參考文獻(xiàn): [1]IEEE Standards Association. 802.11-2012-IEEE Standard for Information technology-Telecommunications and Information Exchange Between Systems Local and Metropolitan Area Networks-Specific Requirements Part 11:Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[S].USA:IEEE,2012. [2]Nathan Naylor. U.S. Department of Transportation Announces Decision to Move Forward with Vehicle-to-Vehicle Communication Technology for Light Vehicles[EB/OL].USA:NHTSA, 2014(2014-02-03)[2015-04-20]. http://www.nhtsa.gov/About+NHTSA/Press+Releases/2014/USDOT+to+Move+Forward+with+Vehicle-to-Vehicle+Communication+Technology+for+Light+Vehicles. [3]IEEE Draft Guide for Wireless Access in Vehicular Environments (WAVE) - Architecture[S].USA:IEEE P1609.0/D5, September 2012, pp. 1-74, 2012. [4]Bilal M, Chan P M L, Pillai P Pillai. Fastest-Vehicle Multi-hop Routing in Vehicular Ad hoc Networks [C]//Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on. IEEE,2010:773-778. [5]Bilal M, Chan P M L, Pillai P Pillai. A Fastest Multi-Hop Routing Scheme for Information Dissemination in Vehicular Communication Systems [C]//Software, Telecommunications and Computer Networks (SoftCOM), 2010 International Conference on. IEEE, 2010: 35-41. [6]張繼永,楊斌. 無線車聯(lián)網(wǎng)WAVE車-車通信中的一種路由算法實現(xiàn)[J].通信技術(shù),2013,46(09):55-57. ZHANG Ji-yong, YANG Bin. A Routing Algorithm for Car-to-Car Communication in Wireless Access Vehicular Environment[J]. Communications Technology, 2013,46(09):55-57. [7]陳思洋,朱西平,文紅.基于NCTUns的IEEE 802.11p MAC協(xié)議性能仿真[J].計算機(jī)應(yīng)用,2014,34(04):945-949. CHEN Si-yang,ZHU Xi-ping,WEN Hong. Performance evaluation of IEEE 802.11p MACprotocol based on NCTUns[J].Journal of Computer Applications, 2014,34(04):945-949. [8]WANG Shie-Yuan. The Protocol Developer Manual for the NCTUns 6.0 Network Simulator and Emulator[J].National Chiao Tung University,2010. [9]Xavier Campos Ríos / Diego Pastor Pérez. Performance Evaluation of Manhattan Downtown Scenarios for Vehicular AD HOC Networks with Citymob and Nctuns[D]. Spain:UPC, Juny 2011. [10]Adrien Daunou. Design of A Privacy-Aware Routing Protocol for Vehichlar AD HOC Networks[D]. Spain:UPC,febrer,2012. 王博(1984—),女,碩士,主要研究方向為計算機(jī)網(wǎng)絡(luò)、自然語言處理; 哈力木拉提·買買提(1959—),男,教授,碩士生導(dǎo)師,主要研究方向為圖像處理、模式識別等。