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

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

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

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