均衡滿意度的并行單色連通分支頻譜分配算法

鄭艷，徐國軍，覃錫忠，賈振紅

1.新疆大學信息科學與工程學院，烏魯木齊 830046

2.中國移動通信集團新疆有限公司，烏魯木齊 830046

均衡滿意度的并行單色連通分支頻譜分配算法

鄭艷1，徐國軍2，覃錫忠1，賈振紅1

1.新疆大學信息科學與工程學院，烏魯木齊 830046

2.中國移動通信集團新疆有限公司，烏魯木齊 830046

1 引言

認知無線電（Cognitive Radio，CR）是當前一種常用的智能共享頻譜資源的技術，它使頻譜資源的使用更加科學合理化，從而改善了次用戶頻譜資源緊缺的問題[1-2]。CR技術是基于時間和空間都快速發生變化的動態環境中的，相比于傳統信道指配里固定信道的分配，CR的頻譜分配方法的有效性直接影響到該系統性能是否達到最優[3-5]。圖論著色的頻譜分配方案是如今主要的頻譜分配方法之一，它將CR網絡中的頻譜分配問題映射成對無向圖G的頂點著色問題[6-8]，是一種簡單易行的方法。

圖論的經典算法是顏色敏感著色[8]（Color Sensitive Graph Coloring，CSGC）算法，它考慮了頻譜效益的差異性和干擾的頻譜差異性，提出了帶權重的復合圖的列表著色[9]（List Coloring，LC）算法。然而CSGC算法存在的一個缺點就是運算量大，隨著用戶數和頻譜數的增加運算量成非線性增加，導致了分配時間較長，大大降低了算法的有效性。判斷一種算法的優劣要考慮它的有效性、公平性、擴展性和它是否使結果最優。為了改進CSGC算法，研究者大多從以下四個方面入手：一是考慮用戶數對算法執行時間的影響，譬如分布式局部議價[10]（Local Bargaining，LB）算法，該算法每次分配時，利用前一次分配的信息，只對局部變動的拓撲進行議價分配，但是分配結果是次優的。二是考慮分配開銷與頻譜數目的關系，如并行頻譜分配[11]（Parallel Algorithm of Spectrum Allocation，PASA）算法，該算法將干擾圖分解成相比于CSGC算法的網絡拓撲圖簡單的單色子圖，對各子圖的并行著色降低了算法的分配時間，但是每個單色子圖只選擇一個標號最大的頂點著色，由干擾關系更新拓撲后才能對該顏色下的其他頂點著色，并沒有完全解決開銷較大的問題。三是從圖的結構出發，如今年發表的連通分支（Connected Branch of Spectrum Allocation，CBSA）算法，將圖G分解為各個無干擾的連通分支，并且在并行處理各連通分支的頻譜分配時，可以同時使多個無干擾的用戶獲取頻譜，既保證了原算法系統收益不變化，又大大提高了整個系統的頻譜分配速率[12]，但是各子圖可能含有若干種顏色，一種顏色分配完后需要更新拓撲繼續分配，依然沒有完全解決開銷較大的問題。四是從分配思想上出發，如改進的頻譜分配[13]（Improved Algorithm of Spectrum Allocation，IASA）算法，打破先標號再分配的思想，同時進行標號和分配減少時間開銷，但IASA算法在頻譜分配過程中需要刪除部分頻譜減少運算來換取系統效用，導致頻譜資源的復用率降低，得到的是比預期低的系統性能。此外，一些算法對用戶的實際需求考慮得也不全面，大多只考慮了最大化系統帶寬，不合理的分配造成了頻譜資源的二次浪費[8-15]。為此，本文為了提高CSGC算法在動態分配中有效性和可擴展性，針對可并行計算的并行算法和連通分支算法存在的不足，提出了兼顧時間開銷和用戶需求的均衡用戶滿意度的并行單色連通分支頻譜分配新算法，從根本上解決時間開銷較大和用戶滿意度不均衡的問題。

2 用戶滿意度均衡的并行單色連通分支頻譜分配算法原理

在PASA算法里基于頻帶正交假設，對某個頻譜的使用不會對其他頻譜造成干擾[8]，即對某個單色子圖的著色不會影響到其他子圖的著色。又由連通分量理論可知各連通分量子圖之間不存在直接或者間接的干擾關系[12]，所以PASA算法和CBSA算法都能并行處理頻譜分配問題。本文結合二者在頻譜和系統拓撲結構上的特點將圖G分解成各個無干擾的單色連通分量子圖，同時對這些子圖并行著色。得到了與PASA算法和CBSA算法相同的分配結果。由于系統拓撲圖G分解成的單色連通分量子圖數目可能會增多，而且每個子圖只需要進行一次分配無需計算更新拓撲，所以該方法可以有效地減少時間開銷。并且圖分解是在分配頻譜之前進行的，所以它可以應用在所有圖論模型里。

然而上述分配并沒有考慮到各個用戶的實際需求，本文將繼續改善分配結果，把滿足需求和沒有滿足需求的用戶分配到的頻譜作調整，均衡了各用戶的滿意度，使未滿足需求的用戶滿足需求或趨近于需求。

2.1 圖論模型的數學描述

假設在一個分配周期里的認知網絡固定。網絡中有N個認知用戶，存入集合V={n|n∈[1，N]}；M個頻譜，存入集合Ms={m|m∈[1，M]}。將認知用戶的頻譜分配問題抽象成圖G=(V，E，L)對頂點的著色問題[8]，則算法的數學模型可以由可用頻譜矩陣L、效益矩陣B、需求矩陣D、干擾矩陣集合C、各用戶有效分配頻譜集合An、用戶滿意度大于1的用戶集合F和小于1的用戶集合K、可調整頻譜集合U等來描述。

2.2 標號準則

假設效益矩陣B在分配周期內是不發生改變的。在著色時，將某顏色帶來的收益越大的頂點，標上越大的號。對于各個單色連通分支頂點，本文制定了協作和非協作方式下的標號準則。

（1）協作式準則

其中Vmw是單色連通分支Gmw所含頂點的集合，bn，m是效益矩陣的元素，Dn，m代表在頻譜m上與認知用戶n有干擾沖突的用戶數，即單色連通分支Gmw除去頂點n剩下頂點的個數。

（2）非協作式準則

在標號過程中，若出現最大標號頂點不唯一的情況，就隨機選擇其中的一個分配相應的顏色m。

2.3 用戶滿意度

用戶滿意度是指某用戶的需求在頻譜分配后得到滿足的程度[14]，所以用戶的滿意度與用戶的需求緊密相關，是衡量用戶得到需求的重要參數。根據實際情況可以是基于業務的傳輸速率、用戶等待時間、用戶帶寬、吞吐量等需求的滿意度。本文針對可以累積疊加的用戶需求制定的滿意度如下：

其中An是頂點n分配到的顏色集合，dn是需求矩陣的元素，且當dn=0時，用戶滿意度sn=1。從式子中可以看出，sn≥1指用戶需求得到滿足，反之是指用戶需求未得到滿足。

2.4 可調整顏色的計算

假設對滿足需求的頂點n*和未滿足需求的頂點n作分配調整。本文算法定義的頂點n的可調整顏色集合計算式如下：

其中n的可用顏色集合Ln由可用頻譜矩陣L得到，An*指頂點n*分配到的顏色集合，CMsAn指該網絡的所有頻譜集合Ms中未分配給頂點n的顏色集合。

考慮到取消某顏色的分配后滿足需求的頂點可能會變成不滿足需求的頂點，所以頂點n*和所有未滿足需求的頂點都可以調整的顏色矩陣如下：

其中，r和n3分別指取消分配后頂點n*的需求依然滿足的顏色集合R的元素和元素個數，n和n1分別指未滿足需求頂點集合K的元素和元素個數。若r∈Un，則pr，n=1。所以pr，n=1指r是頂點n和n*都可以調整的顏色。

3 算法步驟

本文分為兩個階段進行頻譜分配：一是根據信道效益情況對用戶標號來完成初次頻譜分配；二是考慮用戶需求，調整某些頻譜的分配得到最終的分配結果。在文獻[11-12]中具體給出了對拓撲圖的分塊方法，文中不再過多講解。而用戶滿意度均衡的調整分配算法在下面的流程圖介紹中將詳細給出。

根據本文的算法思想，具體的流程如圖1所示。

該算法對系統拓撲圖進行處理后，最終分解成了W個單色連通分量子圖。為了表現出矩陣和集合的意義方便大家理解，由頻譜特點分解成的子圖命名為G1…GM，下標表示該子圖是此顏色下的所有頂點的干擾關系。再由連通分量分解法分解成的單色連通分支Gmw(1≤W≤w)下標的首位和第二位指該連通分支頂點是關于m色的干擾關系并且是第w個連通分支。同理，頂點集合的名稱也隨著算法在改變，完成預分配后頂點存入的集合為Vmwn，是指將顏色m分配給了頂點n的單色連通分支Gmw的頂點集合。

圖1 算法流程圖

完成第一階段的預分配后要對各頂點的分配作調整。先將滿意度最大的滿足需求的頂點n*與所有未滿足需求的頂點根據式（4）計算各自的可調整顏色集合Un。再計算取消分配仍能使n*滿足需求的顏色集合R，為了不使滿足需求頂點取消分配的顏色對它的需求影響太大，本文將集合內的元素按對n*的效益權值從小到大排序。由式（5）得到n*和K中元素都可以調整的各顏色下的未滿足需求頂點集合Q，由于上面的排序，依次存入集合的是對頂點n*的需求影響小的顏色r下的滿意度最低的頂點n。由上面的命名方式能快而直接地找到分配顏色r給n*的單色連通分支的頂點集合Vrwn*，并判斷n是否也是該連通分支的頂點，如果是，就能取消給n*分配r而將r分給n。每次調整分配成功，n和n*的滿意度都會變化。如果頂點n滿足了需求，就從K中刪除n，否則重新計算滿足sn*-bn*，m/dn*≥1的顏色集合R，繼續n*和n的顏色調整。如果最大滿意度頂點n*取消了所有能調整分配的顏色后仍不能使未滿足需求頂點滿足需求，就從F中刪除n*，直到F集合或者K集合中沒有可調整分配的滿足需求頂點或未滿足需求頂點為止。

4 仿真結果與分析

下面對PASA算法和CBSA算法以及本文的PCU算法進行MATLAB仿真。仿真參數如表1所示，本文的用戶效益權值和需求參考IEEE 802.22的設定，同時為了保證算法的準確性，仿真結果取多次隨機的拓撲圖G仿真結果的均值。

表1 仿真參數

4.1 時間開銷

不考慮用戶滿意度的均衡，通過原理可以得到這三種算法頻譜分配的時間取決于分解成的各小塊所需要的分配時間的最大值，所以在相同系統拓撲圖下，由于PCU算法進行著色的子圖比PASA算法、CBSA算法的還要簡單，所以新算法的運算量少，相應的時間開銷更少。本文的比較采取文獻[12]的方法，假設每次分配的循環執行時間為T，時間開銷：t=h×T，其中h是總的執行分配次數。如圖2和圖3是用戶數N取6時PASA算法、CBSA算法及PCU算法在協作準則和非協作準則下分別占CSGC算法的時間開銷比例隨頻譜數目增加而變化的曲線。從圖中可以看出，隨著頻譜數目M的增加，時間開銷比例呈下降趨勢。這是因為CSGC算法的分配循環執行次數隨頻譜數目的增加近似呈線性增加；PASA算法循環執行次數與待分配的頻譜數目無關，循環執行次數幾乎不變；CBSA算法循環執行次數略小于PASA算法[11-12]；而PCU算法執行一次便能完成分配無需循環。所以這三種算法的曲線近似于反比例函數圖，但鑒于實際拓撲圖的不同會出現一些突變點。

圖2 協作式下頻譜分配時間開銷

圖3 非協作式下的頻譜分配時間開銷

4.2 滿意用戶比例

根據式（3）很容易便能計算出用戶滿意度大于等于1的滿足需求用戶數占總用戶數的比例。如圖4是用戶數N取12時這三種算法的滿意用戶占總用戶數的比例。隨著頻譜數目的增加，三種算法的滿足需求用戶比例都有提高。這是由于在分配周期內用戶需求不變化的情況下，隨著頻譜數目的增加，頻譜復用的程度有所增加，用戶獲得的信道效益增多，滿足需求的用戶也隨之增加。還可以看出PASA算法和CBSA算法的滿意用戶所占比例完全相同，PCU算法滿意用戶比例最高并且隨著頻譜數目的增加所有用戶最先達到全部滿足需求的情況。這與PASA算法和CBSA算法的頻譜分配相同，PCU算法根據用戶需求調整分配使更多用戶滿足需求有關。再者，隨機生成的拓撲圖不同導致分配結果也有所不同，所以當頻譜資源少的時候偶爾會出現滿意用戶，即滿意用戶的比例沒有從0開始。

圖4 滿意用戶所占比例

5 結論

本文研究了認知無線電網絡中各類基于圖論著色模型的頻譜分配算法，在詳細分析了CSGC算法的各種改進算法后，提出一種用戶滿意度均衡的并行單色連通分支頻譜分配算法。該算法適用于所有基于圖論的算法處理系統拓撲圖，其特點是：將復雜的系統拓撲圖分解成較多的可以并行計算的無干擾單色連通分量子圖，無需循環更新拓撲圖就能一次性完成分配，大大降低了時間開銷。考慮到實際應用，又采取了均衡用戶滿意度的方法來調整頻譜分配結果，使更多用戶滿足效益需求。并且與并行算法和連通分支算法在時間開銷和滿意用戶比例方面進行比較，仿真表明：新的改進CSGC算法分配時間與頻譜數無關，提高了可擴展性和有效地減少了時間開銷，也更適于實際應用。

[1]Stotas S，Nallanathan A.On the throughput and spectrum sensing enhancement of opportunistic spectrum access cognitive radio networks[J].IEEE Transactions on Wireless Communications，2012，11（1）：97-107.

[2]Leshem A，Zehavi E，Yaffe Y.Multichannel opportunistic carrier sensing for stable channel access control in cognitive radio systems[J].IEEE Journal on Selected Areas in Communications，2012，30（1）：82-95.

[3]Janssen J，Kilakos K，Marcotte O.Fixed preference channel assignment for cellular telephone systems[J].IEEE Transactions on Vehicular Technology，1999，48（2）：533-541.

[4]Akyildiz I F，Lee Won-Yeol，Vuran M C，et al.A survey on spectrum management in cognitive radio networks[J]. IEEE Journal on Communications Magazine，2008，46（4）：40-48.

[5]MacKenzie A B，Reed J H，Athanas P，et al.Cognitive radio and networking research at Virginia tech[J].Proceedings of the IEEE，2009，97（4）：660-688.

[6]Nguyen M V，Lee Hwang Soo.Effective scheduling in infrastructure-based cognitive radio networks[J].IEEE Transactions on Mobile Computing，2011，10（6）：853-867.

[7]Rahwan I，Jahedpari F，Abdallah S.The dynamics of two cognitive heuristics for coordination on networks[C]//2010 IEEE Second International Conference on Social Computing，2010：473-479.

[8]Zheng Haitao，Peng Chunyi.Collaboration and fairness in opportunistic spectrum access[C]//IEEE 2005 International Conference on Communications，Washington DC，2005：3132-3136.

[9]Wang Wei，Liu Xin.List-coloring based channel allocation for open-spectrum wireless networks[C]//Proceedings of IEEE the 62nd Vehicular Technology Conference，Washington DC，2005：690-694.

[10]Cao Lili，Zheng Haitao.Distributed spectrum allocation via local bargaining[C]//Second Annual IEEE Communications Society Conference，2005：475-486.

[11]廖楚林，陳劼，唐友善，等.認知無線電中的并行頻譜分配算法[J].電子信息學報，2007，29（7）：1608-1611.

[12]覃玉榮，胡虹梅.動態頻譜分配的連通分支并行處理[J].電波科學學報，2012，27（1）：152-156.

[13]Wang Jiao，Huang Yuqing，Jiang Hong.Improved algorithm of spectrum allocation based on graph coloring model in cognitive radio[C]//2009 WRI International Conferences on Communications and Mobile Computing，Washington DC，2009：353-357.

[14]Gozupek D，Eraslan B，Alagoz F.Throughput satisfaction based scheduling for cognitive radio networks[J]. IEEE Trans on Vehicular Technology，2012，61（9）：1-16.

[15]Stotas S，Nallanathan A.Enhancing the capacity of spectrum sharing cognitive radio networks[J].IEEE Trans on Vehicular Technology，2011，60（8）：3768-3779.

ZHENG Yan1,XU Guojun2,QIN Xizhong1,JIA Zhenhong1

1.Institute of Information Science and Engineering,Xinjiang University,Urumqi 830046,China
2.Subsidiary Company of China Mobile in Xinjiang,Urumqi 830046,China

This paper analyzes the various spectrum allocation algorithms of graph coloring theory and concerns the problem of costing too much time.It combines connected component theory with the method that divides graph into subgraphs which have one color.A new method is proposed,which can parallel process all one-colored connected branches.This method can be applied to each algorithm to divide graph into small slices.And in view of the problem of unbalanced degree of users’satisfaction,an amendment is presented,which adjusts allocated spectrums to improve the proportion of satisfied users.The simulation results show that the proposed algorithm is fast and makes more users meet the needs of requirements effectively.

cognitive radio;spectrum allocation;graph coloring;parallel;connected branch

針對各類圖論著色頻譜分配算法的時間開銷過大的問題，提出了一種并行單色連通分支處理拓撲圖的方法。該方法結合連通分量理論和單色子圖分解法，可應用于目前所有的圖論著色模型的拓撲圖分解中。并且根據認知用戶的需求來調整分配使滿意的用戶比例增大，從而解決了分配結果存在的用戶滿意度不均衡情況。仿真結果表明，提出的算法是一種快速且能夠使更多用戶滿足需求的有效方法。

認知無線電；頻譜分配；圖論著色；并行；連通分支

A

TN98

10.3778/j.issn.1002-8331.1210-0291

ZHENG Yan,XU Guojun,QIN Xizhong,et al.Parallel process one-colored connected branches in spectrum allocation algorithm based on degree of users’satisfaction balancing.Computer Engineering and Applications,2014,50（18）：197-201.

中國移動通信集團新疆有限公司研究發展基金項目（No.xjm2012-1）。

鄭艷（1987—），女，碩士生，研究方向為無線網絡優化和云計算；徐國軍（1983—），男，網絡工程師，研究方向為網絡優化；覃錫忠（1963—），男，副教授，碩士研究生導師，研究方向為數字信號處理；賈振紅（1964—），男，教授，博士生導師，研究方向為光信息處理、信號與信息處理、云計算等。E-mail：jzhh@xju.edu.cn

2012-10-29

2012-12-15

1002-8331（2014）18-0197-05

CNKI網絡優先出版：2013-01-11，http://www.cnki.net/kcms/detail/11.2127.TP.20130111.0953.022.html