劉俊彤，王可人，張興良，馮 輝

（解放軍電子工程學(xué)院，安徽 合肥 230037）

0 引言

隨著無線通信技術(shù)的高速發(fā)展，人們對無線通信業(yè)務(wù)需求的不斷增加與無線頻譜資源匱乏之間的矛盾越來越尖銳。針對頻譜資源的不足，認(rèn)知無線電（Cognitive Radio，CR）［1］網(wǎng)絡(luò)中的動態(tài)頻譜分配技術(shù)（Dynamic Spectrum Allocation，DSA）能夠靈活地使用空閑頻譜，實(shí)現(xiàn)空閑頻譜的再利用，從而提高頻譜利用率［2］。在目前的研究中，DSA 技術(shù)包含非合作DSA 與合作DSA，非合作DSA 是指非授權(quán)用戶進(jìn)行頻譜檢測，在授權(quán)用戶不使用的頻段進(jìn)行頻譜接入。而合作DSA 則是采用特定的算法對頻譜資源進(jìn)行統(tǒng)一的動態(tài)分配［3-4］。

現(xiàn)有文獻(xiàn)多對合作DSA 進(jìn)行分析討論，文獻(xiàn)［5］采用頻譜拍賣的方式將主用戶的空閑頻段分配給次級用戶，分別解決了拍賣過程中可能出現(xiàn)的次級用戶不誠實(shí)報(bào)價和共謀的問題，同時還有效地解決了網(wǎng)絡(luò)效益降低的問題；文獻(xiàn)［6］提出了一種基于單頻段多贏家拍賣的分配算法，該算法在原始貪婪算法的基礎(chǔ)上增加了多重貪婪策略，以較低的計(jì)算復(fù)雜度獲得了較優(yōu)的解，提高了賣家的收益，有效抑制共謀的發(fā)生，同時提高了拍賣的經(jīng)濟(jì)收益。文獻(xiàn)［7］提出一種以用頻沖突等級最小的頻譜動態(tài)指配數(shù)學(xué)模型，將頻譜指配問題歸結(jié)為沖突等級評價數(shù)學(xué)函數(shù)的優(yōu)化問題，該方法能夠有效地求解頻率指配過程中出現(xiàn)的問題。諸如此類對合作DSA 技術(shù)的研究很多，但是，這些研究所建立的系統(tǒng)模型往往不完善，缺乏對業(yè)務(wù)模型中不同業(yè)務(wù)需求等級的分析，對不同認(rèn)知用戶接入需求度的差異性考慮較少。

針對上述問題，本文提出一種基于不同業(yè)務(wù)需求等級的動態(tài)頻譜分配算法。

1 系統(tǒng)模型與問題描述

1.1 系統(tǒng)模型

在認(rèn)知無線網(wǎng)絡(luò)中，合作DSA 由中心控制器來協(xié)調(diào)和管理CR 用戶對空閑頻譜的使用，通過收集其控制范圍內(nèi)各CR 用戶的頻譜感知信息，建立可用頻譜數(shù)據(jù)庫，通過多個CR 用戶之間相互交換分配信息、協(xié)商頻譜分配，合力達(dá)到全局最優(yōu)的頻譜分配的目的［8］。中心控制器周期性的進(jìn)行頻譜分配，認(rèn)知用戶向中心控制器提供下一個分配周期內(nèi)所要釋放的頻譜資源和新需求的頻譜資源。系統(tǒng)基本模型如圖1所示。

圖1 動態(tài)頻譜分配系統(tǒng)模型Fig.1 The model of DSA system

該模型中，系統(tǒng)的頻譜接入機(jī)制可描述如下：對于請求接入的CR 用戶，中心控制器判斷頻譜空間中是否存在可供該接入請求使用的空閑頻段，若存在，系統(tǒng)對該請求分配一個空閑頻段，若不存在，那么該接入請求被阻塞。該模型可以使認(rèn)知用戶按照一定的效用函數(shù)共享空閑頻譜資源，但沒有考慮不同認(rèn)知用戶對頻譜接入需求的差異性，為完善DSA系統(tǒng)模型，該文提出一種基于不同業(yè)務(wù)需求等級的DSA 系統(tǒng)模型。

圖2給出了基于業(yè)務(wù)需求等級的動態(tài)頻譜分配模型。該模型將認(rèn)知網(wǎng)絡(luò)中的CR 用戶依據(jù)其不同的業(yè)務(wù)需求等級分為一級用戶和二級用戶，其中一級用戶的接入優(yōu)先級高于二級用戶，二級用戶的接入狀態(tài)對一級用戶可視作透明的。

圖2 不同業(yè)務(wù)需求等級DSA 分配模型Fig.2 The model of DSA system with different levels of service demand

在該模型中，系統(tǒng)的頻譜接入機(jī)制可描述如下：

1）一級接入請求：對于一個一級接入請求，當(dāng)頻譜空間中存在可供該接入請求使用的空閑頻段時，系統(tǒng)對該接入請求分配一個空閑信道；若頻譜空間中不存可供該接入請求使用的空閑頻段，但系統(tǒng)存在某個二級用戶接入且該接入頻段可供該一級用戶接入使用時，那么中心控制器將終止此二級用戶的接入，空出頻段來提供一級用戶的接入；若以上兩種情況均不存在，那么該一級接入請求被阻塞。

2）一級接入完成：一級接入需求結(jié)束時，中心控制器自動釋放其占用的信道。

3）二級接入請求：對于一個二級接入請求，中心控制器首先判斷頻譜空間中是否存在可供該接入請求使用的空閑頻段，若存在，則系統(tǒng)對該接入請求分配一個空閑信道，若不存在，那么該二級接入請求被阻塞。

4）二級接入完成：二級接入需求結(jié)束時，中心控制器自動釋放其占用的信道。

該模型對請求接入的認(rèn)知用戶采取分級操作，對不同需求等級的認(rèn)知用戶賦予不同的接入優(yōu)先級，更加合理地使用了空閑頻譜資源。

1.2 問題描述

根據(jù)分析，認(rèn)知無線網(wǎng)絡(luò)中的DSA 問題可以等效為圖著色問題。設(shè)有P 個認(rèn)知用戶競爭接入Q段不連續(xù)的頻段，將每個認(rèn)知用戶抽象為一個頂點(diǎn)，將每段可用頻段映射為一種顏色，則可將頻譜分配問題抽象為圖著色問題G= （V，E，L）［9］，其中參數(shù)定義如下：

定 義 2： 可 用 信 道 矩 陣 L，L =｛lij|lij∈｛0，1｝｝P×Q，lij=1／0表示CR用戶i可以／不可以使用信道j。

定 義 3： 干 擾 關(guān) 系 矩 陣 E，E =｛eij|eij∈｛0，1｝｝P×P，eij=1／0表示CR 用戶i與CR用戶j間有干擾／無干擾。若有干擾，則i與j不能同時占用相同的頻段；若無干擾，則i與j 可以占用相同的頻段。由于i與j 之間的干擾是相互的，因此矩陣E 為對稱矩陣。

定義4：信道分配矩陣A，A=｛aij|aij∈｛0，1｝｝P×Q，aij=1／0表示CR用戶i已分配／未分配使用信道j。當(dāng)滿足以下條件時A 是有效的：

定義5：效用函數(shù)R，對給定的信道分配矩陣A，認(rèn)知網(wǎng)絡(luò)會獲得相應(yīng)的網(wǎng)絡(luò)效益，該效用的大小用認(rèn)知接入用戶量的多少表示。

以圖3為例，頂點(diǎn)1～4分別代表4個不同的認(rèn)知接入用戶，其中1和2為一級用戶，3和4為二級用戶；頂點(diǎn)間連線表示相連接的認(rèn)知用戶不能同時占用相同的頻段，否則將產(chǎn)生干擾；Ⅰ、Ⅱ、Ⅲ分別代表3個不同的主用戶，其占用頻段分別用a、b、c表示，位于主用戶覆蓋范圍（虛線圈）內(nèi)的認(rèn)知用戶不能復(fù)用主用戶占用的頻段，主用戶覆蓋范圍外的認(rèn)知用戶可將該主用戶占用的頻段視為空閑頻段。

根據(jù)分配優(yōu)先級和最大化用戶接入量，可得其中一個有效的信道分配矩陣

圖3 問題描述Fig.3 Description of the problem

該問題屬于NP完全問題，當(dāng)圖較大時，窮舉法在呈指數(shù)遞增的狀態(tài)空間中尋求最優(yōu)解會耗費(fèi)太多的時間和資源。鑒于此，該文在綜合考慮頻譜資源分配問題的基礎(chǔ)上，借鑒自然界生物進(jìn)化過程中適者生存的競爭機(jī)制，選用遺傳算法（Genetic Algorithm，GA）解決該問題，并在基本遺傳算法的基礎(chǔ)上設(shè)計(jì)了一種基于t分布隨機(jī)擾動的變異方案，提高了該算法對本模型的整體尋優(yōu)能力。

遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法［10］。將問題的一個解當(dāng)作生存環(huán)境中的一個個體，以目標(biāo)函數(shù)值或其變化形式來評價個體對環(huán)境的適應(yīng)能力，模擬個體組成群體的進(jìn)化過程，優(yōu)勝劣汰，最終獲得最好的個體。盡管遺傳算法已經(jīng)廣泛應(yīng)用于處理各類優(yōu)化問題中，但仍存在諸如收斂速度慢，搜索效率低，容易陷入局部最優(yōu)等問題。國內(nèi)外學(xué)者做了諸多努力來尋求更好的改進(jìn)方法，文獻(xiàn)［11］提出一種等級變異的選擇算法，將變異尺度分成若干等級，提高了免疫算法的尋優(yōu)性能；文獻(xiàn)［12］為提高變異強(qiáng)度，提出了一種基于強(qiáng)化變異算子的遺傳算法，在尋優(yōu)速度和尋優(yōu)質(zhì)量上均有較大改進(jìn)。通過分析比較一些學(xué)者提出的改進(jìn)算法，我們知道，柯西變異的全局探索能力較強(qiáng)，能夠有效地保持種群的多樣性；而高斯變異的局部開發(fā)能力較強(qiáng)，可以保證進(jìn)化后期的收斂速度。為綜合兩者的優(yōu)點(diǎn)，該文提出一種基于t分布變異的遺傳算法。

t（n）分布又稱學(xué)生分布，含有參數(shù)自由度n，當(dāng)n=1時，t（1）服從柯西分布；當(dāng)n→∞時，t（∞）服從標(biāo)準(zhǔn)高斯分布，一般n取值較大（大于50）時即可認(rèn)為t分布近似服從標(biāo)準(zhǔn)高斯分布。因此可以通過調(diào)節(jié)參數(shù)n，使算法前期具有良好的全局探索能力，而在進(jìn)化后期又具備較優(yōu)的局部開發(fā)性能，以此來提高算法的整體尋優(yōu)能力。

t分布變異遺傳算法就是在原有的個體上附加一個服從t分布的隨機(jī)擾動，即：

t分布變異首先用歷史最優(yōu)染色體替換當(dāng)前最差染色體形成中間種群，然后對中間種群的染色體按式（3）變異，并計(jì)算當(dāng)前染色體的目標(biāo)函數(shù)值，而后繼續(xù)執(zhí)行GA 基本尋優(yōu)運(yùn)算。如此充分利用了當(dāng)前個體的已知信息進(jìn)行擾動，增加了種群狀態(tài)的多樣性，有利于算法進(jìn)行全局搜索，同時也提高了算法的搜索速度。

2 基于t分布變異GA 的認(rèn)知無線電頻譜分配算法

在基于t分布變異GA 的認(rèn)知無線電頻譜分配算法中，每一條染色體編碼采用的二進(jìn)制串表示一種可能的頻譜分配結(jié)果，染色體中的二進(jìn)制碼為1／0代表該可用頻譜已分配／未分配給相應(yīng)的認(rèn)知用戶。由于可用信道矩陣L 中值為0 的元素位置相對應(yīng)的信道分配矩陣A 中元素值必為0，故僅對與L 中值為1 元素對應(yīng)的A 中的元素進(jìn)行染色體編碼，即染色體的個數(shù)等于L 中值為1的元素的個數(shù)。圖4給出了P=4，Q=3時的染色體編碼結(jié)構(gòu)示例。

圖4中xi= ［1，0，0，1，0，0，1，1］ 為初始種群 中第i個染色體的編碼結(jié)果，對結(jié)果進(jìn)行適應(yīng)度評價時需要將其映射為信道分配矩陣A，映射過程可表述為：將染色體編碼后的每一位按行逐個填充到與L 中值為1的元素位置相對應(yīng)的A 的元素。

圖4 染色體編碼結(jié)構(gòu)示例Fig.4 The example of chromosome coding structure

染色體編碼應(yīng)滿足如下約束：對任意空閑頻段m（0≤m≤Q），信道分配矩陣A 中的元素應(yīng)滿足aim·ajm·eij=0。由于該分配所要實(shí)現(xiàn)的目標(biāo)是最大化用戶接入量，故將R（A）做為適應(yīng)度函數(shù)，隨著進(jìn)化代的進(jìn)行，適應(yīng)度函數(shù)值應(yīng)向著增加的趨勢改變，當(dāng)達(dá)到最大迭代次數(shù)時，算法終止，此時對應(yīng)的信道分配矩陣A 即為算法最終的分配結(jié)果。該分級模型中，首先對N 個一級用戶應(yīng)用該算法對Q 段空閑頻段進(jìn)行分配，繼而將剩余的空閑頻段應(yīng)用該算法分配給M 個二級用戶。

綜上所述，該文提出的基于t分變異GA 算法的頻譜分配流程如下：

1）算法初始化，初始化種群規(guī)模S，變異概率pm，最大迭代次數(shù)U。

4）交叉產(chǎn)生新個體，保留新個體中經(jīng)過映射后滿足aim·ajm·eij=0條件的個體，并補(bǔ)充新個體至總?cè)阂?guī)模S。

5）t分布變異操作，變異操作在原有的個體上附加一個服從t分布的隨機(jī)擾動，Xi（t）=Xi（t）+k×Xi（t）×t（n），并計(jì)算當(dāng)前染色體的目標(biāo)函數(shù)值，而后繼續(xù)執(zhí)行GA 基本尋優(yōu)運(yùn)算，充分利用了當(dāng)前個體的已知信息進(jìn)行擾動。

6）適應(yīng)度評價，對子代群體進(jìn)行適應(yīng)度評價，從父代群體與子代群體中選擇適應(yīng)度最高的個體，替換當(dāng)前子代群體中的最差個體，并將該最佳個體保存至Bi中。如此，保留了遺傳操作過程中的最佳個體。

7）判斷是否達(dá)到最大迭代次數(shù)U，若達(dá)到，將Bi中保存的二進(jìn)制串映射為A 的形式；否則，繼續(xù)執(zhí)行遺傳算法操作。

3 仿真及性能分析

仿真環(huán)境設(shè)置：取認(rèn)知接入用戶的個數(shù)P =25，其中一級接入用戶N =10，二級接入用戶M =15，空閑頻段個數(shù)Q=28，仿真過程中，信道可用矩陣L25×28與干擾關(guān)系矩陣E25×25由系統(tǒng)隨機(jī)生成，系統(tǒng)獲得的網(wǎng)絡(luò)效益以用戶接入量衡量，由于考慮不同需求等級的認(rèn)知用戶接入系統(tǒng)會產(chǎn)生不同的網(wǎng)絡(luò)效益，因此，設(shè)一級用戶接入系統(tǒng)獲得的網(wǎng)絡(luò)效益值為2，二級用戶接入系統(tǒng)獲得的網(wǎng)絡(luò)效益為1。算法采用二進(jìn)制編碼方式，基本參數(shù)設(shè)置如下：交叉概率為0.6，變異概率為0.001，種群規(guī)模為30，最大進(jìn)化代數(shù)為500。在對算法進(jìn)行t分布變異操作時，取n=1時，變異類型為柯西變異，取n=100時，變異類型為高斯變異，由于高斯變異中期收斂速度較快，柯西變異全局搜索能力強(qiáng)，故對進(jìn)化代數(shù)≤200時采用高斯變異，當(dāng)進(jìn)化代數(shù)＞200時采用柯西變異。

由圖5可見，加入t變異操作后，GA算法的收斂速度和整體尋優(yōu)能力較普通GA 算法有明顯改善，且與窮舉法所獲得的網(wǎng)絡(luò)效益并無顯著差異，但窮舉法的計(jì)算復(fù)雜度為2q（q 為染色體編碼位數(shù)），需要耗費(fèi)過長的運(yùn)算時間。仿真結(jié)果表明了t變異GA算法對處理該問題的有效性和可用性。

為了進(jìn)一步對比所提出的基于不同需求等級DSA 模型與不考慮需求等級DSA 模型對系統(tǒng)性能產(chǎn)生的差異，圖6 給出了20 種不同初始條件下（L25×28與E25×25不同）兩種模型經(jīng)過DSA 算法分配后各自獲得的網(wǎng)絡(luò)效益。

圖5 算法性能比較Fig.5 Comparison chart of the algorithms

圖6 分級模型與未分級模型網(wǎng)絡(luò)效益比較Fig.6 The comparison chart of the system profits between classification model and common model

由圖6可見，不同實(shí)驗(yàn)初始條件下，分級模型獲得的網(wǎng)絡(luò)效益均高于未分級模型獲得的網(wǎng)絡(luò)效益，在20次試驗(yàn)中，分級模型獲得的平均網(wǎng)絡(luò)效益為30.05，未分級模型獲得的平均網(wǎng)絡(luò)效益為28.70。仿真結(jié)果表明了該分級模型對處理不同需求等級DSA 分配問題的優(yōu)越性。

圖7給出了10種不同初始條件下的DSA 分配結(jié)果，在10 次試驗(yàn)中，一級用戶的平均接入率為94%，二級用戶的平均接入率約為77%，可見分配優(yōu)先滿足了一級用戶的接入請求，同時也基本保證了二級用戶的接入。表明該DSA 分配方法對處理不同需求等級用戶接入的有效性。

圖7 頻譜分配結(jié)果Fig.7 Results of the dynamic spectrum allocation

4 結(jié)論

為解決CR 網(wǎng)絡(luò)中不同業(yè)務(wù)需求等級頻譜分配問題，本文綜合考慮接入用戶的業(yè)務(wù)需求等級與系統(tǒng)的網(wǎng)絡(luò)效益，提出了一種基于不同需求等級改進(jìn)的動態(tài)頻譜分配算法。該算法將頻譜資源分配建模為0-1整數(shù)規(guī)劃問題，提出了一種基于t分布變異GA的認(rèn)知無線電頻譜分配算法。仿真結(jié)果表明：t變異GA 算法對處理該問題具有很高的有效性和可用性；在處理不同需求等級次用戶接入問題上，該文提出的分級模型可顯著提高系統(tǒng)的網(wǎng)絡(luò)效益。

本文所提模型假設(shè)次用戶的接入需求等級不發(fā)生變化，對于次用戶接入需求等級隨條件變化的系統(tǒng)模型有待于進(jìn)一步研究。

［1］MITOLA J.Cognitive radio architecture evolution［J］.Processings of the IEEE，2009，97（4）：626-641.

［2］NIYATO D，HOSSAIN E，ZHU H.Dynamic spectrum access in IEEE802.22based cognitive wireless networks：agame theoretic model for competitive spectrum bidding and pricing［J］.IEEE Wireless Communications，2009，16（2）：16-23.

［3］MODY A N，SHERMAN M J，MARTINEZ R.Survey of IEEE standards supporting cognitive radio and dynamic spectrum access［C］／／Proceedings of the IEEE MILCOM.San Diego，CA，USA，2008：1-7.

［4］ETSI.Reconfigurable Radio Systems（RRS）；Cognitive Radio System Concept［R］.EU：ETSI TR 102 802 V1.1.1，2010.

［5］ZHOU X，ZHENG H.Breaking bidder collusion in large-scale spectrum auctions［C］／／MobiHoc'10，Proceedings of the Eleventh ACM International Symposium on Mobile Ad Hoc Networking and Computing.Chicago，Illinois，USA：2010.

［6］張文柱，王凌云.基于單頻段多贏家拍賣的動態(tài)頻譜分配［J］.通信學(xué)報(bào)，2012，33（2）：1-6.

［7］楊奎.一種基于離散粒子群優(yōu)化的戰(zhàn)場動態(tài)頻譜指配策略［J］.電訊技術(shù)，2012，52（5）：755-760.

［8］HAN Z，ZHENG R，POOR H V.Repeated auctions with bayesian nonparametric learning for spectrum access in cognitive radio networks［J］.IEEE Transactions on Wireless Communications，2011，10（3）：890-900.

［9］Wang F，Krunz M，Cui S.Price-based spectrum management in cognitive radio networks［J］.IEEE Journal of Selected Topics in Signal Processing，2009，2（1）：74-87.

［10］Hwang S，He R S.Improving real-parameter genetic algorithm with simulated annealing for engineering problem［J］.Advances in Engineering Software，2006，37：406-418.

［11］宋丹，賴旭芝，吳敏.基于等級變異的克隆選擇算法［J］.模式識別與人工智能，2011，24（3）：438-443.

［12］Liu Fei，Zeng Guangzhou.Study genetic algorithm with reinforcement leaning to solve the TSP［J］.Expert Systems with Applications，2009（36）：6995-7001.