一種改進的CSGC頻譜分配算法

滕志軍，李 可

（東北電力大學信息工程學院，132012吉林吉林）

一種改進的CSGC頻譜分配算法

滕志軍，李 可

（東北電力大學信息工程學院，132012吉林吉林）

基于圖論著色的頻譜分配算法未充分考慮用戶實際帶寬需求，針對這一問題，本文在原算法基礎上提出了一種改進的CSGC頻譜分配算法.該算法引入了空閑頻譜和用戶請求兩個時間因子，通過設置用戶優(yōu)先級函數，在進行二次頻譜分配時最大限度地滿足用戶需求.仿真結果表明，該算法不僅保留了原CSGC算法的性能，而且大幅度提高了頻譜利用率.

圖論；頻譜；分配；CSGC；用戶優(yōu)先級

隨著無線通信技術的快速發(fā)展，無線用戶日益增加，使得頻譜資源變得越來越緊缺.由于頻譜資源是一種不可再生資源，因此如何更好的利用現有頻譜資源已經成為人們亟待需要解決的問題［1］.認知無線電概念的提出，有效的解決了頻譜資源緊缺的問題，提高了頻譜利用率.

目前，頻譜分配的經典算法有博弈論、圖論和競價拍賣.由于圖論著色算法有較好的靈活性和更高的實用性，因此，受到更多研究者的關注.文獻［2］提出了列表著色（list?coloring，LC）算法的頻譜分配模型，LC算法采用開放式頻譜接入的方式，在現有的干擾約束條件下，其目標是追求最大的頻譜分配數量.文獻［3］提出了顏色敏感圖論著色（color sensitive graph coloring，CSGC）算法的頻譜分配模型，CSGC算法考慮了頻譜分配中頻譜效益的差異性和干擾性，明顯地減少了干擾，提高了網絡吞吐量，使系統帶寬得到最大利用.文獻［4］提出了并行算法，將圖分解成多個子圖，通過同時對多個子圖著色方法來縮短頻譜分配周期，使其能夠更好適應外部無線通信環(huán)境的快速變化.

上述分配算法主要是對頻譜分配數量最大化研究，但缺乏對用戶實際帶寬需求的考慮，容易導致帶寬需求大的用戶分配到較小的頻譜，而帶寬需求小的用戶分配到較大的頻譜，不能更好的滿足用戶需求，從而造成頻譜資源的嚴重浪費.因此，本文在圖論的基礎上，提出一種基于用戶優(yōu)先級的頻譜分配算法，在對頻譜進行二次分配時，通過設置認知用戶的優(yōu)先級函數，最大限度滿足用戶需求，從資源分配和用戶需求雙重角度出發(fā)，提高頻譜分配的公平性和頻譜利用率，優(yōu)化系統性能.

1 傳統CSGC算法概述

1.1 CSGC算法模型的數學描述

顏色敏感圖論著色算法中包含空閑頻譜矩陣、效益矩陣、干擾矩陣和無干擾的頻譜分配矩陣，本文在此基礎上，加入了頻譜空閑時間矩陣和用戶需求時間矩陣.

假設認知無線電系統中有N個等待分配頻譜的認知用戶，則認知用戶的標號n∈［0，N-1］，有M個可用的空閑頻譜，則空間頻譜的標號m∈［0，M-1］．相對于外界通信環(huán)境變化時間而言，頻譜分配時間很短暫，則假設各矩陣在一個分配周期內是保持不變的，各矩陣的定義如下［5］：

1）空閑頻譜矩陣L

在認知無線通信系統中，同時存在著授權用戶和認知用戶，當授權用戶使用某一頻段頻譜時，認知用戶則不能使用，用空閑頻譜表示某個時間沒有授權用戶使用該頻段的頻譜．L＝｛ln，m｜ln，m∈｛0，1｝｝N×M，N為認知用戶數，M為總頻帶數．ln，m＝1為用戶n可以使用頻帶m，反之，ln，m＝0為用戶n不可以使用頻帶m．

2）效益矩陣B

B＝｛bn，m｝N×M，bn，m為認知用戶n使用可用頻譜m所獲得的效益．

3）干擾矩陣C

C＝｛Cn，k，m｝，Cn，k，m∈｛0，1｝N×N×M，為認知用戶n和k同時在信道m(xù)上產生的干擾．

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

4）無干擾的頻譜分配矩陣A

A＝｛an，m｜an，m∈｛0，1｝｝N×M，an，m＝1為將頻帶m分配給認知用戶n使用．A必須滿足無干擾條件：an，m·ak，m＝0，if Cn，k，m＝1；?n，k＜N，m＜M．

5）頻譜空閑時間矩陣W

W＝｛wm｝1×M為授權頻譜m的空閑時間．本文假設在一個分配周期內，每個授權頻譜m的空閑時間不發(fā)生變化．

6）認知用戶請求時間T

T＝｛tn｝N×1為認知用戶n的請求時間．本文假設在一個分配周期內，每個認知用戶n的請求時間不發(fā)生變化．

1.2 CSGC算法準則

采用最大化帶寬總和（max?sum?bandwidth，MSB）［6］為頻譜分配的最優(yōu)化目標函數，其數學表達式為

式（1）為最大化頻譜的效益，其中A∈∧N，M為所有滿足條件的無干擾的頻譜分配矩陣A的集合．

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

1）協作式最大帶寬總和（collaborative?max?sum?bandwidth，CMSB）準則［7］，相應的節(jié)點標號和顏色表達式為

式中，Dn，m表示認知用戶n分配到頻譜m，與該用戶不能同時使用頻譜m的有干擾沖突的用戶數．定義為認知用戶使用頻譜m后，對整個系統產生的效益為bn，m／（Dn，m＋1）．

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

2）非協作式最大帶寬總和（non?collaborative?max?sum?bandwidth，NMSB）準則［8］，相應的節(jié)點標號和顏色表達式為

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

2 基于用戶優(yōu)先級的改進型CSGC頻譜分配算法

在頻譜分配過程中，干擾關系決定著認知用戶所獲得的效益［9］，為避免干擾和沖突，提出了顏色敏感圖論的頻譜分配算法，減少了干擾［10］，但是卻沒有考慮用戶需求.本文繼承了顏色敏感圖論著色的思想，并考慮到用戶的需求，提出一種改進的CSGC頻譜分配算法.該算法的基本思想首先采用最大化帶寬總和作為顏色敏感圖論著色頻譜分配的最優(yōu)目標函數，同時考慮認知用戶的頻譜需求，提出用戶滿意度，根據認知用戶對當前頻譜分配的滿意程度設置用戶優(yōu)先級函數，通過認知用戶對頻譜需求的優(yōu)先程度進行頻譜的再次分配.

2.1 定義

定義1 用戶滿意度sn

認知用戶滿意程度與用戶的需求緊密相連，影響系統的穩(wěn)定性，決定這個系統是否是最優(yōu).本文提出用戶滿意度的概念，用來衡量認知用戶需求是否得到滿足.根據用戶滿意度設置用戶優(yōu)先級，對頻譜進行再次分配時可以滿足更多用戶需求，從而提高頻譜利用率.

用戶滿意度為認知用戶對當前頻譜分配的滿意程度［11］.用戶滿意度定義為頻譜空閑時間與認知用戶請求時間之比，即

sn＝wn／tn．（6）

從式（6）可以看出，當sn≥1時，用戶需求得到滿足，空閑頻譜時間與認知用戶請求時間之比越大，用戶的滿意度就越高；當0≤sn＜1時，用戶的需求未能得到滿足，空閑頻譜時間與認知用戶請求時間之比越小，用戶的滿意度就越低．

定義2 用戶的優(yōu)先級pn

目前研究中，大多沒有考慮到用戶的需求，容易導致系統的頻譜分配達不到最優(yōu)．本文根據用戶滿意度設置用戶優(yōu)先級，使頻譜在再次分配的過程中，按照用戶的優(yōu)先級進行分配，即

當用戶的需求被滿足時，用戶滿意度就大，相應的頻譜分配優(yōu)先級就降低，反之，用戶滿意度小，頻譜分配的優(yōu)先級就升高.

2.2 改進的CSGC算法描述

本文算法分為兩個階段，第一階段，以最大化帶寬總和為目標進行初次頻譜分配，若部分用戶的需求仍不能被滿足，則根據用戶的優(yōu)先級進行第二階段頻譜分配.

改進的CSGC算法，在頻譜分配的第一階段，通過標簽規(guī)則標記每個節(jié)點的標號值（label），每一個標號對應一個頻段.每次分配時，將選取具有最大標號值的節(jié)點，把相應的頻譜分配給該節(jié)點.更新拓撲，在可用頻譜列表中刪除與獲得頻譜用戶有沖突的用戶，同時刪除這些節(jié)點以該顏色相連的邊.進行拓撲更新時，每個節(jié)點的鄰居節(jié)點也將發(fā)生變化，所以節(jié)點干擾限制情況一直是變化的，相關節(jié)點的標號值和干擾限制矩陣也隨之進行更新，若空閑頻譜列表不為空，則進行第二階段的頻譜分配，根據第一階段用戶對當前頻譜分配的滿意程度，得到用戶優(yōu)先級，按優(yōu)先級由高到低的順序進行頻譜的再次分配.首先對具有最高優(yōu)先級用戶進行分配，用戶要求一旦被滿足，立即降低其優(yōu)先級.若有多個認知用戶擁有相同的優(yōu)先級，則將頻譜分配給干擾節(jié)點數最少的認知用戶.若圖為空，本周期分配結束.執(zhí)行過程如下步驟：1）進行初始化設置，設置參數和仿真模型；2）選擇初始分配準則，即最大化帶寬總和準則，利用式（1）搜索具有最大效益的用戶；3）根據準則進行頻譜分配；4）更新拓撲，在可用頻譜列表中刪除與獲得頻譜用戶有沖突的用戶，同時刪除這些節(jié)點以該顏色相連的邊.將已滿足需求的用戶暫時退出分配；5）判斷圖是否為空，若圖為空，則執(zhí)行步驟9；若圖不為空，則執(zhí)行步驟6；6）根據用戶的滿意度，即式（6），設置用戶分配頻譜的優(yōu)先級；7）根據用戶優(yōu)先級進行頻譜分配，搜索具有最高優(yōu)先級的用戶進行分配，若優(yōu)先級相同，選取干擾節(jié)點數最少的認知用戶進行分配；8）判斷圖是否為空，若圖為空，則執(zhí)行步驟9；若圖不為空，則返回步驟4；9）本周期分配結束.

3 算法仿真與分析

本文采用matlab仿真軟件，對改進后的CSGC算法和傳統算法進行仿真，采用協作式下最大帶寬準則和非協作式下最大帶寬準則，對算法的分配目標進行分析比較.設置參數如表1所示.

根據算法的執(zhí)行過程和仿真參數設置，當用戶數固定，信道數從5到30依次取值，進行20 000次仿真實驗，比較CMSB、NMSB準則下改進的CSGC算法和傳統算法的性能.仿真結果如圖1～2所示.

表1 仿真參數設置

圖1、2為協作與非協作方式下系統總效益與頻譜數量的變化曲線.由圖可知，在用戶數固定的情況下，隨著頻譜數量的增加，系統效益都成上升趨勢.而且隨著頻譜數量的增加，新算法下系統總效益的增加幅度明顯變大.在協作式和非協作式準則下新算法的系統性能與傳統CSGC算法相比，提高了約31%和25%.

根據算法的執(zhí)行過程和仿真參數設置，當信道數固定，用戶數從5到20依次取值，進行20 000次仿真實驗，比較CMSB、NMSB準則下改進的CSGC算法和傳統算法的性能.仿真結果如圖3～4所示.

圖1 用戶數不變協作式最大化帶寬準則下系統總效益

圖2 用戶數不變非協作式最大化帶寬準則下系統總效益

圖3 信道數不變協作式最大化帶寬準則下系統總效益

圖4 信道數不變非協作式最大化帶寬準則下系統總效

圖3 、4為兩種協作方式下認知用戶數量與系統總效益的變化曲線.由圖可知，在信道數一定的條件下，隨著認知用戶數量增多，用戶需求增加，系統總效益呈現出下降的趨勢.但新算法下的系統總效益要明顯高于傳統算法.換言之，在相同帶寬條件下，改進后的算法可以支持更多的認知用戶接入.協作式與非協作式條件下，新算法均表現出較高的性能.

4 結 語

本文在深入研究經典圖論模型的基礎上，從認知用戶需求的角度出發(fā)，提出了一種改進的CSGC頻譜分配算法，該算法通過考慮用戶的需求，據此快速進行二次頻譜分配.由仿真結果分析可知，與傳統CGSC算法相比，改進算法能夠更好地滿足各認知用戶當前的需求，極大的提高了頻譜分配的系統效益.

［1］THAKKER P，SARKANI S，MAZUCHI T.A system dynamics approach to demand and allocation of wireless spectrum formobilecommunication［J］.Procedia Computer Science，2012，8：118-123.

［2］BARNES S D，MAHARAJ B T.Prediction based channel allocation performance for cognitive radio［J］.AEU?International Journal of Electronics and Communication，In Press，Uncorrected Proof，2013，4.

［3］LUNDBORG M，REICHL W.RUHLE E O.Spectrum allocation anditsrelevanceforcompetition［J］. Telecommunications Policy，2012，36（8）.

［4］廖楚林，陳劼，唐友喜.認知無線電中的并行頻譜分配算法.［J］電子與信息學報，2007，29（7）：1608-1611.

［5］謝玉鵬，譚學治，馬琳，等.兩種標準聯合的認知無線電頻譜分配算法［J］.哈爾濱工業(yè)大學學報，2013，45（5）：30-34.

［6］賈杰，王闖，張朝陽，等.認知無線電網絡中基于圖論著色的動態(tài)頻譜分配［J］.東北大學學報，2012，33（3）：336-339.

［7］胡慶，常迪，海力群.認知無線電中基于頻譜聚合的需求改進型頻譜分配算法［J］.重慶郵電大學學報（自然科學版），2014，36（1）：8-12.

［8］朱冰蓮，裴光術，張磊，等.認知無線電網絡中系統效益最大化的頻譜分配［J］.計算機工程，2012，38（3）：107-109.

［9］何利，鄭湘渝，劉振坤.基于圖著色理論的最大效用頻譜分配算［J］.計算機工程，2011，19（10）：93-95.

［10］李一兵，楊蕊，高振國.基于著色理論的認知無線電頻譜分配算法［J］.系統工程與電子技術，2010，32（6）：1109-1112.

［11］張玉兵，薛偉，林法杰.基于用戶間公平性的改進型頻譜分配算法［J］.計算機與數字工程，2013，41（7）：1062-1064.

（編輯 苗秀芝）

A CSGC improved algorithm of spectrum allocation

TENG Zhijun，LI Ke

（Dept.of Information Engineering，Northeast Dianli University，132012 Jilin，Jilin，China）

To solve the problem that the spectrum allocation algorithm based on graph theory coloring algorithm has not fully considered the actual bandwidth needs of users，this paper proposes a spectrum allocation based on user priority algorithm improved CSGC and the original algorithm.The algorithm introduces two time factors that are respectively called idle spectrum and user demand，by setting the user priority，the function can meet the needs of users during the second spectrum allocation.Simulation results show that the algorithm not only retains the performance of the original algorithm CSGC，but also greatly improves the spectrum utilization.

graph；spectrum；allocation；CSGC；user′s priority

TN923

：A

：0367-6234（2014）11-0119-04

2014-01-02.

國家自然科學基金（51077010）.

滕志軍（1973—），男，博士，教授.

李 可，likelike1227＠126.com.