無線感測器網路係由多個感測器節點所組成，這些感測器節點具有感測能力、計算能力和無線通訊能力。這些簡單且不具移動能力的感測器節點會被隨意的佈置在廣闊的地理區域中，用來監測某些活動，例如：危險戰場上、農業應用上及海洋的監測等。
在感測器網路中最主要的設計重點就是有效率的使用有限的電量，在設計路由協定方面最主要是要能夠延長整個感測器節點的生存時間。當感測器節點被隨意的佈署之後，有一些節點傳送資料的方法已經被提出來了，包括有節點直接傳送資料的方式、平坦式或叢集式的路由協定等。在本論文中，提出一個應用於無線感測器網路中以樹狀結構為基礎之多重路徑路由協定，本論文提出的路由協定中，一開始整個網路會被建構成樹狀式的架構，在此架構下感測器節點會透過不同的候選父節點產生出多條資料回傳的路徑，用來分散整個節點消耗的電力，以延長整個網路的生存時間。本論文也提出模擬測試，以驗證我們所提的方法會比其他結構的路由協定還要來的好，並且可以改善網路的生存時間。

Wireless sensor networks consist of small nodes with sensing, computation and wireless communication capabilities. In many emerging application scenarios (e.g., battlefield surveillance, large-area and perimeter monitoring in agriculture, and autonomous ocean scientific sampling), a large number of such simple immobile nodes are deployed in a vast geographical area to monitor activities or environmental conditions.
The energy efficiency is a substantial key design issue in such networks. An efficient routing protocol is critical to prolong the life of sensor nodes. Several methods for transmitting data in randomly deployed sensor nodes have been proposed, including direct communication, flat and clustering protocols. In this paper, we propose a Tree-Based Multipath Routing Protocol (TMRP) for wireless sensor networks. According to the proposed TMRP, the wireless sensor network is initially constructed as a layered network. Based on the layered network, sensor nodes have multipath routes to the sink node through candidate parent nodes. In this paper, the verification simulation is also executed to prove the proposed TMRP can increase the lifetime of sensor networks better than other protocol

第一章 緒論	- 1 -
1-1 研究背景	- 2 -
1-2 研究動機	- 3 -
1-3 研究目的	- 5 -
1-4 論文架構	- 7 -
第二章 相關背景研究	- 8 -
2-1 叢集式（Cluster-based）網路協定	- 12 -
2-1-1 LEACH	- 12 -
2-1-2 LEACH-C	- 13 -
2-1-3 TEEN	- 15 -
2-1-4 APTEEN	- 16 -
2-2 鏈結式（Chain-based）網路協定	- 17 -
2-2-1 PEGASIS	- 17 -
2-2-2 Chain-Based Protocols for Data Broadcasting and
Gathering in the Sensor Networks	- 19 -
2-2-3 PAC	- 21 -
2-3 樹狀式（Tree-based）網路協定	- 22 -
2-3-1 PEDAP	- 22 -
2-3-2 HAR	- 24 -
2-3-3 BATR	- 26 -
2-3-4 A Scalable Solution to Minimum Cost Forwarding in Large Sensor Networks	- 27 -
第三章 以樹狀結構為基礎之多重路徑路由協定	- 29 -
3-1 網路環境和假設	- 30 -
3-2 網路階層建構階段Layer Construction Phase	- 32 -
3-3 資料傳送階段Data Dissemination Phase	- 36 -
3-4 網路結構的維護	- 43 -
3-5 資料融合與聚集	- 48 -
3-6  TMRP的優勢	- 49 -
第四章 路由模擬比較與分析	- 51 -
4-1 模擬環境	- 51 -
4-2 模擬結果與分析比較	- 53 -
4-3 TMRP之可容性分析	- 55 -
第五章 結論與未來研究方向	- 58 -
5-1 結論	- 58 -
5-2 未來研究方向	- 59 -
參考文獻	- 60 -
附錄一：論文英文稿	- 63 –
圖目錄
圖1  無線感測器網路路由協定分類圖	- 11 -
圖2  Cluster表示圖	- 12 -
圖3  LEACH-C建構階段流程圖	- 14 -
圖4  Greedy演算法建構chain	- 18 -
圖5  PEGASIS資料傳送圖	- 19 -
圖6  Collecting和Relaying示意圖	- 20 -
圖7  使用Minimum Total Energy演算法建構chain圖   - 21 -
圖8  PAC chain建構圖	- 22 -
圖9  使用minimum spanning tree演算法樹狀架構圖   - 23 -
圖10  HAR樹狀建立圖	- 25 -
圖11  BATR建構子節點數目為2的樹狀圖	- 27 -
圖12  感測器節點佈置環境圖	- 31 -
圖13  LCP建構階段圖	- 33 -
圖14  節點接收LCREQ封包動作流程圖	- 36 -
圖15  TMRP資料回傳圖	- 37 -
圖16  節點 ○56 傳送資料圖，如果有接收到RDACK封包圖- 40 -
圖17  節點 ○56 傳送資料圖，如果沒接收到RDACK封包圖- 40 -
圖18  當RDACK封包Energy欄位為False示意圖	- 42 -
圖19  DDP流程圖	- 43 -
圖20  節點○62收到同階層值節點所回傳的LCREQ封包圖- 45 -
圖21  節點○62只收到子節點所回傳的LCREQ封包圖	- 45 -
圖22  新加入節點找尋候選父節點圖	- 46 -
圖23  節點接收CPREQ封包流程圖	- 47 -
圖24  資料融合和聚集圖	- 49 -
圖25  節點平均電量消耗比較圖	- 53 -
圖26  節點生存時間比較圖	- 55 -
圖27  TMRP之可容性分析比較圖	- 56 -
 
表目錄
表1  Network Construction Packet格式	- 32 -
表2  Candidates Information Table格式	- 33 -
表3  資料封包格式	- 38 -
表4  RDACK封包格式	- 38 -

參考文獻

[1]	I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, “Wireless sensor networks: a survey,” Computer Networks of Elsevier Journal, March 2002, pp. 393-422.
[2]	Heinzelman, W.R., Chandrakasan, A., Balakrishnan. H, “Energy-efficient communication protocol for wireless microsensor networks,” Proceedings of the 33rd Annual Hawaii International Conference, Vol. 2, Jan. 2000, pp. 3005-3014.
[3]	Lindsey, S., Raghavendra. C.S., “PEGASIS: Power-Efficient Gathering in Sensor Information System,” Proceedings of Aerospace Conference, Vol. 3, March 2002, pp. 3-1125-3-1130.
[4]	Manjeshwa. A., Agrawal. D.P., “TEEN: a routing protocol for enhanced efficiency in wireless sensor networks,” Proceedings of 15th International Parallel and Distributed Processing Symposium, April 2001, pp. 2009-2015.
[5]	Shih-Chang Huang, Rong-Hong Jan, “Energy-Aware, Load Balanced Routing Schemes for Sensor Networks,” Proceedings of 10th International Conference on Parallel and Distributed Systems (ICPADS), July 2004, pp. 419-425.
[6]	Fan Ye, Chen, A., Songwu Lu, Lixia Zhang, “A Scalable Solution to Minimum Cost Forwarding in Large Sensor Networks,” Proceedings of Tenth International Conference on Computer Communications and Networks, Oct. 2001, pp. 304-309.
[7]	Qiangfeng Jiang, Manivannan, D., “Routing protocols for sensor networks,” Proceedings of the Consumer Communications and Networking Conference (CCNC), Jan. 2004, pp. 93-98.
[8]	Al-Karaki, J.N., Kamal, A.E., “Routing techniques in wireless sensor networks: a survey,” IEEE Wireless Communications, Vol. 11, Issue 6, Dec. 2004, pp. 6-28.
[9]	Thepvilojanapong. N., Tobe. Y., Sezaki. K., “HAR: Hierarchy-Based Anycast Routing Protocol for Wireless Sensor Networks,” Proceedings of the Symposium on Applications and the Internet, 2005, pp. 204-212.
[10]	Heinzelman. W.B., Chandrakasan. A.P., Balakrishnan. H., “An Application-Specific Protocol Architecture for Wireless Microsensor Networks,” IEEE Transactions on Wireless Communications, Volume 1, Issue 4, Oct. 2002, pp. 660-670.
[11]	Muruganathan. S.D., Ma. D.C.F., Bhasin. R.I., Fapojuwo. A.O., “A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks,” IEEE Communications Magazine, Volume 43, Issue 3, March 2005, pp. 8-13.
[12]	Hüseyin Özgür Tan, Ibrahim Körpeoǧlu, “Power Efficient Data Gathering and Aggregation in Wireless Sensor Networks,” ACM SIGMOD Record, Vol 32, Issue 4, Dec. 2003, pp. 66-71.
[13]	Hyun-sook Kim, Ki-jun Han, “A Power Efficient Routing Protocol Based on Balanced Tree in Wireless Sensor Networks,” First International Conference on Distributed Frameworks for Multimedia Applications, Feb. 2005, pp. 138-143.
[14]	inh-Long Pham, Daeyoung Kim, Yoonmee Doh, Seong-eun Yoo, “Power aware chain routing protocol for data gathering in sensor networks,” Proceedings of Intelligent Sensors, Sensor Networks and Information Processing Conference, Dec. 2004, pp. 107-112.
[15]	Kemei Du, Jie Wu, Dan Zhou, “Chain-Based Protocols for Data Broadcasting and Gathering in the Sensor Networks,” Proceedings of International Conference on Parallel and Distributed Processing Symposium, April 2003, Page(s): 8pp.
[16]	Joanna Kulik, Wendi Heinzelman, Hari Balakrishnan, “Negotiation-based protocols for disseminating information in wireless sensor networks (SPIN),” Proceeding of the 5th Annual ACM/IEEE International Conf. On Mobile Computing and Networking, 1999.
[17]	David Braginsky, Deborah Estrin, “Transport and Routing Protocols: Rumor routing algorthim for sensor networks,” International Conference on Mobile Computing and Networking, 2002, pp. 22-31.
[18]	Fan Ye, Haiyun Luo, Jerry Cheng, Songwu Lu, Lixia Zhang, “A two-tier data dissemination model for large-scale wireless sensor networks,” Proceedings of the 8th ACM Annual International Conference on Mobile Computing and Networking, 2002, pp. 148-159.
[19]	Intanagonwiwat. C., Govindan. R., Estrin. D., Heidemann, J., Silva. F., “Directed diffusion for wireless sensor networking,” IEEE/ACM Transactions on Networking, Vol. 11, Issue 1, Feb. 2003, pp. 2-16.
[20]	S. Servetto, G. Barrenechea, “Constrained Random Walks on Random Graphs: Routing Algorithms for Large-Scale Wireless Sensor Networks,” Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, 2002.
[21]	Manjeshwar. A., Agrawal. D.P., “APTEEN: A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in Wireless Sensor Networks,” Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS), 2002, pp. 195-202.