2014/06/07 by Kranakis, Evangelos, Paquette, Michel
#Computational Complexity (cs.CC) #Distributed #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1406.1923
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(√(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 γ the minimum distance between any two nodes and g = 1/γ. We present broadcast algorithms for networks of nodes placed on the line and on the plane with respective time complexities O(D/l + g2) and O(Dg/l + g4), where l ∈ Θ(max\(1-s),γ\).