YOUSEFI Saleh,ABBASI Tofigh,ANVARI Zahra

（1.烏爾米耶大學工學院計算機系，伊朗烏爾米耶；2.阿薩德大學沙貝斯塔爾分校計算機系，伊朗沙貝斯塔爾）

1 引 言

隨著汽車產業(yè)的快速發(fā)展，私人汽車與公共交通同樣成為現(xiàn)代生活的必需品，人們不得不花費大量時間用于通勤，而交通擁擠使這一問題變得更加嚴重.交通擁擠對出行者、商人、公司和城市帶來各種負面影響.Schrank等[1]根據(jù)德克薩斯州交通協(xié)會2011年度城市流動報告總結了美國439個城市的交通出行時間和燃料消耗.結果表明，在2010年，前15名城市的交通延誤約占所有城市的58%，前20名城市的交通延誤超過全年的65%，人口超過三百萬城市的燃料消耗為16億加侖（大約為全國的70%）.隨著擁擠逐年加重，交通費用也隨之增長.

表1 擁擠對普通通勤者的影響（美國439個城市）[1]Table 1 Congestion effect on the average commuter(for 439 U.S.urban areas)[1]

如表1所示，2010年，439個城市的總擁擠費用為1009億美元，平均每輛通勤汽車的擁擠費用為713美元.因此，降低擁擠程度可以減少出行時間和燃料排放，進而大幅減少交通費用.數(shù)十年來，智能交通系統(tǒng)利用各種先進技術提高城市交通系統(tǒng)的質量.作為ITS的一個重要目標，有效路徑的搜索可以通過交通信息系統(tǒng)和車輛導航這兩種方式來實現(xiàn).前者可以獲得實時交通信息，如車流密度和車輛速度，后者是根據(jù)已有交通信息規(guī)劃有效路徑.

目前，大多數(shù)車輛導航系統(tǒng)使用的是預先設定的離線地圖和從GPS得到的導航數(shù)據(jù).Nadi和Delavar[2]利用離線地圖和由歷史數(shù)據(jù)估算的路況提高了系統(tǒng)性能.但由于在路徑規(guī)劃時缺少實時交通信息使系統(tǒng)性能變差.因此，快速變化的路況導致給出的路徑不總是最優(yōu)的.基于DSRC（專用短波通信）車載通信技術的發(fā)展，使獲得實時交通信息變成可能，考慮將實時交通信息運用到車輛路徑選擇算法中，可以獲得更加有效的路徑.

本文提出的方法包括兩個主要階段：（1）更新交通信息；（2）車輛路徑選擇.在第一階段，利用車輛交互通信設計和使用交通信息系統(tǒng).在第二階段，利用收集的交通信息，計算每個RSU（路側單元）通往目的地的最優(yōu)路徑.本文提出兩個算法，即一步路徑選擇算法和逐步路徑選擇算法.

2 相關研究

本文主要包含兩部分，即交通信息收集和最優(yōu)路徑選擇，有關這兩方面的既有研究如下所述.

2.1 交通信息系統(tǒng)

利用ITS獲得交通信息的方式有多種，最常用的有視頻圖像處理、紅外線傳感器、地磁傳感器、感應線圈傳感器和壓電傳感器等.Mimbela和Klein[3]詳細研究了每種方法的優(yōu)缺點.但由于這些方法不能很好地應用于較大規(guī)模區(qū)域，其應用還受天氣條件和交通狀況的限制，因此提出了一些適用性較強的新方法，相關介紹如下.

在這些先進方法中，GPS（全球定位系統(tǒng)）通常被用作輔助工具來收集交通信息.Dhingral和Gull[4]研究了車輛速度、通行能力和車流密度之間的關系，他們通過觀測和計算歷史交通信息，提出了能夠計算城市機動車數(shù)量的模型.Skordyli和Trigoni[5]利用固定接入點檢測車輛速度和密度以制定路徑方案，但由于固定接入點較難獲取車流密度，根據(jù)交通流理論（Dhingral和Gull[4]），利用檢測器得到的平均速度和交通量計算出車流密度.

車輛交互通信被用在許多最近提出的方法中.Kitani等[6]利用帶有信息擺渡的車輛交互通信技術，提出了一種有效收集、存儲和傳輸交通信息的方法.這種方法將沿既定路徑行駛的公共汽車作為信息擺渡，為了提高低密度區(qū)域的信息傳輸能力，公共汽車盡可能多地從周圍車輛中收集交通信息，并將收集到的信息周期性地傳給臨近車輛.

Khosroshahi等[7]為獲得城市道路上的實時交通信息提出了一種新方法，這種方法基于伴有車輛交互通信和車輛路側通信的車輛自組織網絡與其他一般系統(tǒng)的組合，除了費用函數(shù)和一些已經被定義過的參數(shù)，他們首次提出了一些新參數(shù)，例如不確定性，用于解決交通信息中的路徑選擇問題.

2.2 車輛路徑選擇系統(tǒng)

傳統(tǒng)的最短路徑（SP）問題已被廣泛研究.Fan等[8]證明了當效用函數(shù)是線性或指數(shù)形式時，無論網絡是固定的還是隨機的，為了計算最優(yōu)路徑，都需要借助Dijkstra算法的有效變形形式.Delling和Wagner[9]證明了如果網絡是非穩(wěn)定的、動態(tài)的、隨機的，標準SP算法無法得出期望的最小費用路徑，并且最優(yōu)路徑不是合理路徑.由于存在動態(tài)變化的參數(shù)，因此需要在計算時制定一些規(guī)則，Boutilier等[10]，F(xiàn)eldman和Valdez-Flores[11]研究了這一問題.Bander和White[12]提出了AO*算法，用于有終端成本非穩(wěn)定、隨機最短路徑問題.對于非穩(wěn)定的情況獲得最短路徑，Hashemi等[13]用時變效用研究了行駛時間和停車時間.Lim等[14]提出了一種考慮延誤隨機分布的最優(yōu)路徑算法.Kim等[15]、Psaraftis和Tsitsiklis[16]詳細地闡述了駕駛員可以獲得每條路段擁擠狀態(tài)的情況.而Ramalingam和Reps則實際運用了這一算法.在求解動態(tài)最短路徑（DSP）的算法中，RR算法作為一種更新最短路徑的完全動態(tài)DSP算法，其應用最為廣泛.Buriol等[18]、Frigioni等[19]、Fortz和Thorup[20]在他們的研究中也用了這種算法.RR算法已經被證明是解決DSP問題的最有效的方法.

Goel等[21]研究了有時間約束的最短路徑問題，他試圖在時間約束內找到從單個出發(fā)點到所有目的地的最短路徑，并且證明這是一個非確定性多項式困難問題（NP困難問題）.在實際中，由于車輛數(shù)據(jù)龐大，任何路徑選擇算法都應該在固定的時間限制內以分布式方式計算，就是說每輛車通過自身獲得可行的最優(yōu)路徑，而不是依賴于任何中央實體.此外，還需要考慮路徑選擇算法的速度.上述提到的研究大多都是集中式的，并且耗時很長，不適合在大城市范圍內應用.目前許多導航產品已經被應用多年，為各種出發(fā)地到目的地的用戶尋找最短路徑[22,23].但是由于交通的動態(tài)變化，這些根據(jù)靜態(tài)地圖找到的最短路徑中可能存在擁擠路段.Chen等[24]利用智能交通系統(tǒng)，通過研究歷史交通信息來估算路段上的車流密度.

本文提出的路徑選擇算法不同于以上既有研究，表現(xiàn)為以下幾點.首先，它是請求式的（根據(jù)車輛的請求尋找路徑并發(fā)送建議），而很多既有研究在本質上是主動式的，如Chen等[24]和Fan等[8].其次，它不依賴于蜂窩電話的可用性和車內蜂窩電話的數(shù)量，而既有研究基于蜂窩電話，如Lin等[25].最后，由于路側單元（RSU）比蜂窩基站的成本低，本文提出的方法中，每個RSU（定向天線）的作用范圍不止包含一條路段，而蜂窩基站雖然能同時覆蓋幾條路段，但會引起每條路段車流密度的估算錯誤.

使用DSRC比其他通信網絡更優(yōu)越，這是因為無線保真技術（Wi-Fi）和無線通信技術（Zigbee）標準的工作環(huán)境為2.4 GHz免授權頻段，容易受到網絡干擾，并且它們的無線電程相對于DSRC較短.其他無線個人區(qū)域網（WPAN）和無線局域網（WLAN）技術有明顯缺點.比如，藍牙技術（IEEE 802.13.1）的數(shù)據(jù)速率為723 Kbps，并且高達10 m的無線電程，但僅支持8個有效設備，且網絡介入時間很長（3 s）.射頻識別技術（RFID）存在無線電程和數(shù)據(jù)速率較低的問題.他們能夠被用在車輛識別和電子不停車收費系統(tǒng)（ETC）中，但是不能用于一般的獨立虛擬信道（IVC）.

DSRC技術的響應時間相對于蜂窩網絡的1.5–3.5 s和人造衛(wèi)星的 10–60 s較短，僅為200 ms.DSRC特別為所有ITS的應用設計，因此一般情況下它的性能更好.表2為目前可用或將可用的IVC/ITS無線底層技術的比較，來源于Diao[26].

表2 一些無線底層技術的比較[26]Table2 Comparison of considerable wireless sub-layer techniques[26]

3 提出機制

本文提出的方法主要包括兩個階段：（1）交通信息收集；（2）車輛路徑選擇.在第一階段，利用車輛交互系統(tǒng)為交通信息系統(tǒng)獲取最新的交通信息.將定向天線安置在每條路的入口處，以便獲得交通密度和車輛速度等信息，然后將這些信息發(fā)送給數(shù)據(jù)中心.車輛在出發(fā)前會向最近的RSU發(fā)送請求，假設所有RSU相互連通，并且都能夠通過有線或無線網絡與數(shù)據(jù)中心相連.在本文的仿真中，利用的是WiMAX網絡，其他2.5G（比如GPRS和EDGE）或3G蜂窩網絡也可以.在第二階段，每個RSU計算通往目的地的最優(yōu)路徑.本文提出了兩種最優(yōu)路徑算法，即一步車輛路徑選擇和逐步車輛路徑選擇.

圖1 車輛與RSUs的通信（A），RSUs和數(shù)據(jù)中心的通信（B），摘自[27]Fig.1 The communication between vehicles and RSUs(A),RSUs and the data center(B)Adapted from[27]

3.1 階段1交通信息收集方法

利用車輛通信，在城市交通中建立車輛與RSUs之間的聯(lián)系.本文提出的方法中，每個RSU獲得相應路段的交通狀態(tài)，然后將信息傳輸給數(shù)據(jù)中心，整體結構如圖1所示.

如圖1所示，RSUs安裝在交叉口等一些特殊位置.RSUs是多接口的，即一個RSU有幾個無線接口.IEEE802.11接口、單元接口（GPRS）、衛(wèi)星接口和WiMAX接口是一些典型的常用接口.每個RSU服務于特定路段.比如，某交叉口需要四個802.11無線接口和一個WiMAX/GPRS接口，四個802.11無線接口用于接收從車輛發(fā)來的信息，并將從信息中心發(fā)來的交通狀態(tài)發(fā)送給車輛，WiMAX/GPRS接口用于與數(shù)據(jù)中心相互通信.

3.1.1 利用定向天線檢測車輛位置

定向天線周期性地發(fā)送各個路段的路段ID、RSU-IP和RSU-port（如套接字地址）信息.當車輛進入一條路段，它就會收到定向天線發(fā)送的信息，然后車輛識別自身位置，之后將位置信息和前一路段的路段ID發(fā)送給RSU.信息包括路段名稱/ID和RSU的IP地址，為之后建立連接用.

應用定向天線的原因是這些天線有一個指定方向，可以覆蓋很遠的傳輸距離和接收頻段，并且能在更少的步驟內執(zhí)行更多的平行傳輸和接收.Ramanathan等[28]詳細研究了定向天線的優(yōu)點.使用定向天線的另一個優(yōu)點在于它們只與那些沿著路段某一方向行駛的車輛進行通信，極大地降低了信號所受的干擾.

3.1.2 建立連接

在提出的體系結構中，有兩種連接類型，首先是車輛和RSUs之間的連接，其次是RSUs和數(shù)據(jù)中心之間的連接.當接收到當前路段的ID和RSU的信息之后，車輛與RSU之間建立TCP或者UDP連接，并將前一路段的ID傳輸給RSU，利用前一路段的ID和當前路段的ID可以確定車輛的行駛方向.由于RSUs是多接口的，并且一個接口對應一條路段，所以接口能夠容易地識別出數(shù)據(jù)來源的路段.之后，RSU將前一路段和當前路段的路段ID發(fā)送給數(shù)據(jù)中心，用于更新每條路段的交通密度.同TCP這種常見的用于建立車輛與RSUs之間的連接方式一樣，UDP也是一種可行的方式.當RSU套接字地址并通過定向天線傳輸，表明具有固定IP地址的RSU正在監(jiān)聽行駛中的車輛，相應的通信如圖1中A所示.

根據(jù)既有研究，RSUs和數(shù)據(jù)中心之間的通信也應考慮在內.雖然有其他方式，但本文使用集中式構架.換言之，所有的RSUs都將收集到的交通信息傳輸給數(shù)據(jù)中心.如果RSUs有足夠的存儲空間和處理能力，也可以用作數(shù)據(jù)中心.這一步驟涉及兩個實際操作，WiMAX（單點對多點模式）和蜂窩網絡（比如GPRS和EDGE）.在模擬試驗中，利用WiMAX連接RSUs和數(shù)據(jù)中心，相應的通信如圖1中B所示.

3.1.3 數(shù)據(jù)中心功能

數(shù)據(jù)中心有兩個主要功能：（1）更新所有的交通信息數(shù)據(jù)庫；（2）將最新交通狀態(tài)傳輸給所有RSUs.

為實現(xiàn)第一項功能，接收數(shù)據(jù)后，數(shù)據(jù)中心利用WiMAX/GPRS網絡更新數(shù)據(jù)庫.從RSUs接收到的數(shù)據(jù)包括如下幾方面：

①前一路段的ID或名稱；②當前路段的ID或名稱.

根據(jù)前一路段和當前路段的ID，數(shù)據(jù)中心能夠確定車輛的行駛方向，并對數(shù)據(jù)庫作如下更新：將前一路段ID的車輛數(shù)減1；將當前路段ID的車輛數(shù)加1.

為了實現(xiàn)第二項功能，在更新了交通信息數(shù)據(jù)庫之后，將更新的數(shù)據(jù)從信息中心通過WiMAX/GPRS網絡傳輸給RSUs.有兩種可行模式：

①即時更新，數(shù)據(jù)中心更新后，立刻將數(shù)據(jù)傳輸給RSUs；

②請求更新，車輛請求時將數(shù)據(jù)傳輸給RSUs.

即時更新模式中，數(shù)據(jù)中心的數(shù)據(jù)一旦更新，就會傳輸給RSUs，其優(yōu)點在于車輛請求接收更新數(shù)據(jù)的響應時間更短.在請求更新模式中，假設車輛請求獲得交通狀態(tài)，數(shù)據(jù)先從數(shù)據(jù)中心傳輸給RSU，然后再傳給車輛，它的一個最大優(yōu)點是，RSUs與數(shù)據(jù)中心的數(shù)據(jù)交換少，但是相比較即時更新模式，數(shù)據(jù)傳輸給車輛會有略微延遲.

3.2 階段2車輛路徑選擇方法

本文對每輛請求車輛提出兩種通往目的地的路徑選擇計算方法.

當車輛想要獲得到達目的地的最優(yōu)路徑時，它會給RSU發(fā)送一個請求獲取最新交通信息的請求包.收到車輛請求之后，如果RSUs的更新模式是請求更新，RSU就會給數(shù)據(jù)中心發(fā)送一個交通信息更新請求，之后數(shù)據(jù)中心返回一個包含最新交通信息的響應包，RSU將最新的交通信息發(fā)給請求車輛.如果RSUs的更新模式是即時更新，那么RSUs當前的交通信息就是最新的，不需要發(fā)送更新請求，RSUs直接把這個最新的交通信息發(fā)送給請求車輛.

一旦車輛從RSU接收到最新的交通信息，便開始尋找最優(yōu)路徑.尋路過程可在RSU路側單元或者車輛單元中進行.車輛單元尋路過程因其能輔助緩解路網擁擠并降低RSUs費用，而被認為是首選方式.

為了尋找最優(yōu)路徑，首先需要將城市地圖轉換為網絡圖才能利用尋路算法（例如單一起終點Dijkstra算法）計算最優(yōu)路徑.假設如圖2所示，路網包括雙向道路A1、A2、B1、B2等，表示路段名稱和狀態(tài).例如，A1和A2分別表示在交叉口1和交叉口2之間的交通狀態(tài)，A1表示從交叉口1至交叉口2方向的交通狀態(tài)，A2表示反向的交通狀態(tài).

路段上的車輛數(shù)用圖中邊的權重表示，交叉口用節(jié)點表示.本文中權重的具體值將在5.2節(jié)介紹.需要注意的是，為車輛尋找最短路的過程需要依據(jù)路段上最新的交通狀態(tài)和路段長度.由于路段是雙向的，將圖2中的路段進一步變形為圖3.

圖2 城市道路被轉換成網絡圖Fig.2 An example of a street in an urban environment which can be converted into a graph

圖3 圖2中所示城市的拓撲圖Fig.3 The graph representation of the city map of Fig.2

確定了圖中邊的權重值之后，可用標準最短路徑算法計算最短路，如Dijkstra或者它的變形形式.本文提出如下兩種路徑選擇算法：

①一步車輛路徑選擇；

②逐步車輛路經選擇.

3.2.1 一步車輛路經選擇

在一步算法中，利用最新的交通信息，車輛只執(zhí)行一次尋路過程，然后根據(jù)計算路徑駛向目的地.由于尋路只進行一次，而交通狀態(tài)是動態(tài)變化的，某些車輛可能會遇到交通擁擠.

假設車輛在圖2中的交叉口1處，參考最新交通狀態(tài)，求得車輛通往目的地的路徑為：

由于路徑選擇不是動態(tài)的，當車輛到達交叉口3時，路段E2可能正在發(fā)生嚴重擁擠，車輛就會被迫在路段E2上延遲很長一段時間.Wang和Ledley[29]用Dijkstra算法進行了試驗，發(fā)現(xiàn)這種方法找到的最短路徑取決于各個邊的權重.

3.2.2 逐步車輛路經選擇

類似于一步算法，車輛按照最新的交通信息誘導通往目的地.但不同的是，逐步算法在每個交叉口都進行一次尋路計算，因此考慮了交通狀態(tài)的改變.由于最優(yōu)路徑在每個交叉口根據(jù)最新的交通信息進行更新，車輛被交通擁擠延誤的可能性明顯減小.

在步驟1中，啟動路徑選擇算法，從步驟2開始重復這一過程.即，在第一個交叉口（step1），計算過程與一步算法一樣.從第二個交叉口開始，計算過程表現(xiàn)為逐步路徑選擇算法.

比如，假設車輛在交叉口1要到交叉口11，根據(jù)從數(shù)據(jù)中心獲得的數(shù)據(jù)，尋路結果為：

在第一步（交叉口1）時尋路過程已經開始（圖4和圖5的偽代碼中1-5行），因此尋路過程與一步算法一樣.偽代碼用C語言，索引從0開始.

沿著建議路徑，車輛駛向交叉口2.一旦車輛到達交叉口2，就會向最近的RSU請求最新交通信息.從數(shù)據(jù)中心接收到信息之后，車輛就會在交叉口2執(zhí)行到交叉口11的新尋路過程.從交叉口2開始，重復路徑選擇過程（圖4和圖5中第5行）.這一步的最優(yōu)路徑為：

一旦車輛到達交叉口5，就會向最近的RSU發(fā)送請求最新交通信息.從RSU收到最新交通信息之后，執(zhí)行從位置5到目的地11的尋路過程.

反復計算尋路過程，直到車輛達到終點.

在逐步路徑選擇算法中，最大的問題是環(huán)路.假設起點是交叉口4，終點是交叉口8，尋路過程為步驟1、2、……、10，如下所示：

上面的尋路過程在第5步出現(xiàn)了環(huán)路.根據(jù)最短路徑算法的一般情況，每一步是在不了解任何先前尋路信息的情況下進行的.本文提出了兩種方法來解決這一問題，即環(huán)路規(guī)避和環(huán)路監(jiān)測.

在尋路開始之前，執(zhí)行環(huán)路規(guī)避，將車輛經過的路段權重調整為無窮大，然后再執(zhí)行尋路過程.比如，在step2中，在尋路過程開始之前將圖中路段C的權重值調整為無窮大.在step3中，路段C和E的權重值調整為無窮大.在各步驟尋路前，不斷執(zhí)行此過程直到車輛達到目的地.由于權重值的調整不能夠完全避免環(huán)路出現(xiàn)，因此有必要標記出車輛已經經過的交叉口（圖中的節(jié)點），并令車輛不再經過標記交叉口，避免環(huán)路出現(xiàn).將經過的交叉口設置為有效限制條件，能夠解決環(huán)路問題.除了之前提到的邊權調整，算法需要能夠根據(jù)其他限制條件進行改進，比如規(guī)避經過的交叉口.帶有環(huán)路規(guī)避機制的逐步路徑選擇算法的偽代碼如圖4所示.

圖4 帶有環(huán)路規(guī)避機制的逐步車輛路徑選擇Fig.4 Step-by-step vehicle path suggestion improved by the loop avoidance mechanism

第二種方法為環(huán)路監(jiān)測.首先計算最短路徑，然后應用環(huán)路監(jiān)測算法.假設存在環(huán)路，將一條路段或多條路段的權重調整為無窮大.帶有環(huán)路監(jiān)測機制的逐步車輛路徑選擇算法如圖5所示.

圖5 帶有環(huán)路監(jiān)測機制的逐步車輛路徑選擇Fig.5 Step-by-step vehicle path suggestion improved by the loop detection mechanism

圖6 環(huán)路規(guī)避機制Fig.6 Loop avoidance mechanism

舉例說明，在圖6中，利用帶有環(huán)路規(guī)避機制的逐步路徑選擇方法得到一個方案.假設車輛從交叉口1到交叉口11，需要完成以下步驟.

Step 0

Source=1，u=11，path=1→2→3→4→7→11

Step 1車輛到達交叉口2

source=2，u=11，path=1→2→5→6→7→11，weight streetsA1=A2=∞

Step 2 車輛到達交叉口5

Source=5，u=11，path=1→2→5→9→10→11，weight streetsA1=A2=∞ and D1=D2=∞

Step 3 車輛到達交叉口9

Source=9，u=11，path=1→2→5→9→10→11，weight streets A1=A2=∞ and D1=D2=∞ and H1=H2=∞

Step 4 車輛到達交叉口10

Source=10，u=11，path=1→2→5→9→10→11，weight streets A1=A2=∞ and D1=D2=∞ and H1=H2=∞ and N1=N2=∞

下一步就是最后一步，因為車輛行駛到交叉口11便達到了目的地.

3.3 系統(tǒng)要求和限制

本系統(tǒng)的要求和限制如下.車輛通信設備必須安置在適當位置，如RSUs、OBUs和定向天線.RSUs必須安裝在交叉口，OBU安裝在車輛上，定向天線安裝在路段的入口處.系統(tǒng)要求有適當?shù)臐B透率，也就是裝載OBUs的車輛數(shù).滲透率不夠會導致該方法的工作效率降低.如果路徑選擇算法在車輛上執(zhí)行，為了顯示路徑和目的地，車輛必須安裝必要的處理器和用戶接口.

4 復雜性分析

前文已經闡述了環(huán)路規(guī)避和環(huán)路監(jiān)測兩種方法.設置網絡節(jié)點數(shù)位n，邊數(shù)為e，則認為Dijkstra算法的時間復雜度為O(n2).但利用適當?shù)臄?shù)據(jù)結構，該算法能夠提高至O(e+nlogn)[30].

4.1 一步車輛路徑選擇

一步算法的尋路過程只在第一個交叉口執(zhí)行一次，計算得出的路徑貫穿整個出行.這種模式下，算法的復雜性只表現(xiàn)為時間復雜度.由于尋路過程只進行一次，因此不會有環(huán)路出現(xiàn)，環(huán)路監(jiān)測的時間復雜度為O(1).考慮上述提到的Dijkstra算法的時間復雜度，一步算法的整體復雜度為T(n)=O(1)+O(n2)=O(n2).

4.2 逐步車輛路徑選擇

本節(jié)將估算帶有環(huán)路規(guī)避和環(huán)路監(jiān)測機制的逐步車輛路徑選擇算法的時間復雜度.

4.2.1 方法1：環(huán)路規(guī)避

在環(huán)路規(guī)避小節(jié)中闡述過，車輛經過路段的權重值調整為無窮大，不再將之前經過的交叉口考慮在新的路徑中.環(huán)路規(guī)避的偽代碼如圖4所示.在最壞的情況下每個交叉口的時間復雜度為O(n).所以針對環(huán)路規(guī)避，考慮上述提到的Dijkstra算法的時間復雜度，總的時間復雜度為T(n)=O(n)+O(n2)+O(n)=O(n2).

4.2.2 方法2：環(huán)路監(jiān)測

環(huán)路監(jiān)測的偽代碼如圖5所示.假設在最新的路徑中存在一條環(huán)路，導致環(huán)路出現(xiàn)的所有路段的權重值都調整為無窮大.最壞情況下環(huán)路監(jiān)測方法的時間復雜度為O(e2)，圖5中第8行環(huán)路的時間復雜度為O(e).因此總的來說，環(huán)路監(jiān)測方法中每個交叉口的時間復雜度為O(e3).

如圖7所示，雙向路段的數(shù)量大約比交叉口數(shù)量多三倍.為了計算時間復雜度，將O(3n3)簡化為O(n3)，環(huán)路監(jiān)測方法的時間復雜度為O(n3).

分析執(zhí)行時間：

（1）第9行的時間復雜度（即Dijkstra算法）為O(n2).

（2）第10行的時間復雜度（環(huán)路監(jiān)測）為O(e2).

（3）第10行的時間復雜度（無窮大邊權）為O(e).

（4）第10行的時間復雜度為O(e)*(O(n2)+O(e2)+O(e)).

（5）第15行的時間復雜度為O(n).

假設n=e，總運行時間為T(n)=O(n)*(O(n2)+O(n2)+O(n))+O(n)=O(n3).

最短路徑搜索算法如Dijkstra的時間復雜度依賴于執(zhí)行過程.根據(jù)分析，在實際中，對于大城市，分層方式對控制過程更加有利.城市被分隔成有限的地理區(qū)域（塊）和內在區(qū)域，出行便能夠利用分塊地圖進行內部控制，然后用節(jié)點在塊內地圖上進行尋路.這是未來的一個研究方向.

5 仿真和結果評價

本文利用NCTUns 6.0網絡模擬器仿真所提出的算法.如圖7所示，仿真場景包括25條雙向路段和17個交叉口.如前所述，實際城市由若干個與圖7相似的相鄰場景組成，每個場景有一個數(shù)據(jù)中心.

圖7 仿真環(huán)境Fig.7 The simulation environment

5.1 交通信息收集評價

本節(jié)評價交通信息收集階段.定向天線的信息傳輸模式如圖8所示.信息僅傳給在路段27上的車輛，所以只有車輛91、105和106能夠接收.

首先將RSUs安置在交叉口，然后150輛車進入交通系統(tǒng).仿真參數(shù)如下：

·仿真時間：380 s；

·車輛數(shù)：150；

·建筑物平均高度：10 m；

·路段數(shù)：25（路段名稱為從11至35）.

交通信息收集方法旨在給車輛提供最新的交通信息，因此可用收集信息的精確度進行評價.將信息收集時間設為20 s、40 s、60 s、…、380 s，依次求得本文方法計算的數(shù)據(jù)、真實的交通狀況，以及本文方法的誤差.式(1)為誤差計算公式.

式中 t表示時間，s；n表示路段號；PSi表示用本文算法求得的t時刻i路段上的車輛數(shù)；DRi表示t時刻i路段上實際的車輛數(shù).利用坐標軸可以完成車輛位置檢測.比如，一輛車的坐標為1200

如圖9所示，本文所提出方法的仿真誤差率均低于15%，在可接受范圍內.比如第140 s的誤差概率為14%.造成誤差的一部分原因是2輛或更多車輛同時傳輸信息時發(fā)生沖突.此外，TCP連接建立過程的延誤也會造成一些誤差.需要強調的是，利用適當手段可以調整誤差數(shù)量，比如在協(xié)議棧底層（比如MAC層甚至是應用層）調用避碰技術.

圖9 交通信息收集系統(tǒng)的誤差率Fig.9 The error rate of the traffic data collection system

5.2 車輛路徑選擇評價

在車輛路徑選擇階段計算最優(yōu)路徑，為了得到每條邊的權重，定義式（2）.

式中 SLi是路段i的長度；NVi是路段i上的車輛數(shù)，當路段交通流不飽和時，路段暢通；NAVi是路段i上超出路段通行能力的車輛數(shù)；w1、w2、w3為系數(shù).路段通行能力是能夠以允許速度同時在路段上行駛的最大車輛數(shù)，可根據(jù)交通規(guī)范中允許的最小車頭時距來確定.在本文例子中，w1、w2、w3的值分別設置為0.45、0.4、0.15，由于路段長度和車輛數(shù)是路徑選擇過程中的兩個重要參數(shù)，因此其分配系數(shù)較大，而每條路段上超出通行能力的車輛數(shù)，系數(shù)相對較小.所以，為了均衡這些參數(shù)，路段長度、車輛數(shù)和超出通行能力的車輛數(shù)的權重分別取45%、40%和15%.以上這些參數(shù)乘以變量之和為路段總權重.

值得注意的是上述參數(shù)設置對于本文提出的方法的普適性沒有任何影響，權重函數(shù)可以適當變化.

當路段權重計算得出后，就確定了用于執(zhí)行兩種路徑選擇算法的仿真環(huán)境網絡拓撲圖，如圖10所示.

圖10 仿真地圖Fig.10 The simulation graph

為評價所提出的方法，從150輛車中隨機抽取24輛，這24輛車的起點和終點都是隨機的，并且在兩種模式下仿真，將行駛時間作為性能評價指標.剩余參數(shù)的仿真描述如圖9所示.仿真結果如圖11所示.從圖中可以看出，幾乎所有執(zhí)行逐步路徑選擇算法車輛的行駛時間都減少了.

相比較于一步算法，逐步算法的行駛時間更少，如圖12所示.通過觀察圖11，產生一個問題，為什么車輛2、10、17、20、21、23利用兩種算法得到的行駛時間基本一樣？這是因為在起終點之間的各條路段的密度和長度都大致相同，使兩種方法計算的行駛時間一樣.圖11表明，相較于一步算法，逐步算法共節(jié)約了178 s，相當于平均每輛車節(jié)約了7.41 s.

圖11 分別利用一步算法和逐步算法的車輛平均行駛時間比較Fig.11 The average travel time using one-step vs.step-by-step

圖12 逐步算法比一步算法減少的行駛時間Fig.12 The travel time reduction using step-by-step path suggestion vs.one-step path suggestion

另一個問題是，為什么車輛4、5、14、15的行駛減少時間為負？也就是說，逐步算法比一步算法的行駛時間沒有減少反而增加了？這是因為沒有將計算每條路段權重的參數(shù)，以及車輛的右轉、左轉、掉頭和直行考慮在內.根據(jù)Blue等[31]的研究，這些被稱為出行質量參數(shù).為了提高精確性，權重應該考慮其他影響因素，如出行質量，這也是未來進一步的研究內容.

在不同車流密度下分別對一步和逐步算法進行仿真評價，仿真包括10輛車，隨機起點和終點.仿真結果表明，通常逐步算法比一步算法在行駛時間上的減少量隨著車輛密度的增加而增加.仿真結果如圖13所示.在尋路過程中，路段長度參數(shù)更加顯著，即在權重函數(shù)中（式（1）），為了緩解密度對密集場景的支配作用，它的參數(shù)更大.在圖11，圖12中，參數(shù)為w1=45%、w2=40%、w3=15%，但在圖13中，參數(shù)為w1=50%、w2=35%、w3=15%.

圖13 不同車輛密度情況下逐步算法比一步算法減少的平均行駛時間Fig.13 The average travel time reduction using step-bystep vehicle path suggestion vs.one-step vehicle path suggestion for various traffic densities

圖13表明當路段上有50輛或100輛車時，逐步算法和一步算法的行駛時間差別不大.但是，當路段上的車輛數(shù)增加到150輛或200輛時，逐步算法比一步算法會為大部分車輛節(jié)省很可觀的行駛時間.但當車輛數(shù)為250時，行駛時間的減少量又下降了.這是因為路段上的交通量已經達到飽和狀態(tài)，通過兩種算法計算的最優(yōu)路徑沒有很大差別.

6 研究結論

本文提出的路徑選擇機制包括兩個階段，即實時交通信息收集和最優(yōu)路徑選擇.在第一階段，RSUs在非常短的時間內為駕駛員提供實時交通狀態(tài).在第二階段，利用收集到的交通信息，計算車輛可行的最優(yōu)路徑.在路徑選擇算法中提出了兩種方法，即一步路徑和選擇逐步路徑選擇.

利用NCTUns網絡模擬器仿真交通信息收集和最優(yōu)路徑選擇.在仿真過程之后，通過誤差公式進行仿真評價。結果表明，本文方法能夠獲得實時的道路交通密度，誤差率低于15%.

為了比較和評價路徑選擇算法，仿真一步算法和逐步算法.與靜態(tài)最短路徑算法相比較，一步和逐步算法都能夠顯著減少行駛時間.總體來說，逐步算法要優(yōu)于一步算法，在密度非常低或非常高的情況下，逐步算法的優(yōu)越性并不顯著，而在一般密度下，其優(yōu)越性非常顯著.

對于大城市，算法的時間復雜性會顯著增加，在未來工作中，進一步將研究利用分層方式執(zhí)行算法.此外，為了避免同步傳輸中的信息丟失，避碰技術也要進一步研究.

[1]Schrank D,Lomax T,Eisele B.TTI’s 2011 Urban Mobility report powered by Inrix traffic data[J].Texas Transportation Institute Research Report,The Texas A&M University System,2011.

[2]Nadi S,Delavar M R.Location-based service for invehicle route guidance with real time traffic information[C]//The 12th World Conference on Transport Research(WSTR to WCTR)Proceedings,2010:1-10.

[3]Mimbela L E Y,Klein L Y.A summary of vehicle detection and surveillance technologies used in intelligent transportation systems[R].Federal Highway Administrations (FHWA) Intelligent Transportation Systems Joint Program Office,Research Report,2000 to 2007.

[4]Dhingral S L,Gull I.Traffic flow theory historical research perspectives[C]//75 Years of the Fundamental Diagram for Traffic Flow Theory: Greenshields Symposium Proceedings,2008:45-62.

[5]Skordyli A,Trigoni N.Delay-bounded routing in vehicular Ad- Hoc networks[C]//In 9th ACM International Symposium on Mobile Ad- Hoc Networking and Computing(MobiHoc’08)Proceedings,2008:341-350.

[6]Kitani T,Shinkawa T,Shibata N,et al.Efficient VANET-based traffic information sharing using buses on regular routes[C]//Vehicular Technology Conference(VTC Spring 2008)Proceedings,2008:3031-3036.

[7]Khosroshahi A H,Keshavarzi P,KoozehKanani Z D,et al.Acquiring real time traffic information using VANET and dynamic route guidance, [C]//2nd International Conference on Computing,Control and Industrial Engineering(CCIE)Proceedings,2011:3-13.

[8]Fan Y Y,Kalaba R E,Moore J E.Shortest paths in stochastic networks with correlated link costs[J].Computers&Mathematics with Applications,2005,49(9-10):1549-1564.

[9]Delling D,Wagner D.Time-dependent route planning,robust and online large-scale optimization[J].Lecture Note in Computer Science.2009,5868:207-230.

[10]Boutilier C,Dearden R,Goldszmidt M.Stochastic dynamic programming with factored representations[J].Artificial Intelligence,Elsevier,2000,121(1-2):49-107.

[11]Feldman R M,Valdez-Flores C.Applied probability and stochastic processes[M].Springer,2010.

[12]Bander J L,White C C.A heuristic search approach for a non-stationary stochastic shortest path problem with terminal cost[J].Transportation Science,2002,36(2):218–230.

[13]Hashemi S M,Mokarami S,Nasrabadi E.Dynamic shortest path problems with time-varying costs[J].Optimization Letters,2010,4:147-156.

[14]Lim S,Balakrishnan H,Gifford D,et al.Stochastic motion planning and applications to traffic[J].Algorithmic Foundation of Robotics VIII,Springer Berlin Heidelberg,2009,57:483-500.

[15]Kim S,Lewis M E,White C C.State space reduction for non-stationary stochastic shortest path problems with real-time traffic information[J].IEEE Transactions on Intelligent Transportation Systems,2005,6(3):273-284.

[16]Psaraftis H N,Tsitsiklis J N.Dynamic shortest paths in acyclic networks with markovian arc costs[J].Operations Research,1993,41(1):91-101.

[17]Ramalingam G,Reps T.An incremental algorithm for a generalization of the shortest-path problem[J].Journal of Algorithms,1996,21(2):267–305.

[18]Buriol LS,Resende M G C,Ribeiro C C,et al.A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing[J].Networks,2005,46(1):36–56.

[19]Frigioni D,Marchetti-Spaccamela A,Nanni U.Semidynamic algorithms formaintaining single source shortest path trees[J].Algorithmics,1998,22:250–274.

[20]Fortz B,Thorup M.Increasing internet capacity using local search[J]. Computational Optimization and Applications.2004,29:13-48.

[21]Goel A,Ramakrishnan K G,Kataria D,et al.Efficient computation of delay-sensitive routes from one source to alldestinations[C]// Twentieth AnnualJoint Conference of the IEEE Computer and Communications Societies(INFOCOM 2001)Proceedings,2001:854-858.

[22]http://www.navman.com acc[OL].2014.

[23]http://www.papago.com.tw acc[OL].2014.

[24]Chen P Y,Guo Y M,Chen W T.Fuel-saving navigation system in vehicular Ad-Hoc networks.[C]//IEEE 72nd Vehicular Technology Conference(VTC 2010-Fall)Proceedings,2010:1-5.

[25]Lin B Y,Chen C H,Lo C C.A traffic information estimation model using periodic location update events from cellular network[J].Communications in Computer and Information Science(CCIS),2011,135:72-77.

[26]Diao X,Mou K M,Li J J,et al.Inter-vehicle communication for the next generation of intelligent transport systems:Trends in geographic Ad Hoc routing techniques[C]//Beylot A-L,Labiod H(Eds.),Vehicular Networks-Models and Algorithms,John Wiley&Sons,2013,47-51.

[27]http://www.kurzweilai.net/driverless-vehicles-to-zip-atfull-speed-through-intersections acc[OL].2014.

[28]Ramanathan R,Redi J,Santivanez C,et al.Ad Hoc networkingwith directionalsntennas:A complete system solution[J].IEEE Journal on Selected Areas in Communications,2005,23(3):254-255.

[29]Wang S P,Ledley R S.Computer architecture and security:Fundamentals of designing secure computer systems[M].John Wiley&Sons.2013.

[30]Medhi D,Ramasamy K.Network routing:algorithms,protocols,and architectures[M].Morgan Kaufmann Publishers,2010.

[31]Blue V J,Adler J L,List G F.Real-time multipleobjective path search for in-vehicle route guidance systems[J].Transportation Research Record,1997,1588:159-167.