行動隨意網路的路由協定在近幾年已被廣泛地討論，行動隨意網路中的節點依無線通訊的方式互相交換封包來進行溝通。因為節點的移動使得網路拓樸會頻繁地改變，所以在行動隨意網路中路由協定對於資料傳送過程中如何找出最適當的路徑扮演重要的角色。行動隨意網路的路由協定可分為三類：主動式、被動式及混合式。在被動式的路由協定中，路徑僅在需要時才被建立，因此它們也被稱作隨選式的路由協定。在主動式的路由協定中，每個節點需要週期地傳送封包並更新它們的路由表，所以主動式的路由協定會比被動式的路由協定造成更多頻寬及能源的負擔。混合式的路由協定則兼具主動式和被動式兩種特性，將節點經由分群的方式進行主動及被動的混合模式。AODV是一種被動式的路由協定且受到許多注意，當它需要路徑時會散播路由要求封包並等候回應以建立路徑。然而AODV使用單一路徑而不是利用多重路徑。在單一路徑下，來源點和目的點間原本的路徑發生斷線時必須再找出其他可用的路徑才能繼續傳送資料；相對於多重路徑下，資料封包可透過預先建立好的其他路徑來傳送而不需要節點去重新找尋可用路徑。我們所提出的方法是使用多重路徑應用在AODV上並因此減少因為散播路由要求封包所導致連結斷線的機率。最後，我們對所提出的方法進行模擬並評估效能的改善率。

Routing Protocols for mobile ad hoc networks (MANETs) have been discussed extensively in recent years. Nodes in MANETs communicate with one another by packet exchanges on wireless links. The networks topology changes frequently because of node mobility, therefore routing protocols play an important role in MANETs. Routing protocols of mobile ad hoc networks can be categorized into three classes: Proactive, Reactive and Hybrid. In reactive routing protocols, the routes are established only when required, therefore they are also called on-demand routing protocols. In proactive routing protocols, each node needs to periodic send packets and update its routing table, so they will cause more overheads than reactive routing protocols. The Ad-Hoc On-Demand Distance Vector (AODV) is one of the reactive routing protocols and receiving the most attention. It floods route request packets when it needs a route to use and waits for establishing route by receiving route reply packets. However AODV use single path and do not utilize multiple alternate paths. With alternative routing, data packets are forwarded through a secondary path without requiring the source node to re-flood route request packets to the whole network. We propose a method to use multiple alternate paths on AODV and therefore reduce the connection disruption probability as well as the frequency of flooding of route request. Finally, we apply our method and evaluate the performance improvements by simulation.

中文摘要II
AbstractIII
誌 謝IV
ContentsV
Chapter 1 Introduction1
1.1 Background1
1.2 Motivation3
1.3 Thesis Outline4
Chapter 2 Preliminaries5
2.1 Mobile Ad Hoc Networks5
2.2 AODV and DSR6
2.3 Related Work11
Chapter 3 Research Architecture13
3.1 Problem Description13
3.2 Research Methodology14
3.3 Proposed Approach15
Chapter 4 Simulations and Discussions19
4.1 Simulation Environment19
4.2 Simulation Result20
4.3 Analysis and Discussion31
4.3.1 2HNa vs. NSR34
4.3.2 2HNa vs. AODV-2HBR35
Chapter 5 Conclusion37
5.1 Summary37
5.2 Future Work37
References39

[1] J. Macker and S. Corson, “Mobile Ad Hoc Networks (MANET),” IETF WG
Charter., http://www.ietf.org/html.charters/manet-charter.html, 1997.
[2] E.M. Royer, C.K. Toh, “A Review of Current Routing Protocols for Ad
Hoc Mobile Wireless Networks”, IEEE Personal Communications, April 1999.
[3] C.E. Perkins, E.M. Royer, S.R. Das, “Ad hoc On demand Distance Vector (AODV) Routing”, IETF Draft, February 2000, http://www.ietf.org/ID.html.
[4] C.E. Perkins, P. Bhagwat, “Highly Dynamic Destination-Sequenced
Distance-Vector Routing (DSDV) for Mobile Computers”, Comp. Comm.
Rev., October 1994.
[5] P. Jacquet, P. Muhlethaler, A. Qayyum, “Optimized Link State Routing
Protocol”, IETF Draft, http://www.ietf.org/ID.html.
[6] D.B. Johnson, D.A. Maltz, “The Dynamic Source Routing Protocol (DSR)
for Mobile Ad Hoc Networks”, IETF Draft, http://www.ietf.org/ID.html.
[7] C.-K. Toh , “Long-lived Ad Hoc Routing based on the Concept of Associativity”, IETF MANET Working Group Inter Draft
[8] Z. J. Haas and M. R. Pearlman. The zone routing protocol (zrp) for ad-hoc networks. IETF MANET working group, Internet Draft, June 1999.
[9] Rendong Bai, Mukesh Singhal, "Salvaging Route Reply for On-Demand Routing
Protocols in Mobile Ad-Hoc Networks". MSWiM , pages 10–13, October 2005.
[10] S. J. Lee and M. Gerla, “AODV-BR: Backup Routing in Ad
Hoc Networks,” Proc. IEEE WNMC, vol. 3, pages 1311-1316, Sept. 2000.
[11] Hsing-Lung Chen, Chein-Hsin Lee, "Two Hops Backup Routing Protocol in
Mobile Ad Hoc Networks". Proc. IEEE ICPADS, pages 600 - 604, July 2005.
[12] Perkins C.E., Royer E.M., Das S.R., Marina M.K., "Performance
comparison of two on-demand routing protocols for ad hoc networks".
IEEE wireless communication, vol. 8, issue 1, pages 16-28, February 2001.
[13] Cigdem Sengul, Robin Kravets, “Bypass routing : An on-demand local
recovery protocol for ad hoc networks”, Elsevier Ad Hoc Networks, vol. 4, issue 3, pages 380-397, May 2006.
[14] Suhua Tang, Bing Zhang, “A robust AODV protocol with local update”,
Communications, 2004 and the 5th International Symposium on Multi-Dimensional Mobile Communications Proceedings. The 2004 Joint Conference of the 10th Asia-Pacific Conference on, vol. 1, pages 418-422, Aug 2004.
[15] Gwalani S., Belding-Royer E.M., Perkins C.E., “AODV-PA：AODV with path accumulation”, Communications, 2003. ICC ’03. IEEE International Conference on, Vol. 1, pages 527-531, May 2003.
[16] Higaki H., Umeshima S., “Multiple-route ad hoc on-demand distance vector (MRAODV) routing protocol”, Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS’04), pages 237, April 2004.
[17] Luís Henrique M. K. Costa, Marcelo Dias De Amorim, Serge Fdida, “Reducing Latency and Overhead of Route Repair with Controlled”, Wireless Networks, Vol 10, Issue 4, pages 347-358, July 2004.
[18] Lei Chen, Chung-wei Lee, “Neighbor stability routing in MANETs”, Wireless Communications and Networking Conference 2005 IEEE, Vol. 4, pages 1964-1969, March 2005.
[19] S. Corson, J. Macker, “Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations”, RFC 2501, January 1999.
[20] Lei Chen, Heinzelman W.B., “QoS-Aware Routing Based on Bandwidth Estimation for Mobile Ad Hoc Networks”, Selected Areas in Communications, IEEE Journal on, Vol. 23, Issue 3, pages 561-572, March 2005.
[21] Mueller S., Ghosal D., “Analysis of a distributed algorithm to determine multiple routes with path diversity in ad hoc networks”, Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, 2005. WIOPT 2005. Third International Symposium on, pages 277-285, April 2005.
[22] Charles E. Perkins, Elizabeth M. Royer, “Ad-hoc on-demand distance vector routing”, WMCSA99, pages 90-100, February 1999.
[23] K. Fall and K. Varadhan, Eds., ns Notes and Documentation, VINT project from UC Berkeley, USC/ISI, LBL, and Xerox PARC, http://www.isi.edu/nsnam/ns/, December 2003.
[24] IEEE, “Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications”, IEEE Std. 802.11-1997, 1997.
[25] D. Echardt and P. Steenkiste, “Measurement and Analysis of the Error Characteristics of an In-building Wireless Network” Proc. ACM SIGCOMM ’96, pp. 243-254, Oct. 1999.
[26] B. Tuch, “Development of WaveLAN, an ISM band Wireless LAN,” AT&T Tech. J., vol. 72, no.4, pp. 27-33, July/Aug 1993.
[27] Marcelo Spohn, J.J. Garcia-Luna-Aceves, “Neighborhood aware source routing”, International Symposium on Mobile Ad Hoc Networking & Computing Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, pp. 11-21, 2001.