徐 嵩，李玉峰

（沈陽航空航天大學(xué) 電子信息工程學(xué)院，遼寧 沈陽110136）

最大效益準(zhǔn)則下基于分配公平性的CSGC改進(jìn)算法

徐 嵩，李玉峰

（沈陽航空航天大學(xué) 電子信息工程學(xué)院，遼寧 沈陽110136）

針對傳統(tǒng)基于圖論著色原理的頻譜分配算法公平性較差問題進(jìn)行研究，提出一種在最大效益準(zhǔn)則下基于分配公平性改進(jìn)的CSGC頻譜分配算法。該算法在最大化系統(tǒng)效益準(zhǔn)則下，充分考慮了用戶對頻譜資源占用因素，改進(jìn)了原有CSGC算法。尤其是在頻譜資源緊張情況下，保證了分配的公平性，保障了弱勢用戶的需求。MATLAB仿真實驗結(jié)果表明，該算法在保障系統(tǒng)效益犧牲不大的前提下，提高了頻譜資源分配公平性。

認(rèn)知無線電；圖著色；頻譜分配；CSGC；分配公平性

隨著當(dāng)前無線通信技術(shù)的高速發(fā)展，人們對于無線頻譜資源的需求越來越大，頻譜資源緊缺問題日益嚴(yán)重。而由于無線頻譜資源的不可再生性，人們將研究的重點(diǎn)放在了如何更加合理的利用現(xiàn)有頻譜資源上。在此背景下，認(rèn)知無線電技術(shù)[1-2]應(yīng)運(yùn)而生。認(rèn)知無線電通過頻譜感知技術(shù)，感知空閑頻譜特性并分析空閑頻譜特性及認(rèn)知用戶特征，將無線頻譜資源合理分配給認(rèn)知用戶，以此方法來提高頻譜的利用率。

目前的頻譜分配方法多種多樣，有博弈論、圖著色、遺傳算法和比例公平分配算法等[3-5]。在這些算法當(dāng)中，圖著色算法相對來說復(fù)雜度低，便于理解并且具有良好的實用性，所以廣大研究者極為重視。文獻(xiàn)[6-7]提出了基于比例公平的頻譜資源分配算法，此算法結(jié)合注水算法可以完成頻譜分配的次優(yōu)方案，算法復(fù)雜度較高。文獻(xiàn)[8]提出了基于圖論著色模型的列表著色頻譜分配算法。文獻(xiàn)[9]則是在圖著色理論基礎(chǔ)上提出了優(yōu)先改進(jìn)最小鄰居算法（Progressive Minimum Neighbor First，PMNF）分配模型，此算法的基本思想就是將最難著色的點(diǎn)優(yōu)先進(jìn)行著色處理，基于此思想，PMNF算法給每個頂點(diǎn)分配了一個獨(dú)立的標(biāo)簽，用在限制條件約束下的最低的索引顏色中的最高標(biāo)簽來給頂點(diǎn)著色。文獻(xiàn)[10]根據(jù)PMNF算法的思想提出了顏色敏感圖著色算法（color sensitive graph coloring，簡寫CSGC）模型，其核心思想是將PMNF算法的最難著色點(diǎn)優(yōu)先著色改為了將“價值”最大的點(diǎn)優(yōu)先著色。文獻(xiàn)[11]提出了基于CSGC算法的并行分配改進(jìn)算法，在保證最優(yōu)分配的前提下減少了分配算法所消耗的時間，減少了系統(tǒng)資源消耗。文獻(xiàn)[12]則是在CSGC算法的基礎(chǔ)上，考慮了用戶等待時間因素，引入了之前的分配情況參數(shù)，減少了在資源緊張條件下的用戶等待時間，尤其是降低了弱勢用戶等待分配響應(yīng)所耗時間。文獻(xiàn)[13]將CSGC算法與遺傳算法進(jìn)行了結(jié)合，更有效的實現(xiàn)了網(wǎng)絡(luò)效益的最大化。文中的重點(diǎn)是研究在無線頻譜資源緊張情況且保證系統(tǒng)效益前提下，提高系統(tǒng)頻譜資源分配的公平性，引入已分配用戶對于資源占用的狀態(tài)參數(shù)，并根據(jù)這個參數(shù)定義用戶優(yōu)先級，確定分配時的用戶優(yōu)先級順序，保障了未分配的弱勢用戶的權(quán)益，并減少了強(qiáng)勢用戶對于系統(tǒng)資源的過度消耗，在保證系統(tǒng)效益的前提下，提高了系統(tǒng)分配的整體公平性。

1 基于CSGC的頻譜分配模型

假設(shè)在進(jìn)行頻譜資源分配時，用戶的位置，可用的頻譜資源等環(huán)境條件都是靜態(tài)的。假設(shè)在一個認(rèn)知網(wǎng)絡(luò)中，次級用戶（secondary user，簡寫為SU）的數(shù)量為N個（標(biāo)號為0——N-1），頻譜信道的數(shù)量為M個（0——M-1）。則分配模型的構(gòu)成如下：

1）空閑頻譜矩陣L：L={1n，m|1n，m∈{0，1}}N×M，L是一個N乘M階的二進(jìn)制矩陣。該矩陣體現(xiàn)了信道的可用性狀態(tài)：當(dāng)ln，m=1時，對于次級用戶n來說信道m(xù)是可用的；當(dāng)ln，m=0時，信道m(xù)對于次級用戶n不可用。

2）信道效益矩陣B：B={bn，m}N×M，B也是一個N乘M階的矩陣。bn，m表示次級用戶n使用信道m(xù)（假設(shè)相鄰的用戶間無干擾）時可獲得的效益。

3）干擾限制條件矩陣C：C={cn，k,m|cn，k,m∈{0，1}}N×N×M，C是一個階矩陣N×N×M，該矩陣表述了次級用戶之間的干擾限制條件。如果cn，k，m=1，次級用戶n與次級用戶k在同時使用信道m(xù)時將會互相干擾。限制條件由信道可用性決定， 例如 cn，k，m≤ln，m×lk，m且 cn，n，m= 1-ln，m。

4）無干擾的頻譜分配矩陣A：A={an，m|an，m∈{0，1}，an，m≤1n，m}N×M為表示頻譜分配情況的N乘M 階二進(jìn)制矩陣：如果信道m(xù)分配給用戶n，an，m=1。此矩陣要滿足無干擾條件：an，m·ak，m=0，if Cn，k，m=1；?n，k＜N，m＜M。

5）用戶頻譜資源占用矩陣SU：SU={sun|sun∈N}1×N，SU為表示次級用戶對于頻譜資源占用情況的1乘N階二進(jìn)制矩陣：在初始化狀態(tài)時，SU為全1矩陣，在分配過程中，當(dāng)用戶占用頻譜資源時，sun遞增1，否則sun維持當(dāng)前值不變。

在經(jīng)過上述數(shù)學(xué)建模之后，認(rèn)知無線電網(wǎng)絡(luò)頻譜資源分配問題即被轉(zhuǎn)化為雙向圖G=（V，L，E）著色問題[14-15]。V表示共享頻譜資源的點(diǎn)集（即次級用戶集合），L表示每個頂點(diǎn)的可用顏色列表（即可用的頻譜信道資源），E表示兩個頂點(diǎn)之間沖突的無向邊集。對于任意的兩個頂點(diǎn)u，v∈V，當(dāng)cu，v，m=1時，頂點(diǎn)u和頂點(diǎn)v之間存在著一條m色邊。這些邊取決于相鄰主用戶的頻譜使用狀態(tài)以及次級用戶u與v在信道m(xù)上的傳輸功率所決定的干擾條件C。

在本文中采用最大化總效益（Max-Sum-Reward）為頻譜分配的最優(yōu)化目標(biāo)函數(shù)，其可以表述為：

式（1）表示最大化頻譜效益，A∈∧N，M為滿足條件的全部A的集合。本文中分別采用協(xié)作最大化總效益 （Collaborative-Max-Sum-Reward，CSUM）準(zhǔn)則[10]與非協(xié)作最大化總效益（Non-collaborative-Max-Sum-Reward，NSUM）準(zhǔn)則[10]。

1）CSUM準(zhǔn)則的標(biāo)簽及著色表達(dá)式為：

式中，Dn，m為頂點(diǎn)n的m顏色特異度。Dn，m表示頂點(diǎn)n在顏色m上與其他相鄰用戶的沖突邊的數(shù)目，也就是不能與n同時使用信道m(xù)的相鄰的次級用戶的數(shù)量。

bn，m/（Dn，m+1）為認(rèn)知用戶使用頻譜信道m(xù)之后，對于整個系統(tǒng)的效益貢獻(xiàn)。此規(guī)則充分考慮了頻譜利用與相鄰用戶干擾之間的平衡，可以使系統(tǒng)性能達(dá)到全局最優(yōu)。

2）NSUM準(zhǔn)則的標(biāo)簽及著色表達(dá)式為：

與CSUM規(guī)則相比，由于每個頂點(diǎn)只考慮自己的效益并忽略了對于整個系統(tǒng)的影響，此規(guī)則的表現(xiàn)較為自私，是非協(xié)作的。

2 基于分配公平性的CSGC頻譜分配改進(jìn)算法

本算法的目標(biāo)是在系統(tǒng)資源相對緊張時，在保證系統(tǒng)總效益損失不大的前提下，動態(tài)調(diào)節(jié)用戶分配的優(yōu)先級順序，改善弱勢用戶分配地位并降低強(qiáng)勢用戶對于頻譜資源的占用，從而提高系統(tǒng)整體公平性，減少認(rèn)知用戶間的“貧富差距”。基于此目標(biāo)，在本算法中引入用戶頻譜資源占用參數(shù)，并根據(jù)此參數(shù)進(jìn)行如下定義。

2.1 定 義

定義 次級用戶分配優(yōu)先級P

文中根據(jù)用戶頻譜資源占用狀態(tài)來定義次級用戶的分配優(yōu)先級，在每輪分配過程中按照用戶分配優(yōu)先級順序進(jìn)行頻譜分配，次級用戶分配優(yōu)先級P的定義為：

根據(jù)公式（5）的定義，次級用戶的分配優(yōu)先級與用戶信道占用狀態(tài)成反比。即用戶頻譜占用狀態(tài)越大則優(yōu)先級越低，用戶頻譜占用狀態(tài)越小優(yōu)先級則越高。通過調(diào)節(jié)SU，在頻譜資源分配過程中動態(tài)調(diào)節(jié)次級用戶的分配優(yōu)先級P。

2.2 基于分配公平性的CSGC頻譜分配改進(jìn)算法

本算法充分結(jié)合用戶對頻譜資源占用狀態(tài)信息進(jìn)行頻譜分配。即根據(jù)式（5）定義的分配優(yōu)先級P來進(jìn)行分配，分配優(yōu)先級高的用戶優(yōu)先分配。當(dāng)次級用戶的分配優(yōu)先級一樣時，則采用經(jīng)典CSGC頻譜分配算法中的某個準(zhǔn)則 （如CSUM協(xié)作最大化總效益準(zhǔn)則；NSUM非協(xié)作最大化總效益準(zhǔn)則等）來計算次級用戶的標(biāo)簽值，標(biāo)簽值大的次級用戶將進(jìn)行優(yōu)先分配。其中在CSUM準(zhǔn)則下，標(biāo)簽值按照式（2）進(jìn)行計算；在NSUM準(zhǔn)則下，標(biāo)簽值按照式（3）進(jìn)行計算。次級用戶n分配完成后，退出本次分配，用戶頻譜資源占用參數(shù)SUn遞增1。次級用戶n未分配時，用戶頻譜資源占用參數(shù)SUn不變。這樣，隨著用戶頻譜資源占用參數(shù)的動態(tài)變化，本算法可以動態(tài)的調(diào)整次級用戶的分配優(yōu)先級，這樣既提高了弱勢用戶的分配權(quán)限，也降低了強(qiáng)勢用戶對于頻譜資源占用的權(quán)重，在對系統(tǒng)總效益影響較小的情況下保證了系統(tǒng)的整體公平性。

本算法考慮了用戶頻譜資源占用參數(shù)，減少了強(qiáng)勢用戶對于頻譜資源占用的權(quán)重，降低了系統(tǒng)中用戶的“兩極分化”。在頻譜資源進(jìn)行分配時，用戶優(yōu)先級受用戶頻譜資源占用參數(shù)影響，被分配到頻譜資源越多的用戶優(yōu)先級越低，被分配到頻譜資源越少的用戶優(yōu)先級越高，未分配到的用戶優(yōu)先級最高維持1不變。

算法流程圖如圖1所示，算法步驟如下：

步驟1 系統(tǒng)進(jìn)行初始化，更新各個節(jié)點(diǎn)的信息，檢測用戶狀態(tài)，進(jìn)行相關(guān)的建模。

步驟2 計算用戶分配優(yōu)先級別矩陣P，找出用戶分配級別最高的頂點(diǎn)（認(rèn)知用戶），并按照某種分配準(zhǔn)則（如CSUM或者NSUM等）計算標(biāo)簽值及其可用顏色（信道）。

步驟3找出標(biāo)簽值最大的頂點(diǎn)n，并判斷頂點(diǎn)n是否唯一。若頂點(diǎn)n唯一，對其分配相對應(yīng)顏色m。若頂點(diǎn)n不唯一，則隨機(jī)選取一個頂點(diǎn)進(jìn)行分配。

步驟4 更新用戶頻譜資源占用參數(shù)矩陣SU，更新用戶表單及可用頻譜資源表單，若同一分配優(yōu)先級用戶已全部完成分配或者該級別用戶已無可用頻譜資源，則進(jìn)行下一級別用戶的分配，否則返回步驟2。該級別中已分配用戶的用戶頻譜資源占用參數(shù)遞增1；未分配用戶的用戶頻譜資源占用參數(shù)保持不變。

步驟5 次一分配級別的次級用戶分配重復(fù)步驟2至步驟4。

步驟6 當(dāng)最低級別的用戶完成分配后，本輪分配結(jié)束。

圖1 算法流程圖

3 算法仿真及仿真結(jié)果分析

3.1 仿真參數(shù)與環(huán)境設(shè)定

在本文中利用Matlab軟件對本文算法與原始CSGC算法分別在CSUM準(zhǔn)則與NSUM準(zhǔn)則下進(jìn)行仿真比較，比較不同算法下的系統(tǒng)總效益與系統(tǒng)整體公平性情況。

仿真環(huán)境假設(shè)建立在一個無噪聲，固定的無線網(wǎng)絡(luò)上。當(dāng)主用戶占用一個頻譜m時，該主用戶的保護(hù)范圍半徑為dp（x，m），即在此范圍內(nèi)的所有次級用戶不可以使用頻譜m。次級用戶n通過改變其在信道m(xù)上的傳輸功率來改變其干擾范圍ds（n，m）的大小，從而避免對主用戶的干擾。一個次級用戶n使用主用戶x所占用的頻譜m的條件為滿足ds（n，m）≤Dist（n，x）-dp（x，m），Dist（n，x）為次級用戶 n與主用戶x之間的距離。干擾范圍ds可以用最小與最大傳輸[dmin，dmax]功率來限定。當(dāng)ds小于dmin時，次級用戶n即使未處于主用戶的保護(hù)范圍內(nèi)，同樣不可以使用頻譜m。在指定區(qū)域中（10×10），設(shè)置一定數(shù)量的主用戶與次級用戶，由于本文算法重點(diǎn)考慮的是頻譜資源緊張環(huán)境，所以在仿真中設(shè)定主用戶數(shù)量為20個，頻譜資源數(shù)M為10個，次級用戶的數(shù)量N為20個。在仿真中，每個主用戶隨機(jī)的從10個頻譜中選取一個占用。為簡化問題，在仿真中假設(shè)每個主用戶具有相同的保護(hù)范圍Dp=const。在本算法中設(shè)定cmax=10，Dp=2，dmin=1，dmax=4。另外在仿真中用平均效益代替總效益來使仿真變得更容易：

3.2 仿真結(jié)果及結(jié)果分析

在完成上述仿真參數(shù)及環(huán)境設(shè)定之后，分別在CSUM準(zhǔn)則與NSUM準(zhǔn)則下對原始CSGC頻譜分配算法和本算法進(jìn)行仿真實驗，最終仿真結(jié)果如圖2～4所示。

圖2和圖3分別為次級用戶分配到的頻譜資源數(shù)統(tǒng)計圖與系統(tǒng)效益統(tǒng)計圖。在圖2中橫軸為用戶標(biāo)號，縱軸為各個次級用戶被分配到的頻譜資源數(shù)。虛線表示原始CSGC頻譜分配算法，實線表示本算法。通過圖2（a）中可以非常直觀的看出虛線波動非常大，最大值和最小值分別為76與30，跨度達(dá)到了46；實線波動非常小，其最大值和最小值分別為58與48，跨度為10。圖2（b）中同樣可以觀察到虛線波動大，其最大值與最小值分別為62與22，跨度為40；實線波動非常小，其最大值與最小值分別為43與36，跨度為7。圖3中的曲線表示系統(tǒng)的效益，其中橫軸為實驗標(biāo)號，縱軸為系統(tǒng)效益（為簡化仿真，采用上文定義的平均效益）。虛線代表CSUM準(zhǔn)則與NSUM準(zhǔn)則下的原始CSGC頻譜分配算法，實線為本算法。如圖3所示，原始CSGC頻譜分配算法的系統(tǒng)效益最好，本算法效益低于原始CSGC頻譜分配算法，但差距不大。

圖2 用戶被分配的頻譜資源數(shù)折線圖

圖4為次級用戶分配的頻譜資源柱形統(tǒng)計圖，橫軸為用戶被分配的頻譜資源數(shù)分組，縱坐標(biāo)為用戶數(shù)量分布統(tǒng)計。圖4中的 4個子圖分別對應(yīng)CSUM準(zhǔn)則與NSUM準(zhǔn)則下的兩種算法，通過對比，本算法的跨度小于原始CSGC頻譜分配算法且次級用戶的數(shù)量分布更加集中。這證明本算法很好的減少了頻譜分配分配過程中產(chǎn)生的“邊緣用戶”，即減少了“弱勢用戶”數(shù)量與“強(qiáng)勢用戶”數(shù)量，提高了頻譜資源的分配公平性。

通過對算法的仿真結(jié)果進(jìn)行分析對比，總體來講，本算法在頻譜資源緊張的環(huán)境中，在保證系統(tǒng)效益變化不大的前提下，引入了用戶頻譜資源占用因素，通過自適應(yīng)的改變次級用戶分配優(yōu)先級，有效減少了分配過程中的“邊緣用戶”數(shù)量，降低了系統(tǒng)中用戶的“貧富差距”，提高了系統(tǒng)的公平性。

4 結(jié) 論

在頻譜資源日趨緊張的大環(huán)境下，認(rèn)知無線電技術(shù)為廣大研究者指明了方向，提供了可行方案。在頻譜分配過程中，尤其是在頻譜資源緊張時，在系統(tǒng)中難以避免的會出現(xiàn)用戶的“兩極分化”現(xiàn)象，此現(xiàn)象極大的造成了分配的不公平性。這會導(dǎo)致在現(xiàn)實情況中，部分處于弱勢地位的次級用戶無法分配到頻譜資源或者分配到的頻譜資源過少，進(jìn)而導(dǎo)致無法進(jìn)行有效通信，而另一部分處于強(qiáng)勢地位的次級用戶卻又被分配到大量的頻譜資源，長期占用系統(tǒng)進(jìn)行通信的不公平現(xiàn)象。在本文中第一次引入了基于用戶頻譜資源占用參數(shù)定義的優(yōu)先級，通過在分配過程中動態(tài)的調(diào)整次級用戶的分配優(yōu)先級，降低了“強(qiáng)勢用戶”的分配權(quán)，提高了“弱勢用戶”分配權(quán)，改善了系統(tǒng)的“兩極分化”現(xiàn)象。最后通過仿真分析結(jié)果證明：文中算法在頻譜資源緊張的環(huán)境中，保證了系統(tǒng)效益，且充分提高了系統(tǒng)公平性。

圖3 系統(tǒng)效益折線圖

圖4 用戶分配頻譜資源柱形統(tǒng)計圖

參考文獻(xiàn)：

[1]Joseph MitolaⅢ，Gerald Q.Maguire cognitive Radio:making software radios more personal[J].IEEE Personal Communications，1999，6（4）：3-18.

[2]Cordeiro C，Challapali K，Birru D.IEEE 802.22:The first worldwide wireless standard based on cognitive radios[C]//New Frontiers in Dynamic Spectrum Access Networks，11.2005:328-337.

[3]王欽輝，葉保留，田宇等.認(rèn)知無線電網(wǎng)絡(luò)中頻譜分配算法[J].電子學(xué)報，2012，40（1）:147-154.

[4]莫文承．認(rèn)知無線電頻譜分配算法研究[D]．西安:西安電子科技大學(xué)，2008．

[5]楊鐵軍，林培培.改進(jìn)遺傳算法的認(rèn)知無線電頻譜分配[J]．計算機(jī)仿真，31（2）:250-254.

[6]Wong I C，Zukang Shen，Evans B L，et al.A low complexity algorithm forproportionalresource allocation in OFDMA systems[J].IEEE Workshop on Signal Processing Systems，2004:1-6.

[7]SHEN Zu-kang，Andrews J G，Evans B L，Adaptive resource allocation in multiuser OFDM systems with proportional rate constraints[J].IEEE Transactions on Wireless Communication，2005，4（6）:2726-2737.

[8]WANG Wei，LIU Xin.List-Coloring based channel allocation for open-spectrum wireless Networks[C]// The 62nd IEEE Vehicular Technology Conference（VTC），2005：690-694.

[9]Ramanathan S，A unified framework and algorithm for channel assignment in wireless networks[J].Wireless Networks March 1999，5（2）：81-94.

[10]Peng C，Zheng H，Zhao B．Utilization and fairness in spectrum assignment for opportunistic spectrum access[J]．ACM mobile networks and applications（MONET），2006，11（4）:554-576.

[11]廖楚林，陳劼，唐友喜，等.認(rèn)知無線電中的并行頻譜分配算法[J]．電子與信息學(xué)報，2007，29（7）:1608-1611.

[12]柳平，張敏．基于用戶等待時間的頻譜分配改進(jìn)算法[J]．廣東通信技術(shù)，2009，11（6）:17-20．

[13]鄭志剛，薛菲，周井泉.網(wǎng)絡(luò)效益最大化的認(rèn)知無線電頻譜分配方法[J]．計算機(jī)技術(shù)與發(fā)展，2013，23（8）:91-94.

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

[15]West D B.圖論導(dǎo)引[M].駱吉洲，李建中，譯，北京：電子工業(yè)出版社，2014.

An improved CSGC algorithm based on distribution fairness under the principle of Max-Sum-Reward

XU Song，LI Yu-feng
（College of Electronic and Information Engineering，Shenyang Aerospace University，Shenyang 110136，China）

For the problem of that the worse fairness of the allocation algorithm based on the traditional graph coloring，proposed a CSGC improved algorithm.Under the principle of Max-Sum-Reward，this algorithm improves the traditional CSGC algorithm by considering the factor of spectrum utilization.Especially in the cases of limited spectrum resource，this algorithm ensures the fairness of allocation and the needs of vulnerable users.The simulation results show that under the premise of system's reward this algorithm improves the overall fairness of the system.

cognitive radio；graph coloring；spectrum allocation；CSGC；fairness of allocation

TN929.5

：A

：1674－6236（2017）05-0097-06

2016-03-04稿件編號：201603036

徐 嵩（1986—），男，吉林公主嶺人，碩士研究生，助理工程師。研究方向：信息與通信工程。