{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:16Z","timestamp":1759638976622,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2006,5,1]],"date-time":"2006-05-01T00:00:00Z","timestamp":1146441600000},"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":[[2006,5]]},"abstract":"<jats:p>We consider the joint optimization of sensor placement and transmission structure for data gathering, where a given number of nodes need to be placed in a field such that the sensed data can be reconstructed at a sink within specified distortion bounds while minimizing the energy consumed for communication. We assume that the nodes use either joint entropy coding based on explicit communication between sensor nodes, where coding is done when side information is available, or Slepian-Wolf coding where nodes have knowledge of network correlation statistics. We consider both maximum and average distortion bounds. We prove that this optimization is NP-complete since it involves an interplay between the spaces of possible transmission structures given radio reachability limitations, and feasible placements satisfying distortion bounds.We address this problem by first looking at the simplified problem of optimal placement in the one-dimensional case. An analytical solution is derived for the case when there is a simple aggregation scheme, and numerical results are provided for the cases when joint entropy encoding is used. We use the insight from our 1-D analysis to extend our results to the 2-D case and compare it to typical uniform random placement and shortest-path tree. Our algorithm for two-dimensional placement and transmission structure provides two to three fold reduction in total power consumption and between one to two orders of magnitude reduction in bottleneck power consumption. We perform an exhaustive performance analysis of our scheme under varying correlation models and model parameters and demonstrate that the performance improvement is typical over a range of data correlation models and parameters. We also study the impact of performing computationally-efficient data conditioning over a local scope rather than the entire network. Finally, we extend our explicit placement results to a randomized placement scheme and show that such a scheme can be effective when deployment does not permit exact node placement.<\/jats:p>","DOI":"10.1145\/1149283.1149284","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"155-181","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":40,"title":["Power-efficient sensor placement and transmission structure for data gathering under distortion constraints"],"prefix":"10.1145","volume":"2","author":[{"given":"Deepak","family":"Ganesan","sequence":"first","affiliation":[{"name":"University of Massachusetts, Amherst, Amherst, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R\u0103zvan","family":"Cristescu","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baltasar","family":"Beferull-Lozano","sequence":"additional","affiliation":[{"name":"Swiss Federal Institute of Technology (EPFL), Valencia, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Cheng P. Liu X. and Chuah C. N. 2004. Energy-aware node placement in wireless sensor networks. In IEEE Globecom.  Cheng P. Liu X. and Chuah C. N. 2004. Energy-aware node placement in wireless sensor networks. In IEEE Globecom."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Cover T. and Thomas J. 1991. Elements of Information Theory. Wiley.   Cover T. and Thomas J. 1991. Elements of Information Theory. Wiley.","DOI":"10.1002\/0471200611"},{"key":"e_1_2_1_3_1","unstructured":"Cressie N. 1991. Spatial Statistics. John Wiley and Sons.  Cressie N. 1991. Spatial Statistics. John Wiley and Sons."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Cristescu R. Beferull-Lozano B. and Vetterli M. 2005. Networked Slepian-Wolf: Theory algorithms and scaling laws. IEEE Trans. Info. Theory. 10.1109\/TIT.2005.858980   Cristescu R. Beferull-Lozano B. and Vetterli M. 2005. Networked Slepian-Wolf: Theory algorithms and scaling laws. IEEE Trans. Info. Theory. 10.1109\/TIT.2005.858980","DOI":"10.1109\/TIT.2005.858980"},{"key":"e_1_2_1_5_1","unstructured":"Cristescu R. Beferull-Lozano B. and Vetterli M. 2004. On network correlated data gathering. In INFOCOM.  Cristescu R. Beferull-Lozano B. and Vetterli M. 2004. On network correlated data gathering. In INFOCOM."},{"key":"e_1_2_1_6_1","unstructured":"Dasgupta K. Kukreja M. and Kalpakis K. 2003. Topology--aware placement and role assignment for energy-efficient information gathering in sensor networks. In IEEE ISCC.   Dasgupta K. Kukreja M. and Kalpakis K. 2003. Topology--aware placement and role assignment for energy-efficient information gathering in sensor networks. In IEEE ISCC."},{"key":"e_1_2_1_7_1","unstructured":"Eidenbenz S. 2002. Approximation algorithms for terrain guarding. IPL. 10.1016\/S0020-0190(01)00255-1   Eidenbenz S. 2002. Approximation algorithms for terrain guarding. IPL. 10.1016\/S0020-0190(01)00255-1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Ganesan D. Cristescu R. and Beferull-Lozano B. 2004. Power efficient node placement and transmission structure for data gathering under distortion constraints. In IPSN. 10.1145\/984622.984643   Ganesan D. Cristescu R. and Beferull-Lozano B. 2004. Power efficient node placement and transmission structure for data gathering under distortion constraints. In IPSN. 10.1145\/984622.984643","DOI":"10.1145\/984622.984643"},{"key":"e_1_2_1_9_1","unstructured":"Goel A. and Estrin D. 2003. Simultaneous optimization for concave costs: Single sink aggregation or single source buy-at-bulk. In ACM-SIAM SODA.   Goel A. and Estrin D. 2003. Simultaneous optimization for concave costs: Single sink aggregation or single source buy-at-bulk. In ACM-SIAM SODA."},{"key":"e_1_2_1_10_1","unstructured":"Hamilton M. Center for Embedded Networked Sensing (CENS): James Reserve Data Management System. http:\/\/dms.jamesreserve.edu\/.  Hamilton M. Center for Embedded Networked Sensing (CENS): James Reserve Data Management System. http:\/\/dms.jamesreserve.edu\/."},{"key":"e_1_2_1_11_1","unstructured":"Heinzelman W. Chandrakasan A. and Balakrishnan H. 2000. Energy-efficient communication protocols for wireless microsensor networks. In HICSS.   Heinzelman W. Chandrakasan A. and Balakrishnan H. 2000. Energy-efficient communication protocols for wireless microsensor networks. In HICSS."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Intanagonwiwat C. Govindan R. and Estrin D. 2000. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In ACM\/IEEE Mobicom. Boston MA. 10.1145\/345910.345920   Intanagonwiwat C. Govindan R. and Estrin D. 2000. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In ACM\/IEEE Mobicom. Boston MA. 10.1145\/345910.345920","DOI":"10.1145\/345910.345920"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Lindsey S. Raghavendra C. and Sivalingam K. 2001. Data gathering in sensor networks using the energy delay metric. In IPDPS.   Lindsey S. Raghavendra C. and Sivalingam K. 2001. Data gathering in sensor networks using the energy delay metric. In IPDPS.","DOI":"10.1109\/TPDS.2002.1036066"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Marco D. Duarte-Melo E. Liu M. and Neuhoff D. 2003. On the many-to-one transport capacity of a dense wireless sensor network and the compressibility of its data. In IPSN.   Marco D. Duarte-Melo E. Liu M. and Neuhoff D. 2003. On the many-to-one transport capacity of a dense wireless sensor network and the compressibility of its data. In IPSN.","DOI":"10.1007\/3-540-36978-3_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/332833.332838"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Rappaport T. S. 1996. Wireless Communications Principles and Practice. Prentice Hall.   Rappaport T. S. 1996. Wireless Communications Principles and Practice. Prentice Hall.","DOI":"10.1007\/978-1-4615-5491-2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Slepian D. and Wolf J. 1973. Noiseless coding of correlated information sources. In IEEE Trans. Information Theory. Vol. IT-19. 471--480.  Slepian D. and Wolf J. 1973. Noiseless coding of correlated information sources. In IEEE Trans. Information Theory. Vol. IT-19. 471--480.","DOI":"10.1109\/TIT.1973.1055037"},{"key":"e_1_2_1_18_1","unstructured":"Ye W. Heidemann J. and Estrin D. 2002. An energy-efficient mac protocol for wireless sensor networks. In IEEE Infocom.  Ye W. Heidemann J. and Estrin D. 2002. An energy-efficient mac protocol for wireless sensor networks. In IEEE Infocom."}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1149283.1149284","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1149283.1149284","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:31:13Z","timestamp":1750264273000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1149283.1149284"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,5]]}},"alternative-id":["10.1145\/1149283.1149284"],"URL":"https:\/\/doi.org\/10.1145\/1149283.1149284","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2006,5]]},"assertion":[{"value":"2006-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}