Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks

DOI10.1007/S00446-022-00426-WMaRDI QIDQ6096038OpenAlexFDO

Authors Varsha Dani, Thomas P. Hayes, Seth Pettie

Publication date 11 September 2023

Published in Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

distributed algorithmssensor networksradio networksmaximal matchingenergy-aware computation

Mathematics Subject Classification ID

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

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(lo{g}^{2}n)$, where $n$ is the size of the network. The total latency of our algorithm is $O(nlogn)$ time steps. We observe that there exist families of network topologies for which both of these bounds are simultaneously optimal up to polylog factors, so any significant improvement will require 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 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 a decentralized low-energy algorithm that finds a neighbor assignment whose maximum load is at most a polylog($n$) factor bigger that the optimum.

Recommendations

• scientific article; zbMATH DE number 7774270
• The wake-up problem in multi-hop radio networks
• Automata, Languages and Programming
• The Wake‐Up Problem in MultiHop Radio Networks
• Probabilistic algorithms for the wake-up problem in single-hop radio networks
• scientific article; zbMATH DE number 1979528
• Scalable wake-up of multi-channel single-hop radio networks
• Sleeping on the job: energy-efficient and robust broadcast for radio networks

Cites work

• scientific article; zbMATH DE number 2089983 (Why is no real title available?)
• scientific article; zbMATH DE number 2090695 (Why is no real title available?)
• Contention resolution with constant throughput and log-logstar channel accesses
• Efficient algorithms for leader election in radio networks
• Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection
• Exponential Separations in the Energy Complexity of Leader Election
• Linear-time approximation for maximum weight matching
• On matching cover of graphs
• On the distributed complexity of the semi-matching problem
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Semi-matchings for bipartite graphs and load balancing
• Sleeping is Efficient: MIS in O (1)-rounds Node-averaged Awake Complexity
• Small maximal matchings in random graphs.
• The Energy Complexity of BFS in Radio Networks
• The energy complexity of broadcast
• \textsc{Maximal Independent Sets} in radio networks

Cited in

(5)

• scientific article; zbMATH DE number 7774270 (Why is no real title available?)
• The energy complexity of diameter and minimum cut computation in bounded-genus networks
• scientific article; zbMATH DE number 1979528 (Why is no real title available?)
• Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election
• Probabilistic algorithms for the wake-up problem in single-hop radio networks

This page was built for publication: Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks

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