Optimal clock synchronization in networks
Optimal clock synchronization in networks
复制标题
DOI：
10.1145/1644038.1644061
复制
发表时间：
2009-11
期刊：
影响因子：
--
通讯作者：
C. Lenzen;P. Sommer;Roger Wattenhofer
中科院分区：
文献类型：
--
作者：
C. Lenzen;P. Sommer;Roger Wattenhofer
获得准确的时间是所有网络的重要组成部分；在无线传感器网络中更是如此，因为无线媒体访问或数据融合可能依赖于它。从新颖的分析开始，我们表明正统的时钟同步算法会犯根本性的错误。例如，最先进的时钟同步算法 FTSP 的误差会随着网络规模的扩大而呈指数增长。由于涉及的参数很小，因此该错误仅在大约 10--20 个节点的中型网络中变得可见。相比之下，我们提出了 PulseSync，一种渐近最优的新时钟同步算法。我们在 Mica2 测试台上并通过在大型网络上进行模拟来评估 PulseSync。在 20 个节点的网络上，PulseSync 的原型实现的性能比 FTSP 好 5 倍。理论和仿真表明，对于较大的网络，PulseSync 提供的精度比 FTSP 高出几个数量级。为了使演示更加圆满，我们研究了几个优化问题，例如媒体访问和本地偏差。
Having access to an accurate time is a vital building block in all networks; in wireless sensor networks even more so, because wireless media access or data fusion may depend on it. Starting out with a novel analysis, we show that orthodox clock synchronization algorithms make fundamental mistakes. The state-of-the-art clock synchronization algorithm FTSP exhibits an error that grows exponentially with the size of the network, for instance. Since the involved parameters are small, the error only becomes visible in midsize networks of about 10--20 nodes. In contrast, we present PulseSync, a new clock synchronization algorithm that is asymptotically optimal. We evaluate PulseSync on a Mica2 testbed, and by simulation on larger networks. On a 20 node network, the prototype implementation of PulseSync outperforms FTSP by a factor of 5. Theory and simulation show that for larger networks, PulseSync offers an accuracy which is several orders of magnitude better than FTSP. To round off the presentation, we investigate several optimization issues, e.g. media access and local skew.