More Web Proxy on the site http://driver.im/

research-article

Latency-constrained aggregation in sensor networks

Authors:

LUCA Becchetti,

Alberto Marchetti-Spaccamela,

Andrea Vitaletti,

Peter Korteweg,

Martin Skutella,

Leen StougieAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 6, Issue 1

Article No.: 13, Pages 1 - 20

https://doi.org/10.1145/1644015.1644028

Published: 28 December 2009 Publication History

Abstract

A sensor network consists of sensing devices which may exchange data through wireless communication; sensor networks are highly energy constrained since they are usually battery operated. Data aggregation is a possible way to save energy consumption: nodes may delay data in order to aggregate them into a single packet before forwarding them towards some central node (sink). However, many applications impose constraints on the maximum delay of data; this translates into latency constraints for data arriving at the sink.

We study the problem of data aggregation to minimize maximum energy consumption under latency constraints on sensed data delivery, and we assume unique communication paths that form an intree rooted at the sink. We prove that the offline problem is strongly NP-hard and we design a 2-approximation algorithm. The latter uses a novel rounding technique.

Almost all real-life sensor networks are managed online by simple distributed algorithms in the nodes. In this context we consider both the case in which sensor nodes are synchronized or not. We assess the performance of the algorithm by competitive analysis. We also provide lower bounds for the models we consider, in some cases showing optimality of the algorithms we propose. Most of our results also hold when minimizing the total energy consumption of all nodes.

References

[1]

Akyildiz, I., Su, W., Sanakarasubramaniam, Y., and Cayirci, E. 2002. Wireless sensor networks: A survey. Comput. Netw. J. 38, 4, 393--422.

Digital Library

[2]

Becchetti, L., Korteweg, P., Marchetti-Spaccamela, A., Skutella, M., Stougie, L., and Vitaletti, A. 2006. Latency constrained aggregation in sensor networks. SPOR-report 2006-08, TU Eindhoven. www.win.tue.nl/bs/spor.

[3]

Boulis, A., Ganeriwal, S., and Srivastava, M. B. 2003. Aggregation in sensor networks: An energy-accuracy tradeoff. Ad-hoc Netw. J. 1, 2-3, 317--331.

[4]

Brito, C., Koutsoupias, E., and Vaya, S. 2004. Competitive analysis of organization networks or multicast acknowledgement: How much to wait&quest; In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 627--635.

Digital Library

[5]

Broder, A., and Mitzenmacher, M. 2002. Optimal plans for aggregation. In Proceedings of the 21st Annual Symposium on Principles of Distributed Computing (PODC). 144--152.

Digital Library

[6]

Elson, J., and Estrin, D. 2001. Time synchronization for wireless sensor networks. In Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS), Workshop on Parallel and Distributed Computing Issues in Wireless and Mobile Computing. 1965--1970.

Digital Library

[7]

Elson, J., Girod, L., and Estrin, D. 2002. Fine-Grained network time synchronization using reference broadcasts. In Proceedings of the 5th ACM Symposium on Operating System Design and Implementation (OSDI). 147--164.

Digital Library

[8]

Elson, J., and Römer, K. 2003. Wireless sensor networks: A new regime for time synchronization. Comput. Comm. Rev. 33, 1, 149--154.

Digital Library

[9]

Finke, G., Jost, V., Queyranne, M., and Sebö, A. 2004. Batch processing with interval graph compatibilities between tasks. In Les Cahiers du Laboratoire, 118. Leibniz-IMAG.

[10]

Ganeriwal, S., Kumar, R., and Srivastava, M. 2003. Timing-Sync protocol for sensor networks. In Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys). 138--149.

Digital Library

[11]

Goel, A., and Estrin, D. 2003. Simultaneous optimization for concave costs: Single sink aggregation or single source buy-at-bulk. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 499--505.

Digital Library

[12]

Heinzelman, W., Chandrakasan, A., and Balakrishnan, H. 2000. Energy efficient communication protocols for wireless microsensor networks. In Proceedings of the Hawaiian International Conference on Systems Science. 3005--3014.

Digital Library

[13]

Hu, F., Cao, X., and May, C. 2005. Optimized scheduling for data aggregation in wireless sensor networks. In Proceedings of the International Conference on Information Technology Coding and Computing (ITCC). 557--561.

Digital Library

[14]

Intanagonwiwat, C., Estrin, D., Govindan, R., and Heidemann, J. 2002. Impact of network density on data aggregation in wireless sensor networks. In Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS). 414--458.

Digital Library

[15]

Intanagonwiwat, C., Govindan, R., and Estrin, D. 2000. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Mobile Computing and Networking. 56--67.

Digital Library

[16]

Kalpakis, K., Dasgupta, K., and Namjoshi, P. 2003. Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks. Comput. Netw. 42, 6, 697--716.

Digital Library

[17]

Lindsey, S., and Raghavendra, C. S. 2000. Pegasis: Power-Efficient gathering in sensor information systems. In Proceedings of the IEEE Aerospace Conference. 1125--1130.

[18]

Madden, S., Franklin, M. J., Hellerstein, J. M., and Hong, W. 2002. Tag: A tiny aggregation service for ad-hoc sensor networks. In Proceedings of the 5th ACM Symposium on Operating System Design and Implementation (OSDI). 131--146.

Digital Library

[19]

Madden, S., Franklin, M. J., Hellerstein, J. M., and Hong, W. 2005. Tinydb: An acquisitional query processing system for sensor networks. ACM Trans. Datab. Syst. 30, 1, 122--173.

Digital Library

[20]

Pottie, G. J., and Kaiser, W. J. 2000. Wireless integrated network sensors. Comm. ACM 43, 5, 51--58.

Digital Library

[21]

Yuan, W., Krishnamurthy, V. S., and Tripathi, S. K. 2003. Synchronization of multiple levels of data fusion in wireless sensor networks. In Proceedings of IEEE GlobeCom. 221--225.

Cited By

Mari MPawŀowski MRen RSankowski PDastani MSichman JAlechina NDignum V(2024)Multi-level Aggregation with Delays and Stochastic ArrivalsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663166(2378-2380)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663166
Khan ASubramanian AWiese A(2024)A PTAS for the horizontal rectangle stabbing problemMathematical Programming: Series A and B10.1007/s10107-024-02106-y206:1-2(607-630)Online publication date: 13-Jun-2024
https://dl.acm.org/doi/10.1007/s10107-024-02106-y
Györgyi PKis TTamási TBékési J(2022)Joint replenishment meets schedulingJournal of Scheduling10.1007/s10951-022-00768-026:1(77-94)Online publication date: 8-Dec-2022
https://dl.acm.org/doi/10.1007/s10951-022-00768-0
Show More Cited By

Index Terms

Latency-constrained aggregation in sensor networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

In-network aggregation trade-offs for data collection in wireless sensor networks

This paper explores in-network aggregation as a power-efficient mechanism for collecting data in wireless sensor networks. In particular, we focus on sensor network scenarios where a large number of nodes produce data periodically. Such communication ...
Data aggregation in sensor networks: Balancing communication and delay costs

In a sensor network the sensors, or nodes, obtain data and have to communicate these data to a central node. Because sensors are battery powered they are highly energy constrained. Data aggregation can be used to combine data of several sensors into a ...
Balancing Energy Consumption to Maximize Network Lifetime in Data-Gathering Sensor Networks

Unbalanced energy consumption is an inherent problem in wireless sensor networks characterized by multihop routing and many-to-one traffic pattern, and this uneven energy dissipation can significantly reduce network lifetime. In this paper, we study the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 6, Issue 1

December 2009

374 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1644015

Issue’s Table of Contents

Copyright © 2009 ACM.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 December 2009

Accepted: 01 March 2008

Revised: 01 February 2008

Received: 01 May 2007

Published in TALG Volume 6, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
472
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mari MPawŀowski MRen RSankowski PDastani MSichman JAlechina NDignum V(2024)Multi-level Aggregation with Delays and Stochastic ArrivalsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663166(2378-2380)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663166
Khan ASubramanian AWiese A(2024)A PTAS for the horizontal rectangle stabbing problemMathematical Programming: Series A and B10.1007/s10107-024-02106-y206:1-2(607-630)Online publication date: 13-Jun-2024
https://dl.acm.org/doi/10.1007/s10107-024-02106-y
Györgyi PKis TTamási TBékési J(2022)Joint replenishment meets schedulingJournal of Scheduling10.1007/s10951-022-00768-026:1(77-94)Online publication date: 8-Dec-2022
https://dl.acm.org/doi/10.1007/s10951-022-00768-0
Khan ASubramanian AWiese A(2022)A PTAS for the Horizontal Rectangle Stabbing ProblemInteger Programming and Combinatorial Optimization10.1007/978-3-031-06901-7_27(361-374)Online publication date: 27-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-06901-7_27
Jurdi RAndrews JHeath R(2021)Scheduling Observers Over a Shared Channel With Hard Delivery DeadlinesIEEE Transactions on Communications10.1109/TCOMM.2020.303217269:1(133-148)Online publication date: Jan-2021
https://doi.org/10.1109/TCOMM.2020.3032172
Bienkowski MBöhm MByrka JChrobak MDürr CFolwarczný LJeż ŁSgall JThang NVeselý P(2021)New results on multi-level aggregationTheoretical Computer Science10.1016/j.tcs.2021.02.016861(133-143)Online publication date: Mar-2021
https://doi.org/10.1016/j.tcs.2021.02.016
Bienkowski MBöhm MByrka JChrobak MDürr CFolwarczný LJeż ŁSgall JThang NVeselý P(2020)Online Algorithms for Multilevel AggregationOperations Research10.1287/opre.2019.184768:1(214-232)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1287/opre.2019.1847
Hong CVarghese B(2019)Resource Management in Fog/Edge ComputingACM Computing Surveys10.1145/332606652:5(1-37)Online publication date: 13-Sep-2019
https://dl.acm.org/doi/10.1145/3326066
Riker ASubtil JCurado MMonteiro E(2019)Towards High Energy Efficiency in the Internet of Things2019 IEEE Symposium on Computers and Communications (ISCC)10.1109/ISCC47284.2019.8969700(1-6)Online publication date: Jun-2019
https://doi.org/10.1109/ISCC47284.2019.8969700
Nonner T(2018)Clique Clustering Yields a PTAS for Max-Coloring Interval GraphsAlgorithmica10.1007/s00453-017-0362-980:10(2941-2956)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s00453-017-0362-9
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents