标题: 应用基因演算法优化无线网状网路
Applying Genetic Algorithms for Multi-channel Wireless Mesh Network Planning
作者: 谢凯全
林亭佑
电信工程研究所
关键字: 无线网状网路;线性规划;基因演算法;Wireless Mesh Network;Linear Programming;Genetic Algorithm
公开日期: 2010
摘要: 在多介面多通道无线网状网路环境下有两大因素影响网路效能,分别是通道分配(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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079713539
http://hdl.handle.net/11536/44559
显示于类别:Thesis