.png){kind=icon}
返回
Deterministic and Energy-Optimal Wireless Synchronization
.png){kind=icon}
OA
AI
DOI：10.1145/2629493.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We consider the problem of clock synchronization in a wireless setting where processors must minimize the number of times their radios are used to save energy. Energy efficiency is a central goal in wireless networks, especially if energy resources are severely limited, as occurs in sensor and ad hoc networks, and in many other settings. The problem of clock synchronization is fundamental and intensively studied in the field of distributed algorithms. In the current setting, the problem is to synchronize clocks of mprocessors that wake up in arbitrary time points, such that the maximum difference between wake-up times is bounded by a positive integer n. (Time intervals are appropriately discretized to allow communication of all processors that are awake in the same discrete time unit.) Currently, the best-known results for synchronization for singlehop networks ofmprocessors is a randomized algorithm due to Bradonjic et al. [2009] of O(root n/m . poly-log(n)) radio use times per processor, and a lower bound of Omega (root n/m). The main open question left in their work is to close the poly-log gap between the upper and the lower bound, and to derandomize their probabilistic construction and eliminate error probability. This is exactly what we do in this article. That is, we show a deterministic algorithm with radio use of Omega (root n/m), which exactly matches the lower bound proven in Bradonjic et al. [2009] to a small multiplicative constant. Therefore, our algorithm is optimal in terms of energy efficiency and completely resolves a long sequence of works in this area [Bradonjic et al. 2009; Moscribroda et al. 2006; McGlynn and Borbash 2001; Polastre et al. 2004]. Moreover, our algorithm is optimal in terms of running time as well. To achieve these results, we devise a novel adaptive technique that determines the times when devices power their radios on and off. This technique may be of independent interest. In addition, we prove several lower bounds on the energy efficiency of algorithms for multihop networks. Specifically, we show that any algorithm for multihop networks must have radio use of Omega (root n) per processor. Our lower bounds hold even for specific kinds of networks, such as networks modeled by unit disk graphs and highly connected graphs. Our results imply that the simple deterministic algorithm devised for two-processor networks in Bradonjic et al. [2009] with efficiency O(root n) can be used in multihop networks, and it is the most efficient solution in terms of energy use.
Keyword:
Algorithms
Design
Performance
Clock synchronization
energy efficiency
sensor networks
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
4.7
论文数:
999
被引数:
2.0K
机构
引用论文
.png){kind=icon}
Atypical presentation of burrowing bug pigmentation involving a non-acral site非典型掘穴蝽色素沉着涉及非肢端部位的表现OAAI
OAAI分享收藏Numerical integration of the cartesian equations of motion of a system with constraints: molecular dynamics of n-alkanes具有约束的系统的笛卡尔运动方程的数值积分: 正构烷烃的分子动力学
PREAI
分享收藏Incompleteness and Disgust Predict Treatment Outcome in Pediatric Obsessive-Compulsive Disorder
PREAI
分享收藏
查看更多内容