Energy-efficient broadcasting in ad hoc wireless networks

DOI10.1016/J.JDA.2016.11.004MaRDI QIDQ511146zbMATH OpenOpenAlexFDO

Authors Sushanta Karmakar, Paraschos Koutris, Aris Pagourtzis, Dimitris Sakavalas

Publication date 14 February 2017

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

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

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)

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.

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

Cites work

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

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
• scientific article; zbMATH DE number 7378397 (Why is no real title available?)
• 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)