最大效益準則下基于分配公平性的CSGC改進算法

徐 嵩，李玉峰

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

最大效益準則下基于分配公平性的CSGC改進算法

徐 嵩，李玉峰

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

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

認知無線電；圖著色；頻譜分配；CSGC；分配公平性

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

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

1 基于CSGC的頻譜分配模型

假設在進行頻譜資源分配時，用戶的位置，可用的頻譜資源等環境條件都是靜態的。假設在一個認知網絡中，次級用戶（secondary user，簡寫為SU）的數量為N個（標號為0——N-1），頻譜信道的數量為M個（0——M-1）。則分配模型的構成如下：

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

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

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時將會互相干擾。限制條件由信道可用性決定， 例如 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 階二進制矩陣：如果信道m分配給用戶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階二進制矩陣：在初始化狀態時，SU為全1矩陣，在分配過程中，當用戶占用頻譜資源時，sun遞增1，否則sun維持當前值不變。

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

在本文中采用最大化總效益（Max-Sum-Reward）為頻譜分配的最優化目標函數，其可以表述為：

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

1）CSUM準則的標簽及著色表達式為：

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

bn，m/（Dn，m+1）為認知用戶使用頻譜信道m之后，對于整個系統的效益貢獻。此規則充分考慮了頻譜利用與相鄰用戶干擾之間的平衡，可以使系統性能達到全局最優。

2）NSUM準則的標簽及著色表達式為：

與CSUM規則相比，由于每個頂點只考慮自己的效益并忽略了對于整個系統的影響，此規則的表現較為自私，是非協作的。

2 基于分配公平性的CSGC頻譜分配改進算法

本算法的目標是在系統資源相對緊張時，在保證系統總效益損失不大的前提下，動態調節用戶分配的優先級順序，改善弱勢用戶分配地位并降低強勢用戶對于頻譜資源的占用，從而提高系統整體公平性，減少認知用戶間的“貧富差距”。基于此目標，在本算法中引入用戶頻譜資源占用參數，并根據此參數進行如下定義。

2.1 定 義

定義 次級用戶分配優先級P

文中根據用戶頻譜資源占用狀態來定義次級用戶的分配優先級，在每輪分配過程中按照用戶分配優先級順序進行頻譜分配，次級用戶分配優先級P的定義為：

根據公式（5）的定義，次級用戶的分配優先級與用戶信道占用狀態成反比。即用戶頻譜占用狀態越大則優先級越低，用戶頻譜占用狀態越小優先級則越高。通過調節SU，在頻譜資源分配過程中動態調節次級用戶的分配優先級P。

2.2 基于分配公平性的CSGC頻譜分配改進算法

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

本算法考慮了用戶頻譜資源占用參數，減少了強勢用戶對于頻譜資源占用的權重，降低了系統中用戶的“兩極分化”。在頻譜資源進行分配時，用戶優先級受用戶頻譜資源占用參數影響，被分配到頻譜資源越多的用戶優先級越低，被分配到頻譜資源越少的用戶優先級越高，未分配到的用戶優先級最高維持1不變。

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

步驟1 系統進行初始化，更新各個節點的信息，檢測用戶狀態，進行相關的建模。

步驟2 計算用戶分配優先級別矩陣P，找出用戶分配級別最高的頂點（認知用戶），并按照某種分配準則（如CSUM或者NSUM等）計算標簽值及其可用顏色（信道）。

步驟3找出標簽值最大的頂點n，并判斷頂點n是否唯一。若頂點n唯一，對其分配相對應顏色m。若頂點n不唯一，則隨機選取一個頂點進行分配。

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

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

步驟6 當最低級別的用戶完成分配后，本輪分配結束。

圖1 算法流程圖

3 算法仿真及仿真結果分析

3.1 仿真參數與環境設定

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

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

3.2 仿真結果及結果分析

在完成上述仿真參數及環境設定之后，分別在CSUM準則與NSUM準則下對原始CSGC頻譜分配算法和本算法進行仿真實驗，最終仿真結果如圖2～4所示。

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

圖2 用戶被分配的頻譜資源數折線圖

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

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

4 結 論

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

圖3 系統效益折線圖

圖4 用戶分配頻譜資源柱形統計圖

參考文獻：

[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]王欽輝，葉保留，田宇等.認知無線電網絡中頻譜分配算法[J].電子學報，2012，40（1）:147-154.

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

[5]楊鐵軍，林培培.改進遺傳算法的認知無線電頻譜分配[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]廖楚林，陳劼，唐友喜，等.認知無線電中的并行頻譜分配算法[J]．電子與信息學報，2007，29（7）:1608-1611.

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

[13]鄭志剛，薛菲，周井泉.網絡效益最大化的認知無線電頻譜分配方法[J]．計算機技術與發展，2013，23（8）:91-94.

[14]賈杰，王闖，張朝陽，等.認知無線電網絡中基于圖著色的動態頻譜分配[J].東北大學學報，2012，33（3）：336-339.

[15]West D B.圖論導引[M].駱吉洲，李建中，譯，北京：電子工業出版社，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—），男，吉林公主嶺人，碩士研究生，助理工程師。研究方向：信息與通信工程。