無線感測網路(wireless sensor networks)主要是由一到數個基地台(base station)和眾多感測器所組成的網路系統。現今已廣泛運用在各種不同環境中進行通訊、監測等應用。而感測器有傳輸距離上的限制，所以當感測器與基地台距離太遠時，就必須要透過其他感測器才能將感測到的資料轉傳到基地台。每個感測器都具有體積小、低成本、簡易計算及儲存能力、通訊能力等性質，並配有固定能源。由於感測器節點一經佈署後就無法更換電池，一旦電力耗盡，感測器即失去作用。因此在使用上便有了限制。
    近年來，資料聚集在無線感測網路中變成一個很重要的研究議題。本論文提出一個以樹狀結構為主的資料聚集機制。在網路初始階段建立樹狀架構，並使用混合式參數來選擇傳輸路徑，且在每個週期內對網路中所有感測器節點所蒐集到的資料，透過資料聚集的動作去除重複冗餘的部分，以達到節省電量、延長網路生命周期的效果。

Wireless sensor networks (WSNs) are composed of one to several base stations and multiple sensor nodes, which are extensively used in many different kinds of environments currently, such as communication and monitoring. While the sensors have the limitation of transmission distance so that when the sensors are far away from the base station, they should relay the data to the base station through other sensors. Every sensor has the qualities that small, low-cost, the capacity of simple calculation, storage and communication, and it also equips the fixed energy.  
    In recent years, data aggregation of the wireless sensor networks has become a very important issue in research. In this paper, We propose a Tree-based Data Aggregation Mechanism (TDAM) in wireless sensor networks.  Building a tree structure in the initial phase of the network, and use the hybrid parameters to choose the transmission path, and remove the extra part of the data which are aggregated by all the sensor nodes in the network through the data aggregation in each round. Finally, it will achieve the effect that saving power and extending the lifetime of the network.

第一章 緒論	1
1-1 研究背景	3
1-2 研究動機	4
1-3 研究目的	5
1-4 論文架構	6
第二章 相關研究與背景介紹	7
2-1 機率式（Opportunistic-based）資料聚集方法	10
2-1-1 Direct Diffusion	10
2-2 群集式（Cluster-based）資料聚集方法	11
2-2-1 LEACH	11
2-2-2 LEACH -C	13
2-2-3 TEEN	15
2-3 樹狀式（Tree-based）資料聚集方法	16
2-3-1 PEDAP	16
2-3-2 BATR	18
2-3-3 A Scalable Solution to Minimum Cost Forwarding in Large Sensor Networks	20
2-3-4 E-Span	22
2-3-5 LPT	23
2-3-6 EE-Span	24
第三章 樹狀結構資料聚集機制	26
3-1 網路環境與假設	29
3-2 網路樹狀階層建構階段 （Layer Construction Phase）	31
3-3 資料聚集階段 （Data Aggregation Phase）	36
3-4 特性及優勢	49
第四章 模擬比較與分析	50
4-1 模擬環境設定	51
4-2 模擬結果與分析比較	53
第五章 結論與未來研究方向	56
5-1 結論	56
5-2 未來研究方向	57
參考文獻	58
附錄-英文論文	61

圖目錄
圖1：Direct Diffusion運作示意圖	10
圖2：LEACH之cluster架構表示圖	12
圖3：LEACH-C建構階段流程圖	14
圖4：使用minimum spanning tree演算法樹狀架構圖	17
圖5：BATR建構子節點數目為2的樹狀圖	20
圖6：E-Span演算法建構樹狀架構圖	22
圖7：LPT演算法建構樹狀架構圖	23
圖8：EE-Span演算法建構樹狀架構圖	24
圖9：資料聚集機制流程圖	27
圖10：Hopcount_value值於網路初始時設定完成	30
圖11：LCP建構圖	34
圖12：LCP流程圖	35
圖13：節點15發送SDA_Request封包給節點8和節點14	38
圖14：節點15由回傳之SDA_Reply封包資訊選擇下一節點	40
圖15：節點15選擇節點14作為資料傳送之下一節點	42
圖16：節點11對節點13、14執行資料聚集	43
圖17：聚集節點執行資料聚集圖	45
圖18：節點透過完成之聚集樹傳輸資料到Sink	46
圖19：DAP流程圖	48
圖20：節點平均跳躍次數之模擬結果	53
圖21：節點傳輸次數之模擬結果	54
圖22：節點存活數量之模擬結果	55

表目錄
表1：Network Layer Construction Packet	31
表2：Candidates Information Table格式	32
表3：SDA_Request封包格式	36
表4：SDA_Reply封包格式	38
表5：Data封包格式	41
表6：Data_Re之封包格式	41
表7：環境參數設定	52

[1]	I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "Wireless sensor networks: a survey, " Computer Networks, Vol. 38, No 4, pp. 393-422, 2002.

[2]	Z. Haibo and S. Hong, "Balancing Energy Consumption to Maximize Network Lifetime in Data-Gathering Sensor Networks, " IEEE Transactions on Parallel and Distributed Systems, Vol. 20, No 10, pp. 1526-1539, 2009.

[3]	T. Xueyan and X. Jianliang, "Optimizing Lifetime for Continuous Data Aggregation With Precision Guarantees in Wireless Sensor Networks, " IEEE/ACM Transactions on Networking, Vol. 16, No 4, pp. 904-917, 2008.

[4]	S. Sharafkandi, D. H. C. Du, and A. Razavi, "A Distributed and Energy Efficient Algorithm for Data Collection in Sensor Networks," Proceedings of 2010 39th International Conference on Parallel Processing Workshops (ICPPW), pp.571-580, 13-16 Sept. 2010.

[5]	H. O. Tan, I. Korpeoglu, and I. Stojmenovic, "Computing Localized Power-Efficient Data Aggregation Trees for Sensor Networks, " IEEE Transactions on Parallel and Distributed Systems, Vol. 22, No 3, pp. 489-500, 2011.

[6]	K. W. Kai-Wei Fan, S. Liu, and P. Sinha, "Structure-Free Data Aggregation in Sensor Networks, " IEEE Transactions on Mobile Computing, Vol. 6, No 8, pp. 929-942, 2007.

[7]	L. Ying shu , T. My T, and W. Wei li "Wireless Sensor Networks And Applications," 1st ed. New York: Springer, 2008, ch.13.

[8]	C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva, "Directed diffusion for wireless sensor networking, " IEEE/ACM Transactions on Networking, Vol. 11, No 1, pp. 2-16, 2003.

[9]	W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, "Energy-efficient communication protocol for wireless microsensor networks," Proceedings of Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, 2000, Vol. 2, pp. 1-10, 4-7 Jan. 2000.

[10]	W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, "An application-specific protocol architecture for wireless microsensor networks, " IEEE Transactions on Wireless Communications, Vol. 1, No 4, pp. 660-670, 2002.

[11]	A. Manjeshwar and D. P. Agrawal, "TEEN: a routing protocol for enhanced efficiency in wireless sensor networks," Proceedings of 15th International Parallel and Distributed Processing Symposium, pp.2009-2015, Apr 2001.

[12]	T. Hűseyin Őzgűr and K. Ibrahim, "Power efficient data gathering and aggregation in wireless sensor networks, " SIGMOD Rec., Vol. 32, No 4, pp. 66-71, 2003.

[13]	K. Hyun-sook and H. Ki-jun, "A power efficient routing protocol based on balanced tree in wireless sensor networks," Proceedings of First International Conference on Distributed Frameworks for Multimedia Applications, 2005. DFMA '05, pp.138-143, 6-9 Feb. 2005.

[14]	Y. Fan, A. Chen, L. Songwu, and Z. Lixia, "A scalable solution to minimum cost forwarding in large sensor networks," Proceedings of 10th International Conference onComputer Communications and Networks, 2001, pp.304-309, 2001.

[15]	M. Lee and V. W. S. Wong, "An energy-aware spanning tree algorithm for data aggregation in wireless sensor networks," Proceedings of 2005 IEEE Pacific Rim Conference on Communications, Computers and signal Processing, 2005. PACRIM. , pp.300-303, 24-26 Aug. 2005.

[16]	M. Lee and V. W. S. Wong, "LPT for data aggregation in wireless sensor networks," Proceedings of IEEE Global Telecommunications Conference, 2005. GLOBECOM '05, pp.2969 -2974, 2-2 Dec. 2005.

[17]	Z. Eskandari, M. H. Yaghmaee, and A. H. Mohajerzadeh, "Energy Efficient Spanning Tree for Data Aggregation in Wireless Sensor Networks," Proceedings of 17th International Conference on Computer Communications and Networks, 2008. ICCCN '08., pp.1-5, 3-7 Aug. 2008.

[18]	W.-H. Liao, Y. Kao, and C.-M. Fan, "Data aggregation in wireless sensor networks using ant colony algorithm, " Network and Computer Applications, Vol. 31, No 4, pp. 387-401, 2008.

[19]	Z. Eskandari, M. H. Yaghmaee, and A. M. Mohajerzadeh, "Automata based energy efficient spanning tree for data aggregation in Wireless Sensor Networks," Proceedings of 11th IEEE Singapore International Conference on Communication Systems, 2008. ICCS 2008, pp.943-947, 19-21 Nov. 2008.