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

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