Combinatorial and Probabilistic Approaches to Oscillator and Clock Synchronization

振荡器和时钟同步的组合和概率方法

• 批准号: 2232241
• 负责人: Hanbaek Lyu
• 金额: $ 14.7万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-11-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2232241&HistoricalAwards=false
• 关键词: Combinatorial; Probabilistic; Approaches; Oscillator; Clock

If a group of people is given local clocks with arbitrarily set times, and there is no global reference (for example GPS), is it possible for the group to synchronize all clocks by only communicating with nearby members? In order for a distributed system to be able to perform high-level tasks that may go beyond the capability of an individual agent, the system must first solve a "clock synchronization" problem to establish a shared notion of time. The study of clock synchronization (or coupled oscillators) has been an important subject of research in mathematics and various areas of science for decades, with fruitful applications in many areas including wildfire monitoring, electric power networks, robotic vehicle networks, large-scale information fusion, and wireless sensor networks. However, there has been a gap between our theoretical understanding of systems of coupled oscillators and practical requirements for clock synchronization algorithms in modern application contexts. This project will develop systematic approaches for bridging this gap based on combinatorial and probabilistic methods. The use of discrete oscillators will be a key thread in developing more robust and efficient clock synchronization algorithms, extending the current proof techniques for convergence guarantee, and providing a foundation for a data-driven approach to the clock synchronization problems. This project will also include interdisciplinary collaboration and research opportunities for students at all levels One of the key difficulties in analyzing the behavior of coupled oscillators lies in the cyclic hierarchy in the phase space. A widely used observation in the literature is that, if all initial phases are concentrated in an open half-circle, such a cyclic hierarchy disappears and we have robust synchronization results in various settings. Hence deriving global synchronization from arbitrary initial configurations not only warrants self-stabilization of the clock synchronization algorithm under arbitrary perturbation, but also addresses the theoretical limitation of such a half-circle condition. By extending techniques such as local concentration and adaptive pulse-coupling scheme due to the PI, the project aims at deriving global synchronization from an arbitrary initial configuration on undirected finite trees, for non-identical natural frequencies and non-zero propagation delay of signals with optimal bounds on convergence time. The convergence result will be extended to arbitrary graphs by combining with a spanning tree algorithm, and the composite algorithm will be implemented as a fast and resource-minimal clock synchronization algorithm for modern wireless sensor networks. This project will also include interdisciplinary collaboration and research opportunities for students at all levels. In particular, some of the projects involve generating a large database for the collective behavior of some models of discrete coupled oscillators on finite graphs, and applying machine learning techniques to extract key features of the pair of network topology and initial configuration that guarantee synchronization. The project will provide students with research experiences ranging from dynamical systems to computer science and machine learning.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

如果一群人被给予具有任意设定时间的本地时钟，并且没有全局参考（例如GPS），那么该群体是否可以通过仅与附近成员通信来同步所有时钟？为了使分布式系统能够执行可能超出单个代理能力的高级任务，系统必须首先解决“时钟同步”问题，以建立共享的时间概念。几十年来，时钟同步（或耦合振荡器）的研究一直是数学和各个科学领域的重要研究课题，在野火监测、电力网络、机器人车辆网络、大规模信息融合和无线传感器网络等许多领域都有着卓有成效的应用。然而，我们对耦合振荡器系统的理论理解与现代应用环境中时钟同步算法的实际要求之间存在差距。该项目将根据组合和概率方法制定弥合这一差距的系统方法。离散振荡器的使用将是开发更强大和更有效的时钟同步算法的关键线程，扩展了当前的收敛保证证明技术，并为数据驱动的方法提供基础的时钟同步问题。 该项目还将为各级学生提供跨学科合作和研究机会分析耦合振荡器行为的关键难点之一在于相空间中的循环层次。在文献中广泛使用的观察是，如果所有的初始阶段集中在一个开放的半圆，这样的循环层次消失，我们有强大的同步结果在各种设置。因此，从任意初始配置导出全局同步不仅保证了时钟同步算法在任意扰动下的自稳定性，而且解决了这种半圆条件的理论局限性。通过扩展技术，如局部浓度和自适应脉冲耦合方案，由于PI，该项目的目的是从一个任意的初始配置无向有限树，非相同的自然频率和非零传播延迟的信号的收敛时间的最佳界限，推导出全球同步。通过结合生成树算法，将收敛结果推广到任意图上，并将其实现为一种快速、资源最少的现代无线传感器网络时钟同步算法。该项目还将为各级学生提供跨学科合作和研究机会。特别是，其中一些项目涉及为有限图上的离散耦合振荡器的某些模型的集体行为生成大型数据库，并应用机器学习技术来提取保证同步的网络拓扑和初始配置对的关键特征。该项目将为学生提供从动力系统到计算机科学和机器学习的研究经验。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。