{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:27:41Z","timestamp":1759638461710,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell'Istruzione, dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["RBIN047MH9"],"award-info":[{"award-number":["RBIN047MH9"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004965","name":"Sixth Framework Programme","doi-asserted-by":"publisher","award":["MRTN-CT-2003-504438"],"award-info":[{"award-number":["MRTN-CT-2003-504438"]}],"id":[{"id":"10.13039\/501100004965","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["FET-15964"],"award-info":[{"award-number":["FET-15964"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/1644015.1644028","type":"journal-article","created":{"date-parts":[[2010,8,24]],"date-time":"2010-08-24T13:16:40Z","timestamp":1282655800000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Latency-constrained aggregation in sensor networks"],"prefix":"10.1145","volume":"6","author":[{"given":"LUCA","family":"Becchetti","sequence":"first","affiliation":[{"name":"Sapienza University of Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alberto","family":"Marchetti-Spaccamela","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Vitaletti","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Korteweg","sequence":"additional","affiliation":[{"name":"TU Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Skutella","sequence":"additional","affiliation":[{"name":"TU Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[{"name":"VU University, and CWI Amsterdam, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,12,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(01)00302-4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.1007\/11841036_11"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8705(03)00009-X"},{"key":"e_1_2_1_4_1","unstructured":"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.   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."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571852"},{"volume-title":"Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS), Workshop on Parallel and Distributed Computing Issues in Wireless and Mobile Computing. 1965--1970","author":"Elson J.","key":"e_1_2_1_6_1","unstructured":"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 . 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."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1060289.1060304"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/774763.774787"},{"key":"e_1_2_1_9_1","unstructured":"Finke G. Jost V. Queyranne M. and Seb\u00f6 A. 2004. Batch processing with interval graph compatibilities between tasks. In Les Cahiers du Laboratoire 118. Leibniz-IMAG.  Finke G. Jost V. Queyranne M. and Seb\u00f6 A. 2004. Batch processing with interval graph compatibilities between tasks. In Les Cahiers du Laboratoire 118. Leibniz-IMAG."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958508"},{"volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 499--505","author":"Goel A.","key":"e_1_2_1_11_1","unstructured":"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 . 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."},{"volume-title":"Proceedings of the Hawaiian International Conference on Systems Science. 3005--3014","author":"Heinzelman W.","key":"e_1_2_1_12_1","unstructured":"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 . 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."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITCC.2005.219"},{"volume-title":"Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS). 414--458","author":"Intanagonwiwat C.","key":"e_1_2_1_14_1","unstructured":"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 . 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."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/345910.345920"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(03)00212-3"},{"volume-title":"Proceedings of the IEEE Aerospace Conference. 1125--1130","author":"Lindsey S.","key":"e_1_2_1_17_1","unstructured":"Lindsey , S. , and Raghavendra , C. S . 2000. Pegasis: Power-Efficient gathering in sensor information systems . In Proceedings of the IEEE Aerospace Conference. 1125--1130 . Lindsey, S., and Raghavendra, C. S. 2000. Pegasis: Power-Efficient gathering in sensor information systems. In Proceedings of the IEEE Aerospace Conference. 1125--1130."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1060289.1060303"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061322"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/332833.332838"},{"volume-title":"Proceedings of IEEE GlobeCom. 221--225","author":"Yuan W.","key":"e_1_2_1_21_1","unstructured":"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 . 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."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1644015.1644028","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1644015.1644028","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:44Z","timestamp":1750278404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1644015.1644028"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1145\/1644015.1644028"],"URL":"https:\/\/doi.org\/10.1145\/1644015.1644028","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2009,12]]},"assertion":[{"value":"2007-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-12-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}