摘要基于Gossip 算法的随机分布式一致性算法可有效地避免信道冲突，降低对各智能体自身计算能力的要求，能够更好的适应分布式网络环境，得到了国内外学者的广泛关注。 本文主要研究了标准Gossip 算法、 Greedy Gossip 算法和Broadcast Gossip 算法三种典型的 Gossip 算法，并利用 Matlab 软件仿真研究上述算法的收敛性，得出三种算法在不同多智能体系统中的收敛速度差异。通过考虑网络拓扑结构对局部信息传递的影响，提出了一种与以上三种经典算法不同的基于节点度的选择概率的改进 Broadcast Gossip 算法。仿真结果表明，本研究得出的改进Broadcast Gossip 算法在含有较多智能体的系统中，收敛速度显著提高。 61086
毕业论文关键词 Gossip 算法 分布式一致性 多智能体
Title The distributed consensus of multi-agent sysytems and its application —— Randomized distributed consensus based on Gossip algorithm
Abstract The research was based on multi-agent of Gossip algorithm randomized distribution consensus issues. Gossip algorithm, Greedy Gossip algorithm and Broadcast Gossip algorithm was studied, which was considered of three typical Gossip algorithms. They were conducted with Matlab simulation research on the convergence performance, which were compared in different multi-agent systems of each algorithm in the convergence speed. To comply the selection probability of agent based on node degree of the problem, this paper put forward an modified Broadcast Gossip algorithm, and its convergence properties are simulated. The result is that by comparing the simulation in different agent system, the modified Broadcast Gossip algorithm, Broadcast Gossip algorithm and Greedy Gossip algorithm convergence rate. Containing a higher proportion in the system of agent, the modified Broadcast Gossip algorithm’s convergence speed was improved.
Keywords Gossip algorithm Distributed consensus multi-agent
目录
1引言2
1.1研究背景2
1.2研究现状3
2典型的模型及常用的一致性算法5
2.1预备知识5
2.2信息同步传输情形.6
2.1.1连续多智能体系统..7
2.1.2离散多智能体系统..8
2.3信息异步传输情形10
2.4本章小结..11
3现有典型的Gossip算法12
3.1标准Gossip算法.12
3.1.1标准Gossip算法及性质..12
3.1.2仿真分析16
3.2GreedyGossip算法.18
3.2.1GreedyGossip算法及性质..18
3.2.2仿真分析20
3.3BroadcastGossip算法.21
3.3.1BroadcastGossip算法及性质..21
3.3.1仿真分析22
3.4三种典型Gossip算法的仿真对比分析..24
3.4本章小结..27
4改进BroadcastGossip算法..28
4.1改进BroadcastGossip算法的时间模型28
4.2改进BroadcastGossip算法的描述.29
4.3仿真分析29
4.3.1改进BroadcastGossip算法的仿真.29
4.3.2与几种典型Gossip算法的对比..31
4.4本章小结34
结论.35
致谢.36
参考文献..37
1 引言 1.1 研究背景 自然界中生命体以种群或群落为单位繁衍和生存，例如鸟群、鱼群、蚁群和细菌菌落等，这些生命体种群内部和种群之间存在着复杂的种内和种间关系，以及其生命活动对环境的适应影响和改变环境。例如自然界中普遍存在的捕食或者迁徙，其中大雁南飞集结起来表现出某种协调一致性的群体行为，在迁徙过程中保持队形的稳定性；沙丁鱼在寻找食物和躲避天敌过程中，不时变换队形。以上群体行为的共性：每个个体仅仅依赖局部信息而表现出群体的协调一致性。 近年来，众多学者逐渐关注这种群体的协调行为。其中有学者受到自然界生物之间的群体行为的启发，提出了多智能体系统的概念。多智能体一般专指多智能体系统或多智能体技术。而前人已对智能体有如下定义：试图在复杂的动态环境中实现一组目标的计算机系统。它具有自主性、社会性、反应性和预动性，甚至某些定义（强定义）还认为智能体具备一些人所特有的性质，源]自=优尔-·论~文"网·www.youerw.com/ 比如知识、信念、意图、义务等行为。即智能体可以在没有人或其它智能体的直接干预下运作，而且对自身的行为和内部状态能进行某种控制；可以与其它智能体（也可能是人）通过某种智能体通信语言进行交流；可以认知环境（可以是一个物质世界，或者其它智能体的集合，或者 Internet，或所有的综合），并对环境所发生的改变做出某种及时的反应；还可以主动展示带有目的性的行为。 本研究中所涉及的多智能体系统的分布式一致性问题，是指在没有中心协调器或全局通信下，每个智能体利用自身的状态和相互通信的邻近智能体的状态进行状态更新，最后所有智能体状态能达到一个共同的输出值。通常情况下，多智能体的分布式一致性是指分布式平均一致性，即每个智能体状态最终达到所有智能体初始状态的平均值。在许多实际应用中，通常都需要考虑所有智能体的状态或者动作行为达到一致。多智能体的分布式一致性在许多领域应用广泛，例如无人飞行器的协调控制，队形控制，蜂拥或群集，分布式传感器网络，负载均衡，振荡器同步，通信网络的拥塞控制等。近年来随着网络通信和计算机的快速发展，多智能体分布式一致性成为当前信息与系统科学的一个热点研究领域。其中 gossip 算法作为多智能体分布式一致问题中的一个重要研究分支，受到国内外学者的广泛关注。在随机分布式一致性算法中，各智能体之间随机建立通信链路，通信拓扑被建立成随机图，可有效的避免信道冲突，降低了对各智能体计算能力的要求，并具有较好的扩展性和鲁棒性，能够更好的适应分布式网络环境。分布式计算的 gossip 算法由于它的简单、分布式特性和在嘈杂和不确定环境下稳定性而吸引人。然而，使用标准 gossip算法会导致重大能源的浪费通过不断循环冗余信息。对于现实的传感器网络模型拓扑结构如网格和随机几何图形，低效率的 gossip 算法与在通信图上随机行走的缓慢加权时间有关。因此深入研究便于实现、可适应复杂网络环境的 gossip 算法具有重要的理论价值和应用前景。 基于Gossip算法的多智能体随机分布式一致性问题研究:http://www.youerw.com/zidonghua/lunwen_66692.html