Wave scheduling and routing in sensor networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Wave scheduling and routing in sensor networks

Full text

Pdf (863 KB)

Source

ACM Transactions on Sensor Networks (TOSN) archive
Volume 3 , Issue 1 (March 2007) table of contents

Article No. 2

Year of Publication: 2007

ISSN:1550-4859

Authors

Niki Trigoni	Birkbeck College, University of London, London, United Kingdom
Yong Yao	Cornell University, Ithaca, NY
Alan Demers	Cornell University, Ithaca, NY
Johannes Gehrke	Cornell University, Ithaca, NY
Rajmohan Rajaraman	Northeastern University, Boston, MA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 142, 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:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1210669.1210671 What is a DOI?

ABSTRACT

Sensor networks are being increasingly deployed for diverse monitoring applications. Event data are collected at various sensors and sent to selected storage nodes for further in-network processing. Since sensor nodes have strong constraints on their energy usage, this data transfer needs to be energy-efficient to maximize network lifetime. In this article, we propose a novel methodology for trading energy versus latency in sensor database systems. We propose a new protocol that carefully schedules message transmissions so as to avoid collisions at the MAC layer. Since all nodes adhere to the schedule, their radios can be off most of the time and only wake up during well-defined time intervals. We show how routing protocols can be optimized to interact symbiotically with scheduling decisions, resulting in significant energy savings at the cost of higher latency. We demonstrate the effectiveness of our approach by means of a thorough simulation study, using synthetic data as well as real-world traffic workloads.

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	Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
	2	Bahl, P. and Padmanabhan, V. N. 2000. RADAR: An in-building RF-based user location and tracking system. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM). 775--784.
	3	Bennett, F., Clarke, D., Evans, J., Hopper, A., Jones, A., and Leask, D. 1997. Piconet: Embedded Mobile Networking. IEEE Pers. Comm. 4, 5 (Oct.), 8--15.
	4	Lee Breslau , Deborah Estrin , Kevin Fall , Sally Floyd , John Heidemann , Ahmed Helmy , Polly Huang , Steven McCanne , Kannan Varadhan , Ya Xu , Haobo Yu, Advances in Network Simulation, Computer, v.33 n.5, p.59-67, May 2000 [doi>10.1109/2.841785]
	5	Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
	6	Bulusu, N., Heidemann, J., and Estrin, D. 2000. Gps-less low cost outdoor localization for very small devices. IEEE Pers. Comm. Mag. 7, 5 (October), 28--34.
	7	Cerpa, A., Busek, N., and Estrin, D. 2003. Scale: a tool for simple connectivity assessment in lossy environments. Tech. rep., UCLA, CENS-21.
	8	Chang, J.-H. and Tassiulas, L. 2000. Energy conserving routing in wireless ad hoc networks. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM). IEEE, Los Alamitos, 22--31.
	9	Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks, Wireless Networks, v.8 n.5, p.481-494, September 2002 [doi>10.1023/A:1016542229220]
	10	Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O]
	11	Crossbow Mica2. 2005. Datasheet of the mica2 (mpr400cb) sensor node platform. Crossbow Technology. Inc.
	12	Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844143]
	13	Saurabh Ganeriwal , Ram Kumar , Mani B. Srivastava, Timing-sync protocol for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958508]
	14	Ganesan, D., Krishnamachari, B., Woo, A., Culler, D., Estrin, D., and Wicker, S. 2002. Complex behavior at scale: An experimental study of low-power wireless sensor networks. Tech. Rep., UCLA, CSD-TR 02-0013. February.
	15	Garey, M. and Johnson, D. 1977. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 826--834.
	16	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	17	Abhishek Ghose , Jens Grossklags , John Chuang, Resilient Data-Centric Storage in Wireless Ad-Hoc Sensor Networks, Proceedings of the 4th International Conference on Mobile Data Management, p.45-62, January 21-24, 2003
	18	Hellerstein, J., Hong, W., Madden, S., and Stanek, K. 2003. Beyond average: Towards sophisticated sensing with queries. In 2nd International Workshop on Information Processing in Sensor Networks (IPSN).
	19	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]
	20	Johnson, D. B. and Maltz, D. A. 1996. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, Imielinski and Korth, Eds. The Kluwer International Series in Engineering and Computer Science, vol. 353. Kluwer Academic Publishers.
	21	Kasten, O. 2001. Energy consumption. Tech. rep., Eldgenossische Technische Hochschule (ETH) Zurich. http://www.inf.ethz.ch/kasten/research/bathtub/energy_consumption.html.
	22	Kotz, D., Newport, C., and Elliott, C. 2003. The mistaken axioms of wireless network research. Tech. Rep., Dartmouth College Computer Science, TR2003-467. July.
	23	Koen Langendoen , Niels Reijers, Distributed localization in wireless sensor networks: a quantitative comparison, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.4, p.499-518, 15 November 2003 [doi>10.1016/S1389-1286(03)00356-6]
	24	Lu, G., Sadagopan, N., Krishnamachari, B., and Goel, A. 2005. Delay efficient sleep scheduling in wireless sensor networks. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM).
	25	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]
	26	Park, V. and Corson, S. 1999. Temporally-ordered routing algorithm (tora) version 1 functional specification. Internet Draft, http://www.ietf.org/internet-drafts/draft-ietf-manet-tora-spec-02.txt.
	27	Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
	28	Perkins, C. E. 1999. Ad hoc on demand distance vector (aodv) routing. Internet Draft, http://www.ietf.org/internet-drafts/draft-ietf-manet-aodv-04.txt.
	29	Sylvia Ratnasamy , Brad Karp , Li Yin , Fang Yu , Deborah Estrin , Ramesh Govindan , Scott Shenker, GHT: a geographic hash table for data-centric storage, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570750]
	30	Sen, A. and Huson, M. 1996. A new model for scheduling packet radio networks. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM). 1116--1124.
	31	Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]
	32	Society, I. C. 1999. Wireless LAN medium access control (mac) and physical layer specification. IEEE Std 802.11.
	33	Stemm, M. and Katz, R. 1997. Measuring and reducing energy consumption of network interfaces in hand-held devices. IEICE Trans. Comm. E80-B, 1125--1131.
	34	Niki Trigoni , Yong Yao , Alan Demers , Johannes Gehrke , Rajmohan Rajaraman, WaveScheduling: energy-efficient data dissemination for sensor networks, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada [doi>10.1145/1052199.1052209]
	35	Geoffrey Werner-Allen , Geetika Tewari , Ankit Patel , Matt Welsh , Radhika Nagpal, Firefly-inspired sensor network synchronicity with realistic radio effects, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098934]
	36	Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
	37	Fan Ye , Haiyun Luo , Jerry Cheng , Songwu Lu , Lixia Zhang, A two-tier data dissemination model for large-scale wireless sensor networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570664]
	38	Ye, W., Heidemann, J., and Estrin, D. 2002. An energy-efficient MAC protocol for wireless sensor networks. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM). 1567--1576.
	39	Ye, W., Heidemann, J., and Estrin, D. 2003. Medium access control with coordinated, adaptive sleeping for wireless sensor networks. Tech. Rep. ISI-TR-567, USC/Information Sciences Institute. January.
	40	Yu, Y., Govindan, R., and Estrin, D. 2001. Geographical and energy aware routing: A recursive data dissemination protocol for wireless sensor networks. Tech. Rep. UCLA/CSD-TR-01-0023, University of Southern California. May.
	41	Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]
	42	Gang Zhou , Tian He , Sudha Krishnamurthy , John A. Stankovic, Models and solutions for radio irregularity in wireless sensor networks, ACM Transactions on Sensor Networks (TOSN), v.2 n.2, p.221-262, May 2006 [doi>10.1145/1149283.1149287]