TY - GEN
T1 - On radio broadcasting in random geometric graphs
AU - Elsässer, Robert
AU - Ga̧sieniec, Leszek
AU - Sauerwald, Thomas
N1 - Funding Information:
Partly supported by the Royal Society IJP 2007/R1 “Geometric Sensor Networks with Random Topology”.
PY - 2008
Y1 - 2008
N2 - One of the most frequently studied problems in the context of information dissemination in communication networks is the broadcasting problem. In this paper we consider radio broadcasting in random geometric graphs, in which n nodes are placed uniformly at random in [0, √n]2, and there is a (directed) edge from a node u to a node v in the corresponding graph iff the distance between u and v is smaller than the transmission radius assigned to u. Throughout this paper we consider the distributed case, i.e., each node is only aware (apart from n) of its own coordinates and its own transmission radius, and we assume that the transmission radii of the nodes vary according to a power law distribution. First, we consider the model in which any node is assigned a transmission radius r > rmin according to a probability density function ρ(r) ∼ r-α (more precisely, ρ(r) = (α - 1)rminα-1 r-α), where α ∈(1,3) and rmin > δ √log n with δ being a large constant. For this case, we develop a simple radio broadcasting algorithm which has the running time O(loglogn), with high probability, and show that this result is asymptotically optimal. Then, we consider the model in which any node is assigned a transmission radius r > c according to the probability density function ρ(r) = (α - 1)c α-1 r-α , where α is drawn from the same range as before and c is a constant. Since this graph is usually not strongly connected, we assume that the message which has to be spread to all nodes of the graph is placed initially in one of the nodes of the giant component. We show that there exists a fully distributed randomized algorithm which disseminates the message in O(D (log log n)2) steps, with high probability, where D denotes the diameter of the giant component of the graph. Our results imply that by setting the transmission radii of the nodes according to a power law distribution, one can design energy efficient radio networks with low average transmission radius, in which broadcasting can be performed exponentially faster than in the (extensively studied) case where all nodes have the same transmission power.
AB - One of the most frequently studied problems in the context of information dissemination in communication networks is the broadcasting problem. In this paper we consider radio broadcasting in random geometric graphs, in which n nodes are placed uniformly at random in [0, √n]2, and there is a (directed) edge from a node u to a node v in the corresponding graph iff the distance between u and v is smaller than the transmission radius assigned to u. Throughout this paper we consider the distributed case, i.e., each node is only aware (apart from n) of its own coordinates and its own transmission radius, and we assume that the transmission radii of the nodes vary according to a power law distribution. First, we consider the model in which any node is assigned a transmission radius r > rmin according to a probability density function ρ(r) ∼ r-α (more precisely, ρ(r) = (α - 1)rminα-1 r-α), where α ∈(1,3) and rmin > δ √log n with δ being a large constant. For this case, we develop a simple radio broadcasting algorithm which has the running time O(loglogn), with high probability, and show that this result is asymptotically optimal. Then, we consider the model in which any node is assigned a transmission radius r > c according to the probability density function ρ(r) = (α - 1)c α-1 r-α , where α is drawn from the same range as before and c is a constant. Since this graph is usually not strongly connected, we assume that the message which has to be spread to all nodes of the graph is placed initially in one of the nodes of the giant component. We show that there exists a fully distributed randomized algorithm which disseminates the message in O(D (log log n)2) steps, with high probability, where D denotes the diameter of the giant component of the graph. Our results imply that by setting the transmission radii of the nodes according to a power law distribution, one can design energy efficient radio networks with low average transmission radius, in which broadcasting can be performed exponentially faster than in the (extensively studied) case where all nodes have the same transmission power.
UR - http://www.scopus.com/inward/record.url?scp=56449118881&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=56449118881&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-87779-0_15
DO - 10.1007/978-3-540-87779-0_15
M3 - Conference contribution
AN - SCOPUS:56449118881
SN - 3540877789
SN - 9783540877783
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 212
EP - 226
BT - Distributed Computing - 22nd International Symposium, DISC 2008, Proceedings
T2 - 22nd International Symposium on Distributed Computing, DISC 2008
Y2 - 22 September 2008 through 24 September 2008
ER -