# 臺灣博碩士論文加值系統

(44.192.20.240) 您好！臺灣時間：2024/02/28 18:01

:::

### 詳目顯示

:

• 被引用:0
• 點閱:207
• 評分:
• 下載: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 11.1. Background 11.2. Contribution 41.3. Paper Organization 42. Preliminaries 52.1. Terminology 52.2. Problem Definition 82.3. Related Work 92.4. Motivation 103. Algorithms for STP-MSP and Their Analysis 123.1. Introduction 123.2. The Proof of Steinerized Minimum Spanning Tree 123.3. 3-approximate Algorithm 193.3.1. 3-star Algorithm 193.3.2. Proof of The Approximation Ratio of the 3-star Algorithm 223.3.3. The Worse Case of the 3-star Algorithm 253.4. Convex Path 274. Improved 3-star Algorithm 314.1. Introduction 314.2. Improved 3-star Algorithm 324.3. Relation of Delaunay Triangulation and 3-star 344.4. Proof of The Improved 3-star algorithm 354.5. Neighbor Nodes of Delaunay Triangles 395. Simulations 425.1. Minimum Spanning Tree 425.2. 3-star Algorithm for STP-MSP 435.3. Improved 3-star Algorithm 455.4. Analysis 466. Conclusion and Future Work 487. Reference 50
 [ 1 ] G. Lin and G. Xue, “Steiner tree problem with minimum number ofSteiner 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”, Journalof Global Optimization, Vol. 18(2000), pp. 17–33.[ 3 ] Cheng, D.Z. Du, L. Wang and B. Xu,” Relay sensor placement inwireless sensor networks”, ACM/Springer WINET, accepted. Available athttp://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
 電子全文
 國圖紙本論文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 以理論演算法角度探討無線感測網路的排程問題 2 無線感測網路的中繼節點配置 3 在無線感測網路中探討基於虛擬網格之路由演算法

 無相關期刊

 1 臺北市城市行銷策略之研究：影視目標市場之STP分析 2 以STP-N為基礎之液化潛能評估程序及其驗證 3 高雄港廢汙水排放區底棲生物之群聚結構及四種底棲動物蛋白質表現之研究 4 智能插座與智慧型電力管理系統實作 5 EcoIR: An Infrared Communication and Reprogramming System for Resource-Constrained Wireless Sensor Platforms 6 使用BitTorrent與可適性視訊編碼之影音串流系統 7 以創新擴散與STP行銷策略分析使用者接受創新產品之歷程-以Gogoro為例 8 社區養護中心之 S T P 行銷策略實證探討 - 以高雄市內門區養護中心之行銷推廣組合為例 9 延長無線感測網路生命期之移動式充電演算法研究 10 可移動式節點應用於無線感測器網路壽命延長之研究 11 HYBRIDRANK: A COLLABORATION BETWEEN SUPERVISED AND UNSUPERVISED APPROACHES FOR KEYPHRASE EXTRACTION 12 Adaptive Error Concealment Based On an Extensive Form Game with Perfect Information 13 Novel Pheromone Mechanism on the Size Estimation of Unstructured P2P Networks 14 具高效率及成本效益軟體測試方法之設計與分析 15 基於頻寬與容量之異質雲端儲存系統效能優化

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室