一阶平均同步算法是最基本的同步算法,在工程中有广泛的应用,例如无线传感器网络的分布式计算,以及多个卫星、车辆和机器人的编队控制等。由于实际系统受各种噪声的影响,例如无线通信网络受热噪声、信道衰落和量化效应影响,卫星、车辆和机器人编队系统则存在对邻居状态观测的测量噪声等,该算法已被很多方法研究。例如,为了处理通信链路的随机故障,一些文献假设网络的拓扑结构是确定性的但能切换,另外一些文献则假设网络的拓扑结构服从某些随机分布。尽管一阶平均同步算法已有大量的研究成果,但仍存在一些关键问题没有解决,包括算法同步的临界连通性条件是什么,如何优化系统收敛速度,当网络拓扑为强相关随机序列时同步条件是什么等。
为了解决上述问题,信息技术部陈鸽等科研人员首先提出了可扩展联合连通这一新条件。该条件是指存在一个时间段序列使得在每个时间段内网络的并连通,并且时间段的长度以一个扩展指数单调递增。在该条件下得出系统同步的临界扩展指数为1/2,并且首次提出了切换拓扑下系统收敛速度优化方法,得出系统最快收敛速度与1/t同阶。此外,他们还提出了以“确定性”覆盖“随机性”的新思路,首次给出了非平稳强相关随机拓扑序列的系统同步条件。
最后,他们将理论应用到移动ad-hoc网络的分布式计算,得出为了保证系统同步节点的相对移动速度不能太快。具体而言,若节点的相对速度为O(1/t),那么系统将同步;若节点的相对速度超过c/tb,其中c>0和b<1为常数,那么系统将不同步。下面图1、2、3为仿真实验:

图1:节点间相对速度为1/(t+200),系统同步

图2:节点间相对速度为1/(t+200)0.8,系统不同步。

图3:节点间相对速度为1/(t+200)0.8,系统更明显不同步。
相关文献:G. Chen, L. Y. Wang, C. Chen and G. Yin. Critical connectivity and fastest convergence rates of distributed consensus with switching topologies and additive noises. Will appear to IEEE Transactions on Automatic Control.