應用於都市街道環境的位置資訊服務演算法與效能評估

Performance Evaluation of a Novel Distributed Algorithm for Car-to-Car

Communication Location Service over Street Environments

張耀仁            時定樑

中原大學 電子工程學系暨研究所

320桃園縣中壢市中北路200號

E-mail: yjchang@cycu.edu.tw

摘要

車間通訊為智慧型運輸系統中不可或缺的一環，而應用都市街道中更是值得研究的議題之一。本文提出一種分散式具延展性及可靠性的位置資訊服務，稱為ILS，利用路口特性和Chord演算法，使車與車之間可正確的傳遞封包而不需藉由基地台轉送或是以氾濫方式傳遞訊息。透過模擬結果顯示，ILS相當適合應用在高移動性的都市街道環境中使用，並且驗證了使用路口作為提供位置資訊節點的確優於未利用路口的演算法。

關鍵詞：車輛位置資訊服務、車間通訊

Abstract

In this paper we purpose a distributed, scalable and fault tolerant location service algorithm, called Intersection Location Service (ILS). It uses the characteristics of intersections on street environments and combines the Chord algorithm so that cars can communicate with each other without infrastructures and flooding-based forwarding. We use simulation results to show that ILS is suitable for high mobility environments over street maps.

Keywords: ILS, C2CC, IVC, Chord, Location Service

1.           前言

車間通訊（inter-vehicle communication，IVC）為智慧型運輸系統（intelligent transportation system，ITS）中不可或缺的一環，也是近年來被廣為討論的議題。車間通訊是利用車輛與車輛之間相互傳遞訊息，並將資料蒐集彙整後呈現給駕駛人，例如：交通路況監視、緊急情況通報、動態路由選擇等，藉此提高整體交通的安全與效率。傳統上的交通資訊系統是利用基礎建設模式（infrastructure-based），由設置在路旁的監視器將其記錄路段的交通資料回傳至交通資訊中心（traffic information center，TIC）儲存並分析，駕駛人再利用無線接收機（車用電話、行動電話或是收音機）來接收所需的交通資訊。與基礎建設模式的系統做比較，利用車間通訊模式的系統有幾項優點：

一、不需要龐大的基礎建設費用

傳統基礎建設模式的系統建置成本包括路口監視器、交通資訊中心等。而車間通訊只需要每台車輛配有無線電波收發機、電子地圖和全球定位系統（global positioning system, GPS）即可，其中後面兩項都已整合在配有導航系統的車子中。

二、提供更為精確的交通資料

傳統基礎建設模式的系統因受限其頻寬及覆蓋較大範圍區域，所以只能傳送重大或是概略的交通資訊。而車間通訊則不受此限制，可以傳送精確的交通訊息。

三、不需要服務費用

由於沒有基礎建設費用及服務提供者，因此也不需要任何服務費用。

四、較低的延遲時間

傳統基礎建設模式的系統需經由交通資訊中心分析後在廣播至車輛，其間需耗時約20分鐘[16]，而車間通訊直接藉由車輛與車輛間遞送（forwarding）訊息，大大地減低訊息延遲時間。

車間通訊網路與無線隨意網路（mobile ad hoc networks, MANET）有著類似的概念：網路上的每一點利用無線電波來與相鄰的節點做通訊，並且藉由遞送彼此的封包來將封包轉遞到目的端。在無線隨意網路中，由於節點可任意移動位置造成網路拓撲隨時間快速變動，使得傳統上以拓撲為基礎的路由演算法（topology-based routing）將付出不必要路徑維護成本。隨著全球定位系統的普及化，以位置為基礎的路由演算法逐漸取代以拓撲為基礎的路由演算法應用在高速移動的網路環境下。在以位置為基礎的路由演算法（position-based routing）中當傳送封包時必須先決定其目的端的位置才可以將封包正確的遞送，而位置資訊伺服器（location server）就是負責儲存位置資訊的地方，當來源端傳送封包時，會先詢問位置資訊伺服器得知目的端的位置資訊後，再將位置資訊放入封包的標頭（header）中以便遞送。傳統上的作法是將位置資訊利用氾濫（flooding）方式將位置的資訊傳遞至整個網路上，但是使用氾濫方式會浪費太多的頻寬造成延展性（scalability）不佳。因此，在這篇論文中，提出以Chord[4]演算法為基礎的一種具延展性的分散式位置資訊服務稱為ILS（intersection location service），讓街道上的路口成為位置資訊伺服器，使得在N台車輛K個路口的街道地圖中，每台車只需要維持約O(logK)個路口加上O(N/K)個車輛的位置資訊，並且在詢問目標車輛的位置時也只需要花費約O(logK)個封包就可找到，提高在市區街道中詢問欲通訊車輛位置的成功率。

本文在第二節將介紹關於位置資訊服務的相關研究，第三節介紹ILS的系統模型，第四節以電腦模擬方式評估ILS的效能，第五節對ILS做個簡短的結論。

2.           文獻探討

在CarNet[1]中提到的Grid Location Service（GLS）[2]是一個分散式位置資訊服務，其原理是將地圖切割成許多大小相同的正方形格子（grid），最小的正方形稱為第一層方塊（order-1 square），四個第一層方塊可以組成一個第二層方塊，以此類推，而將整個地圖切割成一個不重疊的四元樹階層架構。當一個節點要將其位置資訊散佈至整個地圖時，會利用地理遞送（geographic forwarding）方式先在鄰近三個第一層方塊中選擇適當的節點存放其位置資訊，之後再存放置鄰近三個第二層方塊中適當的節點，以此類推至位置資訊覆蓋整個地圖區域為止，因此每個節點的位置資訊密度將會隨著與節點距離的增加而呈現指數地減少，也使得CarNet相當的具有延展性。

儘管GLS與傳統氾濫式位置資訊服務相比下相當具有延展性且具有區域性，但卻必須付出當移動節點在位置更新時需同時維持多個位置伺服器的代價，這是一種取捨（trade-off）。此外，在[15]中指出GLS兩個造成效能下降的缺點，第一，由於GLS互不重疊的階層方格特性，因此當移動節點越過N階層的格子邊界（grid boundary）時，其原先N-1階層之位置伺服器將全部失效，必須重新更新N階層以下的所有位置伺服器，因此，若網路中越多節點橫越高階格子邊界，將因為過於頻繁的位置更新而嚴重影響GLS的效能。第二，由於GLS維持的是節點與節點之間連結的關係，因此在高速移動的隨意網路環境下，移動節點與其位置伺服器節點都將因為移動而使連結失效。

在VHR（virtual home region）[3]中提到，將地圖上某一節點A的唯一代碼（unique identifier）經過雜湊函數H（hash function）轉換後映射到地圖上的某一圓心C半徑R的圓盤區域內，此圓盤區域稱為VHR，在此區域內所有的節點將負責存放節點A位置資訊。當另一節點B欲搜尋節點A的位置時，透過同樣的雜湊函數H將節點A的唯一代碼帶入即可算出存放節點A位置資訊的VHR，進而藉由詢問VHR得知節點A目前的位置資訊。

HLS[17]結合VHR以區域為主的位置資訊服務與GLS的階層格子概念，將網路涵蓋的地理地圖切割成不同階層的區域。由於HLS是透過選擇區域，並由區域內之節點擔任位置伺服器，因此當被選擇的區域內無節點時，則會造成更新或是詢問失敗。HLS雖然利用VHR的概念來改良GLS在高速移動網路下所產生的缺點，但由於其與GLS一樣具有階層性區域的概念，當節點在越過高階層區域邊界時將付出昂貴的更新代價，因此在系統可靠度、區域化（位置伺服器個數）與降低更新成本間必須做一個取捨。GHLS[15]提出了另一種平坦式（flat）非階層且以區域為主的位置資訊服務。

2.1          GLS、HLS與GHLS的位置資訊服務比較

在HLS與GHLS中的模擬數據指出，GLS在高速移動的網路環境下及隨著網路規模的增加，由於其維持節點與節點連結與階層格子的特性，使得在節點高速移動的環境下更新成本較高，連帶影響其延展性。而HLS與GHLS以區域為主的位置資訊服務，雖然其更新成本較以節點為主的位置資訊服務來的低，但是卻也有一個需要克服的問題；當透過雜湊函數映射到的區域內沒有任何節點時，則會使得位置伺服器失效而造成位置更新與詢問失敗。在HLS中當位置更新封包遇到空的責任細胞時，則將資訊暫時存放在周圍有節點存在的鄰居細胞內當作暫時的位置伺服器；當位置詢問遇到空的責任細胞時，則詢問責任細胞附近的鄰居細胞或者將封包轉送往上一階層的責任細胞做詢問，這將會些微地影響到詢問的延遲時間與詢問成功率，此外，若映射區域其周邊區域也無任何節點存在時（空區域），則將造成更新或詢問失敗的情形發生。在GHLS則沒有說明遇到空的區域時的處理策略。

在實際街道地圖中，由於車輛的移動速度及都市建築物環境等影響，以及空區域的問題，上述應用在無線隨意網路下的位置資訊服務將無法完全適用，因此希望設計出一個以區域為主的位置資訊服務，且在不影響效能的情形下針對空的區域問題提出解決方法。我們將利用Chord[4]演算法為基礎設計一套針對都市街道特性與適用於在車間通訊的高移動網路環境下，具延展性且可靠的位置資訊服務。

圖1 ILS示意圖

3.           系統模型

在[14]中提到，都市環境中由於街道與街道間有建築物遮蔽影響，將使得封包遞送策略將產生四個缺點，第一、網路分割現象，封包遞送策略原本設計應用於自由空間（free space）上，若應用於都市環境，因無線電波受到建築物遮蔽造成節點間無法通訊，連帶限制以貪婪封包遞送為主策略的可用性。第二、造成封包過多跳躍數（hops），將增加延遲。第三、路由迴圈（routing loops），由於節點的高速移動將可能造成遞送封包路徑形成迴圈。第四、錯誤的遞送方向，封包無法以最短路徑做遞送，將造成過多的跳躍數與路由迴圈的問題。

在都市環境中車輛的相對速度造成都卜勒（Doppler）效應使得封包無法正確被遞送，因此詢問車輛位置資訊的成功率下降。

為了克服上述的問題，我們提出一個創新的想法。我們發現在都市街道中十字路口有一些可利用的特性，當縱向車道是綠燈行進時橫向車道一定是紅燈停車，反之亦然，使得十字路口有匯集車輛的特性。此外紅燈路口的車輛處於靜止狀態，將使得路口車輛將減低因為都卜勒效應影響而無法通訊的機率，增加封包傳遞的成功率。基於上述這些特性，在高移動性的都市街道網路中，交通路口便相當適合當成負責存放位置資訊的區域來儲存移動車輛的位置資訊，如圖1所示。

我們所提出的Intersection Location Service (ILS) 便利用此概念將街道地圖上的路口區域視為提供位置資訊服務的節點。ILS結合Chord[4]演算法，以自組（self-organized）的方式將街道地圖上全部有車輛的路口區域串連形成一路口邏輯代碼環，有車輛之路口區域類似Chord邏輯代碼環中之節點，區域內之車輛將成為位置伺服器，負責儲存更新車輛之位置資訊。Chord原為一種應用在網際網路具延展性的P2P搜尋演算法，其原理是將網路上的節點以及資料利用SHA-1[5]來映射到一個 m位元的代碼，節點將此代碼依大小順序排序形成一個模數2m的邏輯代碼環（identifier circle）或稱為Chord Ring，在邏輯代碼環上每個節點將各自維護自己的指標節點表（finger table）並負責儲存對應到節點的資料。當節點搜尋資料時，先將欲搜尋的資料經過SHA-1算出代碼後，再透過查詢指標節點表找到適當的節點送出詢問封包，當節點收到詢問封包時，同樣搜尋自己的指標節點表並轉送詢問封包，直到找到負責存放資料的節點為止。依據Chord的演算法，在N個節點的環境下，每個節點只需要維護O(logN)個其他節點的資訊（指標節點表），並且保證詢問資料只需花費O(logN)個封包既可找到，因此相當具有延展性。此外，Chord具有容錯性，當節點加入或離開邏輯代碼環時，相關的節點可以透過週期性的更新封包來維護指標節點表，確保資料存取的成功率。

在本研究所提出的ILS中，我們將路口透過雜湊函數映射到一個 m位元的代碼，此代碼依大小順序排序形成一個模數2m的邏輯代碼環。在路口半徑R範圍內的所有車輛皆為該路口的位置資訊伺服器，負責儲存位置資訊並且週期性的維持路口邏輯代碼環的指標節點表資訊，而地圖上的車輛透過雜湊函數將唯一代碼（行照號碼或是車牌）映射到對應的路口上並將位置資訊存放於此。假設一個街道地圖內有8個路口和11台車，透過SHA-1將路口與車輛映射到7位元的代碼，如圖2所示，並將路口的代碼依大小順序排序形成一個模數27的邏輯代碼環，車輛的位置資訊將依照其代碼存放在數字大小最接近路口代碼但不超過的路口區域內，如圖3所示。

圖2 路口與車輛透過SHA-1映射

圖3 路口邏輯代碼環

3.1          位置資訊更新

車輛更新其位置資訊時利用雜湊函數將唯一代碼（行照號碼或是車牌）映射至一個 m位元的代碼，此時將位置更新封包（包括車輛座標、速度和車行方向）傳遞至最近的路口，當路口收到詢問封包時，將比對其指標節點表並將此位置更新封包轉送至適當的路口，如圖4所示，假設車輛N22欲更新其位置資訊，則將其位置資訊更新封包遞送至最近的路口K34，路口K34則透過其指標節點表將封包遞送至路口K100，路口K100則執行同樣的動作，封包則依序經過K7最後到達K23，當K23收到N22的位置資訊更新封包後，透過指標節點表得知自己即為此位置更新封包應該儲存的路口，則將此資訊儲存並以限制範圍氾濫（restricted flooding）方式廣播給此路口區域範圍內的所有車輛，當車輛收到此封包但不在路口區域範圍內則捨棄封包。

圖4 位置資訊更新

3.2          位置資訊詢問

詢問車輛目前的座標時，流程與位置更新類似，若A車欲詢問B車的位置，先將欲詢問的車輛B的唯一代碼透過同樣的雜湊函數映射至一個 m位元的代碼，並將此代碼和發送車輛A本身的座標、速度和車行方向打包成位置詢問封包遞送至最近的路口，當路口收到此位置搜尋封包後，同樣地將比對其指標節點表並將此位置詢問封包轉送至適當的路口，若該路口為存放車輛B之位置資訊的路口，則依其儲存車輛B的座標資料將此封包再轉遞給車輛B，當車輛B收到此詢問封包後，既可從封包中得知發送此詢問封包的車輛A座標，並將自己的位置更新封包回送給車輛A，當A收到B的位置資訊封包後，A、B兩輛車都互相知道對方的位置資訊，便可以開始進行通訊，如圖5所示。

圖5 位置資訊詢問示意圖

3.3          路口區域操作

當車輛進入路口範圍時，將主動發送一個資訊需求封包，當路口範圍的車輛收到此封包時會把此路口的指標節點表及所儲存的位置資訊傳回。當車輛離開路口範圍時，會將該路口的指標節點表及儲存的位置資訊刪除，如圖6所示。但如果車輛為該路口唯一的車輛，則該車輛離開路口時，會將路口儲存的位置資訊帶走，並藉由下一個路口將此位置資訊轉遞到應該儲存的路口，如圖7所示。

圖6 路口資訊交換示意圖

圖7 路口區域無車示意圖

4.           實驗結果

為了評估ILS的效能，在模擬軟體部分我們使用ns-2[18]版本2.29，設定車輛利用IEEE 802.11介面傳遞資料，傳輸速率分別為2Mbps與11Mbps，傳輸範圍為250公尺。在傳遞封包上使用GPSR[8]作為封包遞送策略。我們假設車子在一3x3的街道地圖上移動，街道與街道間距為200公尺，車子移動至路口將隨機決定其移動方向與速度並移動至下一個路口，以此類推。

首先模擬車輛移動速度對ILS所造成的影響，模擬參數如表1所示，在3x3的街道地圖中模擬18台車輛，車輛移動速度從0m/s至30m/s，速度偏移量為5m/s，車輛在路口停留時間為10秒，總模擬時間為30秒，車輛每移動200公尺更新其位置資訊，傳輸速率分別為2Mbps與11Mbps。

表1 實驗一模擬設定參數

模擬結果如圖8所示，位置詢問成功率（query success ratio，QSR）為位置詢問封包透過路口車輛轉送至被詢問車輛，再由被詢問車輛回應位置資訊給詢問車輛之成功率。由圖8中的曲線可以觀察到車輛在移動的環境下，ILS的詢問成功率約在81%至92%間，且隨著車輛的移動速度增加沒有大幅度的下降趨勢。而且無論是2Mbps 或是 11 Mbps 的802.11 傳輸介面效果都近似，顯示效能瓶頸並不在網路介面傳輸速率上，因此本研究中以下的兩個實驗將以2Mbps 的無線介面速度作為模擬參數。

圖8 詢問成功率vs.車輛移動速度

為了研究車輛密度對於ILS所造成的影響，我們將車輛數目由18台依序遞減至9台，模擬參數如表2所示，在3x3的街道地圖中，車輛速度為30m/s，速度偏移量為5m/s，車輛在路口停留時間為10秒，總模擬時間為30秒。

表2 實驗二模擬設定參數

模擬結果如圖9所示，隨著車輛數目的增加，詢問的成功率也跟著增加，這是由於隨著車輛密度的增加，路口區域有無車輛變動的機率也就越小，封包可以藉由路口正確地轉遞，也使得詢問成功的機率越高。

圖9 詢問成功率vs.車輛數

接著我們試著將存放位置資訊的區域從路口移至地圖上其他區域，藉此來比較位置伺服器設置在路口與其他區域的差異，模擬參數如表3所示，在3x3的街道地圖上，我們將存放位置資訊的區域設置在相鄰兩路口之間的道路中央。

表3 實驗三模擬設定參數

模擬結果如圖10所示，將位置伺服器設置在道路中央的詢問成功率介於69%至83%之間，比設置在路口區域低，這是由於相對於路口而言，在道路中央區域的車輛密度將比路口區域小，且由於車輛一直移動的情形下，區域車輛有無的變化情形將比在路口區域大，可能造成路口資訊來不及更新而將封包轉遞至無車的區域，造成詢問失敗的機率增加。由於路口具有車輛密度高與移動速度低等特性，也間接使得有無車輛的變化機率降低，使得查詢成功率大幅提升。而模擬的結果也證實了路口的確適合在都市街道地圖中作為存放位置資訊的區域。

圖10 詢問成功率vs.車輛移動速度

5.           結論

在這篇論文中，我們利用路口的特性提出一個適合應用在街道地圖中的位置資訊服務。ILS執行更新與詢問封包可在轉遞log2I個路口(I為路口數)到達最適合的路口區域中，隨著地圖大小與路口數目的增加，ILS仍可以快速的找到適合的路口。模擬結果顯示，ILS在車輛高速移動下仍可維持不錯的詢問成功率，且隨著路口區域有無車輛的變化，更新與詢問封包仍可正確地被轉遞至適合的路口區域中。而隨著車輛密度的增加，路口區域有無車輛的變化情形減少，也使得ILS的詢問成功率提高。此外也印證了路口比一般道路更適合作為存放位置資訊的區域，因此ILS將相當適合應用在高車輛移動性的都市街道環境中。

參考文獻

[1]   R. Morris, J. Jannotti, F. Kaashoek, J. Li, and D. Decout, “CarNet: A Scalable Ad Hoc Wireless Network System,” in Proc. Of the 9th ACM SIGOPS European workshop: Beyond the PC: New Challenges for the Operating System, Kolding, Denmark, September 2000.

[2]   J. Li, J. Jannotti, D. S. J. De Couto, D. R. Karger, and R. Morris, “A Scalable Location Service for Geographic Ad Hoc Routing,” Proc. 6th Annual ACM/IEEE Int’l. Conf. Mobile Comp. Net., Boston, MA, 2000, pp. 120–30.

[3]   S. Giordano and M. Hamdi, “Mobility Management: The Virtual Home Region,” Technical Report No. SSC/1999/037, EPFL, October 1999.

[4]   I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, “Chord: A scalable peer-to-peer lookup service for Internet applications,” in Proc. ACM SIGCOMM’01, San Diego, CA, Aug. 2001.

[5]   “Secure Hash Standard,” U.S. Dept. Commerce/NIST, National Technical Information Service, Springfield, VA, FIPS 180-1, Apr. 1995.

[6]   M. Mauve, J. Widmer, and H. Hartenstein, “A survey on position-based routing in mobile ad hoc networks,” in IEEE Networks, pp. 30–39, Nov./Dec. 2001.

[7]   P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, “Routing with Guaranteed Delivery in Ad Hoc Wireless Networks,” in Proc. Third Int'l Workshop Discrete Algorithms and Methods for Mobile Computing and Comm., pp. 48-55, Aug. 1999.

[8]   Brad Karp and H. T. Kung, “GPSR: greedy perimeter stateless routing for wireless networks,” in Mobile Computing and Networking, 2000, pp. 243–254.

[9]   Y.-B. Ko and N. H. Vaidya, “Location-aided routing (LAR) in mobile ad hoc networks,” in ACM/Baltzer Wireless Networks (WINET) journal, 6(4):307-321, 2000.

[10]          S. Basagni, I. Chlamtac, V. R. Syrotiuk, and B. A. Woodward, “A distance routing effect algorithm for mobility (DREAM),” in Proc. Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), pages 76–84, 1998.

[11]          L. Blazevic, L. Buttyan, S. Capkun, S. Giordano, J. P. Hubaux, and J. Y. Le Boudec , "Self-Organization in Mobile Ad-Hoc Networks: the Approach of Terminodes," in IEEE Communications Magazine, June 2001.

[12]          L. Blazevic, S. Giordano and J.-Y. Le Boudec, “Self Organized Terminode Routing,” Technical report, DSC/2001/024, Swiss Federal Institute of Technology, Lausanne.

[13]          The grid project homepage. http://pdos.csail.mit.edu/grid/.

[14]          C. Lochert, H. Hartenstein, J. Tian, H. Füßler , D. Hermann, and M. Mauve, “A routing strategy for vehicular ad hoc networks in city environments,” In Proceedings of the IEEE Intelligent Vehicles Symposium, pages 156-161, 2003.

[15]          S. M. Das, H. Pucha and Y. C. Hu, "Performance comparison of scalable location services for geographic ad hoc routing," Proc.of IEEE INFOCOM, pp. 1228–1239, 2005.

[16]          L. Wischhof, A. Ebner, H. Rohling, “Information Dissemination in Self-Organizing Intervehicle Networks,” In IEEE Transactions on Intelligent Transportation Systems, pp. 90-101, Mar. 2005.

[17]          W. Kieß, "Hierarchical Location Service for Mobile Ad-hoc Networks," ACM SIGMOBILE Mobile Computing and Communications Review, vol. 8, pp. 47-58, 2004.

[18]          The ns-2 network simulator. http://www.isi.edu/nsnam/ns/.

Edit this page (if you have permission) |

Google Docs -- Web word processing, presentations and spreadsheets.