{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T05:50:43Z","timestamp":1750830643207,"version":"3.41.0"},"reference-count":16,"publisher":"Wiley","license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["MOST103-2221-E-214-033"],"award-info":[{"award-number":["MOST103-2221-E-214-033"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Sensors"],"published-print":{"date-parts":[[2015]]},"abstract":"The relay node placement problem in wireless sensor network (WSN) aims at deploying the minimum number of relay nodes over the network so that each sensor can communicate with at least one relay node. When the deployed relay nodes are homogeneous and their communication ranges are circular, one way to solve the WSN relay node placement problem is to solve the minimum geometric disk cover (MGDC) problem first and place the relay nodes at the centers of the covering disks and then, if necessary, deploy additional relay nodes to meet the connection requirement of relay nodes. It is known that the MGDC problem is NP-complete. A novel linear time approximation algorithm for the MGDC problem is proposed, which identifies covering disks using the regular hexagon tessellation of the plane with bounded area. The approximation ratio of the proposed algorithm is (5<\/mml:mn>+<\/mml:mo>\u03f5<\/mml:mi><\/mml:math>), where0<\/mml:mn><<\/mml:mo>\u03f5<\/mml:mi>\u2264<\/mml:mo>15<\/mml:mn><\/mml:math>. Experimental results show that the worst case is rare, and on average the proposed algorithm uses less than 1.7 times the optimal disks of the MGDC problem. In cases where quick deployment is necessary, this study provides a fast 7-approximation algorithm which uses on average less than twice the optimal number of relay nodes in the simulation.<\/jats:p>","DOI":"10.1155\/2015\/565983","type":"journal-article","created":{"date-parts":[[2015,5,3]],"date-time":"2015-05-03T21:04:28Z","timestamp":1430687068000},"page":"1-12","source":"Crossref","is-referenced-by-count":5,"title":["Linear Time Approximation Algorithms for the Relay Node Placement Problem in Wireless Sensor Networks with Hexagon Tessellation"],"prefix":"10.1155","volume":"2015","author":[{"given":"Chi-Chang","family":"Chen","sequence":"first","affiliation":[{"name":"Department of Information Engineering, I-Shou University, Kaohsiung 84001, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7094-2683","authenticated-orcid":true,"given":"Chi-Yu","family":"Chang","sequence":"additional","affiliation":[{"name":"Department of Information Engineering, I-Shou University, Kaohsiung 84001, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Po-Ying","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Electronic Engineering, National Chin-Yi University of Technology, Taichung 41170, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","reference":[{"year":"2010","key":"1"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90018-9"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90111-3"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1007\/bf02570718"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90075-S"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2004.1268406"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72870-2_30"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19094-0_16"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1109\/tc.2007.250629"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2004.12.032"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-012-9451-5"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1109\/tc.2013.171"},{"issue":"4","key":"15","doi-asserted-by":"crossref","first-page":"794","DOI":"10.23919\/CJE.2014.10852004","volume":"23","year":"2014","journal-title":"Chinese Journal of Electronics"},{"issue":"1","key":"17","first-page":"53","volume":"5","year":"2014","journal-title":"Journal of Advances in Computer Research"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35452-6_18"}],"container-title":["Journal of Sensors"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/js\/2015\/565983.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/js\/2015\/565983.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/js\/2015\/565983.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T19:50:10Z","timestamp":1748375410000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.hindawi.com\/journals\/js\/2015\/565983\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"references-count":16,"alternative-id":["565983","565983"],"URL":"https:\/\/doi.org\/10.1155\/2015\/565983","relation":{},"ISSN":["1687-725X","1687-7268"],"issn-type":[{"type":"print","value":"1687-725X"},{"type":"electronic","value":"1687-7268"}],"subject":[],"published":{"date-parts":[[2015]]}}}