鄭艷，徐國(guó)軍，覃錫忠，賈振紅

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

2.中國(guó)移動(dòng)通信集團(tuán)新疆有限公司，烏魯木齊 830046

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

鄭艷1，徐國(guó)軍2，覃錫忠1，賈振紅1

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

2.中國(guó)移動(dòng)通信集團(tuán)新疆有限公司，烏魯木齊 830046

1 引言

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

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

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

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

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

2.1 圖論模型的數(shù)學(xué)描述

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

2.2 標(biāo)號(hào)準(zhǔn)則

假設(shè)效益矩陣B在分配周期內(nèi)是不發(fā)生改變的。在著色時(shí)，將某顏色帶來的收益越大的頂點(diǎn)，標(biāo)上越大的號(hào)。對(duì)于各個(gè)單色連通分支頂點(diǎn)，本文制定了協(xié)作和非協(xié)作方式下的標(biāo)號(hào)準(zhǔn)則。

（1）協(xié)作式準(zhǔn)則

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

（2）非協(xié)作式準(zhǔn)則

在標(biāo)號(hào)過程中，若出現(xiàn)最大標(biāo)號(hào)頂點(diǎn)不唯一的情況，就隨機(jī)選擇其中的一個(gè)分配相應(yīng)的顏色m。

2.3 用戶滿意度

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

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

2.4 可調(diào)整顏色的計(jì)算

假設(shè)對(duì)滿足需求的頂點(diǎn)n*和未滿足需求的頂點(diǎn)n作分配調(diào)整。本文算法定義的頂點(diǎn)n的可調(diào)整顏色集合計(jì)算式如下：

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

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

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

3 算法步驟

本文分為兩個(gè)階段進(jìn)行頻譜分配：一是根據(jù)信道效益情況對(duì)用戶標(biāo)號(hào)來完成初次頻譜分配；二是考慮用戶需求，調(diào)整某些頻譜的分配得到最終的分配結(jié)果。在文獻(xiàn)[11-12]中具體給出了對(duì)拓?fù)鋱D的分塊方法，文中不再過多講解。而用戶滿意度均衡的調(diào)整分配算法在下面的流程圖介紹中將詳細(xì)給出。

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

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

圖1 算法流程圖

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

4 仿真結(jié)果與分析

下面對(duì)PASA算法和CBSA算法以及本文的PCU算法進(jìn)行MATLAB仿真。仿真參數(shù)如表1所示，本文的用戶效益權(quán)值和需求參考IEEE 802.22的設(shè)定，同時(shí)為了保證算法的準(zhǔn)確性，仿真結(jié)果取多次隨機(jī)的拓?fù)鋱DG仿真結(jié)果的均值。

表1 仿真參數(shù)

4.1 時(shí)間開銷

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

圖2 協(xié)作式下頻譜分配時(shí)間開銷

圖3 非協(xié)作式下的頻譜分配時(shí)間開銷

4.2 滿意用戶比例

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

圖4 滿意用戶所占比例

5 結(jié)論

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

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

[12]覃玉榮，胡虹梅.動(dòng)態(tài)頻譜分配的連通分支并行處理[J].電波科學(xué)學(xué)報(bào)，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

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

認(rèn)知無線電；頻譜分配；圖論著色；并行；連通分支

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.

中國(guó)移動(dòng)通信集團(tuán)新疆有限公司研究發(fā)展基金項(xiàng)目（No.xjm2012-1）。

鄭艷（1987—），女，碩士生，研究方向?yàn)闊o線網(wǎng)絡(luò)優(yōu)化和云計(jì)算；徐國(guó)軍（1983—），男，網(wǎng)絡(luò)工程師，研究方向?yàn)榫W(wǎng)絡(luò)優(yōu)化；覃錫忠（1963—），男，副教授，碩士研究生導(dǎo)師，研究方向?yàn)閿?shù)字信號(hào)處理；賈振紅（1964—），男，教授，博士生導(dǎo)師，研究方向?yàn)楣庑畔⑻幚?、信?hào)與信息處理、云計(jì)算等。E-mail：jzhh@xju.edu.cn

2012-10-29

2012-12-15

1002-8331（2014）18-0197-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-01-11，http://www.cnki.net/kcms/detail/11.2127.TP.20130111.0953.022.html