透過您的圖書館登入
IP:54.144.81.21
  • 學位論文

無線感測網路的中繼節點配置

Relay Node Placement in Wireless Sensor Network

指導教授 : 石維寬
若您是本文的作者,可授權文章由華藝線上圖書館中協助推廣。

摘要


感測網路(Wireless sensor network, WSN),是由很多低成本,低電能的感測結點(Sensor node,以下簡稱SN) 相互連結在一起所組成之網路,最早使用的是美國軍方,用以散布在戰場來蒐集感測資料。SN可以感測資料以及將他感測到的資料傳送出去。然而,SN主要工作是感測資料,長距離的傳輸在電能的使用上對於SN來說並不是一個有效率的方式。 一種增加整個WSN壽命的方式就是在WSN中使用一種適用於傳輸資料的節點,我們稱之為Relay node(以下簡稱為RN),和SN相較之下,RN比較貴但是也比較powerful,其主要工作就是蒐集SN的資訊後,透過multi-hop的方式把資訊送給資料收集中心,也就是基地台(Base station, BS)。 本論文目標為最小化RN數量以達到節省成本的結果:給予一些隨機散布的SN集合,我們假設所有的SN和RN的傳輸距離分別為r和R,且R≧r> 0,其中SN只可以把自己的資料送出去給RN,但不可以轉送其他SN或RN的資料;而RN可以送資料給其他RN之外,也可以轉送其他RN的資料。因為RN的成本比較高,所以我們的目標是想要佈置最少的RN使得整個WSN可以連結起來。 這個問題可以拆成Disk cover和STP-MSP兩個演算法來執行,本文貢獻在兩個演算法上分別為,(1)Disk cover是一個NP-complete的問題,其目前雖然有Polynomial-time approximation scheme (PTAS),但時間複雜度高,實作上仍耗費很長的時間,所以本文除透過一些技巧對disk cover做實作上的加速之外,另外也將這個問題轉換成set cover problem,得以減少時間,SN個數為40時,set cover比disk cover的PTAS演算法快4700倍。(2) STP-MSP是一個NP-hard的問題,目前STP-MSP最佳的approximation algorithm的approximation factor為3,時間複雜度為O(n3),我們提出的兩個STP-MSP演算法的framework,並搭配三種準則,共六種演算法,給予不同的SN個數以及R, r,平均來說可以減少原始做法的RN個數至96%。在特定的參數下可以減少至90%,甚至在一些特例中可以到50%。

並列摘要


The wireless sensor network (WSN), is by many low costs and low power sensor node (SN). The first use of WSN is American Military for data collection. SN can perform sensing and transmitting sensed data to others. However, the prime task of SN is sensing, not transmitting. It is not suitable for SNs to transmit their data with long distance. A relay node (RN) is a node which is costly, but more powerful than SN. The main function of RN is to communicate with other nodes. RN sends the sensed data to the base-station via multi-hop. How to place the minimize size of RN in wireless sensor network is our major goal. We assume the communication range between SNs is r and between RNs is R, and 0

參考文獻


[ 2 ] 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.
Workshop on High Performance Switching and Routing; pp. 246-250.
[5] D.S. Hochbaum and W. Maass; Approximation schemes for covering

延伸閱讀