車載自組織網絡路由算法研究

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

車載自組織網絡路由算法研究

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

0　引言

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

1　一種基于地理位置的路由協議

1.1物理長度產生的影響

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

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

1.2平面圖產生的影響

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

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

2　算法描述

2.1車載網絡城市結構圖

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

圖1　車載網絡城市結構圖

圖2　車載單元結構圖

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

圖3　車輛更換道路

在路徑選擇方面，交通信息服務中心依據車流量采集系統和電子地圖提供指定路段的車流量數據，并根據源節點和目的節點的位置信息、相關路段的車輛數目以及物理長度計算源節點到目的節點的數據傳輸的路徑。

2.2條件假設及基本概念

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

2.3路由選擇

路由選擇的過程如下：

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

（2）城區主干道啟用車流量采集系統，實時采集各路段的車流量。

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

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

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

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

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

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

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

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

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

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

●D（Rs'）!=∞

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

③重復步驟2，直至A中包含網絡中所有的節點（循環次數=節點數）。

車輛S將返回的消息放入數據包分組的頭部，并根據（Ri，Rj，…，Rd）轉發基站路由的次序，依次向這些RSU基站轉發消息，當RSU基站收到消息后，就在數據分組的頭部做好“簽到”標記，直至將數據傳輸到最后的基站Rd，該基站再將數據轉發至車輛D。圖5給出了路由選擇流程圖。

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

2.4數據轉發

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

圖5　路由選擇流程圖

在介紹本算法的轉發方案前，先強調一點，在路由的轉發時，并不是道路中的所有車輛都參與數據包的轉發，而是選擇符合條件的車輛節點參加數據包的轉發。

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

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

其中：

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

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

圖6　車輛i和j同向行駛

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

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

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

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

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

3　結語

本文主要研究的是城市交通環境下的車載自組織網絡的路由協議，而主要研究其中基于地理位置的路由問題。

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

[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]畢然,黨梅.智能交通系統標準化現狀及發展趨勢[J].電信網技術,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-），男，四川江油人，碩士，研究方向為計算機網絡

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

2016-02-13

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

車載自組織網絡；路由協議；連通性

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

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.