{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T22:45:44Z","timestamp":1649025944302},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2012,3]]},"abstract":"<jats:p> An underwater acoustic wireless sensor network (UA-WSN) consists of many resource-constrained underwater sensor nodes (USNs), which are deployed to perform collaborative monitoring tasks over a given region. One way to preserve network connectivity while guaranteeing other network QoS is to deploy some relay nodes (RNs) in the networks. Although RNs' function is more powerful than USNs, but they can lead to more interference and their cost is more expensive. This paper addresses constrained low-interference relay node deployment problem for 3-D UA-WSNs in which the RNs are placed at a subset of candidate locations to ensure connectivity between the USNs such that the number of RNs deployed and the value of total incremental interference are minimized. We first prove that it is NP-hard, then propose a general approximation algorithm framework. Based on the framework, we get two polynomial time O(1)-approximation algorithms. <\/jats:p>","DOI":"10.1142\/s1793830912500103","type":"journal-article","created":{"date-parts":[[2012,4,10]],"date-time":"2012-04-10T01:24:02Z","timestamp":1334021042000},"page":"1250010","source":"Crossref","is-referenced-by-count":1,"title":["CONSTRAINED RELAY NODE DEPLOYMENT FOR UNDERWATER ACOUSTIC WIRELESS SENSOR NETWORKS"],"prefix":"10.1142","volume":"04","author":[{"given":"DEYING","family":"LI","sequence":"first","affiliation":[{"name":"Key Laboratory of Data Engineering and Knowledge Engineering, MOE, School of Information, Renmin University of China, Beijing, P. R. China"}]},{"given":"ZHENG","family":"LI","sequence":"additional","affiliation":[{"name":"Key Laboratory of Data Engineering and Knowledge Engineering, MOE, School of Information, Renmin University of China, Beijing, P. R. China"}]},{"given":"WENKAI","family":"MA","sequence":"additional","affiliation":[{"name":"Key Laboratory of Data Engineering and Knowledge Engineering, MOE, School of Information, Renmin University of China, Beijing, P. R. China"}]},{"given":"WENPING","family":"CHEN","sequence":"additional","affiliation":[{"name":"Key Laboratory of Data Engineering and Knowledge Engineering, MOE, School of Information, Renmin University of China, Beijing, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2012,4,13]]},"reference":[{"key":"rf1","first-page":"1","volume":"2","author":"Akyildiz I. F.","journal-title":"SIGBED Rev."},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/j.adhoc.2005.01.004"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008384012064"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6568-7"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1142\/9789812791450"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288961"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00201-4"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2007.250629"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1145\/1347364.1347372"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830912500103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T17:53:44Z","timestamp":1565200424000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830912500103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3]]},"references-count":10,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,4,13]]},"published-print":{"date-parts":[[2012,3]]}},"alternative-id":["10.1142\/S1793830912500103"],"URL":"https:\/\/doi.org\/10.1142\/s1793830912500103","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3]]}}}