{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T19:48:37Z","timestamp":1760384917706,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,2,1]],"date-time":"2009-02-01T00:00:00Z","timestamp":1233446400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007523","name":"Advanced Cyberinfrastructure","doi-asserted-by":"publisher","award":["ANI-0308631"],"award-info":[{"award-number":["ANI-0308631"]}],"id":[{"id":"10.13039\/100007523","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":[[2009,2]]},"abstract":"<jats:p>One of the useful approaches to exploit redundancy in a sensor network is to keep active only a small subset of sensors that are sufficient to cover the region required to be monitored. The set of active sensors should also form a connected communication graph, so that they can autonomously respond to application queries and\/or tasks. Such a set of active sensors is known as a connected sensor cover, and the problem of selecting a minimum connected sensor cover has been well studied when the transmission radius and sensing radius of each sensor is fixed. In this article, we address the problem of selecting a minimum energy-cost connected sensor cover, when each sensor node can vary its sensing and transmission radius; larger sensing or transmission radius entails higher energy cost.<\/jats:p>\n          <jats:p>\n            For the aforesaid problem, we design various centralized and distributed algorithms, and compare their performance through extensive experiments. One of the designed centralized algorithms (called CGA) is shown to perform within an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) factor of the optimal solution, where\n            <jats:italic>n<\/jats:italic>\n            is the size of the network. We have also designed a localized algorithm based on Voronoi diagrams which is empirically shown to perform very close to CGA and, due to its communication-efficiency, results in significantly prolonging the network lifetime. We also extend the aforementioned algorithms to incorporate fault tolerance. In particular, we show how to extend the algorithms to address the minimum energy-cost connected sensor\n            <jats:italic>k<\/jats:italic>\n            -cover problem, in which every point in the query region needs to be covered by at least\n            <jats:italic>k<\/jats:italic>\n            distinct active sensors. The CGA preserves the approximation bound in this case. We also propose a localized topology control scheme to preserve\n            <jats:italic>k<\/jats:italic>\n            -connectivity, and use it to extend the Voronoi-based approach to computing a minimum energy-cost\n            <jats:italic>k<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            -connected\n            <jats:italic>k<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            -cover. We study the performance of our proposed algorithms through extensive simulations.\n          <\/jats:p>","DOI":"10.1145\/1464420.1464428","type":"journal-article","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T16:42:19Z","timestamp":1234284139000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":68,"title":["Variable radii connected sensor cover in sensor networks"],"prefix":"10.1145","volume":"5","author":[{"given":"Zongheng","family":"Zhou","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, NY"}]},{"given":"Samir R.","family":"Das","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY"}]},{"given":"Himanshu","family":"Gupta","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY"}]}],"member":"320","published-online":{"date-parts":[[2009,2,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/mathworld.wolfram.com\/VoronoiDiagram.html.  http:\/\/mathworld.wolfram.com\/VoronoiDiagram.html."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/513800.513820"},{"volume-title":"Proceedings of the International Conference on Computer Communications and Networks (IC3N).","author":"Bahramgiri M.","key":"e_1_2_1_3_1","unstructured":"Bahramgiri , M. , Hajiaghayi , M. , and Mirrokni , V . 2002. Fault-Tolerant and 3-dimensional distributed topology control algorithms in wireless multihop networks . In Proceedings of the International Conference on Computer Communications and Networks (IC3N). Bahramgiri, M., Hajiaghayi, M., and Mirrokni, V. 2002. Fault-Tolerant and 3-dimensional distributed topology control algorithms in wireless multihop networks. In Proceedings of the International Conference on Computer Communications and Networks (IC3N)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/570645.570667"},{"volume-title":"Proceedings of the IEEE International Conference on Wireless And Mobile Computing, Networking And Communications (WiMob).","author":"Cardei M.","key":"e_1_2_1_5_1","unstructured":"Cardei , M. , Wu , J. , Lu , M. , and Pervaiz , M . 2005. Maximum network lifetime in wireless sensor networks with adjustable sensing ranges . In Proceedings of the IEEE International Conference on Wireless And Mobile Computing, Networking And Communications (WiMob). Cardei, M., Wu, J., Lu, M., and Pervaiz, M. 2005. Maximum network lifetime in wireless sensor networks with adjustable sensing ranges. In Proceedings of the IEEE International Conference on Wireless And Mobile Computing, Networking And Communications (WiMob)."},{"volume-title":"Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).","author":"Cartigny J.","key":"e_1_2_1_6_1","unstructured":"Cartigny , J. , Simplot , D. , and Stojmenovic , I . 2003. Localized minimum-energy broadcasting in ad hoc networks . In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom). Cartigny, J., Simplot, D., and Stojmenovic, I. 2003. Localized minimum-energy broadcasting in ad hoc networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2002.1146711"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/381677.381686"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/513800.513821"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2005.302"},{"volume-title":"Proceedings of the International Conference on Computer Communications and Networks (IC3N).","author":"Das B.","key":"e_1_2_1_11_1","unstructured":"Das , B. , Sivakumar , R. , and Bhargavan , V . 1997. Routing in ad hoc networks using a spine . In Proceedings of the International Conference on Computer Communications and Networks (IC3N). Das, B., Sivakumar, R., and Bhargavan, V. 1997. Routing in ad hoc networks using a spine. In Proceedings of the International Conference on Computer Communications and Networks (IC3N)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SNPD-SAWN.2006.46"},{"key":"e_1_2_1_13_1","unstructured":"Foley J. Dam A. V. Feiner S. and Hughes J. 1990. Computer Graphics Principles and Practice. Addison Wesley.   Foley J. Dam A. V. Feiner S. and Hughes J. 1990. Computer Graphics Principles and Practice. Addison Wesley."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009201"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/778415.778438"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/938985.939016"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/984622.984685"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.163414"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1023720.1023735"},{"volume-title":"Proceedings of the Hawaii International Conference on System Sciences.","author":"Laouiti A.","key":"e_1_2_1_20_1","unstructured":"Laouiti , A. , Qayyum , A. , and Viennot , L . 2002. Multipoint relaying: An efficient technique for flooding in mobile wireless networks . In Proceedings of the Hawaii International Conference on System Sciences. Laouiti, A., Qayyum, A., and Viennot, L. 2002. Multipoint relaying: An efficient technique for flooding in mobile wireless networks. In Proceedings of the Hawaii International Conference on System Sciences."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2004.842229"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1023720.1023747"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/778415.778431"},{"volume-title":"Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).","author":"Meguerdichian S.","key":"e_1_2_1_24_1","unstructured":"Meguerdichian , S. , Koushanfar , F. , Potkonjak , M. , and Srivastava , M . 2001. Coverage problems in wireless ad-hoc sensor networks . In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom). Meguerdichian, S., Koushanfar, F., Potkonjak, M., and Srivastava, M. 2001. Coverage problems in wireless ad-hoc sensor networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/381677.381691"},{"key":"e_1_2_1_26_1","volume-title":"Computational Geometry in C","author":"O'Rourke J.","unstructured":"O'Rourke , J. 1998. Computational Geometry in C , 2 nd ed. Cambridge University Press . O'Rourke, J. 1998. Computational Geometry in C, 2nd ed. Cambridge University Press.","edition":"2"},{"key":"e_1_2_1_27_1","unstructured":"Osiris. 2008. Osiris photoelectric sensors. http:\/\/schneider-electric.ca\/www\/en\/products\/sensors2000\/html\/osiris.htm.  Osiris. 2008. Osiris photoelectric sensors. http:\/\/schneider-electric.ca\/www\/en\/products\/sensors2000\/html\/osiris.htm."},{"volume-title":"Proceedings of the International Workshop on Information Processing in Sensor Networks (IPSN).","author":"Pattem S.","key":"e_1_2_1_28_1","unstructured":"Pattem , S. , Poduri , S. , and Krishnamachari , B . 2003. Energy-Quality tradeoffs for target tracking in wireless sensor networks . In Proceedings of the International Workshop on Information Processing in Sensor Networks (IPSN). Pattem, S., Poduri, S., and Krishnamachari, B. 2003. Energy-Quality tradeoffs for target tracking in wireless sensor networks. In Proceedings of the International Workshop on Information Processing in Sensor Networks (IPSN)."},{"volume-title":"Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).","author":"Shakkottai S.","key":"e_1_2_1_29_1","unstructured":"Shakkottai , S. , Srikant , R. , and Shroff , N . 2003. Unreliable sensor grids: Coverage, connectivity and diameter . In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom). Shakkottai, S., Srikant, R., and Shroff, N. 2003. Unreliable sensor grids: Coverage, connectivity and diameter. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom)."},{"volume-title":"Proceedings of the International Conference on Communications (ICC).","author":"Slijepcevic S.","key":"e_1_2_1_30_1","unstructured":"Slijepcevic , S. and Potkonjak , M . 2001. Power efficient organization of wireless sensor networks . In Proceedings of the International Conference on Communications (ICC). Slijepcevic, S. and Potkonjak, M. 2001. Power efficient organization of wireless sensor networks. In Proceedings of the International Conference on Communications (ICC)."},{"volume-title":"Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).","author":"Wan P.","key":"e_1_2_1_31_1","unstructured":"Wan , P. , Alzoubi , K. , and Frieder , O . 2002. Distributed construction of connected dominating set in wireless ad hoc networks . In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom). Wan, P., Alzoubi, K., and Frieder, O. 2002. Distributed construction of connected dominating set in wireless ad hoc networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom)."},{"volume-title":"Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).","author":"Wan P.","key":"e_1_2_1_32_1","unstructured":"Wan , P. , Calinescu , G. , Li , X. , and Frieder , O . 2001. Minimum-energy broadcast routing in static ad hoc wireless networks . In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom). Wan, P., Calinescu, G., Li, X., and Frieder, O. 2001. Minimum-energy broadcast routing in static ad hoc wireless networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958496"},{"volume-title":"Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).","author":"Wieselther J. E.","key":"e_1_2_1_34_1","unstructured":"Wieselther , J. E. , Nguyen , G. D. , and Ephremides , A . 2000. On the construction of energy-efficient broadcast and multicast trees in wireless networks . In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom). Wieselther, J. E., Nguyen, G. D., and Ephremides, A. 2000. On the construction of energy-efficient broadcast and multicast trees in wireless networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom)."},{"volume-title":"Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).","author":"Wu J.","key":"e_1_2_1_35_1","unstructured":"Wu , J. and Dai , F . 2003. Broadcasting in ad hoc networks based on self-pruning . In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom). Wu, J. and Dai, F. 2003. Broadcasting in ad hoc networks based on self-pruning. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom)."},{"key":"e_1_2_1_36_1","article-title":"A dominating-set-based routing scheme in ad hoc wireless networks","author":"Wu J.","year":"2001","unstructured":"Wu , J. and Li , H. 2001 . A dominating-set-based routing scheme in ad hoc wireless networks . Telecommun. Syst. J. 3. Wu, J. and Li, H. 2001. A dominating-set-based routing scheme in ad hoc wireless networks. Telecommun. Syst. J. 3.","journal-title":"Telecommun. Syst. J. 3."},{"volume-title":"Proceedings of the International Workshop on Mobile and Wireless Networking (MWN).","author":"Wu J.","key":"e_1_2_1_37_1","unstructured":"Wu , J. and Yang , S . 2004. Coverage and connectivity in sensor networks with adjustable ranges . In Proceedings of the International Workshop on Mobile and Wireless Networking (MWN). Wu, J. and Yang, S. 2004. Coverage and connectivity in sensor networks with adjustable ranges. In Proceedings of the International Workshop on Mobile and Wireless Networking (MWN)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958498"},{"volume-title":"Proceedings of the International Conference on Distributed Computing Systems.","author":"Ye F.","key":"e_1_2_1_39_1","unstructured":"Ye , F. , Zhong , G. , Lu , S. , and Zhang , L . 2003. PEAS: A robust energy conserving protocol for long-lived sensor networks . In Proceedings of the International Conference on Distributed Computing Systems. Ye, F., Zhong, G., Lu, S., and Zhang, L. 2003. PEAS: A robust energy conserving protocol for long-lived sensor networks. In Proceedings of the International Conference on Distributed Computing Systems."},{"volume-title":"Proceedings of IFIP Networking Conference.","author":"Younis O.","key":"e_1_2_1_40_1","unstructured":"Younis , O. , Ramasubramanian , S. , and Krunz , M . 2007. Location-unaware sensing range assignment in sensor networks . In Proceedings of IFIP Networking Conference. Younis, O., Ramasubramanian, S., and Krunz, M. 2007. Location-unaware sensing range assignment in sensor networks. In Proceedings of IFIP Networking Conference."},{"volume-title":"Proceedings of the International Conference on Computer Communications and Networks (IC3N).","author":"Zhou Z.","key":"e_1_2_1_41_1","unstructured":"Zhou , Z. , Das , S. , and Gupta , H . 2004. Connected k-coverage problem in sensor networks . In Proceedings of the International Conference on Computer Communications and Networks (IC3N). Zhou, Z., Das, S., and Gupta, H. 2004. Connected k-coverage problem in sensor networks. In Proceedings of the International Conference on Computer Communications and Networks (IC3N)."}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1464420.1464428","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1464420.1464428","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:53:42Z","timestamp":1750287222000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1464420.1464428"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,2]]}},"alternative-id":["10.1145\/1464420.1464428"],"URL":"https:\/\/doi.org\/10.1145\/1464420.1464428","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2009,2]]},"assertion":[{"value":"2005-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-02-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}