學術產出-Periodical Articles

Article View/Open

Publication Export

Google ScholarTM

政大圖書館

Citation Infomation

題名 On the Construction of Data Aggregation Tree with Minimum Energy Cost in Wireless Sensor Networks: NP-Completeness and Approximation Algorithm
作者 郭桐惟
Kuo, Tung-Wei;Lin, Kate Ching-Ju;Tsai, Ming-Jer
貢獻者 資科系
關鍵詞 Approximation algorithms, Approximation methods, Relays, Routing, Wireless sensor networks, Sensors, Steiner trees
日期 2015-12
上傳時間 29-Jun-2017 09:43:24 (UTC+8)
摘要 In many applications, it is a basic operation for the sink to periodically collect reports from all sensors. Since the data gathering process usually proceeds for many rounds, it is important to collect these data efficiently, that is, to reduce the energy cost of data transmission. Under such applications, a tree is usually adopted as the routing structure to save the computation costs for maintaining the routing tables of sensors. In this paper, we work on the problem of constructing a data aggregation tree that minimizes the total energy cost of data transmission in a wireless sensor network. In addition, we also address such a problem in the wireless sensor network where relay nodes exist. We show these two problems are NP-complete, and propose O(1)-approximation algorithms for each of them. Simulations show that the proposed algorithms each have good performance in terms of the energy cost.
關聯 IEEE Transactions on Computers,
資料類型 article
DOI http://dx.doi.org/10.1109/INFCOM.2012.6195659
dc.contributor 資科系
dc.creator (作者) 郭桐惟zh_TW
dc.creator (作者) Kuo, Tung-Wei;Lin, Kate Ching-Ju;Tsai, Ming-Jer
dc.date (日期) 2015-12
dc.date.accessioned 29-Jun-2017 09:43:24 (UTC+8)-
dc.date.available 29-Jun-2017 09:43:24 (UTC+8)-
dc.date.issued (上傳時間) 29-Jun-2017 09:43:24 (UTC+8)-
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/110580-
dc.description.abstract (摘要) In many applications, it is a basic operation for the sink to periodically collect reports from all sensors. Since the data gathering process usually proceeds for many rounds, it is important to collect these data efficiently, that is, to reduce the energy cost of data transmission. Under such applications, a tree is usually adopted as the routing structure to save the computation costs for maintaining the routing tables of sensors. In this paper, we work on the problem of constructing a data aggregation tree that minimizes the total energy cost of data transmission in a wireless sensor network. In addition, we also address such a problem in the wireless sensor network where relay nodes exist. We show these two problems are NP-complete, and propose O(1)-approximation algorithms for each of them. Simulations show that the proposed algorithms each have good performance in terms of the energy cost.
dc.format.extent 188414 bytes-
dc.format.mimetype application/pdf-
dc.relation (關聯) IEEE Transactions on Computers,
dc.subject (關鍵詞) Approximation algorithms, Approximation methods, Relays, Routing, Wireless sensor networks, Sensors, Steiner trees
dc.title (題名) On the Construction of Data Aggregation Tree with Minimum Energy Cost in Wireless Sensor Networks: NP-Completeness and Approximation Algorithm
dc.type (資料類型) article
dc.identifier.doi (DOI) 10.1109/INFCOM.2012.6195659
dc.doi.uri (DOI) http://dx.doi.org/10.1109/INFCOM.2012.6195659