Survey of clustering techniques for mobile ad hoc networks

Authors

  • Blanca Alicia Correa Universidad Pontificia Bolivariana
  • Laura Ospina Universidad Pontificia Bolivariana
  • Roberto Carlos Hincapié Universidad Pontificia Bolivariana

Keywords:

Mobile ad hoc networks, MANET, clustering, clusterhead

Abstract


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.

|Abstract
= 14 veces | PDF (ESPAÑOL (ESPAÑA))
= 18 veces|

Downloads

Download data is not yet available.

Author Biographies

Blanca Alicia Correa, Universidad Pontificia Bolivariana

Grupo de Investigación, Desarrollo y Aplicación en Telecomunicaciones e Informática (GIDATI). Facultad de
Ingeniería.

Laura Ospina , Universidad Pontificia Bolivariana

Grupo de Investigación, Desarrollo y Aplicación en Telecomunicaciones e Informática (GIDATI). Facultad de
Ingeniería.

Roberto Carlos Hincapié, Universidad Pontificia Bolivariana

Grupo de Investigación, Desarrollo y Aplicación en Telecomunicaciones e Informática (GIDATI). Facultad de
Ingeniería.

References

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 efficient 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. “Efficient flooding 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.fi/u/floreen/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.

Published

2014-03-31

How to Cite

Correa, B. A., Ospina , L., & Hincapié, R. C. (2014). Survey of clustering techniques for mobile ad hoc networks. Revista Facultad De Ingeniería Universidad De Antioquia, (41), 145–161. Retrieved from https://revistas.udea.edu.co/index.php/ingenieria/article/view/19022