基于有向通信拓扑的高阶分布式一致性算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于有向通信拓扑的高阶分布式一致性算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：为了提高有向通信拓扑下分布式一致性算法的收敛速度，提出了一种基于有向通信拓扑的高阶分布式一致性算法。该算法通过有向单跳通信，利用有向二跳邻接节点的前多步信息提高分布式一致性算法的收敛速度。对有向通信拓扑下该算法的收敛性能和收敛速度进行了分析和仿真比较。结果显示，该算法在满足一定条件下能收敛到初始状态的平均值，与其他同样利用二跳邻接节点信息的一致性算法相比，具有通信量小、收敛速度更快的特点，但是能容忍的最大通信延时变小。

关键词：分布式一致性； 多智能体系统； 有向拓扑； 延时； 高阶

0 引言

近年来，多智能体系统的分布式一致性问题在许多领域应用广泛，已经引起许多研究人员的极大关注。

收敛速度是分布式一致性算法的重要研究内容，特别是对于大规模复杂系统。提高分布式一致性算法的收敛速度，关键是提高通信网络拓扑图的代数连通性[1]。现有的分布式一致性算法[1-8]主要通过单跳通信，利用邻接节点的状态进行自身节点状态的更新，收敛速度比较慢。为了提高分布式一致性算法的收敛速度，文献[9]提出通过多跳中继通信，利用非邻接节点的状态进行自身节点状态的更新。由于每个节点获得的节点信息增加，因此这种方法很大程度上提高了分布式一致性算法的收敛速度，但是，多跳中继通信方式复杂，在每次采样间隔中，要求节点间进行多次中继通信，增加了通信要求和通信成本，对中继点的通信负担较重。文献[10]提出了伪二跳中继分布式一致性算法（下面简称伪二跳算法），该算法通过单跳通信，利用二跳邻接节点的信息来进行节点状态更新。与二跳中继分布式一致性算法[9]相比，伪二跳算法由于采用单跳通信，通信方式简单，通信量大大减少，收敛速度与二跳中继分布式一致性算法的收敛速度相当。为了进一步提高分布式一致性算法的收敛速度，文献[10]在伪二跳算法基础上，进一步提出伪多跳中继分布式一致性算法（下面简称伪多跳算法），该算法通过单跳通信，利用多跳邻接节点的信息来进行节点状态更新。伪多跳算法相比伪二跳算法，收敛速度大大提高，但通信量也大大增加。

上述利用非邻接节点信息的分布式一致性算法只考虑了无向通信拓扑下的收敛情况，但是在实际应用中，如电力网络、万维网、神经网络等都是复杂的有向拓扑网络。因此研究如何提高有向通信拓扑下的分布式一致性算法的收敛速度非常必要。文献[11]将伪二跳算法应用在有向通信拓扑上，分析了伪二跳算法在有向拓扑下的收敛性。文献[12]将伪多跳算法应用在有向通信拓扑上，分析了伪多跳算法在有向拓扑下的收敛性，但是伪多跳算法在收敛速度提高的同时，通信量也大大增加。

为了进一步提高有向通信拓扑下的分布式一致性算法的收敛速度，同时又不增加节点间的通信量，在伪二跳算法的基础上，本文提出了一种高阶分布式一致性算法。高阶分布式一致性算法通过有向单跳通信，利用有向二跳邻接节点的前多步信息进行节点状态更新。本文对有向拓扑下的高阶分布式一致性算法的通信量、收敛性能、收敛速度以及带通信延时下的收敛性能进行了分析、计算和仿真比较。

1 有向拓扑下高阶分布式一致性算法

首先，介绍本文需要用到的一些相关概念。有向拓扑图G=（V，E）代表带n个节点的多智能体系统的有向通信拓扑，节点集V内的元素代表智能体，边集E的元素代表智能体之间的通信连接。节点i， j∈V，用有序对（i， j）∈E表示边，边的前后节点分别称之为边的头和尾，信号由节点j传送给节点i。对于有向拓扑G=（V，E），（i， j）≠（j，i）。同节点i相连，且头为i的边数的和，称为节点i的出度，即degout（i）=∑Nj=1ai j；和节点i相连，且尾为i的边数的和，称为节点i的入度，即degin（i）=∑Nj=1aji。如果每个节点的出度等于其入度，则称该图是平衡图。有向路径是指有序节点集（1，2，…，m），其任意相邻的两个有序节点所构成的边（i， j）∈E。如果图G的任意两个有序节点间都存在一条有向路径相连，两节点分别为路径的头与尾，则称有向图G是强连通图。对于节点i，所有满足（i， j）∈E的节点的集合称为i的邻接节点集，用Ni表示节点i的邻接节点集，邻接节点集的元素为节点i的邻接节点。A={ai j}，其中ai j=

本文针对有向通信拓扑，提出一种高阶分布式一致性算法，节点间通过单跳通信进行信息交换，对于有向通信拓扑G=（V，E），每个节点将其状态值和状态派生值传送给有向相邻的节点。有向通信拓扑下的高阶分布式一致性算法可以写成：

其中：xi（k）是节点i在k时刻的状态值， yi（k）是节点i在k时刻的状态派生值， ε是采样间隔，γ 为实参数。在高阶分布式一致性算法中，节点将k时刻的自身状态值和状态派生值传送给有向相邻的节点，而有向相邻节点j在k-1，k-2等时刻的状态值和状态派生值已经分别在k-1，k-2等时刻传送给有向相邻的节点i，并保存在有向相邻的节点i中，因此，在k时刻，节点j需要传送的信息只有xj（k），yj（k）两个值。高阶分布式一致性算法与文献[11]中的有向拓扑下的伪二跳算法的通信量相同，计算量相同；远小于有向拓扑下的伪多跳算法[12]的通信量，计算量也比伪多跳算法的计算量小。