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

何建強 滕志軍 劉 皎

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

1 引言

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

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

2 系統模型

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

1）空閑頻譜矩陣L

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

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

3 本文算法模型

用最大化總帶寬（Max-Sum-Bandwidth，MSB）［6］為頻譜分配的最優化目標函數，其數學表達式為

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

本文采用協作式和非協作式兩種方式，相應的標號準則［7］如下：

1）協作式最大化總帶寬（Collaborative-Max-Sum-Bandwidth，CMSB）準則，相應的節點標號和顏色表達式為其中，Dn，m表示認知用戶n分配到頻譜m，與該用戶不能同時使用頻譜m的有干擾沖突的用戶數。定義為。認知用戶使用頻譜m后，對整個系統產生的效益為。

采用協作式最大化總帶寬的標簽準則，不僅提高頻譜利用率，而且考慮到頻譜分配過程中用戶之間的干擾關系，使頻譜利用率最大化，系統性能達到全局最優。

2）非協作式最大化總帶寬（Non-Collaborative-Max-Sum-Bandwidth，NMSB）準則［8］，相應的節點標號和顏色表達式為

非協作式最大化總帶寬的標簽準則，沒有考慮用戶之間的干擾，用戶與用戶是非合作的關系，每個用戶都是自私的，都只考慮自己的效益而忽略對整個系統產生的影響。

3）最 大 系 統 公 平（Max-Proportional-Fair，MPF）準則［9］：通過度量不同頻譜單元分配結果的公平性，進行頻譜分配，其數學表達式如下：

最大系統公平（Collaborative-Max-Proportional-Fair，CMPF）準則，相應的節點標號和顏色表達式［10］為

4 改進的頻譜分配算法

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

在初次對頻譜進行分配時，以最大化總帶寬為目標函數，若部分用戶的通信要求未被滿足，則根據最大系統公平準則對頻譜再次分配。

算法流程如下：

步驟1初始化；

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

步驟3根據準則分配頻譜；

步驟4更新拓撲，在可用頻譜列表中刪除與獲得頻譜用戶有沖突的用戶，同時刪除這些節點以該顏色相連的邊。將已滿足需求的用戶暫時退出分配；

步驟5判斷圖是否為空，若圖為空，結束分配；若圖不為空，則執行步驟6；

步驟6根據最大系統公平準則分配頻譜；

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

步驟8本周期分配結束。

5 本文算法的仿真驗證

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

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

圖1 在CMSB下系統總效益隨信道數變化

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

圖2 在NMSB下系統總效益隨信道數變化

圖3 在CMSB下系統總效益隨認知用戶數變化

圖4 在NMSB下系統總效益隨認知用戶數變化

6 結語

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