有限带宽和时变拓扑结构数字网络的分布一致性

1、伴随有限带宽和时变拓扑结构的数字网络下的分布一致性摘要在这篇文章里，我们考虑了离散时间下伴有有限通信传输率和时变通信拓扑结构的分布平均一致性。我们基于进位制改革的量化设计了一个分布式编码解码方案，并且在对称补偿方法的基础上设计了一个控制协议。我们提出了一个自适应方案，根据关联信道的活跃与否来选择量化水平的数量。我们证明了，如果网络是共同连接的，那么在协议设计下，平均一致性能渐进地实现，并且收敛速率被量化。尤其是，如果网络中的任何的连接失败的宽度是有界的，那么控制参数和尺度函数可以被恰当的选取出来，如此一来5级量化器对于指数渐进速率下的渐进平均一致性来说足够了。关键词：多代理商系统 分布式一致

2、数据传输率 量化 时变拓扑结构引文在最近几年，多代理商网络上的分布式协作已经成为网络控制系统和复杂性科学的最具活力的一个方向之一。当开始采用数字通信，因为有限的信道容量，每个时间步只有很有限的一小部分的信息能在邻级代理商进行交换。在邻级代理商的通信是编码，传送，接收，解码的综合过程。与传统的单一控制理论相似的是，这个基于由无限开始的多代理商协作的研究没有考虑通信约束，随着深入的研究，研究员渐渐地开始注意通信网络的各个方面。最近，量化一致性或者是量化通信的一致性引起了越来越多的研究人员的注意。大多数现存的关于量化通信分布一致性研究都假定非时变的通信拓扑结构。众所周知，由于许多像联结失败或环境改变

3、这类的原因，多代理商网络下的通信拓扑经常是时变的。由于联结失败引起的网络拓扑结构的改变是一种无源开关。一个好的分布式一致算法需要具备稳健性来对抗这种开关。在某些其他案例里，网络的拓扑结构可能会被有目的的改变，比如说，根据为了整个系统的性能优化的高级命令而选取的不同模式的网络交换机。因为有限的带宽，量化通信和时变拓扑结构下的分布式一致在理论和工程上的观点来说都具有意义。Dimarogonas 和 Johansson 思考了静态无限层次均化和逻辑量化器的量子化的相对状态信息下的分布式一致，并且证明了如果在切换点之间，对于所有的连续时间间隔通信图都保持树，假若量化密度足够的高，那么一致性可以实现。N

4、edic,Olshevsky,Ozdaglar,和Tsitsiklis思考了时变拓扑结构和静态无限层次均化量化器下的量化平均一致性。他们证明了如果通信图是共同连接的，那么近似平均一致性是可以实现的。Carli et al.，Lavaei和Murray考虑了一个基于一个无限级数一致的量化器的量化通信的随机流言算法。Carli et al.（2009a,b）。Kar和Moura(2009)考虑了用静态无穷级和有限级一致的量化器的有着随即连接失败的量化平均一致性。他们在在量化之前添加了一个随机抖动来制造一个量化误差白噪音和证明了如果如果拉普拉斯矩阵序列是i.i.d并且这意味着图总是连通的，然后所有的

5、代理商的状态值最终以极高的可能性进入内部状态平均值的小邻级代理商。注意到以上文献集中在静态无穷层次量化器和稳态误差不是零。在这篇论文里，我们考虑了伴随有限通信带宽的离散时间下的平均一致性。代理商有实值状态和在无向数字网络下彼此之间的通信。网络拓扑可以是时变的。这里存在两个最基本的问题。一个是代理商之间的信道是有限容量的，因此只有有限级的量化器可以被使用，这可能导致无界的量化误差。另一个是对于给定的代理商的邻级代理商可能随着时间发生改变，这可能导致为合适的拓扑情况（Li et al.,2011）设计的编码解码方案之间的不协调。为了克服这些困难，我们设计了一个基于比例创新量化器的分布式编码解码方案

6、，其中扩展函数是用来避免有限层次量化器的饱和。在这里，不像确定拓扑结构的那种情况，每个信道都有自己的编码器解码器。每个量化器的量化电平的数值由相关联信道的状态决定。我们提出一个基于对称补偿的控制协议并且设计了一个合适的方案来选取量化电平的数值。每个量化器的量化电平的数值是根据相关信道在上一步是否活跃而调好的在线数据。通过使用这个方案，我们证明了如果网络是共同连接的，那么在设计的协议下，平均一致性可以没有稳态误差的渐进实现，这就意味着平均一致性随着时间的推移以任意精度被实现。我们表明收敛速率不比扩展函数低。尤其是，如果任何网络中的连接失败的持续时间都是有界的，那么控制增益和扩展函数可以被适当的设

7、置使得对于以指数形式收敛的渐进平均一致性5级量化器也已经足够。这篇论文接下来的部分是这样的。在第2部分，我们提出了网络的模型和公式化问题来进行研究。在第3部分，我们提出了编码解码方案和一个控制协议。在第4部分，我们研究了怎样设置控制参数来确保渐进平均一致性并且为闭路循环系统给出收敛速率。在第5部分，我们给出了数例来论证我们协议的有效性。在第6部分，给出了某些结论和提出了未来的研究课题。下列符号将会在这篇论文中用到：1表示一元素全为1的列向量。I表示一个合适大小的单位矩阵。对于给定的s，表示元素的数量，给出一个向量或是矩阵A，它的转置阵以表示，它的无穷范数用表示，它的欧几里得范数用表示。对于一个

8、给定的正数x，它的自然对数为它以二为底的对数形式为，小于或等于x的最大整数值记为，大于或等于x的最小整数值记为。对于两个实对称矩阵A和B，我们定义如果A-B是半正定的，那么.2.模型描述和问题公式化我们考虑了一个有N个代理商的网络的动态分析，其中分别是第i个代理商时间为t时的状态值和输入值。代理商之间的通信由无向图表示，其中是一组节点，是的邻接矩阵的权重，其中用来表明从j到i是否活跃的通信渠道。由于通信图是无向图，所以是一个对称矩阵，在时间t下第i个代理商的相邻代理商由定义。的基数被叫做i在时间t时的度，并且用表示。定义的拉普拉斯矩阵由定义，其中我们用数对来表示从j到i的通信渠道。活跃通信渠道

9、的一个有序数对被叫做从代理商到代理商的路径。如果对于任意的都有从i 到j的路径，那么图就叫做连通图。对于一序列我们有下列的假设备注1.我们注意到代表第i个代理商的一组无穷多的邻级代理商。假设意味着如果第j个代理商在某一个时刻是i代理商的邻级代理商，那么在时间趋于无穷时它也是i代理商的邻级代理商。注意那些渠道只在有限期里不会对协议设计和闭环管理产生本质上影响的时候存在。在这篇论文里，我们目标是设计一个使用数据的有限比特位的编码解码方案和一个交互协议来实现渐进平均一致性。3.协议设计我们假设在代理商之间只有具有象征意义的数据才能进行交换。对于每个通信渠道，传输器的状态值首先对代表数据进行编码然后进

10、行传输，之后数据被接收，接收器使用的解码器得到一个传送器状态的估计值。对于代理商i和代理商j，其中对于信道，第i个代理商的编码器是按以下设计的 其中是的内部状态，和分别是的输入值和输出值。在这里是一个量化器，并且是一个拓展函数。对于代理商，信道将是永远不会活跃的，对于信渠设计一个编码器它是无关紧要的。因此，总体上看有个 编码器是与代理商i有关联的。对于信道代理商j有关联的解码器由以下给出其中是的输出值。当信道是活跃的，在被代理商j接收之后，解码器被激活来获得的估计值。备注2.众所周知，对于分布式一致性使用动态编码解码方案这个思想是由Carli et al.首次提出的。在这里，编码器（2）和解码

11、器（3）的结构和那些之前（Carli和Bullo,2009;Carli et al.2010a;Li et al.，2011）里的是一样的，然而，由于通信拓扑的时变性，这里有两个主要不同点。对于确定通信拓扑结构的情况，更新增益和编码器的数字转换器都是确定的，对于时变拓扑结构的情况，编码器和解码器的参数，比如和的量化电平的数值都是对于信道合适选取的。对于确定通信拓扑结构的情况，每个代理商都只需要坚持一个编码器，对于时变拓扑结构的情况，因为邻级代理商的状态的链接是随时间变化的，我们需要为第i个代理商设计个编码器。备注3.由上可知，要计算在时间t时编码器和解码器的输出值，需要同时知道代理商i和代理商

12、j的，也就是说，它们之间的的信道是否活跃。我们注意到如果通信拓扑的开关是预先知道的，那么很明显也就知道了，并且如果信道的值不能优先知道，比如间歇性的链接失败或者是数据包丢失的情况，那么我们可以使用一个分离的反馈信道来知道。这个反馈渠道假设是可靠的并且在邻级的代理商间的每个反馈将会花费信息传送的一个比特位。我们采用了有限层次的统一的对称量化器，也就是，量化器采取以下的形式其中K可能随着时间改变。对于是2K+1级量化器。备注4.在确定的拓扑结构的情况下，我们假定量化器的输出值0不会被传送，并且量化器的比特值是。在这里，为了避免与闲置信道的情况混淆，输出值0将会明确地传送给邻级代理商，因此量化器的比

13、特值为。我们用由时间决定的来表示的量化电平数值，并且提出了如下的分布式协议其中控制参数h>0。定义从接下来的定理里我们可以知道协议（2），（3）和（5）能保存闭路循环系统的平均状态。定理3.1.如果假设（A1）成立，那么在协议（2），（3）和（5）下，闭路循环系统满足证明.从（2），（3）可以知道然后由的定义和协议（5），我们知道通过假设（A1），我们知道了此外，当且仅当很容易就可以得到然后和（1）一起推出（6）。备注5.我们注意到可以把控制输入（5）可以分为和误差补偿项因为在编码解码过程中信息的丢失，控制输入偏离了by对于邻级代理商的状态值的估计误差的权重和。从对于定理3.1的证明来看

14、，可以知道估计误差和可以由补偿，这项只是关于邻级代理商的误差补偿的权重和。最关键的思想是对于每个信道，虽然通过代理商i接收误差是不知道的，发送误差可以用减去代理商i本身的编码器的内部状态值得到。因此，代理商i可以对代理商j基于发送误差的接收误差作出补偿。由于整个网络的对称性，全部接收误差的和可以被补偿而且系统的平均值被保存下来。4.收敛分析我们做出了如下假设：（A2）这有一个常数>0，如此以致（A3），其中和已知是非负常数。（A4）存在一个整数T>0和一个实常数>0，使得,其中为拉普拉斯矩阵的第二最小算子。备注6.当且仅当存在整数和常数时，假设（A4）成立，使得这就意味着网络

15、流量在间隔是共同连接并且平均代数连通性一致的下界趋近于零。比如，如果有限数量图中的网络交换机是基于有界的连续不断的间隔中共同连接，那么（A4）成立。如果假设（A4）成立而且那么是可以证明的。令和。从（2），（3）和（5）我们可以看见我们的协议可以由以下参数表征：控制增益h，量化电平的数值和拓展函数，我们可以考虑如何选取控制参数来确保渐进平均一致性。在下面的定理中，我们可以发现对于任意给定的控制增益h和拓展函数，每个信道的量化电平的数值可以由以下步骤合适选取出来：如果在时间t时信道是活跃的，那么在时间t+1的量化电平的数值可以维持为一常数，如果信道不是活跃的，或是存在联结失败，那么量化器的量化电

16、平的数值为了这个信道会被增强，这样因为联结失败导致的不确定性就通过提高信息准确度抵消了。关键点在于通过选取设计参数来令量化器是非饱和的。定理4.1假定假设（A1）（A4）成立。如果，,并且对于任意的，量化电平的数值满足其中然后在协议（2），（3）和（5）下，闭路循环系统满足不只如此，如果那么定理4.1的证明需要闭路循环一致性误差补偿的细节分析。把协议（2），（3）和（5）代入系统（1）。闭路循环系统由给出定义其中当时，定义为0。闭路循环系统（13）又可以写成向量形式然后有上述公式和的定义，当我们得到可以由它得出一致性误差Eq.（14）有以下特性1 均匀部分的状态矩阵是单位矩阵减去一个时变拉普拉

17、斯矩阵。2 和总为0.因为状态矩阵是时变的，在固定拓扑结构情况下使用的对角化方法不再合适。然而，通过结合上述特性，拉普拉斯图的属性和分析线性时变系统的方法，我们研究了引理4.1和4.2来得到一致性误差，控制参数，网络流量的参数和之间的关系。引理4.1.令成为无向图的拉普拉斯矩阵的一组序列，对于任意的整数满足定义对于给定的假设是一个向量满足和令然后且引理4.2 假设当那么不仅如此，如果那么引理4.1的证明。从（2），我们得出由此式和的定义，我们得出，这个式子和（13）得出由以上和（21），我们可以知道如果那么如果，那么仅当由（5）我们可以知道然后通过假设（A3）和（7），它遵循下列条件和（2）可

18、以一起推出相似的，由假设(A2)(A3)，(8)和(23)(26)，我们可以得到定义从我们知道我们注意到对于任意的N维向量x，然后由（15），假设（A4）和引理4.1，我们可以得到这个和得出定义是下面方程的解定义，然后由（29）我们得到从我们得到，然后由（30），假设（A2）和引理4.2，我们可以得到这个和（28）可以得出结合上述方程和（23），（24）和假设（A2），我们得到如果，那么如果那么现在我们证明了如果对于所有的k=0,1,.,t-1,t=2,3,.,那么。假设。如果，那么通过（9）和（32）。我们得到同时相似的，如果，那么由（9）和（33）。我们得到这个和（34）一起推出，然后由（

19、26），（27）和引文，我们总结出从我们可以得出从（30）和引理4.2，我们，这个和（28），（35）和（36）推导出（11）。如果然后由（11）和定理3.1，我们可以得出（12）。备注7.从（21）（22）和的定义，可以看出全局闭路循环系统实质上是由来描述的一个非线性系统。在这里，是由构成的内部状态向量，是由构成的量化器误差向量。是基于有限层次量化器非线性的一个离散非线性时变向量函数。这种系统包括一个在一致性误差和量化误差之间的非线性交互作用。为了分析（37）描述的系统，首先，由（14）引理4.1和4.2，我们得到一个不等式描述一致性误差是怎样被影响支配的。其次我们将（31）代入（23）和（

20、24）来得到量化误差的上界。最后，反过来我们把这个上界值带入到（14）然后得到一个一致性误差的估计值。这个处理一致性误差和量化误差之间的非线性相互作用的方法和那个分析自适应控制系统的算法（过去用来处理系统状态和辨识误差之间的非线性交互作用）在精神上是相似的。备注8.常数和反映了在某些情况下拓展函数的收敛属性。如果那么。通过定理4.1，我们可以看见（11）给出了一个闭路循环系统的恒定不变的误差值：。如果，那么恒定不变的误差值为0而且（11）给出这个闭路循环系统的收敛速率：。备注9.从定理4.1，我们知道为了实现渐进平均一致性，我们可以设置拓展函数随着时间的增加而消逝。比如，在这种情况下，和一致性

21、可以以指数形式快速达成。另一个方法是设置。这种情况，一致性会相对慢些，然后，因为，仅仅从（9）来看，在一种渐进情况下量化电平的数值可能会减少。在情形1里提及的，链接失败和补偿或在通信网络里的数据包丢失可以以网络拓扑的交换。在时间t信道的连接失败暗示这，否则。注意到伴随着有限数据包丢失的单代理商网络控制系统的控制问题已经被广泛进行了研究。在下面，我们可以看见如果网络中的任意连接失败的持续时间是有界的，那么可以选取一个为常数的量化电平的数值。尤其是，控制增益和拓展函数可以被合适的设置以致5层次的量化器（K=2）对于以指数收敛速率收敛的渐进平均一致性已经足够。对于任意，定义在t时由得到。我们需要接下

22、来的假设。（A5）存在一个整数，使得在这里，被调到零。备注10.上述的内容定义了对于信道的第k次失败的开始时间，同时定义了对于信道的第k次补偿的开始时间，表示了信道的第k次失败的持续时间。可以看见假设（A5）意味着所有链接失败的持续时间都是有界的。备注11.假设g是没有链接失败的连通图。因为连接失败，网络拓扑在时间t的成为一个g的子图。如果连接失败的补偿是以一个正整数来表示边界，然后假设（A4）和（A5）随着都成立，这里L是g的拉普拉斯矩阵。定理4.2.假定假设（A1）（A5）成立。对于任意整数,定义然后（i）是非空的。（ii）对于任意的h和都使得和在协议（2），（3）和（5）下和量化电平数值

23、满足闭路循环系统满足证明.对于任意的整数，从（10），我们得到和，这意味着这里存在使得注意到从（42）和（43），我们知道了存在使得,这样（i）成立。对于任意满足的h和，我们有。由（38）和（40），我们得出（7）。由（39），（40）和（41），我们得出（8）。然后与定理4.1相似的，我们得到了（26）和（27）。现在我们证明了如果，对于所有的都有。假设。由（40），（41）假设（A5）和的定义，与（32）相似的，我们可以得到由（44），和（33）相似，我们得到结合（44）和（45），我们得到然后与定理4.1相似的，我们可以得出（ii）成立。在上述的定理中，提到了K可以被设置为1，然后从（4

24、0）和（41），我们可以看出5层次的量化器可以通过合适的设定控制参数来确保渐进平均一致性。备注12.在Li et al.(2011)，我们证明了对于一个联结的网络，渐进平均一致性通过用以3层次（单比特）的量化器总是可以实现。在这里，从定理4.2和备注13，我们可以看出在一个有着间歇链接失败或数据包丢失的连通网络，提供了持续期是有界的，5层次（3比特）量化器足够用于渐进一致性。另外的2层是用来补偿因为连接失败或数据包丢失带来的信息丢失。备注13.从定理4.2，我们可以看见控制参数h和因为某些全球网络拓扑信息N,和T的需求而被设计为不实时的。使得存在不需要基于全球信息的离线设计参数的静态无限层次的

25、量化器的一致性算法，就像Kashyap et al.(2007)和Lavaei，Murray(2009a),在将来为了动态有限层次量化器的分布式一致性设计的实时参数算法是十分有趣的。备注14.在这篇论文里，我们假设通信网络是无向的。对于将来的研究，研究关于有向拓扑的情况将是十分有趣的。主要的困难可能包括对称补偿方法的失败和在引理4.1里的技术。可能需要开发新的补偿和闭路循环分析的方法。5. 数例在这个情景，我们用了一个数例来论证我们协议的有效性。我们考虑了一个三个代理商切换拓扑的网络其中可以看出，这里。控制参数h为0.01和拓展函数为。所以。根据定理4.1，量化电平的数值如下设置：如果或者如果状态的演变和在Fig.1中展现出来了。可以看见平均一致性是可以被渐进实现的。可知定理4.1的结果通常是稳定的，更少的量化电平会被使用并且在这个例子中收敛速率是可以提升的。我们选取h=0.2，。