WRAN中基于量子進化的頻譜分配

王若慧，張華偉

（1.山西大學 工程學院，太原030013；

2.河南財經政法大學 計算機與信息工程學院，鄭州 450000）

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

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

1 WRAN頻譜分配模型

1.1 WRAN簡介

WRAN采用IEEE 802.22技術標準，使用位于54～862MHz VHF／UHF頻段中的電視頻帶，可與電視業務共存且不對其產生有害干擾［3，11］.WRAN具有較大的覆蓋范圍，最大可達100km，可為邊遠地區提供有效的網絡接入服務.

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

1.2 WRAN連接模型

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

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

1.3 WRAN頻譜分配模型

基于圖著色的頻譜分配理論，結合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.顯然，當ln，m＝0時，有bn，m＝0.在WRAN中，效益矩陣定義為帶寬速率，與傳輸時的調制方式及編碼速率有關.參數值設置可參考IEEE 802.22的WRAN提案［3］.

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

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

2 基于量子進化頻譜分配的實現

2.1 量子進化計算

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

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

2.2 算法實現

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

1）初始化.

4）計算P（g）中種群個體的適應度，保存最優個體.

本文直接將網絡效益U（R）作為適應度函數.由于是最大化網絡效益，所以適應度越大越好.適應度最大的個體即為最優個體，其所對應的分配矩陣A即為所求.

5）算法終止條件判斷.

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

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

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

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

其中：θ0為初始旋轉角度，本文設為0.05π；s1和s2用于控制旋轉方向；Fit（x）和Fit（b）用于自適應地調整轉角大小.因此，旋轉角度可根據個體的適應度自適應地調整.

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

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

3 仿真實驗

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

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

表1 網絡收益比較（M＝N＝10）Table 1 Comparison of network profits（M＝N＝10）

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

下面驗證在不同認知用戶數量和可用頻譜數量下網絡的收益情況，并與相關算法進行比較，結果分別如圖2和圖3所示.

圖2 可用頻譜與網絡收益的關系Fig.2 Relationship between available spectrum and network profits

圖3 認知用戶數量與網絡收益的關系Fig.3 Relationship between number of secondary users and network profits

由圖2和圖3可見，隨著可用頻譜數量和認知用戶數量的增加，網絡收益值逐漸增加，本文算法的增益優于已有算法，表明本文算法尋優能力較強.

構建IEEE 802.22的WRAN系統仿真平臺：根據WRAN的覆蓋范圍，考慮一個無限大的區域，完成主用戶和認知用戶的初始化.WRAN系統由基站BS實現集中控制：獲得各小區空閑的TV頻譜集合后，由BS控制各小區內的認知用戶對空閑TV頻譜的占用.結合圖1，空閑頻譜矩陣為

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

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

［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］王欽輝，葉保留，田宇，等.認知無線電網絡中頻譜分配算法 ［J］.電子學報，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］柴爭義，劉芳.基于免疫克隆選擇優化的認知無線網絡頻譜分配 ［J］.通信學報，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］柴爭義，劉芳，朱思峰.混沌量子克隆算法求解認知無線網絡頻譜分配問題 ［J］.物理學報，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］.電子學報，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］.電子學報，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.）