離散量子粒子群優(yōu)化的認(rèn)知無線電頻譜分配

刁 鳴，張志強(qiáng)，高洪元

（哈爾濱工程大學(xué)信息與通信工程學(xué)院，哈爾濱150001）

·移動互聯(lián)與通信技術(shù)·

離散量子粒子群優(yōu)化的認(rèn)知無線電頻譜分配

刁 鳴，張志強(qiáng)，高洪元

（哈爾濱工程大學(xué)信息與通信工程學(xué)院，哈爾濱150001）

為解決認(rèn)知無線電頻譜分配的離散優(yōu)化問題并提高分配性能，提出一種離散量子粒子群優(yōu)化算法。利用量子計算理論更新粒子并用波函數(shù)對量子旋轉(zhuǎn)角進(jìn)行調(diào)節(jié)，使之同時具有粒子群優(yōu)化算法快速收斂和量子計算精度高的優(yōu)點，從而有效提高認(rèn)知無線電頻譜分配的性能。仿真結(jié)果表明，與遺傳算法、量子遺傳算法、粒子群優(yōu)化算法和敏感圖論著色算法相比，該算法能較快地搜尋到最優(yōu)解，且在不同的網(wǎng)絡(luò)效益函數(shù)下性能較優(yōu)。

認(rèn)知無線電；頻譜分配；離散優(yōu)化；離散量子粒子群優(yōu)化算法；網(wǎng)絡(luò)效益函數(shù)

1 概述

目前，頻譜資源變的越來越匱乏，而對有限的頻譜資源的利用率較低又成為一個更為嚴(yán)重的問題［1-2］。為了解決這一問題，認(rèn)知無線電（Cognitive Radio，CR）技術(shù)應(yīng)運(yùn)而生，它作為一種智能無線通信系統(tǒng)，能感知無線環(huán)境的變化并通過實時地修改操作參數(shù)對其做出反應(yīng)，從而為提高無線網(wǎng)絡(luò)的頻譜利用率提供了一種有效的方法［3-4］。這樣的無線網(wǎng)絡(luò)中，在特定的時間和位置上，主用戶未使用的頻譜由次級用戶（或認(rèn)知用戶）識別和接入。為了不影響主用戶的工作，次級用戶接入時要滿足與干擾和沖突有關(guān)的約束條件。在認(rèn)知無線電領(lǐng)域中，頻譜分配問題是一個研究的熱點，最大化頻譜利用率的同時維護(hù)系統(tǒng)的公平性是其主要目標(biāo)［2，5-6］。

在主用戶和次用戶中分配信道同時最小化所有用戶之間干擾的問題在認(rèn)知無線電網(wǎng)絡(luò)中被稱為資源分配或者頻譜分配問題。文獻(xiàn)［7］把這個問題稱為NP難問題。如今，已有很多分配模型用來解決認(rèn)知無線電頻譜分配問題，如圖論著色模型［8-9］、干擾溫度模型［10］、定價拍賣模型和博弈論模型［11］。近年來，進(jìn)化算法被用來解決這個問題，如遺傳算法［10，12］、粒子群優(yōu)化算法［10，13］、人工蜂群算法［11］、量子遺傳算法［14］。但是這些經(jīng)典的進(jìn)化算法都存在收斂速度和收斂性能之間的矛盾，在現(xiàn)有條件下很難在保證收斂速度的條件下避免局部收斂，準(zhǔn)確搜索到最優(yōu)解。因此，需要根據(jù)進(jìn)化算法的發(fā)展提出新算法來解決現(xiàn)有問題。

量子粒子群優(yōu)化算法是基于傳統(tǒng)粒子群算法的改進(jìn)。目前，量子粒子群優(yōu)化算法在函數(shù)優(yōu)化、系統(tǒng)辨識、生物信息、圖像處理和工程優(yōu)化等許多方面得到廣泛應(yīng)用，并取得了較好的應(yīng)用效果。傳統(tǒng)量子粒子群優(yōu)化算法將量子行為引入粒子群算法，提高了收斂精度，但不適用于實際離散空間的搜索，因而不能有效解決認(rèn)知無線電頻譜分配的問題。為此，本文對粒子群算法量子化，利用量子計算理論更新粒子，并用波函數(shù)對量子旋轉(zhuǎn)角進(jìn)行調(diào)節(jié)，提出一種離散量子粒子群優(yōu)化算法（Discrete Quantum-behaved Particle Swarm Optim ization，DQPSO）。

2 CR頻譜分配模型

認(rèn)知無線電頻譜分配模型由可用頻譜矩陣、效益矩陣、干擾矩陣、無干擾分配矩陣構(gòu)成。假設(shè)在一個認(rèn)知無線電網(wǎng)絡(luò)中有N個認(rèn)知用戶（標(biāo)號為1～N）、M個可用頻帶（標(biāo)號為1～M），且各頻帶之間相互正交［3］。模型中各矩陣定義如下：

（1）可用頻譜矩陣L：L=｛ln，m|ln，m∈｛0，1｝｝N×M是一個N行M列的矩陣，ln，m表示頻帶m對用戶n的可用性。如果頻帶m可以被認(rèn)知用戶n使用，則ln，m=1；如果頻帶m不能被認(rèn)知用戶n使用，則ln，m=0。

（2）效益矩陣B：B=｛bn，m｝N×M是一個N行M列的矩陣，bn，m表示用戶n使用頻帶m時所獲得的效益。效益可以用頻譜利用率、吞吐量來表示，本文中，效益正比于認(rèn)知用戶通信覆蓋面積。如果ln，m= 0，則bn，m=0。

（3）干擾矩陣C：C=｛cn，k，m|cn，k，m∈｛0，1｝｝N×N×M是一個N×N×M的三維矩陣，cn，k，m表示用戶n和用戶k同時使用頻帶m時的干擾約束關(guān)系。如果cn，k，m=1，則認(rèn)知用戶n和k同時使用頻帶m時會產(chǎn)生干擾。干擾矩陣和可用頻譜矩陣之間也有制約關(guān)系，當(dāng)n=k時，cn，n，m=1-ln，m。

（4）無干擾分配矩陣A：A=｛an，m|an，m∈｛0，1｝｝N×M是一個N行M列的矩陣，表示一種可行的頻譜分配方案。如果將頻帶m分配給認(rèn)知用戶n，則an，m=1；如果頻帶m沒有分配給認(rèn)知用戶n，則an，m=0。無干擾分配矩陣A必須滿足如下無干擾約束條件：

（1）平均最大網(wǎng)絡(luò)效益：

3 離散量子粒子群優(yōu)化算法

其中，滿足|αij|2+|βij|2=1（i=1，2，…，h；j=1，2，…，l），則量子速度可以表示為2l個狀態(tài)。為了簡單有效地設(shè)計DQPSO算法，設(shè)定αij和βij為實數(shù)，并

傳統(tǒng)量子粒子群優(yōu)化算法難以解決認(rèn)知無線電頻譜分配的離散搜索問題，為此，本文在粒子群優(yōu)化算法中引入量子計算理論來更新粒子，并用波函數(shù)對量子旋轉(zhuǎn)角進(jìn)行調(diào)節(jié)，提出DQPSO算法。

在DQPSO算法中使用量子編碼，稱之為量子比特或者Q比特，基于量子比特的概念，量子速度的概率表示定義為一個量子比特串。DQPSO中每一位采用量子比特的方式表示，稱為量子位，由一對復(fù)數(shù)（α，β）表示。每個量子位的狀態(tài)可以取0或1，|α|2，|β|2分別表示量子位處于0或1的概率，設(shè)共有h個量子粒子，那么第i個量子粒子的量子速度定義為：

且0≤αij≤1，0≤βij≤1。因此，，式（1）中的量子速度可以簡化為：

在離散量子粒子群優(yōu)化算法中，每個量子粒子依靠其自身和周圍量子粒子的歷史經(jīng)驗于l維空間中運(yùn)動。在這個l維空間中共有h個量子粒子，第i個量子粒子在空間中的位置表示為向量xi=［xi1，xi2，…，xil］（i=1，2，…，h），第i個粒子的量子速度表示為向量vi=［vi1，vi2，…，vil］（i=1，2，…，h），第i個量子粒子的個體最優(yōu)位置表示為向量pi=［pi1，pi2，…，pil］（i=1，2，…，h），向量pg=［pg1，pg2，…，pgl］代表至今為止群體中所有量子粒子探索到的最優(yōu)位置。

通過以上分析，將量子粒子的更新過程表示如下：

量子速度的進(jìn)化過程主要依靠量子旋轉(zhuǎn)門［15］來進(jìn)行，量子旋轉(zhuǎn)角的更新方法為：

其中，i=1，2，…，h；j=1，2，…，l；s為［1，h］之間的隨機(jī)整數(shù)；e1，e2為加速因子；φ表示調(diào)整系數(shù)；u是［0，1］之間均勻分布的隨機(jī)數(shù)；t和t+1代表迭代次數(shù)。

這樣，第i個量子粒子的第j個量子位速度vij由如下式方法進(jìn)行更新：其中，i=1，2，…，h；j=1，2，…，l；t和t+1代表迭代次數(shù)。

最終，每一代的第i個量子粒子的量子位置通過如下方程更新：

4 離散量子粒子群優(yōu)化的CR頻譜分配算法

量子粒子群的初始位置在位置空間中隨機(jī)選擇，所有粒子的量子速度初始化為。目標(biāo)函數(shù)的目的是評價每一個量子粒子的狀態(tài)，在頻譜分配問題中，位置優(yōu)化的目標(biāo)是最大化網(wǎng)絡(luò)效益。

基于以上分析，離散量子粒子群優(yōu)化算法用于頻譜分配的工作流程表示如下：

步驟2 基于二進(jìn)制編碼和量子編碼機(jī)制產(chǎn)生一個初始的量子粒子種群。

步驟3 對每個量子粒子位置的第j個量子位映射到an，m中，其中，（m，n）為L1中的第j個元素，且j=1，2，…，l。對所有的m，搜尋所有滿足cn，k，m=1且n≠k的（n，k），檢查矩陣A的第n行、m列與矩陣A的第k行、m列兩位對應(yīng)的元素是否同時為1，如果是，隨機(jī)置其中一位為0。

步驟4 計算每個量子粒子的適應(yīng)度值。

步驟5 更新每個量子粒子的個體最優(yōu)位置，更新量子粒子群體的全局最優(yōu)位置。

步驟6 更新每個量子粒子的量子速度和量子位置。

步驟7 如果算法達(dá)到預(yù)定義的最大進(jìn)化代數(shù)，則停止并輸出最優(yōu)結(jié)果；如果沒有，則轉(zhuǎn)到步驟3。

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

敏感圖論著色算法是為了描述認(rèn)知無線電頻譜分配模型而提出的解決認(rèn)知無線電頻譜分配問題的常用算法。為檢驗DQPSO頻譜分配算法的性能，在仿真中將其與CSGC算法以及其他進(jìn)化算法進(jìn)行比較。CSGC算法使用非協(xié)作式標(biāo)簽規(guī)則。

本文將4種進(jìn)化算法設(shè)置成相同的初始種群和最大進(jìn)化代數(shù)（最大進(jìn)化代數(shù)設(shè)置為1 000）。GA，QGA，PSO的參數(shù)設(shè)置與DQPSO相同［16］。在DQPSO算法中，設(shè)定e1=0.06，φ=0.1。每一次實驗仿真100次。

5.1 基于平均最大網(wǎng)絡(luò)效益的仿真實驗

設(shè)置主用戶數(shù)為20，可用信道數(shù)為20，次級用戶數(shù)為10。仿真結(jié)果如圖1所示。其中，縱坐標(biāo)代表算法使用平均最大網(wǎng)絡(luò)效益函數(shù)時獲得的效益?？梢钥闯觯珻SGC算法效果最差，GA，QGA，PSO算法容易陷入局部最優(yōu)，DQPSO算法雖然在收斂速度上較PSO算法有一定差距，但是在150代以后DQPSO算法獲得的平均最大網(wǎng)絡(luò)效益明顯高于其他算法。

圖1 基于平均最大網(wǎng)絡(luò)效益的收斂曲線

保持次級用戶數(shù)為10不變，逐漸增加信道數(shù)c，并使主用戶數(shù)與信道數(shù)相等，通過仿真研究平均最大網(wǎng)絡(luò)效益的變化，得到結(jié)果如表1所示?？梢钥闯?，次級用戶數(shù)不變，隨著信道數(shù)的增多，可獲得的網(wǎng)絡(luò)效益也增加。同時也可以看出，離散量子粒子群優(yōu)化算法獲得的平均最大網(wǎng)絡(luò)效益在信道數(shù)增多的情況下仍然高于其他4種算法。

表1 信道數(shù)增加時的平均最大網(wǎng)絡(luò)效益

保持主用戶數(shù)為10，信道數(shù)為10不變，逐漸增加次級用戶數(shù)u，通過仿真研究平均最大網(wǎng)絡(luò)效益的變化，得到結(jié)果如表2所示?？梢钥闯?，主用戶數(shù)及信道數(shù)不變，隨著次級用戶數(shù)的增多，由于次級用戶間的競爭更加激烈，從而產(chǎn)生更多干擾，因此可獲得的網(wǎng)絡(luò)效益隨之減少。同時可以看出，離散量子粒子群優(yōu)化算法獲得的平均最大網(wǎng)絡(luò)效益在次級用戶數(shù)增多的情況下仍然高于其他4種算法。

表2 次級用戶數(shù)增加時的平均最大網(wǎng)絡(luò)效益

5.2 基于最大比例公平網(wǎng)絡(luò)效益的仿真實驗

設(shè)置主用戶數(shù)為20，可用信道數(shù)為20，次級用戶數(shù)為10。仿真結(jié)果如圖2所示。其中，縱坐標(biāo)代表算法使用最大比例公平網(wǎng)絡(luò)效益函數(shù)時獲得的效益。可以看出盡管GA，QGA，PSO算法具有較快的收斂速度，但都陷入局部最優(yōu)，而本文的DQPSO算法具有相對較高的收斂精度，300代以后獲得的最大比例公平網(wǎng)絡(luò)效益高于其他算法。

圖2 基于最大比例公平網(wǎng)絡(luò)效益的收斂曲線

保持次級用戶數(shù)為10不變，逐漸增加信道數(shù)c，并使主用戶數(shù)與信道數(shù)相等，通過仿真研究最大比例公平網(wǎng)絡(luò)效益的變化，得到結(jié)果如表3所示?？梢钥闯?，離散量子粒子群優(yōu)化算法獲得的最大比例公平網(wǎng)絡(luò)效益仍然高于其他4種算法，網(wǎng)絡(luò)效益隨信道數(shù)增加而增加。

表3 信道數(shù)增加時的最大比例公平網(wǎng)絡(luò)效益

保持主用戶數(shù)為10、信道數(shù)為10不變，逐漸增加次級用戶數(shù)u，通過仿真研究最大比例公平網(wǎng)絡(luò)效益的變化，得到結(jié)果如表4所示?？梢钥闯?，離散量子粒子群優(yōu)化算法獲得的最大比例公平網(wǎng)絡(luò)效益仍然高于其他4種算法，網(wǎng)絡(luò)效益隨次級用戶數(shù)增加而減少。

表4 次級用戶數(shù)增加時的最大比例公平網(wǎng)絡(luò)效益

6 結(jié)束語

為解決認(rèn)知無線電頻譜分配的離散優(yōu)化問題并提高分配性能，本文提出一種離散量子粒子群優(yōu)化算法，該算法用量子計算理論更新粒子，可以從平均最大網(wǎng)絡(luò)效益和最大比例公平網(wǎng)絡(luò)效益2個方面解決認(rèn)知無線電頻譜分配問題。實驗結(jié)果表明，相較于傳統(tǒng)的CSGC算法和其他經(jīng)典進(jìn)化算法，本文算法在2種效益函數(shù)下都能有效提高網(wǎng)絡(luò)效益。下一步工作是將DQPSO算法應(yīng)用到認(rèn)知無線電頻譜感知等領(lǐng)域。

［1］ Liu Zhe，Geng Xiaoyan，Dong Mo.Two Dimension Spectrum Allocation for Cognitive Radio Networks，Wireless Communications［J］.IEEE Transactions on Wireless Communications，2014，13（3）：1410-1423.

［2］ Tragos E Z，Zeadally S，F(xiàn)ragkiadakis A G，et al. Spectrum Assignment in Cognitive Radio Networks：A Comprehensive Survey［J］.IEEE Communications Surveys&Tutorials，2013，15（3）：1108-1135.

［3］ 王中偉，賈振紅，覃錫忠，等.基于認(rèn)知無線電網(wǎng)絡(luò)的動態(tài)頻譜分配［J］.計算機(jī)工程，2014，40（3）：127-131.

［4］ Haykin S.Cognitive Radio：Brain-em powered Wireless Communications［J］.IEEE Journal on Selected Areas in Communications，2005，23（2）：201-220.

［5］ Zhao Zhijin，Peng Zhen，Zheng Shilian，et al.Cognitive Radio Spectrum Allocation Using Evolutionary Algorithm s［J］.IEEE Transactions on Wireless Communications，2009，8（9）：4421-4425.

［6］ 劉 鑫，譚學(xué)治.認(rèn)知無線電中OFDM多用戶頻譜分配［J］.哈爾濱工程大學(xué)學(xué)報，2009，30（10）：1165-1169.

［7］ Peng Chunyi，Zheng Haitao，Zhao Ben.Utilization and Fairness in Spectrum Assignment for Opportunistic Spectrum Access［J］.ACM Mobile Networks and Applications，2006，11（4）：555-576.

［8］ 彭 振，趙知勁，鄭仕鏈.基于混合蛙跳算法的認(rèn)知無線電頻譜分配［J］.計算機(jī)工程，2010，36（6）：210-212，217.

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

［10］ Kolodzy P J.Interference Temperature：A Metric for Dynamic Spectrum Utilization［J］.International Journal of Network Management，2006，16（2）：103-113.

［11］ Wang Beiwei，Wu Yongle，Liu K JR.Game Theory for Cognitive Radio Networks：An Overview［J］.Computing Networks，2010，54（14）：2537-2561.

［12］ Am iri B，F(xiàn)athian M，Maroosi A.Application of Shuffled Frog-leaping Algorithm on Clustering［J］.International Journal of Advanced Manufacturing Technology，2009，42（1/2）：199-209.

［13］ Gao Hongyuan，Liu Yuqi，Diao Ming.Robust Multi-user Detection Based on Quantum Bee Colony Optimization［J］.International Journal of Innovative Computing and Applications，2011，3（3）：160-168.

［14］ Eusuff M，Lansey K，Pasha F.Shuffled Frog-leaping Algori-thm：A Memetic Meta-heuristic for Discrete Optimization［J］.Engineering Optimization，2006，38（6）：129-154.

［15］ Gao Hongyuan，Diao Ming.Quantum Particle Swarm Optimization for MC-CDMA Multiuser Detection［C］// Proceedings of International Conference on Artificial Intelligence and Computational Intelligence.Washington D.C.，USA：IEEE Press，2009：132-136.

［16］ Gao Hongyuan，Cao Jinlong，Diao Ming.A Simple Quantum-inspired Particle Swarm Optimization and Its Application［J］.Information Technology Journal，2011，10（12）：2315-2321.

編輯金胡考

Cognitive Radio Spectrum Allocation with Discrete Quantum-behaved Particle Swarm Optimization

DIAO Ming，ZHANG Zhiqiang，GAO Hongyuan
（College of Information and Communication Engineering，Harbin Engineering University，Harbin 150001，China）

In order to solve discrete optimization problem in Cognitive Rradio（CR）spectrum allocation and improve the allocation performance，this paper proposes a Discrete Quantum-behaved Particle Swarm Optimization（DQPSO）algorithm.It updates the particles with quantum computing theory and adjusts the rotation angle with wave function，and it has both advantages of fast convergence rate of Particle Swarm Optimization（PSO）algorithm and high precision of quantum Computing.W hen applied in the problem of CR spectrum allocation，it can improve the performance of spectrum allocation effectively.This paper com pares the performance of the proposed algorithm with the Genetic Algorithm（GA），Quantum-inspired Genetic Algorithm（QIGA），PSO algorithm and Color Sensitive Graph Coloring（CSGC）algorithm in different network benefit functions.Simulation results show that the proposed algorithm can search faster for the optimal solution，and it has better performance.

Cognitive Radio（CR）；spectrum allocation；discrete optimization；Discrete Quantum-behaved Particle Swarm Optimization（DQPSO）algorithm；network benefit function

刁 鳴，張志強(qiáng)，高洪元.離散量子粒子群優(yōu)化的認(rèn)知無線電頻譜分配［J］.計算機(jī)工程，2015，41（11）：126-130.

英文引用格式：Diao Ming，Zhang Zhiqiang，Gao Hongyuan.Cognitive Radio Spectrum Allocation with Discrete Quantum-behaved Particle Swarm Optimization［J］.Computing Engineering，2015，41（11）：126-130.

1000-3428（2015）11-0126-05

A

TP393

10.3969/j.issn.1000-3428.2015.11.022

國家自然科學(xué)基金資助項目（61102106）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項基金資助項目（HEUCF140809）；中國博士后科學(xué)基金資助項目（2013M 530148）。

刁 鳴（1960-），男，教授、博士生導(dǎo)師，主研方向：寬帶信號檢測，處理與識別，通信信號處理；張志強(qiáng)，碩士研究生；高洪元，副教授。

2014-11-17

2014-12-14 E-m ail：diaom ing@hrbeu.edu.cn