Improving the 3-star approximation algorithm for relay node placement in wireless sensor network

Shuo Han Chen, Tseng Yi Chen, Hsin Wen Wei, Tsan Sheng Hsu, Chen Hung Huang, Wei Kuan Shih

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publication37th IEEE Sarnoff Symposium, Sarnoff 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509015405
DOIs
StatePublished - 7 Feb 2017
Event37th IEEE Sarnoff Symposium, Sarnoff 2016 - Newark, United States
Duration: 19 Sep 201621 Sep 2016

Publication series

Name37th IEEE Sarnoff Symposium, Sarnoff 2016

Conference

Conference37th IEEE Sarnoff Symposium, Sarnoff 2016
Country/TerritoryUnited States
CityNewark
Period19/09/1621/09/16

Keywords

  • Approximation algorithm
  • Relay sensor
  • STP-MSP
  • Steiner tree
  • Wireless sensor network

Fingerprint

Dive into the research topics of 'Improving the 3-star approximation algorithm for relay node placement in wireless sensor network'. Together they form a unique fingerprint.

Cite this