Combinatorial and Probabilistic Approaches to Oscillator and Clock Synchronization

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

基本信息

批准号：
2010035
负责人：
Hanbaek Lyu
金额：
$ 14.7万
依托单位：
University of California-Los Angeles
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-07-01 至 2022-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2010035&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的法定任务，并且使用基金会的知识分子优点和更广泛的影响标准，被认为值得通过评估来获得支持。