車載自組織網(wǎng)絡路由算法研究

岳志鵬，周永，黃弘（西華大學計算機與軟件工程學院，成都 610039）

車載自組織網(wǎng)絡路由算法研究

岳志鵬，周永，黃弘
（西華大學計算機與軟件工程學院，成都 610039）

0　引言

隨著各國城市化和計算機化的發(fā)展，極大地推動了通信技術在道路交通領域的發(fā)展，一些發(fā)達國家開始研究以提高安全性和效率為目標的交通系統(tǒng)，即智能交通系統(tǒng)（Intelligent Transport System，簡稱ITS）。交通管理系統(tǒng)中嵌入了ITS，ITS是由信號控制系統(tǒng)、監(jiān)控系統(tǒng)、交通流動態(tài)系統(tǒng)和車輛收費系統(tǒng)等聯(lián)網(wǎng)組成，而ITS服務則包括廣播、電臺、路邊終端、路邊情報等發(fā)布渠道，由動態(tài)導航信息服務系統(tǒng)、綜合樞紐換乘信息服務系統(tǒng)、停車信息服務系統(tǒng)等聯(lián)網(wǎng)組成的，由此車載自組織網(wǎng)絡（Vehicle Ad hoc Networks，簡稱VANET）應運而生。本文研究的是城市交通環(huán)境下的車載自組織網(wǎng)絡路由協(xié)議，而主要研究其中基于地理位置的路由問題。傳統(tǒng)的基于地理位置的路由協(xié)議存在著不足，本文提出一種城市環(huán)境下基于地理位置的車載自組織網(wǎng)絡路由協(xié)議GCRR（Geography-based and Network Connectivity Reliable Routing）。GCRR有如下特點：算法不僅考慮了道路的物理長度，而且考慮了道路的連通性；在道路的十字路口部署了RSU基站，來輔助路由發(fā)現(xiàn)；在數(shù)據(jù)傳輸過程中，用公式推導出了使鏈路穩(wěn)定的方案；使得數(shù)據(jù)包投遞率增加，吞吐量增加。

1　一種基于地理位置的路由協(xié)議

1.1物理長度產(chǎn)生的影響

傳統(tǒng)的基于位置的路由協(xié)議主要是考慮了道路的物理長度，而并沒有考慮道路的車輛數(shù)目和道路連通性等因素，因此在應用中會影響網(wǎng)絡中端到端的平均時延和數(shù)據(jù)包投遞率。

依據(jù)物理距離作為判斷路由選擇的機制，是傳統(tǒng)的基于位置路由協(xié)議的局限。所以，在結(jié)合了道路物理距離的同時，需要考慮道路的其他因素和網(wǎng)絡的連通性。

1.2平面圖產(chǎn)生的影響

由于城市交通道路周圍存在大量的建筑物，而車輛無法對它的存在做出判斷，無論使用Gabriel圖還是相關鄰近圖都會隔斷網(wǎng)絡拓撲結(jié)構。為了解決上述問題，可以在每個十字路口部署RSU基站，數(shù)據(jù)包可沿著城市中的道路進行轉(zhuǎn)發(fā)，來提高網(wǎng)絡的連通性。

綜合以上因素，本文給出了一種基于地理位置的路由算法GCRR，該算法的路徑選擇部分是基于路道中車輛數(shù)目和道路的物理長度，數(shù)據(jù)轉(zhuǎn)發(fā)部分則考慮了鏈路的持續(xù)時間，即算法由路徑選擇和數(shù)據(jù)轉(zhuǎn)發(fā)兩部分組成。

2　算法描述

2.1車載網(wǎng)絡城市結(jié)構圖

城市主干道路上部署了車流量采集系統(tǒng)，并在十字路口和三岔路口部署了路邊單元（RSU），（見圖1，其中，路邊單元包括計算處理模塊、無線接口、以太網(wǎng)接口等，車載單元由車路通信模塊、車間通信模塊、電子地圖和GPS定位模塊等組成（見圖2，RSU通過無線接口與車輛互換信息，并且收集車輛的具體位置信息，同時RSU通過以太網(wǎng)接口與交通信息服務中心進行通信。

圖1　車載網(wǎng)絡城市結(jié)構圖

圖2　車載單元結(jié)構圖

當有車輛駛出當前街道，并進入十字路口時，RSU能夠?qū)⒋诵畔⒉杉?，并且車流量采集系統(tǒng)統(tǒng)計道路密度。交通信息服務中心TISC（Traffic Information Service Center）依據(jù)RSU和車流量采集系統(tǒng)，統(tǒng)計城市中所有車輛的位置信息和道路密度，且記錄著每條道路的交通狀況，并可以實時更新道路中的車輛信息，使交通信息服務中心可以獲得實時準確的道路交通信息。如圖3所示，當車輛1從街道Road1駛進Road2時，RSU就會采集到此信息，TISC更改車輛位置更新數(shù)據(jù)內(nèi)容。位置更新數(shù)據(jù)的內(nèi)容包括：（IDi，Roadi，Roadj，Xi，Yi，Vx，Vy），其中IDi代表車輛I的編號，Roadi指之前所在的路段編號，Roadj指剛駛?cè)氲穆范尉幪?，Vx，Vy表示車輛的移動速度和移動方向，Xi，Yi表示車輛所處的地理位置。

圖3　車輛更換道路

在路徑選擇方面，交通信息服務中心依據(jù)車流量采集系統(tǒng)和電子地圖提供指定路段的車流量數(shù)據(jù)，并根據(jù)源節(jié)點和目的節(jié)點的位置信息、相關路段的車輛數(shù)目以及物理長度計算源節(jié)點到目的節(jié)點的數(shù)據(jù)傳輸?shù)穆窂健?/p>

2.2條件假設及基本概念

在該算法中，假設所有車輛都安裝GPS導航系統(tǒng)，車輛可以獲取他們的位置信息和其他車輛的位置，導航系統(tǒng)能為車輛提供城市街道的電子地圖等。本文中提到的節(jié)點是指車輛模型，假設處于十字路口的節(jié)點可以跟無線傳輸范圍內(nèi)的非十字路口節(jié)點進行通信，而不在同一條道路上的非十字路口節(jié)點間不可通信。因此，數(shù)據(jù)的轉(zhuǎn)發(fā)過程，主要是從非十字路口節(jié)點向十字路口節(jié)點逼近，十字路口節(jié)點再轉(zhuǎn)發(fā)給另一個非十字路口節(jié)點，直到數(shù)據(jù)轉(zhuǎn)發(fā)到目的節(jié)點為止。文中提到的車輛為源節(jié)點，車輛為目的節(jié)點。

2.3路由選擇

路由選擇的過程如下：

（1）車輛周期性地廣播信標消息，即車輛的位置信息，消息中包括（IDi，Roadi，Xi，Yi，Vx，Vy），Roadi表示車輛所在的路段編號，同時，每輛車和路邊單元都維護并周期性更新一個鄰居表。車輛之間通過交換信標消息，將直接鄰居的ID和位置信息添加到自己的鄰居列表中，由此獲得對自身周圍網(wǎng)絡拓撲情況的認知。

（2）城區(qū)主干道啟用車流量采集系統(tǒng)，實時采集各路段的車流量。

（3）車輛S由電子地圖獲知本路段兩端的RSU基站地理位置，并由多跳轉(zhuǎn)發(fā)的方式向RSU發(fā)送路徑請求包，數(shù)據(jù)包內(nèi)容包括（IDs，IDd，Xs，Ys，Xd，Yd，Vsx，Vsy），其中，IDs指代源節(jié)點的編號，IDd指代目的節(jié)點編號，Xs，Ys指代當前源節(jié)點的地理位置，Xd，Yd表示目的節(jié)點的地理位置，Vsx，Vsy表示源節(jié)點的行駛速度和行駛方向。

若交通信息服務中心發(fā)現(xiàn)車輛S與車輛D處在同一路段，則不用進行如下計算，直接將數(shù)據(jù)通過多跳方式轉(zhuǎn)發(fā)至車輛D。否則，交通信息服務中心通過車流量采集系統(tǒng)得到第i條路段的車輛數(shù)目，建立一個每條路段的權值公式并計算每條路段的權值，權值公式定義如下:

其中，Li為本路段道路的物理長度，Ni為本路段的車輛數(shù)目，Wi為本路段的道路權重，此參量為Ni和Li的綜合度量，此值表示本路段的物理長度越小，車輛數(shù)目越多，此路段就越可能被選為路由路徑。使用道路權重因子是為了充分利用車輛數(shù)量多的路段，也為了選擇能盡快將數(shù)據(jù)包傳遞至路口RSU的路段。圖4為TISC收集消息及工作流程圖。

最先收到路徑請求包的RSU基站，將此消息發(fā)送給交通信息服務中心，而后來接受到數(shù)據(jù)的RSU將此信息刪除。交通信息服務中心將依據(jù)路徑請求包的內(nèi)容，通過Dijkstra算法計算出路由路徑，再將傳輸路徑數(shù)據(jù)包回復給剛才的RSU基站，傳輸路徑數(shù)據(jù)包內(nèi)容包括（Ri，…，Rj，Xd，Yd），其中，Ri，…，Rj為路由轉(zhuǎn)發(fā)經(jīng)過的RSU基站編號，Xd，Yd為車輛D的地理位置。Dijkstra算法如下：

圖4　 TISC收集消息及工作流程圖

①設Rs'為源RSU基站（路口），令A為已經(jīng)尋找到的最短路徑路口的集合，A＝{Rs'}，把所有不在集合A的節(jié)點放入集合B中，B={R1，R2，…，Ri}。若路口Rs'與路口R1直接相連，有：

其中，W（Rs',1）代表從源路口Rs'到路口1的權值，即D（R1）代表從源路口Rs'到路口R1的權值。

若路口Rs'與路口R1不直接相連，有：

②尋找一個不在中的節(jié)點Ri，其D（Ri）值最小，把它加入到中，再對所有不在中的節(jié)點Rj，

●Rj節(jié)點之前與Rs'不相鄰,即D（Rs'）=∞，則D（Rs'）更新為：

●D（Rs'）!=∞

則用[D（Rs'），D（Ri）+W（Ri，Rj）]中較小的值去替換之前的D（Rs'）值，即:

③重復步驟2，直至A中包含網(wǎng)絡中所有的節(jié)點（循環(huán)次數(shù)=節(jié)點數(shù)）。

車輛S將返回的消息放入數(shù)據(jù)包分組的頭部，并根據(jù)（Ri，Rj，…，Rd）轉(zhuǎn)發(fā)基站路由的次序，依次向這些RSU基站轉(zhuǎn)發(fā)消息，當RSU基站收到消息后，就在數(shù)據(jù)分組的頭部做好“簽到”標記，直至將數(shù)據(jù)傳輸?shù)阶詈蟮幕綬d，該基站再將數(shù)據(jù)轉(zhuǎn)發(fā)至車輛D。圖5給出了路由選擇流程圖。

通常認為道路的連通性與該道路上的車輛數(shù)量有關，車輛數(shù)量越多，則此道路的連通性越好。

2.4數(shù)據(jù)轉(zhuǎn)發(fā)

當車輛S獲知路由路徑后，將傳輸路徑數(shù)據(jù)包的內(nèi)容添加到車輛S的分組頭部，包括傳輸需要經(jīng)過的RSU基站（Ri…Rj），和目的車輛的具體位置（Xd，Yd）。車輛S將按照路徑S-RSUi…RSUj-D進行轉(zhuǎn)發(fā)，而這之間的每一條路段，將采用多跳的方式。

圖5　路由選擇流程圖

在介紹本算法的轉(zhuǎn)發(fā)方案前，先強調(diào)一點，在路由的轉(zhuǎn)發(fā)時，并不是道路中的所有車輛都參與數(shù)據(jù)包的轉(zhuǎn)發(fā)，而是選擇符合條件的車輛節(jié)點參加數(shù)據(jù)包的轉(zhuǎn)發(fā)。

經(jīng)典的GPSR協(xié)議在選取下一跳節(jié)點時，考慮在無線可傳輸范圍內(nèi)，選取離目的節(jié)點最近的節(jié)點作為下一跳，這樣的方式只考慮了盡量遠距離的傳輸，而忽略了行駛中車輛的運動狀態(tài)而導致傳輸鏈路不穩(wěn)定。數(shù)據(jù)的轉(zhuǎn)發(fā)是采取多跳的方式，若其中的一條鏈路斷裂，就會導致數(shù)據(jù)包丟失和數(shù)據(jù)重傳，從而增加了端到端的平均時延，降低了數(shù)據(jù)包的投遞率。因此，每跳鏈路的穩(wěn)定是數(shù)據(jù)轉(zhuǎn)發(fā)中需要重點考慮的，本算法在數(shù)據(jù)轉(zhuǎn)發(fā)部分，下一跳節(jié)點的選取是，將數(shù)據(jù)包轉(zhuǎn)發(fā)給同向行駛的速度盡量相近的車輛。此方案是通過下面的公式推導出來的。

Su W和Lee S J給出了預測每條鏈路連接時間的公式：

其中：

公式（9）中，vi，vj代表移動節(jié)點i，j的速度，（xi，yi），（xj，yj）代表移動節(jié)點i，j的坐標，θi，θj代表節(jié)點i，j的移動方向，r是節(jié)點的有效通信距離。兩個節(jié)點之間的鏈路持續(xù)時間就是預測時間，Su W和Lee S J只給出了鏈路持續(xù)時間的公式，而沒有再簡潔的結(jié)果。這里本文結(jié)合城市車載網(wǎng)絡的特點，將此公式繼續(xù)化簡。

在一條道路中，車輛的下一跳選擇，在方向上分為傳遞給同向行駛的車輛和逆向行駛的車輛，如圖6所示，當車輛i選擇同向行駛的車輛j作為下一跳時，θi= 0，θj=0，代入到公式（9）中，此時：

圖6　車輛i和j同向行駛

將式（10）代入到式（8）中有：

如圖7所示，當車輛i選擇逆向行駛的車輛j作為下一跳節(jié)點時，θi=0，θj=180°，代入到公式（9）中，此時有：

圖7　此圖車輛i，j逆向行駛

將（12）代入到（8）中有：

由公式（11）和（13）可看出，兩公式中只有分母不同，因為（vi-vj）<（vi+vj），所以T1>T2，即選擇同向行駛車輛為下一跳的鏈路持續(xù)時間要長于選擇逆向行駛的。另外，由公式（11），可得出，當vi，vj的大小越接近，則T1越大，即當節(jié)點i和節(jié)點j的行駛速度越相近，鏈路的持續(xù)時間越長。因此，本文在數(shù)據(jù)轉(zhuǎn)發(fā)時，選取在可傳輸范圍內(nèi)，同向行駛的速度相近的節(jié)點作為下一跳節(jié)點，以保證鏈路的穩(wěn)定性。即車輛通過查找自己的鄰居列表，選擇與自身行駛方向一致和速度相近的車輛作為下一跳節(jié)點并發(fā)送數(shù)據(jù)包，以此類推，直到數(shù)據(jù)包到達傳輸路徑的第一跳路邊單元，此路邊單元根據(jù)傳輸路徑數(shù)據(jù)包的內(nèi)容地址，繼續(xù)轉(zhuǎn)發(fā)，直到到達節(jié)點D位置。

3　結(jié)語

本文主要研究的是城市交通環(huán)境下的車載自組織網(wǎng)絡的路由協(xié)議，而主要研究其中基于地理位置的路由問題。

通過對經(jīng)典路由協(xié)議的特點和原理進行了研究后，本文根據(jù)它們存在的不足和城市道路的特點，給出了基于地理位置的路由協(xié)議。本算法在路由選擇部分，利用了交通信息服務中心和交叉口的基站，從而減少了路由查找的時間和路由開銷，另外，借用車流量采集系統(tǒng)，并綜合考慮了道路的物理長度和車輛密度因素。在路由節(jié)點的轉(zhuǎn)發(fā)部分，采用使鏈路穩(wěn)定的方案，通過對比同向和逆向選取下一跳節(jié)點的情況，可推出本算法的轉(zhuǎn)發(fā)方案，即選擇同向行駛的速度相差較近的車輛作為下一跳節(jié)點。同時，像經(jīng)典協(xié)議那樣，只考慮道路的物理長度而進行貪婪轉(zhuǎn)發(fā)的機制是有缺陷的，所以，在算法中考慮道路的連通性對于提高網(wǎng)絡的吞吐量是有必要的。

[1]Su W,Lee S J,Gerla M.Mobility Prediction and Routing in Ad Hoc Wireless Networks[J].International Journal of Network Management,2001,11(1):3-30.

[2]畢然,黨梅.智能交通系統(tǒng)標準化現(xiàn)狀及發(fā)展趨勢[J].電信網(wǎng)技術,2011(4):44-47.

[3]Dijkstra E W.A Note on Two Problems In Connexion With Graphs[J].Numerische Mathematik,1959,1(1):269-271.

[4]Tee C,Lee A C R.Survey of Position Based Routing For Inter Vehicle Communication System[C].Distributed Framework and Applications,2008.Dfma 2008.First International Conference on.IEEE,2008:174-182.

[5]Tian J,Stepanov I,Rothermel K.Spatial Aware Geographic Forwarding For Mobile Ad Hoc Networks[J]，2002.

[6]Karp B,Kung H T.GPSR:Greedy Perimeter Stateless Routing for Wireless Networks[C].Proceedings of The 6th Annual InternationalConference on Mobile Computing and Networking.ACM,2000:243-254.

[7]Sherali Zeadally,Ray Hunt,Yuh-Shyan Chen,Et Al.Vehicular Ad Hoc Networks(VANETS):Status,Results,and Challenges[J]. Telecommunication Systems,2012,50(4):217-241.

[8]Karnadi F K,Mo Z H,Lan K.Rapid Generation of Realistic Mobility Models for VANET[C].Wireless Communications and Networking Conference,2007.WCNC 2007.IEEE.IEEE,2007:2506-2511.

VANET;Routing Protocols;Connectivity

Research on VANET Routing Algorithm

YUE Zhi-peng，ZHOU Yong，HUANG Hong

（College of Computer and Software Engineering,Xihua University,Chengdu610039）

1007-1423（2016）05-0012-06

10.3969/j.issn.1007-1423.2016.05.003

岳志鵬（1990-），男，四川江油人，碩士，研究方向為計算機網(wǎng)絡

黃弘（1987-），女，山東煙臺人，碩士，研究方向為軟件工程師、Android開發(fā)2015-12-30

2016-02-13

車載自組織網(wǎng)絡是專為實現(xiàn)車輛間通信而設計的無線自組織網(wǎng)絡。然而，車載自組織網(wǎng)絡的拓撲變化快等特點使它面臨著挑戰(zhàn)，其中需要解決的關鍵技術之一是路由選擇問題。傳統(tǒng)的自組織網(wǎng)絡路由協(xié)議存在缺陷，不適用于車載自組織網(wǎng)絡。經(jīng)過對經(jīng)典的路由協(xié)議的研究，給出一種適用于城市交通場景下的、基于地理位置的路由算法，主要包括路由的選擇和數(shù)據(jù)包的轉(zhuǎn)發(fā)兩個部分。

車載自組織網(wǎng)絡；路由協(xié)議；連通性

周永（1989-），男，四川廣安人，碩士，研究方向為計算機網(wǎng)絡

VANET is designed for the realization of communication between vehicle wireless self-organized networks.However,VANET topology changes fast and make it faces challenges,which need to be solved,is one of the key technologies of routing problem.Traditional self-organizing network routing protocol is flawed,it does not apply to VANET.After the classical studies of routing protocols,gives a suitable city traffic scene location-based routing algorithms,including the choice of the routing and packet forwarding two parts.