Broadcasting in Networks of Unknown Topology in the Presence of Swamping

Abstract

In this paper, we address the problem of broadcasting in a wireless network under a novel communication model: the {\em swamping} communication model. In this model, nodes communicate only with those nodes at geometric distance greater than $s$ and at most $r$ from them. Communication between nearby nodes under this model can be very time consuming, as the length of the path between two nodes within distance $s$ is only bounded above by the diameter $D$, in many cases. For the $n$-node lattice networks, we present algorithms of optimal time complexity, respectively $O(n/r+r/(r-s))$ for the lattice line and $O(\sqrt{n}/r+r/(r-s))$ for the two-dimensional lattice. We also consider networks of unknown topology of diameter $D$ and of a parameter $g$ ({\em granularity}). More specifically, we consider networks with $\gamma$ the minimum distance between any two nodes and $g=1/\gamma$. We present broadcast algorithms for networks of nodes placed on the line and on the plane with respective time complexities $O(D/l+g^2)$ and $O(Dg/l+g^4)$, where $l\in \Theta (\max \{(1-s),\gamma \})$.

arXiv commentA preliminary version of this paper appeared in Proc. 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2010), New York City, USA, September 20-22, Vol 6366, pp. 267-281, LNCS Springer, 2010. Full proofs for this paper published 2010: https://scs.carleton.ca/content/communication-networks-spatially-correlated-faults