Energy-efficient broadcasting in ad hoc wireless networks

DOI10.1016/J.JDA.2016.11.004zbMATH Open1359.68026arXiv1603.08393OpenAlexW2551373219MaRDI QIDQ511146FDOQ511146

Dimitris Sakavalas, Sushanta Karmakar, Paraschos Koutris, Aris Pagourtzis

Publication date: 14 February 2017

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Abstract: We study distributed broadcasting protocols with few transmissions (`shots') in radio networks where the topology is unknown. In particular, we examine the case in which a bound $k$ is given and a node may transmit at most $k$ times during the broadcasting protocol. Initially, we focus on oblivious algorithms for $k$-shot broadcasting, that is, algorithms where each node decides whether to transmit or not with no consideration of the transmission history. Our main contributions are (a) a lower bound of $Omega(n^2/k)$ on the broadcasting time of any oblivious $k$-shot broadcasting algorithm and (b) an oblivious broadcasting protocol that achieves a matching upper bound, namely $O(n^2/k)$, for every $klesqrtn$ and an upper bound of $O(n^{3/2})$ for every $k>sqrtn$. We also study the general case of adaptive broadcasting protocols where nodes decide whether to transmit based on all the available information, namely the transmission history known by each. We prove a lower bound of $Omegaleft(n^{frac1+kk}ight)$ on the broadcasting time of any protocol by introducing the emph{transmission tree} construction which generalizes previous approaches.

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

Recommendations

• Energy efficient randomised communication in unknown AdHoc networks
• Energy and Time Efficient Broadcasting in Known Topology Radio Networks
• Time efficient \(k\)-shot broadcasting in known topology radio networks
• Efficient k-Shot Broadcasting in Radio Networks
• Efficient \(k\)-shot broadcasting in radio networks

zbMATH Keywords

distributed algorithmsenergy efficiencywireless networks\(k\)-shot broadcastingad hoc radio networksoblivious protocols

Mathematics Subject Classification ID

Distributed algorithms (68W15) Network design and communication in computer systems (68M10) Distributed systems (68M14) Network protocols (68M12)

Cites Work

• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• On Broadcasting in Radio Networks--Problem Analysis and Protocol Design
• Title not available (Why is that?)
• Broadcasting algorithms in radio networks with unknown topology
• Energy efficient randomised communication in unknown AdHoc networks
• Time efficient \(k\)-shot broadcasting in known topology radio networks
• Efficient k-Shot Broadcasting in Radio Networks
• Time of Deterministic Broadcasting in Radio Networks with Local Knowledge
• Title not available (Why is that?)
• Distributed broadcast in radio networks of unknown topology.
• Faster broadcasting in unknown radio networks
• Title not available (Why is that?)
• Distributed broadcast in unknown radio networks
• Fast broadcasting and gossiping in radio networks
• Lower bounds for the broadcast problem in mobile radio networks
• Title not available (Why is that?)
• Message and time efficient multi-broadcast schemes
• Broadcasting in undirected ad hoc radio networks

Cited In (9)

• Efficient and competitive broadcast in multi-channel radio networks
• Energy efficient all-to-all broadcasting for situation awareness in wireless ad hoc networks.
• Sleeping on the job
• Energy and Time Efficient Broadcasting in Known Topology Radio Networks
• Total energy optimal multicasting in wireless ad hoc networks
• Low-weight superimposed codes and related combinatorial structures: bounds and applications
• Energy efficient randomised communication in unknown AdHoc networks
• Title not available (Why is that?)
• STACS 2004

This page was built for publication: Energy-efficient broadcasting in ad hoc wireless networks

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