王若慧，張華偉

（1.山西大學(xué) 工程學(xué)院，太原030013；

2.河南財經(jīng)政法大學(xué) 計算機與信息工程學(xué)院，鄭州 450000）

隨著無線業(yè)務(wù)的快速發(fā)展和不斷增長，有限的無線頻譜資源越來越緊缺.事實上，已有的無線頻譜資源利用率較低，認知無線電技術(shù)是提高頻譜資源利用率的一個有效途徑［1］.在認知無線電技術(shù)中，非授權(quán)用戶（也稱次用戶或認知用戶）可在不干擾授權(quán)用戶（也稱主用戶）并在其允許的情況下，動態(tài)接入主用戶的空閑頻段，從而最大限度地利用無線頻譜資源［2］.

認知無線電技術(shù)是無線通信技術(shù)的革新.基于認知無線電技術(shù)，目前已有幾種針對不同應(yīng)用場景的認知無線電網(wǎng)絡(luò)，如：WRAN（wireless regional area network）、認知mesh和認知Ad hoc等網(wǎng)絡(luò)形態(tài).其中，WRAN是認知無線電技術(shù)的最典型應(yīng)用，是首個將概念變?yōu)楝F(xiàn)實的標(biāo)準(zhǔn)［3］.頻譜分配是WRAN系統(tǒng)中的關(guān)鍵技術(shù).目前，認知無線電的頻譜分配已有很多研究成果，如圖著色、拍賣理論和博弈論等方法［4－5］.但已有的關(guān)于認知無線網(wǎng)絡(luò)頻譜分配的研究多集中在較廣義的范圍［6－10］，對WRAN等具體系統(tǒng)的頻譜分配研究還較少.文獻［11］通過拍賣機制對WRAN中的頻譜分配問題進行了研究.頻譜分配是NP難問題［6－10］，進化算法是求解此類問題的有效途徑.此外，頻譜分配問題還具有實時性，需要較快的收斂.基于此，本文提出一種基于量子進化算法的WRAN頻譜分配方案，利用量子計算的并行性和高效性提高頻譜分配的效果.仿真實驗結(jié)果驗證了其可行性.

1 WRAN頻譜分配模型

1.1 WRAN簡介

WRAN采用IEEE 802.22技術(shù)標(biāo)準(zhǔn)，使用位于54～862MHz VHF／UHF頻段中的電視頻帶，可與電視業(yè)務(wù)共存且不對其產(chǎn)生有害干擾［3，11］.WRAN具有較大的覆蓋范圍，最大可達100km，可為邊遠地區(qū)提供有效的網(wǎng)絡(luò)接入服務(wù).

WRAN由擁有授權(quán)頻譜的電視廣播臺（TV broadcaster）、認知基站BS（base station）和認知用戶CPE（customer premise equipment）組成.每個WRAN小區(qū)至少包括一個認知基站，認知用戶通過基站獲得空閑頻段并進行頻譜分配.在WRAN中，電視廣播臺為主用戶，不同認知用戶被不同區(qū)域的基站覆蓋，一些處于交叉區(qū)域中的認知用戶可由多個認知基站覆蓋.

1.2 WRAN連接模型

圖1 WRAN拓撲示意圖Fig.1 Topology of WRAN

圖1為一個WRAN連接模型的示意圖.假設(shè)在一個仿真區(qū)域中隨機分布4個主用戶和4個認知用戶（次用戶），廣播基站i（1≤i≤4）是主用戶，無線接入點n（1≤n≤4）是認知用戶.仿真系統(tǒng)中有3個可用的電視廣播頻譜資源（A，B，C），每個認知用戶可使用多個空閑頻譜.假設(shè)用戶（包括主用戶和認知用戶）間的干擾由距離決定，每個主用戶i占用一個可用頻譜m，其保護范圍為rp（i，m）（m∈M）.rs（n，m）表示認知用戶n的干擾范圍，其干擾區(qū)域是以用戶n為圓心、以rs（n，m）為半徑的一個圓形區(qū)域（n∈N），并可通過調(diào)整干擾半徑，避免與主用戶沖突.當(dāng)認知用戶與主用戶所處位置間的距離滿足rs（n，m）＋rp（i，m）≤d（n，i）時，可使用相同的頻譜資源.圖1中括號內(nèi)的頻譜資源有不同的含義：對主用戶，表示其正在占用（使用）的頻譜；對認知用戶，表示可用的頻譜資源.圖1中主用戶1和認知用戶1的覆蓋范圍出現(xiàn)重疊，因此認知用戶1只能使用頻譜B和C；同理，認知用戶2只能使用頻譜A和C；而對于認知用戶3，由于其沒有與任何主用戶的覆蓋范圍有重疊，故其可使用頻譜A，B，C.

1.3 WRAN頻譜分配模型

基于圖著色的頻譜分配理論，結(jié)合WRAN的特點，其頻譜分配模型建模為如下矩陣［4－11］：空閑矩陣L（Leisure）、效益矩陣B（Benefit）、干擾矩陣C（Constraint）、無干擾分配矩陣A（Allocation）.

1）空閑頻譜矩陣L是指認知用戶是否可使用的某個特定頻譜資源，也稱為可用矩陣，記為L是一個二值矩陣，ln，m＝1表示可用，ln，m＝0表示不可用.

2）效益矩陣B是指認知用戶分配到特定頻譜資源后所獲得的效益，記為B＝｛bn，m｝N×M.顯然，當(dāng)ln，m＝0時，有bn，m＝0.在WRAN中，效益矩陣定義為帶寬速率，與傳輸時的調(diào)制方式及編碼速率有關(guān).參數(shù)值設(shè)置可參考IEEE 802.22的WRAN提案［3］.

3）干擾矩陣C是指不同認知用戶使用相同的可用頻譜時會產(chǎn)生干擾，記為同時使用頻譜m（1≤m≤M）時會產(chǎn)生干擾.映射在圖1中，即當(dāng)rs（n，m）＋rp（k，m）≤d（n，k）時，認知用戶n和k會產(chǎn)生干擾，即cn，k，m＝1.干擾矩陣C受空閑頻譜矩陣L影響，滿足cn，k，m≤ln，m×lk，m，即只有認知用戶n和k可同時使用空閑頻譜m時，才有可能相互間產(chǎn)生干擾.

4）無干擾分配矩陣A是指將可用的無干擾頻譜資源分配給認知用戶，記為矩陣A必須滿足干擾矩陣C定義的約束條件：

2 基于量子進化頻譜分配的實現(xiàn)

2.1 量子進化計算

進化計算求解問題時，先初始化種群，再通過交叉和選擇等操作，對候選個體進行優(yōu)化.進化計算由于對問題特征無特殊限定，因此在組合優(yōu)化、機器學(xué)習(xí)和網(wǎng)絡(luò)優(yōu)化等方面應(yīng)用廣泛，并取得了較好的求解效果.

量子進化算法是將進化計算和量子計算理論相結(jié)合的一種優(yōu)化算法，主要特征是使用量子比特進行編碼，一個量子染色體可同時表示多個狀態(tài)的信息.因此，可帶來豐富的種群，并加快算法收斂.本文利用量子進化算法求解頻譜分配問題，并設(shè)計一種改進的量子旋轉(zhuǎn)門算子，提高了WRAN中頻譜分配的效果.

2.2 算法實現(xiàn)

設(shè)Q表示量子種群，q表示一個量子個體，P表示普通種群，p表示一個普通個體.本文設(shè)計的基于量子進化的頻譜分配算法基本步驟如下：

1）初始化.

4）計算P（g）中種群個體的適應(yīng)度，保存最優(yōu)個體.

本文直接將網(wǎng)絡(luò)效益U（R）作為適應(yīng)度函數(shù).由于是最大化網(wǎng)絡(luò)效益，所以適應(yīng)度越大越好.適應(yīng)度最大的個體即為最優(yōu)個體，其所對應(yīng)的分配矩陣A即為所求.

5）算法終止條件判斷.

判斷算法是否達到最大進化代數(shù)gmax.如果滿足終止條件，則算法終止；否則，轉(zhuǎn)6）.

6）對量子種群Q（g）進行克隆，生成新的量子種群Q′（g）.

傳統(tǒng)的量子旋轉(zhuǎn)角度選擇是固定從旋轉(zhuǎn)角度表中取值，容易陷入局部最優(yōu)［12］.基于此，本文設(shè)計一種改進的量子旋轉(zhuǎn)門算子，可根據(jù)量子基因位和染色體適應(yīng)度自適應(yīng)地計算旋轉(zhuǎn)角度，提高了算法保持種群多樣性的能力.

假設(shè)xi和bi分別是經(jīng)過量子觀測后的普通個體x和最佳個體b第i位上的值，這兩個個體的適應(yīng)度值分別為Fit（x）和Fit（b），定義

其中：θ0為初始旋轉(zhuǎn)角度，本文設(shè)為0.05π；s1和s2用于控制旋轉(zhuǎn)方向；Fit（x）和Fit（b）用于自適應(yīng)地調(diào)整轉(zhuǎn)角大小.因此，旋轉(zhuǎn)角度可根據(jù)個體的適應(yīng)度自適應(yīng)地調(diào)整.

按照2）中方法，重新觀察量子種群Q′（g），生成P′（g）.

7）對重新生成的普通種群P′（g）進行全干擾交叉，生成P″（g）；轉(zhuǎn)4）.全干擾交叉借鑒量子的相干特性，所有的染色體均參與交叉操作，可充分利用種群中的有效信息，避免算法早熟收斂［12－13］.

3 仿真實驗

算法在Windows環(huán)境下，使用MATLAB7.1進行編程實現(xiàn).仿真實驗環(huán)境為圖1所示的拓撲.采用文獻［9］附錄中提供的偽代碼生成矩陣L，B，C，并滿足如下約束條件：用矩陣L和效益矩陣B均為N×M的二元矩陣，其中，可用矩陣L必須保證每列最少有一個元素為1（即至少有一個可用頻譜）；效益矩陣的衡量標(biāo)準(zhǔn)為帶寬速率，參數(shù)取值可參考IEEE 802.22的 WRAN提案［3］；干擾矩陣C為隨機生成的二元（0，1）對稱矩陣.進化計算中參數(shù)的取值如下：最大進化代數(shù)gmax＝200，種群規(guī)模s＝10，全干擾交叉概率pc＝0.2.

實驗結(jié)果采用最大化網(wǎng)絡(luò)收益衡量.為了對比驗證算法的性能，與求解此問題的CSGC算法［6］及GA－SA算法進行比較［9］.實驗中參數(shù)設(shè)置相同，取算法運行50次的平均值作為最終結(jié)果，比較結(jié)果列于表1.

表1 網(wǎng)絡(luò)收益比較（M＝N＝10）Table 1 Comparison of network profits（M＝N＝10）

由表1可見，本文算法相比已有算法具有較高的網(wǎng)絡(luò)收益，表明本文設(shè)計的各種算子是有效的.此外，本文算法在100代左右開始收斂，而文獻［9］算法在150代以后才開始收斂，表明本文算法具有較快的收斂速度.

下面驗證在不同認知用戶數(shù)量和可用頻譜數(shù)量下網(wǎng)絡(luò)的收益情況，并與相關(guān)算法進行比較，結(jié)果分別如圖2和圖3所示.

圖2 可用頻譜與網(wǎng)絡(luò)收益的關(guān)系Fig.2 Relationship between available spectrum and network profits

圖3 認知用戶數(shù)量與網(wǎng)絡(luò)收益的關(guān)系Fig.3 Relationship between number of secondary users and network profits

由圖2和圖3可見，隨著可用頻譜數(shù)量和認知用戶數(shù)量的增加，網(wǎng)絡(luò)收益值逐漸增加，本文算法的增益優(yōu)于已有算法，表明本文算法尋優(yōu)能力較強.

構(gòu)建IEEE 802.22的WRAN系統(tǒng)仿真平臺：根據(jù)WRAN的覆蓋范圍，考慮一個無限大的區(qū)域，完成主用戶和認知用戶的初始化.WRAN系統(tǒng)由基站BS實現(xiàn)集中控制：獲得各小區(qū)空閑的TV頻譜集合后，由BS控制各小區(qū)內(nèi)的認知用戶對空閑TV頻譜的占用.結(jié)合圖1，空閑頻譜矩陣為

分配矩陣A的結(jié)果表明：頻譜A分配給認知用戶3使用，頻譜B分配給認知用戶1和4共同使用，并且認知用戶間不會產(chǎn)生干擾；頻譜C分配給認知用戶2使用.在這種分配模式下，網(wǎng)絡(luò)收益達到最大.

綜上所述，針對認知無線網(wǎng)絡(luò)中的頻譜分配問題，本文設(shè)計了一種基于量子進化的WRAN頻譜分配算法，并驗證了算法的有效性.實驗結(jié)果表明，本文算法可獲得更高的網(wǎng)絡(luò)收益，滿足WRAN網(wǎng)絡(luò)的頻譜分配需求.

［1］Akyildlz，Li W Y，Vuran M C，et al.Next Generation／Dynamic Spectrum Access／Cognitive Radio Wireless Networks：A Survey［J］.Computer Networks Journal，2006，50（3）：2127－2159.

［2］ZOU Chao，JIN Tao，Chigan C，et al.QoS－Aware Distributed Spectrum Sharing for Heterogeneous Wireless Cognitive Networks［J］.Computer Networks，2009，52（4）：864－878.

［3］HAN Ning，SHON Sunghwan，Chung Jae Hak，et al.Spectral Correlation Based Signal Detection Method for Spectrum Sensing in IEEE 802.22WRAN Systems ［C］／／The 8th International Conference on Advanced Communication Technology.Piscataway：IEEE Press，2008：1770－1775.

［4］王欽輝，葉保留，田宇，等.認知無線電網(wǎng)絡(luò)中頻譜分配算法 ［J］.電子學(xué)報，2012，40（1）：147－154.（WANG Qinhui，YE Baoliu，TIAN Yu，et al.Survey on Spectrum Allocation Algorithms for Cognitive Radio Networks［J］.Acta Electronica Sinica，2012，40（1）：147－154.）

［5］JI Zhu，Liu K J R.Multi－stage Pricing Game for Collusion Resistant Dynamic Spectrum Allocation［J］.IEEE Journal on Selected Areas in Communications，2009，26（1）：182－191.

［6］PENG Chunyi，ZHENG Haitao，Zhao B Y.Utilization and Fairness in Spectrum Assignment for Opportunistic Spectrum Access［J］.Mobile Networks and Applications，2006，11（4）：555－576.

［7］El－Nainay M Y.Island Genetic Algorithm－Based Cognitive Networks ［D］.Blacksburg，USA：Virginia Polytechnic Institute and State University，2009.

［8］柴爭義，劉芳.基于免疫克隆選擇優(yōu)化的認知無線網(wǎng)絡(luò)頻譜分配 ［J］.通信學(xué)報，2010，31（11）：92－100.（CHAI Zhengyi，LIU Fang.Spectrum Allocation of Cognitive Wireless Network Based on Immune Clone Selection Optimization［J］.Journal on Communication，2010，31（11）：92－100.）

［9］ZHAO Zhijin，PENG Zhen，ZHENG Shilian.Cognitive Radio Spectrum Allocation Using Evolutionary Algorithms［J］.IEEE Transactions on Wireless Communications，2009，8（9）：4421－4425.

［10］柴爭義，劉芳，朱思峰.混沌量子克隆算法求解認知無線網(wǎng)絡(luò)頻譜分配問題 ［J］.物理學(xué)報，2011，60（6）：068803.（CHAI Zhengyi，LIU Fang，ZHU Sifeng.Chaos Quantum Clonal Algorithm for Spectrum Allocation of Cognitive Wireless Network［J］.Acta Physica Sinica，2011，60（6）：068803.）

［11］LIU Yingting，ZHANG Hailin，HUI Leifang，et al.Single Relay Selection for Bidirectional Cooperative Networks with Physical－Layer Network Coding［J］.ETRI Journal，2012，34（1）：102－105.

［12］劉芳，王爽，柳瑩瑩，等.基于改進量子旋轉(zhuǎn)門的量子進化數(shù)據(jù)聚類 ［J］.電子學(xué)報，2011，39（9）：2008－2013.（LIU Fang，WANG Shuang，LIU Yingying，et al.A Quantum－Inspired Evolutionary Algorithm Based on a Modified Quantum Rotate Gate for Data Clustering［J］.Acta Electronica Sinica，2011，39（9）：2008－2013.）

［13］游曉明，劉升，王裕明.基于量子計算模型的混合進化算法及其性能分析 ［J］.電子學(xué)報，2012，40（4）：856－860.（YOU Xiaoming，LIU Sheng，WANG Yuming.Hybrid Evolutionary Algorithm Based on Quantum Computing and Performance Analysis［J］.Acta Electronica Sinica，2012，40（4）：856－860.）