請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/42128
標題: | 平衡樹演算法應用於無線感測器網路系統之研究 Study on Application Balanced Tree Algorithm to Wireless Sensor Network System |
作者: | Chu-Ping Tseng 曾主平 |
指導教授: | 江昭皚(Joe-Air Jiang) |
關鍵字: | 平衡樹演算法,集中式路由演算法,分散式路由演算法,無線感測器網路, Balanced low-latency convergecast tree algorithm,Centralized routing algorithm,Distributed routing algorithm,Wireless sensor network, |
出版年 : | 2008 |
學位: | 碩士 |
摘要: | 無線感測器網路系統(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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/42128 |
全文授權: | 有償授權 |
顯示於系所單位: | 生物機電工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf 目前未授權公開取用 | 3.71 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。