分布式平均总体综述

分布式平均算法总体综述分布式平均/分布式一致性问题：所有的节点状态值通过分布式算法最终能够相同/几乎相同，这里所谓的“平均”是加权平均，特例情况，当权值矩阵满足双随机条件（迄今只发现两类情况：Max_degreealgorithms,Metropolisalgorithms）时，各状态值最终收敛于初始状态值的算法平均值。即：一般情况下，谈到“平均”是指加权平均，只要最终节点状态值达到一致性，就说算法是收敛的。对于分布式平均算法的来源，相比集中计算优势，以及近年来广泛运用领域，这里就不再重复了，参见之前的文献综述。这里重点阐述近年来分布式平均问题的不同类型算法。这里不妨说明，之前杨博论文中所提到的传统经典迭代算法：xit+1=x该算法是我们这里谈到的分布式平均算法的一种特例，也是一种最基本的迭代算法，本地节点基于邻居和自己的当前值加权平均得到本节点下一时刻值，但是这种迭代算法注意的问题是，对于网格拓扑和随机拓扑，需要较多的迭代次数才能到达较好的一致性收敛。接下来，我们针对不同情形下分布式平均问题，采取不同的策略以提高一致性性能。提高收敛速率利用存储信息；利用二级节点；利用非线性迭代存在噪声存在链路失效流量控制和拓扑信息相关其它提高收敛速度利用存储信息DistributedComputationofAveragesOverAdhocNetworks2005(SelectedAreasinCommunications,IEEEJournalonDateofPublication:April2005)采用滤波器和延时器文中只是提到前人在分布式计算方面的工作，而且也基本是和路由算法结合在一起，对于分布式平均计算貌似没怎么提到，因此这里就不作陈述。作者提出的算法时运用于自组网和传感网中的分布式平均的计算，而且可以证明，通过获取本地网络连接信息，迭代算法时可以逼近收敛于所期望的状态值。另外，算法还有一个优势，那就是估计序列可以极大地改善迭代次数。再者，算法具有一定容错率，能够很好地适应网络拓扑变化。文章算法主题思想是：对于给定的网络拓扑Φ，第i个节点通过与邻居的信息交互产生的状态序列xi[n]不断逼近所期望的数值G(Xx 作者首先考察一阶LTI（线性是时不变）准则：Wn;k=Wδ(k-1)，因此上述迭代算法为：xn=Wx[n-1]，x而且，文中并给出了ρ的最大和最小取值。（可以看出该公式和（*）式权值矩阵换了）另外，定义了均方误差：x然后基于一阶LTI准则又定义了更一般的LTI渐进收敛准则以更好地提高收敛速率。实际上是经滤波器和延时器处理构成的系统，这样将收敛速率的最大化转化成了系统传递函数的最大谱半径（方程根，注意这里需对滤波器的恰到选择）。这里作者选取了简单经典的滤波器：Hz=(1+c这样最终的迭代方程变为：这里通过对c和ρ的恰当选择，可以提高收敛速率。AcceleratedGossipAlgorithmsforDistributedComputation2006（Forty-FourthAnnualAllertonConferenceAllertonHouse,UIUC,Illinois,USASept27-29,2006）采用移位寄存器作者采用流言算法来提高分布式平均一致性。文章提到了以往一些流言算法：【19】中每个节点将自己当前的值和随机一个邻居值（以一定的概率）两者的取平均作为自己的新值。这中方法有不少优势：首先，算法是完全分布式的，不需要中心节点协调；其次，可以不需要同步时钟来完成全网同步；再者，易实现，每一步只需要一次通信即可；最后算法具有一定的容错能力（链路失效或节点失效）。但是算法致命的不足是需要大量的迭代。因此为提高收敛速度也陆续出现了一些算法。【20】是基于可靠性传播的同步算法来提高收敛速度。【21】基于概率针对特定拓扑提高收敛性。对于在一般网络拓扑是否也具有这样的效果还没得到证实。【22】提出了一种改进型流言算法利用节点的位置信息来提高收敛速度，但这种算法是假定网络使用的协议中包含位置信息。本文，作者采用完全不同方法来提高流言算法收敛性。每个节点采用多阶移位寄存器来存储过去值，节点采用自己和邻居过去值来迭代更新。以二阶为例：此外，作者以二阶为例，证明的算法的收敛性。仿真比较流言算法移位寄存器不同阶数性能。Distributedaverageconsensuswithincreasedconvergencerate2008（Acoustics,SpeechandSignalProcessing,2008.ICASSP2008.IEEEInternationalConferenceon

DateofConference:March312008-April42008）

采用线性预测器本文采用的是一种线性外推法来提高分布式线性迭代速率。对于所提出的算法既有理论分析又有仿真验证。仿真表明，所提出的算法在混合参数采用最优值时，要优于传统的基于权值矩阵的最优一致性算法。文中指出，以往的分布式平均算法【23】【41】【42】，由于收敛所需的迭代次数过多。这样直接限制了算法在实际场景中的运用。在分布式平均算法方面Boyd做了很多工作【23】【41】。他们指出可以将算法的渐进收敛问题转化成权值矩阵的半定规划问题。但是该方法有两个缺点：一是，该方法是基于凸优化模型，这样可能需要充足的时间或计算资源。二是，需要提前知道整个网络的连接情况，这样，就需要有个中心节点或是有某种能够感知全网拓扑信息的分布式机制。为此，针对上述第二点不足，【41】采用了次梯度算法，但是算法对时间，计算和通信情况有特别要求。另一种权值矩阵优化方法就是文献【23】提到的“最优常量”，即邻居的边的权值是常量值，通过优化该常量来获得最大可能的收敛速率。考虑到所有的边权值都是相同的常数值，因此，这也就限制了算法在实际中的运用。文章作者提出了一种快速分布式平均算法，算法结合了一个线性预测器和标准的一致性算法。不同于之前的算法，该算法并不会增加额外的计算负担，因为预测是线性的，而且预测器的参数是可以离线计算的。作者考察了一种特殊情况下的收敛情况，导出了获取渐进收敛速率的最优凸组合参数。算法在优化参数方面，重点考察了权值矩阵的次大和最小特征值。文章给出了一种相对粗略的解决方法，这种方法不需要很多的信息数据，因此便于在实际中运用。迭代算法：这里：z（A矩阵的广义逆矩阵）K:表示对节点状态将来K步预测（这里好像并没有体现K步预测的效果），M：获取本地节点前M个存储值。Multi-AgentConsensusUsingBothCurrentandOutdatedStates2008（Proceedingsofthe17thWorldCongressTheInternationalFederationofAutomaticControlSeoul,Korea,July6-11,2008）采用当前值和过去值，连续时间迭代这里作者提到分布式平均算法发展。Jadbabaieetal.[2003]，在无向图中，基于最近邻居信息来分析MA（multi-agent）系统的一致性问题。Olfatietat.[2004]，考察有向图中平均一致性问题。Moreau[2005]andRenetal.[2005]将Jadbabaie的结果拓展到有向图中。最近这方面的研究是Jinetal.[2006]，采用采用两跳信息（即二级邻居）来提高一致性。这些算法都没有利用到节点去过的信息。该算法既考虑了当前状态又考虑了过去状态，其出发点在于：过去的状态信息存在与任何控制系统中而且也应该考虑；存储器较廉价，这样要保存过去信息的代价不是很高。算法不足地方是，时延可能会有所增加，再者，对于过去值的有选择性地挑选可能会进一步提高算法性能。这里考察的是连续时间迭代模型：（这里对于连续时间为什么采用调整量来表示当前状态值？？？）仿真时，比较有无采用过去状态值算法性能。【】A.Jadbabaie,J.Lin,andA.S.Morse.Coordinationofgroupsofmobileautonomousagentsusingnearestneighborrules.IEEETrans.onAutomaticControl,48:988–1001,2003.【】R.Olfati-SaberandR.M.Murry.Consensusproblemsinnetworksofagentswithswitchingtopologyandtime-delays.IEEETrans.onAutomaticControl,49:1520–1533,2004【】L.Moreau.Stabilityofmulti-agentsystemswithtime-dependentcommunicationlinks.IEEETrans.onAutomaticControl,50:169–182,2005【】W.RenandR.W.Beard.Consensusseekinginmultiagentsystemsunderdynamicallychanginginteractiontopologies.IEEETrans.onAutomaticControl,50:655–661,2005.【】Z.JinandR.M.Murray.Multi-hoprelayprotocolsforfastconsensusseeking.Proc.of45thIEEEConferenceonDecisionandControl,1001–1006,SanDiego,2006AcceleratedDistributedAverageConsensusviaLocalizedNodeStatePrediction2009（IEEETRANSACTIONSONSIGNALPROCESSING,VOL.57,NO.4,APRIL2009）文章研究了一类分布式平均算法：每个节点都初始化本机状态值，每次迭代时节点状态值加权求和来更新当前本机状态值【08】【14】【15】【18】。这一类的算法状态值在时间上是不相关，并且状态值渐进收敛与各节点初始状态值的平均值【15】。这一类算法是非常吸引人的，因为算法完全是分布式的，而且节点间通信是非常简单的。其主要弊端是，要达到收敛于初始平均值需要很多次的迭代。因此文章针对这一不足，提出的算法能有效地提高收敛速度，同时又不会增加的迭代次数和计算的复杂度文章提了一种通用基于预测器的思想来提高分布式平均算法的收敛速度。相比以前的快速算法，文中的算法既简单又完全是线性的，并且参数都是可以离线计算。 更新公式：这里的算法注意和（Multi-AgentConsensusUsingBothCurrentandOutdatedStates）提到的算法作比较。从上也可以看到，节点更新（7a）是采用预测项和正常迭代方式加权，式（7b）是正常迭代方式，式（7c）是预测项，预测是基于本节点当前值和过去值。PolynomialFilteringforFastConvergenceinDistributedConsensus2009（IEEETRANSACTIONSONSIGNALPROCESSING,VOL.57,NO.1,JANUARY2009）近来的主要研究方向是，对权值矩阵W进行优化以达到最快收敛【23】【27】【27】。本文中，作者不再是通过对权值矩阵W的累乘来达到收敛，而是使用到节点之前的数据来提高收敛速度。算法思想类似于【28】【29】。我们知道收敛性是由第二大特征值（绝对值）决定，因此，我们可以通过仔细设计滤波器来影响收敛性。而滤波器的使用就要使用到之前的预测估计值。而滤波器系数的选择（不管是静态拓扑还是动态拓扑）可以依赖于半定规划（SDP）来解决.。而且针对动态拓扑情况，作者给出了基于平均权值矩阵的滤波器系数一种近视算法。文章首先对分布式平均思想进行了阐述，然后针对静态拓扑和动态拓扑两种情况下的分布式平均问题进行了介绍。静态拓扑下，网络的收敛与否取决于权值矩阵的谱半径，对于收敛速度快慢，则取决于次大特征值，文章对此进行了理论推导。多项式滤波器分布式平均算法的主体思想是：对权值矩阵添加滤波器处理，使其频谱变得陡峭，这样使得权值矩阵的第二大特征值最小，最终达到提高收敛的效果。文中是通过半定规划方法来确定最优滤波器的系数。大部分场景中，通过对几种常见权值矩阵运用该算法，其收敛性能都要远好于最新的几种算法。但是也有例外，例如在频繁改变拓扑的网络和节点存储器小的情况下。迭代更新方式：从上图可以很清楚看到，多项式滤波过程实际上是采用本节点过去值来加权得到当前值，因此也看作是一种线性预测过程。滤波之后，再通过正常的迭代方程处理，得到最终当前的值。OptimizationandAnalysisofDistributedAveragingWithShortNodeMemory2010（IEEETRANSACTIONSONSIGNALPROCESSING,VOL.58,NO.5,MAY2010）采用预测器文章提到早期的算法焦点主要集中于每个节点维护和更新自己的单一数据，自己先前的数据并没有利用到，最终到达渐进性地一致性收敛。然而，这种算法的收敛性很大程度上受限于网络拓扑连接，例如在网格和随机拓扑中，收敛的概率就很大程度上降低了。文章首先对于在数据更新规则中增加一个本地预测器可以有效地提高分布式平均算法的收敛性进行了理论推导证明。本地预测器的值是本节点当前值和过去值（例如是过去两个时刻值）的线性组合，数据更新规则是结合预测器的值和邻居值得加权求和来更新的。文章导出了预测器的参量和邻居数值的最优匹配结合参数，并对其能够提高收敛速率进行了理论分析。对于N个节点的链状拓扑，该算法相比传统的一致性同步算法，性能有N倍的提高，对于二维网格拓扑，性能有N传统迭代算法中，每个节点都维护有对整个网络均值的一个估计值。在这种简单的分布式平均算法中，每次迭代时，所有节点都与自己的邻居进行数据交换，然后依据之前对整个网络均值的估计值和邻居的值得加权求和来更新本地均值，可以归结为xt+1=Wxt。这里只要权值矩阵W满足收敛条件，那么当t→∞时，数值仿真表明具有预测性的一致性同步算法收敛要快很多【03】【04】--【07】。但这些文献并没有对算法表现出来的收敛优势进行理论上的推导。此外，这些算法需要大量的初始化工作。本文中，首先对比传统无存储的同步算法，文中对预测性的同步算法的优势进行了理论推导。文章的核心在于线性预测器和导出得到的结合本地预测值和邻居加权值的优化混合参数的闭合表达式。文章对使用节点存储器中存储信息来提高分布式平均算法的收敛性进行了理论推导。文章考察的是情况是含有两个抽头的线性预测器。并导出了该快速收敛算法的混合参数的最优值，和谱半径估计的完全分布式方法。文章另一个重要贡献是，导出了一致性同步矩阵（权值矩阵）的谱半径的上界，该上界将初始权值矩阵的谱半径增长速度和最终收敛的一致性权值矩阵的谱半径增长速度联系起来。迭代算法：这里可以类比（AcceleratedDistributedAverageConsensusviaLocalizedNodeStatePrediction）中提到的预测算法，可以看出这里的算法是前面所提到算法的一种具体特例2阶线性预测。LinearHigh-OrderDistributedAverageConsensusAlgorithminWirelessSensorNetworks2010（HindawiPublishingCorporationEURASIPJournalonAdvancesinSignalProcessingVolume2010,ArticleID373604,6pagesdoi:10.1155/2010/373604）文中作者提出了一种线性高阶分布式平均一致性算法（DAC）并运用于无线传感网中。文中对一致性算法和高阶DAC算法的收敛速率进行了分析。特别指出，算法的收敛速率取决于网络拓扑所决定的权值矩阵的谱半径。仿真表明，该简单的线性高阶DAC算法在不需额外增加通信载荷和对网络拓扑重新配置就可以提高算法的收敛速率。在DAC算法中，对于连通图，节点只需依赖于成对（即和邻居）的本地状态信息就可以逐渐达到一致性收敛。本文作者采用了一种简单的方法（线性高阶）来提高DAC算法的收敛速率。【52】作者证明，DAC算法的收敛速率可以采用小世界“small-world”现象来提高。然而，这种方法，需要对网络拓扑进行随机重连。在【53】中，作者提出了一种无需增加额外通信开销的标度epsilon算法来提高收敛速率。但仿真表明，均方误差并不会随着迭代次数增加而单调递减，因此在实际中不利于运用。【54】将节点从空间角度化分为“leader”节点和“sensor”节点，在满足一定条件下，“sensor”节点的状态值最终会收敛于“leader”节点状态值的线性组合。也可以采取多目标优化（MOP）方法来不断缩小收敛值与达到目标收敛速率时的收敛值间的偏差。【55】采用非线性迭代算法了来提高算法收敛性。本文作者将高阶一致性原理运用于分布式平均问题中以提高收敛速率。算法不仅不会增加额外开销，而且通过利用以往的迭代值来提高收敛状态值更新方式：每个节点将自己的本地状态信息发送给邻居，每个节点在接收到邻居信息后，采用自己和邻居之前存储的M-1个迭代值加权平均来更新当前值。迭代方式为：可见调整量变为自己和邻居的过去M-1阶偏差值，而并非仅仅是只有一阶状态值偏差。可以很明显看出，算法采用本节点和所有邻居以往状态值的加权平均来更新得到当前状态值，也可以看出，高阶算法是一阶算法的一种扩展。这样在引入拉普拉斯矩阵后，上述的迭代公式演变为：文中接下来给出了线性高阶DAC算法的收敛条件，并给出了证明。收敛速率的最大化转化成最迭代等式中ε和γ的选择（这两个参数仅仅取决于网络拓扑）。针对二阶DAC算法，给出了谱半径和最优收敛速度的表达式。而对于三阶以上的DAC算法是不易计算的，因为此时特征方程根不易计算。最后作者指出下一步工作是考察链路失效情况下算法相关性能。Acceleratedlineariterationsfordistributedaveraging2011（\o"GotoAnnualReviewsinControlonSciVerseScienceDirect"AnnualReviewsinControl\o"Gototableofcontentsforthisvolume/issue"Volume35,Issue2,December2011,Pages160–165）基于在Muthukrishnan,Ghosh,andSchultz(1998)文中的算法思想，本文作者研究了一种改进的线性迭代算法用于快速分布式平均收敛，算法中运用到了存储器单元。对于一致性问题中收到人们极大关注的是分布式平均问题（Xiao&Boyd,2004），文中提出了一种经典的迭代算法：xit+1=j∈Niaijxjxit+1=(g+1)j∈Niaijx这里的g是一个基于权值矩阵A的常数值（显然g=0时，即为之前的经典迭代算法），且有g∈(0,1),Muthukrishnanetal.(1998),指出，上述改进后的迭代，只要g的选取恰当，该迭代算法在收敛速度上就可以优于之前的传统迭代算法。，而最近又有作者Aysaletal.(2009)提出了一些新的更好的迭代算法，如：xt+1=g+1很显然（*）式是式（**）的一种特例，此时θ1=1，θ2=0本文的主要贡献是，全面研究模型（*）的行为性能，（文中并不要求权值矩阵具有对称性，但要求权值矩阵的谱是实数谱），采取的研究方法也和之前的Muthukrishnanetal.(1998)不相同，同时得到的结果更具普遍性。g最优值的选取和相应的最快收敛速度最初在Muthukrishnanetal.(1998)文献中有给出计算，而本文，采用新的计算方法，给出了快速收敛时g值范围的闭合形式。接下来，作者给出迭代算法（*）的收敛条件，并进行了证明，以及对于参数g的选择不同，算法的收敛性能或优于或劣于或相当于之前的经典迭代算法（-*）【】Xiao,L.,&Boyd,S.(2004).Fastlineariterationsfordistributedaveraging.SystemsandControlLetters,53(1),65–78【】Muthukrishnan,S.,Ghosh,B.,&Schultz,M.H.(1998).First-andsecond-orderdiffusivemethodsforrapid,coarse,distributedloadbalancing.TheoryofComputingSystems,31,331–354.【】Aysal,T.C.,Oreshkin,B.N.,&Coates,M.J.(2009).Accelerateddistributedaverageconsensusvialocalizednodestateprediction.IEEETransactionsonSignalProcessing,57(4),1563–1576.【】Oreshkin,B.N.,Coates,M.J.,&Rabbat,M.G.(2010).Optimizationandanalysisofdistributedaveragingwithshortnodememory.IEEETransactionsonSignalProcessing,58(5),2850–2865.利用二级节点Multi-HopRelayProtocolsforFastConsensusSeeking2006（Proceedingsofthe45thIEEEConferenceonDecision&ControlManchesterGrandHyattHotelSanDiego,CA,USA,December13-15,2006）基于有向图，考虑连续时间迭代为实现快速一致性收敛，本文提出了多跳中继协议（算法），实际上就是采用二级邻居信息。在网络拓扑没有发生变化时，算法可以扩大代数连接。而且文中讨论了通信时延，而且对通信时延和算法收敛速率进行了均衡。（注意这里通信时延是如何定义） 算法的收敛速率是非常重要的，【09】的作者Xiao和Boyd将一致性问题转化成最有线性迭代问题，而且算法的收敛速率可以通过寻找每条通信链路的最优权重来得到提高。然而，算法要求网络全局结构必须提前知道。对于大型网络，【76】Olfati-Saber提出了一种“随机重连”机制来提高一致性。然而这需要完全改变网络拓扑，实际上这是很困难的。这样我们就希望在不需要改变网络拓扑情况下，可以获得更好的一致性收敛速率。对此文中提出了基于多跳路径的一致性算法，简单考虑，这里采用两跳。每个节点可以将自己的邻居信息发送给其它节点（即，节点可以获取邻居的邻居信息）。基于连续时间：传统的一致性迭代算法：采用二级邻居的一致性迭代算法：这里假定，有向图是一跳连通，对称的，两跳也是连通，对称的，那么可见采用两跳信息的算法收敛速率得到了提高（收敛速度取决于拉普拉斯矩阵次大特征值）。而且代数连接（什么是代数连接？？？）至少提高了λ2 接下来，作者考察了算法的时延情况。尽管算法可以很大程度上提高收敛速率，但是却需要更大带宽。网络拓扑的边越多，一致性收敛越快，同时，通信时延更大。因此，作者采用了频率扫描法来均衡收敛速率和通信时延。Acceleratingdistributedaverageconsensusbyexploringtheinformationofsecond-orderneighbors2010（PhysicsLettersA）作者提到近年来关于分布式平均一致性问题研究工作。【08】针对固定拓扑提出了FDLA算法，通过对边权值的选择来获得更好的收敛速率，当权值矩阵对称时，算法的收敛速率取决于权值矩阵的次大特征值。而FDLA问题进一步可以转化成SDP问题。【77】针对随机拓扑，得到了类似结果。近来，又有人开始采用存储信息来提高一致性。【78】采用当前和过去的状态值来更新得到下一时刻状态值。【79】采用滤波器的方法通过过去值来更新得到当前值。针对固定拓扑和随机拓扑进行了探讨，算法具有较好灵活性和收敛速率。【80】针对连续时间，采用过去值和当前值来提高收敛性。只要过去值选取恰当，在不增加控制能力情况下，可以获得更好的收敛性。近来，又有些采用额外的链路信息来提高收敛速率。【81】作者采用多跳链路来提高收敛性。在基本图不发生变化下，算法可以提高收敛速率。【82】考察增加的链路以提高加权网络一致性同步。本人针对连续时间和离散时间两种情况下利用二级邻居信息来提高分布式平均一致性算法。每次迭代过程中都会用到二级邻居信息，相比只采用一级邻居信息的传统算法本文提出的算法能获取更快的收敛速率。考虑使用二级邻居的部分信息，对于二级邻居的变的选择并不是随机的，作者对此进行了规划。在连续时间情况下，边的选择可以转化成凸优化问题，进一步可以采用凸松弛（convexrelaxationmethod）来解决，在离散情况下，可以采用蛮力法（thebruteforcemethod）解决小型网络下边的选择。采用二级邻居完全信息：离散时间：进一步转化为：连续时间：采用部分二级邻居信息：离散时间：采用凸优化方式m2是二级邻居边的总数，连续时间：ALocalAverageConsensusAlgorithmforWirelessSensorNetworks2011（DistributedComputinginSensorSystemsandWorkshops(DCOSS),2011InternationalConferenceonDigitalObjectIdentifier:10.1109/DCOSS.2011.5982199PublicationYear:2011,Page(s):1-6）

算法适用于分簇结构

文章指出在不少一致性平均算法中，每个传感节点维持对全网状态值平均值的一个估计，采用对邻居值的加权求和来提高收敛速度，这样算法的达到收敛时所需的迭代次数很大程度上取决于所采用的权值矩阵。出于节点间信息传递量和能量考虑，我们希望迭代次数越小越好，当然原则上可以通过计算最优化权值矩阵来做到，但是传统一些算法都是独立采用一个节点（可以看作是中心节点）来获取全网拓扑信息，然后进行计算并广播给网内节点。很显然，在实际中这种办法是不可取的。本文中，作者提出了一种新颖的平均一致性算法，算法中每个节点仅基于本地关于邻居的信息来选取自己的权值。算法适合于具有分簇结构的网络如无线传感网。 文章再次提到分布式一致性算法的优势：仅需通过和本地邻居继续信息交互并进行一些简单的加权求和，就可以迭代计算平均值，这过程中完全是一种分布式的方式。我们知道可以通过半定规划【50】【07】方式来优化权值矩阵使得收敛时间最小，但是半定规划的方式需要获知全网的拓扑信息，而这在大型动态传感网中是不可取的，因为这受限于节点计算能力和通信开销。本文提出了一种新的算法，“邻居算法”，对于不同类型的分簇结构的拓扑而言，算法较其他一些一致性算法具有更少的迭代次数。对于分簇结构的拓扑，算法的收敛性主要受连接不同分簇链路的权重决定。邻居算法可以用来鉴别这样的链路并赋予其更高的权值以提到算法收敛速度。 邻居算法：利用非线性迭代Distributedaverageconsensus:Beyondtherealmoflinearity2009(Signals,SystemsandComputers,2009ConferenceRecordoftheForty-ThirdAsilomarConferenceonDateofConference:1-4Nov.2009)本文提出一种分布式平均一致性算法，算法中采用非线性迭代更新，算法采用状态值偏差的正弦函数更新调整量，相比传统算法仅仅是采用线性偏差值来更新迭代。当权值矩阵满足一定条件时，非线性迭代算法可以收敛于初始均值。仿真表明，算法的收敛速率要优于之前的传统的线性迭代。线性分布式平均一致性（LDAC）算法，每个节点是基于邻居状态值的线性组合来更新自己的状态，只要满足一定的条件，每个节点的状态值就会最终收敛于初始值的均值。迄今人们的焦点一直集中于线性迭代更新算法，算法的收敛速率取决于网络的连接性情况（拓扑拉普拉斯矩阵的次大特征值）。本文作者提出一种非线性迭代一致性算法（NLDAC），算法采用自己和邻居偏差的正弦值来更新调整量。此时，算法的收敛速率取决于节点的实际状态。通过恰当调谐组合权值，NLDAC算法可以达到更快的收敛速率。注意综合考虑这里的节点初始状态值有作限定：yl这里我们参数μ和网络连接性满足一定条件时，上述算法是收敛于初始值的均值。即：这里作者给出并证明了算法收敛条件：当：0<μ<2p这里，pN≜supλ而且这里可以进一步得到：pN≤2而对于分布式线性迭代算法，文献【75】给出了μ的最优取值：文章作者提出NLDAC算法，算法的收敛速率取决于节点状态值偏差的余弦值，即取决于节点实际状态值，相比LDAC算法的收敛性仅仅取决于网络连接性，NLDAC算法收敛性不仅和网络连接性有关，而且还与自由度（参数的选取）有关。存在噪声Distributedaverageconsensuswithleast-mean-squaredeviation2007（JournalofParallelandDistributedComputing,2007）这里考察的存在加性噪声分布式平均迭代模型，模型是经典迭代算法的一种拓展（没有噪声干扰）。文章没有提到前人有关迭代算法中存在噪声的算法模型。文中提出了一种分布式平均的随机模型，模型中，每个节点依据邻居的值来更新本地值，而且每个新值都受到均值为0的加性白噪声干扰，可以说是一种具有噪声干扰的随机模型。一致性的收敛效果通过偏离均值的总的均方误差来衡量，因此我们要解决的问题就是寻求权值矩阵使得最小均方误差能够收敛于一稳定值。而这个问题又可以进一步转化为凸优化问题。紧接着文章就凸优化问题提出了几种计算方法，并对它们的权值矩阵和最小均方误差进行了比较。文章考察了一种很经典的迭代算法（即我们一直研究的互同步算法），通过节点和邻居加权求和，即xit+1=j∈NiWij(xj(t))，在此基础上考察叠加随之噪声收敛情况，即xit+1=xit+j∈NiWijxjtDistributedAverageConsensusinSensorNetworkswithRandomLinkFailuresandCommunicationChannelNoise2009（SignalProcessing,IEEETransactionsonDateofPublication:Jan.2009）本文考察的是传感网络中存在随机链路失效和通信信道噪声情况下分布式平均算法。特别是，在每次迭代过程中，通信链路发生随机失效和正常通信链路存在加性随机噪声。作者考虑这种不理想通信场景下A—ND算法分布式平均。采用A—ND算法全网的状态收敛于有限随机变量θ，这里θ是所期望平均值得无偏估计。通过均方误差值（期望值和实际值间）来刻画之一效果的，只要恰当调整算法的参数，可以使均方误差值任意小。但是，如果通过这种方式来一味地减小均方误差值，会降低算法的收敛速度，因此，我们需要在均方误差和收敛速率间做些权衡。与此同时，我们也可以看到，网络拓扑关系对与算法的收敛性也取到非常关键作用。A—ND算法应用场景：网络链路随机性失效（拓扑可能是随机变化）同时传输数据过程中受到加性噪声干扰。文章指出，这种情况下，只要随机网络的拉普拉斯矩阵次大特征值大于零，那么，A—ND算法就几乎可以保证节点状态收敛在一定子空间。同样地，A—ND算法也是基于分布式线性迭代来完成，每个节点通过邻居的状态值加权求和来更新节点当前值，这过程中邻居的状态值在到达本节点时已经发生了变化（到达本节点的值可能已不是之前的值）。文献【29】提到使用以一种递减系列来模拟加性噪声存在，但是它局限于固定性拓扑。本文考查的算法，拓扑可以随机变化，适用范围更广。A-ND迭代算法：这里：链路失效DistributedAverageConsensusinSensorNetworkswithRandomLinkFailures2007（Acoustics,SpeechandSignalProcessing,2007.ICASSP2007.IEEEInternationalConferenceonDateofConference:15-20April2007）

文章考察传感网络中存在链路随机失效情况下的分布式平均算法。文章得出了，基于网络拓扑的拉普拉斯矩阵的范数函数的分布式平均均方误差收敛的条件。而均方误差的收敛性又与拉普拉斯矩阵（此时的矩阵是变化的）的次大特征值密切相关，这样通过计算次大特征值（拉普拉斯矩阵次大特征值均值或拉普拉斯矩阵均值的次大特征值）来讨论均方误差的收敛情况就方便多了。仿真发现，次大特征值较小者，收敛效果更好。文章也提到了前人对于分布式平均研究的一些工作。文献【30】【31】【32】假定网络拓扑是固定，这在实际运用中是不切实际的。文献【07】考察固定性网络，通过对链路权值矩阵来达到对收敛速度的优化。不同以往工作，作者探讨的是网络存在随机链路失效情况下分布式平均算法的设计和分析。因为在实际的通信信道中，通常会受到噪声的干扰，通信链路就可能发生随机性失效。当然，在某些功率受限的网络中，需要某些链路不时地失效，以节省功率和减少干扰。【33】虽然有考虑到类似链路失效问题，但其考察的是完全图，并且所有链路失效的概率都是相同的。而本文中，作者考察的是更一般的拓扑下的分布式平均算法，结果表明，算法的收敛性能和网络矩阵的特征值的概率分布时刻点（moments）密切相关,而这些时刻点是非常难于计算，并且代价很高，基于此，作者将分布式平均算法的收敛性情况转移到考察平均拉普拉斯矩阵的次大特征值。因为，研究平均拉普拉斯矩阵相对简单多了。文章指出，网络的连接不必是概率1来保证均方收敛，只要有平均的连接程度就行。文章表明，更大的平均拉普拉斯矩阵的第二大特征值能带来更好的收敛速度。这里作者考察线性迭代：向量形式：x考虑链路失效，当<n,l>∈E(i),Wnli这里这里只有恰当地选择参量α，迭代算法就会均方收敛的，文中给出了α的值，αms=1其均值：这样，算法的最快收敛速率为：DistributedAverageConsensuswithStochasticCommunicationFailure2007（DecisionandControl,200746thIEEEConferenceonDateofConference:12-14Dec.2007）

文章考察的是，网络通信链路以一定的独立概率失效情况下分布式平均算法。作者以考察的是类李雅普诺夫（Lyapunov-like）递归矩阵的特征值来研究算法的收敛性情况。作者给出了，失效概率较小情况下衰落因子的表达式，同时，对于任何一种拓扑，作者给出了一种不需经过仿真就能够计算衰落因素的方法，借助于该方法，可以通过链路失效概率函数来研究各种网络的行为。文章指出，在静态网络中，分布式平均算法的收敛速度取决于网络拓扑的拉普拉斯矩阵的次大特征值【07】【34】。然而，这种实际网络中，如移动自组网，传感网，由于受到干扰或队列缓存溢出，数据是可能丢失的。同时，早期的考察动态网络拓扑时，分布式平均算法的研究侧重点集中于算法收敛条件的判定（identification）。文献【35】【36】【37】就网络拓扑不时发生变化情况下的动态拓扑给出了收敛条件。文献【38】指出只要始终出现在图例中的成员是连通，那么总能找到一种分布式平均算法是收敛的。文献【39】以对所有通信链路等概率失效情况下的全连通图，网络的收敛条件进行了探究，指出，算法的收敛性取决于平均网络的拉普拉斯矩阵的次大特征值。最近工作，文献【40】将该模型推广的链路以非等概率失效的任意拓扑情况，并建立基于平均拉普拉斯矩阵的收敛的充分条件。正如上文所提到，对于存在链路失效情况下，算法的收敛性研究已经做了不少工作，但是均没有定量地分析随机链路失效对分布式平均算法的收敛速度影响。文中考察的是以任意网络，网络每条边以独立的概率失效。在这样一种随机网络拓扑中，采用均值偏差来定义收敛性，并用一个衰减因子来描述该偏差，该衰减因子是从类李亚普诺夫的迭代矩阵中导出。文章所做的主要工作是：分布式平均算法的收敛速度取决于类李亚普诺夫的迭代矩阵次大特征值，并给出了链路小概率失效时，乘法衰减因子的表达式。并采用一种非模拟仿真的方法来计算各种存在链路失效的拓扑网络下的衰减因子。特别需指出的是，对于某些特定拓扑，通信链路的失效实际上是可以提高提高分布式平均算法的性能的。文中考察线性迭代：定义,A:=I-βL这样，迭代更新为：x又定义，这里的b(i,j)的第i个元素为1，第j个元素为-1，其它为0这样迭代公式变为：这里：再者定义衰减因子来刻画收敛速率，ConvergenceRatesofDistributedAverageConsensusWithStochasticLinkFailures2010（AutomaticControl,IEEETransactionsonDateofPublication:April2010）本文是在上一篇文献《DistributedAverageConsensuswithStochasticCommunicationFailure》中做了改进，文章的上半篇幅基本是重复上述文献的工作，下半篇幅是在此基础上，引入了零均值的加性随机噪声。这样迭代公式就变为，此时，并不采用收敛速率来衡量算法性能，而是，采用偏离各个节点当前均值偏差和来描述，即这里，DistributedAverageConsensusinSensorNetworkswithRandomLinkFailuresandcommunicationchannelnoise2009（SignalProcessing,IEEETransactionsonDateofPublication:Jan.2009）

见上面“存在噪声”分类文献2.流量控制DistributedAveraginginDenseWirelessNetworks2009（GlobalTelecommunicationsConference,2009.GLOBECOM2009.IEEE）作者考察网络吞吐量对一类分布式平均算法的收敛性的影响，算法的收敛性，注意受网络的连接性影响，然而，建立这样的连接性需要额外的网络资源。本文，作者考察随机拓扑下节点构成以密集无线网络下网络的一致性问题。采用马尔科夫链来分析每条通信链路的通断情况，以此来探讨得到网络的最快一致性收敛。待续DistributedAveragingwithFlowConstraints2011（2011AmericanControlConferenceonO'FarrellStreet,SanFrancisco,CA,USAJune29-July01,2011）文章考虑到的是和网络式存储设备相关的平衡问题：通常在许多应用中都偏向于把可利用的资源平均地分布到整个网络之中，例如现代电子交通工具中电池组中电量的平均使用、数据存储网络的数据平衡分配等。因此，和以往的同步平均算法有区别的是，该文章考虑到网络单元不仅仅传输信息，也传输资源，资源的传输会受限于网络信息交换的传输能力的限制，每个设备也只能存储有限量的资源，因此文章提出了考虑到流量控制的分布式算法。在之前的文章中，对分布式算法做的一些限制主要在于节点的控制决策和同步值方面，并且节点所做控制决策仅仅基于节点本身的限制条件，并未考虑到其他节点的控制决策，即各个节点是独立运作的。该文章的方法中，节点必须考虑到网络通信链路的容量限制，节点自身容量限制，节点与相邻节点在进行传输资源以前要对限制条件综合考虑后就传输资源的量达成一致，也就是说节点间协同工作的。在这篇文章中，作者提出了一种非线性的控制算法，能确保网络中相邻的节点能够收敛到一致的数值。该文章的方法也适用于时变的网络拓扑。文章根据[5]的方法进行了修改，使之符合该文章讨论到得流量限制问题，并对效果做了比较。相较于[07]需要一个中心设计的过程，该文章的算法本质上是分布式的。但是文章算法的缺点在计算上是对每个节点都需要有一个多项式规划的解决，而线性控制方法只需要少量的资源。从文章的实验结果来看，在[07]FDLA算法上修改的该算法和FDLA方法在效果上的表现是差不多的，并且该方法能够满足流量限制的限制条件，最终能够达到和原方法一样的同步状态，但是该方法在收敛速度上相对FDLA要慢。迭代方程（离散迭代）：xi+=x这里xi+为下一时刻状态值，xi表示，当前存储在节点i存储的资源，ϕ和拓扑信息相关这里和拓扑信息相关的一些算法，是指，文章提到的算法是针对具体的拓扑类型，如：时变，线状，完全网格图等DistributedAveraginginSensorNetworksBasedonBroadcastGossipAlgorithms2011本文提出了一种基于广播形式的流言算法用于解决传感网络中分布式一致性问题。所提出的算法实际上是对以前大家所熟悉的流言算法的一种改进，改进之处表现在，每次广播后，各节点的初始值的平均值一直被保留。 文中提到分布式平均问题近年来受到了极大关注是因为，算法通信开销小，因此节点只需和邻居通信而不需要获知全网的信息，这样不易出现网络拥塞。 早期流言算法对于分布式一致性问题的研究主要基于无向图（本文作者考究的是有向图，这一点和我们研究方向有出入），节点双向通信，拓扑有时可能变化。要完成双向通信，就需要收发方彼此同步，并且需要一些通信开销。而且，如果节点并不是以广播形式通信，那么节点间的通信是内部，并且是需要按先后次序进行。文章作者尝试在流言算法中采用广播的形式来处理一致性问题。算法中，以一种随机变量的形式，变量不断逼近初始值得平均值，最终得到收敛一致，收敛过程的快慢主要受节点执行广播的先后次序决定。 作者所提出的该新算法，也是基于拉普拉斯矩阵的相关特性来研究一致性问题，最终的结果可以拓展到任意有向图。此外，考虑稳定性在流言算法中的重要性，作者在针对流言算法的稳定性的若干理论问题阐述了。不足之处是，作者并没有对所提算法的收敛性给出证明，尽管最后给出针对不同拓扑算法性能仿真。 每个节点具有三种状态，三种状态下，节点采用不同的更新规则来更新状态值（有别于传统的相互平均来更新状态值）。此外，对于算法的收敛等方面的性能也主要是通过仿真结果来反映，仿真表明，所提出的广播流言算法性能（收敛速度和节能）要优于传统的基于相互平均（邻居双方采用彼此平均值）的流言算法。节点三种状态下更新迭代如下：ALowerBoundforDistributedAveragingAlgorithmsontheLineGraph2011（）作者得出了一类广泛运用的分布式算法收敛速度的下界。而且证明了，对于n个节点的线状网络拓扑，任何分布式平均算法如果其状态值是一个实数，并且其状态更新函数（可能不是线性的）满足自平稳条件（naturalsmoothnesscondition），那么该算法的最次运行次数（是否可以理解为迭代次数？？？）大约为n2。仿真结果表明，增加存储空间对于改善分布式算法的收敛是非常有用的。作者指出，以往的一些一致性算法，基本思想都是：每节点都有一个初始的实数值，通过和最近邻居信息交互来估计全网节点状态平均值，不断迭代最终达到收敛。这些算法最终都可以达到收敛的效果，而且对于链路失效也有一定的健壮性。但是有一个共同的不足，即使是不存在链路失效情况下，算法的收敛时间并不和网络节点数目成比例。作者指出，如果该算法中节点使用一个标量状态值（这里可以理解为没有利用以往的状态值）并且算法满足自平稳条件，那么对于任何这样的分布式平均算法都有上述这一特点，即使是不存在链路失效，拓扑一直是线状扑。作者指出对于上述所提到的一类通用的分布式平均算法（未使用以往的存储状态值但满足自平稳条件）在收敛速率上有一个极限，因此，如果分布式平均算法要克服这一收敛极限，那么算法就需要利用存储单元和更大的状态空间，或是非平稳更新状态。（但是文中似乎没有体现出来） 紧接着，作者回顾了比较经典的三种分布式平均算法：max-degreemethod【55-】，Metropolismethod【07】，load-balancingalgorithm【56】。这里我们着重关注一下负载均衡算法（负载均衡不是本地分布式平均算法，前两者是）。 作者的目标是考察“本地分布式平均算法”的最次情况下的收敛时间，我们发现即便是线状拓扑不发生变化，算法的收敛时间仍不是很好。注意这里收敛时间的定义：对于∀t≥T(n,ϵ)，都有V(x(t))≤ϵ2V(x(0))这里Vxt=自己理解：给定收敛精度条件下，全网达到该收敛精度值所需的最小时间。文献【56】给出并证明了对于任何时变拓扑都有Tn,ϵ≤Cn2Blog1ϵ,即收敛时间的上界（基于负载均衡算法），这里参量C是个绝对常数和拓扑无关，B是和拓扑的链接情况相关。而且作者指出对于任何本地分布式平均算法，收敛时间是有下界限制的，即:Tn,ϵ≥Cn2log1ϵPerformanceEvaluationofsomeDistributedAveragingAlgorithmsforSensorNetworks2011（完全网格网和非网格网）文章是对传感网中分布式平均算法的性能进行评估。作者指出，分布式平均算法通过不断的运算迭代，最终可以达到一致性收敛。这里作者考察了两类的分布式算法，一类是P2P，一类是点对多点。选取了两种P2P算法和一种点对多点算法，实际上，点对多点是对点对点（P2P）的一种变形。作者定义的一些分析方法来考察这三种算法的性能，并对它们的参数进行了优化以提高收敛性。最后进行了仿真比较。 基于节点间通信，作者将算法划分为流言算法和广播算法。流言算法中每个节点最多能和一个邻居通信，这里具体实现为点对点通信，同样，对于广播算法，每个节点可以和任意多个节点（节点在自己通信范围内）通信，这里实现为点对多点,注意这里的广播概念和以往的广播概念不太一样，这里邻居节点获取的信息只为部分的广播信息值，如取源节点广播值的均值（即广播值平摊给各个邻居）。 算法的目就是在尽可能短的时间内，得到全网初始值均值的估计。对于流言算法，作者考察了单向和双向流言算法。同时，作者指出，在完全网格网（fullymeshednetworks，和任何节点都有和其他节点相连的边）中,单向流言算法的收敛速率和双向流言算法的收敛速率相同，而对于非完全网格网（nonfullymeshednetworks，可能没有直接和某些节点相连的边，但可通过中间节点路由到达）双向流言算法的收敛速率要更快。文中比较新颖的一点是提出了“共享因子”（sharefactor）的概念，并定义了势函数（potentialfunction）来对“共享因子”进行优化。流言算法更新规则：（pointtopoint）双向流言算法：这里的参数α即为“sharefactor”,在完全网格网中最优取值为α=1/2。单向流言算法：广播算法更新规则：（pointtomultipoint）很显然，广播算法是单向流言算法的一种变形，邻居在获取源节点广播值时，只是获取部分的邻居值（所以邻居分摊广播值）。上述三种算法，就收敛时间而言，广播算法的性能是最好的。但是，实际中，上述广播算法需采用正交定向天线来实现，而事实上，定向天线只能运用于P2P情况。因而，实际中上述广播算法可能并不是很实用。从上述算法中可以看出，sharefactor的选择对于算法是非常重要的，因此作者采用自己定义的“potentialfunction”，接着又定义了平均“potentialfunction”用了评估算法的收敛速率。综上，作者主要是针对于完全网格网和非完全网格网拓扑下，UG（单向流言算法）和BG（双向流言算法）以及B（广播算法）的收敛情况进行了考察，针对三种算法中的参数（sharefactor），采用了“potentialfunction”来进行优化sharefactor的取值，仿真时主要考察迭代次数和时隙偏差间的关系。DistributedAveraginginDynamicNetworks2011（动态拓扑，粗度）本文作者考察动态拓扑下网络的分布式平均问题。针对网络节点数发送连续变化时，作者提出了动态感知message-passing或者说动态感知gossip算法来获取网络平均值的较好估计。显然这里需要对每个节点对均值的估计精度和网络动态变化速率做一个均衡。作者的算法中对两者做了均衡，并转化成近优化（nearoptimal）。因为算法的精度依赖于动态等级和对基本图的结构。 针对动态拓扑，这里需要处理好算法的精度和系统动态程度。因此，我们希望能够动态感知的健壮算法。对于动态场景，总的来讲共有三类：高速动态场景，普通动态场景，静态或缓慢变化场景。我们的目标就是，考察分布式平均算法在不同场景下算法的性能以及考究网络动态性，拓扑结构域算法性能间关系。为此，针对网络节点数或节点状态值发生变化的动态拓扑，作者引进了一自然模型。对于高速变化场景，我们用在数值上发生乘性变化来模拟，对于普通变化场景，我们用在数值上产生加性变化来模拟。总的结果就是，算法能够动态感知拓扑场景，并能很好地权衡场景动态性和对估计值的精度。 针对快速动态场景，我们采用“乘性变化”来模拟，我们设计了一种算法，算法中用到了指数分布的极值属性，考察不同动态等级指数随机变量和要维持动态拓扑中节点最小个数分布式算法间关系（怎么理解呢）。针对普通和缓慢变化的动态场景，我们采用“加性变化”来模拟，我们考察的是大家所熟知的线性迭代算法。我们发现，这种场景下的估计偏差和通信矩阵的在谱间隙（spectralgap）相关。不管是“加性变化”还是“乘性变化”，节点的状态值的变化都始终有一定的变化边界:对于给定的δ>0（动态等级）加性变化：v∈V,t≥0，有Xv乘性变化：v∈V,t≥0，有e-δ≤(X(t+1)具体地：乘性变化：对于任意给定的p∈0,1,ϵ∈(0,0.35)，总存在随机算法使得每个节点所维持的全局估计值XV对于∀t≥mD这里，m=(3ln⁡(2/p))/(ϵ加性变化：对于经典的线性迭代算法这里λ=λOntheConvergenceofDistributedRandomGroupingforAverageConsensusonSensorNetworkswithTime-varingGraphs2007（时变拓扑）（传感网中时变拓扑下分布式随机分组用于平均一致性的收敛性）时变拓扑的模拟：在不同时刻（这里是基于离散时间）网络拓扑会形成不同的图Gi,所有的图构成图集合{Gi}，单独考察每个图可能是这种场景感觉不太实际，因为拓扑可能形成的图的穷列不了，即便是能够穷列举，当节点数较多时，会构成多状态的马尔科夫链，计算量较大。本文作者提出了一种类传染病（epidemic-like）算法，分布式随机分组算法（DistributedRandomGrouping）DRG，用于无线传感网中时变拓扑下的分布式平均计算。并针对一系列拓扑给出了DRG算法的收敛条件和收敛时间边界，并提出了一种有效途径来计算边界条件中一关键参数。最终通过仿真验证算法有效性。 传感网的连接图可能因为各种原因时刻发生变化，如：链路干扰，拥塞；节点失效；节点为了节能进入睡眠状态或调整功率覆盖范围等。此时的拓扑图是时变的。文献【68】【69】【70】基于时变拓扑提出了各种分布式平均算法，但是它们都是假设拓扑图是固定连接的。本文作为一个特例，针对随机变化的拓扑，分析【68】提到的DRG分布式平均算法。 在解决平均一致性问题中，有两类很典型的算法：一类是tree-basedalgorithms【71】【72】；一类是epidemic-like例如流言算法和DRG算法。 本文的目标是对于随机变化的拓扑，特殊情况下可能始终是不连通的，不仅提出的对于DRG算法的收敛条件，而且得出来的算法的收敛时间。 文献【68】指出DRG算法非常类似于流言算法，但却有更好的性能。流言算法是在节点对间进行数据交互，而DRG算法是在两个以上节点间通过构造分组来提高数据交互速率。DRG算法如下：在每轮的迭代中，每个节点以概率pg成为一个分组的leader，然后广播invitationmessage给其邻居，成功收到invitationmessage的邻居（可能因为存在碰撞而接收不到）加入分组成为这个分组的member。每次分组只能有一个leader，有0个或多个member，这样在全网会形成很多不重叠的分组。每个分组中，member发送自己的状态值给该分组的leader，leader计算依此计算本地平均值，并将平均值反馈给其member具体步骤：每个idlemode节点以概率pg产生分组，并成为给分组的leader成为leader的节点进入leadermode，然后向其邻居广播分组请求信息，GCM（包含分组标识groupid=i），然后等待邻居回复处在idlemode的邻居在成功收到GCM信息后,回复入组确认信息JACK（包含groupid=i,vj,join分组的leader在收到JACK信息后，计算分组中的成员数J=j∈gijoinLeader广播分组分配信息GAM(包含分组标识和分组平均值：groupid=i,Ave(处在membermode的邻居结束GAM信息，更新自己的状态值，vj=Ave(文献【68】指出，对于固定不变拓扑，只有拓扑是联通的，那么算法就会渐进收敛，而且收敛速率不小于：γ≔infv≠v1 接下来，我们考察一般情况下的一致性收敛问题。拓扑是时变的，甚至有时拓扑是非连通的，此时仍然可以达到一致性收敛，只要theunionofthegraphsappearinginfinitelyoftenisconnected（从长远来看，所有图的联合是连通的）。这种场景下DRG算法的收敛条件在文献【68】【73】中给出了，详细的证明见文献【74】。对于时变拓扑下算法的收敛速率的刻画是比较困难的，因为拓扑图在不时地演化。接着作者以两个图的模型为例（构成2个状态的马尔科夫链，两个图以一定概率转化），来说明DRG算法的收敛速率：这里需要考察二次迭代：第一轮迭代：xk+1=W得到收敛速率下界：收敛时间（迭代次数）算法中核心参数K，具体的计算方法见文献【74】，文中作者针对一种较简单的情况下参数k的计算方法：n个节点构成的h=n-1个图的情形，节点按线状分布。其它类Fastlineariterationsfordistributedaveraging2004（具有开创性工作）快速迭代分布式平均算法实际上就是渐进计算节点的初始值得平均值。如果迭代是对称的话，那么寻求快速收敛迭代算法可以看作是半定规划的问题，这样收敛问题就可以得到有效解决。这些最优的线性迭代算法通常要优于那些基于与拓扑相关的拉普拉斯矩阵的启发式算法。对含有上千个节点或边的网络，文章给出了利用问题结构来加快内点法用于最快分布式迭代问题的处理。对于更大规模的网络，如边数达到100000，文章提出了一种简单的次梯度方法来处理最快分布式迭代。文中提到以往的线性一致性同步协议中，权值矩阵或是常数或是仅取决于各节点的节点度【83】【84】。这些简单权值矩阵选取的方法很多都是运用代数图理论一些概念和工具，特别是运用图的拉普拉斯矩阵来对一致性同步协议的收敛性的分析【85】。这篇文章针对线性迭代中更普通情况下的权值矩阵，以及如何选择权值矩阵来达到更好的收敛效果。文章首先对分布式线性迭代收敛于平均向量值时的收敛条件进行了证明，然后将FDLA（考虑渐进收敛因素）的问题转化为谱半径最小化问题。然后给出了FDLA问题的一个变化形式，此时认为权值矩阵是对称的，这样问题可转化成半定规划问题。文章定义了两个收敛参数，收敛因子和收敛时间。从仿真效果可以看出FDLA优化后的权值矩阵收敛因子并没有得到很明显的改善，但收敛时间改善明显，因此可以说FDLA算法优化下的权值的收敛效果要优于先前的那些简单的启发式算法(maximum-degree;weights;local-degreeweights;bestconstantedgeweight)。此外，文章还采用了内点法来解决对称的FDLA问题，依据简单的次梯度方法来处理大规模网络情况。但是，文章的方法也存在一些缺点例如：第一，凸优化过程需要很大量的计算资源，并且对网络造成一定量的延迟。如果网络的拓扑处于持续的变动之中，这样的缺点就会成为一个大问题；第二，该方法不能算是分布式算法，因为应用该方法需要中心节点，该中心节点掌握着网络全局的拓扑信息，例如采用次梯度算法需要了解权值矩阵的第二大特征根。采用最优化常数权值方法也要掌握网络的连接情况。自己对此文一点感想：本文提出了一种经典的线性迭代算法，而且给出了算法的收敛于初始算术平均值的条件，并进行了证明，并定义了收敛相关参数来可以算法的收敛性。后续的很多分布式平均的迭代算法都是在此基础上进行了改进，收敛性的条件也很多是基于此方法进行类推。DualAveragingforDistributedOptimization:ConvergenceAnalysisandNetworkScaling2012(相关性不大)文中提出了一种基于次梯度的双平均分布式算法并且给出算法收敛速度的边界。文中将优化算法本身的收敛性和网络结构的通信限制效应分离开。结果表明优化算法所需的迭代次数与网络的谱距离（spectralgap，1-σ2(P)文章的目标就是解决给定网络的优化问题，为此提出的分布式算法。文中提到了以往两种很常用的分布式计算优化方法，一重分解和二次分解（Primalanddualdecomposition），见文献【01】。同时提到，最近研究的目标转移到了每个本地节点都有它自己的凸目标函数，这些都是些无约束的最优化。文章工作主要有两点：一是提出了一种简单的次梯度算法用于解决有约束性的凸方程的优化问题。文中称之为“双平均次梯度算法：adualaveragingsubgradientmethod”，该方法是计算并维护整个网络次梯度的加权平均值。这种方法较简单，而且和以往的方法有很大不同，能很好地分析网络，并指出该方法的收敛性取决于网络规模和拓扑；另一点是分析证明了该算法收敛性与网络的内在的谱特性之间的关系。文章将该算法的收敛速度划分两个方面：优化方面和网络分离方面。相比前人工作，该算法的收敛效果情况有很大不同。作者首先阐述了分布式最小化问题和分布式双平均算法，然后对算法进行了仿真并对比了前人的工作，接着给出并证明了双平均算法收敛性条件。同时由此得到了一些基于网络谱距离的具体结论。此外，作者还考究了存在噪声情况下算法的性能。Optimaldistributedlinearaveraging2011(相关性不大)本文讲述的是一种新颖的最优分布式线性平均算法（ODLA）。ODLA算法的目标是依此算法来计算拓扑中各个节点的初始值的平均值，同样，拓扑中的节点只能够和自己的邻居进行通信。而该最优化问题，转化为在无界条件下，代价函数（该代价函数是一个二次函数）取最小值。作者指出，ODLA问题和半稳定性的概念有很大关系。通过对离散时间系统的半稳定性的充要条件的探讨研究，ODLA问题最终可以转化成一个等价的有限制约束条件下的优化问题，进而可以采用凸优化方法来解决。一直以来，人们对分布式平均算法的研究点在于算法的收敛性情况，而对其他一些性能算法的最优性却关注的不是很多。这里的最优性定义为，算法在满足收敛，稳定性和网络连接限制条件下，对于确定代价函数取值最小化。本文中，作者将最优化半稳定线性迭代算法等价为一通用代价函数的二次方程来均衡收敛速率和有限资源。这也就是最优分布式线性平均算法（ODLA）。而代价函数方程的提出主要是源于我们需要在状态的收敛性和网络的控制能力间均衡折中。也就是说，要获取更快的收敛速度，就需要在结构性约束条件（怎么理解）下做大量的控制性工作。Convergencespeedindistributedconsensusandaveraging2009本文作者提出了三种分布式平均算法，其中两种用于固定拓扑，另外一种用于动态拓扑，对于固定拓扑，作者考察了所提出的算法与其他一些算法的收敛速率，对于动态拓扑，作者首次就收敛时间提出时间多项式边界（polynomial-timebound）。文章作者所提出的一致性算法收敛速率和基于优化方式的效果相当。接着作者针对固定拓扑阐述了分布式平均算法

Usingtwoparallelpassesoftheagreementalgorithm：采用并行模式的一致性算法。（该算法比较新颖，可以重点考察）：yt+1=Ay(t),zt+1=Az(t),xit=zi(t)/yi(t基于双向生成树：考察了基于生成树等邻居，是不变，双向模型，研究其收敛速率和收敛时间Polynomial-timeaveragingindynamictopologies（该算法也可以重点考察）节点i和节点j间通信，状态值更新方式为：xi=x具体更新步骤：节点广播其当前状态值到其邻居节点节点A从接收到了邻居中查找状态值最小的邻居B，如果该状态值比自己状态值大，那么节点A不做任何处理，反之，节点A向该邻居发送offer=xA-x对于任意节点B，如果没有收到别节点offer，那么节点B不做任何处理，反之，节点B对收到的offer最大的节点反馈acceptance并拒绝其他节点的offer，然后更新自己的状态值x接收到acceptance的节点A更新自己的状态值，x从上面的步骤可以看出，状态值大的节点状态值不断减小，状态值小的节点状态值不断增大，两者不断逼近，最终收敛于两者均值。Ontheconvergencetimeofasynchronousdistributedquantizedaveragingalgorithms2011(关于异步分布式量化平均算法收敛时间)貌似和本问题不是很相关作者重点考察了所提出的量化分布式平均算法的收敛时间问题，并给出了期望收敛时间的多项式边界，该边界是个网络中节