Approximate consensus in the dynamic stochastic network with incomplete information and measurement delays. (English. Russian original) Zbl 1268.93132
Autom. Remote Control 73, No. 11, 1765-1783 (2012); translation from Avtom. Telemekh. 2012, No. 11, 6-29 (2012).
Summary: Consideration is given to the problem of achieving an approximate consensus in the decentralized stochastic dynamic network under incomplete information about the current states of the nodes, measurement delay, and variable structure of links. The solution is based on the protocol of local voting with non-vanishing steps. It is proposed to analyze dynamics of the closed network with the use of the method of averaged models which is extended to the systems with measurement delays. This method enables one to establish good analytical estimates of the permissible length of the step providing the desired accuracy of consensus and appreciably reduce the computational burden of simulation. The results obtained are applied to the analysis of the dynamics of the system of balancing the computer network loading.
MSC:
| 93E03 | Stochastic systems in control theory (general) |
| 93A14 | Decentralized systems |
| 93A15 | Large-scale systems |
| 93C41 | Control/observation systems with incomplete information |
Keywords:
measurement delay; stochastic dynamic network; computational burden; incomplete information; protocol of local voting; method of averaged models; nonvanishing stepsReferences:
| [1] | Fax, A. and Murray, R.M., Information Flow and Cooperative Control of Vehicle Formations, IEEE Trans. Automat. Control, 2004, vol. 49, pp. 1465–1476. · Zbl 1365.90056 · doi:10.1109/TAC.2004.834433 |
| [2] | Toner, J. and Tu, Y., Flocks, Herds, and Schools: A Quantitative Theory of Flocking, Phys. Rev. E, 1998, vol. 58, no. 4, pp. 4828–4858. · doi:10.1103/PhysRevE.58.4828 |
| [3] | Cortes, J. and Bullo, F., Coordination and Geometric Optimization via Distributed Dynamical Systems, SIAM J. Control Optim., 2005, vol. 44, no. 5, pp. 1543–1574. · Zbl 1108.37058 · doi:10.1137/S0363012903428652 |
| [4] | Paganini, F., Doyle, J., and Low, S., Scalable Laws for Stable Network Congestion Control, in Proc. 40th IEEE Conf. Decision Control, Orlando, 2001, vol. 1, pp. 185–190. · doi:10.1109/CDC.2001.980095 |
| [5] | Antal, C., Granichin, O., and Levi, S., Adaptive Autonomous Soaring of Multiple UAVs Using SPSA, in Proc. 49th IEEE CDC, Atlanta, GA, USA, December 15–17, 2010, pp. 3656–3661. |
| [6] | Jadbabaie, A., Lin, J., and Morse, A.S., Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules, IEEE Trans. Automat. Control, 2003, vol. 48, pp. 988–1000. · Zbl 1364.93514 · doi:10.1109/TAC.2003.812781 |
| [7] | Olfati-Saber, R. and Murray, R.M., Consensus Problems in Networks of AgentsWith Switching Topology and Time-Delays, IEEE Trans. Automat. Control, 2004, vol. 49, pp. 1520–1533. · Zbl 1365.93301 · doi:10.1109/TAC.2004.834113 |
| [8] | Ren, W. and Beard, R.W., Consensus Seeking in Multiagent Systems under Dynamically Changing Interaction Topologies, IEEE Trans. Automat. Control, 2005, vol. 50, no. 5, pp. 655–661. · Zbl 1365.93302 · doi:10.1109/TAC.2005.846556 |
| [9] | Huang, M., Stochastic Approximation for Consensus with General Time-Varying Weight Matrices, in Proc. 49th IEEE CDC, Atlanta, GA, USA, December 2010, pp. 7449–7454. |
| [10] | Agaev, R.P. and Chebotarev, P.Yu., Convergence and Stability in the Problems of Coordination of Characterstics (Review of the Basic Results), Upravlen. Bol’shimi Sist., 2010, vol. 30.1, pp. 470–505. |
| [11] | Ren, W. and Beard, R.W., Distributed Consensus in Multi-Vehicle Cooperative Control, Communication and Control Engineering Series, New York: Springer, 2007. |
| [12] | Tsitsiklis, J.N., Bertsekas, D.P., and Athans, M., Distributed Asynchronous Deterministic and Stochastic Gradient Optimization Algorithms, IEEE Trans. Automat. Control, 1986, vol. 31, no. 9, pp. 803–812. · Zbl 0602.90120 · doi:10.1109/TAC.1986.1104412 |
| [13] | Huang, M. and Manton, J.H., Coordination and Consensus of Networked Agents with Noisy Measurements: Stochastic Algorithms and Asymptotic Behavior, SIAM J. Control Optim., 2009, vol. 48, no. 1, pp. 134–161. · Zbl 1182.93108 · doi:10.1137/06067359X |
| [14] | Kar, S. and Moura, J.M.F., Distributed Consensus Algorithms in Sensor Networks with Imperfect Communication: Link Failures and Channel Noise, IEEE Trans. Signal Proc., 2009, vol. 57, no. 1, pp. 355–369. · Zbl 1391.94263 · doi:10.1109/TSP.2008.2007111 |
| [15] | Li, T. and Zhang, J.-F., Mean Square Average-Consensus under Measurement Noises and Fixed Topologies, Automatica, 2009, vol. 45, no. 8, pp. 1929–1936. · Zbl 1185.93006 · doi:10.1016/j.automatica.2009.04.017 |
| [16] | Rajagopal, R. and Wainwright, M.J., Network-based Consensus Averaging with General Noisy Channels, IEEE Trans. Signal Proc., 2011, vol. 59, no. 1, pp. 373–385. · Zbl 1392.94861 · doi:10.1109/TSP.2010.2077282 |
| [17] | Granichin, O., Vakhitov, A., and Vlasov, V., Adaptive Control of SISO Plant with Time-Varying Coefficients Based on Random Test Perturbation, in Proc. 2010 Am. Control Conf., Baltimore, MD, USA, June 30–July 2, 2010, pp. 4004–4009. |
| [18] | Vakhitov, A.T., Granichin, O.N., and Gurevich, L.S., Algorithm for Stochastic Approximation with Trial Input Perturbation in the Nonstationary Problem of Optimization, Autom. Remote Control, 2009, vol. 70, no. 11, pp. 1827–1836. · Zbl 1187.93141 · doi:10.1134/S000511790911006X |
| [19] | Granichin, O., Gurevich, L., and Vakhitov, A., Discrete-time Minimum Tracking Based on Stochastic Approximation Algorithm with Randomized Differences, in Proc. Combined 48th IEEE Conf. on Decision and Control and 28th Chinese Control Conf., December 16–18, 2009, Shanghai, P.R. China, pp. 5763–5767. |
| [20] | Borkar, V.S., Stochastic Approximation: A Dynamical Systems Viewpoint, New York: Cambridge Univ. Press, 2008. · Zbl 1159.60002 |
| [21] | Granichin, O.N., Stochastic Optimization and System Programming, Stokh. Optim. Informat., 2010, vol. 6, pp. 3–44. |
| [22] | Vakhitov, A.T., Granichin, O.N., and Pan’shenskov, M.A., Methods of Estimation of the Data Transmission Rate in Grid, Neirokomp’yutery: Razrabotka, Primenenie, 2009, no. 11, pp. 45–52. |
| [23] | Amelina, N.O., Balancing Node Loading in the Decentralized Computer Network under Incomplete Information, Neirokomp’yutery: Razrabotka, Primenenie, 2001, no. 6, pp. 56–63. |
| [24] | Amelina, N.O., Multiagent Technologies, Adaptation, Self-Organization, Achieving Consensus, Stokh. Optim. Informat., 2011, vol. 7, no. 1, pp. 149–185. |
| [25] | Amelina, N.O. and Fradkov, A.L., Method of Averaged Models in the Problem of Achieving Consensus, Stokh. Optim. Informat., 2012, vol. 8, no. 1, pp. 3–39. |
| [26] | Derevitskii, D.P. and Fradkov, A.L., TwoModels for Analysis of Dynamics of the Adaptation Algorithms, Autom. Remote Control, 1974, vol. 35, no. 1, part 1, pp. 59–67. |
| [27] | Derevitskii, D.P. and Fradkov, A.L., Prikladnaya teoriya diskretnykh adaptivnykh sistem upravleniya (Applied Theory of the Discrete Adaptive Control Systems), Moscow: Nauka, 1981. · Zbl 0518.93001 |
| [28] | Ljung, L., Analysis of Recursive Stochastic Algorithms, IEEE Trans. Automat. Control, 1977, no. 4, pp. 551–575. · Zbl 0362.93031 |
| [29] | Gerencser, L., A Representation Theorem for the Error of Recursive Estimators, SIAM J. Control Optim., 2006, vol. 44, no. 6, pp. 2123–2188. · Zbl 1139.93036 · doi:10.1137/S0363012991217421 |
| [30] | Kushner, H.J., Approximation and Weak Convergence Methods for Random Processes, with Application to Stochastic Systems Theory, Boston: MIT Press, 1984. · Zbl 0551.60056 |
| [31] | Kushner, H.J. and Clark, D.S., Stochastic Approximation Methods for Constrained and Unconstrained Systems, New York: Springer, 1978. · Zbl 0381.60004 |
| [32] | Ljung, L. and Soderstrom, T., Theory and Practice of Recursive Identification, Boston: MIT Press, 1983. |
| [33] | Fradkov, A.L., Continuous-time Averaged Models of Discrete-Time Stochastic Systems: Survey and Open Problems, in Proc. IEEE CDC-50, 2011, Orlando, USA, pp. 2076–2081. |
| [34] | Friedrich, T.A., Sauerwald, T.B., and Vilenchik, D.C., Smoothed Analysis of Balancing Networks, Random Struct. Algorithms, 2011, vol. 39, no. 1, pp. 115–138. · Zbl 1223.68019 · doi:10.1002/rsa.20341 |
| [35] | Li, H., Load Balancing Algorithm for Heterogeneous P2P Systems Based on Mobile Agent, in Proc. ICEICE 2011, 2011, pp. 1446–1449. |
| [36] | Kechadi, M.-T. and Savvas, I.K., Dynamic Task Scheduling for Irregular Network Topologies, Parallel Comput., 2005, vol. 31, no. 7, pp. 757–776. · doi:10.1016/j.parco.2005.04.007 |
| [37] | Katueva, Ya.V., Balancing Load of Nonsymmetrical Computer System at Handling the Tasks of Stochastic Estimation, Informatika Sist. Upravlen., 2006, no. 2(12), pp. 88–93. |
| [38] | Kostenetskii, P.S., Lepikhov, A.V., and Sokolinskii, L.V., Technologies of Parallel Database Systems for Hierarchical Multiprocessor Environments, Autom. Remote Control, 2007, vol. 68, no. 5, pp. 847–860. · Zbl 1161.68423 · doi:10.1134/S0005117907050116 |
| [39] | Li, Y. and Lan, Z., A Survey of Load Balancing in Grid Computing, in Proc. Int. Symp. Comput. Inf. Sci. (CIS04), 2004, Shanghai, China, pp. 280–285. |
| [40] | Gilly, K., Juiz, C., and Puigjaner, R., An Up-To-Date Survey in Web Load Balancing, World Wide Web, 2011, vol. 14, no. 2, pp. 105–131. · doi:10.1007/s11280-010-0101-5 |
| [41] | Sim, K.M. and Sun, W.H., Ant Colony Optimization for Routing and Load-Balancing: Survey and New Directions, IEEE Trans. Syst. Man, Cybern.-Part A: Syst. Humans, 2003, vol. 33, no. 5, pp. 560–572. · doi:10.1109/TSMCA.2003.817391 |
| [42] | Dzhunusov, I.A. and Fradkov, A.L., Synchronization in Networks of Linear Agents with Output Feedbacks, Autom. Remote Control, 2011, vol. 72, no. 8, pp. 1615–1627. · Zbl 1235.93009 · doi:10.1134/S0005117911080029 |
| [43] | Networks of Interacting Machines: Production Organization in Complex Industrial Systems and Biological Cells, Armbruster, D., Mikhailov, A.S., and Kaneko, K., Eds., World Scientific: Singapore, 2005. · Zbl 1110.90001 |
| [44] | Glashenko, A., Inozemtzev, S., Grachev, I., and Skobelev, P., Magenta Technology: Case Studies of Magenta i-Scheduler for Road Transportation, in Proc. Int. Conf. Autonom. Agents Multi Agent Syst. (AAMAS-6), Hawaii, 2007, pp. 1385–1392. |
| [45] | Amelina, N., Lada, A., Maiorov, I., et al., Study of the Models of Freight Traffic Organization with the Use of Multiagent System of Adaptive Realtime Planning of Trucks, Probl. Upravlen., 2011, no. 6, pp. 31–37. |
| [46] | Gikhman, I.I. and Skorokhod, A.V., Stokhasticheskie differentsial’nye uravneniya (Stochastic Differential Equations), Kiev: Naukova Dumka, 1968. · Zbl 0557.60041 |
| [47] | Bernshtein, S.N., Stokhasticheskie uravneniya v konechnykh raznostyakh i stokhastickie differentsial’nye uravneniya (Stochastic Finite-ifferences Equations and Stochastic Differential Equations), Moscow: Nauka, 1964, vol. 4, pp. 484–542. |
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.
