請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/64541
標題: | 以粒子群聚演算法解決無線隨意網路下靜態與動態最少資源群播問題 Particle Swarm Optimization for the Static and Dynamic Minimum Energy Broadcast Problem in Wireless Ad-Hoc Networks |
作者: | Ping-Che Hsiao 蕭稟哲 |
指導教授: | 傅立成(Li-Chen Fu) |
關鍵字: | 粒子群聚演算法,最少資源群播問題,無線隨意網路,無線感測網路,動態最少資源群播問題, Particle Swarm Optimization,Minimum Energy Broadcast Problem,Wireless Ad-Hoc Network,Wireless Sensor Network,Dynamic MEB Problem, |
出版年 : | 2012 |
學位: | 碩士 |
摘要: | 這篇論文中研究如何解決無線隨意網路(Wireless Ad-hoc Networks)下的最少資源群播(Minimum Energy Broadcast)問題,且此問題已被證明是NP-complete。由於無線隨意網路可以被快速的佈建,因此已被廣泛地應用在不同的領域中,其中一項主要的應用即是無線感測網路(Wireless Sensor Networks)。在無線感測網路中,由於每個感測節點皆只配備了有限的電力資源,因此網路的消耗資源最小化是在研究領域中一個非常重要的議題。最少資源群播問題即是無線感測網路中的一個重要情況,在這個問題中需要把所要傳遞的封包由一個指定的來源節點傳達到網路中其他所有節點上,而這個問題的目的是要將傳送所消耗的資源最小化。我們使用結合了粒子群聚演算法和區域搜尋的混合式方法來解決此問題,我們提出了一個用來定義每個粒子位置的編碼方法,稱作資源階層編碼(power degree encoding);我們也更進一步的分析一個知名的區域搜尋演算法並提出一個改進的版本,稱作強化型r皺縮(intensified r-shrink)。除此之外,為了處理節點故障和節點尋獲下的動態最少資源群播問題,我們在這篇論文中也會使用一個新的架構以快速地連接分離的子網路,其中也提出一個簡易啟發式演算法來選擇連結的對象。實驗結果指出提出的演算法有可被實際應用的潛力。 In this thesis, we addressed the NP-complete minimum energy broadcast (MEB) problem in wireless ad-hoc networks (WANETs). The researches in WANETs have attracted significant attentions because of their convenient deployment and a variety of applications including wireless sensor networks (WSNs). One of the most critical issues in WSNs is lifetime maximization and energy consumption minimization because each node in the network is only equipped limited energy resource. The MEB problem is one of the most important scenarios in WSNs, where the packets have to be transported from a given source node to all other nodes in the network. The objective of the MEB problem is to minimize the total transmission power consumption. A hybrid algorithm based on particle swarm optimization (PSO) and local search was presented to solve the MEB problem. We proposed a power degree encoding to reflect the extent of transmission power level, and it was used to define the particle position in PSO. We also analyzed a well-known local search mechanism, r-shrink, and proposed an improved version, the intensified r-shrink. In order to deal with the dynamic MEB problem, which runs into node removal/insertion, this thesis provided a framework for rapidly linking up disconnected components and presented an effective simple heuristic, Conditional Incremental Power, to repair the network. The promising results indicated the potential of proposed method to be applied to practical use. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/64541 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-101-1.pdf 目前未授權公開取用 | 6.38 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。