@inproceedings{d2398ebf0bbf4471902e40da2df4c630,
title = "Analysis and improvement of the 3-star algorithm for the STP-MSP problem in Wireless Sensor Networks",
abstract = "A Wireless Sensor Network (WSN) uses a larger number of low-power sensor nodes to gather environmental information which is then wirelessly forwarded to a base station. However, sensor nodes have very limited communication ranges. Thus, relay nodes are required to ensure reliable connectivity throughout the WSN. On the other hand, relay nodes are typically more sophisticated and expensive than sensor nodes. Therefore, deployment strategies should seek to minimize the number of required relay nodes, a problem referred to as the Steiner Tree Problem with Minimum Number of Steiner Points (SMT-MSP), which has been shown to be NP-hard. This paper analyzes and improves the 3-star approximation algorithm by reducing the time complexity from O(n3) to O(nlogn) with the identical performance ratio. Experiments are conducted to verify the correctness of the proposed algorithm.",
keywords = "Relay sensor, STP-MSP, Steiner tree, approximation algorithm, wireless sensor network",
author = "Chen, {Shuo Han} and Lee, {Chi Heng} and Chen, {Tseng Yi} and Wei, {Hsin Wen} and Hsu, {Tsan Sheng} and Shih, {Wei Kuan}",
note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 2017 International Conference on Computing, Networking and Communications, ICNC 2017 ; Conference date: 26-01-2017 Through 29-01-2017",
year = "2017",
month = mar,
day = "10",
doi = "10.1109/ICCNC.2017.7876269",
language = "English",
series = "2017 International Conference on Computing, Networking and Communications, ICNC 2017",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "991--995",
booktitle = "2017 International Conference on Computing, Networking and Communications, ICNC 2017",
address = "美國",
}