Deterministic and energy-optimal wireless synchronization

DOI10.1007/978-3-642-24100-0_24zbMATH Open1350.68039arXiv1010.1112OpenAlexW2571397082MaRDI QIDQ3095330FDOQ3095330

Authors: Leonid Barenboim, Shlomi Dolev, Rafail Ostrovsky 

Publication date: 28 October 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We consider the problem of clock synchronization in a wireless setting where processors must power-down their radios in order to save energy. Energy efficiency is a central goal in wireless networks, especially if energy resources are severely limited. In the current setting, the problem is to synchronize clocks of $m$ processors that wake up in arbitrary time points, such that the maximum difference between wake up times is bounded by a positive integer $n$, where time intervals are appropriately discretized. Currently, the best-known results for synchronization for single-hop networks of $m$ processors is a randomized algorithm due to cite{BKO09} of O(sqrt {n /m} cdot poly-log(n)) awake times per processor and a lower bound of Omega(sqrt{n/m}) of the number of awake times needed per processor cite{BKO09}. The main open question left in their work is to close the poly-log gap between the upper and the lower bound and to de-randomize their probabilistic construction and eliminate error probability. This is exactly what we do in this paper. That is, we show a {deterministic} algorithm with radio use of Theta(sqrt {n /m}) that never fails. We stress that our upper bound exactly matches the lower bound proven in cite{BKO09}, up 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. In order to achieve these results we devise a novel {adaptive} technique that determines the times when devices power their radios on and off. In addition, we prove several lower bounds on the energy efficiency of algorithms for {multi-hop networks}. Specifically, we show that any algorithm for multi-hop networks must have radio use of Omega(sqrt n) per processor.

Full work available at URL: https://arxiv.org/abs/1010.1112

Recommendations

• Near-Optimal Radio Use for Wireless Network Synchronization
• Near-optimal radio use for wireless network synchronization
• The wireless synchronization problem
• The wake-up problem in multi-hop radio networks
• The Wake‐Up Problem in MultiHop Radio Networks

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• The firing squad synchronization problem for graphs
• Principles of Distributed Systems
• Deterministic and energy-optimal wireless synchronization
• Near-Optimal Radio Use for Wireless Network Synchronization

Cited In (10)

• Combinatorial algorithms for distributed graph coloring
• Tradeoff analysis between synchronization time and energy consumption for multi-layer networks
• Near-optimal radio use for wireless network synchronization
• Deterministic and energy-optimal wireless synchronization
• Energy-Efficient Communication in the Presence of Synchronization Errors
• Near-Optimal Radio Use for Wireless Network Synchronization
• The wireless synchronization problem
• Cooperative Synchronization in Wireless Networks
• Energy-Efficient Pulse-Coupled Synchronization Strategy Design for Wireless Sensor Networks Through Reduced Idle Listening
• Guaranteed cost synchronization for second-order wireless sensor networks with given cost budgets

This page was built for publication: Deterministic and energy-optimal wireless synchronization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3095330)