行動隨意網路（Mobile Ad Hoc Network）是由行動節點（Mobile Node）動態地聚集而形成的，因此，行動隨意網路的網路拓樸會隨著行動節點的移動而自行調適。在行動隨意網路的環境中，由於資料封包的交換是透過所有的行動節點互相地轉送來達成，所以，行動節點不需要基地台（Base Station）或存取器（Access Point）的輔助，就能夠彼此間相互地通訊。為了要克服行動隨意網路這種先天的特性，本篇論文提出了動態備用路徑路由協定以及一個整合性的快取機制。
    動態備用路徑路由協定是一種隨選路徑路由協定（On-demand Routing Protocol），它可以在一段被給定的時間內建立許多的備用路徑，這些用來設定備用路徑的資訊可以儲存在資料繞送路徑中的節點上，當來源節點到目的節點之間的路徑連結斷裂時，備用路徑可以快速地取代原有的繞送路徑，讓路徑可以很快的恢復連結，資料能夠快速地重新繼續傳輸，透過論文中模擬的結果顯示，動態備用路徑路由協定比其他路由協定更能夠改善路由的品質。本篇論文也同時提出了一個整合動態備用路徑路由的快取機制，藉由此機制的幫助之下，可以將重複出現在行動隨意網路中的資料與資料的存取路徑快取（Cache）在某些特定的行動節點上，如此可以縮短存取資料的路徑，進而加快資料的存取時間，並提高資料的重複使用率，來達到節省網路傳輸頻寬以及行動節點電池能源的消耗。

A Mobile Ad Hoc Network (MANET) is a self-organizing and adaptive wireless network constructed by the dynamic gathering of mobile nodes. The communication among mobile nodes in MANETs is carried out without base stations or access points and the transmission of data packets is completed through relays among nodes. Due to the mobility of mobile nodes, the topology of a MANET frequently changes and thus results in the disability of on-the-fly data transmission routes. To cope with the intrinsic properties of MANETs, Dynamic Backup Routes Routing Protocol (DBR^2P) and an integrated Cache-Based Mechanism are proposed in this dissertation.
    DBR^2P is an on-demand backup routing protocol which can set up many backup routes to reach a destination node in a given period of time. The information of backup routes can be saved in a specific on-the-route node and enables backup routes to be found immediately in situation regarding disconnection. When a link fails, routes from the source node to the destination node are analyzed to obtain backup routes and to sustain quick reconnection. As a result, DBR^2P could more thoroughly improve the quality of routing than previous routing protocols. Furthermore, with the aid of the proposed integrated Cache-Based Mechanism, repetition of data and data paths occurring in a MANET could be cached in some special mobile nodes. Therefore, routes and time span to access data are shortened. The data reusable rate is also enhanced to reduce the consumption of bandwidth and battery power.

Contents

Acknowledgements	-viii-
中文摘要  	-x-
Abstract  	-xi-
List of Figures	-xv-
List of Tables	-xvii-
1	Introduction	-1-
2	Related Work	-7-
2.1	MANET Routing Protocol Performance Issues	-7-
2.2	Classification of Routing Protocols for MANETs	-8-
2.3	Proactive Routing Protocols	-9-
2.3.1	Destination-Sequence Distance-Vector Routing Protocol	-10-
2.3.2	Wireless Routing Protocol	-12-
2.4	Reactive Routing Protocols	-14-
2.4.1	Dynamic Source Routing Protocol	-15-
2.4.2	Ad Hoc On-demand Distance-Vector Routing Protocol	-17-
2.5	Hierarchical Routing Protocols	-19-
2.5.1	Clusterhead-Gateway Switch Routing	-20-
2.5.2	Zone Routing Protocol	-22-
2.6	Position-based Routing Protocols	-23-
2.6.1	Location-Aided Routing Protocol	-24-
2.6.2	Distance Routing Effect Algorithm for Mobility Protocol	-25-
2.7	Multiple/Backup Path(s) Routing Protocols	-26-
2.7.1	AODV-BR	-28-
2.7.2	Signal-Power Adaptive Fast Rerouting Protocol	-29-
2.7.3	Extend Dynamic Source Routing Protocol	-30-
2.7.4	Redundancy Based Multi-path Routing Protocol	-31-
2.8	Passive Acknowledgement	-33-
2.9	Cache Mechanisms	-34-
3	Dynamic Backup Routes Routing Protocol	-37-
3.1	Three Phases of DBR^2P	-38-
3.1.1	Route Discovery Phase	-40-
3.1.2	Backup Node Setup Phase	-42-
3.1.3	Route Maintenance Phase	-43-
3.2	Algorithms of DBR^2P	-44-
3.2.1	Algorithms of Route Discovery Phase	-45-
3.2.2	Algorithms of Backup Node Setup Phase	-49-
3.2.3	Algorithms of Route Maintenance Phase	-53-
3.3	An Example of Using DBR^2P	-54-
4	Performance Evaluation of DBR^2P	-58-
4.1	Simulation Environment	-58-
4.2	Results and Analysis	-62-
5	The Cache-Based Mechanism Integrated with DBR^2P	-67-
5.1	Temporal Locality and Spatial Locality in MANETs	-68-
5.2	Integrated Cache-Based Mechanism	-69-
5.3	Data Caching Scheme	-70-
5.4	Data-path Caching Scheme	-71-
5.5	Compound Caching Scheme	-72-
5.6	Handoff Processes	-73-
5.7	Cache-Based Mechanism Interchangeability	-75-
6	Conclusion and Future Work	-76-
6.1	Conclusion	-76-
6.2	Future Work	-77-
Bibliography	 -78-
Appendix A.	 -84-
Appendix B.	 -114-
Appendix C.	 -140-


List of Figures

Figure 1-1   Infrastructured wireless networks.	-2-
Figure 1-2   Infrastructureless wireless networks (Mobile Ad Hoc Networks).	-3-
Figure 2-1   Classification of Routing Protocols for MANETs.	-9-
Figure 2-2   An example of a MANET with eight mobile nodes.	-11-
Figure 2-3   Creation of the route record in DSR.	-16-
Figure 2-4   AODV route discovery phase.	-18-
Figure 2-5   CGSR routing: showing a data path from source node to destination node.	-21-
Figure 2-6   An example of using Zone Routing Protocol.	-23-
Figure 2-7   Consideration of route physical distance.	-25-
Figure 2-8   Data transmission through multiple paths at the same time.	-27-
Figure 2-9   Data transmission through using a backup path(s) routing protocol.	-28-
Figure 2-10  A fish bone topology formed by multiple routes.	-29-
Figure 2-11  A sample of using extended dynamic source routing.	-31-
Figure 2-12  Route reply process with redundant path setup using RBMR.	-33-
Figure 2-13  An example of the passive acknowledgement.	-34-
Figure 3-1   The main architecture of DBR^2P.	-39-
Figure 3-2   Route discovery phase of DBR^2P.	-40-
Figure 3-3   An example of a MANET.	-55-
Figure 3-4   An example of a route tree and the backup node subset in DBR2P.	-56-
Figure 3-5   An example of a link failure.	-57-
Figure 4-1   Performance comparison of control message overhead.	-63-
Figure 4-2   Performance comparison of data throughput.	-64-
Figure 4-3   Performance comparison of average transfer latency.	-66-
Figure 5-1   Temporal locality and spatial locality in a MANET.	-68-
Figure 5-2   A mobile node is installed with a Cache Sharing Interface.	-70-
Figure 5-3   An example of data transmission path in a MANET.	-71-
Figure 5-4   The cache boundaries when using compound caching scheme.	-73-
Figure 5-5   The handoff processes after link failures occur.	-74-


List of Tables

Table 2-1  Routing table of mobile node C.	-12-
Table 2-2  Advertised table of mobile node C.	-12-
Table 3-1  The main protocol packets of DBR^2P.	-38-
Table 4-1  A summary of DBR^2P, DSR and DSDV.	-61-

Bibliography

[Basagni1998]	S. Basagni, I. Chlamtac, V. R. Syrotiuk, and B. A. Woodward, “A Distance Routing Effect Algorithm for Mobility (DREAM),” Proc. of the 5th Annual ACM/IEEE Int’l Conference on Mobile Computing and Networking, pp. 76-84, 1998.

[Bertsekas1987]	D. Bertsekas and R. Gallager, Data Networks, N. J.: Prentice-Hall, Englewood Cliffs, pp. 297-333, 1987.

[Boukerche2000]	A. Boukerche, A. Fabbri, and S. K. Das, “Analysis of Randomized Congestion Control in DSDV Routing,” Proc. of the 8th Int’l Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pp. 65-72, 2000.

[Broch1998]	J. Broch, D. A. Maltz, D. B. Johnson, Y. C. Hu, and J. Jetcheva, “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols,” Proc. of the Mobicom’98, pp. 85-97, 1998.

[Chiang1997]	C. C. Chiang, “Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel,” Proc. of the IEEE Sicon’97, pp. 197-211, Apr. 1997.

[Cho2003]	Joonho Cho, Seungtaek Oh, Jaemyoung Kim, Hyeong Ho Lee, and Joonwon Lee, “Neighbor Caching in Multi-hop Wireless Ad hHoc Networks,” IEEE Communications Letters, Vol. 7, Iss. 11, pp. 525-527, Nov. 2003.

[Chuang2003]	S. N. Chuang, T. S. Chan, J. Cao, R. Cheung and R. Cheung, “Dynamic Service Reconfiguration for Wireless Web Access,” Proc. of the Int’l WWW conference, pp. 58-67, 2003.

[Cieslak2001]	M. Cieslak, D. Foster, G. Tiwana, and R. Wilson, “Web cache coordination protocol v2.0,” IETF Internet Draft, April 2001.
http://www.ietf.org/internet-drafts/draft-wilson-wrec-wccp-v2-01.txt

[Corson1999]	S. Corson and J. Macker, “Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations,” IETF RFC2501, Jan. 1999.

[Das2000]	S. R. Das, R. Castaneda, and J. Yan, “Simulation-based Performance Evaluation of Routing Protocols for Mobile Ad Hoc Networks,” ACM/Baltzer Mobile Networks and Applications (MONET), Vol. 5, No. 3, pp. 179-189, 2000.

[Denning1972]	P. J. Denning and S. C. Schwartz, “Properties of the Working-set Model,” Communications of the ACM, Vol. 15, No. 3, pp. 185-190, Mar. 1972.

[Fan2000]	L. Fan, P. Cao, J. Almeida and A. Broder, “Summary cache: a scalable wide-area Web cache sharing protocol,” ACM/IEEE Transactions on Networking, Vol. 8, Iss. 3, pp. 281-293, June 2000.

[Frodigh2000]	M. Frodigh, P. Johansson, and P. Larsson, “Wireless Ad Hoc Networking: the Art of Networking without a Network,” Ericsson Review, No. 4, pp. 248-263, 2000.

[FordJr1962]	L. R. Ford Jr. and D. R. Fulkerson, Flows in Networks, Princeton Univ. Press, 1962.

[Hong2002]	X. Hong, Kaixin Xu, and Mario Gerla, “Scalable Routing Protocols for Mobile Ad Hoc Networks,” IEEE Network Magazine, Vol. 16, Iss. 4, pp. 11-21, Jul./Aug. 2002.

[Hwang2001]	Young-Ki Hwang, Hyungkenu Lee, Pramod K. Varshney, “An Adaptive Routing Protocols for Ad-Hoc Networks using Multiple Disjoint Paths,” Proc. of the IEEE Vehicular Technology Conference (VTC’2001), Vol. 3, pp. 2249-2253, May 2001.

[Iwata1999]	A. Iwata, C. C. Chiang, G. Pei, M.Gerla, and T. W. Chen, “Scalable Routing Strategies for Ad Hoc Wireless Networks,” IEEE Journal on Selected Areas in Communications, Special Issue on Ad Hoc Networks, pp. 1369-1379, Aug. 1999.

[Jiang2001]	Ming-Hong Jiang and Rong-Hong Jan, “An Efficient Multiple Paths Routing Protocol for Ad-hoc Networks,” Proc. of the 15th Int’l Conference on Information Networking, pp. 544-549, Jan./Feb. 2001.

[Johansson1999]	P. Johansson, T. Larsson, N. Hedman, B. Mielczarek, and M. Degermark, “Scenario-based Performance Analysis of Routing Protocols for Mobile Ad-Hoc Networks,” Proc. of the ACM/IEEE MOBICOM’99, pp. 195-206, Aug. 1999.

[Johnson1996]	D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad-Hoc Wireless Networks,” Mobile Computing, edited by T. Imielinski and H. Korth, Eds., Kluwer, pp. 153-181, 1996.

[Jubin1987]	John Jubin and Janet D. Tornow, “The DARPA Packet Radio Network Protocols,” Proc. of the IEEE, Vol. 75, No. 1, pp. 21-32, Jan. 1987.

[Karp2000]		Brad Karp and H. T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks” Proc. of the ACM MOBICOM, pp. 243-254, Aug. 2000.

[Katz1998]	R. Katz and M. Stemm, “Reducing Power Consumption of Network Interfaces in Hand-Held Devices” Proc. of the 3rd Int’l Workshop on  Mobile Multimedia Communications (MoMuC-3), pp. 66-75, Dec. 1996.

[Kim2003]	Sangkyung Kim, Wonjong Noh, and Sunshin An, “Multi-path Ad Hoc Routing Considering Path Redundancy,” Proc. of the 8th IEEE Int’l Symposium on Computers and Communications (ISCC’2003), Vol. 1, pp. 45-50, June/Jul. 2003.

[Ko1998]		Y. B. Ko and N. H. Vaidya, “Location-aided Routing (LAR) in Mobile Ad Hoc Networks,” Proc. of the ACM/IEEE Int’l Conf. Mobile Computing and Networking, pp. 66-75, 1998.

[Lau2002]	W. H. O. Lau, M. Kumar, and S. Venkatesh, “A Cooperative Cache Architecture in Support of Caching Multimedia Objects in MANETs,” Proc. of the 5th ACM Int’l workshop on Wireless mobile multimedia, pp. 56-63, Sept. 2002.

[Lee2000]	Sung-Ju Lee, Mario Gerla, “AODV-BR: Backup Routing in Ad Hoc Networks,” Proc. of the IEEE Wireless Communications and Networking Conference (WCNC’2000), Vol. 3, pp. 1311-1316, Sept. 2000.

[LeeWW2000]	C. C. Lee, Y. M. Wang and T. P. Wang, “A Transparent Proxy Mechanism for WWW in Wireless Multihop Networks,” Proc. of the 6th Workshop on Mobile Computing, pp. 145-150, Mar. 2000.

[Lee2001]	Sung-Ju Lee, Mario Gerla, “Split Multipath Routing with Maximally Disjoint Paths in Ad Hoc Networks,” Proc. of the IEEE Int’l Conference on Communications, pp. 3201-3205, June 2001.

[Marina2001]	M. K. Marina and S. R. Das, “On-demand Multipath Distance Vector Routing in Ad Hoc Networks,” Proc. of the 9th IEEE Int’l Conference on Network Protocols (ICNP), pp.14-21, Nov. 2001.

[Markatos1998]	E. Markatos and C. Chronaki, “A Top-10 Approach to Prefetching on the Web,” Proc. of the INET, 1998.

[Moriya2003]	T. Moriya and H. Aida, “Cache Data Access System in Ad Hoc Networks,” Proc. of the IEEE Vehicular Technology Conference (VTC), Vol. 2, pp. 1228-1232, Apr. 2003.

[Murthy1996]	S. Murthy and J. J. Garcia-Luna-Aceves, “An Efficient Routing Protocol for Wireless Networks,” ACM Mobile Networks and App. J., Special Issue on Routing in Mobile Communication Networks, pp. 183-197, Oct. 1996.

[Pearlman1999]	M. R. Pearlman and Z. J. Haas, “Determining the Optimal Configuration for the Zone Routing Protocol,” IEEE Journal on Selected Areas in Communications, Special Issue on Wireless Ad Hoc Networks, Vol. 17, No. 8, pp.1395-1414, Aug. 1999.

[Pei2000]	G. Pei, M. Gerla, and T. W. Chen, “Fisheye State Routing: A Routing Scheme for Ad Hoc Wireless Networks,” Proc. of the 2000 ICDCS Workshop on Wireless Networks and Mobile Computing, Taipei, Taiwan, pp. 71-78, Apr. 2000.

[Perkins1994]	C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” ACM SIGCOMM ’94 Computer Communications Review, Vol. 24, No. 4, pp. 234-244, Aug. 1994.

[Perkins1999]	C. E. Perkins and E. M. Royer, “Ad-hoc On-Demand Distance Vector Routing,” in Proc. of the 2nd IEEE Workshop Mobile Comp. Sys. and Apps., pp. 90-100, Feb. 1999.

[Perkins2003]	C. E. Perkins, E. M. Royer, and S. R. Das, “Ad Hoc on Demand Distance Vector (AODV) Routing,” IETF Internet Draft (work in progress), Feb. 2003.
http://www.ietf.org/internet-drafts/draft-ietf-manet-aodv-13.txt

[RichardIII2000]	G. G. Richard III, “Service Advertisement and Discovery: Enabling Universal Device Cooperation,” IEEE Internet Computing, Vol. 4, No. 5, pp. 18-26, Sep. 2000.

[Rousskov1998]	A. Rousskov and D. Wessels, “Cache digests,” Computer Networks and ISDN Systems, Vol. 3, No. 22-23, pp. 2155-2168, 1998.

[Royer1999]	E. M. Royer and C. K. Toh, “A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks,” IEEE Personal Communications, Vol. 6, No. 2, pp. 46-55, Apr. 1999.

[Smith1982]	A. J. Smith, “Cache Memories,” ACM Computing Surveys, Vol. 14, No. 3, pp. 473-530, Sep. 1982.

[Toh1996]		C. K. Toh, “A Novel Distributed Routing Protocol to Support Ad-Hoc Mobile Computing,” Proc. of the 15th IEEE Annual Int’l. Phoenix Conf. Camp. and Commun., pp. 480-486, Mar. 1996.

[Wessels1997]	D. Wessels and K. Claffy, “Internet Cache Protocol (ICP), version 2,” IETF RFC2186, Sept. 1997.

[Wessels1998]	D. Wessels and K. Claffy, “ICP and the Squid Web Cache,” IEEE Journal on selected areas in Communication, pp. 345-357, 1998.

[Wu2002]	Jie Wu, “An Extended Dynamic Source Routing Scheme in Ad Hoc Wireless Networks,” Proc. of the 35th Annual Hawaii Int’l Conference on System Sciences (HICSS-35), pp. 3832-3838, Jan. 2002.

[Zenel1999]	Bruce Zenel, “A general purpose proxy filtering mechanism applied to the mobile environment,” Wireless Networks, Vol. 5, Iss. 5, pp. 391-409, Oct. 1999.