×

Markov chain analysis of self-organizing mobile nodes self-organizing mobile nodes. (English) Zbl 1245.68230

Summary: Self-organization of autonomous mobile nodes using bio-inspired algorithms in mobile ad hoc networks (manets) has been presented in earlier work of the authors. In this paper, the convergence speed of our force-based genetic algorithm (called fga) is provided through analysis using homogeneous Markov chains. The fga is run by each mobile node as a topology control mechanism to decide a corresponding node’s next speed and movement direction so that it guides an autonomous mobile node over an unknown geographical area to obtain a uniform node distribution while only using local information. The stochastic behavior of fga, like all ga-based approaches, makes it difficult to analyze the effects that various manet characteristics have on its convergence speed. Metrically transitive homogeneous Markov chains have been used to analyze the convergence of our fga with respect to various communication ranges of mobile nodes and also the number of nodes in various scenarios. The Dobrushin contraction coefficient of ergodicity is used for measuring convergence speed for Markov chain model of our fga. Two different testbed platforms are presented to illustrate effectiveness of our bio-inspired algorithm in terms of area coverage.

MSC:

68T40 Artificial intelligence for robotics
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
74S60 Stochastic and other probabilistic methods applied to problems in solid mechanics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Altshuler, Y., Bruckstein, A.M.: Static and expanding grid coverage with ant robots: Complexity results. Theor. Comput. Sci. 412(35), 4661–4674 (2011) · Zbl 1221.68245 · doi:10.1016/j.tcs.2011.05.001
[2] Altshuler, Y., Bruckstein, A.M., Wagner, I.A.: Swarm robotics for a dynamic cleaning problem. In: Swarm Intelligence Symposium, 2005. SIS 2005. Proceedings 2005 IEEE, pp. 209–216 (2005)
[3] Aytug, H., Bhattacharrya, S., Koehler, G.J.: A Markov chain analysis of genetic algorithms with power of 2 cardinality alphabets. Eur. J. Oper. Res. 96, 195–201 (1997) · Zbl 0924.90117 · doi:10.1016/S0377-2217(96)00121-X
[4] Baras, J.S., Tan, X.: Control of autonomous swarms using gibbs sampling. CDC. In: 43rd IEEE Conference on Decision and Control, vol. 5, pp. 4752–4757 (2004)
[5] Barolli, L., Koyama, A., Shiratori, N.: A qos routing method for ad-hoc networks based on genetic algorithm. In: DEXA ’03: Proceedings of the 14th International Workshop on Database and Expert Systems Applications, pp. 175–179 (2003)
[6] Boyd, S., Ghosh, A., Prabhakar, B., Shah, D.: Randomized gossip algorithms. IEEE Trans. Inf. Theory 5(6), 2508–2530 (2006) · Zbl 1283.94005 · doi:10.1109/TIT.2006.874516
[7] Camp, T., Boleng, J., Davies, V.: A survey of mobility models for ad hoc network research. Wirel. Commun. Mob. Comput. 2(5), 483–502 (2002) (Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications) · Zbl 05460801 · doi:10.1002/wcm.72
[8] Campos, C.A.V., de Moraes, L.F.M.: A Markovian model representation of individual mobility scenarios in ad hoc networks and its evaluation. EURASIP J. Wirel. Commun. Netw. 2007(35946), 1–14 (2007) · Zbl 05760890 · doi:10.1155/2007/35946
[9] Dobrushin, R.: Central limit theorem for nonstationary Markov chains ii. Teor. Veroyatnost Primenen, pp. 365–425 (1956)
[10] Dogan, C., Sahin, C.S., Uyar, M.U., Urrea, E.: Testbed for node communication in manets to uniformly cover unknown geographical terrain using genetic algorithms. In: NASA/ESA Conference on Adaptive Hardware and Systems, pp. 273–280 (2009)
[11] Dogan, C., Uyar, M.Ü., Urrea, E., Sahin, C.S., Hökelek, I.: Testbed implementation of genetic algorithms for self spreading nodes in manets. In: GEM, pp. 10–16 (2008)
[12] Gong, Y., Xu, W.: Machine Learning for Multimedia Content Analysis (Multimedia Systems and Applications). Springer New York, Inc., Secaucus, NJ, USA (2007)
[13] Guo, W., Gao, H., Chen, G., Cheng, H., Yu, L.: A pso-based topology control algorithm in wireless sensor networks. In: 5th International Conference on Wireless Communications, Networking and Mobile Computing, 2009 (WiCom ’09), pp. 1–4 (2009)
[14] Hekmat, R.: Ad-hoc Networks: Fundamental Properties and Network Topologies. Springer New York, Inc., Secaucus, NJ, USA (2006) · Zbl 1126.68004
[15] Heo, N., Varshney, P.: A distributed self spreading algorithm for mobile wireless sensor networks. In: IEEE Wireless Communications and Networking (WCNC) 3(1), pp. 1597–1602 (2003)
[16] Hokelek, I.: Analytic models and distributed robotics applications for mobile ad hoc networks. Ph.D. thesis, The Graduate Center of the City Univeristy of New York (2006)
[17] Hokelek, I., Uyar, M., Fecko, M.A.: A novel analytic model for virtual backbone stability in mobile ad hoc networks. Wirel. Netw. 14, 87–102 (2008) · Zbl 05537955 · doi:10.1007/s11276-006-7831-4
[18] Holland, J.: Adaptation in Natural and Artificial Systems. University of Michigan Press (1975) · Zbl 0317.68006
[19] Hong, P., Xing-Hua, W.: The convergence rate estimation of genetic algorithms with elitist. Chin. Sci. Bull. 42, 144–147 (1997) · doi:10.1007/BF03182789
[20] Horn, J.: Finite Markov chain analysis of genetic algorithms with niching. In: Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 110–117. Morgan Kaufmann (1993)
[21] Huang, C.F.: A Markov chain analysis of fitness proportional mate selection schemes in genetic algorithm. In: GECCO ’02: Proceedings of the Genetic and Evolutionary Computation Conference, p. 682. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2002)
[22] Huang, Z., Zhang, Z., Zhu, H., Ryu, B.: Topology control for wireless ad hoc networks: a genetic algorithm-based approach. In: First International Conference on Communications and Networking in China, ChinaCom ’06, pp. 1–5 (2006)
[23] Jarvis, J., Shier, D.: Graph-theoretic analysis of finite Markov chains. In: Shier, D.R., Wallenius, K.T. (eds.) Applied Mathematical Modeling: A Multidisciplinary Approach. CRC Press, Cambridge, MA, USA (1999)
[24] Jiangshe, Z., Zongben, X., Yee, L.: Global annealing genetic algorithm and its convergence analysis. Sci. in China Series E: Technol. Sci. 40, 414–424 (1997) · Zbl 0886.68114 · doi:10.1007/BF02919428
[25] Khanna, R., Liu, H., Chen, H.H.: Self-organisation of sensor networks using genetic algorithms. IJSNET 1(3/4), 241–252 (2006) · Zbl 05465739 · doi:10.1504/IJSNET.2006.012040
[26] Kotecha, K., Popat, S.: Multi objective genetic algorithm based adaptive qos routing in manet. In: Proc. of IEEE Congress on Evolutionary Computation, CEC2007, pp. 1423–1428 (2007)
[27] Lawler, G.F.: Introduction to Stochastic Process. Chapman and Hall, NY, USA (1955)
[28] Ma, X., Zhang, Q., Li, Y.: Genetic algorithm-based multi-robot cooperative exploration. In: IEEE International Conference on Control and Automation, ICCA 2007, pp. 1018–1023. ACM, Guangzhou, China (2007)
[29] Ming, L., Wang, Y., Yiu-Ming, Xidian, C.: On convergence rate of a class of genetic algorithms. In: Proc. of the World Automation Congress (WAC’06), pp. 1–6. Budapest,Hungary (2006)
[30] Misra, S., Woungang, I., Misra, S.C.: Guide to Wireless Ad Hoc Networks. Springer (2009) · Zbl 1159.68352
[31] Mitchell, M.: An Introduction to Genetic Algorithms. MIT Press, Boston, MA (1998) · Zbl 0906.68113
[32] Montana, D., Redi, J.: Optimizing parameters of a mobile ad hoc network protocol with a genetic algorithm. In: GECCO ’05: Proceedings of the 2005 Conference on Genetic and Evolutionary Computation, pp. 1993–1998. ACM, New York, NY, USA (2005)
[33] Nakama, T.: Markov chain analysis of genetic algorithms applied to fitness functions perturbed by multiple sources of additive noise. Studies in Computational Intelligence 149, 123–136 (2008)
[34] Nix, A.E., Vose, M.D.: Modeling genetic algorithms with Markov chains. Ann. Math. Artif. Intell. 5, 79–88 (1992) · Zbl 1034.68534 · doi:10.1007/BF01530781
[35] Othman, W., Amavasai, B.P., McKibbin, S., Caparrelli, F.: An analysis of collective movement models for robotic swarms. In: EUROCON, 2007. The International Conference on Computer as a Tool, pp. 2373–2380 (2007)
[36] Rudolph, G.: Convergence analysis of canonical genetic algorithms. IEEE Trans. Neural Netw. 5, 96–101 (1994) · doi:10.1109/72.265964
[37] Rudolph, G.: Local convergence rates of simple evolutionary algorithms with cauchy mutations. IEEE Trans. Evol. Comput. 1, 223–233 (1998)
[38] Rudolph, G., Xi, L.: Convergence rates of evolutionary algorithms for a class of convex objective functions. Control Cybern. 26, 375–390 (1997) · Zbl 0891.93089
[39] Sahin, C.S.: Design and performance analysis of genetic algorithms for topology control problems. Ph.D. thesis, The Graduate Center of the City Univeristy of New York (2010)
[40] Sahin, C.S., Gundry, S., Urrea, E., Uyar, M.U., Conner, M., Bertoli, G., Pizzo, C.: Convergence analysis of genetic algorithms for topology control in manets. In: Sarnoff Symposium, 2010 IEEE, pp. 1–5 (2010)
[41] Sahin, C.S., Gundry, S., Urrea, E., Uyar, M.U., Conner, M., Bertoli, G., Pizzo, C.: Markov chain models for genetic algorithm based topology control in manets. In: EvoApplications (2). Lecture Notes in Computer Science, pp. 41–50. Springer (2010)
[42] Sahin, C.S., Urrea, E., Uyar, M.U., Conner, M., Bertoli, G., Pizzo, C.: Design of genetic algorithms for topology control of unmanned vehicles. Special Issue of the Int. J. of Applied Decision Sciences on Decision Support Systems for Unmanned Vehicles. IJADS 3, 221–238 (2010) · doi:10.1504/IJADS.2010.036100
[43] Sahin, C.S., Urrea, E., Uyar, M.U., Conner, M., Hokelek, I., Bertoli, G., Pizzo, C.: Genetic algorithms for self-spreading nodes in manets. In: GECCO ’08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, pp. 1141–1142. ACM, New York, NY, USA (2008)
[44] Sahin, C.S., Urrea, E., Uyar, M.U., Conner, M., Hokelek, I., Bertoli, G., Pizzo, C.: Uniform distribution of mobile agents using genetic algorithms for military applications in manets. In: Military Communications Conference, 2008. MILCOM 2008. IEEE, pp. 1–7 (2008)
[45] Schmitt, F., Rothlauf, F.: On the importance of the second largest eigenvalue on the convergence rate of genetic algorithms. In: Proceedings of the 14th Symposium on Reliable Distributed Systems (2001)
[46] Suzuki, J.: A Markov chain analysis on simple genetic algorithms. IEEE Trans. Syst. Man Cybern. 4, 655–659 (1995) · doi:10.1109/21.370197
[47] Svennebring, J., Koenig, S.: Building terrain-covering ant robots: a feasibility study. Auton. Robots 16, 313–332 (2004) · Zbl 05390482 · doi:10.1023/B:AURO.0000025793.46961.f6
[48] Takéhiko, N.: Markov chain analysis of genetic algorithms in a wide variety of noisy environments. In: GECCO ’09: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, pp. 827–834. ACM, New York, NY, USA (2009) · Zbl 1238.60083
[49] Turgut, D., Das, S.K., Elmasri, R., Turgut, B.: Optimizing clustering algorithm in mobile ad hoc networks using genetic algorithmic approach. In: Prof. of the Global Telecommunications Conference (GLOBECOM) 2002, pp. 17–21. Taipei, Taiwan (2002)
[50] Urrea, E., Sahin, C.S., Uyar, M.U., Conner, M., Hokelek, I., Bertoli, G., Pizzo, C.: Bioinspired topology control for knowledge sharing mobile agents. Ad hoc Networks 7(4), 677–689 (2009) · Zbl 05511258 · doi:10.1016/j.adhoc.2008.03.005
[51] WeiXing, F., KeJun, W., XiuFen, Y., ShuXiang, G.: Novel algorithms for coordination of underwater swarm robotics. In: Mechatronics and Automation, Proceedings of the 2006 IEEE International Conference on, pp. 654–659 (2006)
[52] Winkler, G.: Image Analysis, Random Fields and Markov Chains Monte Carlo Methods. Springer Berlin Heidelberg (2006)
[53] Yen, Y.S., Chan, Y.K., Chao, H.C., Park, J.H.: A genetic algorithm for energy-efficient based multicast routing on manets. Comput. Commun. 31(4), 858–869 (2008) · doi:10.1016/j.comcom.2007.10.033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.