感測網路(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<r<=R. Notice that SN can just send the sensed data to the RN. Then, RN transmits those data by multi-hop. Our goal make the sensor network connected with the minimal size of RN.
This problem can be divided into two sub problems. The first sub problem can be solved by geometric disk cover algorithm, and the second sub problem can be solved by STP-MSP algorithm. It has been shown that the Minimum Geometric Disk Cover problem is NP-complete. Thought there is a PTAS for the problem, it really cost time when implement it. Therefore we use some trick to make it faster. We also translate this problem to set cover problem for saving time.
The STP-MSP is NP-hard and there is a 3-approximation algorithm. This thesis presents two frameworks with three principles. Given different parameters, we can reduce size of RN to 96% in average. In some specific parameters can reduced to 90%. For some special case we can reduce 50%.

1. Introduction 1
1.1. Background 1
1.2. Paper Organization 5
2. Preliminaries 6
2.1. Terms 6
2.2. Problem Definition 7
2.3. Related Work 7
2.4. Motivation 11
3. Geometric Disk Cover 12
3.1. Disk Cover Algorithm 12
3.1.1 Initialize 12
3.1.2 Shifting 13
3.1.3 Local Disk Cover 14
3.2. Local Disk Cover Improvement 18
3.2.1 Method 1 18
3.2.2 Method 2 20
4. STP-MSP 23
4.1. Definitions 23
4.2. A 3-approximation algorithm for STP-MSP 25
4.3. Two Framework for STP-MSP 29
4.3.1 A Framework for STP-MSP without Updating the Delaunay Triangulation 31
4.3.2 A Framework for STP-MSP with Updating the Delaunay Triangulation 33
4.3.3 Principle 34
4.3.4 Search_Fermat_Relays 34
4.3.5 Search_Fermat_Edges 41
4.3.6 Find_Max_Paths 41
4.3.7 Approximation-Ratio 44
4.3.8 Time Complexity 44
5. Simulation 46
5.1. Disk Cover 46
5.2. Relay Node Placement 47
5.3. Relay Node Placement Case Study 52
6. Conclusion and Future Work 58
7. Reference 59

[ 1 ] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci; Wireless
sensor networks: a survey; COMNET; Vol. 38(2002), pp. 393–422
[ 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.
[ 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] B. Hao, J. Tang and G. Xue; Fault-tolerant relay node placement in wire-
less sensor networks: formulation and approximation; IEEE HPSR’04:
Workshop on High Performance Switching and Routing; pp. 246-250.
[5] D.S. Hochbaum and W. Maass; Approximation schemes for covering
and packing problems in image processing and VLSI; Journal of the
ACM; Vol. 32(1985), pp. 130–136.
[ 6] 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.
[7] E. Lloyd and G. Xue; Relay node placement in wireless sensor networks;
IEEE Transactions on Computers; Vol. 56(2007), pp. 134–138.
[ 8] Tang, B. Hao and A. Sen; Relay node placement in large scale wireless
sensor networks; Comput. Communications; Vol. 29(2006), pp. 490–501.
[ 9] Weiyi Zhang; Guoliang Xue; Misra, S.; Fault-Tolerant Relay Node Placement in Wireless Sensor Networks: Problems and Algorithms , INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE ,Publication Year: 2007 , Page(s): 1649 - 1657
[ 10] http://imus.csie.ncku.edu.tw/imus/sensor/index.html
[ 11] J. H. Chang and L. Tassiulas. Maximum lifetime routing in wireless sensor networks. in Proc. of ARIRP’00, Mar. 2000.
[12] J. Chang and L. Tassiulas. Routing for maximum system lifetime in wireless ad-hoc networks. In Proc. of Mobicom’99, Sept. 1999.
[13] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocol for wireless micorsensor networks. In Proceedings of the HICSS’00, Jan. 2000.
[14] K. Kalpakis, K. Dasgupta, and P. Namjoshi. Maximum lifetime data gathering and aggregation in wireless sensor networks. In Proc. NETWORKS’02), Aug, 2002.
[15] I. Kang and R. Poovendran. Maximizing static network lifetime of wireless broadcast adhoc networks. In IEEE 2003 International
[16] E. Duarte-Melo and M. Liu. Analysis of energy consumption and lifetime of heterogeneous wireless sensor networks. In in Proc.IEEE Globeco m’03, Nov. 2003.
[17] 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.
[18]G. Gupta, M. Younis, Fault-tolerant clustering of wireless sensor networks, Proceedings of IEEE WCNC’2003, pp. 1579–1584.
[19] G. Gupta, M. Younis, Load-balanced clustering of wireless sensor networks, Proceedings of IEEE ICC’2003, pp. 1848–1852.
[ 20]Ming Zeng , Bugong Xu ,A Three-tiered Topology Control Model for Large Scale Scale Wireless Sensor Network, Control and Automation, 2007. ICCA 2007. IEEE International Conference on, page(s): 3250 - 3253
[ 21] http://en.wikipedia.org/wiki/Steiner_tree_problem
[22]李家同,與DNA 有關的演算法問題,
[ 23] http://www.math.sinica.edu.tw/math_media/d244/24404.pdf
[ 24]Fermat point, http://en.wikipedia.org/wiki/Fermat_Point
[ 25] 方鈞正 , 利用各個擊破的策略來解決無線感測網路上的連接及覆蓋問題
[ 26]A. Srinivas, E. Modiano, Minimum energy disjoint path routing in
wireless ad-hoc network, Proceedings of ACM MOBICOM’2003, pp.
122–133.
[ 27] Improved Approximation Algorithms for Relay Placement,Alon Efrat1 , Sándor P. Fekete2 , Poornananda R. Gaddehosur1 , Joseph S. B. Mitchell3 , Valentin Polishchuk4 and Jukka Suomela4 ,Springer Berlin, Volume 5193/2008