以基因演化為基礎之多介面無線網狀網路資源管理實作

Abstract

在multi-channel multi-radio（MCMR） Wireless Mesh Networ（WMN）環境下有兩大因素影響網路效能，分別是channel assignment（CA）與multi-channel routing（MCR）。而結合CA與MCR的WMN最佳化問題也已經被證明是一個NP-hard的問題。在此篇論文裡，我們搭配使用兩種最佳化工具genetic algorithm（GA）與linear programming（LP）來處理結合CA與MCR的網路最佳化問題。首先我們利用GA的離散性質，將可能的CA對應成GA中的chromosome，然後透過LP得到相應的最佳MCR。因為CA與MCR彼此是互相影響的，為了反映這樣的特性，我們在GA中藉由計算linear objective function的結果來評價每個chromosome（可能的CA）的fitness value（能夠解決問題的程度）。藉此我們成功地拆解了這兩個問題，並且在polynomial time內得到最佳的CA與相應的最佳化MCR決策。在我們的實作方面，我們設計了一個含有我們網路資源管理演算法的路由器軟體來最大化我們的系統throughtput。在我們的測試平台上評估路由器軟體時，我們觀察到三個因素造成網路資源管理演算法表現不如預期，第一個是無法準確地估測wireless link capacity，第二個是非理想的傳輸排程，第三個是難以滿足使用者預先定義的流量需求。因此，計算出的路由路徑並不如演算法打算的是一個最佳化的路徑。雖然這兩個因素在理論的最佳化模型上通常是被假設為可解的，但從我們的實作經驗來看，我們推論這些假設在某些網路並不完全成立。

Two main issues involved with the performance of multi-channel multi-radio (MCMR) 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. In our implementation, we design a router software the incorporates our WMN resource management algorithm to maximize the system throughput. When evaluating the software on our operational testbed, we observe three factors that prevent the resource management algorithm from performing well as expected. The first factor is the inaccuracy of wireless link capacity estimation, the second one is the imperfection of traffic scheduling, and the third one is the difficulty of satisfying pre-defined user bandwidth demand. Consequently, the computed routing path is not optimized as the algorithm intends to. While the three factors are generally assumed to be solvable in theoretical optimization models, from our prototyping experiences, we conclude that these assumptions do not always hold in practical networks.