漁夫捕魚優化算法的認知無線電頻譜分配

項響琴，張滬寅

1.合肥學院網絡與智能信息處理重點實驗室，合肥 230601

2.武漢大學計算機學院，武漢 430072

漁夫捕魚優化算法的認知無線電頻譜分配

項響琴1，張滬寅2

1.合肥學院網絡與智能信息處理重點實驗室，合肥 230601

2.武漢大學計算機學院，武漢 430072

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

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

1 引言

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

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

為了提高認知無線電頻譜利用率，充分利用SFOA全局尋優能力，提出一種基于SFOA的認知無線電頻譜分配算法。首先以系統效益最大化為優化目標，建立認知無線電頻譜分配優化的數學模型，然后采用SFOA找到空閑頻譜最優分配方案，仿真結果表明，SFOA可以有效求解認知無線電的頻譜分配問題，使網絡系統效益達到最大化。

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

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

圖1 頻譜分配問題描述

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

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

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

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

（2）干擾矩陣C為：

圖2 認知無線電系統的模型

當認知用戶n和k同時使用信道m產生干擾，則cn，k，m=1；若認知用戶n和k同時使用信道m不產生干擾，則cn，k，m=0。

（3）效益矩陣B為：

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

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

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

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

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

3 模擬漁夫捕魚優化算法

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

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

3.2 漁夫捕魚算法的描述

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

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

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

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

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

4.1 漁夫位置編碼

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

圖3 漁夫位置的編碼方式

4.2 目標函數設計

認知無線電頻譜分配目標是使整個小區內所有認知用戶取得的效益總和最大化，因此采用系統效益作為魚的密度度量函數（目標函數），即

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元素對應的n與m，即令L={(n，m)|ln，m=1}。

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

步驟3對初始化漁夫的位置，根據式（9）評價漁夫的位置優劣，并找出當前最優捕魚位置，在公示板公布。

步驟4漁夫在各自的區域進行移動搜索，尋找更優的捕魚位置。

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

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

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

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

步驟9輸出最優捕魚位置對應的認知無線電頻譜分配方案，結束。

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

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

5 仿真實驗

5.1 仿真環境及對比算法

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

表1 仿真參數

5.2 結果與分析

5.2.1 收斂速度對比

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

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

5.2.2 系統效益與可用頻譜數之間的變化關系

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

圖6 系統效益與頻譜數的變化關系

5.2.3 系統效益與用戶數之間的變化關系

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

圖7 N變化時系統效益

5.2.4 網絡效益與實驗次數之間的變化關系

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

圖8 不同算法的網絡效益對比

6 結語

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

[1]滑楠，曹志剛.認知無線電網絡路由研究綜述[J].電子學報，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]寧國勤，張靜.基于時間預測的多跳頻譜切換算法研究[J].計算機工程與應用，2013，49（13）：71-75.

[4]王欽輝，葉保留，田宇，等.認知無線電網絡中頻譜分配算法[J].電子學報，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]柴爭義，劉芳.基于免疫克隆選擇優化的認知無線網絡頻譜分配[J].通信學報，2010，31（11）：92-100.

[8]知勁，彭振，鄭仕鏈，等.基于量子遺傳算法的認知無線電頻譜分配[J].物理學報，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]唐萬斌，喻火根，李少謙.基于信道預測的認知無線電混合頻譜切換算法[J].計算機工程與應用，2012，48（27）：17-21.

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

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

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

[15]肖淑艷，孫茜，衡芹，等.基于D-S理論的認知無線電頻譜感知算法[J].計算機工程與應用，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.

國家自然科學基金（No.61272454）。

項響琴（1976—），女，講師，主要研究領域為數據挖掘與智能軟件；張滬寅（1962—），男，博士，教授，主要研究領域為網絡體系結構，高性能計算，e-Learning。

2013-08-14

2013-10-18

1002-8331（2014）06-0072-05

CNKI網絡優先出版：2014-01-15，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1308-0152.html