# Broadcast in radio networks: time vs. energy tradeoffs

Source: [Broadcast in radio networks: time vs. energy tradeoffs](<https://www.sota2.com/research/paper/68fa64631e209131cea04402>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T21:02:11.964Z

Authors: Marek Klonowski, Dominik Paj\\k{a}k

Published: 2017-11-11T15:17:40.000Z

## Abstract

In wireless networks, consisting of battery-powered devices, energy is a costly resource and most of it is spent on transmitting and receiving messages. Broadcast is a problem where a message needs to be transmitted from one node to all other nodes of the network. We study algorithms that can work under limited energy measured as the maximum number of transmissions by a single station. The goal of the paper is to study tradeoffs between time and energy complexity of broadcast problem in multi-hop radio networks. We consider a model where the topology of the network is unknown and if two neighbors of a station are transmitting in the same discrete time slot, then the signals collide and the receiver cannot distinguish the collided signals from silence.   We observe that existing, time efficient, algorithms are not optimized with respect to energy expenditure. We then propose and analyse two new randomized energy-efficient algorithms. Our first algorithm works in time $O((D+\\varphi)\\cdot n^{1/\\varphi}\\cdot \\varphi)$ with high probability and uses $O(\\varphi)$ energy per station for any $\\varphi \\leq \\log n/(2\\log\\log n)$ for any graph with $n$ nodes and diameter $D$. Our second algorithm works in time $O((D+\\log n)\\log n)$ with high probability and uses $O(\\log n/\\log\\log n)$ energy.   We prove that our algorithms are almost time-optimal for given energy limits for graphs with constant diameters by constructing lower bound on time of $\\Omega(n^{1/\\varphi} \\cdot \\varphi)$. The lower bound shows also that any algorithm working in polylogaritmic time in $n$ for all graphs needs energy $\\Omega(\\log n/\\log\\log n)$.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1711.04149>)

[PDF](<https://arxiv.org/pdf/1711.04149.pdf>)