無線感測網路中繼節點配置演算法的建置與改善

Analysis and Improvement of the 3-star Algorithm for STP-MSP problem in Wireless Sensor Network

黃成弘(Chen-hung Huang)

指導教授 ： 石維寬

國立清華大學/電機資訊學院/資訊系統與應用研究所/碩士(2011年)

https://doi.org/10.6843/NTHU.2011.00535

摘要

無線感測網路(Wireless Sensor Network, WSN)是由一到數個無線資料收集器及許多感測器(Sensor Node, 以下簡稱SN)所構成的網路系統。 節點與節點間的溝通是採用無線通訊的方式。 為了省電及距離的限制，必須藉由multi-hop機制建立網路路由的方法。如何最佳化整體WSN的使用壽命則是目前熱門研究之一。
其中一種增加整個WSN壽命的方式就是在WSN中使用一種適用於傳輸資料的節點，我們稱之為Relay node(以下簡稱為RN)。 RN較SN來說效能較好、傳輸距離遠，但成本高。 其主要功能為收集SN的資訊，將資料轉送給BS，並使整個WSN成為connected network。 因此，本論文主要討論的問題是，如何最小化RN數量以節省成本。
問題定義：在Euclidean plane上，給定一個正的常數R2和一組數量為N的節點，找出一個Steiner tree連接N個點，tree中的edge長度皆小於等於R，並使其擁有最少的Steiner point的個數，此問題已被證明為NP-hard problem[ 1 ]，且存在ratio為3的approximation algorithm[ 2 ][ 3 ]。
本論文將提供以下的建置與改善：(1) 提供二個方向分析此approximation algorithm，分別為convex path 和此approximation algorithm的worse case。(2) 此approximation algorithm的時間複雜度為O(n3)，我們利用Delaunay triangulation降低此演算法的時間複雜度，使其從O(n3)降至O(nlogn)，以加速運算。

關鍵字

中繼節點配置 ； 無線感測網路 ； 史坦納樹 ； 近似演算法

並列摘要

Wireless Sensor Network (WSN) is a network consisting of a number of sensor nodes (SN). Due to the restraint of power consumption and communication range, sensor nodes communicate with each other using the multi-hop method. When the distance between some SNs is larger than their communication range, the WSN cannot be connected. One approach to resolve this problem is to place relay nodes (RN) which have better transmission power, but more expensive, than general SNs. This thesis focuses on the minimization of the relay node placement problem.
This problem is called STP-MSP (the Steinerized Tree Problem with Minimum number of Steiner Points), which is defined as follows. Given a set of SNs, X={p1,p2,…,pn}, in the Euclidean plane R2, and a positive constant R, representing SNs’ communication range, STP-MSP asks for a Steiner tree T that connects all nodes in X such that each edge in T has length less than or equal to R, and the number of Steiner points is minimized. In [1], it is shown showed that the STP-MSP problem is NP-hard. In [2][3], authors presented an approximate algorithm with approximation ratio 3.
In this paper, we proved some analyses and improvements on the 3-approximation algorithm. First, we analyzed the worst cases of the algorithm, which could lead a tighter bound of the approximation ratio. Second, we used the Delaunay triangulation to improve the performance of the algorithm, by which the time complexity is reduced from O(n3) to O(n log n).

並列關鍵字

Relay node placement ； Wireless sensor networks ； Steiner tree ； Approximation algorithm ； STP-MSP

參考文獻

[ 1 ] G. Lin and G. Xue, “Steiner tree problem with minimum number of

Vol. 69(1999), pp. 53-57.

tions for Steiner trees with minimum number of Steiner points”, Journal

of Global Optimization, Vol. 18(2000), pp. 17–33.

[ 4 ] G. Gupta, M. Younis, “Load-balanced clustering of wireless sensor networks”, Proceedings of IEEE ICC’2003, pp. 1848–1852.