skip to main content
10.1145/1127777.1127788acmconferencesArticle/Chapter ViewAbstractPublication PagescpsweekConference Proceedingsconference-collections
Article

Data gathering tours in sensor networks

Published: 19 April 2006 Publication History

Abstract

A basic task in sensor networks is to interactively gather data from a subset of the sensor nodes. When data needs to be gathered from a selected set of nodes in the network, existing communication schemes often behave poorly. In this paper, we study the algorithmic challenges in efficiently routing a fixed-size packet through a small number of nodes in a sensor network, picking up data as the query is routed. We show that computing the optimal routing scheme to visit a specific set of nodes is NP-complete, but we develop approximation algorithms that produce plans with costs within a constant factor of the optimum. We enhance the robustness of our initial approach to accommodate the practical issues of limited-sized packets as well as network link and node failures, and examine how different approaches behave with dynamic changes in the network topology. Our theoretical results are validated via an implementation of our algorithms on the TinyOS platform and a controlled simulation study using Matlab and TOSSIM.

References

[1]
https://mirage.berkeley.intel-research.net/.]]
[2]
http://www.cs.berkeley.edu/~ameli/routing.pdf.]]
[3]
D. Braginsky and D. Estrin. Rumor routing algorithm for sensor networks. In ICDCS-22, 2002.]]
[4]
D. Braginsky and D. Estrin. Rumor routing algorthim for sensor networks. In 1st ACM international workshop on Wireless sensor networks and applications. ACM Press, 2002.]]
[5]
M. Charikar, S. Khuller, and B. Raghavachari. Algorithms for capacitated vehicle routing. In 30th annual ACM symposium on Theory of computing. ACM Press, 1998.]]
[6]
N. Christofides. Worst case analysis of a new heuristic for the traveling salesman problem. Technical report, Carnegie Mellon University, 1976.]]
[7]
R. Cristescu, B. Beferull-Lozano, and M. Vetterli. On network correlated data gathering, 2004.]]
[8]
R. Cristescu, B. Beferull-Lozano, M. Vetterli, D. Ganesan, and J. Acimovic. On the interaction of data representation and routing in sensor networks. In ICASSP, 2005.]]
[9]
D. De Couto, D. Aguayo, B. Chambers, and R. Morris. Performance of multihop wireless networks: Shortest path is not enough. In HotNets-I. ACM SIGCOMM, October 2002.]]
[10]
A. Deshpande, C. Guestrin, S. Madden, J. Hellerstein, and W. Hong. Model-driven data acquisition in sensor networks. In VLDB, 2004.]]
[11]
D. Ganesan, B. Greenstein, D. Perelyubskiy, D. Estrin, and J. Heidemann. Multi-resolution storage and search in sensor networks. ACM Transactions on Storage, Aug. 2005.]]
[12]
M. R. Garey and D. S. Johnson. Computers and Intractability - A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979.]]
[13]
M. Haimovich and A. H. G. R. Kan. Bounds and heuristics for capacitated routing problems. Mathematics of Operations Research, November 1985.]]
[14]
S. T. Hedetniemi, S. M. Hedetniemi, and A. Liestman. A survey of gossiping and broadcasting in communication networks. Networks, 1998.]]
[15]
W. Heinzelman, J. Kulik, and H. Balakrishnan. Adaptive protocols for information dissemination in wireless sensor networks, 1999.]]
[16]
C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed diffusion: a scalable and robust communication paradigm for sensor networks. In 6th annual international conference on Mobile computing and networking, 2000.]]
[17]
J. Kulik, W. R. Heinzelman, and H. Balakrishnan. Negotiation-based protocols for disseminating information in wireless sensor networks. Wireless Networks, 2002.]]
[18]
P. Levis, N. Lee, M. Welsh, and D. Culler. TOSSIM: Accurate and scalable simulation of entire tinyos applications. In Proc. ACM Conference on Embedded Networked Sensor Systems (SenSys), Nov. 2003.]]
[19]
X. Li, Y. J. Kim, R. Govindan, and W. Hong. Multi-dimensional range queries in sensor networks. In 1st international conference on Embedded networked sensor systems. ACM Press, 2003.]]
[20]
S. Madden, M. Franklin, J. Hellerstein, and W. Hong. The design of an acquisitional query processor for sensor networks. In ACM SIGMOD, 2003.]]
[21]
S. Madden and J. Gehrke. Query processing in sensor networks. Pervasive Computing, 3(1), January-March 2004.]]
[22]
T. Ralphs, L. Kopman, W. Pulleyblank, and L. Trotter. The capacitated vehicle routing problem.]]
[23]
S. Ratnasamy, B. Karp, L. Yin, F. Yu, D. Estrin, R. Govindan, and S. Shenker. Ght: a geographic hash table for data-centric storage. In 1st ACM international workshop on Wireless sensor networks and applications. ACM Press, 2002.]]
[24]
A. Scaglione and S. D. Servetto. On the interdependence of routing and data compression in multi-hop sensor networks. In MobiCom, pages 140--147, 2002.]]
[25]
A. Woo, T. Tong, and D. Culler. Taming the underlying challenges of reliable multihop routing in sensor networks. In SenSys, pages 14--27, 2003.]]
[26]
Y. Yu, B. Krishnamachari, and V. K. Prasanna. Energy-latency tradeoffs for data gathering in wireless sensor networks. In INFOCOM, 2004.]]

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
IPSN '06: Proceedings of the 5th international conference on Information processing in sensor networks
April 2006
514 pages
ISBN:1595933344
DOI:10.1145/1127777
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 April 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. routing algorithms
  2. sensor networks
  3. splitting tours

Qualifiers

  • Article

Conference

IPSN06
Sponsor:

Acceptance Rates

Overall Acceptance Rate 143 of 593 submissions, 24%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 27 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2018)Model-Based Querying in Sensor NetworksEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_222(2293-2299)Online publication date: 7-Dec-2018
  • (2017)Model-Based Querying in Sensor NetworksEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_222-2(1-6)Online publication date: 21-Jan-2017
  • (2016)On mobile sensor data collection using data mules2016 International Conference on Computing, Networking and Communications (ICNC)10.1109/ICCNC.2016.7440562(1-7)Online publication date: Mar-2016
  • (2013)Wireless Sensor Network Design for Energy-Efficient MonitoringIntelligent Technologies and Techniques for Pervasive Computing10.4018/978-1-4666-4038-2.ch007(134-156)Online publication date: 2013
  • (2013)Data Gathering, Storage, and Post-ProcessingThe Art of Wireless Sensor Networks10.1007/978-3-642-40009-4_15(497-534)Online publication date: 14-Dec-2013
  • (2012)Evolutionary and Noise-Aware Data Gathering for Wireless Sensor NetworksBio-Inspired Models of Network, Information, and Computing Systems10.1007/978-3-642-32615-8_5(32-39)Online publication date: 2012
  • (2011)Path Planning of Data Mules in Sensor NetworksACM Transactions on Sensor Networks10.1145/1993042.19930438:1(1-27)Online publication date: 1-Aug-2011
  • (2011)Energy‐conserving data gathering by mobile mules in a spatially separated wireless sensor networkWireless Communications and Mobile Computing10.1002/wcm.118413:15(1369-1385)Online publication date: 15-Aug-2011
  • (2010)Quality-aware sensor data collectionInternational Journal of Sensor Networks10.1504/IJSNET.2010.0331157:3(127-140)Online publication date: 1-May-2010
  • (2010)Effective Determination of Mobile Agent Itineraries for Data Aggregation on Sensor NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2009.20322:12(1679-1693)Online publication date: 1-Dec-2010
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media