SmartGossip: an improved randomized broadcast protocol for sensor networks

ABSTRACT

We investigate four performance metrics for randomized broadcast protocols on sensor networks: the fraction of nodes that receive the message (coverage), the number of first-time receivers per transmission (energy efficiency), the node-average normalized time till reception (per hop latency), and the average number of control messages per node (overhead). Our focus is to evaluate the extent to which the exchange of local information (either active or passive) can improve protocol performance. To this end we study via simulation three protocols from the literature that exploit local information (GOSSIP3 from [8], SPIN-1 from [10], and PUSH&PULL from [12])and compare their performance against the well known GOSSIP1 ([8]) protocol which does not employ any local information in making transmission decisions. Our findings are that i) local information is of course quite valuable in increasing protocol performance, and ii) it is possible to obtain high coverage and efficiency but one must then incur either increased delay or increased overhead. We study the strengths and weaknesses of the above protocols and propose the new SmartGossip protocol which combines several ideas from the above protocols, as well as several new mechanisms, to achieve superior performance.

REFERENCES

• 1: Christopher L. Barrett , Stephan J. Eidenbenz , Lukas Kroc , Madhav Marathe , James P. Smith, Parametric probabilistic sensor network routing, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941368]
• 2: David Braginsky , Deborah Estrin, Rumor routing algorthim for sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570742]
• 3: P. Erdos and A. Renyi. On random graphs I. Publ. Math. Debrecen, 6(290), 1959.
• 4: P. Eugster, R. Guerraoui, A.-M. Kermarrec, and L. Massoulie. Epidemic information dissemination in distributed systems. IEEE Computer, 37(5):60--67, May 2004.
• 5: A. M. Farley and A. Proskurowski. Gossiping in grid graphs. Journal of Combinatorics, Information and System Sciences, 5(2):161--172, 1980.
• 6: D. Gavidia, S. Voulgaris, and M. van Steen. Epidemic-style monitoring in large-scale wireless sensor networks. Technical Report IR-CS-012, Vrije University, Dept. of Computer Science, Amsterdam, Netherlands, March 2005.
• 7: G. Grimmett. Percolation. Springer-Verlag, New York, NY, 1989.
• 8: Z. J. Haas, J. Y. Halpern, and L. Li. Gossip-based ad hoc routing. In Proceedings of IEEE INFOCOM, pages 1707--1716, 2002.
• 9: John Heidemann , Fabio Silva , Deborah Estrin, Matching data dissemination algorithms to application requirements, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958517]
• 10: 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]
• 11: Jonathan W. Hui , David Culler, The dynamic behavior of a data dissemination protocol for network programming at scale, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031506]
• 12: R. Karp , C. Schindelhauer , S. Shenker , B. Vocking, Randomized rumor spreading, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.565, November 12-14, 2000
• 13: P. Kouznetsov, R. Guerraoui, S. B. Handurukande, and A.-M. Kermarrec. Reducing noise in gosssip-based reliable broadcast. In Proceedings of the 20th IEEE Symposium on Reliable Distributed Systems, pages 186--189, October 2001.
• 14: Sandeep S. Kulkarni , Limin Wang, MNP: Multihop Network Reprogramming Service for Sensor Networks, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS'05), p.7-16, June 06-10, 2005 [doi>10.1109/ICDCS.2005.50]
• 15: H. G. Landau and A. Rapoport. Contribution to the mathematical theory of contagion and spread of information: I. spread through a thoroughly mixed population. Bulletin of Mathematical Biophysics, 15:173--183, 1953.
• 16: Philip Levis , David Culler, The firecracker protocol, Proceedings of the 11th workshop on ACM SIGOPS European workshop: beyond the PC, September 19-22, 2004, Leuven, Belgium [doi>10.1145/1133572.1133589]
• 17: P. Levis, N.Patel, D. Culler, and S. Shenker. Trickle: A self-regulating algorithm for code maintenance and propagation. In Proceedings of the First USENIX/ACM symposium on Network Systems Design and Implementation, Boston, MA, 2004.
• 18: Meng-Jang Lin , Keith Marzullo, Directional Gossip: Gossip in a Wide Area Network, Proceedings of the Third European Dependable Computing Conference on Dependable Computing, p.364-379, September 15-17, 1999
• 19: M. Penrose. Random Geometric Graphs. Oxford Studies in Probability. Oxford University Press, 2003.
• 20: L. Rodrigues, S. Handurukande, J. Pereira, R. Guerraoui, and A.-M. Kermarrec. Adaptive gossip-based broadcast. In Proceedings of the 2003 International Conference on Dependable Systems and Networks (DSN), 2003.
• 21: T. Stathopoulos, J. Heidemann, and D. Estrin. A remote code update mechanism for wireless sensor networks. In Technical Report CENS Technical report 30, 2003.
• 22: Qixiang Sun , Daniel C. Sturman, A Gossip-Based Reliable Multicast for Large-Scale High-Throughput Applications, Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8), p.347, June 25-28, 2000
• 23: Sameer Tilak , Amy Murphy , Wendi Heinzelman, Non-Uniform Information Dissemination for Sensor Networks, Proceedings of the 11th IEEE International Conference on Network Protocols, p.295, November 04-07, 2003
• 24: Duncan J. Watts, Small worlds: the dynamics of networks between order and randomness, Princeton University Press, Princeton, NJ, 1999

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Design, Performance

Keywords:
SmartGossip, performance analysis, randomized protocols, sensor networks