無線感測網路是一個高度受能源限制的裝置。他們受限於裝置的大小與花費等許多限制。多數的無線感測網路無法充電或置換電池，所以，最佳化的利用裝置的能源是無線感測網路最大的挑戰。其中叢集化(Clustering)是常見能在受限制的無線感測網路環境下有效延長其使用壽命的路由機制之一。其中固定叢集化(Static Clustering)能有效減少多次重新叢集化(Re-Clustering)的能源消耗而被廣泛採用，對固定叢集化而言，叢集分割內成員數的平蘅(Balance)是一個重要挑戰的議題，對此本篇論文提出論點以面積分割式叢集化方法用鮮少的訊息傳送確保叢集分割大小的一致，並使叢集分割內的成員達到平衡並得到許多可預估的環境參數以用來運用於許多節省能源的機制。另外，許多叢集化方法都將擁有不同的叢集頭交換方法影響能源消耗，
本論文除了採用先前預估的參數使用較省能的叢集頭更換方法外，將針對每回合是否需要更換叢集頭提供三種方法決擇，利用最少次的叢集頭更換以達到節省能源延長壽命的效果。經由模擬，我們將顯示其網路壽命將優於兩固定叢集化網路Hausdorff和ERP-SCDS。

A wireless sensor network is composed of power-limited devices with constraints of size, condition, and etc. Due to impossibility to recharge or to replace the batteries of sensors, power control becomes a challenging issue in WSN. To prolong the network lifetime, clustering is one of viable approaches. Among the clustering approaches, static clustering avoids the energy consumption in periodical re-clustering. However, how to achieve balanced members in a cluster for static clustering forms another issue. In this thesis, an area-partitioned clustering with a few control messages is proposed. It can not only make balanced members of a cluster but also possesses more flexible parameters. Different from the cluster head rotation methods in the literature, three cluster head rotation methods are further proposed to conserve the energy of cluster head rotation. Via simulations, we show that our proposal outperforms two well-known static clustering protocols, i.e., Hausdorff and ERP-SCDS, in the literature.

Keywords: Clustering, Wireless Sensor Network, Static Clustering.

[1]D. P. Agrawal, and Q. A. Zeng, Introduction to wireless and mobile systems, 2nd ed., Thomas, 2006.
[2] L. K. Alazzawi, A. M. Elkateeb, and A. Ramesh, ``Scalability analysis for wireless sensor networks routing protocols,'' in Proc. IEEE AINAW'08 Apr. 2008.
[3] A. Awang, S. Agarwal, and M. Drieberg, "Data Aggregation using RSSI for Multihop WSN: Energy and Delay Performance," in Communications (MICC), 2013 IEEE Malaysia International Conference on, pp. 422-426, Nov. 2013.
[4] E. Babaee, S. Zareei, and R. Salleh, "Best Path Cluster-based Routing Protocol for WSN," in Computer Modelling and Simulation (UKSim), 2013 UKSim 15th International Conference on, pp. 663-667, Apr. 2013.
[5] Z. Beiranvand, A. Patooghy, and M. Fazeli, "I-LEACH: An Efficient Routing Algorithm to Improve Performance and to Reduce Energy Consumption in WSN," in Information and Knowledge Technology (IKT), 2013 5th Conference on, pp. 13-18, May. 2013.
[6] A. Boukerche, A. Martirosyan, and R. Pazzi, ``An inter-cluster communication based energy aware and fault tolerant protocol for wireless sensor networks,'' ACM Transaction on Mobile Network Application, vol. 13, no. 6, pp. 614-626, Dec. 2008.
[7] A. Boukerche, A. Martirosyan, and R. Pazzi, ``Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting,'' in Proc. IEEE INFOCOM'06, Apr. 2006.
[8] O. Boyinbode, L. Hanh, A. Mbogho, M. Takizawa and R. Poliah, "A Survey on Clustering Algorithms for WSN," in Network-Based Information Systems (NBiS), 2010 13th International Conference on, pp. 358-364, Sep. 2010.
[9] I.R. Chen, A.P. Speer, and M. Eltoweissy, "Adaptive Fault-Tolerant QoS Control Algorithms for Maximizing System Lifetime of Query-Based WSN," in Dependable and Secure Computing, IEEE Transactions on, pp. 161-176, Apr. 2011.
[10] R.S. Elhabyan, and M.C.E. Yagoub, "Weighted tree based routing and clustering protocol for WSN," in Electrical and Computer Engineering (CCECE), 2013 26th Annual IEEE Canadian Conference on, pp. 1-6, May. 2013.
[11] F. Farazandeh, R. Abrishambaf, S. Uysal, T. Gomes, and J. Cabral,, ``A Hybrid Energy-Efficient routing protocol for Wireless Sensor Networks,'' in Industrial Informatics (INDIN), 2013 11th IEEE International Conference on, pp. 18-23.
[12] H. W. Ferng, R. Tendean and A. Kurniawan. ``An energy efficient routing mechanism for wireless sensor networks,'' in Springer Journal of wireless personal communication(published online) March 2011.
[13] M. Ghelichi, S. K. Jahanbakhsh, and E. Sanaei, ``RCCT: Robust clustering with cooperative transmission for energy efficient wireless sensor networks,'' in Proc. IEEE ITNG'08, Feb. 2008.
[14] X. H. Hao, K. Yi, and Y. H. Wang, ``Geographical-based multihop clustering algorithm for distributed wireless sensor network,'' in Proc. IEEE WCICA'08, Jun. 2008.
[15] W. B. Heinzelman, ``Application-specific protocol architectures for wireless networks,'' Ph.D. Thesis, Massachusetts Institute of Technology, MA, Jun. 2000.
[16] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, ``An application-specific protocol architecture for wireless microsensor networks,'' in IEEE Transactions on Wireless communications, vol. 1, no. 4, pp. 660-670, Oct. 2002.
[17] J. Hong, J. Kook, and S. Lee, ``T-LEACH: The method of threshold-based cluster head replacement for wireless sensor networks,'' in Springer Science+Business Media, LLC 2008.
[18] Y. Kang, Y. Han, and J. Hu, "A node scheduling based on partition for WSN," in Wireless Telecommunications Symposium (WTS), 2012, pp. 1-6, Apr. 2012.
[19] A. Kumar, V. Kumar, and N. CHand, "Energy Efficient Clustering and Cluster Rotation Scheme for Wireless Sensor Networks," in IJACSA International Journal of Advanced Computer Science and Applications, vol. 3, No. 5, 2011.
[20] C. F. Li, M. YE, G. Chen and J. Wu, ``An energy-efficient unequal clustering mechanism for wireless sensor networks,'' in Proc. of the 2nd IEEE International Conference on Mobile Ad-hoc and Sensor Systems(MASS), Washington, DC, Nov. 2005.
[21] X. Y. Li, D. P. Huang, and J. Yang, ``Energy efficient routing protocol based on residual energy and energy consumption rate for heterogeneous wireless sensor networks,'' in Proc. IEEE CCC'07, Jul. 2007.
[22] G. Liu, and H. Zhang, "Adaptive Dynamic Hybrid Routing Algorithm in WSNs," in IT in Medicine and Education (ITME), 2011 International Symposium on, pp. 1-6, Dec. 2011.
[23] Q. Mamun, S. Ramakrishnan, and B. Srinivasan, "An Efficient Localized Chain Construction Scheme for Chain Oriented WSN," in Autonomous Decentralized Systems (ISADS), 2011 10th International Symposium on, pp. 3-9, Mar. 2011.
[24] A. Manjeshwar and D. P. Agrawal, ``TEEN: A routing protocol for enhanced efficiency in wireless sensor networks,'' in Proc. IEEE IPDPS'01, Apr. 2001.
[25] V.K. Mehra, "A Multi-Hop Routing Protocol With Pre-Cluster Head Annoucement," in Cloud and Ubiquitous Computing and Emerging Technologies (CUBE), 2013 International Conference on, pp. 93-97, NOV. 2013.
[26] C. Nam, H. Jeong, and D. Shin, ``The adaptive cluster head selection in wireless sensor networks,'' in Proc. IEEE IWSCA'08, Jul. 2008.
[27] K.P. Ng, and C. Tsimenidis, "Energy-Balanced Dynamic Source Routing Protocol for WSN," in Wireless Sensor (ICWISE), 2013 IEEE Conference on, pp. 36-41, Dec. 2013.
[28] M. Patil, and R.C. Biradar, "A Survey on Routing Protocols in WSN," in Networks (ICON), 2012 18th IEEE International Conference on, pp. 86-91, Dec. 2012.
[29] T. M. Rahayu, S.G. Lee,and H. J. Lee, ``Survey on LEACH-based security protocols,'' Advanced Communication Technology(ICACT), 2014 16th International conference on PP. 304-309, Feb. 2014.
[30] A. E. Rhazi and S. Pierre, ``A Tabu search algorithm for cluster building in wireless sensor networks,'' IEEE Transactions on Mobile Computing, vol. 8, no. 4, pp. 433-444, Apr. 2009.
[31] H. Taheri, P. Neamatollahi, M. Naghibzadeh, and M. Yaghmaee, "Improving on HEED Protocol of WSN using Non Probabilistic Approach and Fuzzy Logic(HEED-NPF)," in Telecommunications (IST), 2010 5th International Symposium on, pp. 193-198, Dec. 2010.
[32] A. Thakkar, and K. Kotecha, "Cluster Head Election for Energy and Delay Constraint Applications of Wireless Sensor Network," in IEEE Sensors Journal(Volume:PP, Issue:99), Mar. 2014.
[33] R.K. Tripathi, Y.N. Singh, and N.K. Verma, "N-LEACH, a Balanced Cost Cluster-Heads Selection Algorithm for WSN," in Communications (NCC), 2012 National Conference on, pp. 1-5, Feb. 2012.
[34] W. Wang, V. Srinivasan, and K. Chua, ``Using mobile relays to prolong the lifetime of wireless sensor networks,'' in Proc. ACM MobiCom'05, Sep. 2005.
[35] X. B. Wu, G. H. Chen, and S. K. Das, ``Avoiding energy holes in wireless sensor networks with nonuniform node distribution,'' in IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 5, pp. 710-720, May. 2008.
[36] Z. Z. Xu, S. Q. Zhang, X. L. Zhang, B. H. Bao, and P. Li, ``An adaptive clustering protocol for medium-scale wireless sensor networks,'' in Proc. IEEE WiCom'07, Sep 2007.
[37] M. YE, C. F. Li, G. Chen and J. Wu, ``EECS:an energy efficient clustering scheme in wireless sensor networks,'' in Proc. IEEE INt'1 Perfomance Computing and communications conference(IPCCC), pp. 535-540, 2005.
[38] M. YE, C. F. Li, G. Chen and J. Wu, ``EECS:an energy efficient clustering scheme in wireless sensor networks,'' to appear in International Journal of Ad Hoc and Sensor Wireless Networks.
[39] O. Younis and S. Fahmy, ``HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks,'' in IEEE Transactions on Mobile Computing, vol. 3, no. 4, pp. 366-379, Oct.-Dec. 2004.
[40] J. W. Zhang, Y. Y. Ji, J. J. Zhang, and C. L. Yu, ``A weighted clustering algorithm based routing protocol in wireless sensor networks,'' in Proc. IEEE CCCM'08, Aug. 2008.
[41] Z. D. Zhou, C. Xu, and Q. Liu, ``Energy modeling and HMST-based wireless sensor networks routing protocol,'' in Proc. IEEE ICIEA'07, May. 2007.
[42] X. R. Zhu, L. F. Shen, and T.-S. P. Yum, ``Hausdorff clustering and minimum energy routing for wireless sensor networks,'' IEEE Transaction on Vehicular Technology, vol. 58, no. 2, pp. 990-997, Feb. 2009.