Broadcasting in sensor networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Broadcasting in sensor networks: the role of local information

Full text

Pdf (753 KB)

Source

IEEE/ACM Transactions on Networking (TON) archive
Volume 16 , Issue 5 (October 2008) table of contents

Pages 1133-1146

Year of Publication: 2008

ISSN:1063-6692

Authors

Sundar Subramanian	Wireless Networking and Communications Group, Department of Electrical and Computer Engineering, The University of Texas at Austin, Austin, TX
Sanjay Shakkottai	Wireless Networking and Communications Group, Department of Electrical and Computer Engineering, The University of Texas at Austin, Austin, TX
Ari Arapostathis	Wireless Networking and Communications Group, Department of Electrical and Computer Engineering, The University of Texas at Austin, Austin, TX

Publisher

IEEE Press Piscataway, NJ, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 52, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	10.1109/TNET.2007.912034

ABSTRACT

Flooding based querying and broadcasting schemes have low hop-delays of Θ (1/R(n) to reach any node that is a unit distance away, where R(n) is the transmission range of any sensor node. However, in sensor networks with large radio ranges, flooding based broadcasting schemes cause many redundant transmissions leading to a broadcast storm problem. In this paper, we study the role of geographic information and state information (i.e., memory of previous messages or transmissions) in reducing the redundant transmissions in the network.

We consider three broadcasting schemes with varying levels of local information where nodes have: (i) no geographic or state information, (ii) coarse geographic information about the origin of the broadcast, and (iii) no geographic information, but remember previously received messages. For each of these network models, we demonstrate localized forwarding algorithms for broadcast (based on geography or state information) that achieve significant reductions in the transmission overheads while maintaining hop-delays comparable to flooding based schemes. We also consider the related problem of broadcasting to a set of "spatially uniform" points in the network (lattice points) in the regime where all nodes have only a local sense of direction and demonstrate an efficient "sparse broadcast" scheme based on a branching random walk that has a low number of packet transmissions. Thus, our results show that even with very little local information, it is possible to make broadcast schemes significantly more efficient.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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]
	2	J. Cartigny, D. Simplot, and I. Stojmenovic, "Localized minimum-energy broadcasting in ad-hoc networks," in Proc. IEEE INFOCOM, 2003, pp. 2210-2217.
	3	C. Chang, D. Yao, and T. Zajic, "Large deviations, moderate deviations, and queues with long-range dependent inputs," Adv. Appl. Prob., vol. 31, pp. 254-277, 1999.
	4	Nicholas B. Chang , Mingyan Liu, Optimal Controlled Flooding Search in a Large Wireless Network, Proceedings of the Third International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, p.229-237, April 04-06, 2005 [doi>10.1109/WIOPT.2005.36]
	5	M. Chu, H. Haussecker, and F. Zhao, "Scalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks," Xerox PARC, 2001, Tech. Rep. P2001-10113.
	6	A. E. Gamal, J. Mammen, B. Prabhakar, and D. Shah, "Throughput delay trade-off in wireless networks," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004, pp. 461-475.
	7	W. Feller, An Introduction to Probability Theory and Its Applications, Volume II. New York: Wiley, 1966.
	8	P. Gupta and P. R. Kumar, "Critical power for asymptotic connectivity in wireless networks," in Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming, W. M. McEneany and Q. Zhang, Eds. Boston, MA: Birkhauser, 1998, pp. 547-566.
	9	Z. J. Haas, J. Y. Halpern, and L. Li, "Gossip-based ad hoc routing," in Proc. IEEE INFOCOM, 2002, pp. 1707-1716.
	10	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	11	B. Hajek, "Minimum mean hitting times of Brownian motion with constrained drift," in Proc. 27th Conf. Stochastic Processes and Their Applications , Jul. 2000.
	12	Christopher Ho , Katia Obraczka , Gene Tsudik , Kumar Viswanath, Flooding for reliable multicast in multi-hop ad hoc networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.64-71, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313291]
	13	Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
	14	Sze-Yao Ni , Yu-Chee Tseng , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.151-162, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313525]
	15	L. Orecchia , A. Panconesi , C. Petrioli , A. Vitaletti, Localized techniques for broadcasting in wireless sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022638]
	16	Wei Peng , Xi-Cheng Lu, On the reduction of broadcast redundancy in mobile ad hoc networks, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
	17	N. Sadagopan, B. Krishnamachari, and A. Helmy, "The acquire mechanism for efficient querying in sensor networks," in Proc. IEEE Int. Workshop Sensor Network Protocols Applications (SNPA'03), May 2003.
	18	S. Shakkottai, "Asymptotics of query strategies over a sensor network," IEEE Trans. Autom. Control, vol. 50, no. 5, pp. 594-606, May 2005.
	19	Ivan Stojmenovic , Mahtab Seddigh , Jovisa Zunic, Dominating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.14-25, January 2002 [doi>10.1109/71.980024]
	20	Sundar Subramanian , Sanjay Shakkottai, Geographic routing with limited information in sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
	21	S. Subramanian, S. Shakkottai, and A. Arapostathis, "Broadcasting in sensor networks: The role of local information," presented at the IEEE INFOCOM, Barcelona, Spain, Apr. 2006.
	22	J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, "On the construction of energy-efficient broadcast and multicast trees in wireless networks," in Proc. IEEE INFOCOM, Apr. 2000, pp. 589-594.
	23	B. Hajek, An Exploration of Random Processes for Engineers 2006 [Online]. Available: http://www.ifp.uiuc.edu/~hajek/Papers/randomprocesses.html
	24	Brad Williams , Tracy Camp, Comparison of broadcasting techniques for mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513825]