收稿日期:20130118;修回日期:20130307 基金项目:国家自然科学基金资助项目(61104186);江苏省智能传感器网络工程技术研
究开发中心开放基金资助项目(401050611ZK111)
作者简介:彭换新(1973),男,湖南涟源人,博士研究生,主要研究方向为非线性滤波、数据融合(penghx@niit.edu.cn);戚国庆(1977),男,副
研究员,博士,主要研究方向为非线性滤波、数据融合;盛安冬(1964),男,研究员,博导,主要研究方向为满意控制.
离散高阶分布式一致性算法
彭换新
1,2
,戚国庆
2
,盛安冬
2
(1.南京工业职业技术学院 机械系,南京 210046;2.南京理工大学 自动化学院,南京 210094)
摘 要:为了提高分布式一致性算法的收敛速度,提出了一种离散高阶分布式一致性算法。该算法通过单跳通
信,利用二跳邻接节点的前多步信息来加速分布式一致性算法的收敛速度。对无向通信拓扑下该算法的收敛性
能和收敛速度,以及带通信延时的该算法的收敛性能进行了分析和仿真比较,结果显示,该算法在满足条件下能
收敛到初始状态的平均值,与同样利用二跳邻接节点信息的算法相比,具有通信量小,收敛速度更快的特点,但
是能容忍的通信延时变小。
关键词:分布式一致性;多智能体系统;延时;高阶
中图分类号:TP274 文献标志码:A 文章编号:10013695(2013)09270004
doi:10.3969/j.issn.10013695.2013.09.035
Discretetimehighorderdistributedconsensusalgorithm
PENGHuanxin
1,2
,QIGuoqing
2
,SHENGAndong
2
(1.Dept.ofMechanicalEngineering,NanjingInstituteofIndustryTechnology,Nanjing210046,China;2.SchoolofAutomation,Nanjing
UniversityofScience&Technology,Nanjing210094,China)
Abstract:Inordertoimprovetheconvergencerateofdistributedconsensusalgorithms,thispaperproposedadiscretetime
highorderdistributedconsensusalgorithm.Thenewhighorderalgorithmutilizedthepreviousstatevaluesoftwohopadjacency
nodestoacceleratetheconvergenceratebasedonsinglehopcommunication.Theconvergenceperformanceandconvergence
rateofthediscretetimehighorderdistributedconsensusalgorithmwereanalyzedunderundirectednetworks,meanwhile,it
analyzedthediscretetimehighorderdistributedconsensusalgorithmwithcommunicationtimedelay.Itprovidedthesimulation
resultstoverifytheseanalyticalresults,theresultsshowthatanaverageconsensuscanbereachedunderacertaincondition,
theconvergencerateofthehighorderalgorithmissuperiortothoseconsensusalgorithms,butthetimedelayissmallerthan
theotheralgorithmsutilizingtheinformationoftwohopadjacencynodes.
Keywords:distributedaverageconsensus;multiagentsystem;timedelay;highorder
,
引言
近年来,多智能体系统的分布式一致性问题在许多领域应
用广泛,已经引起了许多研究人员的兴趣
[1~9]
。分布式一致性
通常指分布式平均一致性,即所有节点状态能到达初始状态的
平均值。在文献[
1,2]中,OlfatiSaber等人基于一阶算法为分
布式一致性问题建立了一套理论框架。收敛速度是分布式一
致性算法的重要研究内容,特别是对于大规模复杂系统。文献
[1]根据谱图论和拉普拉斯矩阵理论,指出分布式一致性收敛
速度由网络的拓扑结构和局部加权系数确定,收敛速度取决于
网络拓扑图的代数连通性(algebraicconnectivity)。提高分布
式一致性算法的收敛速度,关键是提高网络拓扑图的代数连通
性。目前,提高分布式一致性算法的收敛速度主要有优化网络
拓扑结构
[10,11]
、优化加权系数
[12]
,以及节点间采用不同通信
方式
[13,14]
等
[15,16]
方法。这些方法虽然能在较大程度上提高一
致性算法的收敛速度,但是也存在一些不足。优化网络拓扑结
构能大大提高网络拓扑图的代数连通性,但是对于已经给定的
通信网络拓扑结构则无能为力,同时,必须事先知道整个网络
拓扑结构;优化加权系数方法必须事先知道整个通信网络拓扑
结构;采用不同的通信方式方法的缺点是必须采用特定的通信
方式。
上述分布式一致性算法主要通过单跳通信,利用邻接节点
的状态来进行自身节点状态的更新。为了提高分布式一致性
算法的收敛速度,文献[
14]提出采用多跳中继通信(multihop
delaycommunication)方法,利用非邻接节点的状态进行自身节
点状态的更新。由于每个节点获得的节点信息增加,因此这种
方法很大程度上提高了分布式一致性算法的收敛速度。但是,
多跳中继通信方式复杂,多跳中继通信要求每个采样间隔进行
多次中继通信,增加了通信要求和通信成本,对中继点的通信
负载较重。文献[
17]首先提出了伪二跳分布式一致性算法,
该算法通过单跳通信,利用二跳邻接节点的信息来进行节点状
态更新。与二跳算法相比,伪二跳分布式一致性算法由于采用
单跳通信,通信方式简单,通信量大大减少,收敛速度与二跳算
法的收敛速度相当。为了进一步提高分布式一致性算法的收
敛速度,文献[17]在伪二跳算法基础上提出了伪多跳分布式
一致性算法,该算法通过单跳通信,利用多跳邻接节点的信息
来进行节点状态更新。伪多跳算法相对于伪二跳算法,收敛速
度大大提高,但同时通信量也大大增加。
第 30卷第 9期
2013年 9月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol.30No.9
Sep.2013