王若慧，張華偉

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

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

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

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

1 WRAN頻譜分配模型

1.1 WRAN簡(jiǎn)介

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

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

1.2 WRAN連接模型

圖1 WRAN拓?fù)涫疽鈭DFig.1 Topology of WRAN

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

1.3 WRAN頻譜分配模型

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

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

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

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

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

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

2.1 量子進(jìn)化計(jì)算

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

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

2.2 算法實(shí)現(xiàn)

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

1）初始化.

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

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

5）算法終止條件判斷.

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

6）對(duì)量子種群Q（g）進(jìn)行克隆，生成新的量子種群Q′（g）.

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

假設(shè)xi和bi分別是經(jīng)過(guò)量子觀測(cè)后的普通個(gè)體x和最佳個(gè)體b第i位上的值，這兩個(gè)個(gè)體的適應(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ù)個(gè)體的適應(yīng)度自適應(yīng)地調(diào)整.

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

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

3 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

綜上所述，針對(duì)認(rèn)知無(wú)線網(wǎng)絡(luò)中的頻譜分配問(wèn)題，本文設(shè)計(jì)了一種基于量子進(jìn)化的WRAN頻譜分配算法，并驗(yàn)證了算法的有效性.實(shí)驗(yàn)結(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］王欽輝，葉保留，田宇，等.認(rèn)知無(wú)線電網(wǎng)絡(luò)中頻譜分配算法 ［J］.電子學(xué)報(bào)，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］柴爭(zhēng)義，劉芳.基于免疫克隆選擇優(yōu)化的認(rèn)知無(wú)線網(wǎng)絡(luò)頻譜分配 ［J］.通信學(xué)報(bào)，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］柴爭(zhēng)義，劉芳，朱思峰.混沌量子克隆算法求解認(rèn)知無(wú)線網(wǎng)絡(luò)頻譜分配問(wèn)題 ［J］.物理學(xué)報(bào)，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］劉芳，王爽，柳瑩瑩，等.基于改進(jìn)量子旋轉(zhuǎn)門的量子進(jìn)化數(shù)據(jù)聚類 ［J］.電子學(xué)報(bào)，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ì)算模型的混合進(jìn)化算法及其性能分析 ［J］.電子學(xué)報(bào)，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.）