k-shot Broadcasting in Ad Hoc Radio Networks

2016/03/28 by Sushanta Karmakar, Paraschos Koutris, Karmakar, Sushanta +5
Computer Science · #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.DC

paper · pdf · doi:10.48550/arxiv.1603.08393

21 pages, 2 figures, preliminary version presented in CATS 2011: 161-168

arxiv created 2016/03/28 · arxiv updated 2016/03/29

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 Ω(n²/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²/k), for every k ≤ √(n) and an upper bound of O(n^3/2) for every k > √(n). 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 Ω(n^(1+k)/(k)) on the broadcasting time of any protocol by introducing the transmission tree construction which generalizes previous approaches.

Related

• Distributed Broadcast in Wireless Networks with Unknown Topology
• Energy Efficient Randomized Communication in Unknown AdHoc Networks
• Improved lower bound for deterministic broadcasting in radio networks
• Information Gathering in Ad-Hoc Radio Networks with Tree Topology
• Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks