應用基因演算法優化無線網狀網路

Abstract

在多介面多通道無線網狀網路環境下有兩大因素影響網路效能，分別是通道分配(Channel Assignment)與多通道路由(Multi-Channel Routing)。而合併考慮通道分配與多通道路由的網路最佳化問題也已經被證明是NP-hard問題。在此篇論文裡，我們搭配使用兩種最佳化工具基因演算法(Genetic Algorithm)與線性規劃(Linear Programming)來處理合併考慮通道分配與多通道路由的最佳化問題，首先我們利用基因演算法的離散型變數可解性，將一種通道分配結果對應成基因演算法中的染色體，每個通道分配透過運作線性規劃來得到相應的最佳多通道路由決策。因為通道分配與多通道路由彼此是互相影響的，為了反映這樣的特性，我們在基因演算法中藉由計算線性目標函數的結果來評價每個染色體(一種通道分配的可能)的適合值(fitness value)。藉此我們成功地分開這兩個問題並且在多項式時間(polynomial time)內得到最佳的通道配置與相應的最佳化多通道路由決策。根據這樣的基因演算架構，我們對三種不同的無線網狀網路建置限制設計了三種基因演算法，每個演算法都是基於相同的演算架構但根據限制的不同只需要做部分的修改，希望可以透過客制化不同需求的無線網狀網路建置方法，使本篇研究成為有效的無線網狀網路建置指導方針。模擬的部分，我們將我們的演算法所得到的結果，與之前解決相同問題的其他研究做比較，顯示我們的方法可以有效的增加並改善網路的效能。

Two main issues involved with the performance of multi-channel multi-radio wireless mesh networks (WMNs) are channel assignment (CA) and multi-channel routing (MCR). Joint CA and MCR problem has been proven to be NP-hard. In this thesis, we propose to apply genetic algorithms for CA problem and tackle MCR using linear programming techniques. Since CA and MCR tend to interact with each other, to reflect such interplay property, we evaluate the fitness value of a chromosome (certain CA configuration) in our genetic algorithms by computing the linear objective function. Therefore, we successfully decouple the two problems and obtain an optimized CA configuration with corresponding MCR schedule in polynomial time at the WMN planning stage. We demonstrate the detailed genetic evolution processes for three WMNs with different deployment constraints, which serves as a useful guideline on customizing WMNs under various requirements. Simulation results show the proposed approach effectively increases the network capacity.