Broadcasting in Networks of Unknown Topology in the Presence of Swamping

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\mathrm{/}r+r\mathrm{/}(r-s))$ for the lattice line and $O(\sqrt{n}\mathrm{/}r+r\mathrm{/}(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\mathrm{/}\gamma$. We present broadcast algorithms for networks of nodes placed on the line and on the plane with respective time complexities $O(D\mathrm{/}l+g^2)$ and $O(Dg\mathrm{/}l+g^4)$, where $l \in \Theta(\max{(1-s),\gamma})$.