臺灣博碩士論文加值系統

隨意式無線網路(Ad Hoc wireless networks)是由許多任意移動的節點(mobile nodes)所形成的，與傳統無線網路不同的是，隨意式無線網路並沒有固定的控制中心或基地台可以管理網路內所有節點。由於網路上的節點總是任意且快速的移動，因此增加了隨意式網路管理上的困難。而可將所有網路節點區分為數個群組(clusters)，並且在每一個群組中選出一個節點為叢集標頭(cluster-head)以暫時扮演控制中心角色的叢集技術(cluster techniques)，可幫助隨意式無線網路解決節點管理及資源分配的問題。目前，許多的研究提出類似的技術，例如，利用最小節點識別碼(lowest-ID)或最高連結度(highest-connectivity)節點當成叢集標頭，雖然簡單但有叢集形成時不能移動的限制。為了解決這個問題，相關的研究已經提出，例如，適用於節點移動時的分散式動態可調式技術(DMAC)叢集技術、還有利用傳送功率控制(power control)叢集形成以節省系統發射功率的技術，以及單純考慮叢集半徑(radius)或跳躍次數(hop distance)來決定叢集架構的技術等等。各種不同的叢集技術有不同的優、缺點，也適用於不同的環境，之前的技術雖然解決了部分的問題，卻同時產生其他的問題。因此，在本文中我們提出一個新的動態配置叢集技術改善上述的問題，此技術是利用節點在某個間隔時間的位移及方向，決定是否要換手(handoff)到較接近的叢集。因為如此不但可兼顧節點移動時叢集變化的問題，還可以節省傳輸功率，使得形成的叢集更穩定。另一方面，我們亦考慮了叢集重疊的問題，若兩個以上的叢集重疊比例超過標準，其中一個必須重新形成，以節省網路資源。最後，撰寫模擬程式比較後，可證明我們提出的動態配置叢集技術可降低叢集標頭發生錯誤的機率，使網路穩定性更佳，並提供簡單的節省系統發射功率，以及利用模擬找出在不同的移動速率中具有最佳效能的重疊比例門檻。本論文貢獻在於高速移動的環境下，仍能達到以上所提的優點，並且找出在不同移動速率中的最佳重疊比例。

An Ad Hoc network is a temporary network formed by a collection of mobile nodes without the aid of any centralized coordinator. The Ad Hoc wireless network is adaptable to the highly dynamic topology resulted from the mobility; hence it is hard to predict and manage. Clustering is a technique to divide nodes that randomly moving in the network into several groups and also be used for controlling the spatial reuse of the shared channels. Moreover, it can reduce communication overhead and is easy to manage network resource in Ad Hoc wireless network. Many techniques have been proposed in previous researches. For example, Lowest-ID cluster algorithm and highest-connectivity algorithm are used to elect cluster-heads. Distributed and mobility-adaptive clustering (DMAC) is proposed for dealing with cluster nodes in highly dynamic network topology. In addition, the techniques of clustering based on power control are used to promote the system performance and elaborate the power economy. Other parameters, such as cluster radius, cluster dismissed distance and hop distance are also proposed as alternatives of traditional power transmission range to evaluate system performance.
In this paper, we propose a novel clustering technique, which is called Dynamic Allocation of Clustering Algorithm (DACA). The DACA algorithm is based on the moving displacement and direction in a certain amount of time to re-cluster or handoff nodes to the proper cluster dynamically, especially for the overlapping nodes between clusters. In addition, we also consider the optimal overlap percentage between clusters to reduce communication overhead. If the overlap percentage is larger than threshold, the overlapping nodes must be re-clustered. Therefore, DACA can enhance topology stability and mobility management, and it is power saving as well if the transmission power level is controlled. Comparing the existing algorithms with the proposed algorithms by evaluating system parameters, such as lowest-id cluster algorithm, highest-connectivity cluster algorithm, multi-hop with lowest-id clustering technique, and multi-hop with highest-connectivity clustering technique, DACA with lowest-id clustering technique, and DACA with highest-connectivity clustering technique, respectively. From the experiment results, it can demonstrate the feasibility and practicability characteristics of the proposed method. We conclude that our method has better performance especially in highly dynamic network, such as (i) reducing the dropping probability of cluster-head, (ii) increasing stabilities of the cluster structure in terms of the probability of nodes that change their roles, the probability of nodes that change clusters (handoff), (iii) providing simple power saving mechanism of cluster structure. Moreover, we also show the proper overlap percentage threshold with different various mobility speeds by computer simulation. Currently, there are many routing protocols are developed based on the existing cluster techniques. In the future, we also can further investigate the related works based on the well-developed DACA techniques.

中文摘要I
ABSTRACTIII
CONTENTV
LIST OF FIGURESVII
CHAPTER 1 INTRODUCTION1
1.1 Motivation1
1.2 Survey of related studies2
1.3 Proposed approach3
1.4 Organization of the paper3
CHAPTER 2 RELATED RESEARCHES錯誤! 尚未定義書籤。
2.1 Ad Hoc networks錯誤! 尚未定義書籤。
2.1.1 Major problems in Ad Hoc network錯誤! 尚未定義書籤。
2.2 Cluster-head election algorithms overview錯誤! 尚未定義書籤。
2.2.1 Lowest-ID cluster algorithm錯誤! 尚未定義書籤。
2.2.2 Highest-connectivity cluster algorithm錯誤! 尚未定義書籤。
2.3 Clustering techniques overview錯誤! 尚未定義書籤。
2.3.1 A GPS-based peer-to-peer hierarchical link state routing algorithm錯誤! 尚未定義書籤。
2.3.2 Distributed and mobility-adaptive clustering, DMAC錯誤! 尚未定義書籤。
2.3.3 Clustering with power control錯誤! 尚未定義書籤。
2.3.4 A clustering technique for large multihop mobile wireless networks錯誤! 尚未定義書籤。
2.3.5 Adaptive clustering for mobile wireless networks錯誤! 尚未定義書籤。
CHAPTER 3 DYNAMIC ALLOCATION OF CLUSTERING TECHNIQUE16
3.1 System model16
3.1.1 Description and definitions of notions16
3.1.2 Assumptions18
3.2 Implementation of Mobility Models19
3.3 Dynamic allocation of clustering algorithm20
3.3.1 Cluster setup20
3.3.2 Cluster maintenance21
3.3.2.1 Nodes changing location22
3.3.2.2 Cluster-head failure27
3.3.2.3 Clusters overlapping28
CHAPTER 4 SIMULATION31
4.1 Environment31
4.2 Performance Evaluations32
4.2.1 The dropping probability of cluster-head32
4.2.2 Network topology stability35
4.2.3 The probability of cluster reform41
4.2.4 Power saving mechanism43
4.2.5 The overlap percentage threshold of cluster46
CHAPTER 5 CONCLUSION49
REFERENCES51

References
[1]B. Awerbuch and D. Peleg, “Sparse Partions,” Proceedings of the 31st Annual Symposium on Fundations of Computer Science, pp. 503-513, 1990.
[2]S. Basagni, “Distributed clustering for Ad Hoc networks,” Parallel Architectures, Algorithms, and Networks, 1999. (I-SPAN '99) Proceedings. Fourth International Symposium on, pp. 310 —315, 1999.
[3]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. 1, No. 3, pp. 226-237, Jan. 1984.
[4]C. C. Chiang, H. K.Wu, W. Liuand and M. Gerla, “Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel,” in Proceedings of IEEE Singapore international Conference on Network (SICON97), 1997.
[5]Hwa-Chun Lin and Yung-Hua Chu, “A clustering technique for large multihop mobile wireless networks,” Vehicular Technology Conference Proceedings, 2000. VTC 2000-Spring Tokyo. 2000 IEEE 51st, Vol. 2, pp. 1545 -1549 vol.2, 2000.
[6]M.S. Corson, J.P. Macker, and G.H. Cirincione, “Internet-based mobile Ad Hoc networking,” IEEE Internet Computing Vol. 34, July-Aug., pp. 63-70, 1999.
[7]M. Gerla, G. Pei, and J.T.C. Tsai, “Multicluster, mobile, multimedia radio network,” ACM-Biltzer Journal of Wireless Network, Vol. 1, No. 3,pp. 255-265, 1995.
[8]Taek Jin Kwon and M. Gerla, “Clustering with power control,” Military Communications Conference Proceedings, 1999. MILCOM 1999. IEEE, Vol. 2, pp.1424 -1428 Vol.2, 1999.
[9]Hwa-Chun Lin and Yung-Hua Chu, ”A clustering technique for large multihop mobile wireless networks,” Vehicular Technology Conference Proceedings, 2000. VTC 2000-Spring Tokyo. 2000 IEEE 51st, Vol. 2, pp. 1545 -1549 Vol. 2, 2000.
[10]C.R. Lin, and M. Gerla, “Adaptive clustering for mobile wireless networks “ Selected Areas in Communications, IEEE Journal on Vol. 157, Sept. pp. 1265 —1275, 1997.
[11]M. Joa-Ng and I-Tai Lu, “A GPS-based peer-to-peer hierarchical link state routing for mobile Ad Hoc networks,” Vehicular Technology Conference Proceedings, 2000. VTC 2000-Spring Tokyo. 2000 IEEE 51st, Vol. 3, pp. 1752 -1756 Vol. 3, 2000.
[12]D. Peleg and E. Upfal, “A Trade-Off Between Space and Efficiency for Routing Tables,” Journal of the ACM, Vol. 36, No. 3, pp. 510-530, July 1989.
[13]C. V. Ramomoorthy, A. Bhide, and J. Srivastava, “Reliable Clustering Techniques for Large, Mobile Packet Radio Networks,” Proc. of IEEE INFOCOM’87, pp. 218-226, 1987.
[14]D.B. Johnson, “Scalable and Robust Internetwork Routing for Mobile Hosts,” ICDCS, June 1994.
[15]D.B. Johnson and D.A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,” Mobile Computing, edited by Tomasz Imielinski and Hank Korth, Chapter 5, Kluwer Academic Publishers, 1996.
[16]P. Krishna, M. Chatterjee, N.H. Vaidya and D.K. Pradhan, “A Cluster-based Approach for Routing in Ad-Hoc Networks,” Second USENIX Symposium on Mobile and Location-Independent Computing, 1995.