利用蟻群優化演算法解決隨建即連網路之多目標叢聚問題

隨著4G行動通訊協定的發表以及行動裝置的普及，無線隨意網路成了熱門的研究議題，這篇論文在研究如何解決隨建即連網路(Mobile Ad-hoc Networks)的叢聚(clustering)問題。由於隨建即連網路可以被快速的佈建，且受到地形的限制較少，因此已被廣泛地應用在不同的領域中。通訊協定是隨建即連網路的重要議題之一，但經過證實，無論是主動式路由(proactive routing scheme)而或是回應式路由(reactive routing scheme)在規模較大的隨建即連網路中都不能表現得很好，甚至是不能實行，叢聚(clustering)是目前最有效的解決方法，它試圖將資訊的流通集中在叢聚頭(cluster head)上，進而減少通訊時的規模，因此如何選出適合的叢聚頭中是在研究領域中一個非常重要的議題。此問題除了已被證明是NP-hard的問題，而且在選叢聚頭的過程中我們必須考慮多項因素，更是一個多目標的問題。我們結合了蟻群優化演算法和非支配(non-dominated)的概念來解決此問題，我們提出了叢聚矩陣編碼(clustering matrix encoding)，用來選擇適合的叢聚頭並決定屬於同個叢聚的成員，以及一個修復演算法來提升最佳解的效能，除此之外，我們也提出了一個叢聚保持機制來針對動態的環境，實驗果證實提出的演算法勝過許多知名的算法，並且有被實際應用的潛力。

關鍵字

隨建即連網路；蟻群優化演算法；多目標最佳化；網路叢聚問題

並列摘要

With the rise of the fourth generation (4G) communication standards and the growing usage of mobile computing devices, mobile ad hoc network becomes a hot topic and getting more and more attention in recent years. In this thesis, we address the clustering problem in mobile ad hoc network (MANET). Due to the convenient deployment and the flexibility for variety terrains, MANET has been widely used in various fields. Routing protocols are the most important issue of MANETs, however, it has been proved that both proactive and reactive routing schemes cannot perform well or even didn’t work in a large scale size of MANET, and clustering is the most efficient method to deal with it. Clustering leads a hierarchical structure, for each cluster a cluster head will be chosen for intra- and inter- communication. However clustering in MANET is NP-hard and needs to consider multiple objectives. In this thesis, we propose a Pareto-based ant colony optimization (ACO) algorithm to deal with this multiobjective optimization problem. We proposed a clustering matrix encoding to reflect the cluster selection and cluster formation without any bias and redundant solutions. A repair function is proposed for upgrading the quality of solutions. Apart from this, we also propose a mechanism to maintain the cluster structure for dynamic situations. The experiment results confirm that it outperforms several state-of-the-art algorithms and indicates the potential to be applied to practical use.

並列關鍵字

Mobile ad hoc network ； Ant colony optimization ； Multiobjective optimization ； Clustering problem.

參考文獻

[1] X.-M. Hu, J. Zhang, Y. Yu, C. H. S. H, Y.-L. Li, Y.-h. Shi, et al., "Hybrid genetic algorithm using a forward encoding scheme for lifetime maximization of wireless sensor networks," IEEE Transactions on Evolutionary Computation., vol. 14, pp. 766-781, 2010.

[2] C.-C. Lai, C.-K. Ting, and R.-S. Ko, "An effective genetic algorithm to improve wireless sensor network lifetime for large-scale surveillance applications," in IEEE Congress on Evolutionary Computation. , 2007, pp. 3531-3538.

[3] M. Younis and K. Akkaya, "Strategies and techniques for node placement in wireless sensor networks: A survey," Ad Hoc Networks, vol. 6, pp. 621-655, 2008.

[4] G. Wang, G. Cao, and T. La Porta, "Movement-assisted sensor deployment," IEEE Transactions on Mobile Computing, vol. 5, pp. 640-652, 2006.

[5] J.-A. Jiang, T.-S. Lin, C.-L. Chuang, C.-P. Chen, C.-H. Sun, J.-Y. Juang, et al., "A QoS-guaranteed coverage precedence routing algorithm for wireless sensor networks," Sensors, vol. 11, pp. 3418-3438, 2011.

國際替代計量

利用蟻群優化演算法解決隨建即連網路之多目標叢聚問題

全文下載

主題瀏覽