漁夫捕魚優(yōu)化算法的認知無線電頻譜分配

項響琴，張滬寅

1.合肥學(xué)院網(wǎng)絡(luò)與智能信息處理重點實驗室，合肥 230601

2.武漢大學(xué)計算機學(xué)院，武漢 430072

漁夫捕魚優(yōu)化算法的認知無線電頻譜分配

項響琴1，張滬寅2

1.合肥學(xué)院網(wǎng)絡(luò)與智能信息處理重點實驗室，合肥 230601

2.武漢大學(xué)計算機學(xué)院，武漢 430072

針對認知無線電系統(tǒng)中認知用戶頻譜分配問題，提出一種基于漁夫捕魚優(yōu)化算法（SFOA）的頻譜分配算法。以系統(tǒng)效益最大化為優(yōu)化目標(biāo)，建立認知無線電頻譜分配優(yōu)化的數(shù)學(xué)模型，采用設(shè)置參數(shù)少、易于編碼實現(xiàn)、尋優(yōu)能力強的漁夫捕魚優(yōu)化算法對模型進行求解，得到空閑頻譜最優(yōu)分配方案，在Matlab 2012平臺上進行仿真實驗。結(jié)果表明，SFOA不僅提高了用戶平均系統(tǒng)效益，而且提高了頻譜分配效率。

認知無線電；頻譜分配；漁夫捕魚優(yōu)化算法；移動和收縮搜索

1 引言

隨著無線通信技術(shù)迅速發(fā)展，無線用戶的數(shù)量急劇增加，頻譜資源短缺和頻譜利用不均衡現(xiàn)象日益嚴重。為了解決頻譜資源日益緊張和由于固定頻譜分配造成的頻譜利用率低的問題，Joseph Mitola在軟件無線電的基礎(chǔ)上提出了認知無線電（Cognitive Radio，CR）的概念。認知無線電可以在不影響用戶正常通信的條件下，能夠合理利用頻譜空穴，提高頻譜利用率，因此如何合理、有效利用空閑頻譜，具有十分重要的現(xiàn)實意義[1]。

頻譜分配必須保證其靈活性，由于頻譜信息的不斷更新，相應(yīng)的頻譜分配算法也必須滿足實時性的要求。針對認知無線電頻譜分配問題，已有許多學(xué)者進行了相關(guān)研究，提出了不同的頻譜分配算法，主要包括博弈論、圖論著色、議價機制、拍買理論等[2-5]。相對于議價機制、博弈論、拍買理論，基于圖論著色理論的頻譜分配算法可以提高頻譜利用率，計算復(fù)雜度較低，但是其存在不公平性、貧困用戶等缺點[6]。近年來，有學(xué)者把認知無線電頻譜分配問題轉(zhuǎn)化成為一個優(yōu)化問題，然后采用群智能算法進行求解，出現(xiàn)了基于量子遺傳算法，離散人工蜂群算法，差分進化算法，二進制粒子群優(yōu)化算法和混合蛙跳算法等無線電頻譜分配算法[7-11]，這些算法通過模擬自然界生物行為，實現(xiàn)信息交流和共享，提高了頻譜利用率，實現(xiàn)了認知用戶間的公平性。但這些算法都存在各自的不足，如易陷入局部最優(yōu)等[12]。因此，需要引入新的算法來解決認知無線電頻譜分配問題。漁夫捕魚算法（Optimization Algorithm on Simulating the Fisher Fishing，SFOA）是模擬漁夫捕魚行為習(xí)慣而提出的一種新的智能優(yōu)化算法[13]，該算法具有原理簡單、設(shè)置參數(shù)少、易于編碼實現(xiàn)等優(yōu)點，在多目標(biāo)優(yōu)化領(lǐng)域得到了廣泛的應(yīng)用，并取得比其他群智能算法更好的效果，為解決認知無線電頻譜分配問題提供了一種新的研究工具。

為了提高認知無線電頻譜利用率，充分利用SFOA全局尋優(yōu)能力，提出一種基于SFOA的認知無線電頻譜分配算法。首先以系統(tǒng)效益最大化為優(yōu)化目標(biāo)，建立認知無線電頻譜分配優(yōu)化的數(shù)學(xué)模型，然后采用SFOA找到空閑頻譜最優(yōu)分配方案，仿真結(jié)果表明，SFOA可以有效求解認知無線電的頻譜分配問題，使網(wǎng)絡(luò)系統(tǒng)效益達到最大化。

2 認知無線電頻譜分配問題

頻譜分配是根據(jù)需要接入系統(tǒng)的節(jié)點數(shù)目及其服務(wù)要求，將頻譜分配給一個或多個指定節(jié)點，圖1表示的就是對頻譜分配問題的一個簡單描述。

圖1 頻譜分配問題描述

在效益最大化的頻譜分配模型中，由認知用戶構(gòu)成的網(wǎng)絡(luò)拓撲結(jié)構(gòu)可抽象成圖G(V，E，L)，V是頂點集合，一個頂點代表一個認知用戶；E是邊的集合，若兩個認知用戶i，j的干擾范圍不出現(xiàn)重疊，則ei，j=0，否則ei，j=1；L用來表示次用戶的信道可用性。如圖2所示[14]。

認知無線網(wǎng)絡(luò)頻譜分配問題可用信道矩陣、效益矩陣、干擾約束矩陣和分配矩陣描述，它們分別定義如下：

（1）信道的可用矩陣L為：

式中，ln，m=1表示認知用戶n可以使用信道m(xù)；ln，m=0表示認知用戶n不能使用信道m(xù)。

（2）干擾矩陣C為：

圖2 認知無線電系統(tǒng)的模型

當(dāng)認知用戶n和k同時使用信道m(xù)產(chǎn)生干擾，則cn，k，m=1；若認知用戶n和k同時使用信道m(xù)不產(chǎn)生干擾，則cn，k，m=0。

（3）效益矩陣B為：

其中，B表示認知用戶n使用信道m(xù)時所獲得的效益權(quán)重，bn，m=α表示認知用戶n使用信道m(xù)時獲得效用權(quán)重為α；bn，m=0表示認知用戶n不能夠使用信道m(xù)。

（4）無干擾的頻譜分配矩陣A為：

其中，an，m=1表示信道m(xù)被分配給了用戶n；否則an，m=0。

矩陣A必須滿足無干擾限制條件：an，m+ak，m≤1, if cn，k，m=1，?0＜n，k＜N，0＜m＜M。

頻譜分配技術(shù)的主要目的是對可用頻譜空間進行合理的分配，使得系統(tǒng)性能得到改善或逼近于最優(yōu)狀態(tài)，同時必須考慮計算量及復(fù)雜度即效率的問題，因此U越大，分配得到的帶寬收益越大，認知無線電頻譜分配問題定義為：

3 模擬漁夫捕魚優(yōu)化算法

3.1 漁夫捕魚算法的基本思想

漁夫撒網(wǎng)捕魚時，開始時很隨意地選擇江面上一點撒下魚網(wǎng)，然后在當(dāng)前下網(wǎng)點的前后左右各撒一次網(wǎng)，而且漁夫總希望每次撒網(wǎng)能捕捉到盡可能多的魚，而水中魚的密度越大，能捕捉到的魚相應(yīng)就多，因此，漁夫選擇在何處撒網(wǎng)的準則為：（1）哪處魚的密度大，就在哪處下網(wǎng)；（2）何處魚的密度較大，便移到該處撒網(wǎng)；（3）避免在同一地點重復(fù)撒網(wǎng)的現(xiàn)象發(fā)生；（4）若發(fā)現(xiàn)當(dāng)前自己所處的位置魚的密度較大，便收縮撒網(wǎng)范圍，以便達到“一網(wǎng)打盡”。漁夫捕魚算法是一種模擬漁夫捕魚行為的智能優(yōu)化算法。

3.2 漁夫捕魚算法的描述

式中，ε＞0為自定義的較小的常數(shù)，那么i漁夫就快速移動，以便跳出局部捕魚區(qū)域（即避免陷入局部最優(yōu)）。

（4）公告板記錄最優(yōu)漁夫位置，每個漁夫的位置均要與公告板的位置進行比較，若更優(yōu)，便替換公告板中的位置，算法結(jié)束后，公告板值為全局最優(yōu)值。

（5）若某漁夫在某點處收縮搜索次數(shù)達到了最大閾值，但其位置沒有改變，那么漁夫重新隨機選擇一個點進行搜索。

4 SFOA的認知無線電頻譜分配

在L，B，C已知的情況下，如何找到最優(yōu)的無干擾分配矩陣A，使得認知系統(tǒng)效益達到最大化，并盡可能使時間開銷最小[15]。從式（6）可知，認知無線電頻譜分配問題是一個非線性、多目標(biāo)優(yōu)化問題，是一種典型的NP難題，而漁夫捕魚算法是近年解決復(fù)雜NP問題較為理想的方法，因此本文首次將SFOA應(yīng)用到頻譜分配問題中，對公式（6）進行尋優(yōu)，使U最大，使得認知系統(tǒng)效益達到最大化。

4.1 漁夫位置編碼

每一個漁夫位置代表一個潛在的認知無線電頻譜分配方案，漁夫位置初始化根據(jù)無干擾分配矩陣A進行設(shè)計，如果頻譜矩陣L中的ln，m=0，那么矩陣A中的an，m=0，為了降低計算時間開銷，因此選擇L中值為1位置對應(yīng)A中的元素位置進行編碼，對于N=5、M=5的認知無線電頻譜分配問題，漁夫位置編碼方式如圖3所示。

圖3 漁夫位置的編碼方式

4.2 目標(biāo)函數(shù)設(shè)計

認知無線電頻譜分配目標(biāo)是使整個小區(qū)內(nèi)所有認知用戶取得的效益總和最大化，因此采用系統(tǒng)效益作為魚的密度度量函數(shù)（目標(biāo)函數(shù)），即

4.3 SFOA的認知無線電頻譜分配求解步驟

步驟1給定頻譜矩陣L={ln，m|ln，m∈{0，1}N×M，效益矩陣B={bn，m}N×M，干擾矩陣C={cn,k,m|cn,k,m∈{0,1}}N×N×M，L記為1元素對應(yīng)的n與m，即令L={(n，m)|ln，m=1}。

步驟2隨機初始化漁夫的位置，即表示一種可能的頻譜分配策略。

步驟3對初始化漁夫的位置，根據(jù)式（9）評價漁夫的位置優(yōu)劣，并找出當(dāng)前最優(yōu)捕魚位置，在公示板公布。

步驟4漁夫在各自的區(qū)域進行移動搜索，尋找更優(yōu)的捕魚位置。

步驟5如果漁夫找到更優(yōu)的捕魚位置，便進入步驟6，否則回到步驟4繼續(xù)進行移動搜索。

步驟6如果達到收縮操作的閾值CN，便進入到步驟7，不然以最優(yōu)漁夫位置為中心進行收縮搜索。

步驟7與公示板公示的捕魚位置進行比較，如果漁夫位置更優(yōu)，便替代公示板公示的捕魚位置，并返回到步驟6，不然進入步驟8。

步驟8判斷是否滿足算法的最大迭代次數(shù)，若滿足條件，便進入步驟9，不然回到步驟4。

步驟9輸出最優(yōu)捕魚位置對應(yīng)的認知無線電頻譜分配方案，結(jié)束。

基于SFOA的認知無線電頻譜分配算法的工作流程如圖4。

圖4 認知無線電頻譜分配算法的工作流程圖

5 仿真實驗

5.1 仿真環(huán)境及對比算法

為了驗證SFOA的認知無線電頻譜分配算法的效果，在Matlab 2012平臺進行仿真測試，并采用文獻[13]的粒子群優(yōu)化算法（PSO）和文獻[14]的遺傳算法優(yōu)化（GA）進行對比實驗。認知無線電系統(tǒng)的參數(shù)見表1。SFOA參數(shù)設(shè)置為：漁夫個數(shù)K=20，移動搜索閾值N=100，收縮搜索閾值CN=20；PSO算法的參數(shù)為：粒子數(shù)k=20，c1=c2=2，慣性權(quán)重w=0.5；GA的參數(shù)為：個體數(shù)為k= 20，pc=0.9，pm=0.1，所有算法的最大迭代次數(shù)均為500。

表1 仿真參數(shù)

5.2 結(jié)果與分析

5.2.1 收斂速度對比

當(dāng)M=10，N=10時，GA、PSO和SFOA的系統(tǒng)效益變化曲線如圖5所示，從圖5可知，隨著迭代次數(shù)的增加，認知無線電系統(tǒng)效益不斷增加，SFOA在200代左右，系統(tǒng)效益就達到最優(yōu)，即找到了認知無線電頻譜分配的全局最優(yōu)解，而GA、PSO分別在280、300代左右才找到最優(yōu)解，而且系統(tǒng)效益明顯低于SFOA，這表明SFOA的收斂速度要快于GA、PSO，而且找到了比GA、PSO更優(yōu)的無線電系統(tǒng)頻譜分配方案。

圖5 不同算法的收斂速度比較

5.2.2 系統(tǒng)效益與可用頻譜數(shù)之間的變化關(guān)系

在N=10條件下，隨著可用頻譜數(shù)的增加，系統(tǒng)效益的變化趨勢如圖6所示。從圖6可知，隨著可用頻譜數(shù)增加，用戶可以選擇頻譜增多，用戶間干擾減小，系統(tǒng)效益逐漸增加，而且SFOA的頻譜分配算法的系統(tǒng)效益明顯優(yōu)于GA、PSO的系統(tǒng)效益，對比結(jié)果表明，相對于GA、PSO，SFOA可以使系統(tǒng)效益更加最大化。

圖6 系統(tǒng)效益與頻譜數(shù)的變化關(guān)系

5.2.3 系統(tǒng)效益與用戶數(shù)之間的變化關(guān)系

當(dāng)M=20時，隨著用戶數(shù)N變化，系統(tǒng)效益變化趨勢如圖7所示。從圖7可知，隨著N增加，用戶之間的頻譜競爭越來越激烈，用戶之間干擾頻率增加，系統(tǒng)效益慢慢遞減，但是SFOA的頻譜分配算法的系統(tǒng)效益減幅明顯要小于GA、PSO的系統(tǒng)效益。

圖7 N變化時系統(tǒng)效益

5.2.4 網(wǎng)絡(luò)效益與實驗次數(shù)之間的變化關(guān)系

以最大網(wǎng)絡(luò)總效益為目標(biāo)函數(shù)、當(dāng)N=10，M=20時，在不同初始條件下的實驗結(jié)果如圖8所示。不同實驗中B，L，C不同，同一次實驗中GA、PSO、SFOA的頻譜分配算法采用的B，L，C相同。從圖8可知，在大多數(shù)情況下，SFOA的無線電頻譜分配算法獲得的網(wǎng)絡(luò)效益要明顯優(yōu)于GA、PSO獲得的網(wǎng)絡(luò)效益，只有少數(shù)點的網(wǎng)絡(luò)效益相差不大，這說明基于SFOA的無線電頻譜分配算法提高了認知系統(tǒng)的效益，可以較好地滿足認知無線電網(wǎng)絡(luò)頻譜分配要求。

圖8 不同算法的網(wǎng)絡(luò)效益對比

6 結(jié)語

針對認知無線電系統(tǒng)的頻譜分配問題，提出了一種基于SFOA的認知無線電頻譜分配算法，并通過具體仿真實驗測試性能。仿真結(jié)果表明，相對于PSO、GA，SFOA可以找到更優(yōu)的認知無線電系統(tǒng)頻譜分配方案，實現(xiàn)網(wǎng)絡(luò)效益的最大化，可以滿足更廣泛的認知無線電網(wǎng)絡(luò)應(yīng)用需求。

[1]滑楠，曹志剛.認知無線電網(wǎng)絡(luò)路由研究綜述[J].電子學(xué)報，2010，38（4）：910-918.

[2]Rahimi-Vahed A，Mirzaei A H.Solving a bi-criteria permutation flow-shop problem using shuffled frog-leaping algorithm[J].Soft Computing，2008，12（5）：435-452.

[3]寧國勤，張靜.基于時間預(yù)測的多跳頻譜切換算法研究[J].計算機工程與應(yīng)用，2013，49（13）：71-75.

[4]王欽輝，葉保留，田宇，等.認知無線電網(wǎng)絡(luò)中頻譜分配算法[J].電子學(xué)報，2012，40（1）：147-154.

[5]Jie Jia，Wang Chuang，Zhang Zhaoyang，et al.Dynamic spectrum assignment based on graph coloring in cognitive radio network[J].Journal of Northeastern University：Natural Science，2012（3）：336-339.

[6]彭振，趙知勁，鄭仕鏈.基于混合蛙跳算法的認知無線電頻譜分配[J].計算機工程，2010，36（6）：210-217.

[7]柴爭義，劉芳.基于免疫克隆選擇優(yōu)化的認知無線網(wǎng)絡(luò)頻譜分配[J].通信學(xué)報，2010，31（11）：92-100.

[8]知勁，彭振，鄭仕鏈，等.基于量子遺傳算法的認知無線電頻譜分配[J].物理學(xué)報，2009，58（2）：1358-1363.

[9]Chuang Liyeh，Tsai Shengwei，Yang Chenghong.Chaotic catfish particle swarm optimization for solving global numerical optimization problems[J].Applied Mathematics and Computation，2011，217.

[10]Zhao Zhijing，Peng Zheng，Zheng Shilian，et al.Cognitive radio spectrum allocation using evolution algorithms[J]. IEEE Trans on Wireless Communications，2009，8（9）：4421-4425.

[11]唐萬斌，喻火根，李少謙.基于信道預(yù)測的認知無線電混合頻譜切換算法[J].計算機工程與應(yīng)用，2012，48（27）：17-21.

[12]張北偉，朱云龍，胡琨元.基于粒子群算法的認知無線電頻譜分配算法[J].計算機應(yīng)用，2011，32（12）：3184-3214.

[13]王勇，陳建榮，龐興.一種模擬漁夫捕魚的尋優(yōu)算法[J].計算機應(yīng)用研究，2008，26（8）：2888-2890.

[14]朱冰蓮，裴光術(shù)，張磊，等.認知無線電網(wǎng)絡(luò)中系統(tǒng)效益最大化的頻譜分配[J].計算機工程，2012，38（3）：107-109.

[15]肖淑艷，孫茜，衡芹，等.基于D-S理論的認知無線電頻譜感知算法[J].計算機工程與應(yīng)用，2011，47（33）：91-93.

XIANG Xiangqin1,ZHANG Huyin2

1.Key Lab of Network and Intelligent Information Processing,Hefei University,Hefei 230601,China
2.College of Computer,Wuhan University,Wuhan 430072,China

This paper proposes a novel spectrum allocation method of cognitive radio based on Optimization Algorithm on Simulating the Fisher Fishing（SFOA）to solve the spectrum allocation problem of cognitive radio system.Spectrum allocation optimization mathematical model of the cognitive radio is established whose maximum benefit is taken as the optimization goal,and then the optimal spectrum allocation scheme is obtained by SFOA which has less parameters, encodes easily,strong ability.The simulation experiment is carried out to test the performance of SFOA algorithm.The results show that the proposed method not only increases users mean system utility,but also improves the efficiency of spectrum allocation.

cognitive radio;spectrum allocation;Optimization Algorithm on Simulating the Fisher Fishing（SFOA）;moving and diminishing search

A

TN914

10.3778/j.issn.1002-8331.1308-0152

XIANG Xiangqin,ZHANG Huyin.Spectrum allocation of cognitive radio system based on SFOA.Computer Engineering and Applications,2014,50（6）：72-76.

國家自然科學(xué)基金（No.61272454）。

項響琴（1976—），女，講師，主要研究領(lǐng)域為數(shù)據(jù)挖掘與智能軟件；張滬寅（1962—），男，博士，教授，主要研究領(lǐng)域為網(wǎng)絡(luò)體系結(jié)構(gòu)，高性能計算，e-Learning。

2013-08-14

2013-10-18

1002-8331（2014）06-0072-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-01-15，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1308-0152.html