隨著大型行動隨意網路的出現，理想的路由機制必須要能夠因應網路拓樸的變化提供更好的延展性以及網路的通訊效能。混合式(Hybrid)路由協定，結合了主動式(Proactive/Table Driven)路由協定以及反應式(Reactive/On Demand)路由協定的優點，因此受到廣大的使用[3][10]。
在[1]一文中作者提出了Core Gateway Relay Routing Protocol(CG2R)混合式的路由協定。先經由 Cell Formation 找出每個節點所屬的 cell， cell 內任兩點皆在彼此的通訊範圍(即任兩點的距離為 one hop)。居於兩個 cell 以上的節點稱為 gateway，gateway 所屬的 cell 之集合稱為 super cell，再藉由 Core Gateway Determination 的程序從 gateway 中挑出 core gateway，使得網路中除了 core gateway 以外的節點距離其最近的 core gateway 皆為 one hop。由此，只要將封包送到所有的 core gateway 即可再經由一個 hop 送達網路中的所有節點。
本論文指出 CG2R 中經由 Cell Formation 所形成的 cell，無法確保任意兩點皆在彼此的通訊範圍內。經由分析，我們提出可讓 Cell Formation 正常運作之拓樸必須滿足的兩個條件，並模擬路由控制成本(Control Overhead)及網路拓樸改變(Topology Change)在不同的節點移動速度與不同網路密度下的變化，以及在不同網路密度下 CG2R 可正常運作的比率。

With the advent of large scale mobile ad-hoc networks, the routing protocol should be able to provide better scalability and performance with the change of the network topology. The hybrid routing protocols combine the best features of proactive/table-driven routing protocol and reactive/on-demand routing protocol, thus have led to widespread use[3][10].
Hung proposed a hybrid routing protocol called Core Gateway Relay Routing Protocol (CG2R)[1]. In the first of this protocol, each node is identified the cell it belongs to by the process of cell formation, such that, within the cell, any two nodes are one hop away from each other. The nodes that belong to two or more cells are called gateways; the set of cells that a gateway belongs to is defined as a super cell. Through the procedure of core gateway determination, certain gateways are determined as the core gateway. As the result, the nodes other than the core gateway nodes are all one hop away from the nearest core gateway node. Thus, as long as a packet is sent to all core gateways, it can be sent to all nodes in the network by one additional forwarding.
In this thesis, we point out that it cannot be ensured that two nodes in a cell are always one hop away from each other, so the CG2R cannot work properly in all network topology. By analysis, we present two conditions of topology which ensure that the process of cell formation can operate normally. In addition, we investigate the control overhead and the change of topology in variant nodes moving speed as well as nodes density, respectively. The ratio of network topology that CG2R can perform correctly is also simulated.

論文審定書 i
致謝 ii
摘要 iii
Abstract iv
目錄 v
圖次 vii
表次 ix
字母縮寫對照表 x
第一章 導論 1
1.1 簡介 1
1.1.1 無線網路通訊模式 1
1.1.2 無線網路架構 3
1.2 研究方向與相關背景 4
1.2.1 主動式路由協定 6
1.2.2 反應式路由協定 7
1.2.3 混合式路由協定 8
1.3 研究動機 9
1.4 論文架構 9
第二章 背景與相關研究 10
2.1 Core Gateway Relay Routing Protocol 10
2.2 功能及名詞釋義 10
2.3 路徑規劃 12
2.3.1 初始階段 12
2.3.2 路徑搜尋階段 12
2.3.3 路徑維護階段 13
2.3.4 選取Core Gateway演算法 15
2.4 選取Core Gateway例子 16
第三章 系統架構與運作 17
3.1 CG2R演算法分析 17
3.2 可正常運作CG2R拓樸例子 17
3.3 可正常運作CG2R的拓樸性質探討 22
3.3.1 Cell Formation 22
3.3.2 Maximal Complete Graph 23
3.3.3 拓樸依據節點與節點鄰居之分支度關係探討 24
3.4 可正常運作CG2R拓樸條件 27
第四章 模擬結果與討論 28
4.1 模擬工具介紹 28
4.2 模擬環境假設 30
4.3 模擬環境參數設定 31
4.4 模擬結果分析與討論 32
4.4.1 Control Overhead 32
4.4.2 Topology Change 34
4.5 可正常運作CG2R網路拓樸模擬 35
4.5.1 開發環境與模擬操作介面介紹 35
4.5.2 模擬架構 36
4.5.3 模擬結果 40
第五章 結論 41
參考文獻 42

[1] 洪基傑，「行動隨意網路中使用核心閘道為中繼點的混合式路由協定」，國立中山大學電機工程研究所，碩士論文，民國100年9月。
[2] L. Chen and W. B. Heinzelman, “QoS-aware routing based on bandwidth estimation for mobile ad hoc networks,” IEEE J. Selected Areas in Communication, vol. 23, no. 3, pp. 561-572, Mar. 2005.
[3] M. Chatterjee, S. K. Sas and D. Turgut, “A Weighted Clustering Algorithm (WCA) for Mobile Ad Hoc Networks,” Journal of Cluster Computing, vol.5, no.2, pp.193-204, Apr. 2002.
[4] C. C. Chiang, H. K. Wu, W. Liu, and M. Gerla, “Routing in clustered multihop mobile wireless networks with fading channel,” in Proc. IEEE Singapore International Conference on Networks (SICON), 1997, pp. 197-211.
[5] S. Choi and K. G. Shin, “A unified wireless LAN architecture for real-time and non-real-time communication services,” IEEE/ACM Trans. Networking, vol. 8, no. 1, pp. 44-59, Feb. 2000.
[6] D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,” Boston, MA: Kluwer Academic, 1996.
[7] M. Joa and I. T. Lu, “A peer-to-peer zone-based two-level link state routing for mobile ad hoc networks,” IEEE J. Selected Areas in Communications, vol. 17, no. 8, pp. 1415-1425, Aug. 1999.
[8] P. M. Jawandhiya, R. S. Mangrulkar, M. Atique, M.S. Ali, “A Novel Hybrid Routing Protocol for Mobile Adhoc Network,” International Journal of Advancements in Technology, vol 1, no 2, 2010.
[9] H. Liu and D. Raychaudhuri, “Label switched multi-path forwarding in wireless ad-hoc networks,” in Proc. IEEE International Conference on Pervasive Computing and Communications Workshops, pp. 248-252, Mar. 2005.
[10] B. S. Manoj, C. Siva Ram Murthy, Ad Hoc Wireless Networks Architectures and Protocols, NJ：Prentice Hall, May 2004.
[11] C. E. Perkins and P. Bhagwat, “Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers,” in Proc. ACM SIGCOMM, pp. 234-244, Sep. 1994.
[12] C. E. Perkins and E. M. Royer, “Ad hoc on-demand distance vector (AODV) routing,” IETF Internet draft, Jul. 2003.
[13] M. R. Pearlman and Z. J. Haas, “Determining the optimal configuration for the zone routing protocol,” IEEE J. Selected Areas in Communications, vol. 17, no. 8, pp. 1395-1414, Aug. 1999.
[14] V. D. Park and M. S. Corson, “A highly adaptive distributed routing algorithm for mobile wireless networks,” in Proc. IEEE INFOCOM, pp. 1405-1413, Apr. 1997.
[15] K. RahimiZadeh, “Design of a Cluster-based Routing for Integrated Cellular and Ad Hoc Networks,” in Proc. Communication Networks and Services Research Conference, pp. 422-424, May. 2009.
[16] The UCB/LBNL/VINT Network Simulator-ns (Version 2). VINT Project. Available: http://www.isi.edu/nsnam/ns/