- 學位論文
最小生成樹應用於分散式叢集之研究
On the Study of Distributed Clustering Method Using Minimum Spanning Tree
摘要
無線感測網路(WSNs)是由許多有限電量的感測器所組成，並且經常佈署在人煙稀少的位置，因此如何有效率地節省感測器能源並延長網路壽命成為相當重要的議題。其中最常見且有效率的能節能方法為叢集方法，目的將無線感測網路劃分為許多叢集，每個叢集推選出一個叢集頭匯集感測器的資料，最後發送給基地台。此方法可以有效地降低整體網路能量的損耗，但是會導致叢集頭快速死亡，因此我們提出CEMST演算法，叢集頭的選擇考慮節點重疊度(overlapping degrees)、密度(density)與剩餘電能(residual energy)，並且傳輸的路徑使用Dijkstra最短路徑演算法和最小生成樹(MST)中的Borůvka演算法，減緩並平衡叢集的電能損耗，並延長感測網路的壽命。
並列摘要
Wireless sensor network (WSNs) is limited by many power sensors, and are often deployed in a sparsely populated place, so how to effectively save energy and prolong the sensor network lifetime has become an important issue. One of the most common and efficient energy saving method for cluster method, the wireless sensor network is divided into clusters, each cluster to elect a cluster head collects sensor data, and finally sent to the base station. This method can effectively reduce the energy loss of the whole network, but will lead to rapid death of the cluster head, so we propose CEMST algorithm, the cluster head selection considering node overlap degrees(overlapping degrees), density and residual energy, and transmission path using Dijkstra shortest path algorithm and the minimum spanning tree (MST) in the Borůvka algorithm, reduce power loss and balance the cluster, and extend the network lifetime.