{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T02:30:51Z","timestamp":1660271451178},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:p> In this paper we discuss minimum energy broadcast routing with directional antennas in ad hoc and sensor networks. We assume that the network consists of sensor nodes whose antennas are switched beam directional antennas. The problem of our concern is: a given set V with n nodes and each node v<jats:sub>i<\/jats:sub> has l(i) transmission directions (i.e. the antenna sectors) and a broadcast request sourced at s, how to find a broadcast tree rooted at s and spanning all nodes in V such that the total energy is minimized. This problem involves with the choice of transmitting nodes and their transmission directions, which is NP-hard. We firstly propose a directed Steiner tree-based approximation algorithm for this problem and discuss its distributed implementation. Then we also propose a |V|-approximation algorithm and one heuristic with lower time complexities. Extensive simulations have demonstrated the efficiency of our algorithms. <\/jats:p>","DOI":"10.1142\/s1793830909000166","type":"journal-article","created":{"date-parts":[[2009,7,2]],"date-time":"2009-07-02T07:53:30Z","timestamp":1246521210000},"page":"205-218","source":"Crossref","is-referenced-by-count":2,"title":["MINIMUM ENERGY BROADCAST ROUTING IN AD HOC AND SENSOR NETWORKS WITH DIRECTIONAL ANTENNAS"],"prefix":"10.1142","volume":"01","author":[{"given":"ZHENG","family":"LI","sequence":"first","affiliation":[{"name":"Key Laboratory of Data Engineering and Knowledge Engineering, Renmin University of China, MOE, China"},{"name":"School of Information, Renmin University of China, Beijing, China"}]},{"given":"DEYING","family":"LI","sequence":"additional","affiliation":[{"name":"Key Laboratory of Data Engineering and Knowledge Engineering, Renmin University of China, MOE, China"},{"name":"School of Information, Renmin University of China, Beijing, China"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8705(03)00013-1"},{"key":"rf3","volume-title":"Smart Antennas","author":"Sarkar T. K.","year":"1996"},{"key":"rf6","first-page":"1","volume":"17","author":"Dai F.","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"rf7","author":"Kang I.","journal-title":"Proc. Wirel. Opt. Commun."},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1109\/TSC.2011.1"},{"key":"rf13","first-page":"144","volume":"3","author":"Li D.","journal-title":"IEEE Trans. Mob. Comput."},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1042"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1145\/358690.358717"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830909000166","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:57:55Z","timestamp":1565179075000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830909000166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":8,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2009,6]]}},"alternative-id":["10.1142\/S1793830909000166"],"URL":"https:\/\/doi.org\/10.1142\/s1793830909000166","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6]]}}}