階層式路由（Hierarchical Routing）以分群（Clustering）的方式提供在大型行動隨意網路（Mobile Ad Hoc Networks，MANETs）中解決路由資訊傳送距離過長，路由資訊將變得不確定的問題，HSR是其中最典型的代表，然而傳統階層式路由協定，皆需要特定的節點，來維護整個路由資訊管理架構，當這個特定的節點變動的頻率過高時，整個路徑管理架構重建的次數也隨之變多，這將大幅降低路由維護的效率。
本篇論文在DDR演算法進行衍生，提出一個多層式閘道路由通訊協定（Multi-level Gateway Routing Protocol，MGRP），將網路上的節點分割成為數個不相重疊的區域（Zone）。再以動態的方式將閘道節點（Gateway）組成階層式的架構，透過階層式架構交換路由資訊，減少路徑探詢的成本；同時因為不需要特定節點維護階層架構，可降低路徑管理架構重建的成本。經研究發現，當MGRP將有n個節點的網路拓墣平均分割成 k 個群組時，在路徑探尋階段的時間複雜度，可降至為O(2n / k)。若網路拓墣被以傳統階層式路由演算法分成h層，在特定的節點遺失時，MGRP對於路由資訊重建的通訊複雜度可從O(( n / k) × h )降為O(3n / k)，約為3 / h。

關鍵字：階層式路由、群組、閘道節點、行動隨意網路

By means of clustering Hierarchical Routing Protocol aims to eliminate the instability of the transference of routing information in large Mobile Ad Hoc Networks. However, the traditional hierarchical routing protocol tends to be inefficient and ineffective. Take Hierarchical State Routing (HSR) for example, this approach maintains hierarchical framework information at each level with the use of a specific node. When some critical node changes, the whole framework may need to be reconstructed. Therefore, the more often the critical nodes change, the less efficient and effective the routing information management. This paper propose a Multi-level Gateway Routing Protocol (MGRP), intending to better the routing information management. Derived from DDR Algorithm, the protocol forms a hierarchical framework by cutting topology into non-overlapping Zone and clustering the Gateway node into Clusters. This arrangement can reduce the time complexity of path discovery. Besides, it can reduce the overhead of reconstructing the hierarchical frameworks. It is found in this study that MGRP can reduce the time complexity of path discovery to O(2n / k) by cutting a topology of n nodes into k Cluster in each level. What’s more, MGRP is more competent in reducing communication complexity than HSR. Given that HSR and MGRP cluster the topology to average h level hierarchical framework, MGRP performs better in the reconstruction of the hierarchical framework by reducing the communication complexity from O(( n / k) × h ) to O(3n / k) ,about 3 / h .

Keyword: Hierarchical Routing、Cluster、Gateway 、MANETs

1.緒論
1.1 研究背景
1.2 研究動機與目的
2.相關研究
2.1 DSDV演算法
2.2 AODV演算法
2.3 HSR 演算法
2.4 DDR演算法
2.5 HARP 演算法
3.多層式閘道路由協定
3.1 FIST-LEVEL CLUSTERING （ ZONE CREATING ）
3.2 HIGHER-LEVEL CLUSTERING
3.3 PATH DISCOVERY
3.4 PACKET DELIVERY
3.5 PATH RECOVERY
3.6 MGRP 範例
3.7 MGRP 演算法
4.研究結果
5.結論
6.參考文獻

〔1〕S. Corson and J. Macker, “Mobile Ad hoc Networking （MANET）: Routing Protocol Performance Issues and Evaluation Considerations,” RFC 2501, January 1999.
〔2〕E. M. Royer and C-K. Toh, “A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks,” IEEE Personal Communications, pp. 46-55, April 1999.
〔3〕C.Siva Ram Murthy and B.S.Manoj, “Ad Hoc Wireless network Architectures and Protocol,” PRENCE HALL PTR, 2004.
〔4〕C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing （DSDV） for Mobile Computers,” in proceedings of the SIGCOMM 1994 Conference on Communications Architectures, Protocols and Applications, pp. 234-244, August 1994.
〔5〕C. E. Perkins and E. M. Royer, “Ad-hoc On-Demand Distance Vector Routing,” in proceedings of 2nd IEEE Workshop Mobile Computing System And Applications, pp. 90-100, February 1999.
〔6〕Na. Nikaein, H. Labiod, and C. Bonnet, “DDR-distributed dynamic routing algorithm for mobile ad hoc networks,” in proceedings of the MobiHOC 2000. IEEE, pp. 19–27, Augest 2000.
〔7〕Na. Nikaein, Christian Bonnet and Neda Nikaein, ”Hybrid Ad Hoc Routing Protocol-HARP,” in proceedings of IST 2001:International Symposiumon Telecommunications, September 2001.
〔8〕R. S. Sisodia, B. S. Manoj, and C. Siva Ram Murthy, “A Preferred Link-Based Routing Protocol for Ad Hoc Wireless Networks,” Journal of Communications and Networks, vol. 4, no. 1, pp. 14-21, March 2002.
〔9〕T. H. Clausen, G. Hansen, L. Christensen, and G. Behrmann, “The Optimized Link State Routing Protocol, Evaluation Through Experiments and Simulation,” in proceedings of IEEE Symposium on Wireless Personal Mobile Communications 2001, September 2001.
〔10〕B. S. Manoj, R. Ananthapadmanabha, and C. Siva Ram Murthy, “Link life-Based Routing Protocol for Ad Hoc Wireless Networks,” in proceedings of IEEE IC-CCN 2001, pp. 573-576, October 2001.
〔11〕P. Sinha, R. Sivakumar, and V. Bharghavan, “CEDAR: A Core-Extraction Distributed Ad Hoc Routing Algorithm,” in proceedings of IEEE INFOCOM 1999, pp. 202-209, March 1999.
〔12〕P. S. Sisodia, I. Karthigeyan, B. S. Manoj, and C. Siva Ram Murthy, “A Preferred Link-Based Multicast Protocol for Wireless Mobile Ad Hoc Networks,” in proceedings of IEEE ICC 2003, vol. 3, pp. 2213-2217, May 2003.
〔13〕M. Joa-Ng and I-Tai Lu, “A peer-to-peer Zone-based two-level link state routing for mobile ad hoc networks,” IEEE on Selected Areas in Communications,vol. 17, no. 8, pp. 1415–1425, 1999.
〔14〕Z. J. Haas, “The Performance of Query Control Schemes for the Zone Routing Protocol,” IEEE/ACM Transactions on Networking, vol. 9, no. 4, pp. 427-438, August 2001.
〔15〕C.-C. Chiang, “Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel,” in proceedings of IEEE SICON 1997, pp. 197-211, April 1997.
〔16〕M. R. Pearlman and Z. J. Hass, “Determining the optimal configuration for Zone routing protocol,” IEEE Journal on Selected Areas in Communications, vol. 17, no. 8, pp. 1395–1414, 1999.
〔17〕C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing （DSDV） for Mobile Computers,” in proceedings of the SIGCOMM 1994 Conference on Communications Architectures, Protocols and Applications, pp. 234-244, August 1994.
〔18〕S. J. Lee, M. Gerla, and C. C. Chiang, “On-Demand Multicast Routing Protocol,” in proceedings of IEEE WCNC 1999, pp. 1298-1302, September 1999.
〔19〕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, vol. 17, no. 8, pp. 1369-1379, August 1999.
〔20〕I. Karthigeyan, B. S. Manoj, and C. Siva Ram Murthy, “Multicast Priority Scheduling Protocol for Ad Hoc Wireless Networks,” Technical Report, Department of Computer Science and Engineering, Indian Institute of Technology, Madras, India, January 2004.
〔21〕洪永城 “N-Stage Two-level pointer Forwarding with Caching Strategy for Location Management in PCS Networks,” 2003海峽兩岸財經高層論壇,南京, October 2003.
〔22〕E.M. Belding-Royer, ”Multi-Level Hierarchies for Scalable Ad hoc Routing,”W ireless Networks 9, pp.461–478, 2003.