Deterministic and Energy-Optimal Wireless Synchronizationn
Leonid Barenboim, shlomi dolev, Rafail Ostrovsky
Abstract:
We consider the problem of clock "synchronization in a wires setting where processors must minimize the number of times their radios are used, in order to save energy. Energy efficiency is a central goal in wireless networks, especially if energy resources are severely limited , as occurs in sensor and as-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 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.( 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 fir synchronization for single-hop networks of m processors is a randomized algorithm due to Bradonjic, Kohler and Ostrovsky [2] of O(√n/m.\em poly-log(n)) radio-use times per processor, and a lower bound of Ω(√n/m). The main open question left in their work is to close the poly-log gap between the upper and lower bound and to de-randomize their probabilistic constructions and eliminate error probability. This is exactly what we do in this paper. That is we show a "deterministic algorithm with radio use of Θ(√n/m).which exactly matches the lower bound proven in [2], up to small multiplicative constant. Therefore, our algorithm is "optimal" in terms of energy efficiency and completely resolves a long sequence of works in this area[2,11-14]. Moreover, our algorithm is optimal in terms of running time as well. In order 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 independent intrest.
In addtion, we provie 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 Ω(√n) per processor. Our lower bounds holds even for specific kinds of networks such as networks modled by unit disk graphs and highly connected graphs.
A full version of this paper with full proofs and pseudocode of all procedures is available on-line[1].
comment: Preliminary version appeared in DISC 2011:237-251. Full version appeared in TOSN 11(1): 13:1-13:25 (2014)
Fetch PDF file of the paper
| Back to Publications List |