基于用戶需求的改進型CSGC頻譜分配算法

胡虹梅，覃玉榮

（廣西大學計算機與電子信息學院，廣西南寧530004）

0 引言

圖論著色模型是研究認知無線電頻譜分配的一個重要模型，它將認知用戶和授權用戶所組成的網絡拓撲結構抽象成圖，把頻譜分配問題等效為圖論著色問題。文獻1基于圖論模型提出了列表著色頻譜分配算法，其目標是最大化頻譜利用率。文獻2充分考慮頻譜效益的差異性和干擾性，提出了CSGC算法。還有學者提出了并行頻譜分配算法，極大地減少了頻譜分配的時間開銷，能夠更好地適應認知無線電環境快速時變的要求[3]。

以上算法主要從認知用戶所獲得的帶寬效益進行頻譜分配，但缺乏考慮認知用戶本身的帶寬需求因素，很可能造成帶寬需求大但信道質量差的用戶得不到滿足，帶寬需求小但信道質量好的用戶卻占用著大量的頻譜資源，從而帶來頻譜資源二次浪費的不公平現象。為此，文獻[4]和文獻[5]基于CSGC算法分別采取了結合需求的暫時退出機制和排隊方式來最小化系統未滿足的帶寬需求，但前者需要二次構造網絡拓撲圖，帶來了時間開銷;后者引入未知參數變量，使計算困難。2種算法均未能較好解決用戶需求這一重要問題。

在上述研究基礎上，主要研究了能較好解決用戶需求的改進型CSGC頻譜分配算法。該算法的特點是當某用戶達到帶寬需求后，立即用各頻段收益最小非零值的一半來代替其剩余頻段的帶寬收益，使該用戶在下一輪分配中優先級最低。通過犧牲少量系統帶寬總收益來達到大幅提升滿足用戶需求的性能，提高系統分配公平性和頻譜利用率的目的。同時算法中無新的時間開銷和參數變量，易簡單實現。

1 頻譜分配圖論模型建模

在認知無線電頻譜分配的圖論著色模型研究中，將認知用戶組成的網絡拓撲結構抽象成圖，圖中的每個頂點代表一個認知無線電用戶，每一個頂點與一個列表相關聯，這個列表代表頂點所在區域位置可以使用的頻譜資源集合，如果圖中的某2個頂點以某顏色邊相連，則這2個頂點不能同時使用該顏色所代表的頻譜。該文建立的圖論著色模型，將認知用戶的頻譜分配問題抽象成圖G=（V，E，S）對頂點的著色問題，其中:V是圖G的頂點集合，代表認知用戶;E是圖G的邊集，由干擾矩陣決定;S表示各個頂點處的可選顏色列表，即各認知用戶的可用頻譜。該模型具體使用可用矩陣、效益矩陣、干擾矩陣、干擾限制矩陣、帶寬需求向量和分配矩陣進行描述，相關假設與定義如下:

①假設某一時刻網絡中有N個認知用戶需要通信，授權頻段有M個空閑頻譜。假設在一個分配周期內，認知用戶的網絡拓撲保持不變;

③效益矩陣B={bn，m}N×M，bn，m表示用戶n

使用頻帶m能夠帶來的頻譜效益;

2 改進型CSGC算法

2.1 算法分配目標

原有的CSGC算法以一個最優化的效益函數為目標，按照某個分配準則對頂點進行標號，選擇具有最大標號值的頂點并為其分配頻段。在最大化系統帶寬收益效益函數下，分配準則分別為協作式最大化帶寬總和（CMSB）和非協作式最大化帶寬總和（NMSB）。其中，ΛN，M表示所有滿足條件的無干擾分配矩陣A的集合。

原算法從用戶所獲得的帶寬收益角度分配頻譜，未考慮認知用戶的帶寬需求，這很可能導致帶寬需求小的用戶分配到大量頻譜，而帶寬需求大的用戶卻得不到滿足，從而帶來頻譜資源的二次浪費。針對此問題，結合用戶自身的帶寬需求因素，提出了改進型CSGC頻譜分配算法。

考慮用戶在一個分配周期內的帶寬需求。假設demn為用戶n在一個分配周期內的帶寬需求，USn為經過分配后用戶n未滿足的帶寬需求，則其中，函數（x）+=max（0，x）。基于用戶需求的CSGC改進算法的分配目標是最小化一個分配周期內系統中所有認知用戶的未滿足帶寬需求總量，即

2.2 算法原理

為最小化系統未滿足的帶寬需求，在分配過程中應盡量減少未滿足需求用戶的數量，即某個用戶的需求一旦得到滿足，立即降低其分配的優先級以優先考慮尚未滿足需求的用戶。文獻[5]采用“滿足條件的某一值”將已滿足帶寬需求的用戶置于隊尾，但是“滿足條件的某一值”是一個模糊的概念，難于計算。該文的做法簡單明確:在某次分配循環過程中，假設用戶n已滿足自身的帶寬需求。進行拓撲更新后，找出用戶n剩余的所有可用頻段，分別計算這些可用頻段下各認知用戶的帶寬收益，取出各頻段下帶寬收益的最小非零值，將其倍減后作為用戶n在該頻段下新的帶寬收益。這樣就能夠使得在同一可用頻段下用戶n的效益比其他用戶的都小，即優先級最低。該文提出的算法不需要二次構圖，也沒有引入新參數變量，用戶分配優先級的計算簡單易行，在CSGC算法的基礎上增加考慮用戶自身的帶寬需求，使得頻譜分配與自身需求相匹配，提高了分配的公平性和頻譜利用率。

2.3 算法分配流程

定義帶寬收益矩陣R={r（n，m）}N×M。r（n，m）表示在某個目標準則下某循環階段用戶n使用頻帶m的帶寬收益，在NMSB分配準則下r（n，m）=bn，m，在CMSB準則下，r（n，m）=bn，m/（Dn，m+1）。基于用戶需求的CSGC頻譜分配算法是在原有CSGC算法上做出了一定改進的算法，因此其算法流程與CSGC算法較為接近，不同的地方在于改進算法增加考慮了用戶的帶寬需求滿足情況。

基于用戶需求的改進型CSGC頻譜分配算法流程如圖1所示。算法每一輪分配循環只分配一個頻譜給相應的用戶，反復地循環分配，直至將所有可用頻譜分配完畢。

圖1 算法流程圖

3 數值仿真與結果分析

為比較2種算法的性能，對CMSB和NMSB準則下的CSGC頻譜分配算法和基于用戶需求的改進型CSGC算法進行MATLAB仿真。仿真參數如表1所示，頻帶效益和帶寬需求如表2和表3所示，其參數參照文獻[4]。

表1 仿真參數

表2 頻帶效益等級

表3 帶寬需求

未滿足需求的帶寬總量如圖2所示，圖中的橫軸表示一個分配周期內所有認知用戶的未滿足需求總量，縱軸為經過多次實驗后所獲得的統計概率累積分布函數。基于用戶需求的CSGC改進算法，就總體趨勢而言其未滿足需求總量均小于CSGC算法，在協作和非協作模式下其滿足用戶需求的性能比CSGC算法分別能夠提高約30%和26%。此外，CSGC算法滿足帶寬需求的概率為4%，基于用戶需求的算法滿足帶寬需求的概率為14%～20%，增加了約10%～16%。

圖2 未滿足需求的總量比較圖

系統帶寬總收益和分配時間開銷分別如圖3和圖4所示。從圖中可以看到，就總體趨勢而言，基于用戶需求的改進算法的總帶寬收益在協作與非協作模式下均略小于原CSGC算法，其分配的時間開銷與CSGC算法大致相當。圖4中T為一次分配循環周期。

以上仿真結果表明:基于用戶需求的CSGC算法有效地兼顧了頻譜利用率和分配的時間開銷，通過犧牲少量的系統帶寬總收益，其滿足用戶需求的性能比CSGC算法大約提升26%～30%，提高了分配的公平性。

圖3 系統帶寬總收益比較圖

圖4 分配的時間開銷

4 結束語

基于圖論著色模型，研究了基于用戶帶寬需求的CSGC改進算法。該算法通過降低已滿足需求用戶的分配優先級來減少未滿足需求用戶的數量，較好地實現了頻譜分配與自身需求相匹配。仿真結果表明，所提算法滿足需求的性能比CSGC算法大約提高26%～30%，更好地滿足了用戶的帶寬需求。

[1]WANG WEI，LIU XIN.List-Coloring Based Channel Allocation for Open-Spectrum Wireless Networks[C]//the 62nd IEEE Vehicular Technology Conference.May 2005:690-694.

[2]ZHENG Hai-tao，PENG Chun-yi.Collaboration and Fairness in Opportunistic Spectrum Access[C]//IEEE International Conferencen Communication.May 2005:3132-3136.

[4]廖楚林.認知無線電系統的頻譜分配算法研究[D].成都:電子科技大學碩士學位論文，2007.

[5]莫文承.認知無線電的頻譜分配算法研究[D].成都:電子科技大學碩士學位論文，2008.