{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:45Z","timestamp":1763468025288,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,2,1]],"date-time":"2011-02-01T00:00:00Z","timestamp":1296518400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-0509383CNS-0625518CNS-0932392ANI-00331481CCR-0120778CCF-0448095CCF-0729022CCF-0325453IIS-0329064CNS-0403340CCR-0122581"],"award-info":[{"award-number":["CNS-0509383CNS-0625518CNS-0932392ANI-00331481CCR-0120778CCF-0448095CCF-0729022CCF-0325453IIS-0329064CNS-0403340CCR-0122581"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0509383CNS-0625518CNS-0932392ANI-00331481CCR-0120778CCF-0448095CCF-0729022CCF-0325453IIS-0329064CNS-0403340CCR-0122581"],"award-info":[{"award-number":["CNS-0509383CNS-0625518CNS-0932392ANI-00331481CCR-0120778CCF-0448095CCF-0729022CCF-0325453IIS-0329064CNS-0403340CCR-0122581"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N000140911044"],"award-info":[{"award-number":["N000140911044"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CNS-0509383CNS-0625518CNS-0932392ANI-00331481CCR-0120778CCF-0448095CCF-0729022CCF-0325453IIS-0329064CNS-0403340CCR-0122581"],"award-info":[{"award-number":["CNS-0509383CNS-0625518CNS-0932392ANI-00331481CCR-0120778CCF-0448095CCF-0729022CCF-0325453IIS-0329064CNS-0403340CCR-0122581"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["CNS-0509383CNS-0625518CNS-0932392ANI-00331481CCR-0120778CCF-0448095CCF-0729022CCF-0325453IIS-0329064CNS-0403340CCR-0122581"],"award-info":[{"award-number":["CNS-0509383CNS-0625518CNS-0932392ANI-00331481CCR-0120778CCF-0448095CCF-0729022CCF-0325453IIS-0329064CNS-0403340CCR-0122581"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2011,2]]},"abstract":"<jats:p>\n            When monitoring spatial phenomena with wireless sensor networks, selecting the best sensor placements is a fundamental task. Not only should the sensors be informative, but they should also be able to communicate efficiently. In this article, we present a data-driven approach that addresses the three central aspects of this problem: measuring the predictive quality of a set of sensor locations (regardless of whether sensors were ever placed at these locations), predicting the communication cost involved with these placements, and designing an algorithm with provable quality guarantees that optimizes the NP-hard trade-off. Specifically, we use data from a pilot deployment to build nonparametric probabilistic models called\n            <jats:italic>Gaussian Processes<\/jats:italic>\n            (GPs) both for the spatial phenomena of interest and for the spatial variability of link qualities, which allows us to estimate predictive power and communication cost of unsensed locations. Surprisingly, uncertainty in the representation of link qualities plays an important role in estimating communication costs. Using these models, we present a novel, polynomial-time, data-driven algorithm, PSPIEL, which selects Sensor Placements at Informative and communication-Efficient Locations. Our approach exploits two important properties of this problem:\n            <jats:italic>submodularity<\/jats:italic>\n            , formalizing the intuition that adding a node to a small deployment can help more than adding a node to a large deployment; and\n            <jats:italic>locality<\/jats:italic>\n            , under which nodes that are far from each other provide\n            <jats:italic>almost<\/jats:italic>\n            independent information. Exploiting these properties, we prove strong approximation guarantees for our PSPIEL approach. In addition, we show how our placements can be made robust against changes in the environment, and how PSPIEL can be used to plan informative paths for information gathering using mobile robots. We also provide extensive experimental validation of this practical approach on several real-world placement problems, and built a complete system implementation on 46 Tmote Sky motes, demonstrating significant advantages over existing methods.\n          <\/jats:p>","DOI":"10.1145\/1921621.1921625","type":"journal-article","created":{"date-parts":[[2011,3,2]],"date-time":"2011-03-02T18:19:53Z","timestamp":1299089993000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["Robust sensor placements at informative and communication-efficient locations"],"prefix":"10.1145","volume":"7","author":[{"given":"Andreas","family":"Krause","sequence":"first","affiliation":[{"name":"California Institute of Technology, Pasadena, CA"}]},{"given":"Carlos","family":"Guestrin","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]},{"given":"Jon","family":"Kleinberg","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}]}],"member":"320","published-online":{"date-parts":[[2011,2,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979528826X"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132905.1132921"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1127777.1127783"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-005-1412-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-7152(84)90020-8"},{"volume-title":"Proceedings of the ACM\/IEEE International Conference on Information Processing in Sensor Networks.","author":"Cerpa A.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062689.1062741"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1177009939"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","author":"Chekuri C.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.9"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-006-0724-8"},{"key":"e_1_2_1_12_1","unstructured":"Cressie N. A. 1991. Statistics for Spatial Data. Wiley.  Cressie N. A. 1991. Statistics for Spatial Data. Wiley."},{"key":"e_1_2_1_13_1","unstructured":"Csato L. Fokue E. Opper M. Schottky B. and Winther O. 2000. Efficient approaches to gaussian process classification. In Advances in Neural Information Processing Systems.  Csato L. Fokue E. Opper M. Schottky B. and Winther O. 2000. Efficient approaches to gaussian process classification. In Advances in Neural Information Processing Systems."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374384"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/938985.939000"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases.","author":"Deshpande A.","key":"e_1_2_1_16_1"},{"volume-title":"Proceedings of the IEEE International Conference on Communications.","author":"Ergen S. C.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSP.2007.4301342"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1946.234568"},{"key":"e_1_2_1_20_1","article-title":"Approximation algorithms for submodular set cover with applications. TIEICE: IEICE","author":"Fujito T.","year":"2000","journal-title":"Trans. Comm.\/Electron.\/Inf. Syst. E83-D, 3."},{"volume-title":"Proceedings of the 3rd International Conference on ADHOC Networks and Wireless (ADHOC-NOW).","author":"Funke S.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060650"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/984622.984624"},{"volume-title":"Proceedings of the Annual IEEE Symposium on Foundations of Computer Science.","author":"Gupta A.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/778415.778438"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","author":"Johnson D. S.","key":"e_1_2_1_26_1"},{"volume-title":"Proceedings of the International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks.","author":"Kar K.","key":"e_1_2_1_27_1"},{"volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence Nectar Track.","author":"Krause A.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1641503.1641516"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1127777.1127782"},{"key":"e_1_2_1_31_1","unstructured":"Krause A. McMahan B. Guestrin C. and Gupta A. 2007a. Selecting observations against adversarial objectives. In Advances in Neural Information Processing Systems.  Krause A. McMahan B. Guestrin C. and Gupta A. 2007a. Selecting observations against adversarial objectives. In Advances in Neural Information Processing Systems."},{"key":"e_1_2_1_32_1","unstructured":"Krause A. Singh A. and Guestrin C. 2007b. Near-optimal sensor placements in Gaussian processes: Theory efficient algorithms and empirical studies. J. Mach. Learn. Res..   Krause A. Singh A. and Guestrin C. 2007b. Near-optimal sensor placements in Gaussian processes: Theory efficient algorithms and empirical studies. J. Mach. Learn. Res.."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.11.002"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2007.18"},{"volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence Nectar Track.","author":"Meliou A.","key":"e_1_2_1_35_1"},{"volume-title":"Proceedings of the Conference on Optimization Techniques","series-title":"Lecture Notes in Computer Science","author":"Minoux M.","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","unstructured":"Morrow R. 2004. Wireless Network Coexistence 1st Ed. McGraw-Hill Professional.  Morrow R. 2004. Wireless Network Coexistence 1st Ed. McGraw-Hill Professional."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/89.4.819"},{"volume-title":"Wireless Communication: Principles and Practice","year":"2000","author":"Rappaport T.","key":"e_1_2_1_40_1"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Rasmussen C. E. and Williams C. K. 2006. Gaussian Processes for Machine Learning. Adaptive Computation and Machine Learning. The MIT Press.   Rasmussen C. E. and Williams C. K. 2006. Gaussian Processes for Machine Learning. Adaptive Computation and Machine Learning. The MIT Press.","DOI":"10.7551\/mitpress\/3206.001.0001"},{"volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 2204--2211","author":"Singh A.","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Vazirani V. V. 2003. Approximation Algorithms. Springer.   Vazirani V. V. 2003. Approximation Algorithms. Springer.","DOI":"10.1007\/978-3-662-04565-7"},{"key":"e_1_2_1_44_1","unstructured":"Widmann M. and Bretherton C. S. 1999. 50 km resolution daily precipitation for the pacific northwest. http:\/\/www.jisao.washington.edu\/data_sets\/widmann\/.  Widmann M. and Bretherton C. S. 1999. 50 km resolution daily precipitation for the pacific northwest. http:\/\/www.jisao.washington.edu\/data_sets\/widmann\/."},{"key":"e_1_2_1_45_1","unstructured":"Zhao F. and Guibas L. 2004. Wireless Sensor Networks: An Information Processing Approach. Morgan Kaufmann.   Zhao F. and Guibas L. 2004. Wireless Sensor Networks: An Information Processing Approach. Morgan Kaufmann."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/79.985685"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1240226.1240227"}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921621.1921625","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1921621.1921625","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:52:11Z","timestamp":1750243931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921621.1921625"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["10.1145\/1921621.1921625"],"URL":"https:\/\/doi.org\/10.1145\/1921621.1921625","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2011,2]]},"assertion":[{"value":"2008-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-02-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}