{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T16:13:16Z","timestamp":1761581596987,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,8,16]],"date-time":"2017-08-16T00:00:00Z","timestamp":1502841600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Basic Science Research Program through the National Research Foundation of Korea"},{"name":"Institute for Information 8 Communications Technology Promotion"},{"name":"Korea government","award":["B0126-17-1046"],"award-info":[{"award-number":["B0126-17-1046"]}]},{"name":"Ministry of Science, ICT 8 Future Planning (MSIP) of Republic of Korea","award":["NRF-2016R1A2B1014934"],"award-info":[{"award-number":["NRF-2016R1A2B1014934"]}]},{"name":"Research of Network Virtualization Platform and Service for SDN 2.0 Realization"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2017,8,31]]},"abstract":"<jats:p>We consider the energy efficiency of collecting sparse data in wireless sensor networks using compressive sensing (CS). We use a sparse random matrix as the sensing matrix, which we call Sparse Random Sampling (SRS). In SRS, only a randomly selected subset of nodes, called the source nodes, are required to report data to the sink. Given the source nodes, we intend to construct a data gathering tree such that (1) it is rooted at the sink and spans every source node and (2) the minimum residual energy of the tree nodes after the data collection is maximized. We first show that this problem is NP-complete and then develop a polynomial time algorithm to approximately solve the problem. We greedily construct a sequence of data gathering trees over multiple rounds and propose a polynomial-time algorithm to collect linearly combined measurements at each round. We show that the proposed algorithm is provably near-optimal. Simulation and experimental results show that the proposed algorithm excels not only in increasing the minimum residual energy, but also in extending the network lifetime.<\/jats:p>","DOI":"10.1145\/3085576","type":"journal-article","created":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T11:49:04Z","timestamp":1503575344000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Energy-Efficient Collection of Sparse Data in Wireless Sensor Networks Using Sparse Random Matrices"],"prefix":"10.1145","volume":"13","author":[{"given":"Xiaohan","family":"Yu","sequence":"first","affiliation":[{"name":"Zhejiang Gongshang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1226-0147","authenticated-orcid":false,"given":"Seung Jun","family":"Baek","sequence":"additional","affiliation":[{"name":"Korea University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,8,16]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1109\/WF-IoT.2015.7389098"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1109\/MCOM.2002.1024422"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1109\/MSP.2007.4286571"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1007\/s00365-007-9003-x"},{"doi-asserted-by":"crossref","unstructured":"Jean-Daniel Boissonnat and Mariette Yvinec. 1998. Algorithmic Geometry. Cambridge University Press.  Jean-Daniel Boissonnat and Mariette Yvinec. 1998. Algorithmic Geometry. Cambridge University Press.","key":"e_1_2_1_5_1","DOI":"10.1017\/CBO9781139172998"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1109\/TVT.2008.2008715"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/1182807.1182838"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1109\/MSP.2007.914731"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1109\/TVT.2010.2054842"},{"key":"e_1_2_1_10_1","volume-title":"Cambridge, MA: MIT Press.","author":"Cormen T.","year":"2009","edition":"3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/1993042.1993049"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1109\/TIT.2006.871582"},{"volume-title":"Proceedings of the European Conference on Wireless Sensor Networks (EWSN), Poster\/Demo session","year":"2007","author":"Dunkels Adam","key":"e_1_2_1_13_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1109\/LCN.2004.38"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1016\/j.adhoc.2013.12.004"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1017\/CBO9780511794308"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1006\/jagm.1994.1042"},{"unstructured":"M. Garey and D. Johnson. 2002. Computers and Intractability. W.H. Freeman.  M. Garey and D. Johnson. 2002. Computers and Intractability. W.H. Freeman.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","first-page":"6","article-title":"Sparse recovery using sparse matrices","volume":"98","author":"Gilber A.","year":"2010","journal-title":"Proceedings of the IEEE"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1016\/j.future.2013.01.010"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1109\/MSP.2007.914732"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1109\/TII.2010.2051813"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1109\/JSEN.2013.2244036"},{"volume-title":"Sparse recovery with very sparse compressed counting. arXiv:1401.0201","year":"2013","author":"Li Ping","key":"e_1_2_1_24_1"},{"volume-title":"Proceedings of the 27th Conference on Learning Theory. 1058--1077","year":"2014","author":"Li Ping","key":"e_1_2_1_25_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1145\/381677.381687"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1109\/TMC.2007.250667"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1109\/TPDS.2002.1036066"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1145\/1614320.1614337"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1109\/SURV.2013.042313.00197"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1109\/ITA.2009.5044947"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1109\/TWC.2012.081612.110612"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1109\/79.985679"},{"unstructured":"Gabriel Robins and Alexander Zelikovsky. 2000. Improved Steiner tree approximation in graphs. In SODA. Citeseer 770--779.  Gabriel Robins and Alexander Zelikovsky. 2000. Improved Steiner tree approximation in graphs. In SODA. Citeseer 770--779.","key":"e_1_2_1_34_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1504\/IJSNET.2009.028024"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1145\/321879.321884"},{"volume-title":"2.4 GHz IEEE 802.15. 4\/ZigBee-ready RF transceiver. Available at: http:\/\/www.ti.com\/lit\/gpn\/cc2420. 53","year":"2006","key":"e_1_2_1_37_1"},{"unstructured":"Texas_Instruments. 2009. MSP430 F1611 datasheet. Available at TI Website. (2009) 77.  Texas_Instruments. 2009. MSP430 F1611 datasheet. Available at TI Website. (2009) 77.","key":"e_1_2_1_38_1"},{"volume-title":"Proceedings of the 6th ACM\/IEEE International Conference on Information Processing Sensor Networks (IPSN\u201907)","author":"Wang W.","key":"e_1_2_1_39_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1109\/TNET.2010.2045896"}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3085576","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3085576","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:37:01Z","timestamp":1750217821000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3085576"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,16]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/3085576"],"URL":"https:\/\/doi.org\/10.1145\/3085576","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2017,8,16]]},"assertion":[{"value":"2016-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}