岳志鵬，周永，黃弘（西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，成都 610039）

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

岳志鵬，周永，黃弘
（西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，成都 610039）

0　引言

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

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

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

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

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

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

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

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

2　算法描述

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

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

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

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

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

圖3　車輛更換道路

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

2.2條件假設(shè)及基本概念

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

2.3路由選擇

路由選擇的過程如下：

（1）車輛周期性地廣播信標(biāo)消息，即車輛的位置信息，消息中包括（IDi，Roadi，Xi，Yi，Vx，Vy），Roadi表示車輛所在的路段編號(hào)，同時(shí)，每輛車和路邊單元都維護(hù)并周期性更新一個(gè)鄰居表。車輛之間通過交換信標(biāo)消息，將直接鄰居的ID和位置信息添加到自己的鄰居列表中，由此獲得對(duì)自身周圍網(wǎng)絡(luò)拓?fù)淝闆r的認(rèn)知。

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

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

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

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

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

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

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

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

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

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

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

●D（Rs'）!=∞

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

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

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

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

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

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

圖5　路由選擇流程圖

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

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

Su W和Lee S J給出了預(yù)測(cè)每條鏈路連接時(shí)間的公式：

其中：

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

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

圖6　車輛i和j同向行駛

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

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

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

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

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

3　結(jié)語

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

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

[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)標(biāo)準(zhǔn)化現(xiàn)狀及發(fā)展趨勢(shì)[J].電信網(wǎng)技術(shù),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-），男，四川江油人，碩士，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)

黃弘（1987-），女，山東煙臺(tái)人，碩士，研究方向?yàn)檐浖こ處?、Android開發(fā)2015-12-30

2016-02-13

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

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

周永（1989-），男，四川廣安人，碩士，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)

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.