基于模擬退火遺傳算法的無線mesh網(wǎng)絡路由放置問題研究.pdf

1、網(wǎng)絡的路由放置問題在無線Mesh網(wǎng)絡中一直是一個重要研究方向。一個高效的mesh路由節(jié)點放置方法能有力地保證網(wǎng)絡的連通和用戶的全覆蓋。因為無線mesh網(wǎng)絡可以提供價格低廉的無線帶寬，所以在網(wǎng)絡基礎設施建設上它變得越來越重要。然而，此類問題是NP難題，研究者們通過利用啟發(fā)式算法去解決這類問題以獲得近似最優(yōu)，希望能在合理的時間內(nèi)得到高質(zhì)量的解。
　　 本文首先介紹了無線Mesh網(wǎng)絡和路由放置問題的多種模型，并詳細討論了模擬退火算法(

2、SimulatedAnnealingAlgorithm)和遺傳算法(GeneticAlgorithm)這兩種經(jīng)典的啟發(fā)式算法的聯(lián)系。在此基礎上對模擬退火算法和遺傳算法進行了改進，進一步提出了模擬退火遺傳算法(SimulatedAnnealing-GeneticAlgorithm，SA-GA)去解決無線mesh網(wǎng)絡中的路由放置問題。一方面，SA-GA算法在模擬退火算法的降溫過程中采用覆蓋范圍小且處在用戶密集區(qū)域的路由器與覆蓋范圍大且處于用

3、戶稀疏區(qū)域的路由器進行交換，提高大中型網(wǎng)絡的局部優(yōu)化能力；另外，采用覆蓋范圍最大的路由放置在區(qū)域中用戶最集中的位置，提高小型網(wǎng)絡計算時間；另一方面，在遺傳算法種群進化過程中，從已選擇好的父系個體中選取適應度值高的兩個父系個體以一定大小隨機區(qū)域為交叉因子進行交叉，提高全局優(yōu)化能力。最后，以遺傳算法流程為主體，融合模擬退火算法進一步對種群進行優(yōu)化調(diào)整，達到增加隨機性和提高全局搜索能力的目的，即從父系群體中選取較小比例的父系個數(shù)，另外，增加路