隨著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.

摘要 i
ABSTRACT ii
CONTENTS iii
LIST OF FIGURES 1
LIST OF TABLES 3
Chapter 1 Introduction 4
1.1 Motivation 4
1.2 Problem Description 8
1.3 Contribution 10
1.4 Organization 11
Chapter 2 Literature Review 12
2.1 Concerned Objectives 12
2.1.1 Single Objective Clustering Algorithms 12
2.1.2 Aggregated Objective Clustering Algorithms 15
2.1.3 Multiple Objectives Clustering Algorithms 20
2.2 Encoding Scheme 22
2.2.1 Random Permutation Encoding 23
2.2.2 Bit String Encoding 25
2.3 Decoding Scheme 28
2.3.1 Neighbor Based Decoding 28
Chapter 3 Clustering Algorithm for Mobile Ad Hoc Networks 31
3.1 Preliminaries 31
3.1.1 Multiobjective Optimization 32
3.1.2 Ant Colony Optimization Algorithm (ACO) 33
3.2 Cluster Construction 35
3.2.1 Clustering Matrix Encoding 35
3.2.2 Matrix Based Decoding 40
3.3 Repair Function 42
3.4 Evaluation 45
3.5 Pheromone Update 47
3.6 Cluster Maintenance for Dynamic Situations 50
3.6.1 Node Insertion 51
3.6.2 Node Removal 52
Chapter 4 Experiments and Results 54
4.1 Benchmark Instances 54
4.2 Benchmark Algorithms 55
4.3 Parameter Setting 55
4.4 Performance Evaluation 57
4.4.1 Experiments in Different Node Sizes 57
4.4.2 Experiments in Different Weights 60
4.4.3 Experiments for Multi-Objectives Algorithms 62
4.4.4 Experiments in Dynamic Situations 64
4.5 Discussion 65
Chapter 5 Conclusions and Future Work 67
5.1 Conclusions 67
5.2 Future Work 68
REFERENCE 70

[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.
[6]K. Pandey and A. Swaroop, "A comprehensive performance analysis of proactive, reactive and hybrid MANETs routing protocols," International Journal of Computer Science Issues (IJCSI), vol. 8, 2011.
[7]Y. B. Ko and N. H. Vaidya, "Flooding-based geocasting protocols for mobile ad hoc networks," Mobile Networks and Applications, vol. 7, pp. 471-480, 2002.
[8]K. Xu, X. Hong, and G. M, "An ad hoc network with mobile backbones," in Conference on IEEE International Communications, 2002., 2002, pp. 3138-3143 vol.5.
[9]E. M. Belding&;#8208;Royer, "Hierarchical routing in ad hoc mobile networks," Wireless Communications and Mobile Computing, vol. 2, pp. 515-532, 2002.
[10]C. R. Lin and M. Gerla, "Adaptive clustering for mobile wireless networks," IEEE Journal on Selected Areas in Communications., vol. 15, pp. 1265-1275, 1997.
[11]J. Y. Yu and P. H. J. Chong, "A survey of clustering schemes for mobile ad hoc networks," IEEE Communications Surveys and Tutorials, vol. 7, pp. 32-48, 2005.
[12]T.-C. Hou and T.-J. Tsai, "A access-based clustering protocol for multihop wireless ad hoc networks," IEEE Journal on Selected Areas in Communications, vol. 19, pp. 1201-1210, 2001.
[13]A. Iwata, C.-C. Chiang, G. Pei, M. Gerla, and T.-W. Chen, "Scalable routing strategies for ad hoc wireless networks," IEEE Journal on Selected Areas in Communications, vol. 17, pp. 1369-1379, 1999.
[14]S. Basagni, I. Chlamtac, F. Andras, and E. Jonsson, "A generalized clustering algorithm for peer-to-peer networks," in Workshop on Algorithmic Aspects of Communication, 1997.
[15]J. Wu, M. Gao, and S. I., "On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks," in International Conference on Parallel Processing, 2001., 2001, pp. 346-354.
[16]S. Okdem, D. Karaboga, and C. Ozturk, "An application of Wireless Sensor Network routing based on Artificial Bee Colony Algorithm," in IEEE Congress on Evolutionary Computation (CEC), 2011, 2011, pp. 326-330.
[17]S. Guo and O. W. W. Yang, "Energy-aware multicasting in wireless ad hoc networks: A survey and discussion," Computer Communications, vol. 30, pp. 2129-2148, 6/30/ 2007.
[18]T. Kwon, M. Gerla, V. K. Varma, M. Barton, and T. R. Hsing, "Efficient flooding with passive clustering-an overhead-free selective forward mechanism for ad hoc/sensor networks," Proceedings of the IEEE, vol. 91, pp. 1210-1220, 2003.
[19]A. S. William and C. Y. Lee, "Mobile Cellular Telecommunications: Analog and Digital Systems," 1995.
[20]J. Wu and H. Li, "On calculating connected dominating set for efficient routing in ad hoc wireless networks," pp. 7-14, 1999.
[21]Y. P. Chen and A. L. Liestman, "Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks," pp. 165-172, 2002.
[22]T. Ohta, S. Inoue, and Y. Kakuda, "An Adaptive Multihop Clustering Scheme for Highly Mobile Ad Hoc Networks," pp. 293 - 300, 2003.
[23]A. D. Amis and R. Prakash, "Load-balancing clusters in wireless ad hoc networks," in 3rd IEEE Symposium on Application-Specific Systems and Software Engineering Technology, 2000. Proceedings., 2000, pp. 25-32.
[24]C. K. Ho and H. T. Ewe, "A hybrid ant colony optimization approach (hACO) for constructing load-balanced clusters," in IEEE Congress on Evolutionary Computation, 2005, pp. 2010-2017 Vol. 3.
[25]H. Cheng, S. Yang, and J. Cao, "Dynamic genetic algorithms for the dynamic load balanced clustering problem in mobile ad hoc networks," Expert Systems with Applications, vol. 40, pp. 1381-1392, 2013.
[26]C.-c. Chiang, H.-k. Wu, W. Liu, and M. Gerla, "Routing In Clustered Multihop, Mobile Wireless Networks With Fading Channel," pp. 197-211, 1997.
[27]A. Ephremides, J. E. Wieselthier, and D. J. Baker, "A design concept for reliable mobile radio networks with frequency hopping signaling," Proceedings of the IEEE, vol. 75, pp. 56-73, 1987.
[28]M. Gerla and J. T.-c. Tsai, "Multicluster, Mobile, Multimedia Radio Network," Journal of Wireless Networks, vol. 1, p. 11, 1995.
[29]H. Bagci and A. Yazici, "An energy aware fuzzy approach to unequal clustering in wireless sensor networks," Applied Soft Computing, vol. 13, pp. 1741-1749, 2013.
[30]J. Leu, M.-H. Tsai, T.-C. Chiang, and Y.-M. Huang, "Adaptive Power-Aware Clustering and Multicasting Protocol for Mobile Ad Hoc Networks," in Ubiquitous Intelligence and Computing. vol. 4159, J. Ma, H. Jin, L. Yang, and J. P. Tsai, Eds., ed: Springer Berlin Heidelberg, 2006, pp. 331-340.
[31]Y. Xu, Y. Mori, D. Estrin, and J. Heidemann, "Topology control protocols to conserve energy in wireless ad hoc networks," 2003.
[32]E.-B. Zouhair, M. Kadoch, B. L. Agba, F. Gagnon, and M. Bennani, "A Flexible Weight Based Clustering Algorithm in Mobile Ad hoc Networks," in International Conference on Systems and Networks Communications, 2006. ICSNC ''06. , 2006, pp. 50-50.
[33]S.-C. Lo, Y.-J. Lin, and J.-S. Gao, "A Multi-Head Clustering Algorithm in Vehicular Ad Hoc Networks," International Journal of Computer Theory &; Engineering, vol. 5, pp. 242-247, 2013.
[34]A. D. Amis, R. Prakash, T. H. P. Vuong, and D. T. Huynh, "Max-min d-cluster formation in wireless ad hoc networks," in INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. , 2000, pp. 32-41 vol.1.
[35]J. Y. Yu and P. H. J. Chong, "3hBAC (3-hop between adjacent clusterheads): a novel non-overlapping clustering algorithm for mobile ad hoc networks," in IEEE Pacific Rim Conference on Communications, Computers and signal Processing, 2003. PACRIM. , 2003, pp. 318-321 vol.1.
[36]M. Chatterjee, S. K. Das, and D. Turgut, "An on-demand weighted clustering algorithm (WCA) for ad hoc networks," in IEEE Global Telecommunications Conference, 2000. GLOBECOM ''00., 2000, pp. 1697-1701 vol.3.
[37]M. Chatterjee, S. K. Das, and D. Turgut, "WCA: A weighted clustering algorithm for mobile ad hoc networks," Cluster Computing, vol. 5, pp. 193-204, 2002.
[38]D. Turgut, S. K. Das, R. Elmasri, and B. Turgut, "Optimizing clustering algorithm in mobile ad hoc networks using genetic algorithmic approach," in IEEE Global Telecommunications Conference 2002, pp. 62-66 vol.1.
[39]D. Turgut, B. Turgut, R. Elmasri, and T. V. Le, "Optimizing clustering algorithm in mobile ad hoc networks using simulated annealing," in IEEE Wireless Communications and Networking, 2003, pp. 1492-1497 vol.3.
[40]S. Thirumurugan and E. G. D. P. Raj, "W-PAC: an efficient weighted partitioning around cluster head mechanism for ad hoc network," presented at the Proceedings of the Second International Conference on Computational Science, Engineering and Information Technology, Coimbatore UNK, India, 2012.
[41]W. Shahzad, F. Khan, and A. Siddiqui, "Clustering in mobile ad hoc networks using comprehensive learning particle swarm optimization (CLPSO)," in Communication and Networking. vol. 56, D. &;#346;l&;#281;zak, T.-h. Kim, A.-C. Chang, T. Vasilakos, M. Li, and K. Sakurai, Eds., ed: Springer Berlin Heidelberg, 2009, pp. 342-349.
[42]J. Kennedy and R. Eberhart, "Particle swarm optimization," in IEEE International Conference on Neural Networks, 1995. Proceedings., 1995, pp. 1942-1948 vol.4.
[43]U. K. Chakraborty, S. K. Das, and U. T. E. Abbott, "Clustering in mobile ad hoc networks with differential evolution," in IEEE Congress on Evolutionary Computation 2011, pp. 2223-2228.
[44]A. Bentaleb, S. Harous, and A. Boubetra, "A weight based clustering scheme for mobile ad hoc networks," pp. 161-166, 2013.
[45]R. P. Selvam and V. Palanisamy, "Stable and flexible weight based clustering algorithm in mobile ad hoc networks," International Journal of Computer Science and Information Technologies, vol. 2, pp. 824-828, 2011.
[46]X. Zhao, W. N. N. Hung, Y. Yang, and X. Song, "Optimizing communication in mobile ad hoc network clustering," Computers in Industry, vol. 64, pp. 849-853, 2013.
[47]K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEE Transactions on Evolutionary Computation., vol. 6, pp. 182-197, 2002.
[48]C.-W. Wu, T.-C. Chiang, and L.-C. Fu, "An ant colony optimization algorithm for multi-objective clustering in mobile ad hoc networks," presented at the IEEE Congress on Evolutionary Computation, 2014.
[49]C. A. C. Coello, G. T. Pulido, and M. S. Lechuga, "Handling multiple objectives with particle swarm optimization," IEEE Transactions on Evolutionary Computation., vol. 8, pp. 256-279, 2004.
[50]M. Dorigo and G. Di Caro, "Ant colony optimization: a new meta-heuristic," in Proceedings of the IEEE Congress on Evolutionary Computation, 1999.
[51]D. Costa and A. Hertz, "Ants can colour graphs," Journal of the operational research society, vol. 48, pp. 295-305, 1997.
[52]A. Colorni, M. Dorigo, V. Maniezzo, and M. Trubian, "Ant system for job-shop scheduling," Belgian Journal of Operations Research, Statistics and Computer Science, vol. 34, pp. 39-53, 1994.
[53]B. Bullnheimer, R. F. Hartl, and C. Strauss, "An improved ant System algorithm for thevehicle Routing Problem," Annals of operations research, vol. 89, pp. 319-328, 1999.
[54]M. Dorigo and L. M. Gambardella, "Ant colonies for the travelling salesman problem," BioSystems, vol. 43, pp. 73-81, 1997.
[55]R. S. Sutton and A. G. Barto, Introduction to reinforcement learning: MIT Press, 1998.
[56]M. Dorigo and T. St&;uuml;tzle, "Ant colony optimization: overview and recent advances," in Handbook of metaheuristics, ed: Springer, 2010, pp. 227-263.
[57]B. N. Clark, C. J. Colbourn, and D. S. Johnson, "Unit disk graphs," Annals of Discrete Mathematics, vol. 48, pp. 165-177, 1991.
[58]R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang, "Distributed topology control for power efficient operation in multihop wireless ad hoc networks," in Proceedings of IEEE INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies., 2001, pp. 1388-1397.
[59]F. Kuhn, R. Wattenhofer, and A. Zollinger, "Asymptotically optimal geometric mobile ad-hoc routing," in Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, 2002, pp. 24-33.
[60]F. Kuhn, R. Wattenhofer, Y. Zhang, and A. Zollinger, "Geometric ad-hoc routing: Of theory and practice," in Proceedings of the twenty-second annual symposium on Principles of distributed computing, 2003, pp. 63-72.