一種改進(jìn)的CSGC頻譜分配算法

滕志軍，李 可

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

一種改進(jìn)的CSGC頻譜分配算法

滕志軍，李 可

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

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

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

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

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

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

1 傳統(tǒng)CSGC算法概述

1.1 CSGC算法模型的數(shù)學(xué)描述

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

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

1）空閑頻譜矩陣L

在認(rèn)知無(wú)線通信系統(tǒng)中，同時(shí)存在著授權(quán)用戶和認(rèn)知用戶，當(dāng)授權(quán)用戶使用某一頻段頻譜時(shí)，認(rèn)知用戶則不能使用，用空閑頻譜表示某個(gè)時(shí)間沒(méi)有授權(quán)用戶使用該頻段的頻譜．L＝｛ln，m｜ln，m∈｛0，1｝｝N×M，N為認(rèn)知用戶數(shù)，M為總頻帶數(shù)．ln，m＝1為用戶n可以使用頻帶m，反之，ln，m＝0為用戶n不可以使用頻帶m．

2）效益矩陣B

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

3）干擾矩陣C

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

當(dāng)Cn，k，m＝1時(shí)，為認(rèn)知用戶n和k在同時(shí)使用頻帶m時(shí)會(huì)產(chǎn)生干擾．當(dāng)n＝k時(shí)，Cn，n，m＝1-ln，m，只由空閑頻譜矩陣L決定．

4）無(wú)干擾的頻譜分配矩陣A

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

5）頻譜空閑時(shí)間矩陣W

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

6）認(rèn)知用戶請(qǐng)求時(shí)間T

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

1.2 CSGC算法準(zhǔn)則

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

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

本文采用協(xié)作式和非協(xié)作式兩種方式，相應(yīng)的標(biāo)號(hào)準(zhǔn)則如下：

1）協(xié)作式最大帶寬總和（collaborative?max?sum?bandwidth，CMSB）準(zhǔn)則［7］，相應(yīng)的節(jié)點(diǎn)標(biāo)號(hào)和顏色表達(dá)式為

式中，Dn，m表示認(rèn)知用戶n分配到頻譜m，與該用戶不能同時(shí)使用頻譜m的有干擾沖突的用戶數(shù)．定義為認(rèn)知用戶使用頻譜m后，對(duì)整個(gè)系統(tǒng)產(chǎn)生的效益為bn，m／（Dn，m＋1）．

采用協(xié)作式最大帶寬總和的標(biāo)簽準(zhǔn)則，不僅提高頻譜利用率，而且考慮到頻譜分配過(guò)程中用戶之間的干擾關(guān)系，使頻譜利用率最大化，系統(tǒng)性能達(dá)到全局最優(yōu).

2）非協(xié)作式最大帶寬總和（non?collaborative?max?sum?bandwidth，NMSB）準(zhǔn)則［8］，相應(yīng)的節(jié)點(diǎn)標(biāo)號(hào)和顏色表達(dá)式為

非協(xié)作式最大帶寬總和的標(biāo)簽準(zhǔn)則，沒(méi)有考慮用戶之間的干擾，用戶與用戶是非合作的關(guān)系，都只考慮自己的效益而忽略對(duì)整個(gè)系統(tǒng)產(chǎn)生的影響.

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

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

2.1 定義

定義1 用戶滿意度sn

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

用戶滿意度為認(rèn)知用戶對(duì)當(dāng)前頻譜分配的滿意程度［11］.用戶滿意度定義為頻譜空閑時(shí)間與認(rèn)知用戶請(qǐng)求時(shí)間之比，即

sn＝wn／tn．（6）

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

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

目前研究中，大多沒(méi)有考慮到用戶的需求，容易導(dǎo)致系統(tǒng)的頻譜分配達(dá)不到最優(yōu)．本文根據(jù)用戶滿意度設(shè)置用戶優(yōu)先級(jí)，使頻譜在再次分配的過(guò)程中，按照用戶的優(yōu)先級(jí)進(jìn)行分配，即

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

2.2 改進(jìn)的CSGC算法描述

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

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

3 算法仿真與分析

本文采用matlab仿真軟件，對(duì)改進(jìn)后的CSGC算法和傳統(tǒng)算法進(jìn)行仿真，采用協(xié)作式下最大帶寬準(zhǔn)則和非協(xié)作式下最大帶寬準(zhǔn)則，對(duì)算法的分配目標(biāo)進(jìn)行分析比較.設(shè)置參數(shù)如表1所示.

根據(jù)算法的執(zhí)行過(guò)程和仿真參數(shù)設(shè)置，當(dāng)用戶數(shù)固定，信道數(shù)從5到30依次取值，進(jìn)行20 000次仿真實(shí)驗(yàn)，比較CMSB、NMSB準(zhǔn)則下改進(jìn)的CSGC算法和傳統(tǒng)算法的性能.仿真結(jié)果如圖1～2所示.

表1 仿真參數(shù)設(shè)置

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

根據(jù)算法的執(zhí)行過(guò)程和仿真參數(shù)設(shè)置，當(dāng)信道數(shù)固定，用戶數(shù)從5到20依次取值，進(jìn)行20 000次仿真實(shí)驗(yàn)，比較CMSB、NMSB準(zhǔn)則下改進(jìn)的CSGC算法和傳統(tǒng)算法的性能.仿真結(jié)果如圖3～4所示.

圖1 用戶數(shù)不變協(xié)作式最大化帶寬準(zhǔn)則下系統(tǒng)總效益

圖2 用戶數(shù)不變非協(xié)作式最大化帶寬準(zhǔn)則下系統(tǒng)總效益

圖3 信道數(shù)不變協(xié)作式最大化帶寬準(zhǔn)則下系統(tǒng)總效益

圖4 信道數(shù)不變非協(xié)作式最大化帶寬準(zhǔn)則下系統(tǒng)總效

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

4 結(jié) 語(yǔ)

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

［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］廖楚林，陳劼，唐友喜.認(rèn)知無(wú)線電中的并行頻譜分配算法.［J］電子與信息學(xué)報(bào)，2007，29（7）：1608-1611.

［5］謝玉鵬，譚學(xué)治，馬琳，等.兩種標(biāo)準(zhǔn)聯(lián)合的認(rèn)知無(wú)線電頻譜分配算法［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2013，45（5）：30-34.

［6］賈杰，王闖，張朝陽(yáng)，等.認(rèn)知無(wú)線電網(wǎng)絡(luò)中基于圖論著色的動(dòng)態(tài)頻譜分配［J］.東北大學(xué)學(xué)報(bào)，2012，33（3）：336-339.

［7］胡慶，常迪，海力群.認(rèn)知無(wú)線電中基于頻譜聚合的需求改進(jìn)型頻譜分配算法［J］.重慶郵電大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，36（1）：8-12.

［8］朱冰蓮，裴光術(shù)，張磊，等.認(rèn)知無(wú)線電網(wǎng)絡(luò)中系統(tǒng)效益最大化的頻譜分配［J］.計(jì)算機(jī)工程，2012，38（3）：107-109.

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

［10］李一兵，楊蕊，高振國(guó).基于著色理論的認(rèn)知無(wú)線電頻譜分配算法［J］.系統(tǒng)工程與電子技術(shù)，2010，32（6）：1109-1112.

［11］張玉兵，薛偉，林法杰.基于用戶間公平性的改進(jìn)型頻譜分配算法［J］.計(jì)算機(jī)與數(shù)字工程，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.

國(guó)家自然科學(xué)基金（51077010）.

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

李 可，likelike1227＠126.com.