【摘 要】提出基于模擬退火算法的WLAN組網(wǎng)信道選擇算法，仿真結(jié)果表明采用此算法進行信道選擇是行之有效的。

【關(guān)鍵詞】模擬退火算法 信道選擇

一、引言

無線通信技術(shù)為人們生活帶了便利和高效率。作為傳統(tǒng)有線網(wǎng)絡(luò)的一種替代方案和延伸，無線通信技術(shù)用無線空口替代網(wǎng)線，把人們固定有線接入解放出來，隨時隨地方便的獲取信息和提供娛樂。隨著智能手機和Pad的大規(guī)模普及，基于移動智能終端的數(shù)據(jù)業(yè)務(wù)爆發(fā)式增長，傳統(tǒng)運營商采用的2G/3G宏基站網(wǎng)絡(luò)無法支持移動互聯(lián)網(wǎng)海量數(shù)據(jù)流量，移動運營商開始關(guān)注利用微基站接入點作為容量吸收層承載數(shù)據(jù)業(yè)務(wù)。微基站接入點包括家庭用Femto、WLAN等。在國內(nèi)，中國電信、中國移動、中國聯(lián)通自2008年以來都大范圍的部署和推廣微蜂窩接入點，將其作為現(xiàn)有無線網(wǎng)絡(luò)的補充，吸收容量。微蜂窩由于數(shù)量眾多，部署場景千差萬別，微蜂窩與宏蜂窩的差別之一就是要能夠?qū)崿F(xiàn)自動的頻段規(guī)劃，否則依靠人工規(guī)劃部署，巨大的工作量將導(dǎo)致不可能進行實際部署。

二、數(shù)學(xué)建模和求解

運營商部署WLAN網(wǎng)絡(luò)面臨的一個重要問題就是，如何進行WLAN網(wǎng)絡(luò)頻率資源的規(guī)劃，頻譜規(guī)劃的好壞關(guān)系到網(wǎng)絡(luò)的性能。簡單的說為了網(wǎng)絡(luò)獲取更好的性能，頻率規(guī)劃的原則應(yīng)該使得相鄰微基站盡量使用不同的頻點盡量錯開，整個網(wǎng)絡(luò)的平均干擾水平最小。

以WLAN微蜂窩為例，WLAN一般使用20MHz工作帶寬，工作在2.4GHz和5GHz頻段非授權(quán)頻譜。在2.4GHz頻段WLAN有3個不重疊的20MHz信道，信道之間相互不會干擾。

為了使得問題具有通用性，假設(shè)有N個相互不干擾的工作頻點，N為確定常數(shù)。在一定區(qū)域內(nèi)要部署M個微基站接入點，最終求解是使得M個AP形成的網(wǎng)絡(luò)性能最好，即干擾最小。在第n個頻點工作的PAni對PAnj的干擾為。這個問題就變成求解最小。這是個問題可歸結(jié)為一個數(shù)學(xué)上的NP問題。使用窮舉求解這個問題，需要的實驗次數(shù)為M^N，即求解該問題的復(fù)雜度O（M^N）。

通過窮舉遍歷試驗可以求得NP問題的最優(yōu)解，但一般情況下，遍歷的復(fù)雜度即實驗時間往往會是一個天文數(shù)字，使得實際中根本無法通過這種方法獲得最優(yōu)解。爬山算法是一種局部最優(yōu)化解，其復(fù)雜度為線性，但往往會導(dǎo)致只搜索到局部最優(yōu)解。爬山算法是一種簡單的貪心搜索算法，該算法每次從當(dāng)前解的臨近解空間中選擇一個最優(yōu)解作為當(dāng)前解，直到達到一個局部最優(yōu)解。爬山算法實現(xiàn)很簡單，其主要缺點是會陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解。1989 年 Johnson 等人通過詳盡的實驗證實了采用模擬退火算法求解NP問題的優(yōu)點。爬山法每次都選擇一個當(dāng)前局部最優(yōu)解，因此只能搜索到局部的最優(yōu)值。模擬退火在搜索過程引入了隨機因素，以一定的概率來接受一個比當(dāng)前解要差的解，所以可能會跳出這個局部的最優(yōu)解，到達全局最優(yōu)解。模擬退火算法在搜索到局部最優(yōu)解后，會以一定的概率接受到非局部最優(yōu)的移動。也許經(jīng)過幾次這樣的不是局部最優(yōu)的移動后會跳出了局部最優(yōu)向全局最優(yōu)方向進行搜索。

模擬退火算法基本思想和過程如下：

假設(shè)代價函數(shù)為J（Y），第i次迭代過程代價函數(shù)為J（Y（i））；

若J（ Y（i+1） ）>= J（ Y（i） ），即移動后得到更優(yōu)解，則總是接受該移動；

若J（ Y（i+1） ）< J（ Y（i） ），即移動后的解比當(dāng)前解要差，則以一定的概率接受移動，而且這個概率隨著時間推移逐漸降低，以使得該過程收斂。

這里的“一定的概率”計算參考了金屬冶煉的退火過程，這也是模擬退火算法名稱的由來。根據(jù)熱力學(xué)的原理，在溫度為T時，出現(xiàn)能量差為dE的降溫的概率為P（dE），表示為，P（dE） = exp（ dE/（kT） ）。

其中k是一個常數(shù)，exp表示自然指數(shù)，且dE<0。這條公式說明：溫度越高，出現(xiàn)一次能量差為dE的降溫的概率就越大；溫度越低，則出現(xiàn)降溫的概率就越小。又由于dE總是小于0，因此dE/kT < 0 ，所以P（dE）的函數(shù)取值范圍是（0，1） 。隨著溫度T的降低，P（dE）會逐漸降低。將一次向較差解的移動看做一次溫度跳變過程，以概率P（dE）來接受這樣的移動，最終搜索得趨向于最優(yōu)解。

假設(shè)在1000平方米區(qū)域隨機布放200個接入點，有4個可用信道頻率。使用窮舉法，需要進行200^4=1.6x10^9次試驗。

使用模擬退火算法，構(gòu)建代價函數(shù)，

其中，代表工作在第n個頻點的PAni對PAnj的干擾。

通過仿真證明，使用模擬退火算法能夠以較小的復(fù)雜度得到與窮舉法幾乎一致的最優(yōu)解。

三、總結(jié)

本文分析了WLAN頻率規(guī)劃中的數(shù)學(xué)問題，歸結(jié)為NP問題求解，證明了模擬退火算法解決這一類問題的實際可行性。

參考文獻：

[1]Optimization by Simulated Annealing： An Experimental Evaluation； Part I， Graph Partitioning， David S. Johnson， Cecilia R. Aragon， Lyle A. McGeoch， Catherine Schevon；

[2]模擬退火算法與遺傳算法的結(jié)合，王雪梅，王義和， 《計算機學(xué)報》1997年04期；

[3]新型遺傳模擬退火算法求解物流配送路徑問題， 閻慶， 鮑遠律， 計算機應(yīng)用 2004年z1期；

[4]一種屬性約簡的探測性貪婪算法，李 旻， 陳衛(wèi)東， 計 算 機 工 程2012年10月第38卷第19期；

[5]基于模擬退火算法的布局問題研究，張和君，張 躍， 計算機工程與設(shè)計，2006年6月， 第27卷第11期；