跳到主要內容

臺灣博碩士論文加值系統

(18.97.9.172) 您好!臺灣時間:2024/12/13 23:50
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:黃成弘
研究生(外文):Huang, Chen-hung
論文名稱:無線感測網路中繼節點配置演算法的建置與改善
論文名稱(外文):Analysis and Improvement of the 3-star Algorithm for STP-MSP problem in Wireless Sensor Network
指導教授:石維寬石維寬引用關係
指導教授(外文):Shih, Wei-Kuan
口試委員:呂政修衛信文李哲榮
口試日期:2011-7-12
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊系統與應用研究所
學門:電算機學門
學類:系統設計學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:中文
論文頁數:51
中文關鍵詞:中繼節點配置無線感測網路史坦納樹近似演算法
外文關鍵詞:Relay node placementWireless sensor networksSteiner treeApproximation algorithmSTP-MSP
相關次數:
  • 被引用被引用:0
  • 點閱點閱:221
  • 評分評分:
  • 下載下載:31
  • 收藏至我的研究室書目清單書目收藏:0
無線感測網路(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).

1. Introduction 1
1.1. Background 1
1.2. Contribution 4
1.3. Paper Organization 4
2. Preliminaries 5
2.1. Terminology 5
2.2. Problem Definition 8
2.3. Related Work 9
2.4. Motivation 10
3. Algorithms for STP-MSP and Their Analysis 12
3.1. Introduction 12
3.2. The Proof of Steinerized Minimum Spanning Tree 12
3.3. 3-approximate Algorithm 19
3.3.1. 3-star Algorithm 19
3.3.2. Proof of The Approximation Ratio of the 3-star Algorithm 22
3.3.3. The Worse Case of the 3-star Algorithm 25
3.4. Convex Path 27
4. Improved 3-star Algorithm 31
4.1. Introduction 31
4.2. Improved 3-star Algorithm 32
4.3. Relation of Delaunay Triangulation and 3-star 34
4.4. Proof of The Improved 3-star algorithm 35
4.5. Neighbor Nodes of Delaunay Triangles 39
5. Simulations 42
5.1. Minimum Spanning Tree 42
5.2. 3-star Algorithm for STP-MSP 43
5.3. Improved 3-star Algorithm 45
5.4. Analysis 46
6. Conclusion and Future Work 48
7. Reference 50

[ 1 ] G. Lin and G. Xue, “Steiner tree problem with minimum number of
Steiner points and bounded edge-length”, Information Processing Letters,
Vol. 69(1999), pp. 53-57.
[ 2 ] D. Chen, D.Z. Du, X.D. Hu, G. Lin, L. Wang and G. Xue,” Approxima-
tions for Steiner trees with minimum number of Steiner points”, Journal
of Global Optimization, Vol. 18(2000), pp. 17–33.
[ 3 ] Cheng, D.Z. Du, L. Wang and B. Xu,” Relay sensor placement in
wireless sensor networks”, ACM/Springer WINET, accepted. Available at
http://www.seas.gwu.edu/?cheng/Publication/relay.pdf.
[ 4 ] G. Gupta, M. Younis, “Load-balanced clustering of wireless sensor networks”, Proceedings of IEEE ICC’2003, pp. 1848–1852.
[ 5 ] J. H. Chang and L. Tassiulas,” Maximum lifetime routing in wireless sensor networks”, Proceedings of ARIRP’00, Mar. 2000.
[ 6 ] J. Chang and L. Tassiulas,” Routing for maximum system lifetime in wireless ad-hoc networks.” Proceedings of Mobicom’99, Sept. 1999.
[ 7 ] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan.,” Energy-efficient communication protocol for wireless micorsensor networks.”, Proceedings of the HICSS’00, Jan. 2000.
[ 8 ] K. Kalpakis, K. Dasgupta, and P. Namjoshi.,” Maximum lifetime data gathering and aggregation in wireless sensor networks.”, Proceedings NETWORKS’02, Aug, 2002.
[ 9 ] I. Kang and R. Poovendran.,” Maximizing static network lifetime of wireless broadcast adhoc networks.”, In IEEE 2003 International Conference on Communications 2003.
[10] E. Duarte-Melo and M. Liu,” Analysis of energy consumption and lifetime of heterogeneous wireless sensor networks”, Proceedings IEEE Globeco m’03, Nov. 2003.
[11] J. Pan, Y.T. Hou, L. Cai, Y. Shi, S.X. Shen, “Topology control for wireless sensor networks”, Proceedings of ACM MOBICOM’2003, pp.286–299.
[12]G. Gupta, M. Younis, “Fault-tolerant clustering of wireless sensor networks”, Proceedings of IEEE WCNC’2003, pp. 1579–1584.
[13] Theorem 1, http://research.engineering.wustl.edu/~pless/506/117.html

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top