Abstract CoDNS Improving DNS Performance and Reliability via Cooperative Lookups

现代电子技术Modern Electronics Technique2023年11月1日第46卷第21期Nov. 2023Vol. 46 No. 210 引 言交通是国民经济的命脉，交通安全与人民群众生命财产安全、社会稳定和长治久安以及国民经济高质量发展密切相关。

道路交通事故占交通事故的绝大多数，据统计，近五年我国道路交通事故年均发生接近25万起，年均造成死亡人数超6万人，财产损失近14亿元，且仍处于道路交通事故发展的上升期。

因此，本文通过对非规则改进DAB⁃DETR 算法的非规则交通对象检测林 峰1，2， 宁琪琳1， 朱智勤2（1.重庆邮电大学 通信与信息工程学院， 重庆 400065； 2.重庆邮电大学 自动化学院， 重庆 400065）摘 要： 非规则交通对象主要指任何在车辆行驶过程中可能对车辆行驶起到阻碍作用的物体，例如坑洼、落石、树枝等影响车辆正常驾驶的目标。

针对道路中的非规则交通对象检测问题，提出一种基于改进DAB⁃DETR 算法的非规则交通对象目标检测算法，经过对原始模型结构的分析，发现在图像特征输入编码器前加入绝对位置编码来弥补图像位置信息的缺失，只能隐式地表达特征间的相对位置信息，因此改进DAB⁃DETR 在Transformer 的编码结构中的多头自注意力机制中添加了针对图像的相对位置编码；其次发现在原始训练策略中，对得到的检测定位结果与类别信息进行二分匹配并计算损失值时，只是简单地将定位损失和分类损失加权求和，这样会导致性能下降，所以在训练策略中增加了将分类、定位损失集成在一个统一参数化公式中的AP 损失函数。

实验结果表明：改进DAB⁃DETR 算法的检测精度达到了82.00%，比原始模型提高了3.3%，比传统模型Faster R⁃CNN 、YOLOv5分别提高了6.20%、7.71%。

关键词： 非规则交通对象； 目标检测； DAB⁃DETR 算法； 相对位置编码； AP 损失函数； 消融实验中图分类号： TN911.73⁃34； TP751 文献标识码： A 文章编号： 1004⁃373X （2023）21⁃0141⁃08Irregular traffic object detection by improved DAB⁃DETR algorithmLIN Feng 1, 2, NING Qilin 1, ZHU Zhiqin 2(1. School of Communications and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China;2. School of Automation, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)Abstract ： Irregular traffic objects mainly refer to any objects that may play an obstructive role in vehicle driving, such as potholes, falling rocks, tree branches and other objectives that affect the normal driving of vehicles. Therefore, an irregular traffic object detection algorithm based on improved DAB⁃DETR (dynamic anchor boxes are better queries for DETR) is proposed. Byanalyzing the structure of the original model, it is found that the absolute position encoding is added before the image features are input into the encoder to make up for the lack of image location information can only implicitly show the relative location information between features. Therefore, in the improved DAB ⁃DETR algorithm, the relative location encoding for images isadded to the multi⁃headed self⁃attention mechanism in the encoding structure of transformer. When binary matching is carriedout on both the obtained detection and positioning results and the category information and then the loss value is calculated, the localization loss and classification loss are simply weighted and summed, which may lead to decreased performance, so an AP loss function that integrates the classification and localization losses in a unified parameterized formula is added to the improved strategy. The experimental results show that the detection accuracy of the improved DAB ⁃DETR algorithm can reach 82.00%,which is 3.3% higher than that of the original model, and 6.20% and 7.71% higher than those of the traditional models Faster R⁃CNN and YOLOv5, respectively.Keywords ： irregular traffic object; object detection; DAB ⁃DETR algorithm; relative position encoding; AP loss function;ablation experimentDOI ：10.16652/j.issn.1004⁃373x.2023.21.026引用格式：林峰，宁琪琳，朱智勤.改进DAB⁃DETR 算法的非规则交通对象检测[J].现代电子技术，2023，46（21）：141⁃148.收稿日期：2023⁃05⁃10 修回日期：2023⁃05⁃29基金项目：重庆市教委“成渝地区双城经济圈建设”科技创新项目（KJCXZD2020028）141现代电子技术2023年第46卷交通对象（任何在车辆行驶过程中可能对车辆行驶起到阻碍作用的物体）检测的研究来减少道路交通事故的发生。

2022年5月25日第6卷第10期现代信息科技Modern Information TechnologyMay.2022 Vol.6 No.1016基于信誉值的实用拜占庭容错改进算法研究王启河（华北电力大学 控制与计算机工程学院，河北 保定 071003）摘 要：共识问题是区块链中的核心问题，针对联盟链常用的实用拜占庭容错算法（PBFT ）中主节点选取随意、网络通信量大、公平性较低等问题，提出一种基于信誉值的PBFT 改进算法。

首先改变信誉值主节点选取方式，然后优化共识流程，节点的累计信誉作为判断达成共识的条件。

达成共识时没有参与共识过程的节点或恶意节点的信誉值降低，降低的信誉值均分给成功参与共识的节点。

经过多次共识后，故障或恶意节点对共识的影响变小，提高了算法的公平性。

关键词：联盟链；实用拜占庭容错算法；共识机制；信誉值；公平性中图分类号：TP311.5文献标识码：A文章编号：2096-4706（2022）10-0016-05Research on Improved Algorithm of Practical Byzantine Fault Tolerance Based onReputation ValueWANG Qihe(School of Control and Computer Engineering, North China Electric Power University, Baoding 071003, China)Abstract: The consensus problem is the core problem in the blockchain. In view of the problems of arbitrary master node selection, large amount of network communication and low fairness of the Practical Byzantine Fault Tolerance (PBFT), which is commonly used in coalition chains, an improved algorithm of PBFT based on reputation value is proposed. Firstly, it changes the selection mode of reputation value master node. Then the consensus process is optimized, and the accumulated reputation of nodes is used as a condition to judge reaching consensus. The reputation value of nodes that do not participate in the consensus process or malicious nodes is reduced when consensus is reached, and the reduced reputation value is equally distributed to the nodes that successfully participate in consensus. After multiple consensus, the impact of the fault or malicious node on the consensus becomes small and the fairness of the algorithm is improved.Keywords: coalition chain; practical Byzantine fault tolerant algorithm; consensus mechanism; reputation value; fairness0 引 言近2008年中本聪[1]提出一种点对点的电子现金系统即比特币，使得区块链底层技术得到了社会广泛关注。

ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００３－３１１４．２０２４．０１．００５引用格式：李尧，高岩，张淅，等．太赫兹固态通信系统技术发展现状与挑战［Ｊ］．无线电通信技术，２０２４，５０（１）：４１－５７．［ＬＩＹａｏ，ＧＡＯＹａｎ，ＺＨＡＮＧＸｉ，ｅｔａｌ．ＯｖｅｒｖｉｅｗｏｆＴｅｒａｈｅｒｔｚＳｏｌｉｄ ｓｔａｔｅＣｏｍｍｕｎｉｃａｔｉｏｎＳｙｓｔｅｍＴｅｃｈｎｏｌｏｇｙＤｅｖｅｌｏｐｍｅｎｔＳｔａｔｕｓａｎｄＣｈａｌ ｌｅｎｇｅｓ［Ｊ］．ＲａｄｉｏＣｏｍｍｕｎｉｃａｔｉｏｎｓＴｅｃｈｎｏｌｏｇｙ，２０２４，５０（１）：４１－５７．］太赫兹固态通信系统技术发展现状与挑战李　尧１，高　岩１，张　淅２，秦雪妮１，周雨萌１，３，赵　亮１，郑　重２，费泽松２，３，于伟华１，４（１．北京理工大学集成电路与电子学院，北京１０００８１；２．北京理工大学信息与电子学院，北京１０００８１；３．北京理工大学长三角研究院，浙江嘉兴３１４０９９；４．北京理工大学重庆微电子研究院，重庆４０００３１）摘　要：太赫兹固态通信系统被认为是下一代通信的重要技术备选方案，其高速、实时、大容量传输特性为“万物智联”提供了可能。

当前，太赫兹固态通信系统面临诸多技术挑战。

为进一步推动太赫兹固态通信系统研制，梳理了太赫兹波段信号调制、固态器件、天线以及收发系统的研究进展与关键技术，并剖析了太赫兹通信系统未来的发展方向。

太赫兹固态通信系统将进一步加快通信系统小型化研究，促进信号、器件、芯片、系统等多项技术深度优化融合，为商业化应用提供技术基础。

关键词：太赫兹通信；功率放大器；低噪声放大器；片上天线；太赫兹固态电路中图分类号：ＴＮ７６１；Ｏ４５２ 文献标志码：Ａ 开放科学（资源服务）标识码（ＯＳＩＤ）：文章编号：１００３－３１１４（２０２４）０１－００４１－１７ＯｖｅｒｖｉｅｗｏｆＴｅｒａｈｅｒｔｚＳｏｌｉｄ ｓｔａｔｅＣｏｍｍｕｎｉｃａｔｉｏｎＳｙｓｔｅｍＴｅｃｈｎｏｌｏｇｙＤｅｖｅｌｏｐｍｅｎｔＳｔａｔｕｓａｎｄＣｈａｌｌｅｎｇｅｓＬＩＹａｏ１，ＧＡＯＹａｎ１，ＺＨＡＮＧＸｉ２，ＱＩＮＸｕｅｎｉ１，ＺＨＯＵＹｕｍｅｎｇ１，３，ＺＨＡＯＬｉａｎｇ１，ＺＨＥＮＧＺｈｏｎｇ２，ＦＥＩＺｅｓｏｎｇ２，３，ＹＵＷｅｉｈｕａ１，４（１．ＳｃｈｏｏｌｏｆＩｎｔｅｇｒａｔｅｄＣｉｒｃｕｉｔｓａｎｄＥｌｅｃｔｒｏｎｉｃｓ，ＢｅｉｊｉｎｇＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ１０００８１，Ｃｈｉｎａ；２．ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎａｎｄＥｌｅｃｔｒｏｎｉｃｓ，ＢｅｉｊｉｎｇＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ１０００８１，Ｃｈｉｎａ；３．ＹａｎｇｔｚｅＤｅｌｔａＲｅｇｉｏｎＡｃａｄｅｍｙｏｆＢｅｉｊｉｎｇＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，Ｊｉａｘｉｎｇ３１４０９９，Ｃｈｉｎａ；４．ＢＩＴＣｈｏｎｇｑｉｎｇＩｎｓｔｉｔｕｔｅｏｆＭｉｃｒｏｅｌｅｃｔｒｏｎｉｃｓａｎｄＭｉｃｒｏｓｙｓｔｅｍｓ，Ｃｈｏｎｇｑｉｎｇ４０００３１，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｅｒａｈｅｒｔｚｓｏｌｉｄ ｓｔａｔｅｃｏｍｍｕｎｉｃａｔｉｏｎｓｙｓｔｅｍｈｏｌｄｓｇｒｅａｔｐｒｏｍｉｓｅａｓａｔｅｃｈｎｏｌｏｇｉｃａｌａｌｔｅｒｎａｔｉｖｅｆｏｒｎｅｘｔｇｅｎｅｒａｔｉｏｎｏｆｃｏｍ ｍｕｎｉｃａｔｉｏｎ，ｔｈａｎｋｓｔｏｉｔｓｈｉｇｈ ｓｐｅｅｄ，ｒｅａｌ ｔｉｍｅ，ａｎｄｈｉｇｈ ｃａｐａｃｉｔｙｔｒａｎｓｍｉｓｓｉｏｎｃａｐａｂｉｌｉｔｉｅｓｔｈａｔｓｕｐｐｏｒｔＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ＆Ｉｎｔｅｒ ｎｅｔｏｆＴｈｉｎｇｓａｐｐｌｉｃａｔｉｏｎｓ．Ｈｏｗｅｖｅｒ，ｔｅｒａｈｅｒｔｚｓｏｌｉｄ ｓｔａｔｅｃｏｍｍｕｎｉｃａｔｉｏｎｓｙｓｔｅｍｓｃｕｒｒｅｎｔｌｙｆａｃｅｓｅｖｅｒａｌｔｅｃｈｎｏｌｏｇｉｃａｌｃｈａｌｌｅｎｇｅｓ．Ｔｏｆｏｓｔｅｒｔｈｅｉｒｄｅｖｅｌｏｐｍｅｎｔ，ｔｈｉｓｏｖｅｒｖｉｅｗｓｕｍｍａｒｉｚｅｓｒｅｓｅａｒｃｈｐｒｏｇｒｅｓｓａｎｄｋｅｙｔｅｃｈｎｉｃａｌｄｉｒｅｃｔｉｏｎｓｉｎｔｅｒａｈｅｒｔｚｂａｎｄｓｉｇｎａｌｍｏｄｕｌａｔｉｏｎ，ｓｏｌｉｄ ｓｔａｔｅｄｅｖｉｃｅｓ，ａｎｔｅｎｎａｓ，ａｎｄｔｒａｎｓｃｅｉｖｅｒｓｙｓｔｅｍｓ．Ｉｔａｎａｌｙｚｅｓｆｕｔｕｒｅｄｅｖｅｌｏｐｍｅｎｔｄｉｒｅｃｔｉｏｎｏｆｔｅｒａｈｅｒｔｚｃｏｍｍｕｎｉｃａｔｉｏｎｓｙｓｔｅｍｓ．Ｕｌｔｉｍａｔｅｌｙ，ｔｅｒａｈｅｒｔｚｓｏｌｉｄ ｓｔａｔｅｃｏｍｍｕｎｉｃａｔｉｏｎｓｙｓｔｅｍｉｓａｂｌｅｔｏｓｔｉｍｕｌａｔｅａｄｖａｎｃｅｍｅｎｔｓｉｎｃｏｍｍｕｎｉｃａｔｉｏｎｓｙｓｔｅｍｍｉｎｉａｔｕｒｉｚａｔｉｏｎａｎｄｈａｒｍｏｎｉｚｅｖａｒｉｏｕｓｔｅｃｈｎｏｌｏｇｉｅｓｉｎｓｉｇｎａｌ，ｄｅｖｉｃｅｓ，ｃｈｉｐ，ｓｙｓｔｅｍｓｅｓｔａｂｌｉｓｈｉｎｇａｓｏｌｉｄｔｅｃｈｎｏｌｏｇｉｃａｌｆｏｕｎｄａｔｉｏｎｆｏｒｃｏｍｍｅｒｃｉａｌａｐｐｌｉｃａ ｔｉｏｎｓ．Ｋｅｙｗｏｒｄｓ：ｔｅｒａｈｅｒｔｚｃｏｍｍｕｎｉｃａｔｉｏｎ；ｐｏｗｅｒａｍｐｌｉｆｉｅｒ；ｌｏｗ ｎｏｉｓｅａｍｐｌｉｆｉｅｒ；ｏｎ ｃｈｉｐａｎｔｅｎｎａ；ｔｅｒａｈｅｒｔｚｓｏｌｉｄ ｓｔａｔｅｃｉｒｃｕｉｔ收稿日期：２０２３－１０－２８基金项目：北京市科技计划（Ｚ２１１１００００４４２１０１２）；北京理工大学重庆微电子研究院专项计划（２０２２ＣＸ０５００００３）ＦｏｕｎｄａｔｉｏｎＩｔｅｍ：ＢｅｉｊｉｎｇＭｕｎｉｃｉｐａｌＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＰｒｏｊｅｃｔ（Ｚ２１１１００００４４２１０１２）；ＳｐｅｃｉａｌＦｕｎｄｏｆＢＩＴＣｈｏｎｇｑｉｎｇＩｎｓｔｉｔｕｔｅｏｆＭｉｃｒｏｅｌｅｃｔｒｏｎｉｃｓａｎｄＭｉｃｒｏｓｙｓｔｅｍｓ（２０２２ＣＸ０５００００３）０　引言自２０世纪８０年代以来，移动通信系统基本按照每１０年迭代的速率进行演进。

A Sufficient Condition for Convergence of Sampled-DataConsensus for Double-Integrator Dynamics With Nonuniform and Time-Varying Communication Delays Jiahu Qin,Student Member,IEEE,andHuijun Gao,Senior Member,IEEEAbstract—This technical note investigates a discrete-time second-order consensus algorithm for networks of agents with nonuniform and time-varying communication delays under dynamically changing communica-tion topologies in a sampled-data setting.Some new proof techniques are proposed to perform the convergence analysis.It isfinally shown that under certain assumptions upon the velocity damping gain and the sampling pe-riod,consensus is achieved for arbitrary bounded time-varying commu-nication delays if the union of the associated digraphs of the interaction matrices in the presence of delays has a directed spanning tree frequently enough.Index Terms—Double-integrator agents,sampled-data consensus,span-ning tree,time-varying communication delays.I.I NTRODUCTIONIn recent years,consensus problems for agents with single-integrator dynamics have been studied from various perspectives(see,e.g.,[4], [7],[10],[11],[14],[16],[17],[26]).Taking into account that double-integrator dynamics can be used to model more complicated systems in reality,cooperative control for multiple agents with double-integrator dynamics has been studied extensively recently,see[12],[18]–[20], [23],[28]for continuous algorithms and[1]–[3],[5],[6],[8],[13]for discrete-time algorithms.In[8],a sampled-data algorithm is studied for double-integrator dy-namics through a Lyapunov-based approach.The analysis in[8]is lim-ited to an undirected network topology and cannot be extended to deal with the directed case.However,the informationflow might be directed in practical applications.In a similar sampled-data setting,[1]studies two sampled-data consensus algorithms,i.e.,the case with an absolute velocity damping term and the case with a relative velocity damping term,in the context of a directed network topology by extensively using matrix spectral analysis.Reference[2]extends the algorithms in[1]to deal with a dynamic directed network topology.References[5]and[6] mainly investigate sampled-data consensus for the case with a relative velocity damping term under a dynamic network topology.In[5],the network topologies are required to be both balanced and strongly con-nected at each sampling instant.On the other hand,considering that it might be difficult to measure the velocity information in practice,[6] Manuscript received November17,2009;revised September15,2010; August15,2011,and January24,2012;accepted January25,2012.Date of publication February17,2012;date of current version August24,2012.This work was supported in part by the National Natural Science Foundation of China under Grants60825303,60834003,and61021002,by the973Project (2009CB320600),and by the Foundation for the Author of National Excellent Doctoral Dissertation of China(2007B4).Recommended by Associate Editor H.Ito.J.Qin is with Harbin Institute of Technology,Harbin,China,and also with the Australian National University,Canberra,A.C.T.,Australia(e-mail:jiahu. qin@.au).H.Gao is with the Research Institute of Intelligent Control and Systems, Harbin Institute of Technology,Harbin150001,China(e-mail:hjgao@. cn).Color versions of one or more of thefigures in this paper are available online at .Digital Object Identifier10.1109/TAC.2012.2188425proposes a consensus strategy using the measurements of the relative positions between neighboring agents to estimate the relative velocities. In[13],consensus problems of second-order multi-agent systems with nonuniform time delays and dynamically changing topologies is investigated.However,the paper considers a discrete-time model es-timated by using the forward difference approximation method rather than a sampled-data model.In general,a sampled-data model is more realistic.Also,in[13],the weighting factors must be chosen from a finite set.With this background,we study the convergence of sam-pled-data consensus for double-integrator dynamics under dynamically changing topologies and allow the communication delays to be not only different but also time varying.Here,considering the weighting factors of directed edges between neighboring agents usually represent confi-dence or reliability of the transmitted information,it is more natural to consider choosing the weighting factors from an infinite set,which is more general than thefinite set case in[2]and[13].Moreover,dif-ferent from that in[13],A(k),the interaction matrix in the presence of delays at time t=kT,is introduced in this technical note and the dif-ference between A(k)and A(k),the adjacency matrix at time t=kT, is further explored as well.The reason for introducing A(k)is that it is more relevant than A(k)to the strategies investigated in this technical note.It is worth pointing out that the method employed to perform the convergence analysis is totally different from most of the existing liter-ature which heavily relies on analyzing the system matrix by spectral analysis.By using the similar transformation as that used in[13],we can treat the sampled-data consensus for double-integrator dynamics as the consensus for multiple agents modeled byfirst-integrator dynamics. Then,in order to make the transformed system dynamics mathemati-cally tractable,a new graphic method is proposed to specify the rela-tions between0(A(k)),the associated digraph of the interaction matrix in the presence of delays,and the the associated digraph of the trans-formed system matrix.Finally,motivated by the work in[22,Theorem 2.33]and[27],by employing the product properties of row-stochastic matrices from an infinite set,we present a sufficient condition in terms of the associated digraph of the interaction matrix in the presence of delays for the agents to reach consensus.Note here that the proving techniques employed in this technical note can be extended directly to derive similar results by considering the discrete-time model in[13]. The rest of the technical note is organized as follows.In Section II, we formulate the problem to be investigated and also provide some graph theory notations,while the convergence analysis is given in Section III.In Section IV,a numerical example is provided to show the effectiveness of the new result.Finally,some concluding remarks are drawn in Section V.II.B ACKGROUND AND P RELIMINARIESA.NotationsLet I n2n2n and0n;n2n2n denote,respectively,the identity matrix and the zero matrix,and1m2m be the column vector of all ones.Letand+denote,respectively,the set of nonnegative and positive integers.Given any matrix A=[a ij]2n2n,let diag(A) denote the diagonal matrix associated with A with the ith diagonal element equal to a ii.Hereafter,matrices are assumed to be compatible for algebraic operations if their dimensions are not explicitly stated.A matrix M2n2n is nonnegative,denoted as M 0,if all its entries are nonnegative.Let N2n2n.We write M N if M0N 0.A nonnegative matrix M is said to be row stochastic if all its row sums are1.Let k i=1M i=M k M k01111M1denote the left product of the matrices M k;M k01;111;M1.A row-stochastic matrix M is ergodic0018-9286/$31.00©2012IEEE(or indecomposable and aperiodic )if there exists a column vector f2nsuch that lim k !1M k =1n f T .B.Graph Theory NotationsLet G =(V ;E ;A )be a weighted digraph of order n with a finite nonempty set of nodes V =f 1;2;...;n g ,a set of edges E V 2V ,and a weighted adjacency matrix A =[a ij ]2n 2n with nonnegative adjacency elements a ij .An edge of G is denoted by (i;j ),meaning that there is a communication channel from agent i to agent j .The adjacency elements associated with the edges are positive,i.e.,(j;i )2E ,a ij >0.Moreover,we assume a ii =0for all i 2V .The set of neighbors of node i is denoted by N i =f j 2V :(j;i )2Eg .Denote by L =[l ij ]the Laplacian matrix associated with G ,where l ij =0a ij ,i =j ,and l ii=n k =1;k =i a ik .A directed path is a sequence of edges in a digraph of the form (i 1;i 2);(i 2;i 3);....A digraph has a directed spanning tree if there exists at least one node,called the root node,having a directed path to all the other nodes.A spanning subgraph G s of a directed graph G is a directed graph such that the node set V (G s )=V (G )and the edge set E (G s ) E (G ).Given a nonnegative matrix S =[s ij ]2n 2n ,the associated di-graph of S ,denoted by 0(S ),is the directed graph with the node set V =f 1;2;...;n g such that there is an edge in 0(S )from j to i if and only if s ij >0.Note that for arbitrary nonnegative matrices M;N2p 2p satisfying M N ,where >0,if 0(N )has a di-rected spanning tree,then 0(M )also has a directed spanning tree.C.Sampled-Data Consensus Algorithm for Double-Integrator DynamicsEach agent is regarded as a node in a digraph G of order n .Let T >0denote the sampling period and k2denote the discrete-time index.For notational simplicity,the sampling period T will be dropped in the sequel when it is clear from the context.We consider the following sampled-data discrete-time system which has been investigated in [1],[2],and [8]asr i (k +1)0r i (k )=T v i (k )+12T 2u i (k )v i (k +1)0v i (k )=T u i (k )(1)where x i (k )2p ,v i (k )2p and u i (k )2p are,respectively,the position,velocity and control input of agent i at time t =kT .For simplicity,we assume p =1.However,all results still hold for any p2+by introducing the notation of Kronecker product.In this technical note,we mainly consider the following discrete-time second-order consensus algorithm which takes into account the nonuniform and time-varying communication delays as u i (k )=0 v i (k )+j 2N (k )ij (k )(r j (k 0 ij (k ))0r i (k ))(2)where >0denotes the absolute velocity damping gain,N i (k )de-notes the neighbor set of agent i at time t =kT that varies with G (k )(i.e.,the dynamic communication topology at time t =kT ), ij (k )>0if agent i can receive the delayed position r j (k 0 ij (k ))from agent j at time t =kT while ij (k )=0otherwise,and 0 ij (k ) max ,where ij (k )2,is the communication delay from agent j to agent i .Here,we assume ii (t ) 0,that is,the time delays affect only the in-formation that is transmitted from one agent to another.Moreover,we assume that all the nonzero and hence positive weighting factors areboth uniformly lower and upper bounded,i.e., ij (k )2[ ;],where 0< < ,if j 2N i (k ).Remark 1:In general,(j;i )2E (G (k ))or a ij (k )>0,which cor-responds to an available communication channel from agent j to agent i at time t =kT ,does not imply ij (k )>0even if the reverse is true.This is mainly because the communication topologies are dynamicallychanging and the communication delays are time varying,which may destroy the continuity of information.Note that ij (k )>0requires a ij >0for the whole time between k 0 ij (k )and k .DefineA (k )= 11(k )111 1n (k )......... n 1(k )111 nn (k):To distinguish A (k )from the adjacency matrix A (k )at time t =kT ,we call A (k )the interaction matrix in the presence of delays to em-phasize that A (k )is closely related to not only the available commu-nication channel but also the information transmission in the presence of delays.Let L (k )be L (k )=D (k )0A (k ),where D (k )is a diag-onal matrix with the i th diagonal entrybeing n j =1;j =i ij (k ).In fact,0(A (k )),the associated digraph of A (k ),is a spanning subgraph of the communication topology G (k )at time t =kT .To illustrate,consider a team of n =3agents.The possible communication topologies are modeled by the digraph as shown in Fig.1.Assume the communica-tion delays 21(k )and 32(k ),k2,are all larger than 1T ,while the communication topology switches periodically between Ga and Gb at each sampling instant.Clearly,A (k )=03;3at each sampling instant.However,in the special case that there is no communication delay be-tween neighboring agents,0(A (k ))=G (k ).In the case that both the communication topology and the communication delays are time in-variant,0(A (k ))=G (k )after max time steps.We say that consensus is reached for algorithm (2)if for any initial position and velocity states,and any i;j 2Vlim k !1r i (k )=lim k !1r j (k )and lim k !1v i (k )=0:It is assumed that r i (k )=r i (0)and v i (k )=v i (0)for any k <0and i;j 2V .III.M AIN R ESULTSDenote G=f G 1;G 2;...;G m g as the finite set of all possible com-munication topologies for all the n agents.In the sequel,when we men-tion the union of a group of digraphs f G i ;...;G i g G,we mean a digraph with the node set V =f 1;2;...;n g and the edge set given by the union of the edge sets of G i ,j =1;...;k .Firstly,we perform the following model transformation,which helps us deal with the consensus problem for an equivalent trans-formed discrete-time system.Denote r (k )=[r 1(k );111;r n (k )]T ,v (k )=[v 1(k );111;v n (k )]T ,x (k )=(2= )v (k )+r (k ),andy (k )=[r (k )T x (k )T ]T.Then,applying algorithm (2)and by some manipulation,(1)can be written in a matrix form asy (k +1)=40(k )y (k )+`=14`(k )y (k 0`)(3)where we get the equation shown at the bottom of the next page,and 4`(k )=T2A `(k )0n;n2T +12T 2A `(k )0n;n;`=1;2;...; max :Here in 4p (k ),p =0;1;...; max ,the ij th element of A p (k )is either equal to ij (k )if ij (k )=p ,or equal to 0otherwise and L (k )is the Laplacian matrix of the digraph of A (k ).1ObviouslyA 0(k )+A 1(k )+111+A(k )=A (k ):The following lemma will allow us to perform the convergence anal-ysis by using the product properties of row-stochastic matrices.1NoteL (k )is different from the Laplacian matrix of the communicationtopology G(k).Fig.1.Two possible communication topologies for the three agents.Lemma 1:Let d (k )be the largest diagonal element of the Lapla-cian matrix L (k ),i.e.,d (k )=max if n j =1;j =i ij (k )g .If the ve-locity damping gain and the sampling period T satisfy the following condition:4 T 0 T >2and T 01 2T d (k )(4)then 4(k )=40(k )+41(k )+111+4(k );k2+,is a row-stochastic matrix with positive diagonal elements.Proof:It follows from A 0(k )+A 1(k )+111+A(k )=A (k )=diag L (k )0L (k )that4(k )=40(k )+41(k )+111+4(k )=411(k )412(k )421(k )422(k )(5)where 411(k )=(10( =2)T +( 2=4)T 2)I n 0(T 2=2)L (k ),412(k )=(( =2)T 0( 2=4)T 2)I n ,421(k )=(( =2)T +( 2=4)T 2)I n 0((2= )T +(1=2)T 2)L (k )422(k )=(10( =2)T 0( 2=4)T 2)I n .One can easily check from (4)that all the matrices 411(k ),412(k ),421(k ),and 422(k )are nonnegative with positive di-agonal elements.That is,4(k )is a nonnegative with positive diagonal elements.Finally,it follows straightforwardly from L (k )1n =1n that 4(k )is a row-stochastic matrix.Remark 2:By some manipulation,we can get that (4)is equivalent to the following condition:1+1+8T 2d (k )2T <p 501:(6)This is achieved by solving ( T )2+2 T 04<0and T 20 02T d (k ) 0,which can be considered the quadratic inequalities in T and ,respectively.In the sequel,4(k )will be used to denote the row-stochastic matrix as described in Lemma 1.In order to make the transformed system dynamics mathematically tractable in terms of 0(A (k )),the associated digraph of the interaction matrix in the presence of delays,we need to explore the relations be-tween 0(A (k ))and the associated digraph of the transformed system matrix 0(4(k )).To this end,a new graphic method is proposed as follows.Lemma 2:Given any digraph G (V ;E ).Let G 1(V 1;E 1)be a graph with n nodes and an empty edge set,that is,V 1=f n +1;n +2;...;2n g and E 1=.Let ~G(~V ;~E )be a digraph satisfying the fol-lowing conditions:(A)~V=V [V 1=f 1;...;n;n +1;...;2n g ;(B)there is an edge from node n +i to node i ,i.e.,(n +i;i )2~",for any i 2V ;(C)if (j;i )2E ,then (j;n +i )2~Efor any i;j 2V ;i =j .Then,G has a directed spanning tree if and only if ~Ghas a directed spanning tree.Proof:Necessity:Denote G s as a directed spanning tree of the digraph G .Assume,without loss of generality,`is the root node of G s .By rules (B )and (C ),split each edge (i;j )in G s into edges (i;n +j );(n +j;j )and add edge (n +`;`)for the root node `,then we canget a directed spanning tree for ~G.Sufficiency:Let ~Gs be a directed spanning tree of ~G .Note that by the definition of ~G,the digraph G can be obtained by contracting all the edges (n +i;i );i 2V in the digraph ~G.Thus,the operation of the edge contraction on ~Gs will result in a directed spanning tree,say G s ,of the digraph G .Based on the above lemma,now we have the following result.Lemma 3:Suppose that and T satisfy the inequality in (4).Let f z 1;z 2;...;z q g be any finite subsetof +.If the union of the digraphs 0(A (z 1));0(A (z 2));...;0(A (z q ))has a directed spanning tree,then the union of digraphs 0(4(z 1));0(4(z 2));...;0(4(z q ))also has a directed spanning tree.Proof:The union of the digraphs 0(4(z 1));0(4(z 2));...;0(4(z q ))hereby is exactly the digraph0(q l =14(z l )).Because and T satisfy (4),it follows that 4(z l ),l =1;2;...;q ,is a row-stochastic (and hence nonnegative)matrix with positive diagonal entries.Note that L (z l )=diag L (z l )0A (z l ).By observing the equation in (5),we get that there exists a positive number ,say =min f q (( =2)T 0( 2=4)T 2);(2= )T +(1=2)T 2g ,such that we get (7),as shown at the bottom of the page.It thus follows from ~M 12=I n that (n +i;i )20(q l =14(z l ))for any i 2V .On the other hand,~M 21=q l =1A (z l )implies that(j;i )20(q l =1A (z l ))if and only if (j;n +i )20(ql =14(z l ))for any i;j 2V ;i =j .Combining these arguments,we knowthat the digraphs0(q l =14(z l ))and0(ql =1A (z l ))correspondto the digraphs ~G and G ,respectively,as described in Lemma 2.Note that the digraph0(q l =1A (z l ))is just the union of digraphs 0(A (z 1));0(A (z 2));...;0(A (z q )).It then follows from Lemma 2that the digraph0(q l =14(z l ))has a directed spanning tree,which proves the Lemma.Let P be the set of all n by n row-stochastic matrices.Given any row-stochastic matrix P =[p ij ]2P ,define (P )=10mini;j k min f p ik ;p jk g [25].Lemma 4: (1)is continuous on P .40(k )=102T +4T2I n 0T2(diag L (k )0A 0(k))2T 04T2In2T +4T2I n 02T +12T 2(diag L (k )0A 0(k))102T 04T2I nql =14(z l )q2T 04T2I n2T +12T 2diag q l =1L (z l )0q l =1L (z l )0Inql =1A (z l )0= ~M 11~M12~M 21~M22:(7)Proof:2:P can be viewed as a subset of metricspace n .All the functions involved in the definition of (1)are continuous,and since the operations involved are sums and mins,it readily follows that (1)is continuouson n .The restriction of a continuous function is con-tinuous,so (1)is also continuous on P .Two nonnegative matrices M and N are said to be of the same type,denoted by M N ,if they have zero elements and positive elements in the same places.To derive the main result,we need the fol-lowing classical results regarding the infinite product of row-stochastic matrices.Lemma 5:([25])Let M =f M 1;M 2;...;M q g be a finite set of n 2n ergodic matrices with the property that for each se-quence M i ;M i ;...;M i of positive length,the matrix productM i M i111M i is ergodic.Then,for each infinite sequence M i ;M i ;...there exists a column vector c2n such thatlim j !1M i M i111M i =1c T :(8)In addition,when M is an infinite set, (W )<1,where W =S k S k 111Sk,S k 2M ,j =1;2;...;N (n )+1,and N (n )(which may depend on n )is the number of different types of all n 2n ergodic matrices.Furthermore,if there exists a constant 0 d <1satisfying (W ) d ,then (8)still holds.Let d=(n 01) .Assume,in the sequel,that ;T satisfy (4= T )0 T >2and T 01 (2= )T d.Then,by Lemma 1,all possible 4(k )must be nonnegative with positive diagonal elements.In addition,since the set of all 2n ( max +1)22n ( max +1)matrices can be viewed as the metricspace [2n (+1)],for each fixed pair ;T ,all possible 4(k )compose a compact set,denoted by 7( ;T ).This is because all the nonzero and hence positive entries of 4(k )are both uniformly lower and upper bounded,which can be seen by observing the form of 4(k )in (5).Let 3(A )=f B =[b ij ]22n 22n :b ij =a ij or b ij =0;i;j =1;2;...;2n g ,and denote by 5( ;T )the set of matricesM (40;41;...;4)=40411114014I 2n 0111000I 2n 11100 0111I 2nsuch that 40;41;...;423(4(k ))and 40+41+...+4=4(k ),where 4(k )27( ;T ).The set 5( ;T )is compact,since givenany 4(k )27( ;T ),all possible choices of 40;41;...;4are finite.Let (k )=[ 1(k ); 2(k );111; 2n (+1)(k )]T =[y T (k );y T (k 01);111;y T (k 0 max )]T22n (+1).Then,there exists a matrix M (40(k );41(k );...;4(k ))25( ;T )such that system (3)is rewritten as(k +1)=M (40(k );41(k );...;4(k )) (k ):(9)Clearly,the set 5( ;T )includes all possible system matrices of system (9).2Weare indebted to Associate Editor,Prof.Jorge Cortes,for his help with a simpler proof of this lemma.Given any positive integer K,define ~5(;T )=i =1M (4i 0;4i 1;...;4i):M (1)25( ;T )and there exists a integer ;1 K suchthat the union of digraphsj =04ij ;i =1;...; ;has a directed spanningtree :~5(;T )is also a compact set,which can be derived by noticing the following facts:1)5( ;T )is a compact set;2)all possible choices of are finite since is bounded by K;3)all possible choices of the directed spanning trees are finite;and 4)given the directed spanning tree and ,the followingset:i =1M (4i 0;4i 1;...;4i):M (1)25( ;T )and the union of the digraphsj =04ij;i =1;...; ;hasthe speci ed directed spanningtreeis compact (this can be proved by following the similar proof of [27,Lemma 10]).Note that the set ~5(;T )includes all possible products of ; K ,consecutive system matrices of system (9).The following lemma is presented to prove that all the possible prod-ucts of consecutive system matrices of system (9)satisfy the result as stated in Lemma 5,which in turn allow us to use the properties of in-finite products of row-stochastic matrices from an infinite set to derive our main result.Lemma 6:If 81;...;8k 2~5(;T ),where k =N (2n ( max +1))+1,then there exists a constant 0 d <1such that(k i =18i ) d .Proof:We first prove that for any 82~5(;T );8is an er-godic matrix.According to the definition of ~5(;T ),there exist pos-itive integer (1 K),M (4i 0;4i 1;...;4i )25( ;T ),i =1;...; ,such that 8= i =1M (4i 0;4i 1;...;4i)and the union of digraphs0(j =04ij ),i =1;...; ,has a directed span-ning tree.Since M (4i 0;4i 1;...;4i )25( ;T ),j =04ij must be nonnegative matrices with positive diagonal elements.Furthermore,there exists a positive number 1such that diag(j =04ij ) I 2n ,for any M (4i 0;4i 1;...;4i )25( ;T ).Specifically,by observing (5),we can choose as=min 1;10 2T + 24T20T 22(n 01) ;10 2T 0 24T2:Combining this with the condition that the union of digraphs0(j =04ij ),i =1;...; ,has a directed spanning tree,we can prove that matrix 8is ergodic by following the proof of [26,Lemma 7].Letd =max 82~5(;T )ki =18i :From Lemma 5,we know that(k i =18i )<1.This,together withthe fact that ~5( ;T )is a compact set and (1)is continuous (Lemma4),implies d must exist and 0 d <1,which therefore completing the proof.For notational simplicity,we shall denote M (40(k );41(k );...;4(k ))by M (k )if it is self-evident from the context.Based on the preceding work,now we can present our main result as follows.Theorem 1:Assume that and T satisfy (4= T )0 T >2andT 01 (2= )T d.Then,employing algorithm (2),consensus is reached for all the agents if there exists an infinite sequence of con-tiguous,nonempty,uniformly bounded time intervals [k j ;k j +1),j =1;2;...,starting at k 1=0,with the property that the union of the di-graphs 0(A (k j ));0(A (k j +1));...;0(A (k j +101))has a directed spanning tree.Proof:We first prove that consensus can be reached for system (9)using algorithm (2).Let 8(k;k )=I 2n (+1),k 0,and 8(k;l )=M (k 01)111M (l +1)M (l ),k >l 0.Assume,without loss of generality,that the lengths of all the time intervals [k j ;k j +1),j =1;2;...,are bounded by K.It follows from Lemma 3and the condition that the union of the digraphs 0(A (k j ));0(A (k j +1));...;0(A (k j +101))has a directed spanning tree that the union of the digraphs 0(4(k j ));0(4(k j +1));...;0(4(k j +101))also has a directed spanning tree for each j2+,which,together with the proof ofLemma 6,implies that 8(k j +1;k j )=k 01k =k M (k )2~5(;T ).Since 8(k j ;0)=8(k j ;k j 01)8(k j 01;k j 02)1118(k 2;k 1),it then follows from Lemma 5and Lemma 6thatlim j !18(k j ;0)=12n (+1)wT(10)where w22n (+1)and w 0.For each m >0,let k l be the largest nonnegative integer such that k l m .Note that matrix 8(m;k l )is row stochastic,thus we have8(m;0)012n w T =8(m;k l)8(k l ;0)012n wT :The matrix 8(m;k l )is bounded because it is the product of fi-nite matrices which come from a bounded set ~5(;T ).By using (10),we immediately have lim m !18(m;0)=12n (+1)w T .Combining this with the fact that (m )=8(m;0) (0)yields lim m !1 (m )=(w T (0))12n (+1)which,in turn,implies lim m !1x (m )=(w T (0))1n and lim k !1v (m )=0,and there-fore completing the proof.Remark 3:Matrix A (k )is a somewhat complex object to study compared with the adjacency matrix A (k )(see Remark 1).It is worth noting that more general results in which the sufficient conditions for guaranteeing the final consensus are presented in terms of G (k )instead of the interaction matrix in the presence of delays can be provided if some additional conditions are imposed.For example,if in addition to the conditions on and T as that required in Theorem 1,it is further required that a certain communication topology which takes effect at some time will last for at least max +1time steps,then we can get that consensus can be reached if there exists an infinite sequence of contiguous,nonempty,uniformly bounded time intervals [k j ;k j +1),j =1;2;...,starting at k 1=0,with the property that the union of the digraphs G (k j );G (k j +1);...;G (k j +101)has a directed spanning tree.This can be observed by reconstructing a new sequence of con-tiguous,nonempty and uniformly bounded time intervals which satis-fies the condition in Theorem 1by using similar technique as that in in [26,Theor.3].IV .I LLUSTRATIVE E XAMPLEConsider a group of n =6agents interacting between the possible digraphs f Ga;Gb;Gc g (see Fig.2),all of which have 0–0.2weights.Fig.2.Digraphs which model all the possible communicationtopologies.Fig.3.Position and velocity trajectories for agents.Take and T as =2and T =0:6respectively.Assume that the communication delays ij (k )satisfies 21(k )= 32(k )= 43(k )=1T s , 52(k )= 54(k )=2T s ,while 65(k )= 61(k )=3T s ,for any k2+.Moreover,we assume the switching signal is periodically switched,every 3T s in a circular way from Ga to Gb ,from Gb to Gc ,and then from Gc to Ga .Obviously,the union of the digraphs 0(A (k ))across each time in-terval of 9T s is precisely the digraph G d in Fig.2,which therefore has a directed spanning tree.Fig.3shows that consensus is reached for algorithm (2),which is consistent with the result in Theorem 1.V .C ONCLUSIONS AND F UTURE W ORKIn this technical note,we have investigated a discrete-time second-order consensus algorithm for networks of agents with nonuniform and time-varying communication delays under dynamically changing com-munication topologies in a sampled-data setting.By employing graphic method,state argumentation technique as well as the product proper-ties of row-stochastic matrices from an infinite set,we have presented a sufficient condition in terms of the associated digraph of the interac-tion matrix in the presence of delays for the agents to reach consensus.Finally,we have shown the usefulness and advantages of the proposed result through simulation results.It is worth noting that the case with input delays is an interesting topic which deserves further investigation in our future work.。