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

胡虹梅，覃玉榮

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

0 引言

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

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

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

1 頻譜分配圖論模型建模

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

①假設(shè)某一時刻網(wǎng)絡(luò)中有N個認知用戶需要通信，授權(quán)頻段有M個空閑頻譜。假設(shè)在一個分配周期內(nèi)，認知用戶的網(wǎng)絡(luò)拓撲保持不變;

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

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

2 改進型CSGC算法

2.1 算法分配目標

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

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

考慮用戶在一個分配周期內(nèi)的帶寬需求。假設(shè)demn為用戶n在一個分配周期內(nèi)的帶寬需求，USn為經(jīng)過分配后用戶n未滿足的帶寬需求，則其中，函數(shù)（x）+=max（0，x）?；谟脩粜枨蟮腃SGC改進算法的分配目標是最小化一個分配周期內(nèi)系統(tǒng)中所有認知用戶的未滿足帶寬需求總量，即

2.2 算法原理

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

2.3 算法分配流程

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

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

圖1 算法流程圖

3 數(shù)值仿真與結(jié)果分析

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

表1 仿真參數(shù)

表2 頻帶效益等級

表3 帶寬需求

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

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

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

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

圖3 系統(tǒng)帶寬總收益比較圖

圖4 分配的時間開銷

4 結(jié)束語

基于圖論著色模型，研究了基于用戶帶寬需求的CSGC改進算法。該算法通過降低已滿足需求用戶的分配優(yōu)先級來減少未滿足需求用戶的數(shù)量，較好地實現(xiàn)了頻譜分配與自身需求相匹配。仿真結(jié)果表明，所提算法滿足需求的性能比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]廖楚林.認知無線電系統(tǒng)的頻譜分配算法研究[D].成都:電子科技大學碩士學位論文，2007.

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