基於Fuzzy C-Means聚類法之混合型階層式群集方法於無線感測網路 之研究

A Hybrid Hierarchical Clustering Approach Based on Fuzzy C-Means for Wireless Sensor Networks

高宗毅(Tsung-Yi Kao)

指導教授 ： 李俊賢

國立臺北科技大學/電資學院/電機工程系研究所/碩士(2012年)

https://doi.org/10.6841/NTUT.2012.00265

摘要

近年來，由於半導體的發展，帶起無線感測網路(wireless sensor network, WSN)的進步。在無線感測網路中，感測節點通常佈置於不易維護的環境，以及感測節點能源上的限制。因此學者們為了提高節點能源使用效率，提出各種路由演算法，依結構可分成平面式、階層式、基於位置三種。其中階層式演算法可再區分為分散式與集中式演算法，其中最具代表性的分散式演算法為低能源自適應性群集階層式路由演算法(low energy adaptive clustering hierarchy, LEACH)。它是由隨機選擇群集簇頭(cluster head, CH)，以及輪流當任CH的方式，使感測節點之能源均勻使用，有效的提升網路壽命。而集中式演算法是透過基地台(base station, BS)做分群，典型的演算法如LEACH-Centralized (LEACH-C)。
本論文是以LEACH演算法為基礎來改良，提出混合型階層式群集方法(hybrid hierarchical clustering approach, HHCA)，將分群演算法之結構進一步拆分成上、下層兩個部份。在上層方面，我們使用集中式的方式執行Fuzzy C-Means聚類法計算上層分格(grid)。在下層方面，以分散式的LEACH加入感測節點能源與節點數量之考量，進一步對grid再做分群。利用由上往下的選擇順序，及混合分散式與集中式的選擇方式，達到分群再分群的階層式結構，以延長感測網路的壽命。

關鍵字

無線感測網路 ； 階層式演算法 ； 群集方法 ； 群集簇頭 ； 能源消耗

並列摘要

In recent years, because of development of the semiconductor technology, it leads the progress of wireless sensor networks (WSNs). In WSNs, sensor nodes are usually arranged in a hardly maintainable environment and sensor nodes have limited on energy. Thus, scholars have proposed routing algorithms in order to improve energy efficiency. Routing algorithms in WSNs can be divided into flat-based routing, hierarchical-based routing, and location-based routing depending on the network structure. Hierarchical-based routing can be further divided into the distributed and centralized routing algorithms. Low energy adaptive clustering hierarchy (LEACH) is the most representative distributed routing algorithm. LEACH uses random rotation mechanism to select cluster head (CH) to improve WSN lifetime. LEACH-Centralized (LEACH-C) is a centralized routing algorithm and it selects CH by base station (BS).
In this paper, based on the LEACH, we proposed hybrid hierarchical clustering approach (HHCA). The approach is split into upper and lower layer according to the algorithm structure. First, we use Fuzzy C-Means clustering method to calculate the grid head by BS in the upper layer. Then, based on the LEACH, we consider remaining energy and number of nodes to cut the grid in the lower layer. By different selection order, mixed selection mechanism lead to a hierarchical structure and improve WSN lifetime.

並列關鍵字

Wireless sensor network ； hierarchical routing algorithm ； cluster head ； clustering approaches ； fuzzy c-means ； energy consumption

參考文獻

[19] V. Katiyar, N. Chand, G. C. Gautam, and A. Kumar, “Improvement in LEACH protocol for large-scale wireless sensor networks”, in Proc. International Conference on Emerging Trends in Electrical and Computer Technology ICETECT’11, Hamirpur, India, Mar. 2011, pp. 1070-1075.

[1] J. N. Al-Karaki, and A. E. Kamal, “Routing techniques in wireless sensor networks: a survey,” IEEE Wireless Commun., vol. 11, no. 6, pp. 6-28, Dec. 2004.

[2] K. Akkaya, and M. Younis, “A survey of routing protocols in wireless sensor networks,” Elsevier Ad Hoc Network, vol. 3, pp. 325-349, May. 2005.

[4] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks,” IEEE Trans. Wireless Communications, vol.1, no.4, pp. 660-670, Oct. 2002.

[6] T. Rappaport, “Wireless communications: principles & practice,” Englewood Cliffs. NJ, Prentice-Hall, 1996.