在這個資訊爆炸的時代，無線網路技術的研發進展極為迅速，相關應用日新月異，行動隨意網路(Mobile Ad- Hoc Network,簡稱MANET)便是其中之一。該網路架構是一種完全經由無線連結的行動節點所組成的網路架構，並且不會透過基礎建設(non-infrastructure mobile networks)來協助，每個行動節點都可以成為中繼點，幫助彼此間的資料透過不同的行動節點以多點跳躍(multi-hop)的方式傳遞。車載網路(Vehicular ad hoc network，簡稱VANET)是MANET所發展出來的一種應用，特色是車輛會高速的移動，如在高速公路上高速行駛時，網路拓樸的改變是非常快速的，因而需要一個穩定的路由協定(Routing Protocol)來為這些車輛找出彼此溝通的路徑，改善車輛移動所造成的路徑損壞，造成資料時常無法順利傳遞的缺點。
根據以往傳統Topology-Based路由協定的做法，當節點要傳送資料封包給目標節點時，必須仰賴事先建立或是當下立即建立起來的路徑來幫助傳送資料封包，必須耗費一定數量的控制封包，包括路由探索封包(Route Request ，簡稱RREQ)以及路由回覆封包(Route Reply，簡稱RREP)，而路徑建立起來之後，又必須定期維護這些路徑確保資料傳輸的可靠度，如果使用在如VANET此類移動性較高的環境中，事先建立好的路徑發生斷裂的情況會越來越嚴重，這些路由協定為了確保傳輸的品質，必須依靠大量的控制封包來處理，對頻寬造成的負擔也會相對增加。
因此我們的研究目標為設計一個可倚靠位置資訊(Position-based)建立之可自身調節路徑並且降低控制封包數量的VANET路由協定，以提升VANET之路由資訊的穩定度與降低成本，每台車輛可以不必耗費資源去儲存大量的路由表，
並且透過我們設計出來的控制封包蒐集鄰近路口資訊，使得封包在路口轉傳的時候，可以根據不同的環境變化而有自我判斷路徑的功能，降低以往GPSR因為找不到適合的節點轉傳，而進入環繞模式這種效率較低的轉傳模式之機率。
在我們的研究模擬的部分，可以看出我們的方法適合使用在移動頻繁的V2V的環境下。不僅可以降低控制封包的數量，也能夠更正確的選定封包轉傳對象，增進傳輸效能。

VANET (Vehicular Ad-hoc NETwork) is a kind of research projecting from MANET (Mobile Ad-hoc NETwork), the characteristic of VANET is which has fast-moving vehicles, and the topology will be changed frequently, so we need a stable routing protocol to help vehicular found the path, then using this path to transmit data packet, improve path broken caused by vehicle movement to make data transmission problem.
Based on past the traditional topology-based routing protocol approach, when node want to send data packet to destination node, must rely on the path which established immediately or early, it would spend a certain amount of control packets, such as route request packet (RREQ), route reply packet (RREP), and for ensure the reliability of data transmission, also need some control packets help. In the higher mobility VANET environment, the path which established early would break frequently, those routing protocol would increase the burden on bandwidth.
Therefore, our research goal to design a position-based of self-regulation path which can be created and reduce the number of control packets of VANET routing protocols, the VANET routing information in order to enhance the stability and reduce costs, each vehicle can not have to spend resources to store large amounts of routing tables, and designed by us to collect close to the junction of the control information packets, making packet transmit at the intersection, according to different environmental changes and determine the path of self-function, reducing the probability of past GPSR nodes can not found next hop turn for transmission, and into the periodic mode switch to this less efficient mode of transmission.
In the simulation part of our research, we can see that our method is suitable for frequent use in mobile V2V environments. Not only can reduce the number of control packets, and can more accurately target the selected packet to transfer, enhance transmission efficiency.

第一章、緒論 1
1.1論文簡介 1
1.2研究動機 2
第二章、背景知識與相關研究 10
2.1 隨意移動網路(MANET)的架構 10
2.1.1 Topology-based 11
2.1.1.1 Proactive routing protocol 12
2.1.1.2 Reactive routing protocol 12
2.1.1.3 Hybrid routing protocol 12
2.1.2 Position-based 13
2.1.2.1 None-DTN (Non-Delay tolerant network) 14
2.1.2.2 DTN (delay tolerant network) 14
2.1.2.3 Hybrid 14
2.2 車載網路(VANET)的架構 15
2.2.1 Vehicle to RSU(V2R) 18
2.2.2 Vehicle to Vehicle(V2V) 18
2.2.3 結合V2R 和V2V 的網路架構 19
2.3 既有的路由協定介紹 19
2.3.1 AODV 19
2.3.1.1 維護拓樸資訊 20
2.3.1.2 Route Request 20
2.3.1.3 Route Reply 23
2.3.1.4 Route Maintenance 24
2.3.2 GPSR 26
2.3.2.1 每個節點只維護其發射範圍內的節點拓撲信息 27
2.3.2.2 貪婪演算法(Greedy Forwarding) 27
2.3.2.3 平面圖環繞法(Planer Perimeter) 28
2.3.3 JARR 32
2.3.3.1 Adaptive Beaconing & Path Density Estimation 32
2.3.3.2 非路口轉傳機制 34
2.3.3.3 路口轉傳機制 35
2.3.4 Wang et al 36
2.3.4.1 Adaptive Beaconing 36
2.3.4.2 路口判斷方法 36
2.3.4.3 改進過後的貪婪轉傳模式 38
2.3.4.4 路口轉傳機制 39
第三章、新方法 41
3.1 Adaptive Beaconing 43
3.2 判斷是否處於路口 44
3.3 位於路口時封包轉傳演算法 47
3.3.1 計算道路密度 47
3.3.2 預測移動座標 47
3.3.3 計算next hop的權重值 47
3.3.4 當車輛在路口的封包轉傳對象選擇演算法 48
3.3.5 整體封包轉傳的演算法 50
第四章、模擬與比較 53
4.1 模擬比較採用協定之緣由 54
4.1.1 Position-Based與Topology-Based的路由協定效能之差異性 54
4.1.2 Junction-Based模擬協定的比較 55
4.1.3 模擬環境 56
4.1.3.1 控制封包overhead 58
4.1.3.2 路口判斷精確度 62
4.1.3.3 封包傳輸抵達率 65
4.1.3.4 封包傳輸平均延遲時間 68
4.1.3.5 各協定在不同密度下之評比 71
第五章、結論與未來工作 73
第六章、參考文獻 78


圖目錄
圖 1. RREQ示意圖 3
圖 2. RREP示意圖 4
圖 3. 路徑損壞示意圖 5
圖 4. Propagation of RREQ through the Network 22
圖 5. Response of RREP 24
圖 6. Propagation of RERR 26
圖 7. Greedy forwarding example. 28
圖 8. Greedy forwarding failure.. 29
圖 9. The right-hand rule (interior of the triangle) 30
圖 10. RNG(Relative Neighborhood Graph) 31
圖 11. GG(Gabriel Graph） 31
圖 12. Example scenario of forwarding packet in a path. 34
圖 13. Wang et al 的路口示意圖 37
圖 14. 改進後的貪婪模式 39
圖 15. 多路口的封包傳遞示意圖 42
圖 16. 路口示意圖 45
圖 17. 車輛行進角度示意圖 45
圖 18. Ours_nexthop( ) - 當車輛在路口時的演算法 50
圖 19. 整體轉傳封包的演算法 52
圖 20. Simulation Scenario (1500 × 300) by SUMO 57
圖 21. Overhead vs. connections 59
圖 22. Overhead vs. connections 60
圖 23. 路口判斷數比較 62
圖 24. 路口判斷誤判率 63
圖 25. PDR vs. speed 65
圖 26. PDR vs. connections 67
圖 27. ADT vs. speed 68
圖 28. ADT vs. connections 69
圖 29. PDR vs. density 71


表目錄
表 1. AODV_ Beacon 20
表 2. AODV_RREQ 21
表 3. AODV_RREP 23
表 4. AODV_RERR 25
表 5. GPSR_ Beacon 27
表 6. JARR_ Beacon 32
表 7. JARR的道路密度建立方式 33
表 8. Wang et al_ Beacon 36
表 9. Wang et al_Junction Packet 38
表 10. OURS_Beacon 44
表 11. Wang et al與我們的方法之比較 46
表 12. 模擬環境參數 57
表 13. 控制封包SIZE整理表 59
表 14. 各協定控制封包特性總結 76
表 15. 各協定主要模擬結果總結 77

[1].F. Li and Y. Wang, “Routing in Vehicular Ad Hoc Networks : A Survey,” IEEE Vehicular Technology Magazine, June 2007, Vol. 2, No. 2, pp. 12 - 22.
[2].S. Yousefi, M. S. Mousavi, and M. Fathy, “Vehicular Ad Hoc Networks (VANETs): Challenges and Perspectives,” Proceedings of International Conference on ITS Communication (ITST2006), June 2006, Chengdu, China.
[3].S. Basagni, I. Chlamtac, V. R. Syrotiuk and B. A. Woodward, “A distance routing effect algorithm for mobility (DREAM),” The fourth annual ACM/IEEE international conference on Mobile computing and networking, 1998, pp. 76–84.
[4].Y. B. Ko, and N.H. Vaidya, “Location-aided routing(LAR) in mobile ad hoc networks,” Proceedings of the ACM/IEEE Int’l Conf. Mobile Computing and Networking, 1998, pp. 66-75.
[5].B. Karp and H. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” Proceedings of IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), August 2000, Boston, Massachusetts.
[6].Stojmenovic, M. Russcll, and B. Vukojevic, “Depth first search and location based localized routing and QoS routing in wireless networks,” Proceedings of the International Conference on Parallel Processing, 2000 , pp. 173-180.
[7].W. L. Liao, Y. C. Tseng, and J. P. Sheu, “GRID: A Fully Location-Aware Routing Protocol for Mobile Ad Hoc Networks,” Telecommunication Systems, Sept. 2001, pp. 37-60.
[8].SUMO, http://sumo,sourceforge.net
[9].NS2, http://www.isi.edu/nsnam/ns/
[10].T.S. Su, W.L. Jeng, W.S. Hsieh, “ A Survey on Topology-Based Routing for Ad Hoc Wireless Networks” The Proceeding of 2006 the Fundamental Academic Conference on Army College, May 2006, pp. CS1~8.
[11].M. Mauve, A. Widmer ,H. Hartenstein, "A Survey on Position-Based Routing in Mobile Ad-Hoc Networks.", IEEE Network Magazine 15 (6) , November 2001, pp. 30-39.
[12].Stojmenovic, "Position-based routing in ad hoc networks.", IEEE. Communications Magazine, 2002, vol. 40, Issue 7, pp. 128-134.
[13].C. E. Perkins and P. Bhagwat, “Highly dynamic destination sequence distance vector routing (DSDV) for mobile computers,” in ACM SIGCOMM, 1994, pp. 234-244.
[14].C.-C. Chiang, “Routing in Clustered Multihop Mobile Wireless Networks with Fading Channel”, Proceeding of IEEE SICON’97, Apr.1997, pp. 197-211.
[15].T. Clausen, P. Jacquet, “Optimized Link State Routing Protocol (OLSR)” , 2003, RFC3626.
[16].G. Pei, M. Gerla, T.-W. Chen, “Fisheye state routing in mobile ad hoc networks”, in Proceedings of the 2000 ICDCS Workshops, April 2000, pp. D71–D78, Taipei, Taiwan.
[17].C. A. T. H. Tee and A. Lee, “Adaptive Reactive Routing for VANET in City Environments,” Proceedings of the 10th International SymPosium on Pervasive Systems, Algorithms, and Networks, December 2009, pp. 610-614.
[18].Yan-Bo Wang, Tin-Yu Wu,Wei-Tsong Lee, and Chih-Heng Ke, "A Novel Geographic Routing Strategy over VANET", The 4th International Workshop on Telecommunication Networking, Applications and Systems (IEEE TeNAS2010) , 2010, April 20-23, Perth, Australia.
[19].C. E. Perkins and E. M. Royer, “Ad hoc On-Demand Distance Vector Routing,” in: Second IEEE Workshop on Mobile Computing Systems and Applications (WMCSA), February 1999, pp. 90-100, USA.
[20].Johnson, B.D., Maltz, D.A., and Hu, Y.C. “The dynamic source routing protocol for mobile ad hoc networks (DSR)”, draft-ietfmanet-dsr-09.txt (work in progress), Internet Draft, IETF MANET Working Group, Apr. 2003.
[21].Y. Ko and N. H. Vaidya; “GeoTORA: A protocol for geocasting in mobile ad hoc networks”. In Proceeding of 8th International Conference on Network Protocols (ICNP) , November 2000, Pages: 240-250.
[22].Z. J. Haas, “The Routing Algorithm for the Reconfigurable Wireless Networks”. In Proceedings of 6th International Conference on Universal Personal Communications ICUPC, October 1997, vol. 2, pp. 562-566.
[23].A N Al-Khwildi, K.K. Loo & H S Al-Raweshidy, ”An Efficient Routing Protocol for Wireless Ad Hoc Networks”, IEEE Science of Electronic Technology of Information and Telecommunications (SETIT 2007 IEEE),2007 , Tunisia.
[24].Y. Peng, Z. Abichar, and J. Chang, “Roadside-Aided Routing (RAR) in Vehicular Networks,” in IEEE International Conference on Communications, June 2006, vol. 8, pp. 3602-3607.
[25].Y-W Lin, Y-S Chen and S-L Lee, "Routing Protocols in Vehicular Ad Hoc Networks: A Survey and Future Perspectives.", Journal of Information Science and Engineering 26卷3期(2010/05).
[26].Y. Ding , C. Wang and L. Xiao "A static-node assisted adaptive routing protocol in vehicular networks", Proceedings VANET, 2007, pp. 59.
[27].Kevin C. Lee, Uichin Lee, Mario Gerla, "Survey of Routing Protocols in Vehicular Ad Hoc Networks," Advances in Vehicular Ad-Hoc Networks: Developments and Challenges, Oct 2009, IGI Global.
[28].J. Bernsen and D. Manivannan, "Greedy Routing Protocols for Vehicular Ad Hoc Networks," Proceeding Wireless Commun. and Mobile Comp, Aug. 2008, pp. 632-37.
[29].K. H. Lu, S. F. Hwang and C. R. Dow, "A Hybrid Location Service Scheme for Large Ad Hoc Networks." Proceedings of Workshop on 21st Century Digital Life and Internet Technologies Workshop, Sep. 2003.
[30].Hightower, J., and Borriello, G., "A Survey and Taxonomy of Location Systems for Ubiquitous Computing." Tech. Rep. UW-CSE 01-08-03, Dept. of Computer Science and Engineering, University of Washington, 2001.
[31].Lichuan Liu Zhigang Wang Wern-Kueir Jehng, “A Geographic Source Routing Protocol for Traffic Sensing in Urban Environment”, Automation Science and Engineering, 2008, pp. 347-352.
[32].M. Abolhasan, T. Wysocki, and E. Dutkiewicz, “A review of routing protocols for mobile ad hoc networks”, Elsevier Ad Hoc Networks Journal, January 2004, vol. 2, no. 1, pp. 1-22.
[33].Yue Liu, Jun Bi, Ju Yang, “Research on Vehicular Ad Hoc Networks”, Chinese Control and Decision Conference (CCDC), 2009. PP. 4430 – 4435
[34].H. Fusler, H. Hartenstein, J. Widmer, M. Mauve and W. Effelsberg, “Contention-Based Forwarding for Street Scenarios,” Proceedings of the 1st International Workshop on Intelligent Transportation (WIT) , March 2004, pp. 155-160, Hamburg, Germany.
[35].G. Korkmaz, E. Ekici, F. Ozguner and U. Ozguner,, “Urban Multi-Hop Broadcast Protocol for Inter-Vehicle Communication Systems,” First ACM Workshop on Vehicular Ad Hoc Networks (VANET 2004), Oct. 2004, Philadelphia, USA.
[36].Y. Sugiyama, M. Fukui, M. Kikuchi, K. Hasebe, A. Nakayama, K. Nishinari, S. Tadaki and S. Yukawa, “Traffic jams without bottlenecks – experimental evidence for the physical mechanism of the formation of a jam,” New Journal of Physics, 10(033001), 7, March 2004.
[37].Y. Toor, P. Muhlethaler, A. Laouiti, and A.D.L. Fortelle, "Vehicle ad hoc networks: Applications and related technical issues", presented at IEEE Communications Surveys and Tutorials, 2008, pp. 74-88.
[38].Zhang Guoqing,Mu Dejun,”A Survey on the Routing schemes of Urban Vehicular Ad Hoc Networks”, IEEE conference, 2008, pp. 338-343.
[39].Wai Chen,Ratul K.,”A Survey and Challenges in Routing and Data Dissemination in Vehicular Ad-hoc Network”, IEEE International Conference, 2008, pp. 328-333.
[40].J. Zhao and G. Cao, "VADD: Vehicle-Assisted Data Delivery in Vehicular Ad Hoc Networks", IEEE Trans. Vehicular Technology, May 2008, Vol. 57, No. 3.
[41].I. Leontiadis and C. Mascolo, “GeOpps: Opportunistic Geographical Routing for Vehicular Networks,” in proceedings of the IEEE Workshop on Autonomic and Opportunistic Communications, 2007, pp. 1–6.