平衡樹演算法應用於無線感測器網路系統之研究

Study on Application Balanced Tree Algorithm to Wireless Sensor Network System

曾主平(Chu-Ping Tseng)

指導教授 ： 江昭皚

國立臺灣大學/生物資源暨農學院/生物產業機電工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.01360

摘要

無線感測器網路系統(Wireless Sensor Network, WSN)因各感測器節點的電量有限，使得無線感測器網路無法長時間運作，故侷限無線感測器網路系統在各領域的應用與發展。為改善無線感測器網路系統的系統壽命，專家學者利用各種路由演算法以增加無線感測器網路系統之壽命。本研究於一階負載平衡樹路由演算法(BLLCT)之應用中發現，一階負載平衡樹路由演算法的規劃路徑有可改善之空間。因此，吾人提出靜態修正及動態修正兩種改善方式，並於模擬實驗中證實此兩種改善方式能夠增加傳統一階負載平衡樹路由演算法的WSN系統壽命。
靜態修正方式以平衡傳統一階負載平衡樹路由演算法所形成之各子樹的方式，將負載較大之子樹的節點轉移至其他子樹，以達到較佳的一階節點負載平衡性。動態修正則在傳統一階負載平衡樹路由演算法中加入一電量評估步驟，做為決定是否更換父節點的依據，規劃各感測器節點在不同回合時的回傳路徑。集中式與分散式路由演算法在不同的應用領域中分別有其優缺點，本研究亦提出一分散式路由演算法，分別使用逐層跳躍及一次跳躍兩層的方式進行回傳路徑規劃。
由分析不同模擬情況下各演算法的數據後可得，在一個固定區域中均勻佈放節點，節點數目多寡將不會對WSN系統壽命有太大的影響。集中式路由演算法在通訊距離及節點數目增加時，因整體網路內感測器節點通信連結數變多的情況，造成收集整體網路拓樸需耗費較多的電量，而降低WSN系統壽命。因此，集中式路由演算法是較適合於小規模的網路拓樸中使用。分散式路由演算法因建立於感測器節點本身，不受整體網路拓樸規模大小的影響，可較有利於大規模的網路拓樸中使用。

關鍵字

平衡樹演算法 ； 集中式路由演算法 ； 分散式路由演算法 ； 無線感測器網路

並列摘要

The applications of wireless sensor network (WSN) in many fields are limited due to insufficient of battery lifetime. In previous studies, a number of routing algorithms have been proposed to prolong the lifetime of WSN system. We found some drawbacks of balanced low-latency convergecast tree (BLLCT) algorithm while applying it to real-world application. To overcome the problems in BLLCT algorithm, this study proposed static and dynamic fixing schemes to prolong the lifetime of WSN system. In the experimental results, the proposed schemes can extend the lifetime of WSN.
For every sub-tree constructed by BLLCT algorithm, static fixing scheme balances the loading of first-order nodes by diverting the nodes in max-loading sub-tree to the other sub-trees. Dynamic fixing scheme combines the BLLCT algorithm with consideration of remaining power of node’s parent node. The dynamic fixing scheme decides whether the node needs to change its parent node or not.
Centralized and distributed routing algorithms are also proposed in this study. These algorithms are suitable for many applications. The proposed distributed routing algorithm is applied to a WSN system that operates in one hop or two hops mode.
The experimental results show that the network size of the WSN system affects the lifetime of WSN system slightly if the sensing nodes are deployed in a region with same area. The WSN’s lifetime using centralized routing algorithm is shortened because sink nodes need to collect large amount of information from the entire network. Thus, the centralized routing algorithm is more suitable for smaller networks, and the distributed routing algorithm is suitable for larger networks.

並列關鍵字

Balanced low-latency convergecast tree algorithm ； Centralized routing algorithm ； Distributed routing algorithm ； Wireless sensor network

參考文獻

林亦謙。2006。應用於無線感測器網路之被動式電力決策路由演算法。碩士論文。台北：淡江大學資訊工程研究所。

陳義祥。2005。遠端微氣候無線監測系統之開發。碩士論文。台北：台灣大學生物產業機電工程研究所。

劉新盛。2006。無線居家照護網路之研製。碩士論文。台北：台北科技大學電腦與通訊研究所。

李明儒。2006。應用無線感測器網路提高隧道防救災機制之研究。碩士論文。桃園：中原大學土木工程研究所。

林冠璋。2007。使用無線感測器網路之自動化害蟲生態監測系統研製。碩士論文。台北：台北科技大學機電整合研究所。