以粒子群聚演算法解決無線隨意網路下靜態與動態最少資源群播問題

Abstract

這篇論文中研究如何解決無線隨意網路(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.