臺灣博碩士論文加值系統

對於隨意無線網路 (ad hoc wireless networks) 上的路由選擇演算法 (routing algorithm) 的研究，近年來以反應式演算法最為熱門。反應式演算法的特點在於，節點不會主動維護到網路其他節點的路徑，只有在上層通訊協定或應用提出需求時，才設法求取所需的路徑。這樣的演算法由於不會浪費資源維護用不到的路徑，可以大幅減低所需的額外負擔。
反應式演算法主要的問題在於，路徑資訊並沒有辦法即時的更新，反應網路拓樸的變動。對於已經獲得的路徑，若是因為拓樸改變而失效，反應式演算法只能由資料封包傳送的錯誤才有辦法發現，發現以後又必須花費相當多的時間與頻寬去求取新的路徑資訊。這些因素造成的是大量封包漏失以及通訊暫時中斷，相當不利於多媒體應用的即時通訊需求。
混合式路由選擇演算法就是試圖結合兩種演算法優點而生的。這種演算法試圖主動維護鄰近範圍節點的路徑，並以反應式演算法尋找在該範圍以外節點的路徑。Zone Routing Protocol (ZRP)是一個混合式演算法的例子，但其主要目的在減少尋找路徑時的處理負擔 (control overhead)，而非頻寬負擔 (communication overhead)。事實上，ZRP在尋找路徑時所花費的頻寬往往比純粹反應式演算法還要多。
在本論文中，我們提出了一個基於底層叢集結構的混合式路由選擇演算法。這個演算法主動維護叢集內節點的拓樸與路由資訊，對於位於別的叢集的節點，就用反應式演算法求取路徑。如果資料封包傳送時發現路徑資訊已經過時，轉送該封包的節點可以利用叢集內的路由資訊試圖找到替代路徑以繼續傳送，減少封包漏失及找尋路徑的次數。另外，利用叢集結構找尋路徑，所需要的封包數目也可以大幅的減少。

A reactive routing protocol, such as the dynamic source routing protocol (DSR) [7], for ad hoc wireless networks initiates a route discovery to find a new routing path whenever a route error occurs. A hybrid proactive/reactive routing protocol such as the zone routing protocol (ZRP) [6] can be used to reduce the number of route discoveries that need to be initiated due to broken routes. To further reduce the number of route discoveries that need to be initiated due to broken routes, we propose a hybrid proactive/reactive source routing protocol based on the clustering technique developed in our previous work [8]. In the proposed hybrid proactive/reactive source routing protocol, a link state (proactive) routing protocol is used for the source node to find the path to a destination located within the cluster and an on-demand (reactive) routing protocol is employed to determine the path to a destination located beyond the cluster. When a route breaks, the node that detects the broken route tries to repair it using the link state information. A route discovery is initiated only if the broken route cannot be repaired. Our simulation results show that the proposed hybrid proactive/reactive source routing protocol initiates significantly smaller number of route discoveries due to broken routes than the zone routing protocol (ZRP) and the dynamic source routing (DSR) protocol.

中文摘要 I
Abstract II
Contents III
Chapter 1. Introduction 1
Chapter 2. The Clustering Technique 5
Chapter 3. The Cluster-Based Hybrid Proactive/Reactive Source Routing Protocol 8
A. Data structures 8
B. Intra-cluster routing 10
C. Inter-cluster routing 11
1) Route discovery 12
2) Route maintenance 16
Chapter 4. Protocol Options 18
A. Route Optimization within Cluster 18
B. Extended Searches for Alternate Paths 18
Chapter 5. Simulation and Results 20
Chapter 6. Conclusions 25
References 27

[1] A. D. Amis, R. Prakash, T.H. P. Vuong and D. T. Huynh, "Max-Min D-Cluster Formation in Wireless Ad Hoc Networks," in 2000 Proc. INFOCOM Conf., pp. 32–41.
[2] B. Awerbuch and D. Peleg, “Sparse Partitions,” Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990, pp. 503-513.
[3] D. J. Baker and A. Ephremides, "The Architectural Organization of a Mobile Radio Network via a Distributed Algorithm," IEEE Transactions on Communications, vol. COM-29(11), pp. 1694-1701, Nov. 1981.
[4] D. J. Baker, A. Ephremides, and J. A. Flynn, “The Design and Simulation of a Mobile Radio Network with Distributed Control,” IEEE Journal on Selected Areas in Communications, Vol. SAC-2, pp. 226-237, Jan. 1984.
[5] R. Dube, C. D. Rais, K. Y. Wang, and S. K. Tripathi, "Signal Stability-Based Adaptive Routing (SSA) for Ad Hoc Mobile Networks", IEEE Personal Communications Magazine, Vol. 4, No. 1, pp. 36-45, Feb. 1997.
[6] Z. J. Haas, "A New Routing Protocol for the Reconfigurable Wireless Networks," Proc. IEEE ICUPC'97, 1997, pp. 562-566.
[7] D. B. Johnson and D. A. Maltz, "Dynamic Source Routing in Ad Hoc Wireless Networks," Mobile Computing, edited by T. Imiclinski and H. Korth, Chapter 5, Kluwer Publishing Company, 1996, pp. 153-181.
[8] H. C. Lin and Y. H. Chu, "A Clustering Technique for Large Multihop Mobile Wireless Networks," Proc. of the IEEE Vehicular Technology Conference, Spring 1999, pp. 1545-1549.
[9] J. Moy, "OSPF Version 2," RFC-1247, July 1991.
[10] S. Murthy and J. J. Garcia-Luna-Aceves, "An Efficient Routing Protocol for Wireless Networks," ACM Mobile Networks and Applications, vol.1, no.2, pp.183-197, Oct. 1996.
[11] V. D. Park and M. S. Corson, "A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks," Proc. IEEE INFOCOM, April. 1997.
[12] C. E. Perkins and P. Bhagwat, "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers," Comp. Commun. Rev., pp.234-44, Oct.1994.
[13] C. E. Perkins and E. 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.
[14] C. V. Ramamoorthy, A. Bhide, and J. Srivastava, “Reliable Clustering Techniques for Large, Mobile Packet Radio Networks,” Proc. of IEEE INFOCOM, 1987, pp. 218-226.
[15] R. Ramanathan and M. Steenstrup, “Hierarchically-organized, Multihop Mobile Wireless Networks for Quality-of-service Support,” Mobile Networks and Applications, Vol. 3, pp. 101-119, 1998.
[16] C. K. Toh, "A Novel Distributed Routing Protocol to Support Ad-Hoc Mobile Computing," Proceedings of 15th IEEE Annual International Phoenix Conference on Computers and Communications, Mar. 1996, pp.480-486.