Survey of clustering techniques for mobile ad hoc networks
Keywords:Mobile ad hoc networks, MANET, clustering, clusterhead
Clustering methods allow fast connection and also better routing and topology management of mobile ad hoc networks (MANET). In this paper a survey of clustering techniques for MANET is presented and some preliminary concepts for designing clustering algorithms are introduced. These concepts relate to network topology, routing schemes, graph partitioning and mobility algorithms. In addition, some of the most popular clustering techniques, such as Lowest-ID heuristic, Highest degree heuristic, DMAC (distributed mobility-adaptive clustering), and WCA (weighted clustering algorithm), among other techniques are described. The aim is to illustrate the main concepts concerning clustering techniques in mobile ad hoc networks.
Y. Fernandess, D. Malkhi. “K-clustering in wireless ad hoc networks”. Proceedings of the second ACM inter-national workshop on Principles of Mobile Computing. 2002. pp. 31-37.
J.P. Grady, A. McDonald. “State of the Art: Ad Hoc Networking”. M-Zones State of the Art Paper, SOA paper 05/03. 2003.
S. Sivavakeesar, G. Pavlou. “A Prediction-Based Cluste-ring Algorithm to achieve Quality of Service in Mulithop Ad Hoc Networks”. Proc. of the London Communications Symposium (LCS). 2002. pp. 157-160.
B. An, S. Papavassiliou. “A mobility-based clustering approach to support mobility management and multicast routing in mobile ad-hoc wireless networks”. International Journal of Network Management. Vol. 11. 2001. pp. 387-395.
C. Prehofer, C. Bettstetter. “Self organization in com-munication networks: Principles and design paradigms”. IEEE Communications Magazine. Vol. 43. Issue 7. 2005. pp. 78-85.
Y. P. Chen, A. L. Liestman, J. Liu. Ad Hoc and Sensor Networks, Wireless Networks and Mobile Computing. Clustering Algorithms for Ad hoc Wireless Networks. Vol. 2. Chapter 7: Nova Science Publishers, Hauppage NY, 2004. pp. 145-164.
J. Wu, J. Cao. “Connected k-hop clustering in ad hoc networks”. ICPP. 2005. pp 373-380.
I. Chatzigiannakis, S. Nikoletseas. “Design and analysis of an efﬁcient communication strategy for hierarchical and highly changing ad-hoc mobile networks”. Mobile Networks and Applications. Vol. 9. 2004. pp. 319-332.
M. Frodigh, P. Johansson, P. Larsson. “Wireless Ad Hoc Networking--The Art of Networking without a Net-work”. Ericsson Review. Vol. 77. 2000. pp. 248-263.
P. Krishna, N.H. Vaidya, M. Chatterjee, D.K. Pradhan. “A cluster-based approach for routing in dynamic net-works”. ACM SIGCOMM Computer Communication Review. 1997. pp. 49-65.
S. Srivastava, R. K. Ghosh. “Cluster based routing using a k-tree core backbone for mobile ad hoc networks”. Proceedings of the 6th international workshop on discrete algorithms and methods for mobile computing and communications. 2002. pp. 14-23.
Y.P. Chen, A. L. Liestman. “A zonal algorithm for clustering ad hoc networks”. International Journal of Foundations of Computer Science. Vol.14. 2003. pp. 305-322.
Y. Yi, M. Gerla, T. J. Kwon. “Efﬁcient ﬂooding in ad hoc networks: a comparative performance study”. Proc. of the IEEE International Conference on Communications (ICC). Vol. 2. 2003. pp. 1059-1063.
S. Sesay, Z. Yang, J. He. “A survey on mobile ad hoc wireless network”. Information Technology Journal. Vol. 3. 2004. pp. 168-175.
A. B. McDonald, T. F. Znati. “A mobility-based framework for adaptive clustering in wireless Ad Hoc networks”. IEEE Journal on Selected Areas in Communications. Vol. 17. 1999. pp. 1466-1487.
R. Rajaraman. “Topology control and routing in ad hoc networks: a survey”. SIGACT News, Vol. 33. 2002. pp. 60-73.
V. Kawadia, P. R. Kumar. “Power control and clustering in ad hoc networks”. INFOCOM 2003, Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. Vol.1. 2003. pp. 459-469.
L. Bao, J.J. Garcia-Luna-Aceves. “Topology management in ad hoc networks”. Proceedings of the 4th ACM international symposium on mobile ad hoc networking & computing. Vol. 9. 2003. pp. 129-140.
L. Wang and S. Olariu. “Cluster maintenance in mobile ad-hoc networks”. Cluster Computing. Vol. 8. 2005. pp. 111-118.
T. C. Hou, T. J. Tsai. “An Access-Based Clustering Protocol for Multihop Wireless Ad Hoc Networks”. IEEE J. Selected Areas Comm. Vol. 19. 2001. pp. 1201-1210.
I. Er and W. Seah. “Mobility-based d-hop clustering algorithm for mobile ad hoc networks”. IEEE Wireless Communications and Networking Conference. Vol. 4. 2004. pp. 2359-2364.
G. Lugano. “Clustering for hierarchical routing”. 2003.[Online]. Available: http://www.cs.helsinki.ﬁ/u/ﬂoreen/adhoc/lugano.pdf. Consultado julio de 2006.
R. Purtoosi, H. Taheri, A. Mohammadi, F. Foroozan. “A light-weight contention-based clustering algorithm for wireless ad hoc networks,” Computer and Information Technology (CIT ’04). 2004. pp. 627-632.
W. Lou, J. Wu. “An enhanced message exchange mechanism in cluster-based mobile ad hoc networks”. ISPA. 2004. pp. 223-232.
M. Gerla, J. Tsai. “Multicluster, mobile, multimedia radio network”. Wireless networks. Vol 1. 1995. pp. 255-265.
C.R. Lin, M. Gerla. “Adaptive clustering for mobile wireless networks”. IEEE Journal of Selected Areas in Communications. Vol. 15. 1997. pp. 1265-1275.
G. Chen, F. Nocetti, J. Gonzalez, and I. Stojmenovic, “Connectivity based k-hop clustering in wireless networ-ks”. Proceedings of the 35th Annual Hawaii International Conference on System Sciences. Vol. 7. 2002. pp. 188.3.
M. Marathe, H. Breu, H. Ravi, and D. Rosenkrantz. “Simple heuristics for unit disk graphs”. 1995. [Online]. Available: http://citeseer.ist.psu.edu/marathe95simple.html. Consultado Julio de 2006.
B. Clark, C. J. Colbourn, and D. S. Johnson. “Unit disk graphs”. Discrete Mathematics. Vol. 86. 1990. pp. 165-177.
K. M. Alzoubi, P.-J. Wan, and O. Frieder. “Weakly-con-nected dominating sets and sparse spanners in wireless ad hoc networks”. Proceedings of the 23rd International Conference on Distributed Computing Systems. 2003. pp. 96-104.
J.N. Al-Karaki, A.E. Kamal, R. Ul-Mustafa. “On the optimal clustering in mobile adhoc networks”. First IEEE Consumer Communications and Networking Conference (CCNC). 2004. pp. 71-76.
A. Ephremides, J.E. Wieselthier, D.J. Baker. “A design concept for reliable mobile radio networks with frequen-cy hoping signaling”. Proc. IEEE 75. 1987. pp. 56-73.
A. Parekh. “Selecting routers in ad hoc wireless net-works”. Proceedings of the SBT/IEEE International Telecommunications Symposium. 1994.
S. Basagni. “Distributed clustering for ad hoc networks”. Proc. ISPAN’99 Int. Symp. On Parallel Architectures, Algorithms, and Networks. 1999. pp. 310-315.
Y. P. Chen, A. L. Liestman. “Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks”. Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing. 2002. pp. 165-172.
D. Dubhashi, A. Mei, A. Panconesi, J. Radhakrishnan, A. Srinivasan. “Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons”. Proceedings of the Fourteenth ACM-SIAM Symposium on Discrete Algorithms, (SODA). 2003. pp. 717-724.
J. Habetha, B. Walke. “Fuzzy rule-based mobility and load management for self-organizing wireless networks”. International Journal of Wireless Information Networks. Vol. 9. 2002. pp. 119-140.
I., Hwang, C. Liu, C. Wang. “Link stability based clustering and routing in ad-hoc wireless networks using fuzzy ser theory”. International Journal of Wireless Information Networks. Vol. 9. 2002. pp. 201-212.
A.D. Amis, R. Prakash, T.H.P Vuong, D.T. Huynh. “Max-Min D-Cluster Formation in Wireless Ad Hoc Networks”. Proceedings of IEEE Conference on Computer Communications (INFOCOM). Vol. 1. 2000. pp. 32-41.
M. Chatterjee, S. K. Das, D. Turgut. “WCA: A Weighted clustering algorithm for mobile ad hoc networks”. Cluster Computing. Vol. 5. 2002. pp. 193-204.
A. B. McDonald, T. F. Znati. “Design and Simulation of a Distributed Dynamic Clustering Algorithm for Multimode Routing in Wireless Ad Hoc Networks”. SIMULATION. Vol. 78. 2002. pp. 408-422.
A. Gopalan, S. Dwivedi, T. Znati, B. McDonald. “On the Implementation and Performance of the (α, t) Protocol on Linux”. SIMULATION. Vol. 81. 2005. pp. 413-424.
P. Basu, N. Khan, T. D. C. Little. “A mobility based metric for clustering in mobile ad hoc networks”. Proceedings of the 21st International Conference on Distributed Computing Systems. 2001. pp. 413.
D. Turgut, S.K. Das, R. Elmasri, B. Turgut. “Optimizing clustering algorithm in mobile ad hoc networks using genetic algorithmic approach”. Global Telecommunications Conference, IEEE. Vol. 1. 2002. pp. 62-66.
D. Turgut, B. Turgut, R. Elmasri, T. V. Le. “Optimizing clustering algorithm in mobile ad hoc networks using simulated annealing”. Wireless Communications and Networking, IEEE. Vol. 3. 2003. pp.1492-1497.
C. Ji, Y. Zhang, S. Gao, P. Yuan, Z. Li. “Particle swarm optimization for mobile ad hoc networks clustering”. IEEE International Conference on Networking, Sensing and Control. Vol. 1. 2004. pp. 372-375.
C. Bettstetter. “The Cluster Density of a Distributed Clustering Algorithm in Ad Hoc Networks”. Proc. IEEE Intern. Conf. on Communications (ICC). Vol. 7. 2004. pp. 4336-4340.
C.-C. Chiang, H.-K. Wu, W. Liu, M. Gerla. “Routing in clustered multihop, mobile wireless networks with fading channel”. IEEE Singapore International Conference on Networks (SICON). 1997. pp. 197-211.
Y. -X. Wang, F. S. Bao. “An Entropy-based Weighted Clustering Algorithm and Its Optimization for Ad Hoc Networks”. 2006. [Online]. Available: http://forrest.bao.googlepages.com/WCA_ETS.pdf. Consultado diciembre de 2006.
K. Robinson, D. Turgut, M. Chatterjee. “An entropy-ba-sed clustering in mobile ad hoc networks”. Proceedings of the 2006 IEEE International Conference on Networking, Sensing and Control (ICNSC). 2006. pp. 1-5.
How to Cite
Revista Facultad de Ingeniería, Universidad de Antioquia is licensed under the Creative Commons Attribution BY-NC-SA 4.0 license. The material published in the journal can be distributed, copied and exhibited by third parties if the respective credits are given to the journal. No commercial benefit can be obtained and derivative works must be under the same license terms as the original work.