{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:30:15Z","timestamp":1750307415466,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2010,8,1]],"date-time":"2010-08-01T00:00:00Z","timestamp":1280620800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2010,8]]},"abstract":"<jats:p>\n            We consider two related data gathering problems for wireless sensor networks (WSNs). The MLDA problem is concerned with maximizing the system lifetime\n            <jats:italic>T<\/jats:italic>\n            so that we can perform\n            <jats:italic>T<\/jats:italic>\n            rounds of data gathering with in-network aggregation, given the initial available energy of the sensors. The M\n            <jats:sup>2<\/jats:sup>\n            EDA problem is concerned with minimizing the maximum energy consumed by any one sensor when performing\n            <jats:italic>T<\/jats:italic>\n            rounds of data gathering with in-network aggregation, for a given\n            <jats:italic>T<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            We provide an effective algorithm for finding an everywhere sparse integral solution to the M\n            <jats:sup>2<\/jats:sup>\n            EDA problem which is within a factor of \u03b1 = 1+ 4\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>T<\/jats:italic>\n            of the optimum, where\n            <jats:italic>n<\/jats:italic>\n            is the number of nodes. A solution is everywhere sparse if the number of communication links for any subset\n            <jats:italic>X<\/jats:italic>\n            of nodes is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>X<\/jats:italic>\n            ), in our case at most 4|\n            <jats:italic>X<\/jats:italic>\n            |. Since often\n            <jats:italic>T<\/jats:italic>\n            = \u03c9(\n            <jats:italic>n<\/jats:italic>\n            ), we obtain the first everywhere sparse, asymptotically optimal integral solutions to the M\n            <jats:sup>2<\/jats:sup>\n            EDA problem. Everywhere sparse solutions are desirable since then almost all sensors have small number of incident communication links and small overhead for maintaining state.\n          <\/jats:p>\n          <jats:p>\n            We also show that the MLDA and M\n            <jats:sup>2<\/jats:sup>\n            EDA problems are essentially equivalent, in the sense that we can obtain an optimal fractional solution to an instance of the MLDA problem by scaling an optimal fractional solution to a suitable instance of the M\n            <jats:sup>2<\/jats:sup>\n            EDA problem. As a result, our algorithm is effective at finding everywhere sparse, asymptotically optimal, integral solutions to the MLDA problem, when the initial available energy of the sensors is sufficient for supporting optimal system lifetime which is \u03c9(\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>","DOI":"10.1145\/1806895.1806904","type":"journal-article","created":{"date-parts":[[2010,8,17]],"date-time":"2010-08-17T12:19:29Z","timestamp":1282047569000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Everywhere sparse approximately optimal minimum energy data gathering and aggregation in sensor networks"],"prefix":"10.1145","volume":"7","author":[{"given":"Konstantinos","family":"Kalpakis","sequence":"first","affiliation":[{"name":"University of Maryland Baltimore County, Baltimore, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,8,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2002.1024422"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00003-6"},{"key":"e_1_2_1_3_1","unstructured":"Bertsimas D. and Tsitsiklis J. N. 1997. Introduction to Linear Optimization. Athena Scientific Nashua NH.   Bertsimas D. and Tsitsiklis J. N. 1997. Introduction to Linear Optimization. Athena Scientific Nashua NH."},{"volume-title":"Proceedings of the International Conference on Communications.","author":"Bhardwaj M.","key":"e_1_2_1_4_1","unstructured":"Bhardwaj , M. , Garnett , T. , and Chandrakasan , A . 2001. Upper bounds on the lifetime of sensor networks . In Proceedings of the International Conference on Communications. Bhardwaj, M., Garnett, T., and Chandrakasan, A. 2001. Upper bounds on the lifetime of sensor networks. In Proceedings of the International Conference on Communications."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2004.833122"},{"volume-title":"Surveys in Combinatorics","author":"Frank A.","key":"e_1_2_1_6_1","unstructured":"Frank , A. 1993. Applications of submodular functions . In Surveys in Combinatorics . London Mathematical Society Lecture Note Series 187, K. Walker, Ed. Cambridge University Press , Cambridge, U.K., 85--136. Frank, A. 1993. Applications of submodular functions. In Surveys in Combinatorics. London Mathematical Society Lecture Note Series 187, K. Walker, Ed. Cambridge University Press, Cambridge, U.K., 85--136."},{"volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. 300--309","author":"Garg N.","key":"e_1_2_1_7_1","unstructured":"Garg , N. and Konemann , J . 1998. Faster and simpler algorithms for multicommodity flow and other fractional packing problems . In Proceedings of the IEEE Symposium on Foundations of Computer Science. 300--309 . Garg, N. and Konemann, J. 1998. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In Proceedings of the IEEE Symposium on Foundations of Computer Science. 300--309."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.48"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/313451.313529"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/820264.820485"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2006.132"},{"key":"e_1_2_1_13_1","unstructured":"Hurkens C. A. J. Lovasz L. Schrijver A. and Tardos E. 1988. How to tidy up your set-system&quest; Combinatorics 52 309--314.  Hurkens C. A. J. Lovasz L. Schrijver A. and Tardos E. 1988. How to tidy up your set-system&quest; Combinatorics 52 309--314."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/313451.313558"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(03)00212-3"},{"key":"e_1_2_1_17_1","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"Korte B.","year":"1991","unstructured":"Korte , B. and Vygen , J . 1991 . Combinatorial Optimization: Theory and Algorithms . Springer Verlag , Berlin, Germany . Korte, B. and Vygen, J. 1991. Combinatorial Optimization: Theory and Algorithms. Springer Verlag, Berlin, Germany."},{"volume-title":"Proceedings of the International Workshop on Distributed Event-Based Systems.","author":"Krishnamachari B.","key":"e_1_2_1_18_1","unstructured":"Krishnamachari , B. , Estrin , D. , and Wicker , S . 2002. The impact of data aggregation in wireless sensor networks . In Proceedings of the International Workshop on Distributed Event-Based Systems. Krishnamachari, B., Estrin, D., and Wicker, S. 2002. The impact of data aggregation in wireless sensor networks. In Proceedings of the International Workshop on Distributed Event-Based Systems."},{"volume-title":"Proceedings of the IEEE Aerospace Conference.","author":"Lindsey S.","key":"e_1_2_1_19_1","unstructured":"Lindsey , S. and Raghavendra , C. S . 2002. PEGASIS: Power efficient gathering in sensor information systems . In Proceedings of the IEEE Aerospace Conference. Lindsey, S. and Raghavendra, C. S. 2002. PEGASIS: Power efficient gathering in sensor information systems. In Proceedings of the IEEE Aerospace Conference."},{"volume-title":"Proceedings of the IPDPS Workshop on Issues in Wireless Networks and Mobile Computing.","author":"Lindsey S.","key":"e_1_2_1_20_1","unstructured":"Lindsey , S. , Raghavendra , C. S. , and Sivalingam , K . 2001. Data gathering in sensor networks using the energy&ast;delay metric . In Proceedings of the IPDPS Workshop on Issues in Wireless Networks and Mobile Computing. Lindsey, S., Raghavendra, C. S., and Sivalingam, K. 2001. Data gathering in sensor networks using the energy&ast;delay metric. In Proceedings of the IPDPS Workshop on Issues in Wireless Networks and Mobile Computing."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031510"},{"key":"e_1_2_1_22_1","volume-title":"-P","author":"Luo J.","year":"2005","unstructured":"Luo , J. and Hubaux , J . -P . 2005 . Joint mobility and routing for lifetime elongation in wireless sensor networks. In Proceedings of INFOCOM. 1735--1746. Luo, J. and Hubaux, J.-P. 2005. Joint mobility and routing for lifetime elongation in wireless sensor networks. In Proceedings of INFOCOM. 1735--1746."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1060289.1060303"},{"volume-title":"Proceedings of the 4th IEEE Workshop on Mobile Computing and Systems Applications.","author":"Madden S.","key":"e_1_2_1_24_1","unstructured":"Madden , S. , Szewczyk , R. , Franklin , M. J. , and Culler , D . 2002b. Supporting aggregate queries over ad-hoc wireless sensor networks . In Proceedings of the 4th IEEE Workshop on Mobile Computing and Systems Applications. Madden, S., Szewczyk, R., Franklin, M. J., and Culler, D. 2002b. Supporting aggregate queries over ad-hoc wireless sensor networks. In Proceedings of the 4th IEEE Workshop on Mobile Computing and Systems Applications."},{"volume-title":"Proceedings of the Conference on VLSI Design.","author":"Min R.","key":"e_1_2_1_25_1","unstructured":"Min , R. , Bhardwaj , M. , Cho , S. , Sinha , A. , Shih , E. , Wang , A. , and Chandrakasan , A . 2001. Low-power wireless sensor networks . In Proceedings of the Conference on VLSI Design. Min, R., Bhardwaj, M., Cho, S., Sinha, A., Shih, E., Wang, A., and Chandrakasan, A. 2001. Low-power wireless sensor networks. In Proceedings of the Conference on VLSI Design."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2005.68"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9098-2"},{"volume-title":"Proceedings of the IEEE Computer Society Annual Workshop on VLSI.","author":"Rabaey J.","key":"e_1_2_1_28_1","unstructured":"Rabaey , J. , Ammer , J. , da Silva Jr , J. , and Patel , D . 2000. PicoRadio: Ad-hoc wireless networking of ubiquitous low-energy sensor\/monitor nodes . In Proceedings of the IEEE Computer Society Annual Workshop on VLSI. Rabaey, J., Ammer, J., da Silva Jr, J., and Patel, D. 2000. PicoRadio: Ad-hoc wireless networking of ubiquitous low-energy sensor\/monitor nodes. In Proceedings of the IEEE Computer Society Annual Workshop on VLSI."},{"volume-title":"Proceedings of INFOCOM.","author":"Sankar A.","key":"e_1_2_1_29_1","unstructured":"Sankar , A. and Liu , Z . 2004. Maximum lifetime routing in wireless ad-hoc networks . In Proceedings of INFOCOM. Sankar, A. and Liu, Z. 2004. Maximum lifetime routing in wireless ad-hoc networks. In Proceedings of INFOCOM."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SNPD-SAWN.2006.22"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2006.04709"}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806895.1806904","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1806895.1806904","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:37Z","timestamp":1750246777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806895.1806904"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["10.1145\/1806895.1806904"],"URL":"https:\/\/doi.org\/10.1145\/1806895.1806904","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2010,8]]},"assertion":[{"value":"2008-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-08-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}