無線感測網路是一種用於收集資料的網路，此種網路通常由數百到數千個節點所組成，各節點主要由電池供電。由於其規模龐大的節點數量，所以環境部署後的節點回收再充電是非常困難的。因此，如何有效利用能源來延長整體網路的壽命將是此種網路的設計重點。

在大規模感測網路中，使用群組劃分是比較簡單、有效率的方法。此種方法主要是把大規模網路劃分成許多的小群組，然後藉由群組核心（cluster head）來負責群組內的資料整合、各群組間的資料交換。此方法省電的原因如下：
1.群組劃分有助於資料的分區與整合，對於大規模感測網路中龐大的資料量，有效的達到資料的減量，而減少資料傳輸的能源消耗。
2.群組核心的觀念，有助於減少網路中負責資料轉傳的節點數量，進		而減少通道競爭的情況。
3.群組/群組核心的週期重選機制，可以避免高能源消耗的重擔集中於	某些節點，而是由各節點輪流承擔，有助於整體網路的負載平衡、		延長整體網路壽命。

如上述，可以看出群組核心在群組劃分裡的重要性，除了資料的收集、轉傳之外，群組核心的選擇也決定著群組大小、位置和整體群組數量，影響著整體感測網路的能源效能。因此，ㄧ個執行效率好的群組核心選擇機制，是在此領域討論的重點。

本篇論文提出一個新的群組劃分（clustering）方法，並且使用一個創新的群組核心選取方式，來達到低訊息交換、最佳能源的群組核心選擇的目的。

此方法主要使用剩餘能源與時間優先權的觀念，利用各節點的剩餘能源比來計算出各節點的群組等待時間，而群組等待時間最短的節點，將獲得鄰近地區最高的優先權，而成為此一地區的群組核心，進而收集群組成員（cluster member）。如此的群組核心選取方式，可以在良好的同步機制運作下，就選取到能源狀況比較好的群組核心，進而節省訊息交換的封包傳輸能源消耗。

A Wireless Sensor Network consists of hundreds or thousands of sensor nodes. Sensor nodes are battery-powered and usually deployed in an unprotected environment to collect the needed information. Because of the enormous number of sensor nodes, it is difficult to recharge sensor nodes after distribution. So, how to increase energy efficiency and prolong the network lifetime is the design focus.

Clustering is the easier and more efficient way to save energy in wireless sensor networks. Having cluster heads process the data collected by cluster members have the following energy efficient factors:
1.Considering the data collected by large amount of sensor nodes, cluster 	heads help the aggregation of data and reduce the number of data transmissions.
2.Clustering reduces the number of nodes that need to relay data, therefore reduces the channel-competing situation.
3.Periodical reselection of clusters/cluster heads can avoid the heavy loads on particular nodes, letting all nodes take turns balances loading and extends the entire network lifetime.

The importance of cluster heads is stated above. Besides data aggregation and transmission, the method of selecting cluster heads also determines the size of a cluster, the position of a cluster head and the number of cluster heads in a network, thus affecting the energy consumption of a wireless sensor network. Implementing an efficient cluster head selection scheme is one of the key points in clustering.

This paper presents a new clustering approach. It uses a new cluster-head selection method to reach the goals of low clustering information overhead and optimal cluster-head selection.

It uses node residual energy to compute the clustering waiting time of each node. The node, which has the shortest waiting time, will have the highest priority to become a cluster head. This method can choose nodes with more energy as cluster heads and further decreases energy consumption for clustering overhead.

目   錄
中文摘要                                                    I
英文摘要                                                  III
目   錄                                                     V
圖 表 目 錄                                               VII
第一章 簡介                                                 1
  1.1.前言                                                  1
  1.2.章節架構                                              5
第二章 相關研究背景                                         6
  2.1.背景知識                                              6
  2.2.LEACH                                                10
  2.3.HEED                                                 13
  2.4.TDC                                                  16
第三章 新群組核心選擇機制(2RTD、3RTD)                      19
  3.1.研究動機                                             19
  3.2.機制(2RTD、3RTD)的設計                               20
    3.2.1.設計的想法                                       20
    3.2.2.2RTD                                             23
    3.2.3.3RTD                                             26
第四章 效能評估                                            29
  4.1.模擬環境與參數設定                                   29
  4.2.能源模組                                             31
  4.3.網路壽命(network lifetime)比較                       33
  4.4.RTD區間延遲時間比例與效能的關係                      39
  4.5.3RTD第二分段點位置與效能的關係                       42
第五章 結論與未來工作                                      47
參考文獻                                                   49

圖 表 目 錄
圖 1.1 無線感測網路基本架構                                 2
圖 2.1 群組大小與無線感測網路的負載平衡                     8
圖 2.2 無線感測網路群組傳輸，不經由閘道器節點               9
圖 2.3 無線感測網路群組傳輸，經由閘道器節點                 9
圖 2.4 LEACH的100個隨機節點                                12
圖 2.5 HEED論文中的程式演算法                              15
圖 2.6 TDC的分段線性函式                                   18
圖 3.1 孤立節點範例                                        22
圖 3.2 2RTD群組核心選擇機制流程圖                          25
圖 3.3 3RTD群組核心選擇機制流程圖                          28
圖 4.1 廣播能源消耗模組                                    31
圖 4.2a 500個感測器節點的網路壽命，不含群組劃分能源消耗    35
圖 4.2b 群組核心平均數量                                   35
圖 4.3a 300個感測器節點的網路壽命，不含群組劃分能源消耗    36
圖 4.3b 群組核心平均數量                                   36
圖 4.4 500個感測器節點的網路壽命                           38
圖 4.5 300個感測器節點的網路壽命                           38
圖 4.6 2RTD與3RTD在500個感測器節點的網路壽命               46
圖 4.7 2RTD與3RTD在300個感測器節點的網路壽命               46
表 4.1 參數設定                                            30
表 4.2a 500個感測器節點的區間比例模擬                      40
表 4.2b 感測器節點座落在二個能源區間的比例                 40
表 4.3a 300個感測器節點的區間比例模擬                      41
表 4.3b 感測器節點座落在二個能源區間的比例                 41
表 4.4a 500個感測器節點的第二分段點模擬                    44
表 4.4b 感測器節點座落在三個能源區間的比例                 44
表 4.5a 300個感測器節點的第二分段點模擬                    45
表 4.5b 感測器節點座落在三個能源區間的比例                 45

[1] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks”, IEEE Communications Magazine, Vol. 40, Issue 8, pp. 102-114, Aug. 2002.
[2] D. P. Agrawal, and Q. A. Zeng, Introduction to Wireless and Mobile Systems, 2/e, Thomson, Mar. 2005, pp. 303-357.
[3] W.R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy- efficient communication protocol for wireless microsensor networks”, Proc. 33rd Annual Hawaii Int’l Conf. System Sciences, vol.2, Jan 4-7 2000.
[4] W.B. Heinzelman, A.P. Chandrakasan, and H. Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks”, IEEE Trans. on Wireless Communications, Vol. 1, Issue 4, pp. 660-670, Oct. 2002.
[5] Ruay-Shiung Chang, and Chia-Jou Kuo, “An energy efficient routing mechanism for wireless sensor networks”, proc. 20th Int’l Conf. on Advanced Information Networking and Applications, Vol. 2, Apr. 18-20 2006.
[6] O. Younis, and S. Fahmy, “HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks”, IEEE Trans. on Mobile Computing, Vol. 3, Issue 4, pp. 366-379, Oct.-Dec. 2004.
[7] Tao Zhong, Sheng Wang, Shizhong Xu, Hongfang Yu, and Du Xu, “Time Delay Based Clustering in Wireless Sensor Networks”, Wireless Communications and Networking Conf. IEEE, March 11-15 2007, pp. 3956-3960.
[8] L. Clare, G. Pottie, and J. Agre, “Self-organizing distributed sensor networks”; in Proc. SPIE Conf. Unattended Ground Sensor Technologies and Applications, Vol. 3713, pp. 229–237, Apr. 1999.
[9] Limin Hu, “Distributed code assignments for CDMA packet radio networks”, IEEE/ACM Trans. on Networking, Vol. 1, Issue 6, pp. 668 – 677, Dec. 1993.
[10] O. Younis, M. Krunz, and S. Ramasubramanian, “Node clustering in wireless sensor networks: recent developments and deployment challenges”, IEEE Network Magazine, Vol. 20, Issue 3, pp. 20-25, May-June 2006.
[11] T. Shu, M. Krunz, and S. Vrudhula, “Power Balanced Coverage Time Optimization for Clustered Wireless Sensor Networks”, Proc. 6th ACM Int’l Symp. on Mobile and Ad Hoc Networking and Computing, May 2005, pp. 111-120.