基于車聯網WAVE的多跳路由連接中斷預測算法

王　博，哈力木拉提·買買提

(新疆大學 信息科學與工程學院，新疆 烏魯木齊 830046)

摘　要：當信息源車輛與信息目標車輛之間不能通過一跳來完成信息交互時，車輛間多跳路由連接的建立是保證車聯網WAVE中信息源車輛和信息目標車輛之間能夠進行信息傳遞的關鍵。通過研究和分析快速多跳路由算法FMHR得知，車聯網中各節點車輛之間建立起來的多跳路由連接會因各節點車輛之間的速度不匹配而時常發生通信中斷，針對這一問題，試著在原有算法中增加路由連接中斷的預測方法，并使用支持IEEE 802.11p的開源軟件NCTUns-6.0建立相關仿真實驗，結果表明，增加路由連接中斷的預測方法可改善車輛之間信息傳遞的效率。

關鍵詞：車聯網WAVE；多跳路由；路由連接

doi:10.3969/j.issn.1002-0802.2015.06.015

基于車聯網WAVE的多跳路由連接中斷預測算法

王博，哈力木拉提·買買提

(新疆大學 信息科學與工程學院，新疆 烏魯木齊 830046)

摘要：當信息源車輛與信息目標車輛之間不能通過一跳來完成信息交互時，車輛間多跳路由連接的建立是保證車聯網WAVE中信息源車輛和信息目標車輛之間能夠進行信息傳遞的關鍵。通過研究和分析快速多跳路由算法FMHR得知，車聯網中各節點車輛之間建立起來的多跳路由連接會因各節點車輛之間的速度不匹配而時常發生通信中斷，針對這一問題，試著在原有算法中增加路由連接中斷的預測方法，并使用支持IEEE 802.11p的開源軟件NCTUns-6.0建立相關仿真實驗，結果表明，增加路由連接中斷的預測方法可改善車輛之間信息傳遞的效率。

關鍵詞：車聯網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

文獻標志碼：碼：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引言

由于交通事故導致的逐年上升，世界各國越來越關注交通事故，研究智能交通以達到減少交通事故的目的。車聯網作為智能交通的核心，已經成為世界上研究智能交通領域的熱點。與車聯網有關的新一代無線通信標準IEEE 802.11-2012[1]也亦2012年發布。從美國美國國家航空航天局官方網站得知[2]，世界各大汽車廠商和各國政府也正在積極投入到智能交通各個領域的研究和開發當中。作為新標準的車聯網WAVE網絡自然成為智能交通中研究的熱點問題，而作為車聯網核心功能的路由算法也備受到人們的極大關注。

1研究背景

車輛是車聯網WAVE的基本單元，具體分為車載單元(OBU)和路邊單元(RSU)[3]，車輛在行駛的過程中因某些需求而進行信息數據的交互，由于發送信息的車輛和接收對應信息的車輛間距離較遠，發送信息的車輛不能直接把信息數據直接發送到接收該信息的目標車輛，也就是發送信息的車輛與接收信息的車輛之間不能通過一跳直接完成所需信息的交互。此時，發送信息的車輛就需要其他的中間車輛作為傳遞信息的下一跳來進行信息的傳遞，從而把需要發送的信息數據發送到接收該信息的目標車輛，即發送信息的信息源車輛與接收該信息的目標車輛之間是通過建立起來的路由連接進行信息交互的。通過研究和分析發現，路由連接中相互通信的節點車輛之間因時常發生中斷而影響到信息數據的傳遞效率。這一問題也存在于快速多跳路由算法FMHR[4-5]中，FMHR是針對802.11p的快速多跳路由算法，FMHR是通過減少信息傳遞過程中所需下一跳的個數來達到整體減少信息傳遞開銷和提高信息效率的目的。針對這一問題，文章試著給出一種預測路由中斷的方法，為了區分于FMHR算法，以FMHR-V表示在原有FMHR算法中加入預測路由中斷方法之后的算法名稱。

2FMHR算法要點

文獻[4-5]通過對Fastest Ferry Routing in DTN enabled VANET(FFRDV)算法的研究，假設①所有車輛上均帶有GPS定位系統②目標車輛提前得知③仿真高速公路行車場景，且沒有設置障礙物等干擾因素。基于以上假設，作者提出一種新的FMHR算法，結合文獻[6]對FMHR的理解，FMHR算法在選擇發送信息車輛的時，以時間和距離策略來決定選擇信息發送范圍內哪個車輛來傳遞信息，即在發送信息范圍內選擇速度最大和距離最短的那個車輛來傳遞信息，直到該信息被傳遞到目標車輛為止。總體來看，FMHR算法思想有三大步驟，具體如下。

2.1路由創建與保持

信息源車輛IV要向目標車輛DV發送信息數據，首先IV需要定位DV的位置，IV需要通過廣播形式向其信息發送范圍內的所有周圍車輛發送信息傳遞的請求，每個中間傳遞信息的車輛都會通過其各自周圍車輛來傳遞信息，直到DV接收到IV發來的信息。當DV接收到由IV發來的定位請求時，DV就利用中間車輛進行應答，直到把該應答信息傳遞到IV為止。

作為中間車輛，其需要定期通過發送和接收信息數據與其通信的下一個中間車輛之間進行信息交互，保持并不斷更新與其相鄰的下一個中間車輛的相關信息，比如中間車輛的ID號，只有這樣才能保證信息數據成功的在每一個中間車輛之間完成發送與接收。從而，才能保證信息數據從IV到DV。

當車輛間的通信路由發生中斷時，都有前一跳的車輛負責路由創建與保持，并不斷實時更新路由信息，以此來確保信息數據在每個環節的發送與接收。

2.2下一跳車輛的選擇

FMHR通過式(1)來完成下一跳車輛的選擇，選擇的策略以時間和速度共同決定，式(1)中SNHV表示兩個車輛之間的實時距離，VNHV表示車輛之間的實時速度之差，即考慮距離與速度、時間三者之間的關系。比如IV在選擇其下一跳車輛NHV時，IV通過各個NHV發回來的ACK信息，提取位置和速度信息，計算出各個時間，如B= {TNHV1,TNHV2…,TNHVn}，然后，比較各個時間值的大小，只選擇并保存與最小時間值對應的那個車輛作為IV的下一跳車輛。以此類推，其它中間車輛計算出來的時間也是最小的，這樣信息數據從IV到DV的總體時間就可以達到最小。從這個角度講，信息從IV到DV減小了中間不必要的跳數。

TNHV=SNHV/VNHV

(1)

2.3與下一跳車輛的通信

選擇完下一跳NHV之后，接下來的任務就是和NHV之間進行信息數據的交互。IV以最短的時間向NHV發送信息數據，并接收返回信息數據。一旦被選擇的NHV接收到信息數據后，該NHV也將執行相同的過程，選擇自己的NHV，并把信息數據傳遞出去，直到信息數據傳遞到目標車輛DV為止。在與下一跳NHV進行通信的時候，有以下情況需要考慮：

(a)：如果DV在IV的發送信息范圍內，那么IV將不再執行選擇下一跳的程序，直接把信息數據發送目標車輛DV。當DV接收到信息數據之后，會向IV發送ACK應答信息。

(b)： 如果IV在其發送信息范圍內找不到DV，IV將向其所有周圍車輛發送得到它們位置和車輛速度的請求信息，然后，根據式(1)計算各自的時間T出來，并存放到IV的緩沖區中，進而通過比較各個T大小，來選擇與對應T值最小的那個車輛作為IV的NHV，IV把所要傳遞的信息數據傳遞給該NHV。由該HHV根據(a)(b)規則來進行信息數據的傳遞，直到把信息數據傳遞到DV為止。

3路由連接中斷預測

3.1路由連接中斷預測的意義

車輛在實際的行車過程中，對于隨機分布在車道上任意兩個節點車輛的速度彼此相等的概率是很小的，當兩個節點車輛的速度不一致時，路由連接中相互連接的兩個節點車輛之間的通信就有發生連接中斷的可能，研究路由連接中斷的可能性不僅可以提高兩個節點車輛之間信息傳遞的效率，而且對整個信息傳遞過程中涉及到路由選擇有重要作用，通過在路由選擇算法中增加路由連接中斷的預測策略可改善路由選擇算法的性能。

3.2路由連接中斷預測算法

路由連接中斷發生在各節點車輛之間進行信息傳遞的過程中，車聯網中節點車輛之間進行信息傳遞的模型如圖1所示。

圖1　WAVE中節點車輛之間的信息傳遞模型

圖1中t1，t2，t3分別表示三個連續發生且不同的時間點，D(t1)，D(t2)，D(t3)，分別表示t1，t2，t3時間點處任意節點車輛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)

通過對以上分析，結合FMHR算法思想，分別在信息源車輛A和其下一跳車輛B兩端增加路由連接中斷的預測，車輛A的偽代碼：

利用getcurrentposition函數分別獲取車輛A和車輛B的當前坐標(Xat3,Yat3)、(Xbt3,Ybt3)。

根據式(4)計算此時車輛A與車輛B之間的距離。

根據式(5)、式(6)、式(7)估算車輛B在其信息發送半徑R內活動的剩余時間Tt3。

if T(32) > Tt3 //說明車輛B已經不在R的范圍內活動了，車輛A需要重新啟動選擇新的下一跳。

啟動選擇下一跳的程序。

else if Tt3/T(32) < 2 //車輛A計算得知，車輛B可以接收到自己所發送的信息，而自己將接收不到車輛B返回來的信息，此時，車輛A啟動選擇下一跳的程序。

啟動選擇下一跳的程序

else //認為路由連接正常，正常接收和發送信息

sendWSM(mysockfd,send_wsmp, wsm_data);

當車輛B接收到數據信息時，車輛B依然使用T(21)來估算數據在t2時間點時從車輛B發出到車輛A所需要的時間，通過車輛B的估算，如果這個時間滿足某些條件，車輛B認為其發送的數據在沒有被車輛A接收到的情況下，車輛B本身已經駛離了車輛發送半徑R的覆蓋范圍，因此，車輛B的偽代碼：

if根據式(6)計算出來的時間T比值T(21)的值小于1

{

sendWSM(mysockfd,send_wsmp,wsm_data);//車輛B將作為車輛A的下一跳向前發送信息數據。注意，此時，車輛B把時間T發送給車輛A作為參考，同時車輛B將盡其最大的努力以廣播形式告之車輛A，車輛A接收到這一信息之后將重新選擇新的下一跳來傳遞信息

}

else if ( 1 <時間T/T(21)的值 < 2)

{//此時，車輛B認為其發送的應答信息可以被車輛A所接收到，但是，車輛A再次發送的數據將不會被自己接收到

sendWSM(mysockfd,send_wsmp,wsm_data);

Broadcast();

}

else

{//此時，車輛B對路由中斷不做任何預測，正常接收數據和發送數據

sendWSM(mysockfd,send_wsmp,wsm_data);

}

4實驗及結果分析

仿真過程中，信息從IV到DV的傳輸策略選擇FMHR算法，而預測路由中斷方法作用于選擇傳輸策略后路由節點車輛間通信的路由連接情況，可看作是對FMHR算法的補充。為了更好地驗證預測路由中斷方法有效，分別采用對802.11p支持較好的NCTUns-6.0[7-8]對FMHR和FMHR-V進行仿真，仿真參數如下：車道長度為2.6 km×2.6 km，車輛個數150，發送范圍550 m、650 m、750 m，數據發送速率6 Mb/s，仿真時間100 s，包的大小為1 000 bytes，車輛類型CarAgent，車輛速度在15～45 m/s，由配置文件profile來隨意分配車輛速度。僅ID為1的路口有SignalAgent控制。通過AWK提取仿真的相關數據信息[9-10]，并通過MATLAB繪制圖形以進行實驗分析，見圖1，圖2。

圖1數據包延時與仿真時間關系

圖2　數據包丟失個數與仿真時間關系

通過分析可知，當車輛的信息發送范圍設置在550 m時，算法在修改前和修改后的數據包丟失個數和數據包延時上區別幅度不是太大，當車輛的信息發送范圍設置在650 m和750 m時，FMHR-V性能相對于原有算法FMHR的性能有所改善，經分析得知，隨著發送半徑的范圍增大，當發送信息的車輛和接收信息的車輛之間的速度不一致的時候，FMHR算法中發送信息的車輛無法提前得知其下一跳在未來某段時間內已經不在其信息的發送半徑范圍內，只有經過某一段時間才會認為通信中斷，這樣就造成無謂的等待時間；而在FMHR-V算法中，當作為下一跳的車輛一旦離開或者將要離開發送信息車輛的發送信息半徑范圍時，作為下一跳的車輛和發送信息的車輛都可以盡自己最大努力對這一事件進行預測。當發送信息的車輛通過FMHR-V預測到這一事件時，即可選擇新的下一跳，一方面節省了無謂的等待時間，某種程度上增強了整個信息傳輸過程的實時性；另一方面也減少了不可能被接收到的數據包的發送，進而，也減少了數據包被下一跳或者終端接收時丟失的可能性。

5結語

通過理論研究和相關實驗數據分析，在車聯網的各節點車輛快速移動過程中，各節點車輛與車輛之間通過建立起來的路由連接進行通信，當處在路由連接中的某兩個節點車輛之間的速度不一致時，節點車輛之間建立起來的路由連接會因此而處于不穩定狀態，發生路由連接中斷，通過預測該中斷發生的可能性，并在預測的基礎上采取相應措施，可在一定程度上改善信息傳遞的性能。

參考文獻：

[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]張繼永,楊斌. 無線車聯網WAVE車-車通信中的一種路由算法實現[J].通信技術,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協議性能仿真[J].計算機應用,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—)，女，碩士，主要研究方向為計算機網絡、自然語言處理;

哈力木拉提·買買提(1959—)，男，教授，碩士生導師,主要研究方向為圖像處理、模式識別等。