最近幾年，隨著無線網路技術的進步與普及進而使得車載行動通訊網路(Vehicular Ad Hoc Network, VANET)的相關議題備受關注，許多車載行動通訊網路的相關研究也如雨後春筍般的出現。車載行動通訊網路與一般無線隨意網路之研究最大的差異性在於載體的移動速度，因為載體為車輛等交通工具擁有較高之移動速度。因此在車載行動通訊網路中，有效率的轉送資料將是一個相當大的挑戰，為此有許多研究著重於路由協定之發展。由於諸多路由協定提出的當下，都是假設在一個散佈且理想的環境，因此針對特殊之地理環境，例如城市這類複雜的環境，必定需要做額外的修改，以提升路由協定之效能。
在傳統的行動隨意網路(Mobile Ad Hoc Network, MANET)中，要傳遞資訊至某目的節點，即有相對應之路由協定(Routing Protocols)，如DSDV、AODV、DSR，來輔助移動節點找尋傳遞資訊之路徑。但隨著移動節點之移動速度的提升，如車載行動通訊網路中之車輛，傳統的路由協定則不敷使用。因此，需要後來因應節點移動性(Mobility)之特點，所提出之基於地理資訊的路由協定(Geographic Position-based Routing Protocols)。基於地理資訊的路由協定提出之當下，只是針對節點移動性之特點，利用全球定位系統(Global Positioning System, GPS)獲得地理資訊以輔助協定，僅利用局部網路拓撲資訊，即可做出路由之決策。但對於特殊場景之使用，如城市場景(Urban Scenario)，仍有些不足之處。
因此本篇論文主要的研究目的，在於針對城市之場景設計出相對應之路由協定，使之能有較高的效能與適應性。為此目的，我們提出了Greedy on Straight Roads and Predictive at Intersections (GSPI)路由協定，在筆直的道路使用貪婪模式(Greedy Mode)演算法，在十字路口之區域使用預測模式(Predictive Mode)。在貪婪模式中，我們結合了距離與多重傳輸速度(Multi-rate)等參數所構成之權重數值(Weight, Wi)，作為選擇下一台轉傳車輛之依據。在預測模式中，我們預測車輛的動向作為選擇下一台轉傳車輛之考量。根據我們使用網路模擬器(Network Simulator, NS-2)之模擬結果，此方法確實有其可行之處。

In recent years, thanks to the development and popularization of wireless network technologies, the issue of Vehicular Ad-Hoc Network (VANET) has received great attention, and more and more VANET-related researches have been brought up. Generally speaking, the biggest difference between VANET and traditional Ad Hoc Network is the velocity of carriers because in VANET, the velocity of vehicles the carriers is much higher than those in traditional Ad Hoc. Therefore, it would be a great challenge to forward data efficiently in VANETs and many researches proposed have focused on the development of routing protocols. The current proposed routing protocols are all assumed to simulate in a distributed and ideal environment. As for the complex geographic environments, like urban scenarios, extra amendments must be needed to improve the efficiency of the routing protocols. 
In traditional Mobile Ad Hoc Network (MANET), there are corresponding routing protocols, such as DSDV, AODV, DSR, to assist the mobile node to find the path from source to destination, when the mobile node want to send data to destination. Accompany with the velocity of mobile nodes become higher, such like the vehicles in VANET, the traditional Ad Hoc routing protocols are inadequate. Therefore, the geographic position-based routing protocols are proposed to support the feature of the mobility of nodes. When the geographic position-based routing protocols are proposed, it focuses on solving the problem only that is the feature of the mobility of nodes. It use the Global Positioning System (GPS) to obtain the geographic information, and the information support the routing protocol to make routing decision when the routing protocol only has the local topology information. But it is also inadequately in some scenario, such as urban scenario.
Thus, the main purpose of this paper is to design a suitable routing protocol for urban scenarios with better performance and adaptability. For this reason, Greedy on Straight Roads and Predictive at the Intersections (GSPI) routing protocol is proposed: to use greedy mode on straight roads, and to use predictive mode at the intersections. In greedy mode, we choose the next hop according to the weight value (Weight, Wi) that combines the distances and multi-rate. In predictive mode, we predict the direction of the vehicles to determine the next hop. The simulation results of Network Simulator (NS-2) reveal that our proposed algorithm indeed proves its feasibility.

目    錄
第一章  緒論	- 1 -
1.1	前言	- 1 -
1.2	動機與目的	- 2 -
1.3	論文章節架構	- 4 -
第二章  背景知識與相關研究	- 6 -
2.1	無線網路之架構	- 6 -
2.1.1	基礎架構模式與無基礎架構模式	- 6 -
2.1.2	行動隨意網路	- 8 -
2.1.3	車載行動通訊網路	- 10 -
2.1.4	行動隨意網路與車載行動通訊網路之比較	- 13 -
2.2	隨意網路路由協定	- 15 -
2.2.1	基於拓撲的路由協定	- 17 -
2.2.2	基於地理資訊的路由協定	- 24 -
2.3	相關研究	- 28 -
2.3.1	基於拓撲的路由	- 29 -
2.3.2	基於地理位置的路由	- 29 -
第三章  應用於城市場景之路由機制GSPI	- 34 -
3.1	系統模型	- 34 -
3.2	Beacon訊息的功能	- 37 -
3.3	貪婪模式	- 39 -
3.4	預測模式	- 43 -
3.5	備援模式	- 46 -
第四章  模擬結果	- 49 -
4.1	模擬工具	- 49 -
4.2	模擬結果與分析	- 52 -
4.2.1	實驗一	- 53 -
4.2.2	實驗二	- 59 -
第五章  結論與未來展望	- 64 -
參考文獻	- 66 -

 
圖目錄
圖2.1 基礎架構模式(Infrastructure Mode)	- 7 -
圖2.2 無基礎架構模式(Ad Hoc Mode)	- 7 -
圖2.3 行動隨意網路(MANET)示意圖	- 10 -
圖2.4 車間通訊架構(CALM)之網路分層(來源[6])	- 13 -
圖2.5 隨意網路路由協定之分類(來源[7][8])	- 15 -
圖2.6 簡單的行動隨意網路(MANET)拓撲	- 20 -
圖2.7 RREQ與Reverse Path Setup	- 23 -
圖2.8 RREP與Forward Path Setup	- 23 -
圖2.9 貪婪模式(Greedy Forwarding Mode)之範例(來源[10])	- 26 -
圖2.10 邊緣模式(Perimeter Forwarding Mode)之範例(來源[25])	- 27 -
圖2.11 路由迴路(Routing Loop)之例子	- 27 -
圖2.12 加布里埃爾圖(GG) (來源[10])	- 28 -
圖2.13 相對鄰域圖(RNG)(來源[10])	- 28 -
圖2.14 節點移動速度導致GPSR失誤之示意圖(來源[21])	- 30 -
圖3.1 城市場景(Urban Scenario)	- 36 -
圖3.2 Beacon訊息格式	- 39 -
圖3.3 十字路口(Intersection)之範例	- 39 -
圖3.4 參數解說之示意圖	- 42 -
圖3.5 預測模式(Predictive Mode)之範例	- 45 -
圖3.6 車輛B之夾角示意圖	- 45 -
圖3.7 備援模式(Recovery Mode)之範例	- 48 -
圖3.8 備援模式(Recovery Mode)策略之示意圖	- 48 -
圖4.1 MOVE主畫面(來源[33])	- 50 -
圖4.2 MOVE-Mobility model generator介面(來源[33])	- 50 -
圖4.3 MOVE系統架構圖(來源[33])	- 52 -
圖4.4 模擬場景	- 54 -
圖4.5 Packet Delivery Ratio與車輛速度之關係圖	- 57 -
圖4.6 Routing Overhead與車輛速度之關係圖	- 58 -
圖4.7 Throughput與車輛速度之關係圖	- 58 -
圖4.8 權重數值(Weight Score)與Packet Delivery Ratio之關係圖	- 62 -
圖4.9 Packet Delivery Ratio與車子數量之關係圖	- 63 -
圖4.10 End-to-end Delay與車子數量之關係圖	- 63 -

 
表目錄
表2.1 MANET與VANET特性比較表	- 14 -
表2.2 MH4的初始路由表	- 20 -
表3.1 IEEE 802.11b Data Rate Specifications and the Transmission Range(來源[14])	- 42 -
表4.1 模擬參數設定	- 54 -
表4.2 模擬參數設定	- 60 -

參考文獻

[1]	D. Jiang, and L. Delgrossi, “IEEE 802.11p Towards an International Standard for Wireless Access in Vehicular Environments” Vehicular Technology Conference, 2008 (VTC Spring 2008), 2008, pp. 2036-2040.
[2]	“Car2Car Communication Consortium,” http://www.car-to-car.org/
[3]	“InternetITS Consortium,” http://www.internetits.org/
[4]	“The Network on Wheels Project,” http://www.network-on-wheels.de/
[5]	“ITS Taiwan,” http://www.its-taiwan.org.tw/its-taiwan-2.htm
[6]	“DSRC—Dedicated Short Range Communications Project, ” http://www.leearmstrong.com/DSRC/DSRCHomeset.htm
[7]	Elizabeth M. Royer, Chia-Keong Toh, “A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks,” IEEE Personal Communications, vol. 6, Issue 2, April 1999, pp. 46 – 55.
[8]	M. Mauve, J. Widmer, H. Hartenstein, “A survey on position-based routing in mobile ad-hoc networks,” IEEE Network Magazine, vol. 15, Issue 6, November 2001, pp. 30-39.
[9]	Ivan Stojmenovic, “Position-based routing in ad hoc networks,” IEEE Communications Magazine, vol. 40, Issue 7, Jul 2002, pp. 128-134.
[10]	Karp, B. and Kung, H.T., “Greedy Perimeter Stateless Routing for Wireless Networks,” in Proc. of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), Boston, MA, August 2000, pp. 243-254.
[11]	X. Jiang and T. Camp., “A Review of Geocasting Protocols for a Mobile Ad Hoc Network,” in Proc. of the Grace Hopper Celebration (GHC), Vancouver, Canada, Oct. 2002.
[12]	Young-Bae Ko and Nitin H.Vaidya., “Location-Aided Routing (LAR) in mobile ad hoc networks,” ACM/Baltzer Wireless Networks (WINET) journal, 6(4):307-321, 2000.
[13]	S. Basagni, I. Chlamtac, V.R. Syrotiuk and B.A. Woodward, “A Distance Routing Effect Algorithm for Mobility (DREAM),” in Proc. of the 4th annual ACM/IEEE international conference on Mobile computing and networking, Dallas, Texas, United States, Oct. 25-30, 1998, pp. 76-84.
[14]	Dong-Hee Kown, Woo-Jae Kim, and Young-Joo Suh, “Performance Comparisons of Two On-demand Ad Hoc Routing Protocols in Dynamic Rate Shifting WLANs,” in Proc. of IEEE International Conference on Communications. (ICC 2003), vol. 1, May 2003, pp.512-516.
[15]	Yongho Seok, Jaewoo Park, and Yanghee Choi, “Multi-rate Aware Routing Protocol for Mobile Ad hoc Networks,” in proc. of IEEE Vehicular Technology Conf.( VTC 2003), vol. 3, Apr. 2003, pp. 22-25.
[16]	B. Awerbuch, D. Holmer, and H. Rubens, “High Throughput Route Selection in Multi-Rate Ad Hoc Wireless Networks,” in Proc. WONS’ 2004, January 2004, pp. 251-268.
[17]	S. Zhao, Z. Wu, A. Acharya, and D. Raychaudhuri, “PARMA: a PHY/ MAC aware routing metric for ad-hoc wireless networks with multi-rate radios,” in proc. of Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks .(WoWMoM 2005), Jun. 2005, pp. 286–292.
[18]	Lochert C, Hartenstein H, Tian J, Fussler H, Hermann D, and Mauve M, “A Routing Strategy for Vehicular Ad Hoc Networks in City Environments,” IEEE Intelligent Vehicles Symposium. (IVS 2003), June 2003, pp. 156-161.
[19]	Christian, L., Martin, M., Holger Fusler., Hannes, H., “Geographic Routing in City Scenarios,” in proc. of ACM SIGMOBILE Mobile Computing and Communications Review, vol. 9, Issue 1, January 2005, pp. 69-72.
[20]	Kevin C. Lee, Jerome Harri, Uichin Lee, and Mario Gerla, “Enhanced Perimeter Routing for Geographic Forwarding Protocols in Urban Vehicular Scenarios,” in Proc. of AutoNet'07, Washington, DC., Nov. 2007, pp. 1-10.
[21]	Brahmi, N., Boussedjra, M., Mouzna, J.,“Mobility Support and Improving GPSR Routing Approach in Vehicular Ad Hoc Networks,” New Technologies, Mobility and Security.(NTMS 2008), Nov. 2008, pp. 1 – 6.
[22]	S.A. Rao, M. Pai, M. Boussedjra and J. Mouzna, “GPSR-L: greedy perimeter stateless routing with lifetime for VANETS,” 8th International Conference on ITS Telecommunications. (ITST 2008), Oct. 2008, pp. 299–304.
[23]	J. Gong, C. Xu, and J. Holle, “Predictive Directional Greedy Routing in Vehicular Ad hoc Networks,” in proc. of the 27th International Conference on Distributed Computing System Workshops (ICDCSW’07), June 2007, pp. 2-2.
[24]	Kumar, R., Rao, S.V., “Directional Greedy Routing Protocol (DGRP) in Mobile Ad-Hoc Networks,” International Conference on Information Technology ( ICIT '08), Dec. 2008, pp.183 – 188.
[25]	Sukdea Yu, Hoon Choi, Gihwan Cho, “A New Recovery Method for Greedy Routing Protocols in High Mobile Vehicular Communications,” IEEE International Conference on Vehicular Electronics and Satety, 2008. (ICVES 2008), September 2008, pp. 45-50.
[26]	Karp, B., “Challenges in geographic routing: Sparse networks,Obstacles, and Traffic provisioning,” in Proc. of the DIMACS Workshop on Pervasive Networking, Piscataway, NJ, May 2001
[27]	J. Tian, I. Stepanov, and K. Rothermel, “Spatial aware geographic forwarding for mobile ad hoc networks,” Technical Report,University of Stuttgart, 2002.
[28]	Lichuan Liu, Zhigang Wang, Wern-Kueir Jehng, “A Geographic Source Routing Protocol for Traffic Sensing in Urban Environment,” IEEE International Conference on Automation Science and Engineering, 2008. (CASE 2008), Aug. 2008, pp. 347-352.
[29]	F. Li and Y. Wang, “Routing in Vehicular Ad Hoc Networks: A Survey,” IEEE Vehicular Technology Magazine, vol. 2, Issue 2, June 2007, pp. 12-22.
[30]	Karnadi, F.K., Zhi Hai Mo, Kun-chan Lan, “Rapid Generation of Realistic Mobility Models for VANET,” IEEE Wireless Communications and Networking Conference, 2007. (WCNC 2007), 11-15 March 2007, pp. 2506 – 2511.
[31]	SUMO Simulation of Urban MObility. http://sumo.sourceforge.net/.
[32]	The Network Simulator ns 2. http://www.isi.edu/nsnam/ns/index.html.
[33]	Setup and use of MOVE simulator. http://lens1.csie.ncku.edu.tw/MOVE/
[34]	An Introduction to Mobile Ad Hoc Networks. http://dclab.cs.nthu.edu.tw/~kwc/