基于模擬退火遺傳算法的無線mesh網(wǎng)絡(luò)路由放置問題研究的中期報(bào)告

基于模擬退火遺傳算法的無線mesh網(wǎng)絡(luò)路由放置問題研究的中期報(bào)告摘要：無線Mesh網(wǎng)絡(luò)已經(jīng)成為一種重要的無線自組織網(wǎng)絡(luò)形式，它的典型應(yīng)用是城市覆蓋網(wǎng)絡(luò)和緊急應(yīng)急通信網(wǎng)絡(luò)。在無線Mesh網(wǎng)絡(luò)中，路由節(jié)點(diǎn)的合理放置是關(guān)鍵因素之一，可以有效地影響網(wǎng)絡(luò)的性能。本文提出了一種基于模擬退火遺傳算法的路由節(jié)點(diǎn)放置問題求解方法，并且進(jìn)行了實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，所提出的方法在效率上和準(zhǔn)確度上都優(yōu)于其他基準(zhǔn)算法。關(guān)鍵詞——無線Mesh網(wǎng)絡(luò)，路由放置問題，模擬退火遺傳算法1.引言無線Mesh網(wǎng)絡(luò)是一種新興的無線自組織網(wǎng)絡(luò)形式，它采用分散式的無線節(jié)點(diǎn)構(gòu)成網(wǎng)絡(luò)，利用節(jié)點(diǎn)之間相鄰的無線鏈路進(jìn)行數(shù)據(jù)通信。由于無線Mesh網(wǎng)絡(luò)具有較低的成本、易于部署、容易擴(kuò)展等優(yōu)點(diǎn)，已經(jīng)成為各種應(yīng)用場景中的重要網(wǎng)絡(luò)技術(shù)之一。然而，在無線Mesh網(wǎng)絡(luò)中，節(jié)點(diǎn)之間的通信必須經(jīng)過多跳傳輸，這就需要合理地安排路由節(jié)點(diǎn)的位置，以實(shí)現(xiàn)網(wǎng)絡(luò)的高效運(yùn)行。2.相關(guān)工作在路由節(jié)點(diǎn)放置問題方面，已經(jīng)涌現(xiàn)出許多求解方法。BaichuanLi等人提出了一種基于啟發(fā)式算法的路由節(jié)點(diǎn)最優(yōu)化放置方法，它利用遺傳算法和模擬退火算法實(shí)現(xiàn)節(jié)點(diǎn)放置優(yōu)化[1]。MaodingDu等人提出了一種基于遺傳算法的路由節(jié)點(diǎn)段選模型[2]。雖然這些方法在一定程度上提高了問題求解的效率和準(zhǔn)確度，但還有很多問題需要進(jìn)一步解決。3.問題模型本文研究的路由節(jié)點(diǎn)放置問題模型如下所示。假設(shè)在一個平面區(qū)域中有n個節(jié)點(diǎn)，每個節(jié)點(diǎn)可以作為網(wǎng)絡(luò)中的路由節(jié)點(diǎn)?，F(xiàn)在需要從這些節(jié)點(diǎn)中選出一部分節(jié)點(diǎn)作為路由節(jié)點(diǎn)，以實(shí)現(xiàn)網(wǎng)絡(luò)的高效運(yùn)行。節(jié)點(diǎn)的選擇具有以下兩個約束條件：（1）每個節(jié)點(diǎn)只能被選中一次。（2）選中的節(jié)點(diǎn)之間必須滿足網(wǎng)絡(luò)拓?fù)湟?，即?jié)點(diǎn)之間的距離不超過一定范圍。4.方法設(shè)計(jì)與實(shí)現(xiàn)本文提出了一種基于模擬退火遺傳算法的路由節(jié)點(diǎn)放置問題求解方法。該方法首先利用遺傳算法對解空間進(jìn)行搜索，然后在模擬退火的基礎(chǔ)上進(jìn)行局部搜索。具體來說，該方法包括以下三個步驟：（1）初始化：將所有節(jié)點(diǎn)隨機(jī)排列，得到第一代種群。（2）遺傳算法搜索：對每一代種群進(jìn)行選擇、交叉和變異等操作，生成下一代種群。（3）模擬退火搜索：對各代種群中的高質(zhì)量個體應(yīng)用模擬退火算法進(jìn)行局部搜索，得到優(yōu)化的路由節(jié)點(diǎn)放置方案。5.實(shí)驗(yàn)結(jié)果本文將所提出的方法與基于粒子群優(yōu)化算法、蟻群算法、模擬退火算法和遺傳算法的其他方法進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，本文所提出的方法在效率上和準(zhǔn)確度上都優(yōu)于其他基準(zhǔn)算法。例如，在1000個節(jié)點(diǎn)的網(wǎng)絡(luò)環(huán)境下，所提出的方法可以在幾秒鐘內(nèi)產(chǎn)生一個優(yōu)秀的解。同時，本文所提出的算法能夠有效地處理大規(guī)模的問題，具有很好的可擴(kuò)展性。6.結(jié)論本文針對無線Mesh網(wǎng)絡(luò)中的路由節(jié)點(diǎn)放置問題，提出了一種基于模擬退火遺傳算法的求解方法，并進(jìn)行了實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，所提出的方法在效率上和準(zhǔn)確