臺灣博碩士論文加值系統

在本篇研究中，我們提出一個在隨意型無線網路上面 “A Grid-Based Zone Routing Protocol”（簡稱：GZRP）的路由機制，主要用於改善在ZRP[8]當中效率(Performance)不足的問題，並可進一步提升路徑穩定性(Stability)。

在ZRP所提出的方法中，雖然混合了表格驅動(Table-Driven)和需求式(On-Demand)的路徑尋找方式來平衡兩者的缺點。但隨著網路密度的增加，各節點所需交換路由訊息的次數及儲存的路由表格項目則會增多，因而造成延展性 (Scalability) 不足的問題。

在ZRP的方法當目的節點在來源節點的區域(zone)外，此時負責轉送路徑挖掘封包(RREQ)的zone的邊緣節點(peripheral node)個數也影響了系統效能。因此，我們期望提出一個機制在結合GRID的概念下，來改善ZRP延展性的不足，並進一步利用GRID的地理資訊，選擇合適的邊緣節點讓系統效能再提升。

In this research, we proposed “A Grid-based Zone Routing Protocol” called GZRP for Ad-hoc networks. It improves Performance and Stability in ZRP[8] and uses the concept of “zone” in GRID[5] to reduce Delay time in some situation.

Although a hybrid method of “Table-Driven” and “On-Demand” was proposed in ZRP to balance two distinct disadvantages of the two above algorithms. However, it still exist the problem of the routing table of each node stored will increase with the density of network in ZRP. By the way, it will cause the scalable problem.

In ZRP, the number of peripheral nodes of a zone influences the overheads of establishing routing path when destination node is in the outside of the zone. Hence, we expect to propose the enhanced mechanism to overcome the scalable problem by the concept of GRID, and reduce the overheads when establish routing path by the geographic information of GRID.

摘要 II
誌謝 IV
目錄 V
圖目錄 VII
一、緒論 1
1.1研究背景 1
1.1 研究動機及目的 2
1.3 章節概要 3
二、相關研究討論 4
2.1表格驅動演算法 4
2.1.1 DSDV 4
2.2 需求演算法 5
2.2.1 AODV 5
2.3 混合式演算法 6
2.3.1 ZRP 6
2.4 地理位置相關演算法 8
2.4.1 LAR 8
2.4.2 GRID 10
三、以網格為基礎的區域路由協定 13
3.1 GRID的建立 13
3.2 GZRP基本架構 14
3.2.1 路由訊息的更新方式 15
3.2.2 路由路徑的建立 16
3.2.3利用地理特性進一步減少控制封包數量 17
四、系統實驗 21
4.1 系統實驗環境 21
4.1.1 實驗參數 21
4.2 模擬數據分析 22
4.2.1 節點數量與控制封包數量的關係 22
4.2.2 路徑長度比較 24
4.2.3 速度和控制封包數量的關係 25
4.2.4速度和路徑穩定度的關係 26
4.2.5 速度與平均傳輸時間的關係 27
五、結論 28
5.1 結論 28
參考文獻 29

[1]J. M. McQuillan, I. Richer, and E. C. Rosen. “The new routing algorithm for the Arpanet,” IEEE Trans. on Communication, COM-28(5), May 1980.
[2]Charles E, Perkins, Pravin Bhagwat, “Highly dynamic Destination-Sequenced Distance-vector routing (DSDV) for mobile computers.”, In Proc. ACM SIGCOMM Conference (SIGCOMM ’94), pages 234-244, August 1993
[3]Charles E. Perkins, Elizabeth M. Royer “Ad-hoc on-Demand Distance Vector Routing” Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, February 1999, pp. 90-100.
[4]Young-Bae Ko and Nitin H. Vaidya, "Location-Aided Routing(LAR) in Mobile Ad hoc Networks," ACM/Baltzer Wireless Networks (WINET) journal, Vol.6-4, 2000 - Extended version of the Mobicom''98 paper.
[5]Wen-Hwa Liao, Jang-Ping Sheu, Yu-Chee Tseng, “GRID: A Fully Location-Aware Routing Protocol for Mobile Ad hoc Networks.” Telecommunication Systems 18(1-3): 37-60 (2001)
[6]Josh Broch, David Johnson, and David Maltz, “The Dynamic Source Routing Protocol for Mobile Ad hoc Networks.”, http://www.ietf.org/internet-drafts/ draft-ietfmanet-dsr-01.txt, Dec 1998. IETF Internet Draft (workin progress).
[7]S.-C. M. Woo, S. Singh, “Scalable routing protocol for ad hoc networks.”, Wireless Networks, vol. 7, pp. 513 529, Sept. 2001.
[8]Z. J. Haas and M. R. Pearlman, "The Zone Routing Protocol (ZRP) for Ad Hoc Networks", Internet Draft draft-zonerouting-protocol-01.txt, Aug, 1998.
[9]T.-W. Chen and M. Gerla, “Global State Routing: A New Routing Scheme for Ad-hocWireless Networks,” In Proceedings of IEEE ICC’98, Atlanta, GA, Jun. 1998, pp. 171-175.
[10]Royer, E.M. , Chai-Keong Toh, “A review of current routing protocols for ad hoc mobile wireless networks.”, IEEE Personal Communication, Volume: 6 Issue: 2, April 1999.
[11]Xiaoyan Hong Kaixin Xu, Mario Gerla, “Scalable Routing Protocols for Mobile Ad Hoc Networks.”, IEEE Network Magazine, July-Aug, 2002.
[12]S, Murthy, J. J. Garcia- Luna-Aceves, “An Efficient Routing Protocol for Wireless Networks.” ACM Mobile Networks and Applications Journal, Special Issue on Routing in Mobile Communication Networks, pp. 183-197, October 1996.
[13]T. Camp, J. Boleng,B. Williams, L. Wilcox, W. Navidi, “Location Information Services in Mobile Ad Hoc Networks.”, In Proceedings of the IEEE International Conference on Communications(ICC),pages 3318-3324,New York City,New York, April 2002.
[14]B. Karp, H. T. Camp, “GPSR:Greedy perimeter stateless routing for wireless networks.” In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking(MOBICOM’00),page 243-254,2000.
[15]S.-Y. Ni, Y,-C. Tseng, Y.-S Chen, J.-P. Sheu, “The Broadcast Storm Problem in a Mobile Ad Hoc Network.”, In Proc. Of the 5th ACM/IEEE International Conference on Mobile Computing and Networking(MobiCom’99), Auguest, 1999.
[16]Y.-C.Tseng, T.-Y.Hsieh, “Fully power-aware and location-aware protocols for wireless multi-hop ad hoc networks.”, Proceedings 11th International Conference, 2002
[17]J. Moy, “OSPF Version 2”, RFC 2328, April, 1998.
[18]USCG Navigation Center GPS page Novembre 2003, http://www.navcen.uscg.gov/gps/default.htm
[19]E.D. Kaplan., “Understanding GPS: Principles and Applications.”, Artech House, Boston, MA, 1996.
[20]M. Takai, L. Bajaj, R, Ahuja, R. Bagrodia and M. Gerla, “GloMoSim: A Scalable Network Simulation Environment,” Technical report 990027, UCLA, Computer Science Department, 1999.
[21]R. Bagrodia, R. Meyer, M. Takai, Y. Chen, X. Zeng, J. Martin, and H.Y. Song, “PARSEC: A Parallel Simulation Environment for Complex Systems,” IEEE Computer, vol. 31, no. 10, Oct. 1998, pp.77-85.