@inproceedings{ec65713983e24485b76608df6c7d4c96,
title = "Improving the 3-star approximation algorithm for relay node placement in wireless sensor network",
abstract = "A Wireless Sensor Network (WSN) is composed by a larger number of low-power sensor nodes to gather environmental information and forward those gathered information wirelessly to a base station. However, due to the limited communication range of sensor nodes, relay nodes need to be included in order to make the whole WSN connected. Relay nodes are typically more advanced and more expensive than sensor nodes. Therefore, developing strategies to deploy relay nodes effectively and minimize the number of relay nodes has always been a hot research topic, also known as the Steiner Tree Problem with Minimum number of Steiner Points (SMT-MSP), which is proved to be NP-hard by previous work. In this paper, we analyze and improve the 3-star approximation algorithm by reducing the time complexity from O(n3) to O(n log n) with identical performance ratio. Experiments are conducted to verify the correctness of the proposed algorithm.",
keywords = "Approximation algorithm, Relay sensor, Steiner tree, STP-MSP, Wireless sensor network",
author = "Chen, {Shuo Han} and Chen, {Tseng Yi} and Wei, {Hsin Wen} and Hsu, {Tsan Sheng} and Huang, {Chen Hung} and Shih, {Wei Kuan}",
note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 37th IEEE Sarnoff Symposium, Sarnoff 2016 ; Conference date: 19-09-2016 Through 21-09-2016",
year = "2017",
month = feb,
day = "7",
doi = "10.1109/SARNOF.2016.7846724",
language = "???core.languages.en_GB???",
series = "37th IEEE Sarnoff Symposium, Sarnoff 2016",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "37th IEEE Sarnoff Symposium, Sarnoff 2016",
}