胡虹梅，覃玉榮

（廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西南寧530004）

0 引言

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

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

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

1 頻譜分配圖論模型建模

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

①假設(shè)某一時(shí)刻網(wǎng)絡(luò)中有N個(gè)認(rèn)知用戶需要通信，授權(quán)頻段有M個(gè)空閑頻譜。假設(shè)在一個(gè)分配周期內(nèi)，認(rèn)知用戶的網(wǎng)絡(luò)拓?fù)浔３植蛔?

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

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

2 改進(jìn)型CSGC算法

2.1 算法分配目標(biāo)

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

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

考慮用戶在一個(gè)分配周期內(nèi)的帶寬需求。假設(shè)demn為用戶n在一個(gè)分配周期內(nèi)的帶寬需求，USn為經(jīng)過分配后用戶n未滿足的帶寬需求，則其中，函數(shù)（x）+=max（0，x）。基于用戶需求的CSGC改進(jìn)算法的分配目標(biāo)是最小化一個(gè)分配周期內(nèi)系統(tǒng)中所有認(rèn)知用戶的未滿足帶寬需求總量，即

2.2 算法原理

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

2.3 算法分配流程

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

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

圖1 算法流程圖

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

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

表1 仿真參數(shù)

表2 頻帶效益等級(jí)

表3 帶寬需求

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

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

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

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

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

圖4 分配的時(shí)間開銷

4 結(jié)束語

基于圖論著色模型，研究了基于用戶帶寬需求的CSGC改進(jìn)算法。該算法通過降低已滿足需求用戶的分配優(yōu)先級(jí)來減少未滿足需求用戶的數(shù)量，較好地實(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]廖楚林.認(rèn)知無線電系統(tǒng)的頻譜分配算法研究[D].成都:電子科技大學(xué)碩士學(xué)位論文，2007.

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