Survey of Clustering Schemes in Mobile Ad hoc Networks

Abdelhak Bentaleb, Abdelhak Boubetra, Saad Harous

Department of Computer Science, University of Bachir el Ibrahimi, Bordj Bou Arreridj, Algeria.
Faculty of Information Technology, United Arab Emirates University, P.O Box 17551 Al Ain, UAE.

DOI: 10.4236/cn.2013.52B002                

Abstract

Mobile ad-hoc networks (MANETs) are a specific kind of wireless networks that can be quickly deployed without pre- existing infrastructures. They are used in different contexts such as collaborative, medical, military or embedded applications. However, MANETs raise new challenges when they are used in large scale network that contain a large number of nodes. Subsequently, many clustering algorithms have emerged. In fact, these clustering algorithms allow the structuring of the network into groups of entities called clusters creating a hierarchical structure. Each cluster contains a particular node called cluster head elected as cluster head according to a specific metric or a combination of metrics such as identity, degree, mobility, weight, density, etc. MANETs has drawbacks due to both the characteristics of the transmission medium (transmission medium sharing, low bandwidth, etc.) and the routing protocols (information diffusion, path finding, etc.). Clustering in mobile ad hoc networks plays a vital role in improving resource management and network performance (routing delay, bandwidth consumption and throughput). In this paper, we present a study and analyze of some existing clustering approaches for MANETs that recently appeared in literature, which we classify as: Identifier Neighbor based clustering, Topology based clustering, Mobility based clustering, Energy based clustering, and Weight based clustering. We also include clustering definition, review existing clustering approaches, evaluate their performance and cost, discuss their advantages, disadvantages, features and suggest a best clustering approach.

Keywords

Clustering; Mobile Ad hoc Networks; Routing Protocol

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	S. Corson, J. Macker., “Mobile Ad hoc Networking (MANET),”RFC 2501, 1999.
[2]	N. Chauhan, L. K. Awasthi, N. chand, V. Katiyar and A. Chug, “A Distributed Weighted Cluster Based Routing Protocol for Manets,” World Academy of Science, Engineering and Technology 75, 2001, pp.1167-1171.
[3]	B. A. Correa, R.C. Hincapie and Laura Ospina, “Survey on Clustering Techniques for Mobile Ad Hoc Networks,” Revista Facultad de Ingenierí，No. 41, 2007.
[4]	S. A. Ade and P.A. Tijare , “Performance Comparison of AODV, DSDV, OLSR and DSR Routing Protocols in Mobile Ad Hoc Networks,” International Journal of Information Technology and Knowledge Management, Vol. 2, 2010, pp. 545-548.
[5]	P. Suman, D. Bisen, P. Tomar, V. Sejwar and R. Shukla, “Comparative Study of Routing Protocols for Mobile Ad-Hoc Networks,” International Journal of Information Technology & Knowledge Management, 2009.
[6]	X. Hong, K. Xu, M. Gerla, “Scalable Routing Protocols for Mobile Ad Hoc Networks,” Onr Minuteman project, 2002.
[7]	B. Lee, C. Yu, S. Moh, “Issues in Scalable Clustered Network Architecture for Mobile Ad Hoc Networks,” Handbook of Mobile Computing, 2004.
[8]	B. Maqbool, M.A.Peer, “Classification of Current Routing Protocols for Ad Hoc Networks,” IJCA, 2010.
[9]	Y.Y. Su, S.F. Hwang, and C.R. Dow, “An EfficientCluster-Based Routing Algorithm in Ad Hoc Networks with Unidirectional Links,” Journal of Information Science and Engineering 24, 2008, pp.1409-1428.
[10]	R. Agarwal and M. Motwani, “Survey of Clustering Algorithms for MANET,” International Journal on Computer Science and Engineering ,Vol. 1, No. 2, 2009.
[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. No. 1, 2005, pp. 32–48. doi:10.1109/COMST.2005.1423333
[12]	A. Abbasi and M. F. Younis., “A Survey on Clustering Algorithms for Wireless Sensor Networks,” Computer Communications, Vol. 30, No. 14-15, 2007, pp. 2826-2841. doi:10.1016/j.comcom.2007.05.024
[13]	A. Amis, R. Prakash, D. Huynh and T. Vuong. “Max-Min D-Cluster Formation in Wireless Ad Hoc Networks,” Infocom, Vol. 1, 2000, pp. 32–41.
[14]	S. Chinara, S. Rath, “A Survey on One-Hop Clustering Algorithms in Mobile Ad Hoc Networks,” Journal of Network and Systems Management, Vol. 17, No. 1-2, 2009, pp. 183-207. doi:10.1007/s10922-009-9123-7
[15]	J. J.Yin Leu, M.H. Tsai, T. C. Chiang and Y. M. Huang "Adaptive Power-Aware Clustering and Multicasting Protocol for Mobile Ad Hoc Networks," 2006.
[16]	O. Younis and S. Fahmy “HEED: A Hybrid, Energy- Effcient, Distributed Clustering Approach for Ad Hoc Sensor Networks,” IEEE Transactions on Mobile Computing, Vol. 3, No. 4, 2004, pp. 366–379 doi:10.1109/TMC.2004.41
[17]	M. Anupama and B. Sathya-narayana “Survey of Cluster Based Routing Protocols in Mobile Ad hoc Networks,” International Journal of Computer Theory and Engineering, Vol. 3, No. 6, 2011.
[18]	N. Gupta, M. Shrivastava, A. Singh, “Cluster Based on Demand Routing Protocol for Mobile Ad Hoc Network,” IJERT, Vol. 1, No. 3, 2012.
[19]	H. Wu, Z. Zhong and L. Hanzo.” A Cluster-head Selection and Update Algorithm for Ad Hoc,” In IEEE Globecom, 2010.
[20]	A.Ephremides, J. E. Wieselthier and D.J. Baker. “A Design Concept for Reliable Mobile Radio Networks with Frequency Hopping Signaling,”IEEE, 1987, pp. 56-73.
[21]	M. Gerla and J.T. Tsai. “Multicluster, Mobile, Multimedia Radio Network. Wireless Networks,” 1995.
[22]	S. Basagni, “Distributed clustering for ad hoc networks,” 1999.
[23]	M. Chatterjee, S.K. Das, D. Turgut, “WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks,” Vol. 5, No. 2, 2002, pp. 193-204.
[24]	W. Choi, M. Woo, “A Distributed Weighted Clustering Algorithm for Mobile Ad Hoc Networks,” Advanced International Conference on Telecommunications, 2006.
[25]	C. Johnen and L.H. Nguyen, “Self-stabilizing weight- based clustering algorithm for ad hoc sensor networks,” ALGOSENSORS, Italy, Vol. 4240, 2006. pp. 83-94.
[26]	U.C. Kozat and L. Tassiulas, “Virtual Dynamic Backbone for Mobile Ad Hoc Networks,” ICC, 2001.
[27]	A. B. McDonald and T. Znat, “A Mobility-based Frame Work for Adaptive Clustering in Wireless Ad Hoc Networks,” IEEE Journal on Selected Areas in Communications,Vol. 17,No. 8, 1999, pp. 1466-1487. doi:10.1109/49.780353
[28]	M. Anupama and B. Sathyanarayana. “Survey of Cluster Based Routing Protocols in Mobile Ad hoc Networks,” International Journal of Computer Theory and Engineering, Vol. 3, No. 6, 2011.
[29]	S. J. Francis and E. B. Rajsingh, “Performance Analysis of Clustering Protocols in Mobile Ad hoc Networks,” Journal of Computer Science, 2008, pp. 192-204.
[30]	C.C. Chiang, H.K. Wu, W. Liu and M. Gerla., “Routing In Clustered Multihop, Mobile Wireless Networks With Fading Channel,” SICON, Singapore, 1997, pp. 197-212.
[31]	C. R. Lin and M. Gerla., “Adaptive Clustering for Mobile Wireless Networks,” IEEE Journal on Selected Areas in Communications, Vol. 15, No. 7, 1997, pp.1265-1275. doi:10.1109/49.622910
[32]	G. Chen, F. G. Nocetti, J. S. Gonzalez and I. Stojmenovic. “Connectivity Based k-Hop Clustering in Wireless Networks,” 5th HICSS, 2002.
[33]	O. Flauzac, B. S. Haggar and F. Nolot, “Self-stabilizing Clustering Algorithm for Ad Hoc Networks,” ICWMC, No. 24-29, 2009.
[34]	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,” IEEE PACRIM, 2003.
[35]	B. Guizani, B. Ayeb and A. Koukam., “Impact of Stability in Cluster Based Link State Routing Protocol for Self-Organizing Networks,” 7th ICWMC, 2011.
[36]	A. Ramalingam, S. Subramani and k. Perumalsamy. , “Associativity-based Cluster Formation and Cluster Management in Ad Hoc Networks,” HiPC, 2002.
[37]	F. Li, S. Zhang, X. Wang, X. Xue and H. Shen, “Vote- Based Clustering Algorithm in Mobile Ad Hoc Networks," International Conference on Networking Technologies, 2004.
[38]	P. Basu, N. Khan, and T.D.C. Little. “A Mobility Based Metric for Clustering in Mobile Ad Hoc Networks,” ICDCSW, 2001, pp. 413-418.
[39]	C. Konstantopoulos, D. Gavalas and G.Pantziou. “Clustering in Mobile Ad Hoc Networks through Neighborhood Stability-based Mobility Prediction,” 2008.
[40]	M. Ni, Z. Zhong and D. Zhao. “MPBC: A Mobility Prediction-Based Clustering Scheme for Ad Hoc Networks,” IEEE TVT, Vol. 60, No. 9, 2011.
[41]	A.H. Hussein, A.O. Abu Salem and S. Yousef., “A flexible Weighted Clustering Algorithm Based on Battery Power for Mobile Ad hoc Networks,” ISIE, 2008.
[42]	A. Fathi and H. Taheri. “Enhance Topology Control Protocol(ECEC) to Conserve Energy based clustering in Wireless Ad Hoc Networks,” 3rd IEEE ICCSIT, 2010.
[43]	Ya Xu, S. Bien, Y. Mori, J. Heidemann, D. Estrin, “Topology Control Protocols to Conserve Energy in Wireless Ad Hoc Networks,” CENS Technical Report , 2003.
[44]	Z. El-Bazzal, M. Kadoch, B.L. Agba, F. Gagnon and M. Bennani, “A Flexible Weight Based Clustering Algorithmin Mobile Ad hoc Networks,” International Conference on Systems and Networks Communications, 2006.
[45]	S. Adabi, S. Jabbehdari, A.M.Rahmani and Se. Adabi. “Sbca: Score Based Clustering Algorithm for Mobile Ad Hoc Networks,” the 9th ICYCS, 2008.
[46]	M.R Monsef, S. Jabbehdari and F. Safaei. “An Efficient Weight-Based Clustering Algorithm for Mobile Ad-hoc Networks,” Journal of Computing, Vol. 3, 2011.
[47]	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, 2011, pp. 824-828.