改進(jìn)智能算法的認(rèn)知無線Mesh網(wǎng)絡(luò)優(yōu)化頻譜分配算法

常遠(yuǎn)，謝紅，解武

哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱 150001

改進(jìn)智能算法的認(rèn)知無線Mesh網(wǎng)絡(luò)優(yōu)化頻譜分配算法

常遠(yuǎn)，謝紅，解武

哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱 150001

隨著網(wǎng)絡(luò)資源日益緊張，認(rèn)知無線Mesh網(wǎng)絡(luò)中的頻譜優(yōu)化分配問題的研究主要集中在總帶寬的最大化和占用頻譜數(shù)的最小化。文中考慮到雜草算法的多樣性以及容易實(shí)現(xiàn)和編碼快捷等特點(diǎn)，提出一種基于改進(jìn)入侵雜草優(yōu)化算法（IWO）的頻譜優(yōu)化分配方法（IIOW）。通過對擴(kuò)散條件中調(diào)和指數(shù)的優(yōu)化，使得擴(kuò)散更加均勻準(zhǔn)確，大大加快收斂速度，同時優(yōu)化了適應(yīng)度函數(shù)的曲線。仿真結(jié)果表明：基于改進(jìn)IWO的優(yōu)化算法能在最大化總帶寬與最小化信道占用數(shù)的情況下，獲得較為理想的適應(yīng)度函數(shù)曲線，同時加快收斂速度。

認(rèn)知無線Mesh網(wǎng)絡(luò)；頻譜優(yōu)化；改進(jìn)入侵雜草優(yōu)化算法；調(diào)和指數(shù)優(yōu)化；收斂速度

隨著人們對于網(wǎng)絡(luò)帶寬、傳輸速度以及大容量數(shù)據(jù)交換需求的日益擴(kuò)大，傳統(tǒng)的具有組網(wǎng)靈活、網(wǎng)絡(luò)覆蓋率高、網(wǎng)絡(luò)容量高、前期投入少等優(yōu)勢的無線Mesh網(wǎng)絡(luò)已經(jīng)不能滿足現(xiàn)實(shí)的要求。將認(rèn)知無線電（cognitive radio，CR）技術(shù)與無線Mesh網(wǎng)絡(luò)（wire-lessmesh net，WMN）相結(jié)合而成的一種新型無線網(wǎng)絡(luò)-認(rèn)知無線Mesh網(wǎng)絡(luò)（cognitive wirelessmesh net，CWMN）［1］，使得無線Mesh網(wǎng)絡(luò)的節(jié)點(diǎn)具有在其具有認(rèn)知能力、自組織能力、可重配置能力，這使得CWMN具有感知環(huán)境、分析和學(xué)習(xí)感知到的信息和適應(yīng)環(huán)境的能力，從而能夠更好地滿足大眾的需求。

頻譜分配是認(rèn)知無線Mesh網(wǎng)絡(luò)中的重要研究內(nèi)容，目前對于CWMN的研究仍處于初級階段，面臨許多困難與挑戰(zhàn)。針對CWMN的頻譜分配問題，大多數(shù)的研究基于線性規(guī)劃的方法求解。文獻(xiàn)［2］通過將認(rèn)知無線電技術(shù)加入到無線Mesh網(wǎng)絡(luò)，提出了認(rèn)知無線Mesh網(wǎng)絡(luò)，提高其在資源利用率的性能。針對認(rèn)知無線Mesh網(wǎng)絡(luò)中功率分配問題，文獻(xiàn)［3］提出了一種非合作博弈的方案。針對基于OFDMA的認(rèn)知無線Mesh網(wǎng)絡(luò)的資源分配問題，文獻(xiàn)［4］提出了以最大化端到端速率為目標(biāo)的資源分配的算法。針對無線Mesh中的線性規(guī)劃問題，文獻(xiàn)［5］提出了基于字典序最大最小公平性模型的解決方案，以公平性為目標(biāo)，并定義了2個公平性帶寬分配問題。針對多射頻認(rèn)知無線Mesh網(wǎng)絡(luò)的架構(gòu)問題，文獻(xiàn)［6］提出了Urban-X這一新型構(gòu)架。為使認(rèn)知無線Mesh網(wǎng)絡(luò)與其他認(rèn)知無線網(wǎng)絡(luò)能夠更好地共存，以最小化占用頻譜數(shù)為目標(biāo)，文獻(xiàn)［7］提出了認(rèn)知無線Mesh網(wǎng)絡(luò)中的頻譜分配算法。為使Mesh客戶端的數(shù)量最大化，并用線性規(guī)劃方法求解頻譜分配，文獻(xiàn)［8］提出了一個基于接收器可調(diào)的頻譜分配算法。文獻(xiàn)［9］針對認(rèn)知用戶的動態(tài)性，提出一種基于系統(tǒng)效用穩(wěn)定、減少頻譜重分配的認(rèn)知節(jié)點(diǎn)數(shù)的頻譜分配算法，簡化了動態(tài)頻譜重分配的復(fù)雜度。文獻(xiàn)［10］基于授權(quán)頻譜空閑時間和認(rèn)知用戶請求時間的時間差，提出一種基于時間差因子的改進(jìn)頻譜分配算法，降低認(rèn)知用戶通信中斷概率，提高系統(tǒng)穩(wěn)定性。

已有的基于CWMN的研究不能在優(yōu)化頻譜的同時對帶寬進(jìn)行優(yōu)化。本文基于CR-Mesh路由器以及CR-Mesh網(wǎng)關(guān)，針對感知后的可用頻譜，全面考慮頻譜分配時總帶寬的最大化和占用頻譜數(shù)的最小化；采用包括信道可用用戶在相應(yīng)信道的可用概率、穩(wěn)定度、信道帶寬這些因素進(jìn)行量化；利用入侵雜草算法在較少迭代次數(shù)就顯示出優(yōu)于其他傳統(tǒng)算法的優(yōu)勢的特點(diǎn)，本文針對頻譜優(yōu)化這一課題采用入侵雜草算法。盡管入侵雜草算法這一較新的智能算法已在傳統(tǒng)智能算法之上有了相當(dāng)大的改進(jìn)，但其迭代時間較長，尤其是在一些復(fù)雜程序的問題上，基于此，本文對擴(kuò)散條件進(jìn)行改進(jìn)，意在加快收斂速度并優(yōu)化適應(yīng)度函數(shù)曲線，提出IIWO算法，使得雜草算法的優(yōu)勢得以展現(xiàn)。

1 網(wǎng)絡(luò)模型及問題描述

1.1 網(wǎng)絡(luò)模型

在一個認(rèn)知無線Mesh網(wǎng)絡(luò)的授權(quán)信道中，隨機(jī)分布著主用戶PU（primary user）、次用戶SU（sec-ondary user）、CR-Mesh路由器和CR-Mesh網(wǎng)關(guān)節(jié)點(diǎn)。每一個PU都有一個以其為中心的1個圓形覆蓋區(qū)域。在此區(qū)域內(nèi)，PU所占用的信道，SU不能使用，反之亦然。本文主要研究的是這種被稱為交叉共享接入的overlay方式下的信道分配問題。

將認(rèn)知無線Mesh網(wǎng)絡(luò)建模表示為1個簡單圖G＝（V，E）。V表示主用戶集合。E表示認(rèn)知網(wǎng)關(guān)和認(rèn)知路由器。V中每個元素vi有一個感知可用信道集合Ki，Ii個可用認(rèn)知射頻接口，表示總的可用信道的集合，ψi，j表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj相同的可用信道集合。每個節(jié)點(diǎn)vi∈V均存在1個通信距離TR和1個干擾距離IR。在一般情況下，有3 TR＞IR＞TR，本文假設(shè)IR＝2TR。di，j表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj之間的物理距離。

所有節(jié)點(diǎn)假設(shè)采用半雙工方式工作，存在一個公共信道，并且假設(shè)存在一個頻譜分配服務(wù)器負(fù)責(zé)為CR-Mesh節(jié)點(diǎn)分配頻譜。

1.2 問題描述

主用戶的頻譜只有空閑與占用2種狀態(tài)，在相同考察時間內(nèi)，在頻譜占用率相同情況下，跳表次數(shù)多的情況穩(wěn)定度不高；穩(wěn)定度相同（即跳變次數(shù)相同）情況下，頻譜占用率與主用戶可用性成正比，而與次用戶的可用性成反比。

因而在這里，考慮2個參量：

1）頻譜占用度Pi。即每個主用戶在相應(yīng)信道上的可用概率。在算法中可以用一個M×N階可用概率矩陣表示，M表示主用戶數(shù)量，N表示考察時間個數(shù)，矩陣中的元素為0或者1，為0時，表示此主用戶在相應(yīng)信道上是不可用的，表示為E（p）＝0，p為相應(yīng)考察時間內(nèi)所考察的信道；為1時，表示其在相同信道上是可用的，表示為E（p）＝1可用概率計算方法如式（1）：

2）信道穩(wěn)定度Si（i表示某個考察主用戶）。即主用戶在考察信道上的由空閑跳變到占用的跳變（即由0～1）次數(shù)Hi（i表示某個考察主用戶）。信道占用率體現(xiàn)的是此用戶在考察期間保持信道占用的穩(wěn)定程度。信道占用率定義如式（2）：

2 入侵雜草算法的頻譜分配算法

2.1 基本入侵雜草算法

入侵性雜草優(yōu)化算法（invasive weed optimiza-tion，IWO）是伊朗德黑蘭大學(xué)的A.R.Mehrabian和C.Lucas［11］受雜草啟發(fā)而首次提出的一種基于種群的數(shù)值優(yōu)化計算方法，廣泛應(yīng)用于模式識別、自動控制、機(jī)械設(shè)計、數(shù)據(jù)挖掘、決策分析等諸多領(lǐng)域。入侵雜草優(yōu)化算法的基本步驟主要有4個步驟：

1）初始化雜草種群

設(shè)置種群個體數(shù)、最大種群個體數(shù)、迭代次數(shù)、所要解決的問題維數(shù)、最大種子數(shù)、最小種子數(shù)、調(diào)和指數(shù)、方差的最大值和最小值、問題解的最大最小范圍。

2）種子的生長和繁殖

產(chǎn)生雜草種群的種子，種子數(shù)量如公式（3）：

式中：σiter是第iter次迭代時的標(biāo)準(zhǔn)差值，σinitial是起始標(biāo)準(zhǔn)差值，σfinal是最終標(biāo)準(zhǔn)差值，最大的迭代次數(shù)用itermax來表示，n是調(diào)和指數(shù)。

4）競爭排除

每次生長完成后都要將適應(yīng)度函數(shù)值最差的個體去除，保持種群大小不變。

2.2 改進(jìn)策略

用動態(tài)標(biāo)準(zhǔn)差作為更新的步長，是雜草算法區(qū)別于其他算法的優(yōu)勢所在，σiter伴隨著迭代次數(shù)iter發(fā)生改變，算法的前期和中期，對優(yōu)秀個體周圍的空間搜索頻率較快，以防陷入局部最小值；到了后期，隨著iter的增加，σiter愈來愈小，搜索的范圍愈縮愈縮小，有利于提高算法的精度，找到最優(yōu)解。但在以往傳統(tǒng)的入侵雜草算法中的n是固定不變的，通常設(shè)定為一個常數(shù)，這使得σiter在每次更新時的動態(tài)可擴(kuò)展性不強(qiáng)，沒有充分發(fā)揮其在收斂問題上的優(yōu)勢，本文對于n做了相應(yīng)調(diào)整，使其按照式（5）、（6）進(jìn)行更新調(diào)整。

式中：Nseed表示產(chǎn)生的種子數(shù)，f表示適應(yīng)度函數(shù)值。個體適應(yīng)度值與產(chǎn)生種子數(shù)成線性關(guān)系。fmax為種群最大的適應(yīng)度值，fmin則代表種群最小適應(yīng)度值；Smax、Smin分別代表最大、最小種子數(shù)，一般Smin＝1，Smax＝5足以解決絕大部分最優(yōu)化問題。

3）種子的空間擴(kuò)散

對于每個個體產(chǎn)生的所有種子，按照其父代為基準(zhǔn)（也就是均值），產(chǎn)生正態(tài)分布隨機(jī)數(shù)以正態(tài)分布的方式將種子擴(kuò)散到維空間中去，標(biāo)準(zhǔn)差的更新公式如式（4）：

本文設(shè)置n的初值為Xmax／15（Xmax為搜索范圍的最大值），nmin＝0.03，iter為當(dāng)前迭代次數(shù)，S范圍為［1，15］。

2.3 適應(yīng)度函數(shù)

本文主要研究以最大化總帶寬和最小化占用頻譜數(shù)的情況下，以較快的收斂速度找到適應(yīng)度函數(shù)的最優(yōu)解。對任意粒子i，定義其適應(yīng)度函數(shù)為F（i），如式（9）?？値払指的是所有CR-Mesh節(jié)點(diǎn)獲得的帶寬總和。其中E（li，j）表示信道是否分配無線鏈路li，j。記b1表示無線鏈路li，j在信道的帶寬，其大小是由信道的特征決定的，一般取0～10之間的數(shù)。Si表示某考察用戶的頻譜穩(wěn)定度；Pi表示頻譜占用率。H表示為頻譜占用次數(shù)，θ（i）表示所有考察時間內(nèi)的0的個數(shù)。粒子的適應(yīng)度值越大，表示其被選中的可能性越大，本文的目標(biāo)是希望找到適應(yīng)度值最大的粒子。

2.4 改進(jìn)雜草算法

1）初始化種群，對調(diào)和指數(shù)按式（5）、（6）進(jìn)行優(yōu)化，對其他相關(guān)實(shí)驗參數(shù)進(jìn)行設(shè)定。

2）按照式（6）～（9）計算初始種群適應(yīng)度函數(shù)f（i），對其升序排列。

3）按照式（3）計算每個個體能產(chǎn)生的種子數(shù)。

4）產(chǎn)生新個體，與父代相加，組成新種群，若新種群超出設(shè)定的最大種群個體數(shù)，則去除適應(yīng)度函數(shù)較小的且超出種群限定范圍的個體，否則跳到5）；

5）若達(dá)到最大迭代次數(shù)，算法終止，否則回到步驟2）繼續(xù)執(zhí)行算法。

3 性能仿真及結(jié)果分析

實(shí)驗采用MATLAB R2010a軟件進(jìn)行仿真，在Intel（R）Celeron（R）CPU 2.60 GHz，2 GB內(nèi)存，Windows Xp系統(tǒng)的計算機(jī)上運(yùn)行。采用PSO和改進(jìn)IIWO的方法對本實(shí)驗進(jìn)行仿真對比。

假設(shè)仿真的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為某高校的校園網(wǎng)，在2 500m×2 500 m的區(qū)域，存在若干主用戶以及若干可用信道，主用戶隨機(jī)的占用這些可用信道。在該區(qū)域部署著具有認(rèn)知能力的Mesh路由器。Mesh路由器節(jié)點(diǎn)的傳輸范圍為50 m，并且均勻部署在區(qū)域內(nèi)。

以下實(shí)驗結(jié)果均為50次獨(dú)立仿真結(jié)果的均值。性能的比較主要包括系統(tǒng)總帶寬、占用的信道數(shù)目2個方面，占用信道數(shù)越多，表示其他認(rèn)知無線網(wǎng)絡(luò)可用的信道數(shù)越少。假設(shè)各信道的帶寬屬于［0，10］，并且隨機(jī)產(chǎn)生，考察信道帶寬b隨機(jī)產(chǎn)生，取值在0～10之間；主認(rèn)知用戶數(shù)為6，可用頻帶數(shù)為8。

實(shí)驗主要由以下2方面進(jìn)行仿真：

1）對參數(shù)a，b、節(jié)點(diǎn)數(shù)N和可用信道數(shù)K進(jìn)行分析仿真，得到使得算法性能最佳的值。

2）使用在1）中得到的參數(shù)數(shù)值，對調(diào)和指數(shù)的改進(jìn)進(jìn)行仿真對比，對迭代時間進(jìn)行記錄，得出結(jié)論。

3.1 參數(shù)對算法性能的影響分析

根據(jù)文獻(xiàn)［12］對于參數(shù)a，b的描述，設(shè)定a＝0.6，b＝0.4。

1）可用信道數(shù)｜K｜對基于IIWO算法的性能影響。用戶數(shù)M的范圍為［21，51］，間隔為10，頻譜數(shù)N的范圍為［1，M］。|K| 取值范圍設(shè)為［0，30］，迭代4次。

由圖1可知，隨著|K| 值的增大，目標(biāo)函數(shù)值隨之增大，但是并不隨著M，N的增大而增大，由圖可知當(dāng)M，N在取值范圍［31，41］之間時目標(biāo)函數(shù)曲線較為理想。

圖1 可用信道數(shù)K與目標(biāo)函數(shù)的關(guān)系

2）可用頻譜數(shù)N對基于IIWO算法的性能影響?？捎眯诺罃?shù)｜K｜＝10，a＝0.6，b＝0.4，M取值35，N取值范圍為［1，50］，圖迭代50次。分別仿真了變量N對總帶寬曲線和信道占用數(shù)曲線的影響，仿真圖如圖2、3。

由圖2可知，隨著N增大，總帶寬變大，并有緩慢下降的趨勢。由圖3可知，N在0～25之間時，信道占用數(shù)基本不變，并且震蕩較不穩(wěn)定，且有下降趨勢；N在25～50之間時，信道占用數(shù)曲線較理想，趨于平衡。

圖2 種群大小N與總帶寬B的關(guān)系

圖3 種群大小N與信道占用數(shù)K關(guān)系

3.2 改進(jìn)算法的優(yōu)化結(jié)果

在調(diào)和指數(shù)按照式（5）、（6）改進(jìn)后，所得適應(yīng)度函數(shù)值隨迭代次數(shù)的變化曲線與應(yīng)用粒子群算法的適應(yīng)度函數(shù)曲線圖的對比如圖4所示。改進(jìn)前算法收斂時間為1.259 088 s，改進(jìn)后，算法收斂速度為1.082 003 s，最優(yōu)值為0.802 311。由此可見，基于改進(jìn)的IIWO算法確實(shí)加快了算法的收斂速度，曲線也得到了有效改善。

圖4 適應(yīng)度函數(shù)最優(yōu)值與迭代次數(shù)的關(guān)系

4 結(jié)論

1）利用IWO算法種群多樣化的優(yōu)勢，提出了基于IIWO的網(wǎng)絡(luò)優(yōu)化頻譜分配算法。綜合考慮同時獲得最大系統(tǒng)總帶寬和最小化占用信道數(shù)的情況下，對調(diào)和函數(shù)進(jìn)行改進(jìn)，有效提高了算法的收斂速度，并獲得較為理想的目標(biāo)函數(shù)曲線。

2）通過合理的參數(shù)設(shè)置，在獲得高的系統(tǒng)總帶寬和較少頻譜占用數(shù)的情況下，通過改進(jìn)雜草算法和粒子群算法對方案的實(shí)現(xiàn)進(jìn)行對比，本文所提出的IIWO算法對適應(yīng)度函數(shù)有明顯的改進(jìn)。

因此，采用本文提出的IIWO算法在保證高的系統(tǒng)總帶寬并且占用較少頻譜的情況下，同時達(dá)到了加快收斂速度和改善適應(yīng)度曲線的效果。

［1］仵國鋒，季仲梅，張靜，等.認(rèn)知無線Mesh網(wǎng)絡(luò)［J］.信息工程大學(xué)學(xué)報，2010，11（4）：429-433.

［2］LEE D H，JEONW S，JEONG D G.Joint channel assign-ment androuting in cognitive radio-based wireless meshnet-works［C］／／IEEE Vehicular Technology Conference.Otta-wa，Canada，2010：1-5.

［3］ZHANG Jianmin，ZHANG Zhaoyang，LUO Haiyan.Joint-subchannel，rate and power allocateion in OFDMA-based-cognitive wireless mesh network［J］.Wireless Personal Communications，2009，58（3）：1478-1487.

［4］AlMASAEID H M，KAMAL A E.Receiver-based channel allocation for wireless cognitive radio mesh networks［C］／／2010 IEEE Symposium on New Frontiers in Dynamic Spec-trum，DYSPAN2010.Singapore，2010：1-5.

［5］TANG Jian，HINCAPIéR，XUE Guoliang，et al.Fair bandwidth allocation in wirelessmesh networks with cogni-tive radios［J］.IEEE Transactions on Vehicular Technolo-gy，2010，59（3）：1487-1496.

［6］WOOSEONG K，KASSLER A K，DIFM，et al.Urban-X：towards distributed channel assignment in cognitivemulti-ra-diomesh networks［C］／／2010 IFIPWireless Days.［S.l.］，2010：1-5.

［7］YONG Ding，LIXiao.Channel allocation in multi-channel wireless mesh networks［J］.Computer Communications，2011，34（7）：803-815.

［8］BOUABDALLAH N，ISHIBASHI B，BOUTABA R.Per-formance of cognitive radio-based wireless mesh networks ［J］.IEEE Transactions on Mobile Computing，2011，10 （1）：122-135.

［9］李一兵，楊蕊，高振國.基于著色理論的認(rèn)知無線電頻譜分配算法［J］.系統(tǒng)工程與電子技術(shù)，2010，32（6）：1109-1112.

［10］文凱，傅小玲，付玲生.認(rèn)知無線電中基于時間差因子的頻譜分配算法［J］.計算機(jī)應(yīng)用，2011，31（5）：1173-1175.

［11］MITOLA J.Cognitive radio：making software radio more personal［J］.IEEE Personal Commnuication，1999，6 （4）：13-18.

［12］鄺祝芳.認(rèn)知無線Mesh網(wǎng)絡(luò)中一種有效的多目標(biāo)優(yōu)化頻譜分配算法》［J］.中南大學(xué)學(xué)報，2013（6）：73-75.

Spectrum allocation optim ization algorithm based on
improved intelligence algorithm in cognitive w ireless M esh networks

CHANG Yuan，XIE Hong，XIEWu
College of Information and Communication Engineering，Harbin Engineering University，Harbin 150001，China

As resources of networks become increasingly tight，the research on the spectrum allocation optimization of cognitive wirelessmesh networks focuses on maximization of the total bandwidth and minimized number of spec-trum occupation.This paper proposed an improved algorithm for spectrum allocation based on invasiveweed optimi-zation（IWO）after considering such characters as the diversity of theweed algorithm，easy realization and fast cod-ing.By optimizing the harmonic index in diffusion conditions，the diffusion becomesmore even and accurate，the convergence speed becomes faster；in addition，the curve of the fitness function is optimized.Simulation results show that the optimization algorithm based on improved IWO can realize ideal fitness function and speed up conver-gence speed under the conditions ofmaximizing the total bandwidth and minimizing the number of occupied chan-nels.

cognitive wireless Mesh network；spectrum optimization；improved invasive weed optimization algo-rithm；optimization of harmonic index；convergence rate

TN911

A

1009-671X（2015）02-24-05

10.3969／j.issn.1009-671X.201405017

2014-05-20.

日期：2015-03-25.

黑龍江省自然科學(xué)基金資助項目（F201339）.

常遠(yuǎn)（1989-），女，碩士研究生；

謝紅（1962-），女，教授，博士生導(dǎo)師.

常遠(yuǎn)，E-mail：466959339＠qq.com.

http：／／www.cnki.net／kcms／detail／23.1191.u.20150325.1300.014.html