License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2022.16
URN: urn:nbn:de:0030-drops-172071
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17207/
Dani, Varsha ;
Hayes, Thomas P.
How to Wake up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks
Abstract
Recent work [Chang et al., 2018; Chang et al., 2020; Varsha Dani et al., 2021] has shown that it is sometimes feasible to significantly reduce the energy usage of some radio-network algorithms by adaptively powering down the radio receiver when it is not needed. Although past work has focused on modifying specific network algorithms in this way, we now ask the question of whether this problem can be solved in a generic way, treating the algorithm as a kind of black box.
We are able to answer this question in the affirmative, presenting a new general way to modify arbitrary radio-network algorithms in an attempt to save energy. At the expense of a small increase in the time complexity, we can provably reduce the energy usage to an extent that is provably nearly optimal within a certain class of general-purpose algorithms.
As an application, we show that our algorithm reduces the energy cost of breadth-first search in radio networks from the previous best bound of 2^O(√{log n}) to polylog(n), where n is the number of nodes in the network
A key ingredient in our algorithm is hierarchical clustering based on additive Voronoi decomposition done at multiple scales. Similar clustering algorithms have been used in other recent work on energy-aware computation in radio networks, but we believe the specific approach presented here may be of independent interest.
BibTeX - Entry
@InProceedings{dani_et_al:LIPIcs.DISC.2022.16,
author = {Dani, Varsha and Hayes, Thomas P.},
title = {{How to Wake up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {16:1--16:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-255-6},
ISSN = {1868-8969},
year = {2022},
volume = {246},
editor = {Scheideler, Christian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17207},
URN = {urn:nbn:de:0030-drops-172071},
doi = {10.4230/LIPIcs.DISC.2022.16},
annote = {Keywords: Radio Networks, Low Energy Computation, Clustering}
}
|
Keywords: |
|
Radio Networks, Low Energy Computation, Clustering |
|
Collection: |
|
36th International Symposium on Distributed Computing (DISC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
17.10.2022 |
