近年來，在 Wireless Sensor Networks (WSNs)的架構之下可以探討的主題，有非常多種不同的方向，如傳送路徑的規畫、佈點的方式、繞境處理、空洞偵測等…，其中有關sensor node的電源消耗，一直是一個非常重要而且值得深入研究的議題。為了要延長網路的有效存活時間，如何好好善用電源來延長網路壽命將是個重點。而其中Two-Tiered Wireless Sensor Network(TT-WSN)的就是用來改善sensor node在網路存活時間的一種網路架構；在TT-WSN的結構底下，會有sensor node(SN)跟Relay node (RN)兩種感測器，其中SN用來感測資料，並起把資料傳送給one hop鄰居內的RN，而RN蒐集完這些資料後傳送回BS，而其間的傳送只能透過RN來傳遞。而RN的成本是較為高昂的，因此我們希望能將RN的佈建數量降到最低，而每個RN還可以保持互相通訊。而我們現存的技術不是計算過於複雜，不然就是效率不夠明顯，因此本篇論文提供一個有效的方法，在佈置Relay node方面可以大幅降低所需要用到的數量，來有效降低花費在佈建RN上面的成本。
本論文主要概念是針對共享路徑方式，去建構佈點的方向，並使用此方法去找尋佈置RN的位置，因此在佈建用來與遠端RN達成通訊的新RN時，可以因此大幅降低佈建的個數。

In Wireless Sensor Networks (WSNs), energy is a scarce resource which must be utilized efficiently in order to enhance the network lifetime. Two-Tiered Wireless Sensor Network (TT-WSN) architecture is proposed to improve the lifetime longevity of the network. In TTWSN the lower tier consists of sensor nodes (SN), which are mainly responsible for sensing the environment and forwarding the data to its one hop neighbor relay node (RN). While the upper tier is constituent of more power affluent relay nodes (RNs), which deliver the data to the base station through potentially multiple connected relay nodes in a multi-hop fashion. As relay nodes are more expensive, it is therefore desirable to deploy a minimum number of such nodes so that every sensor node has at least one relay node as its one-hop neighbor and all the relay nodes form a connected network. Unfortunately the problem of finding such a minimum set of relay nodes is NP-Hard. Thus an approximation based algorithm is required to solve the problem in polynomial time. Existing solutions are either very complex or less efficient. In this paper we present a centralized deployment algorithm to solve the problem. The performance of the algorithm is compared with the existing algorithms through simulations. The extensive simulation results show that our algorithm outperforms the existing algorithms in terms of number of relay nodes deployed.

Table of Contents 	V
List of Figures  VI
List of Tables  VII
第一章、緒論  1
第二章、問題表述  4
2.1 名詞定義  4
2.2 問題描述  6
第三章、相關研究  7
第四章、共享路徑建構  9
4.1 場景建構  10
4.2 基本構想  14
4.3 共享路徑  15
4.4 佈點機制  18
4.5 特別案例與多點以上共享路徑探討  21
4.6 Pseudo Code概念  25
第五章、公式推導證明  28
5.1 Steiner poin  28
5.2 佈點位置  32
第六章、模擬分析 34
第七章、結論  38
參考文獻  39
附錄—英文論文  42
List of Figures
圖一 : 六角網格網路之座標編排方式  10
圖二 : 全區六角型網路架構  11
圖三 : Relay node的半徑  12
圖四 : 六角形的Relay node佈建  13
圖五 : 建立全區連線 14
圖六 : 角度比對選取 16
圖七 : Steiner point 之計算 17
圖八 : 佈建通訊用RN之順序及方向 19
圖九 : 夾角角度≧120°  20
圖十 : 角度共線與 >120°  21 
圖十一 : 多點以上共享路徑  24
圖十二 : Steiner point 證明  29
圖十三 : 選取外推之正三角形端點  31
圖十四 : 在已知兩點位置間佈置RN  33
圖十五 : SPP與IRNP比較圖  34
圖十六 : SPP與IRNP比較圖  35
圖十七 : SPP與IRNP比較圖  36
圖十八 : SPP與IRNP比較圖  37
List of Tables
Table1 :DATA STRUCTURE AND NOTATION  9

[1]I.F. Akyildiz, W. Su, Y.Sankarasubramaniam and E.Cayirci; “Wireless sensor network: asurvey”; COMNET; Vol. 38(2002),pp. 393-422.
[2]Jennifer Yick , Biswanath Mukherjee , Dipak Ghosal; “Wireless sensor network survey; Computer Networks”; Vol.52(August, 2008) n.12; pp.2292-2330.
[3]J.Bredin, E. Demaine, M. Hajiaghayi and D. Rus; “Depolying sensor network with guaranteed capacity and fault tolerance”; MobiHoc’s05; pp. 309-319. 
[4]Xiuzhen Cheng, Ding-Zhu,Lusheng Wang,and Baogang Xu; “Relay Sensor Placement in Wireless Sensor Networks”; Wireless Networks, January 2007, DOI: 10.1007/s11276-006-0724-8. 
[5]B. Hao, J. Tang and G. Xue; “Fault-tolerant relay node placement in wireless sensor networks: formulation and approximation”; IEEE HPSR’04: Workshop on High Performance Switch and Routing; pp.246-250.
[6]J.Tang, B. Hao, and A. Sen; “Relay Node Placement in Large Scale Wireless Sensor Networks”; Computer Comm; vol. 29(2006), pp.490-501. 
[7]H. Liu, P.J. Wan and X.H. Jia; “Fault-tolerant relay node placement in wireless sensor network”; LNCS; Vol. 3595(2005), pp.230-239.
[8]Srinivas, A., Zussman, G., and Modiano; “Mobile backbone networks : construction and maintenance”; MobiHoc ’06; pp. 166-177.
[9]J. Pan, Y.T Hou, L. Cai, Y. Shi, S.X. Shen; “Topology control for wireless sensor networks”; MobiCom’03, pp. 286-299.
[10]E. Lloyd and G. Xue; “Relay node placement in wireless sensor networks”; IEEE Transaction on Computer;Vol. 56(2007), pp.134-138.
[11]W. Zhang, G. Xue and Misra S.; “Fault-Tolerant Relay Node Placement in Wireless Sensor Networks”; Problems and Algorithm; Infocom-2007, pp.1649-1657, 2007
[12]Shams, S.M.S; chowdhury, A.H.; Ki-Hyung Kim; Noh Bok Lee; “A fast approximation algorithm for relay node placement in double-tiered wireless sensor network”; MILCOM 2008, pp.1-6
[13]E.S Biagioni, G. Sasaki; “Wireless sensor placement for reliable and efficient data collection”; in: Proceedings of the 36th Annual Hawaii international Conference on System Science (HICSS’03) Track 5 Volume 5, Big Island, Hawaii, January 2003.
[14]D. Pompili, T. Melodia, I.F. Akyildiz; “Deployment analysis in under-water acoustic wireless sensor networks”; in: Proceedings of the ACM International Workshop on Under- Water Networks (WUWNet), Los Angeles, CA, September 2006.
[15]D.S. Hochbaum and W. Maass; “Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI”; J.ACM, vol.32(1985), pp. 130-136.
[16]M. Younis, K. Akkaya; “Strategies and techniques for node placement in wireless sensor networks: A survey”; Ad Hoc Network Volume 6 , Issue 4 (June 2008) pp. 621-655 , 2008.
[17]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,1999.

[18]D. Chen, D.Z. Du, X.D. Hu, G. Lin, L. Wang and G. Xue; “Approximations for Steiner trees with minimum number of Steiner points; Journal of Global Optimization”; Vol. 18(2000), pp. 17-33.
[19]Xiaofeng Han; Xiang Cao; Lloyd, E.L.; “Chien-Chung Sheng, Fault-Tolerant Relay Node Placement in Heterogence Wireless Sensor Networks”, Infocom-2007, pp 1667-1675
[20]Bilal Zafar; Zeeshan Mir; S.M. Saif Shams; “On Improved Relay Nodes Placement in Two-Tiered Wireless Sensor Networks”; MILCOM 2009.
[21]Available from : URL :
http://www.jfvs.tpc.edu.tw/jfvs/%B1%D0%BE%C7%B2%D5/%B1M%C3D%B3%F8%A7i/95%BC%C6%BE%C7%AC%EC/%BC%C6%BE%C7%AC%EC%B1M%C3D-%B6O%B0%A8%C2I.doc