Abstract
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, \sqrt{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 > r min according to a probability density function ρ(r) ~r − α (more precisely, \(\rho(r) = (\alpha-1)r_{\min}^{\alpha-1} r^{-\alpha}\)), where α ∈ (1,3) and \(r_{\min}> \delta \sqrt{\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 (loglogn)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.
Partly supported by the Royal Society IJP 2007/R1 “Geometric Sensor Networks with Random Topology”.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Berenbrink, P., Cooper, C., Hu, Z.: Energy efficient randomised communication in unknown adhoc networks. In: Proc. of 19th SPAA 2007, pp. 250–259 (2007)
Brusci, D., Pinto, M.D.: Lower bounds for the broadcast problem in mobile radio networks. Distributed Computing 10(3), 129–135 (1997)
Chernoff, H.: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493–507 (1952)
Chlamtac, I., Kutten, S.: On broadcasting in radio networks - problem analysis and protocol design. IEEE Transactions on Communications 33(12), 1240–1246 (1985)
Chlebus, B., Ga̧sieniec, L., Östlin, A., Robson, J.: Deterministic radio broadcasting. In: Welzl, E., Montanari, U., Rolim, J. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 717–728. Springer, Heidelberg (2000)
Chlebus, B., Gąsieniec, L., Gibbons, A., Pelc, A., Rytter, W.: Deterministic broadcasting in ad hoc radio networks. Distributed Computing 15(1), 27–38 (2002)
Chrobak, M., Gąsieniec, L., Rytter, W.: Fast broadcasting and gossiping in radio networks. Journal of Algorithms 43(2), 177–189 (2002)
Cicalese, F., Manne, F., Xin, Q.: Faster centralized communication in radio networks. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol. 4288, pp. 339–348. Springer, Heidelberg (2006)
Clementi, A., Monti, A., Silvestri, R.: Distributed broadcast in radio networks with unknown topology. Theoretical Computer Science 302, 337–364 (2003)
Czumaj, A., Rytter, W.: Broadcasting algorithms in radio networks with unknown topology. Journal of Algorithms 60(2), 115–143 (2006)
Czumaj, A., Wang, X.: Fast messgae dissemination in random geometric ad-hoc radio networks. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 220–231. Springer, Heidelberg (2007)
De Marco, G., Pelc, A.: Faster broadcasting in unknown radio networks. Information Processing Letters 79(2), 53–56 (2001)
Dessmark, A., Pelc, A.: Broadcasting in geometric radio networks. Journal of Discrete Algorithms 5, 187–201 (2007)
Elkin, M., Kortsarz, G.: An improved algorithm for radio broadcast. ACM Transactions on Algorithms 3(1) (2007)
Elsässer, R., Gąsieniec, L.: Radio communication in random graphs. Journal of Computer and Systems Sciences 72, 490–506 (2006)
Emek, Y., Gąsieniec, L., Kantor, E., Pelc, A., Peleg, D., Su, C.: Broadcasting in udg radio networks with unknown topology. In: Proc. of PODC 2007, pp. 195–204 (2007)
Gaber, I., Mansour, Y.: Centralized broadcast in multihop radio networks. Journal of Algorithms 46(1), 1–20 (2003)
Ganesan, D., Govindan, R., Shenker, S., Estrin, D.: Highly resilient, energy-efficient multipath routing in wireless sensor networks. ACM SIGMOBILE Mobile Computing and Communication Review 5(4), 11–25 (2001)
Gąsieniec, L., Pagourtzis, A., Potapov, I., Radzik, T.: Deterministic communication in radio networks with large labels. Algorithmica 47(1), 97–117 (2007)
Gąsieniec, L., Peleg, D., Xin, Q.: Faster communication in known topology radio networks. Distributed Computing 19(4), 289–300 (2007)
Hagerup, T., Rüb, C.: A guided tour of Chernoff bounds. Information Processing Letters 36(6), 305–308 (1990)
Ishizuka, M., Aida, M.: Achieving power-law placement in wireless sensor networks. In: Proc. of ISADS 2005, pp. 661–666 (2005)
Kowalski, D., Pelc, A.: Time of deterministic broadcasting in radio networks with local knowledge. SIAM Journal on Computing 33, 870–891 (2004)
Kowalski, D., Pelc, A.: Broadcasting in undirected ad hoc radio networks. Distributed Computing 18(1), 43–57 (2005)
Kowalski, D., Pelc, A.: Optimal deterministic broadcasting in known topology radio networks. Distributed Computing 19(3), 183–195 (2007)
Krishnamachari, B., Wicker, S., Bejar, R., Pearlman, M.: Critical density thresholds in distributed wireless networks. In: Communications, Information and Network Security. Kluwer Academic Publishers, Dordrecht (2002)
Lotker, Z., Navarra, A.: Managing random sensor networks by means of grid emulation. In: Boavida, F., Plagemann, T., Stiller, B., Westphal, C., Monteiro, E. (eds.) NETWORKING 2006. LNCS, vol. 3976, pp. 856–867. Springer, Heidelberg (2006)
Meguerdichian, S., Koushanfar, F., Potkonjak, M., Srivastava, M.: Coverage problems in wireless ad-hoc sensor networks. In: Proc. of INFOCOM 2001, vol. 3, pp. 1380–1387 (2001)
Muthukrishnan, S., Pandurangan, G.: The bin-covering technique for thresholding geometric graph properties. In: Proc. of 16th SODA 2005, pp. 989–998 (2005)
Penrose, M.: Random Geometric Graphs. Oxford Studies in Probability (2003)
Sen, A., Huson, M.L.: A new model for scheduling packet radio networks. In: Proc. of INFOCOM 1996, pp. 1116–1124 (1996)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Elsässer, R., Gąsieniec, L., Sauerwald, T. (2008). On Radio Broadcasting in Random Geometric Graphs. In: Taubenfeld, G. (eds) Distributed Computing. DISC 2008. Lecture Notes in Computer Science, vol 5218. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87779-0_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-87779-0_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87778-3
Online ISBN: 978-3-540-87779-0
eBook Packages: Computer ScienceComputer Science (R0)