而在無線感測網路中，感測器佈署完成後通常是沒辦法進行充電之行為，因此電能受到限制。所以在電能受限的情況下，如何設計一個有效的路由演算法就變得很重要。一個有效益的演算法能夠降低能源的消耗並且進一步使得網路的生命週期得以延長。本篇論文提出了一個路由協定。首先，此演算法會將網路分割成制定好的區塊大小，並且將這些區塊個別視為一個叢集。然後使用本篇論文提出的路由演算法條件來進行合併動作，進而產生數個叢集。之後依照節點的電量來執行叢集頭選取以及路由路徑的規劃。透過叢集化的方式可以減少節點的能源消耗，而使得整個網路透過演算法可以更有效的利用能源來進行感測。最後會經由模擬的部分與其他演算法進行比較，來證明我們這篇論文提出的方法比其他方法更能夠達到省電效益，以至於整個網路的生命周期得以延長。

After sensors are deployed, it cannot be recharged in Wireless sensor networks. Therefore, the energy of sensors is limited. In this situation, how to design a routing algorithm is very important. An effective algorithm can reduce energy consumption and prolong network lifetime. In this proposal, we proposed a routing protocol. First, this algorithm divides networks into several units and those units would be regarded as clusters. Second, it uses conditions of method we proposed to generate some clusters by combining. According to remaining energy of nodes, it will execute cluster-head selection. And it can reduce the energy consumption of nodes and use energy effectively to sense by clustering. Finally, we compare the methods we proposed with the others by simulation, and the conclusion proves the method we proposed can save more power to make network lifetime longer than other ways.

第一章	緒論	1
1-1	研究背景	2
1-2	研究動機	7
1-3	研究目的	8
1-4	論文架構	9
第二章	相關背景與研究	10
2-1 研究領域相關背景知識	12
2-1-1	無線感測網路硬體設備	12
2-1-2	無線感測網路設計之影響因素	14
2-1-3	無線感測網路之路由型態	16
2-2 叢集式(CLUSTER-BASED)網路路由協定	18
2-2-1	LEACH	18
2-2-2	EBCRP	20
第三章	無線感測網路之合併網格叢集化路由協定	23
3-1	網路環境設定與假設	27
3-1-1	系統環境	28
3-1-2	能源消耗模組	29
3-1-3	感測器節點與叢集資訊介紹	30
3-2	叢集化階段	32
3-2-1	叢集化	32
3-2-2	選擇叢集頭	39
3-3	路由階段	42
3-3-1	內部傳輸路徑建立	44
3-3-2	外部傳輸路徑建立	45
3-3-3	叢集頭替換機制	46
第四章	模擬比較與分析	50
4-1	模擬環境	50
4-2	模擬結果的分析與比較	51
第五章 結論與未來研究方向	54
5-1	結論	54
5-2	未來研究方向	55
參考文獻	56
附錄—英文論文	63

圖目錄
圖 2.1 感測器節點架構	12
圖 2.2 各種資料聚集拓撲架構	17
圖 2.3 EBCRP叢集化示意圖	21
圖 3.1 網格合併叢集化路由協定流程圖	24
圖 3.2 感測器節點佈置環境示意圖	27
圖 3.3 單位區塊中心示意圖	32
圖 3.4 叢集示意圖	33
圖 3.5 叢集化步驟流程圖	35
圖 3.6 網格編號示意圖	36
圖 3.7 選擇叢集頭流程圖	39
圖 3.8 路徑初始化流程圖	42
圖 3.9 Bellman-Ford演算法範例	44
圖 3.10 叢集頭替換機制流程圖	47
圖 3.11 叢集頭替換排程表	48
圖 4.1 節點存活個數與回合次數關係圖	51
圖 4.2 節點平均電量消耗與回合次數關係圖	51

表目錄
表 2.1 各路由架構方法之優缺點比較表	17
表 3.1 感測器節點資訊表	30
表 3.2 Cluster_Table	31
表 3.3 Head_List	31
表 3.3 叢集頭確認封包	41
表 4.1 模擬環境參數設定	50
表 4.2 MGCRP參數設定	50

[1]	I. F. Akyildiz, S. Weilian, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks, " IEEE Communications Magazine, vol. 40, No 8, pp. 102-114, Aug. 2002.

[2]	C. Meesookho, S. Narayanan, and C. S. Raghavendra, "Collaborative classification applications in sensor networks," Proceedings of 2002 Sensor Array and Multichannel Signal Processing Workshop Proceedings pp.370-374, Aug. 2002.

[3]	T. Arampatzis, J. Lygeros, and S. Manesis, "A Survey of Applications of Wireless Sensors and Wireless Sensor Networks," Proceedings of the 2005 IEEE International Symposium on Mediterrean Conference on Control and Automation Intelligent Control., pp.719-724, June.2005.

[4]	J. N. Al-Karaki and A. E. Kamal, "Routing techniques in wireless sensor networks: a survey, " IEEE Wireless Communications, vol. 11, No 6, pp. 6-28, Dec. 2004.

[5]	J. Qiangfeng and D. Manivannan, "Routing protocols for sensor networks," Proceedings of First IEEE Consumer Communications and Networking Conference, 2004. CCNC 2004. , pp.93-98, Jan. 2004.

[6]	C. Chee-Yee and S. P. Kumar, "Sensor networks: evolution, opportunities, and challenges, " Proceedings of the IEEE, vol. 91, No 8, pp. 1247-1256, Aug. 2003.

[7]	J. J. Lotf, M. N. Bonab, and S. Khorsandi, "A Novel cluster-based routing protocol with extending lifetime for wireless sensor networks," Proceedings of 5th IFIP International Conference on Wireless and Optical Communications Networks, 2008. WOCN '08. , pp.1-5, May. 2008.

[8]	Y. Jae Duck, K. Kyung Tae, J. Bo Yle, and Y. Hee Yong, "An Energy Efficient Chain-Based Clustering Routing Protocol for Wireless Sensor Networks," Proceedings of International Conference on Advanced Information Networking and Applications Workshops, 2009. WAINA '09., pp.383-388, May. 2009.

[9]	L. Xin, W. Quanyu, and J. Xuliang, "An energy-efficient routing protocol for wireless sensor networks," Proceedings of 7th World Congress on Intelligent Control and Automation, 2008. WCICA 2008. , pp.1728-1733, June 2008.

[10]	Y. Zhenhua, L. Yu, and C. Yuanli, "Design of an Energy-Efficient Distributed Multi-level Clustering Algorithm for Wireless Sensor Networks," Proceedings of 4th International Conference on Wireless Communications, Networking and Mobile Computing, 2008. WiCOM '08. , pp.1-4, Oct. 2008.

[11]	A. H. Mohajerzadeh, M. H. Yaghmaee, Z. Eskandari, and H. Deldari, "Energy efficient and congestion aware routing algorithms for Wireless Sensor Networks connected as Hypercube," Proceedings of International Symposium on Telecommunications, 2008. IST 2008. , pp.324-329, Aug. 2008.

[12]	L. Wenjun and Y. Jiguo, "Energy efficient clustering and routing scheme for wireless sensor networks," Proceedings of IEEE International Conference on Intelligent Computing and Intelligent Systems, 2009. ICIS 2009., pp.612-616, Nov. 2009.

[13]	L. Wen-Jiunn and F. Kai-Ten, "Greedy Routing with Anti-Void Traversal for Wireless Sensor Networks, " IEEE Transactions on Mobile Computing, vol. 8, No 7, pp. 910-922, July 2009.


[14]	X. Zhu, L. Shen, and T. S. P. Yum, "Hausdorff Clustering and Minimum Energy Routing for Wireless Sensor Networks, " IEEE Transactions on Vehicular Technology, vol. 58, No 2, pp. 990-997, Feb. 2009.

[15]	M. Youssef, A. Youssef, and M. Younis, "Overlapping Multihop Clustering for Wireless Sensor Networks, " IEEE Transactions on Parallel and Distributed Systems, vol. 20, No 12, pp. 1844-1856, Dec. 2009.

[16]	S. Momma, T. Mikoshi, and T. Takenaka, "Power aware routing and clustering scheme for wireless sensor networks," Proceedings of 8th Asia-Pacific Symposium on Information and Telecommunication Technologies (APSITT), 2010 pp.1-6, June 2010.

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

[18]	X.-r. Bao, S. Zhang, D.-y. Xue, and Z.-t. Qie, "An Energy-Balanced Chain-Cluster Routing Protocol for Wireless Sensor Networks," Proceedings of the 2010 2th International Conference on Networks Security Wireless Communications and Trusted Computing (NSWCTC), pp.79-84, Apr. 2010.

[19]	D. Bertsekas and R. Gallager, Data Networks, 2nd ed. Englewood Cliffs, New Jersey: Prentice–Hall, 1992.

[20]	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, Oct. 2002.

[21]	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, Oct. 2002.