Abstract
In the last decade, numerous efforts have been devoted to design efficient algorithms for clustering the wireless mobile ad-hoc networks (MANET) considering the network mobility characteristics. However, in existing algorithms, it is assumed that the mobility parameters of the networks are fixed, while they are stochastic and vary with time indeed. Therefore, the proposed clustering algorithms do not scale well in realistic MANETs, where the mobility parameters of the hosts freely and randomly change at any time. Finding the optimal solution to the cluster formation problem is incredibly difficult, if we assume that the movement direction and mobility speed of the hosts are random variables. This becomes harder when the probability distribution function of these random variables is assumed to be unknown. In this paper, we propose a learning automata-based weighted cluster formation algorithm called MCFA in which the mobility parameters of the hosts are assumed to be random variables with unknown distributions. In the proposed clustering algorithm, the expected relative mobility of each host with respect to all its neighbors is estimated by sampling its mobility parameters in various epochs. MCFA is a fully distributed algorithm in which each mobile independently chooses the neighboring host with the minimum expected relative mobility as its cluster-head. This is done based solely on the local information each host receives from its neighbors and the hosts need not to be synchronized. The experimental results show the superiority of MCFA over the best existing mobility-based clustering algorithms in terms of the number of clusters, cluster lifetime, reaffiliation rate, and control message overhead.
Similar content being viewed by others
References
Akbari Torkestani, J., Meybodi, M.R.: Approximating the minimum connected dominating set in stochastic graphs based on learning automata. In: Proceedings of International Conference on Information Management and Engineering (ICIME 2009), Kuala Lumpur, Malaysia, April 3–5 (2009)
Akbari Torkestani, J., Meybodi, M.R.: Solving the minimum spanning tree problem in stochastic graphs using learning automata. In: Proceedings of International Conference on Information Management and Engineering (ICIME 2009) Kuala Lumpur, Malaysia, April 3–5 (2009)
Akbari Torkestani, J., Meybodi, M.R.: Clustering the wireless ad hoc networks: a distributed learning automata approach. J. Parallel Distrib. Comput. 70, 394–405 (2010)
Akbari Torkestani, J., Meybodi, M.R.: Weighted steiner connected dominating set and its application to multicast routing in wireless MANETs. Wireless Personal Communications (2010). doi:10.1007/s11277-010-9936-4
Akbari Torkestani, J., Meybodi, M.R.: A learning automata-based cognitive radio for clustered wireless ad-hoc networks. J. Netw. Syst. Manag. (2010, in press)
Akbari Torkestani, J., Meybodi, M.R.: An intelligent backbone formation algorithm in wireless ad hoc networks based on distributed learning automata. J. Comput. Netw. 54, 826–843 (2010)
Akbari Torkestani, J., Meybodi, M.R.: A new vertex coloring algorithm based on variable action-set learning automata. J. Comput. Inf. 29(3), 1001–1020 (2010)
Artail, H., Antoun, R., Fawaz, K.: CRUST: implementation of clustering and routing functions for mobile ad hoc networks using reactive tuple-spaces. Ad Hoc Netw. 7, 1064–1081 (2009)
Baker, D.J., Ephremides, A.: The architectural organization of a mobile radio network via a distributed algorithm. IEEE Trans. Commun. 29(11), 1694–1701 (1981)
Basagni, S.: Distributed clustering for ad-hoc networks. In: Proceedings of International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN’99), pp. 310–315 (1999)
Basu, P., Khan, N., Little, T.D.C.: Mobility-based metric for clustering in mobile ad-hoc networks. In: Workshop on Distributed Computing Systems, pp. 413–418 (2001)
Chatterjee, M., Das, S., Turgut, D.: WCA: a weighted clustering algorithm for mobile ad-hoc networks. Cluster Comput. 5, 193–204 (2002)
Chen, A., Cai, Z., Hu, D.: Clustering in mobile ad hoc network based on neural network. J. Cent. South Univ. Technol. 13(6), 699–702 (2006)
Elhdhili, M., Azzouz, L., Kamoun, F.: CASAN: clustering algorithm for security in ad hoc networks. Comput. Commun. 31, 2972–2980 (2008)
Er, I.I., Seah, W.K.G.: Clustering overhead and convergence time analysis of the mobility-based multi-hop clustering algorithm for mobile ad hoc networks. J. Comput. Syst. Sci. 72, 1144–1155 (2006)
Er, I., Seah, W.K.G.: Performance analysis of mobility-based D-hop (MobDHop) clustering algorithm for mobile ad-hoc networks. Comput. Netw. 50, 3375–3399 (2006)
Esnaashari, M., Meybodi, M.R.: Data aggregation in sensor networks using learning automata. Wirel. Netw. 16(3), 687–699 (2010)
Esnaashari, M., Meybodi, M.R.: Dynamic point coverage problem in wireless sensor networks: a cellular learning automata approach. J. Ad hoc Sens. Wirel. Netw. 10(2–3), 193–234 (2010)
Esnaashari, M., Meybodi, M.R.: A learning automata based scheduling solution to the dynamic point coverage problem in wireless sensor networks. Comput. Netw. (2010, to appear)
Garcia Nocetti, F., Solano Gonzalez, J., Stojmenovic, I.: Connectivity based k-hop clustering in wireless networks. Telecommun. Syst. 22(1–4), 205–220 (2003)
Gerla, M., Tsai, J.: Multicluster, mobile, multimedia radio network. ACM/Baltzer J. Wirel. Netw. 1(3), 255–265 (1995)
Ghosh, R., Basagni, S.: Mitigating the impact of node mobility on ad-hoc clustering. J. Wirel. Commun. Mob. Comput. 8, 295–308 (2008)
IEEE Computer Society LAN MAN Standards Committee: Wireless LAN Medium Access Protocol (MAC) and Physical Layer (PHY) specification, IEEE Standard 802.11-1997. The Institute of Electrical and Electronics Engineers, New York (1997)
Konstantopoulos, C., Gavalas, D., Pantziou, G.: Clustering in mobile ad-hoc networks through neighborhood stability-based mobility prediction. Comput. Netw. 52, 1797–1824 (2008)
Lin, C.R., Gerla, M.: Adaptive clustering for mobile wireless networks. IEEE J. Sel. Areas Commun. 15(7), 1265–1275 (1997)
Narendra, K.S., Thathachar, K.S.: Learning Automata: An Introduction. Prentice-Hall, New York (1989)
Palit, R., Hossain, E., Thulasiraman, P.: MAPLE: a framework for mobility-aware pro-active low energy clustering in ad-hoc mobile wireless networks. Wirel. Commun. Mob. Comput. 6, 773–789 (2006)
Shahzad, W., Aslam Khan, F., Basit Siddiqui, A.: Clustering in mobile ad hoc networks using comprehensive learning particle swarm optimization (CLPSO). Commun. Netw. 56, 342–349 (2009)
Thathachar, M.A.L., Harita, B.R.: Learning automata with changing number of actions. IEEE Trans. Syst. Man Cybern. SMG-17, 1095–1100 (1987)
Thathachat, M.A.L., Sastry, P.S.: A hierarchical system of learning automata that can learn the globally optimal path. Inf. Sci. 42, 743–766 (1997)
Wang, S.-C., Pan, H.-H., Yan, K.-Q., Lo, Y.-L.: A unified framework for cluster manager election and clustering mechanism in mobile ad hoc networks. Comput. Stand. Interfaces 30, 329–338 (2008)
Yang Yu, J., Chong, P.: An efficient clustering scheme for large and dense mobile ad hoc networks (MANETs). Comput. Commun. 30, 5–16 (2006)
Zhang, Y., Mee Ng, J., Ping Low, C.: A distributed group mobility adaptive clustering algorithm for mobile ad hoc networks. Comput. Commun. 32, 189–202 (2009)
Akbari Torkestani, J., Meybodi, M.R.: Learning automata-based algorithms for finding minimum weakly connected dominating set in stochastic graphs. Int. J. Uncertain. Fuzziness Knowl.-Based Syst. 18(6) (2010)
Akbari Torkestani, J., Meybodi, M.R.: A learning automata-based heuristic algorithm for solving the minimum spanning tree problem in stochastic graphs. J. Supercomput. (2010, in press)
Akbari Torkestani, J., Meybodi, M.R.: A cellular learning automata-based algorithm for solving the vertex coloring problem. J. Expert Syst. Appl. (2011, in press)
Akbari Torkestani, J., Meybodi, M.R.: Mobility-based multicast routing algorithm in wireless mobile ad hoc networks: a learning automata approach. J. Comput. Commun. 33(6), 721–735 (2010)
Akbari Torkestani, J., Meybodi, M.R.: An efficient cluster-based CDMA/TDMA scheme for wireless mobile ad-hoc networks: a learning automata approach. J. Netw. Comput. Appl. 33, 477–490 (2010)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Akbari Torkestani, J., Meybodi, M.R. A mobility-based cluster formation algorithm for wireless mobile ad-hoc networks. Cluster Comput 14, 311–324 (2011). https://doi.org/10.1007/s10586-011-0161-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10586-011-0161-z