常遠，謝紅，解武

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

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

常遠，謝紅，解武

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

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

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

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

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

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

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

1.1 網(wǎng)絡模型

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

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

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

1.2 問題描述

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

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

1）頻譜占用度Pi。即每個主用戶在相應信道上的可用概率。在算法中可以用一個M×N階可用概率矩陣表示，M表示主用戶數(shù)量，N表示考察時間個數(shù)，矩陣中的元素為0或者1，為0時，表示此主用戶在相應信道上是不可用的，表示為E（p）＝0，p為相應考察時間內(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）是伊朗德黑蘭大學的A.R.Mehrabian和C.Lucas［11］受雜草啟發(fā)而首次提出的一種基于種群的數(shù)值優(yōu)化計算方法，廣泛應用于模式識別、自動控制、機械設計、數(shù)據(jù)挖掘、決策分析等諸多領域。入侵雜草優(yōu)化算法的基本步驟主要有4個步驟：

1）初始化雜草種群

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

2）種子的生長和繁殖

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

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

4）競爭排除

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

2.2 改進策略

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

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

3）種子的空間擴散

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

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

2.3 適應度函數(shù)

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

2.4 改進雜草算法

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

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

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

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

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

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

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

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

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

實驗主要由以下2方面進行仿真：

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

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

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

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

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

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

圖1 可用信道數(shù)K與目標函數(shù)的關系

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的關系

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

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

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

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

4 結(jié)論

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

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

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

［1］仵國鋒，季仲梅，張靜，等.認知無線Mesh網(wǎng)絡［J］.信息工程大學學報，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］李一兵，楊蕊，高振國.基于著色理論的認知無線電頻譜分配算法［J］.系統(tǒng)工程與電子技術，2010，32（6）：1109-1112.

［10］文凱，傅小玲，付玲生.認知無線電中基于時間差因子的頻譜分配算法［J］.計算機應用，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］鄺祝芳.認知無線Mesh網(wǎng)絡中一種有效的多目標優(yōu)化頻譜分配算法》［J］.中南大學學報，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.

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

常遠（1989-），女，碩士研究生；

謝紅（1962-），女，教授，博士生導師.

常遠，E-mail：466959339＠qq.com.

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