行動無線隨意網路(Mobile Ad Hoc Networking)是指由一群具移動性的節點所動態組成的無線網路。此網路不需要如基地台等形式的基礎建設或集中式的管理設備，而是透過網路中的節點互相幫助將資訊繞送至目的端。而在行動無線隨意網路中，路由協定一直是相關研究中的重點項目，因為節點具有移動性，且在頻寬與能源都受到限制的環境下，如何建立理想的封包繞送路徑便成為最重要的課題。
而路由協定中，亦有許多不同的問題需要克服，以需求式的距離向量路由協定AODV為例，路由的探索都是透過濫傳的方式進行，而濫傳所產生的控制封包，往往容易造成網路的壅塞，尤其是在節點數量或是連線數目上升時更為明顯，我們稱這個現象為廣播風暴。除此之外，已建立的路徑常因為節點的移動而損毀，在AODV中是以重新廣播路由探索封包的方式來重建或修補路由，這個做法的修復速度較慢且會耗費更多的控制封包。對於廣播風暴的問題，已有許多方法被提出，如多重中繼點廣播機制，而亦有許多多路徑或區域修復的機制，用來解決路徑損毀的問題，如AOMDV或AODV-ABR。但這些方法中，大部份都只有針對單一的問題進行深究，而未探討如何將廣播機制與路由機制作良好的結合。
因此，在本論文中，將以多重中繼點的廣播機制與2-hop的區域修復機制結合，透過多重中繼點廣播機制減少廣播封包，並利用多重中繼點額外建立的2-hop鄰居表進行有效的區域修復。最後，再與其他利用多重中繼點的路由協定或是多路徑路由協定進行模擬與評估，實驗結果證明本論文所提出的方法，可以有效的修復路由且減少控制封包所消耗的頻寬。

MANET (Mobile Ad Hoc Networking) is a dynamic wireless network with a group of mobile nodes. This network does not need base stations and other forms of infrastructure or centralized management of devices but to send information to the destination through nodes cooperation of the network. In mobile wireless ad hoc networks, routing protocols research has been the focus of related field, because of node mobility and restriction of the bandwidth and energy. How to create the ideal packet routing path is the most important issue. 
There are many problems need to overcome in routing protocol. For example, in on-demand distance vector routing protocol (AODV), route of exploration is through flooding route request packet (RREQ), and the flooding packets often result in network congestion, particularly when the number of nodes or connections increase. We call this phenomenon as the Broadcast storm. In addition, the established path may broke frequently due to mobility. AODV will re-Broadcast route discovery packet to rebuild or repair route, but it is not an efficient way, because this procedure will consume more control packet. There are many methods have been proposed to solve Broadcast storm problem, such as multipoint relaying (MPR). And there are many multi-path or repair scheme to solve the damage issues of path, such as AOMDV or AODV-ABR. However, most of proposed methods are single goal chaser, but neglect of perfect combination of Broadcast scheme and routing repair scheme. 
In this thesis, we will combine multi-point relaying Broadcast scheme and 2-hop route repair scheme, through the multi-point relaying Broadcast scheme to reduce Broadcast packet, and use an additional 2-hop neighbor table to repair route. Finally, simulation results show that the proposed protocol can effectively repair the route and reduce bandwidth consumed by control packets.

目錄
第一章、緒論	1
1.1、簡介與研究動機	1
1.2、論文架構	5
第二章、相關研究	6
2.1、AODV	6
2.1.1、Route Request	6
2.1.2、Route Reply	8
2.1.3、Route Maintenance	9
2.2、多路徑路由協定	11
2.2.1、AOMDV	11
2.2.2、AODV-BR	13
2.3、區域路由修復機制	15
2.3.1、PATCH	16
2.3.2、AODV-ABR	17
2.3.3、OPTAODV	19
2.4、相關協定之比較	20
2.5、無線隨意網路中的廣播機制	23
2.5.1、廣播問題的特性	23
2.5.2、因為濫傳引起的廣播風暴	24
2.5.3、解決廣播風暴的機制	25
2.5.4、多重中繼點	29
第三章、新協定之提出	33
3.1、基本構想	33
3.2、鄰居表維護	34
3.3、路由探索	38
3.4、路由回覆	43
3.5、路由維護	46
3.6、路由修復	47
第四章、效能評估	63
4.1、模擬環境	64
4.2、模擬結果	67
4.2.1、Packet Delivery Ratio	67
4.2.2、Hop Counts	70
4.2.3、Delay per Hop	79
4.2.4、Control Overhead	85
4.3、總結	93
第五章、結論	95
參考文獻	98

圖目錄
圖1. Propagation of RREQ in AODV	8
圖2.Propagation of RREP in AODV	9
圖3.Propagation of RERR in AODV	10
圖4.Alternate Route of AODV-BR	14
圖5(a).Re-Route of data packet in AODV-ABR	18
圖5(b).Re-Route of data packet in AODV-ABR	18
圖5(c).Re-Route of data packet in AODV-ABR	18
圖6.MPR Set 選擇範例	30
圖7.2-hop鄰居表維護範例	38
圖8.接收RREQ之處理流程	40
圖9. Propagation of RREQ in the Proposed Protocol	42
圖10.接收RREP之處理流程	44
圖11. Propagation of RREP in the Proposed Protocol	45
圖12.路由修復之流程	48
圖13.接收RPRQ之處理流程	53
圖14.RPRQ演算法	54
圖15.RPRP演算法	55
圖16(a).2-hop修復機制修復成功示意圖	56
圖16(b). 2-hop修復機制修復成功示意圖	57
圖16(c). 2-hop修復機制修復成功示意圖	57
圖16(d). 2-hop修復機制修復成功示意圖	57
圖16(e). 2-hop修復機制修復成功示意圖	58
圖17(a). 2-hop修復機制修復失敗示意圖	59
圖17(b). 2-hop修復機制修復失敗示意圖	59
圖17(c). 2-hop修復機制修復失敗示意圖	59
圖17(d). 2-hop修復機制修復失敗示意圖	60
圖18. Average Packet Delivery Ratio (Scenario-1)	67
圖19.Average Packet Delivery Ratio (Scenario-2)	69
圖20.Average Hop Count (Scenario-1)	71
圖21(a).利用多重中繼點廣播機制探索之路徑	73
圖21(b).未利用多重中繼點廣播機制探索之路徑	73
圖22. Average Hop Count (Scenario-2)	75
圖23.Average Hop Count Ratio (Scenario-2)	77
圖24. Average End to End Delay (Scenario-1)	80
圖25. Average Delay per Hop (Scenario-1)	80
圖26. Average Delay per Hop (Scenario-2)	83
圖27. Average End to End Delay (Scenario-2)	84
圖28.Total Control Overhead (Scenario-1)	86
圖29. Control Overhead for MPRDV, MMDV and the Proposed Protocol (Scenario-1)	89
圖30. Total Control Overhead (Scenario-2)	91
圖31. Total Control Overhead in 54Mbps(Scenario-2)	91
圖32. Control Overhead for MPRDV, MMDV and the Proposed Protocol (Scenario-2)	93

表目錄
表1.現有多路徑機制之比較	21
表2.現有路由修復機制之比較	22
表3.Hello Packet Format	35
表4.Hello Type List	35
表5.RREQ Packet Format	39
表6.RREP Packet Format	44
表7(a).RPRQ Packet Format	49
表7(b).RPRP Packet Format	49
表7(c).RPF Packet Format	49
表7(d).RTCH Packet Format	50
表8.RERR Packet Format	51
表9.Summary of Common Parameters Used in Simulation	65
表10. Parameters Used in Scenario	66
表11.各協定模擬結果總結	94

[1] S. Corson, J. Macker, “Mobile Ad Hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations (Internet-Draft),” RFC2501, January 1999.
[2] Internet Engineering Task Force (IETF) Mobile Ad Hoc Networks (MANET) Working Group Charter, Chaired by J. Macker and M. Scott Corson, http://www.ietf.org/html.charters/manet-charter.html.
[3] C. E. Perkins, E. M. Royer, “Ad hoc On-Demand Distance Vector (AODV) Routing,” Internet Draft, Mobile Ad Hoc Networking Working Group, March 2001. 
[4] D. B. Johnson, D. A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,” Mobile Computing, Chapter 5, ed. T. Imielinski and H. Korth, Kluwer Academic Publishers, pp.153-181, 1996.
[5] C. E. Perkins, P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” Proceedings of the Special Interest Group on Data Communications 1994 Conference on Communications Architectures, Protocols and Applications, August 1994, pp. 234-244.
[6] T. Clausen, P. Jacquet, Eds., “Optimized Link State Routing Protocol (OLSR),” RFC 3626, Oct. 2003.
[7] L. Liang, Y. A. Sekercioglu, N. Mani, “A Survey of Multipoint Relay Based Broadcast Schemes in Wireless Ad Hoc Networks,” IEEE Communications Surveys and Tutorials, vol. 8, no. 1-4, pp. 30-46, December 2006.
[8] A. Qayyum, L. Viennot, A. Laouiti, “Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks,” Proceedings of the 35th Annual Hawaii International Conference on System Sciences, Hawaii, 2002, pp. 298-308.
[9] G. Allard, P. Jacquet, L. Viennot, “Ad Hoc Routing Protocols with Multipoint Relaying,” 5eme Rencontres Francophones sur les aspects Algorithmiques des Telecommunications, 2003.
[10] M. K. Marina, S. R. Das, “On-demand Multipath Distance Vector Routing for Ad Hoc Networks,” Proceedings of the International Conference for Network Procotols, Riverside, November 2001, pp. 14-23.
[11]S. Mueller, R.P. Tsang, D. Ghosal, “Multipath Routing in Mobile Ad Hoc Networks: Issues and Challenges,” Proceedings of the 11th International Symposium on Modeling, Analysis and Simulation of Computer and Telecomm. Systems Tutorials, 2003, pp. 209-234.
[12] “The VINT project. The network Simulator - ns-2.” [Online]. Available: http://www.isi.edu/nsnam/ns
[13] A. Mtibaa, F. Kamoun, “MMDV: Multipath and MPR Based AODV Routing Protocol,” Proceedings of the IFIP Fifth Annual Mediterranean Ad Hoc Networking Workshop, 2006, pp. 137-144.
[14] S. J. Lee, M. Gerla, “AODV-BR: Backup Routing in Ad Hoc Networks,” Proceedings of the IEEE Wireless Communications and Networking Conference, 2000, pp.1311-1316.
[15] G. Liu, K. J. Wong, B. S. Lee, B. C. Seet, C. H. Foh, L. J. Zhu, “PATCH: A Novel Local Recovery Mechanism for Mobile Ad Hoc Networks,” Proceedings of the IEEE Vehicular Technology Conference, October 2003, vol. 5, pp. 2995-2999.
[16]W. K. Lai, S. Y. Hsiao, Y. C. Lin, “Adaptive Backup Routing for Ad Hoc Networks,” Computer Communications, vol. 30, Issue. 2, pp. 453-464, January 2007.
[17]W. Ge, P. W. Li, “(OPTAODV)An Optimized AODV Protocol for Ad Hoc Network,” Proceedings of the International Conference on 4th Wireless Communications, Networking and Mobile Computing, 2008, pp. 1-4.
[18] J. Cai, W. Wu, “Degraded Link-disjoint Multipath Routing in Ad Hoc Networks,” Proceedings of the International Symposium on 4th Wireless Pervasive Computing, 2009, pp. 1-5.
[19] B. Xue, P. Y. Ren, S. C. Yan, “Link Optimization Ad Hoc On-Demand Multipath Distance Vector Routing for Mobile Ad-Hoc Networks,” Proceedings of the International Conference on 5th Wireless Communications, Networking and Mobile Computing, 2009, pp .1-6.
[20] J. J. Galvez, P. M. Ruiz, A. Skarmeta , “Achieving Spatial Disjointness in Multipath Routing without Location Information,”  Proceedings of the Wireless Communications and Networking Conference, 2009, pp. 5-8.
[21] S. Wang, Q. Li, Y. Jiang, H. Xiong, “Stable On-demand Multipath Routing for Mobile Ad Hoc Networks,” Proceedings of the Asia-Pacific Conference on Computational Intelligence and Industrial Applications, 2009, pp. 318-321.
[22] M. Pan, S. Y. Chuang, S. D. Wang, “Local Repair Mechanisms for On-demand Routing in Mobile Ad Hoc Networks,” Proceedings of the 11th Pacific Rim International Symposium on Dependable Computing, December 2005, pp. 1-8.
[23] J. Singh, P. Singh, S. Rani, “Enhanced Local Repair AODV (ELRAODV),” Proceedings of the International Conference on Advances in Computing, Control, and Telecommunication Technologies, December 2009, pp. 787-791.
[24] J. Sirilar, K. Rojviboonchai, “OHO: Overhearing On-demand Route Repair Mechanism for Mobile Ad Hoc Networks,” Proceedings of the International Conference on Electrical Engineering/Electronics Computer Telecommunications and Information Technology, May 2010, pp. 66-70.
[25] N.S. Kulkarni, I. Gupta, B. Raman, “On Demand Routing Protocols for Mobile Ad Hoc Networks: A Review,” Proceedings of the IEEE International Advance Computing Conference, 2009, pp. 586-591.
[26] J. Wu, “An Enhanced Approach to Determine a Small Forward Node Set Based on Multipoint Relays,” Proceedings of the IEEE Semiannual Vehicular Technology, 2003, pp. 866–81.
[27] X. Chen, J. Shen, “Reducing Connected Dominating Set Size with Multipoint Relays in Ad Hoc Wireless Networks,” Proceedings of the 7th international symposium on parallel architectures, algorithms and networks, May 2004, pp. 539-43.
[28] J. Wu, W. Lou, “Extended Multipoint Relays to Determine Connected Dominating Sets in MANETs,” IEEE Transactions on Computers, vol. 55, pp. 334-347, March 2006.
[29] B. Mans, N. Shrestha, “Performance Evaluation of Approximation Algorithms for Multipoint Relay Selection,” Proceedings of the 3rd Annual Mediterranean Ad Hoc Networking Workshop, 2004, pp. 480-491.
[30] N. Shrestha, “Performance Evaluation of Multipoint Relays: Collision and Energy Efficiency Issues,” Macquarie University, Technology Report, April 2003.
[31] J. Lipman, P. Boustead, J. Judge, “Utility-based Multipoint Relay Flooding in Heterogeneous Mobile Ad Hoc Networks,” Proceedings of the Workshop on the Internet, Telecommunications and Signal Processing , 2002, pp. 27–33.
[32] S. Y. Ni, Y. C. Tseng, Y. S. Chen, J. P. Sheu, “The Broadcast Storm Problem in a Mobile Ad Hoc Network,” Proceedings of the International Conference on Mobile Computing and Networking, 1999, pp. 151-162.
[33] B. Williams, T. Camp, “Comparison of Broadcasting Techniques for Mobile Ad Hoc Networks,” Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking and computing, 2002, pp, 194-205.
[34] S. Kumar, R. K. Rathy, D. Pandey, “Traffic Pattern Based Performance Comparison of Two Reactive Routing Protocols for Ad Hoc Networks Using NS2,” Proceedings of the 2nd IEEE International Conference on  Computer Science and Information Technology, 2009, pp. 369-373.
[35] C. E. Perkins, E. M. Royer, S. R. Das, M. K. Marina, “Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks,” Proceedings of the IEEE Conference on Computer Communications, March 2000, pp. 3–12.