×

Distributed optimisation and control of graph Laplacian eigenvalues for robust consensus via an adaptive multilayer strategy. (English) Zbl 1366.93013

Summary: Functions of eigenvalues of the graph Laplacian matrix \(\mathbf L\), especially the extremal non-trivial eigenvalues, the algebraic connectivity \(\lambda_2\) and the spectral radius \(\lambda_n\), have been shown to be important in determining the performance in a host of consensus and synchronization applications. In this paper, we focus on formulating an entirely distributed control law for the control of edge weights in an undirected graph to solve a constrained optimization problem involving these extremal eigenvalues.
As an objective for the distributed control law, edge weights must be found that minimize the spectral radius of the graph Laplacian, thereby maximizing the robustness of the network to time delays under a simple linear consensus protocol. To constrain the problem, we use both local weight constraints that weights must be non-negative, and a global connectivity constraint, maintaining a designated minimum algebraic connectivity. This ensures that the network remains sufficiently well connected.
The distributed control law is formulated as a multilayer strategy, using three layers of successive distributed estimation. Adequate timescale separation between the layers is of paramount importance for the proper functioning of the system, and we derive conditions under which the distributed system converges as we would expect for the centralized control or optimization system to converge.

MSC:

93A14 Decentralized systems
93B35 Sensitivity (robustness)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
93A13 Hierarchical systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Olfati-Saber, Consensus problems in networks of agents with switching topology and time-delays, IEEE Transactions on Automatic Control 49 (9) pp 1520– (2004) · Zbl 1365.93301
[2] Olfati-Saber, Consensus and cooperation in networked multi-agent systems, Proceedings of the IEEE 95 (1) pp 215– (2007) · Zbl 1376.68138
[3] Wen, Consensus in multi-agent systems with communication constraints, International Journal of Robust and Nonlinear Control 22 (2) pp 170– (2012) · Zbl 1244.93018
[4] Wan, The impact of multi-group multi-layer network structure on the performance of distributed consensus building strategies, International Journal of Robust and Nonlinear Control 23 (6) pp 653– (2013) · Zbl 1273.93010
[5] Huang, Generic behavior of master-stability functions in coupled nonlinear dynamical systems, Physical Review E 80 (3) pp 036204-1-036204– (2009)
[6] Pecora, Master stability functions for synchronized coupled systems, Physical Review Letters 80 (10) pp 2109– (1998)
[7] Comellas, Synchronizability of complex networks, Journal of Physics A: Mathematical and Theoretical 40 (17) pp 4483– (2007) · Zbl 1189.90030
[8] Sundararaman, Clock synchronization for wireless sensor networks: a survey, Ad hoc networks 3 (3) pp 281– (2005) · Zbl 05387768
[9] He, Sats: secure average-consensus-based time synchronization in wireless sensor networks, IEEE Transactions on Signal Processing 61 (24) pp 6387– (2013) · Zbl 1394.94222
[10] Dörfler, Synchronization in complex oscillator networks and smart grids, Proceedings of the National Academy of Sciences 110 (6) pp 2005– (2013) · Zbl 1292.94185
[11] Zhao, Consensus-based energy management in smart grid with transmission losses and directed communication, IEEE Transactions on Smart Grid PP (99) pp 1–
[12] De Gennaro MC Jadbabaie A Decentralized control of connectivity for multi-agent systems 45th IEEE Conference on Decision and Control IEEE San Diego, USA 2006 3628 3633
[13] Zavlanos, Distributed connectivity control of mobile networks, IEEE Transactions on Robotics 24 (6) pp 1416– (2008) · Zbl 1370.93181
[14] Fiedler, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal 23 (2) pp 298– (1973) · Zbl 0265.05119
[15] Boyd, Convex optimization of graph Laplacian eigenvalues, Proceedings of the International Congress of Mathematicians 3 pp 1311– (2006) · Zbl 1100.05063
[16] Kim, On maximizing the second smallest eigenvalue of a state-dependent graph Laplacian, IEEE Transactions on Automatic Control 51 (1) pp 116– (2006) · Zbl 1366.05069
[17] Simonetto, Constrained distributed algebraic connectivity maximization in robotic networks, Automatica 49 (5) pp 1348– (2013) · Zbl 1337.93011
[18] Zavlanos, Graph-theoretic connectivity control of mobile robot networks, Proceedings of the IEEE 99 (9) pp 1525– (2011)
[19] Schuresko, Distributed motion constraints for algebraic connectivity of robotic networks, Journal of Intelligent and Robotic Systems 56 (1-2) pp 99– (2009) · Zbl 1203.68271
[20] Wang, Connectivity maintenance and distributed tracking for double-integrator agents with bounded potential functions, International Journal of Robust and Nonlinear Control 25 (4) pp 542– (2015) · Zbl 1312.93013
[21] Yang, Decentralized estimation and control of graph connectivity for mobile sensor networks, Automatica 46 (2) pp 390– (2010) · Zbl 1205.93106
[22] Satici AC Poonawala HA Eckert H Spong MW Connectivity preserving formation control with collision avoidance for nonholonomic wheeled mobile robots International Conference on Intelligent Robots and Systems (IROS) IEEE Tokyo, Japan 2013 5080 5086
[23] Kempton L Herrmann G di Bernardo M Adaptive weight selection for optimal consensus performance 53rd Annual Conference on Decision and Control IEEE Los Angeles, USA 2014 2234 2239
[24] Qu, Cooperative control with distributed gain adaptation and connectivity estimation for directed networks, International Journal of Robust and Nonlinear Control 24 (3) pp 450– (2014) · Zbl 1285.93009
[25] Bertrand A Moonen M Topology-aware distributed adaptation of Laplacian weights for in-network averaging 21st European Signal Processing Conference (EUSIPCO 2013) IEEE 2013 1 5
[26] Donetti, Optimal network topologies: expanders, cages, ramanujan graphs, entangled networks and all that, Journal of Statistical Mechanics: Theory and Experiment 2006 (08) pp P08007, 1– (2006)
[27] Gorochowski, Evolving enhanced topologies for the synchronization of dynamical complex networks, Physical Review E 81 (5) pp 056212, 1– (2010)
[28] Liu, Synchronization of dynamical networks by network control, IEEE Transactions on Automatic Control 57 (6) pp 1574– (2012) · Zbl 1369.93034
[29] Jalili M Rad AA Rewirings based on the eigenvectors of the Laplacian matrix for enhancing synchronizability of dynamical networks 7th IEEE International Conference on Industrial Informatics IEEE 2009 588 593
[30] Hoppensteadt, On systems of ordinary differential equations with several parameters multiplying the derivatives, Journal of Differential Equations 5 (1) pp 106– (1969) · Zbl 0167.08204
[31] Horn, Matrix Analysis (2012)
[32] De Abreu, Old and new results on algebraic connectivity of graphs, Linear algebra and its applications 423 (1) pp 53– (2007) · Zbl 1115.05056
[33] Mesbahi, Graph Theoretic Methods in Multiagent Networks (2010) · Zbl 1203.93001
[34] Münz, Delay robustness in consensus problems, Automatica 46 (8) pp 1252– (2010) · Zbl 1204.93013
[35] Lewis, Convex analysis on the hermitian matrices, SIAM Journal on Optimization 6 (1) pp 164– (1996) · Zbl 0849.15013
[36] Freeman RA Yang P Lynch KM Stability and convergence properties of dynamic average consensus estimators Proceedings of the 45th IEEE Conference on Decision and Control San Diego, USA 2006
[37] Boyd, Convex Optimization (2004)
[38] Lax, Linear Algebra and Its Applications (2007)
[39] Bertsekas, Nonlinear Programming (1999)
[40] Guckenheimer, Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields 42 (2013)
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.