Abstract
We study the complexity of distributed protocols for the classical information dissemination problem of distributed gossiping. We consider the model of random geometric networks, one of the main models used to study properties of sensor and ad-hoc networks, where n points are randomly placed in a unit square and two points are connected by an edge/link if they are at at most a certain fixed distance r from each other. To study communication in the network, we consider the ad − hoc radio networks model of communication. We examine various scenarios depending on the local knowledge of each node in the networks, and show that in many settings distributed gossiping in asymptotically optimal time \({\mathcal{O}}(D)\) is possible, where D is the diameter of the network and thus a trivial lower bound for any communication.
Research supported in part by the Centre for Discrete Mathematics and its Applications (DIMAP), University of Warwick.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. Journal of Computer and System Sciences 45(1), 104–126 (1992)
Capkun, S., Hamdi, M., Hubaux, J.-P.: GPS-free positioning in mobile ad hoc networks. Cluster Computing 5(2), 157–167 (2002)
Clementi, A.E.F., Monti, A., Silvestri, R.: Distributed broadcast in radio networks of unknown topology. Theoretical Computer Science 302, 337–364 (2003)
Chlebus, B.S., Ga̧sieniec, L., Gibbons, A., Pelc, A., Rytter, W.: Deterministic broadcasting in ad hoc radio networks. Distributed Computing 15(1), 27–38 (2002)
Chlebus, B.S., Kowalski, D.R., Rokicki, M.A.: Average-time coplexity of gossiping in radio networks. In: Flocchini, P., Gąsieniec, L. (eds.) SIROCCO 2006. LNCS, vol. 4056, pp. 253–267. Springer, Heidelberg (2006)
Chrobak, M., Ga̧sieniec, L., Rytter, W.: Fast broadcasting and gossiping in radio networks. Journal of Algorithms 43(2), 177–189 (2002)
Czumaj, A., Rytter, W.: Broadcasting algorithms in radio networks with unknown topology. Journal of Algorithms 60(2), 115–143 (2006)
Czumaj, A., Wang, X.: Communication problems in random line-of-sight ad-hoc radio networks. In: Proc 4th Symposium on Stochastic Algorithms, Foundations, and Applications (SAGA), pp. 70–81 (2007)
Dessmark, A., Pelc, A.: Broadcasting in geometric radio networks. Journal of Discrete Algorithms 5(1), 187–201 (2007)
Elsässer, R., Ga̧sieniec, L.: Radio communication in random graphs. Journal of Computer and System Sciences 72, 490–506 (2006)
Ga̧sieniec, L., Peleg, D., Xin, Q.: Faster communication in known topology radio networks. In: Proc. 24th PODC, pp. 129–137 (2005)
Ga̧sieniec, L., Radzik, T., Xin, Q.: Faster deterministic gossiping in directed ad-hoc radio networks. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 397–407. Springer, Heidelberg (2004)
Giordano, S., Stojmenovic, I.: Position based ad hoc routes in ad hoc networks. In: Handbook of Ad Hoc Wireless Networks. ch. 16, pp. 1–14 (2003)
Gupta, P., Kumar, P.R.: Critical power for asymptotic connectivity in wireless networks. In: Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming, pp. 547–566 (1998)
Gupta, P., Kumar, P.R.: The capacity of wireless networks. IEEE Transactions on Information Theory IT-46, 388–404 (2000)
Ko, Y.B., Vaidya, N.H.: Location aided routing (LAR) in mobile adhoc networks. In: Proc 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), pp. 66–75 (1998)
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), 185–195 (2007)
Li, X., Shi, H., Shang, Y.: A partial-range-aware localization algorithm for Ad-hoc wireless sensor networks. In: Proc. 29th Annual IEEE International Conference on Local Computer Networks (2004)
Nasipuri, A., Li, K., Sappidi, U.R.: Power consumption and throughput in mobile ad hoc networks using directional antennas. In: Proc. 11th IEEE International Conf. on Computer Communications and Networks (ICCCN), pp. 620–626 (2002)
Penrose, M.D.: Random Geometric Graphs. Oxford University Press, UK (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Czumaj, A., Wang, X. (2007). Fast Message Dissemination in Random Geometric Ad-Hoc Radio Networks. In: Tokuyama, T. (eds) Algorithms and Computation. ISAAC 2007. Lecture Notes in Computer Science, vol 4835. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77120-3_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-77120-3_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77118-0
Online ISBN: 978-3-540-77120-3
eBook Packages: Computer ScienceComputer Science (R0)