分布式网络的平均一致估计及优化

发布时间：2018-03-06 02:31

本文选题：平均一致　切入点：收敛速度　出处：《重庆大学》2014年博士论文　论文类型：学位论文

【摘要】：分布式平均算法已经受到极大的关注，由于在分布式网络系统中节点保持简单的状态信息并且只与一跳邻居交换信息.因此，不需要建立或保持复杂的路由结构.而且，网络不会存在由计算可能被对手损坏、丢失或者干扰引起的瓶颈链接(树状或环状结构).最重要的是，平均一致性算法最优异的性质在于算法最终计算的值均可以应用于整个网络，使网络用户询问任何节点都能立即得到一个响应，而不是询问或者等待融合中心的反应.此外，最终计算的值就是网络节点初始测量的平均值，由于其在无线传感器网络中的广泛应用而受到关注.本论文主要致力于分析分布式通信网络的平均一致估计和优化问题，其主要内容和创新之处可概述如下： ①基于广播的随机多Gossip对算法的平均一致估计问题基于无线传感器网络、点对点网络和ad hoc网络的应用和普及，我们提出了一个基于广播的随机多Gossip对算法，算法适用于任意形式连通的网络进行信息交换和计算.不像传统的随机Gossip算法，本章提出的算法是基于push-sum机制的，使得算法在任意时钟周期内都能保存和以及权值，并且允许随机扩散矩阵不是双随机的.基于弱遍历理论和信息传播理论，推导出权值存在下界，并给出了下界的一个估计值.通过引入一个误差势函数，推导出算法以概率1收敛到节点初始状态的平均.此外，本章也提供了扩散速度、-收敛时间以及广播传输次数的上界.最后，通过一个仿真的例子，示例了本章的算法与它相似算法相比较所表现出的优势. ②基于预测机制多智能体网络加速平均一致问题探讨了多智能体网络达到分布式加权平均一致的双积分器的一致加速问题.首先，给出了有向和无向网络收敛到加权平均一致的充要条件，但是收敛速度很慢.为了提升收敛速度，提出一个预测方法加速达到一致，即利用线性预测器通过当前时刻和过去时刻节点的状态来预测将来节点的状态.因此，基于预测机制的一致性协议就变成了原始一致性协议和线性预测器的凸加权和的形式，由于忽略冗余状态，这使得达到加权平均一致的收敛速度变快.而且，对于无向网络，还给出了混合参数的可行域以及最优值.值得指出的是，加速框架已经尽可能地挖掘存储在内存中的当前时刻和过去时刻节点的状态的最大潜能，用以提升收敛速度而不增加存储和计算负担.最后，给出一个仿真实验证明方法的有效性. ③单积分器的多智能体网络的加权平均预测问题讨论了在多智能体网络达到加权平均一致的前提下，如何同时提升网络的鲁棒性以及收敛速度.为了达到这个目的，提出了一个加权平均预测方法，那么网络一致性协议就变为一个时滞的中立型协议.通过运用Hopf分岔分析技术，获得了一个使网络能达到加权平均一致所允许的最大通信时滞.而且，通过理论分析并与原一致性协议相比，所得到的结果不仅增强了网络对于通信时滞的鲁棒性而且提升了网络协议的收敛速度.最后，给出两个仿真实验证明方法的有效性. ④基于时滞次梯度信息的分布式协同优化讨论了带有通信时滞的可计算的多智能体网络的分布式协同优化问题，其中，每个智能体有自己的凸代价函数，，并且协同最小化整个网络的全局代价函数.为了解决这个问题，提出了一个基于对偶平均更新和时滞次梯度信息的算法，通过利用Brgman距离函数分析了衰减步长情况下算法的收敛性质.而且，本章提供了收敛速率的一个紧致上界，它是网络规模和拓扑(表现为逆谱距)的一个函数.最后，给出了一个仿真实验证明了本章的算法与其它相似算法相比表现出的优势.
[Abstract]:Distributed average algorithm has received great attention due to the distributed network nodes in the system to maintain state information is simple and only exchange information with one hop neighbors. Therefore, don't need to establish or maintain routing with complicated structure. Moreover, the network does not exist by calculating the opponent may be lost or damaged, the interference caused by the bottleneck link (or tree ring structure). The most important is the average consensus algorithm is the most excellent properties of final algorithm can be applied to the calculation of the value of the whole network, the network users ask any node can immediately get a response, rather than asking or waiting for the fusion center reaction. In addition, the final calculation value is the initial network node the measured average value, because of its wide application in wireless sensor networks and the average attention. This dissertation focuses on a distributed communication network The main content and innovation of unanimous estimation and optimization can be summarized as follows:
Average uniform estimation of random multiple Gossip pairs based on broadcast
Based on wireless sensor network, peer-to-peer applications and network ad hoc and popularization of the network, we propose a multi Gossip based on random broadcast algorithm, algorithm for communicating with any form of network information exchange and random calculation. Unlike the traditional Gossip algorithm, the proposed algorithm is based on the push-sum mechanism. The algorithm at any clock cycle can be saved and weights, and allows the random diffusion matrix is not double random. Weak ergodic theory and based on the theory of information communication, the weights of existing lower bounds are derived, and gives a lower bound value. By introducing an error function and derive the algorithm convergence by probability 1 the average node initial state. In addition, this chapter also provides the diffusion speed of - convergence time and the upper bound of broadcasting transmission times. Finally, through a simulation example, the example of this chapter is The superiority of the method is compared with its similar algorithm.
Acceleration average consistency problem of multi agent network based on prediction mechanism
Accelerate the consistent multi-agent networks of double integrator distributed weighted average consensus problem. First of all, gives the sufficient and necessary conditions of undirected and weighted network to converge to the average of the same, but the convergence speed is very slow. In order to improve the convergence speed, put forward a prediction method to speed up, namely the use of linear predictor to predict the future status of nodes through the current time and past time node state. Therefore, the consistency protocol based on prediction mechanism becomes the original agreement and convex weighted linear predictor and form, by ignoring the redundant state, which makes the weighted average convergence rate is reached consistent faster. Moreover, for free to network, gives the feasible domain of mixing parameters and the optimal value. It is worth noting that the framework has been accelerated as much as possible mining is stored in the memory of the current and past The maximum potential of nodes at any time is used to improve the convergence speed without increasing the burden of storage and computation. Finally, a simulation experiment is given to demonstrate the effectiveness of the method.
The weighted average prediction problem of the multi agent network of a single integrator
The premise of the weighted average consensus in multi-agent networks, how to enhance the network robustness and convergence speed. In order to achieve this goal, proposes a weighted average forecasting method, then the network consistency protocol is a protocol neutral delay. By using Hopf bifurcation analysis technology, obtain a network can reach the maximum allowable uniform weighted average communication delay. Moreover, through theoretical analysis and compared with the original agreement, the result not only enhances the network robustness to the communication delay and enhance the convergence speed of the network protocol. Finally, gives two effective methods to prove the simulation experiment.
Distributed cooperative optimization based on time-delay subgradient information
This paper discusses the distributed computational multi-agent networks with communication delays of the collaborative optimization problem, where each agent has its own convex cost function, and the collaborative global cost function minimization of the whole network. In order to solve this problem, proposed a based on the average delay time and even update the gradient information through the algorithm. Using the Brgman distance function to analyze the convergence properties of the algorithm step attenuation situation. Moreover, this chapter provides a tight upper bound of convergence rate, it is the network size and topology (expressed as the inverse spectral distance) a function. Finally, a simulation experiment is given to prove the algorithm showed in this chapter compared with other similar algorithms.

【学位授予单位】：重庆大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TN92

【参考文献】