一種基于改進(jìn)顏色敏感圖論著色的頻譜分配算法*

何建強 滕志軍 劉 皎

（1.商洛學(xué)院電子信息與電氣工程學(xué)院 商洛 726000）（2.東北電力大學(xué)信息工程學(xué)院 吉林 132012）

1 引言

在移動通信系統(tǒng)某些固定頻段中，授權(quán)頻譜大多處于空閑狀態(tài)，而一些頻段的頻譜卻又非常擁擠［1］。枯竭的頻譜資源與較低的利用率之間的矛盾日益突顯，固定的頻譜分配方式是導(dǎo)致頻譜利用率低下的主要原因［2］。認(rèn)知無線電技術(shù)被認(rèn)為是解決頻譜資源利用率低下的最有效方法，它能夠根據(jù)認(rèn)知用戶需求，提高網(wǎng)絡(luò)吞吐量。

在認(rèn)知無線電網(wǎng)絡(luò)中，實現(xiàn)頻譜資源的合理有效分配是重點和難點性問題［3］。博弈論與圖論是目前比較常用的頻譜分配算法，博弈論能夠較好地解決頻譜分配中的沖突問題，圖論主要是對系統(tǒng)總體效益實現(xiàn)最優(yōu)分配［4］。本文主要在顏色敏感圖論著色（color sensitive graph coloring，CSGC）算法的基礎(chǔ)上，在頻譜分配過程中，對認(rèn)知用戶的分配效益和公平性進(jìn)行考慮，在保證系統(tǒng)總效益的前提下兼顧用戶分配的公平性。

2 系統(tǒng)模型

假設(shè)認(rèn)知無線電系統(tǒng)中有N個等待分配頻譜的認(rèn)知用戶，每個認(rèn)知用戶的標(biāo)號n∈[0，N-1]；另有M個可用的信道，則信道的標(biāo)號m∈[0，M-1]。假設(shè)在一個分配周期里不存在干擾，系統(tǒng)中的變化遠(yuǎn)遠(yuǎn)小于外部環(huán)境的變化，各矩陣參數(shù)是保持不變的，各矩陣的定義如下［5］：

1）空閑頻譜矩陣L

在認(rèn)知無線通信系統(tǒng)中，由于同時存在著授權(quán)用戶和認(rèn)知用戶，當(dāng)授權(quán)用戶使用某一頻段頻譜時，認(rèn)知用戶則不能使用，即為頻譜占用，反之為空閑頻譜。其中，N是認(rèn)知用戶數(shù)，M為總的頻帶數(shù)。ln，m=1表示用戶n可以使用頻帶m，反之，ln，m=0表示用戶n不可以使用頻帶m。

當(dāng) Cn，k，m=1時，表示認(rèn)知用戶 n和 k在同時使用頻帶 m 時會產(chǎn)生干擾。當(dāng) n=k時，Cn，n，m=1-ln，m，只由空閑頻譜矩陣L決定。

3 本文算法模型

用最大化總帶寬（Max-Sum-Bandwidth，MSB）［6］為頻譜分配的最優(yōu)化目標(biāo)函數(shù)，其數(shù)學(xué)表達(dá)式為

它的含義為最大化頻譜的效益，其中∧N，M表示所有滿足條件的無干擾的頻譜分配矩陣A的集合。

本文采用協(xié)作式和非協(xié)作式兩種方式，相應(yīng)的標(biāo)號準(zhǔn)則［7］如下：

1）協(xié)作式最大化總帶寬（Collaborative-Max-Sum-Bandwidth，CMSB）準(zhǔn)則，相應(yīng)的節(jié)點標(biāo)號和顏色表達(dá)式為其中，Dn，m表示認(rèn)知用戶n分配到頻譜m，與該用戶不能同時使用頻譜m的有干擾沖突的用戶數(shù)。定義為。認(rèn)知用戶使用頻譜m后，對整個系統(tǒng)產(chǎn)生的效益為。

采用協(xié)作式最大化總帶寬的標(biāo)簽準(zhǔn)則，不僅提高頻譜利用率，而且考慮到頻譜分配過程中用戶之間的干擾關(guān)系，使頻譜利用率最大化，系統(tǒng)性能達(dá)到全局最優(yōu)。

2）非協(xié)作式最大化總帶寬（Non-Collaborative-Max-Sum-Bandwidth，NMSB）準(zhǔn)則［8］，相應(yīng)的節(jié)點標(biāo)號和顏色表達(dá)式為

非協(xié)作式最大化總帶寬的標(biāo)簽準(zhǔn)則，沒有考慮用戶之間的干擾，用戶與用戶是非合作的關(guān)系，每個用戶都是自私的，都只考慮自己的效益而忽略對整個系統(tǒng)產(chǎn)生的影響。

3）最 大 系 統(tǒng) 公 平（Max-Proportional-Fair，MPF）準(zhǔn)則［9］：通過度量不同頻譜單元分配結(jié)果的公平性，進(jìn)行頻譜分配，其數(shù)學(xué)表達(dá)式如下：

最大系統(tǒng)公平（Collaborative-Max-Proportional-Fair，CMPF）準(zhǔn)則，相應(yīng)的節(jié)點標(biāo)號和顏色表達(dá)式［10］為

4 改進(jìn)的頻譜分配算法

本文繼承了顏色敏感圖論著色的思想，提出一種改進(jìn)的頻譜分配算法，系統(tǒng)效益與用戶公平性兼顧。所提算法首先采用最大化總帶寬作為顏色敏感圖論著色頻譜分配的目標(biāo)函數(shù)，同時考慮認(rèn)知用戶間分配的公平性，采用最大系統(tǒng)公平準(zhǔn)則對頻譜二次分配，從而避免了算法只通過追求系統(tǒng)總效益導(dǎo)致分配公平性較弱的問題。兼顧系統(tǒng)公平性對頻譜進(jìn)行分配，更好改善認(rèn)知用戶間的公平性，提高頻譜利用率，優(yōu)化系統(tǒng)性能。

在初次對頻譜進(jìn)行分配時，以最大化總帶寬為目標(biāo)函數(shù)，若部分用戶的通信要求未被滿足，則根據(jù)最大系統(tǒng)公平準(zhǔn)則對頻譜再次分配。

算法流程如下：

步驟1初始化；

步驟2選擇最大化總帶寬準(zhǔn)則，計算具有最大效益的用戶；

步驟3根據(jù)準(zhǔn)則分配頻譜；

步驟4更新拓?fù)洌诳捎妙l譜列表中刪除與獲得頻譜用戶有沖突的用戶，同時刪除這些節(jié)點以該顏色相連的邊。將已滿足需求的用戶暫時退出分配；

步驟5判斷圖是否為空，若圖為空，結(jié)束分配；若圖不為空，則執(zhí)行步驟6；

步驟6根據(jù)最大系統(tǒng)公平準(zhǔn)則分配頻譜；

步驟7判斷圖是否為空，若圖為空，結(jié)束分配；若圖不為空，返回步驟4；

步驟8本周期分配結(jié)束。

5 本文算法的仿真驗證

下面通過Matlab進(jìn)行仿真驗證，對本文算法和改進(jìn)前的CSGC與最大系統(tǒng)公平算法進(jìn)行比較。

設(shè)置信道數(shù)從5～30，進(jìn)行10 000次仿真實驗，從圖1和圖2中可以看出，改進(jìn)算法、CSGC算法和最大系統(tǒng)公平算法都會隨著信道數(shù)增加，系統(tǒng)效益增大，最大系統(tǒng)公平算法系統(tǒng)總效益最低，本文算法系統(tǒng)總效益明顯高于其他算法，使系統(tǒng)得到優(yōu)化。圖1為協(xié)作式下系統(tǒng)效益，圖2為非協(xié)作式下系統(tǒng)效益，從圖中可以看出，協(xié)作式下系統(tǒng)性能要優(yōu)于非協(xié)作式。

圖1 在CMSB下系統(tǒng)總效益隨信道數(shù)變化

設(shè)置信道數(shù)為10，認(rèn)知用戶數(shù)從5～20，進(jìn)行10000仿真實驗，從圖3和圖4中可以得知，改進(jìn)算法、CSGC算法和最大系統(tǒng)公平算法都隨著認(rèn)知用戶數(shù)的增多，系統(tǒng)效益呈下降趨勢，本文算法下降幅度最小，與傳統(tǒng)算法相比較，系統(tǒng)效益更好，分配結(jié)果更理想。圖3為協(xié)作式下系統(tǒng)效益，圖4為非協(xié)作式下系統(tǒng)效益，從圖中可以看出，協(xié)作式下頻譜利用率要高于非協(xié)作式。

圖2 在NMSB下系統(tǒng)總效益隨信道數(shù)變化

圖3 在CMSB下系統(tǒng)總效益隨認(rèn)知用戶數(shù)變化

圖4 在NMSB下系統(tǒng)總效益隨認(rèn)知用戶數(shù)變化

6 結(jié)語

本文所提算法，結(jié)合了最大化總帶寬與最大系統(tǒng)公平兩種準(zhǔn)則，提出一種改進(jìn)的頻譜分配算法，仿真驗證得出，改進(jìn)的算法比單一算法更能提高頻譜使用效率，大大提高系統(tǒng)效益。