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.2021.19
URN: urn:nbn:de:0030-drops-148219
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14821/
Dani, Varsha ;
Gupta, Aayush ;
Hayes, Thomas P. ;
Pettie, Seth
Wake up and Join Me! an Energy-Efficient Algorithm for Maximal Matching in Radio Networks
Abstract
We consider networks of small, autonomous devices that communicate with each other wirelessly. Minimizing energy usage is an important consideration in designing algorithms for such networks, as battery life is a crucial and limited resource. Working in a model where both sending and listening for messages deplete energy, we consider the problem of finding a maximal matching of the nodes in a radio network of arbitrary and unknown topology.
We present a distributed randomized algorithm that produces, with high probability, a maximal matching. The maximum energy cost per node is O(log² n), and the time complexity is O(Δ log n). Here n is any upper bound on the number of nodes, and Δ is any upper bound on the maximum degree; n and Δ are parameters of our algorithm that we assume are known a priori to all the processors. We note that there exist families of graphs for which our bounds on energy cost and time complexity are simultaneously optimal up to polylog factors, so any significant improvement would need additional assumptions about the network topology.
We also consider the related problem of assigning, for each node in the network, a neighbor to back up its data in case of eventual node failure. Here, a key goal is to minimize the maximum load, defined as the number of nodes assigned to a single node. We present an efficient decentralized low-energy algorithm that finds a neighbor assignment whose maximum load is at most a polylog(n) factor bigger that the optimum.
BibTeX - Entry
@InProceedings{dani_et_al:LIPIcs.DISC.2021.19,
author = {Dani, Varsha and Gupta, Aayush and Hayes, Thomas P. and Pettie, Seth},
title = {{Wake up and Join Me! an Energy-Efficient Algorithm for Maximal Matching in Radio Networks}},
booktitle = {35th International Symposium on Distributed Computing (DISC 2021)},
pages = {19:1--19:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-210-5},
ISSN = {1868-8969},
year = {2021},
volume = {209},
editor = {Gilbert, Seth},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14821},
URN = {urn:nbn:de:0030-drops-148219},
doi = {10.4230/LIPIcs.DISC.2021.19},
annote = {Keywords: Distributed Algorithms, Energy-Aware Computation, Radio Networks, Maximal Matching, Sensor Networks}
}
|
Keywords: |
|
Distributed Algorithms, Energy-Aware Computation, Radio Networks, Maximal Matching, Sensor Networks |
|
Collection: |
|
35th International Symposium on Distributed Computing (DISC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.10.2021 |
