Distributed Asynchronous Algorithms for Solving Positive Definite Linear Equations over Dynamic Networks
Distributed Asynchronous Algorithms for Solving Positive Definite Linear Equations over Dynamic Networks
复制标题
动态网络上求解正定线性方程的分布式异步算法
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Choon Yik Tang
中科院分区：
文献类型：
--
作者：
Jie Lu;Choon Yik Tang
本文开发了一种分布式算法，用于求解具有任意异步交互和成员动态的代理网络上的对称正定线性方程组，其中每个代理可以在任何时候加入和离开网络，无限多次，并且在离开时可能会丢失所有内存。为了设计和分析SE，我们引入了一个随时间变化的Lyapunov函数，定义在一个状态空间与变化的维度，和一个广义的网络连接的概念，能够处理这样的相互作用和成员动态。在此基础上，我们建立了SE的有界性、渐近收敛性和指数收敛性，沿着以及收敛速度的一个界。最后，通过大量的模拟，我们证明了SE在一个易变的代理网络的有效性，并表明，SE的一个特殊情况下，称为Groupwise的优化，是显着更高的带宽/能源效率比现有的两种算法在多跳无线网络。
This paper develops Subset Equalizing (SE), a distributed algorithm for solving a symmetric positive definite system of linear equations over a network of agents with arbitrary asynchronous interactions and membership dynamics, where each agent may join and leave the network at any time, for infinitely many times, and may lose all its memory upon leaving. To design and analyze SE, we introduce a time-varying Lyapunov-like function, defined on a state space with changing dimension, and a generalized concept of network connectivity, capable of handling such interactions and membership dynamics. Based on them, we establish the boundedness, asymptotic convergence, and exponential convergence of SE, along with a bound on its convergence rate. Finally, through extensive simulation, we demonstrate the effectiveness of SE in a volatile agent network and show that a special case of SE, termed Groupwise Equalizing, is significantly more bandwidth/energy efficient than two existing algorithms in multi-hop wireless networks.