Energy efficient randomised communication in unknown AdHoc networks

ABSTRACT

This paper studies broadcasting and gossiping algorithms in random and general AdHoc networks. Our goal is not only to minimise the broadcasting and gossiping time, but also to minimise the energy consumption, which is measured in terms of the total number of messages (or transmissions) sent. We assume that the nodes of the network do not know the network, and that they can only send with a fixed power, meaning they can not adjust the area sizes that their messages cover. We believe that under these circumstances the number of transmissions is a very good measure for the overall energy consumption.

For random networks, we present a broadcasting algorithm where every node transmits at most once. We show that our algorithm broadcasts in O(log n) steps, w.h.p., where n is the number of nodes. We then present a O(d log n) (d is the expected degree) gossiping algorithm using O(log n) messages per node.

For general networks with known diameter D, we present a randomised broadcasting algorithm with optimal broadcasting time O(D log (n/D) + log²n) that uses an expected number of O(log²n/log(n/D)) transmissions per node. We also show a tradeoff result between the broadcasting time and the number of transmissions: we construct a network such that any oblivious algorithm using a time-invariant distribution requires Ω(log²n/ log(n/D)) messages per node in order to finish broadcasting in optimal time. This demonstrates the tightness of our upper bound. We also show that no oblivious algorithm can complete broadcasting w.h.p. using o(log n) messages per node.

REFERENCES

• 1: William Aiello , Fan Chung , Linyuan Lu, A random graph model for massive graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.171-180, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335326]
• 2: Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
• 3: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization, Journal of Computer and System Sciences, v.45 n.1, p.104-126, Aug. 1992 [doi>10.1016/0022-0000(92)90042-H]
• 4: Reuven Bar-Yehuda , Amos Israeli , Alon Itai, Multiple communication im multihop radio networks, SIAM Journal on Computing, v.22 n.4, p.875-887, Aug. 1993 [doi>10.1137/0222055]
• 5: Belá Bollobás. The diameter of random graphs. IEEE Transaction on Information Theory, vol. 36, num. 2, pp. 285--288, 1990.
• 6: Bogdan S. Chlebus, Dariusz R. Kowalski and Mariusz A. Rokicki. Average-Time Complexity of Gossiping in Radio Networks. Proc 13th Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 253--267, 2006.
• 7: M. Chrobak , L. Gasieniec , W. Rytter, Fast broadcasting and gossiping in radio networks, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.575, November 12-14, 2000
• 8: Marek Chrobak , Leszek Gasieniec , Wojciech Rytter, A Randomized Algorithm for Gossiping in Radio Networks, Proceedings of the 7th Annual International Conference on Computing and Combinatorics, p.483-492, August 20-23, 2001
• 9: Fan Chung , Linyuan Lu, The diameter of sparse random graphs, Advances in Applied Mathematics, v.26 n.4, p.257-279, May 2001 [doi>10.1006/aama.2001.0720 ]
• 10: Andrea E. F. Clementi , Angelo Monti , Riccardo Silvestri, Selective families, superimposed codes, and broadcasting on unknown radio networks, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.709-718, January 07-09, 2001, Washington, D.C., United States
• 11: Artur Czumaj , Wojciech Rytter, Broadcasting algorithms in radio networks with unknown topology, Journal of Algorithms, v.60 n.2, p.115-143, August 2006 [doi>10.1016/j.jalgor.2004.08.001]
• 12: Robert Elsässer , Leszek Gasieniec, Radio communication in random graphs: extended abstract, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074021]
• 13: Robert Elsässer, On the communication complexity of randomized broadcasting in random-like graphs, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148135]
• 14: Wendi Rabiner Heinzelman , Joanna Kulik , Hari Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.174-185, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313529]
• 15: Lefteris M. Kirousis , Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, Power Consumption in Packet Radio Networks (Extended Abstract), Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, p.363-374, February 27-March 01, 1997
• 16: Dariusz R. Kowalski , Andrzej Pelc, Deterministic Broadcasting Time in Radio Networks of Unknown Topology, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.63-72, November 16-19, 2002
• 17: Dariusz R. Kowalski , Andrzej Pelc, Broadcasting in undirected ad hoc radio networks, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.73-82, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872045]
• 18: Eyal Kushilevitz , Yishay Mansour, An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks, SIAM Journal on Computing, v.27 n.3, p.702-712, June 1998 [doi>10.1137/S0097539794279109]
• 19: Ding Liu , Manoj Prabhakaran, On Randomized Broadcasting and Gossiping in Radio Networks, Proceedings of the 8th Annual International Conference on Computing and Combinatorics, p.340-349, August 15-17, 2002
• 20: Linyuan Lu, The diameter of random massive graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.912-921, January 07-09, 2001, Washington, D.C., United States
• 21: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 22: S. Muthukrishnan , Gopal Pandurangan, The bin-covering technique for thresholding random geometric graph properties, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 23: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 24: Michael Mitzenmacher and Eli Upfal. Probability and Computing Cambridge Press, 2005.
• 25: Ying Xu.An O(n^1.5) deterministic gossiping algorithm for radio networks. algorithmica, vol. 36, num. 1, pp. 93--96, 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
ad hoc networks, broadcasting, energy efficiency, gossiping, randomized algorithms