﻿ 群平衡化赋权有向图/无向图的分布式算法研究 Distributed Strategies for Group-Balancing General Weighted Directed/Undirected Graphs

Vol.05 No.03(2016), Article ID:18448,15 pages
10.12677/AAM.2016.53058

Distributed Strategies for Group-Balancing General Weighted Directed/Undirected Graphs

Fan Yang1, Junyan Yu1, Yulan Gao2, Mei Yu3, Jinliang Shao1

1School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu Sichuan

2National Key Laboratory of Science and Technology on Communications, University of Electronic Science and Technology of China, Chengdu Sichuan

3School of Electrical and Electronic Engineering, North China Electric Power University, Beijing

Received: Aug. 17th, 2016; accepted: Aug. 27th, 2016; published: Aug. 30th, 2016

ABSTRACT

A key problem of solving the consensus coordination control of multi-agent systems is to design appropriate protocols or algorithms which guarantee the agents reaching consensus. Although existing theoretical results have illustrated the balance conditions and the group-balance conditions are necessary when it comes to average consensus and group average consensus respectively, there are few results on how to balance and group-balance a general graph. In this paper, we design two distributed algorithm to group-balance directed and undirected graphs respectively, and prove the validity of the algorithms via both theoretical analysis and example illustrations.

Keywords:Multi-Agent Systems, Group Consensus, Distributed Algorithms, Group-Balance, Directed/Undirected Graphs

1电子科技大学，数学科学学院，四川 成都

2电子科技大学，通信抗干扰技术国际级重点实验室，四川 成都

3华北电力大学，控制与计算机工程学院，北京

1. 引言

2. 图理论及准备工作

3. 赋权有向图的群平衡化算法

A. 算法I

2) 计算(中所有点的群外邻接出权值和)， (中所有点的群外邻接出权值和)。如果，转3)；如果，转4)。

3) 由知，对于每个群，群内所有点的群外邻接出权值之和为零，如果群内每个点的群外邻接出权值都为零，则群内每个点的群外邻接出权值相等，平衡条件达到。为了达到此目的设计了(i)~(iii)。

(i) 在中选择有最大值的点，它的值表示为，在中选择有最小值的点

(ii) 找到的其中一条出边的其中一条出边的权值减去的权值加上

(iii) 置，转1)并重复以上迭代。

4) 以下(i)~(ii)为重新赋值。因为某个群中可能存在没有群外出邻居的点(点的群外出邻居是指与点的出边相关联并且与点不在同一个群内的点)，这样的点群外邻接出权值只能是零。在此情况下，要使此群内每个点的群外邻接出权值相等，则此群内所有点的群外邻接出权值之和必需为零。若图中每个点都有群外出邻居，假设在中有个点，在中有个点。如果群内每个点的群外邻接

(i) 如果，若中存在没有群外出邻居的点，让中某一点的某一出边的边权值减，重新计算，则；若中每个点至少有一个群外出邻居，则

(ii) 如果，若中存在没有群外出邻居的点，让中某一点的某一出边的边权值减，重新计算，则。若此时，算法转3)；若中每个点至少有一个群外出邻居，则

(iii) 令，如果对任意，有，此时，满足平衡条件(1)和(2)，则图达到群平衡，退出算法。

(iv) 在中选择有最大值的点，它的值表示为，在中选择有最小值的点

(v) 找到的其中一条出边的其中一条出边的权值减去的权值加上

(vi) 置，转1) 并重复以上迭代。

B. 算法有效性分析

1)值变为零；

2) 除了，其他点的值没有改变；

3)值增加了。

Figure 1. The weights of the edges in Example 1 and the initial values of and

Figure 2. Some changes of weights in Example 1 after the procedure 4)-v)

Figure 3. The weights of edges in Example 1 and the real-time values of and, when the graph reaches balance

4. 赋权无向图的群平衡化算法

4.1. 含有两个子图且子图间连通的赋权无向图的群平衡化

2) 计算。如果，转3)；如果，转4)。

3) 由知，对于每个群，群中所有点的群外邻接出权值之和为零，如果群内每个点的群外邻接出权值都为零，则群平衡条件达到，由此设计了(i)~(iii)。

(i) 在中选择有最大值的点，它的值表示为，在中选择有最小值的点

(ii) 找到一个从的无圈路(由奇数个点组成)。

，其中

(iii) 置，转1)并重复以上迭代。

4)中所有点的邻接出权值之和与中所有点的邻接出权值之和都为，假设在中有个点，

(i) 令。如果对任意，有，则此时，满足平衡条件(1)和(2)，则群平衡达到，退出算法。

(ii) 在中选择有最大值的点，它的值表示为，在中选择有最小值的点,。

(iii) 找到一个从无圈路， (由奇数个点组成)，其中

(iv) 置，转1)并重复以上迭代。

，如图5

4.2. 含有两个子图且子图间有s (s > 1)个连通分支的赋权无向图的群平衡化

1) 如果对每个连通分支，有，其中代表第个连通分支中所有点的值总和。对于每个连通分支，算法类似于4.1-3)，若每个连通分支达到群平衡，则此无向图达到群平衡。

2) 如果

Figure 4. The weights of the edges in Example 2 and the initial values of and

Figure 5. Some changes of weights in Example 2 after the procedure 4)-iii)

Figure 6. The weights of edges in Example 2 and the real-time values of and, when the graph reaches balance

3) 计算

4) 令是既在中也在第个连通分支中的点，其中

5) i) 如果，有(是第个连通分支中的点)，则对于每个连通分支，算法类似于4.1-4)，目的是每个连通分支达到群平衡。

ii) 如果，(是第个连通分支中的点)，让第个连通分支中某一边的边权值减，则重新计算(是第个连通分支中的点)，则(是第个连通分支中的点)。

。因此算法III不能平衡该图。下面验证此结论。

，如图8

i) 包含两个子图且子图间连通的赋权无向图；

ii) 满足为常数的包含两个子图且子图间不连通的赋权无向图；

5. 结论

Figure 7. The weights of the edges in Example 3 and the initial values of and

Figure 8. Some changes of weights in Example 3 after the procedure 5)-ii)

Figure 9. The graph in Example 3 cannot reach balance

Distributed Strategies for Group-Balancing General Weighted Directed/Undirected Graphs[J]. 应用数学进展, 2016, 05(03): 472-486. http://dx.doi.org/10.12677/AAM.2016.53058

1. 1. Olfati-Saber, R. and Murray, R.M. (2003) Consensus Protocols for Networks of Dynamic Agents. Proceedings of the American Con-trol Conference, Denver, 4-6 June 2003, 951-956.

2. 2. Olfati-Saber, R. and Murray, R.M. (2004) Consensus Problems in Networks of Agents with Switching Topology and Time Delay. IEEE Transactions on Automatic Control, 49, 1520-1533. http://dx.doi.org/10.1109/TAC.2004.834113

3. 3. Ren, W. and Bward, R.W. (2005) Consensus Seeking in Multi-Agent Systems under Dynamically Charging Interaction Topologies. IEEE Transactions on Automatic Control, 50, 655-661. http://dx.doi.org/10.1109/TAC.2005.846556

4. 4. Xiao, F. and Wang, L. (2006) State Consensus for Multi-Agent Systems with Switching Topologies and Time-Varying Delays. International Journal of Control, 79, 1277-1284. http://dx.doi.org/10.1080/00207170600825097

5. 5. Xiao, F. and Wang, L. (2008) Consensus Protocols for Discrete-Time Mul-ti-Agent Systems with Time-Varying Delays. Automatica, 44, 2577-2582. http://dx.doi.org/10.1016/j.automatica.2008.02.017

6. 6. Xiao, F. and Wang, L. (2008) Asynchronous Consensus in Conti-nuous-Time Multi-Agent Systems with Switching Topology and Time-Varying Delays. IEEE Transactions on Automatic Control, 53, 1804-1816. http://dx.doi.org/10.1109/TAC.2008.929381

7. 7. Xiao, F. and Wang, L. (2006) Consensus Problems of Multi-Agent Systems under Discrete Communication Structure. Proceedings of the IEEE Conference on Decision and Control, San Diego, 13-15 December 2006, 4289-4294. http://dx.doi.org/10.1109/CDC.2006.376956

8. 8. Xiao, F. and Wang, L. (2006) Consensus Behavior of Agents in Networked Systems under General Communication Topologies. Proceedings of the 2006 IEEE International Symposium on Intelligent Control, Munich, 4-6 October 2006, 862-867.

9. 9. Ren, W. and Atkins, E. (2007) Distributed Multi-Vehicle Coordinated Control via Local Information Exchange. International Journal of Robust and Nonlinear Control, 17, 1002-1033. http://dx.doi.org/10.1002/rnc.1147

10. 10. Xie, G.M. and Wang, L. (2007) Consensus Control for a Class of Networks of Dynamic Agents. International Journal of Robust and Nonlinear Control, 17, 941-959. http://dx.doi.org/10.1002/rnc.1144

11. 11. Lin, P. and Jia, Y.M. (2009) Consensus of Second-Order Discrete-Time Multi-Agent Systems with Non-Uniform Time-Delays and Dynamically Changing Topologies. Automatica, 45, 2154-2158. http://dx.doi.org/10.1016/j.automatica.2009.05.002

12. 12. Yu, W.W. and Chen, G. (2010) Second-Order Consensus for Mul-ti-Agent Systems with Directed Topologies and Nonlinear Dynamics. IEEE Transactions on Systems, Man, and Cybernetics Society, 40, 881-891.

13. 13. Sun, Y.G. and Wang, L. (2009) Consensus of Multi-Agent Systems in Directed Networks with Non-Uniform Time- Varying Delays. IEEE Transactions on Automatic Control, 54, 1607-1613. http://dx.doi.org/10.1109/TAC.2009.2017963

14. 14. Li, T. and Zhang, J.F. (2009) Mean Square Average-Consensus under Mea-surement Noises and Fixed Topologies. Automatica, 45, 1929-1936. http://dx.doi.org/10.1016/j.automatica.2009.04.017

15. 15. Zheng, Y.S. and Wang, L. (2012) Finite-Time Consensus of Hetero-geneous Multi-Agent Systems with and without Velocity Measurements. Systems and Control Letters, 61, 871-878. http://dx.doi.org/10.1016/j.sysconle.2012.05.009

16. 16. Zheng, Y.S. and Wang, L. (2012) Distributed Consensus of Heterogeneous Multi-Agent Systems with Fixed and Switching Topologies. International Journal of Control, 85, 1967-1976. http://dx.doi.org/10.1080/00207179.2012.713986

17. 17. Zheng, Y.S. and Wang, L. (2016) Consensus of Switched Multi-Agent Systems. IEEE Transactions on Circuits and Systems, 63, 314-318.

18. 18. Yu, J.Y. and Wang, L. (2009) Group Consensus of Mul-ti-Agent Systems with Undirected Communication Groups. Proceedings of the 7th Asian Control Conference, Hong Kong, 27-29 August 2009, 105-110.

19. 19. Yu, J.Y. and Wang, L. (2010) Group Consensus in Multi Agent Systems with Switching Topologies and Communication Delays. Systems & Control Letters, 59, 340-348. http://dx.doi.org/10.1016/j.sysconle.2010.03.009

20. 20. Yu, J.Y. and Wang, L. (2012) Group Consensus of Multi-Agent Systems with Directed Information Exchange. International Journal of Systems Science, 43, 334-348. http://dx.doi.org/10.1080/00207721.2010.496056

21. 21. Chen, Y. and Lv, J.H. (2011) On the Cluster Consensus of Discrete-Time Multi-Agent Systems. Systems & Control Letters, 60, 517-523. http://dx.doi.org/10.1016/j.sysconle.2011.04.009

22. 22. Qin, J.H. and Yu, C.B. (2013) Cluster Consensus Control of Generic Linear Multi-Agent Systems under Directed Topology with Acyclic Partition. Automatica, 49, 2898-2905. http://dx.doi.org/10.1016/j.automatica.2013.06.017

23. 23. Han, Y.J. and Yu, W.W. (2013) Cluster Consensus in Discrete-Time Networks of Multi-Agents with Inter-Cluster Nonlinear Inputs. IEEE Transactions on Neural Networks and Learning Systems, 24, 566-578. http://dx.doi.org/10.1109/TNNLS.2013.2237786

24. 24. Xie, D.M. and Liu, Q.L. (2014) Necessary and Sufficient Condition for Group Consensus of Multi-Agent Systems. Applied Mathematics and Computation, 243, 870-878. http://dx.doi.org/10.1016/j.amc.2014.06.069

25. 25. Tan, C. and Liu, G.P. (2011) Group Consensus of Networked Multi-Agent Systems with Directed Topology. Proceedings of the 28th IFAC World Congress, Milano, 28 August-2 September 2011, 8878-8883. http://dx.doi.org/10.3182/20110828-6-it-1002.02690

26. 26. Hadjicostis, C.N. and Rikos, A. (2012) Distributed Strategies for Balancing a Weighted Digraph. Proceedings of the 20th Mediterranean Conference on Control and Automation, Barcelona, 3-6 July 2012, 1141-1146. http://dx.doi.org/10.1109/med.2012.6265792

27. 27. Apostolos, I.R. and Cristoforos, N.H. (2013) Distributed Balancing of a Di-graph with Integer Weights. Proceedings of the IEEE Conference on Decision Control, Firenze, 10-13 December 2013, 1983-1988.

28. 28. Attilio, P. and Andera, R. (2013) A Decentralized Algorithm for Balancing a Strongly Connected Weighted Digraph. Proceedings of the American Control Conference, Washington DC, 17-19 June 2013, 6547-6552.

29. 29. Fan, Y. and Han, R.Z. (2015) Graph-Balancing Algorithms for Average Consensus over Directed Networks. International Journal of Systems Science, 47, 135-148. http://dx.doi.org/10.1080/00207721.2015.1029720