隨意式網路的動態配置叢集技術

Dynamic Allocation of clustering Technique in Ad Hoc Wireless Network

王瓊英(Chiung-Ying Wang)

指導教授 ： 黃依賢 博士

元智大學/資訊學院/資訊工程學系/碩士(2001年)

摘要

隨意式無線網路(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.

並列關鍵字

Ad Hoc wireless network ； DACA algorithm ； cluster ； mobility management ； handoff ； system parameters

參考文獻

[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.

[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.