由於無線的通訊及缺乏基礎的網路建設，在無線特定網路上的路由協定主要有兩項需克服的問題：分別是動態的拓樸和頻寬限制。目前無線特定網路上所提出來的解決方式可概分為表格驅動以及需求驅動兩種。表格驅動的協定法必須透過大量的控制訊息來維護即時的路徑資訊；需求驅動的協定法雖然減少了控制訊息的數量，但是在路徑取得的效率上卻不夠即時。因此要達到快速取得路徑的目的，又要減少控制訊息的數量以便節省網路頻寬，是一個無線特定網路上重要的研究議題。
本論文在無線特定網路上提出一個k-hop叢集式的距離向量路由方法，此路由法將擴展最小識別碼演算法來形成k-hop之叢集，叢集與叢集間則透過叢集管理者利用距離向量的方式來交換路由資訊，由於經過叢集管理者來管理整個網路的路徑資訊，除了可以減少路由資訊封包的交換數量外，在路徑取得的效率上也獲得相當的改善。此路由協定曾利用模擬與其他協定比較，證明在路徑取得與資料封包的傳輸上會有較佳之效果。

Due to lack of fixed infrastructure, routing in wireless communications by ad hoc network generates two research problems: dynamic topologies and bandwidth- constrained. According to how they react to the link state changes, the routing protocols for ad hoc network can be roughly categorized into 2 kinds, there are table-driven and on-demand. A table-driven protocol has to use a lot of control message to maintain the real time routing information, while an on-demand protocol use less control messages but suffer from inefficient route obtaining. How to achieve the goals of quick route obtaining and use less control packets is an important issue of ad hoc network.
In this paper we present a k-hop cluster-based distance vector routing to meet the requirements in wireless ad hoc networks. This routing scheme uses the lowest ld algorithm to construct the k-hop cluster, and the distance vector routing method which keep in the head node of a k-hop cluster is used to maintain the routing information of the networks. This routing scheme we present not only can reduced the number of routing information packets, but also improve the efficiency of route obtaining. By simulation, compared with other protocols and we found that our routing scheme is more efficient, and use less number of routing information packets.

中文摘要
英文摘要
目錄
表目錄
圖目錄
第一章簡介………………………………………………………………………1
第二章背景知識…………………………………………………………………4
2.1 無線網路………………………………………………………………4
2.1.1 無線網路上的議題……………………………………………4
2.1.2 無線區域網路架構……………………………………………5
2.2 路由技術………………………………………………………………7
2.2.1 距離向量………………………………………………………8
2.2.2 連結狀態………………………………………………………9
2.3 行動特定網路上之路由協定…………………………………………10
2.3.1 表格驅動路由協定法…………………………………………11
2.3.2 需求驅動路由協定法…………………………………………11
2.3.3 混合式路由協定法……………………………………………12
2.3.4 位置協助路由協定法…………………………………………12
2.4 相關研究………………………………………………………………12
2.4.1 目的序號距離向量路由……………………………………13
2.4.2 k-hop叢集基礎動態來源路由………………………………14
2.5 分散式叢集形成演算法………………………………………………16
2.5.1 最小識別碼演算法……………………………………………17
2.5.2 最高連結性演算法……………………………………………18
第三章以k-hop叢集為基礎之距離向量路由協定……………………………21
3.1 k-hop叢集的形成……………………………………………………21
3.2 路由資訊的交換………………………………………………………24
3.2.1 叢集內資訊的交換……………………………………………24
3.2.2 叢集間資訊的交換……………………………………………25
3.2.2.1 閘道點的選出…………………………………………26
3.2.2.2 路由資訊的交換………………………………………27
3.3 路徑的取得及封包的傳送……………………………………………29
3.3.1 叢集內封包傳送………………………………………………29
3.3.2 叢集外封包傳送………………………………………………30
3.4 叢集的維護……………………………………………………………32
3.4.1 點的移動………………………………………………………32
3.4.2 叢集管理者的退休……………………………………………33
第四章效能分析…………………………………………………………………35
4.1 模擬環境設定…………………………………………………………35
4.2 效能評估………………………………………………………………36
4.2.1 叢集個數分析…………………………………………………36
4.2.2 路徑取得效率分析……………………………………………38
4.3 優缺點分析……………………………………………………………41

第五章結論………………………………………………………………………43
參考文獻……………………………………………………………………………44

[1]M. Conti, S. Giordano, ” Mobile ad-hoc networking,” System Sciences, 2001. Proceedings of the 34th Annual Hawaii International Conference on , Jan. 3-6, 2001.
[2]S.L. Wu, S.Y. Ni, Y.C. Tseng, J.P. Sheu, “Route maintenance in a wireless mobile ad hoc network”, Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, 2000 pp. 3015 —3024
[3]C.E. Perkins, P. Bhagwat, “Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers,” Proc. ACM SIGCOMM’94, pp. 234-244, Oct. 1994.
[4]D.B. Johnson, D.A. Maltz, “Dynamic source routing in ad hoc wireless networks in mobile computing,” T. Imielinski and H. Korth eds., page 153-181. Kluwer Academic, 1996.
[5]C.E. Perkins, E.M. Royer, “Ad-hoc on-demand distance vector routing,” Mobile Computing Systems and Applications, 1999. Proceedings. WMCSA ''99. Second IEEE Workshop on , 25-26 Feb. 1999.
[6]R. Dube, C.D. Rais, Kuang-Yeh Wang, S.K. Tripathi, “Signal stability-based adaptive routing (SSA) for ad hoc mobile networks,” Personal Communications, IEEE [see also IEEE Wireless Communications] , Volume: 4 Issue: 1 , Feb. 1997
[7]Z.J. Hass, “A new routing protocol for the reconfigurable wireless networks,” Universal Personal Communications Record, 1997. Conference Record., 1997 IEEE 6th International Conference on , Volume: 2 , 12-16 Oct. 1997.
[8]Kim Dongkyun, Ha Seokjae, Choi Yanghee, “K-hop cluster-based dynamic source routing in wireless ad-hoc packet radio network,” Vehicular Technology Conference, 1998. VTC 98. 48th IEEE , Volume: 1 , 18-21 May 1998
[9]B. Das, V. Bharghavan, “Routing in ad-hoc networks using minimum connected dominating sets,” Communications, 1997. ICC 97 Montreal, ''Towards the Knowledge Millennium''. 1997 IEEE International Conference on , Volume: 1 , 8-12 June 1997
[10]Y. Ko, N. Vaidya, "Location-aided routing (LAR) in mobile ad-hoc networks," In Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networks (MobiCom''98), Dallas, 1998.
[11]M. Mauve, A. Widmer, H. Hartenstein, “A survey on position-based routing in mobile ad hoc networks,” Network, IEEE , Volume: 15 Issue: 6 , Nov.-Dec. 2001.
[12]R. Sivakumar, P. Sinha, V. Bharghavan, “CEDAR: a core-extraction distributed ad hoc routing algorithm,” Selected Areas in Communications, IEEE Journal on , Volume: 17 Issue: 8 , Aug 1999
[13]M.S. Corson, M. Gerla, “A distributed routing algorithm for mobile wireless networks,” ACM/Baltzer Wireless networks, vol. 1, no. 1, Feb. 1995. pp. 61-81.
[14]M. Gerla, T. C. Tsai, “Multicluster, mobile, multimedia radio network,” ACM-Baltzer J. Wireless Networks, vol. 1, no 3, 1995, pp. 255-265.
[15]C.C. Chiang, H.K. Wu, W. Liu, M. Gerla, “Routing in cluster multihop, mobile wireless networks with fading channel,” Proc. IEEE Singapore International Conference on Network (SICON’97), 1997.
[16]Liu Kai, Li Jiandong, “Mobile cluster protocol in wireless ad hoc networks,” In Communication Technology Proceedings, 2000. WCC - ICCT 2000. International Conference on, volume 1, pages : 568 -573, 2000.
[17]P. Krishna, N. H. Vaidya, M. Chatterjee, and D. K. Pradhan, “A cluster-based approach for routing in dynamic networks,” ACM SIGCOMM Computer Communication Review, pages 49--65, April 1997.
[18]C. Hedrick, "Routing Information Protocol," RFC 1058, 1988.
[19]J. Moy, “OSPF Version 2,” RFC 1583, 1994.
[20]區域網路與高速網路, 黃能富著, 維科出版社. 1996.
[21]電腦網路─系統原理, Larry L. Peterson & Bruce S. David著, 潘育群、顧金福、邵喻美譯, 東華書局, 2001.
[22]IETF MANET Working Group. http://http://www.ietf.org/html.charters/manet-charter.html.
[23]The Network Simulator — ns-2. http://www.isi.edu/nsnam/ns/