Distributed deterministic broadcasting in uniform-power ad hoc wireless networks

DOI10.1007/978-3-642-40164-0_20MaRDI QIDQ2842785zbMATH OpenOpenAlexFDO

Authors Tomasz Jurdziński, Dariusz R. Kowalski, Grzegorz Stachowiak

Publication date 16 August 2013

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

ad hoc wireless networksbroadcast problemlocal leader electionsignal-to-interference-and-noise ratio (SINR)uniform power

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Development of many futuristic technologies, such as MANET, VANET, iThings, nano-devices, depend on efficient distributed communication protocols in multi-hop ad hoc networks. A vast majority of research in this area focus on design heuristic protocols, and analyze their performance by simulations on networks generated randomly or obtained in practical measurements of some (usually small-size) wireless networks. %some library. Moreover, they often assume access to truly random sources, which is often not reasonable in case of wireless devices. In this work we use a formal framework to study the problem of broadcasting and its time complexity in any two dimensional Euclidean wireless network with uniform transmission powers. For the analysis, we consider two popular models of ad hoc networks based on the Signal-to-Interference-and-Noise Ratio (SINR): one with opportunistic links, and the other with randomly disturbed SINR. In the former model, we show that one of our algorithms accomplishes broadcasting in $O(Dlo{g}^{2}n)$ rounds, where $n$ is the number of nodes and $D$ is the diameter of the network. If nodes know a priori the granularity $g$ of the network, i.e., the inverse of the maximum transmission range over the minimum distance between any two stations, a modification of this algorithm accomplishes broadcasting in $O(Dlogg)$ rounds. Finally, we modify both algorithms to make them efficient in the latter model with randomly disturbed SINR, with only logarithmic growth of performance. Ours are the first provably efficient and well-scalable, under the two models, distributed deterministic solutions for the broadcast task.

Recommendations

• Broadcast in the Ad Hoc SINR Model
• Deterministic broadcasting in ad hoc radio networks
• Faster Deterministic Broadcasting in Ad Hoc Radio Networks
• Broadcasting in an Unreliable SINR Model.
• Distributed Multiple-Message Broadcast in Wireless Ad-Hoc Networks under the SINR Model

Cited in

(18)

• Distributed bare-bones communication in wireless networks
• Deterministic protocols in the SINR model without knowledge of coordinates
• Distributed Multiple-Message Broadcast in Wireless Ad-Hoc Networks under the SINR Model
• On the impact of geometry on ad hoc communication in wireless networks
• scientific article; zbMATH DE number 2040806 (Why is no real title available?)
• Distributed backbone structure for algorithms in the SINR model of wireless networks
• Deterministic digital clustering of wireless ad hoc networks
• Distributed deterministic broadcasting in wireless networks of weak devices
• Brief announcement: Data dissemination in unified dynamic wireless networks
• Brief announcement: Multi-broadcasting under the SINR model
• Local broadcasting with arbitrary transmission power in the SINR model
• BROADCASTING IN AD HOC NETWORKS BASED ON SELF-PRUNING
• Token traversal in ad hoc wireless networks via implicit carrier sensing
• Token traversal in ad hoc wireless networks via implicit carrier sensing
• Dynamic multiple-message broadcast: bounding throughput in the affectance model
• Collaborative broadcast in \(\mathcal{O}(\log \log n)\) rounds
• Distributed \((\varDelta + 1)\)-coloring in the physical model
• Distributed multiple-message broadcast in wireless ad hoc networks under the SINR model

This page was built for publication: Distributed deterministic broadcasting in uniform-power ad hoc wireless networks

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