動態(tài)頻譜分配的連通分支并行處理

覃玉榮 胡虹梅

（廣西大學(xué)計算機與電子信息學(xué)院，廣西 南寧 530004）

引 言

認(rèn)知無線電是有效解決當(dāng)前頻譜資源緊缺問題的最佳方案［1-2］。為適應(yīng)快速時變的認(rèn)知無線電環(huán)境，動態(tài)頻譜分配是必然要求。如何快速無干擾地分配頻譜資源，是認(rèn)知無線電頻譜分配算法研究的關(guān)鍵。

圖論著色模型是目前國內(nèi)外動態(tài)頻譜分配研究的熱點模型之一，其特點是將認(rèn)知無線電用戶所組成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)抽象成圖，則頻譜分配問題可轉(zhuǎn)化為對圖的著色研究。2005年，有學(xué)者在IEEE車載技術(shù)會議（VTC）上提出了避免干擾的List-Coloring頻譜分配算法，研究目標(biāo)為最大化系統(tǒng)頻段分配數(shù)［3］。同年5月，其他學(xué)者在IEEE Communica-tions提出了顏色敏感的圖論著色（CSGC）算法［4］，該算法考慮干擾和頻帶的差異性，以不同效益函數(shù)為分配目標(biāo)來提高頻譜利用率。2010年，Zhang Beiwei等在頻譜分配過程中引入群智能技術(shù)，探究系統(tǒng)帶寬收益與認(rèn)知用戶接入公平性之間的均衡［5］。此外，還有學(xué)者提出了局部議價算法，基于服務(wù)需求的分配算法等［6-11］。

目前國內(nèi)外基于圖論著色模型算法的基本特點是:在頻譜分配過程中，按照效益目標(biāo)函數(shù)逐次分配頻段給滿足條件的某單個認(rèn)知用戶，因此，存在時間開銷過大瓶頸問題。有學(xué)者采用頻譜并行分配（SAP）算法，即同時分配正交頻帶以嘗試縮短分配的循環(huán)周期，在一定程度上縮短了系統(tǒng)的頻譜分配時間開銷［12］。但該方法分配頻譜時仍然依次考慮整個系統(tǒng)中的認(rèn)知用戶，這是制約系統(tǒng)頻譜分配速率有效提高的一個重要因素。

為有效解決上述瓶頸問題，引入連通分量理論，結(jié)合并行原理，提出了一種基于圖論著色模型的快速頻譜分配新方法:將系統(tǒng)拓?fù)鋱D分解為無干擾的連通分支，用某種圖論算法并行處理各連通分支的頻譜分配，使多個無干擾的用戶同時獲取頻譜，在保證原算法系統(tǒng)收益不變的基礎(chǔ)上，大大提高了整個系統(tǒng)的頻譜分配速率，能夠有效解決目前基于圖論模型的分配算法時間開銷過大問題。利用所提的連通分支并行處理方法對SAP算法進行實例應(yīng)用探討。

1.連通分支并行方法

1.1 頻譜分配的圖論基本原理

頻譜分配圖論著色模型將認(rèn)知用戶的頻譜分配問題抽象成圖G=（V，E，S）對頂點的著色問題。其中頂點集合V= ｛vn｜n=1，2，…，N｝表示網(wǎng)絡(luò)中的所有認(rèn)知用戶；邊集E表示網(wǎng)絡(luò)中各頂點之間的干擾約束關(guān)系，若vn和vk有邊相連，表示認(rèn)知用戶vn和vk同時使用相同頻帶時會產(chǎn)生干擾；可選顏色列表S表示各認(rèn)知用戶的可用頻譜集合。

在無向圖中，如果從頂點vn存在到達(dá)頂點vk的路徑，則稱頂點vn和vk連通［13］。對應(yīng)于連通關(guān)系，存在著圖G 的頂點集分劃 ｛V1，V2，…，VW｝，使得圖G中任意兩個頂點vn和vk連通當(dāng)且僅當(dāng)vn和vk屬于同一個分塊Vw（1≤w≤W）。子圖G（Vi）中任意兩個頂點都是連通的，并且子圖G（Vi）中的頂點和G（Vj）的頂點（i≠j）絕不會連通，則子圖G（Vi）是拓?fù)鋱DG的極大連通子圖，稱為圖G的連通分支。

認(rèn)知無線電通信網(wǎng)絡(luò)系統(tǒng)中干擾是相互的，若vn使用某頻帶m會對vk產(chǎn)生干擾，則vk使用頻帶m也會對vn產(chǎn)生干擾，因此系統(tǒng)的干擾拓?fù)鋱D是一個無向圖，根據(jù)連通性原理可以將其分解成多個連通分支。

1.2 連通分支的求解

假設(shè)C= ｛cn，k｜cn，k∈ ｛0，1｝｝N×N是無向圖G 的布爾鄰接矩陣，其矩陣元素cn，k=1，當(dāng)且僅當(dāng)頂點vn與頂點vk之間有直接相連的邊。鄰接矩陣反映了拓?fù)鋱DG的所有信息，可以從中判定圖的連通性質(zhì)。根據(jù)圖的連通性原理，設(shè)計連通分支的求解步驟為:

第一步:根據(jù)圖的鄰接矩陣，計算傳遞閉包矩陣= （C+I）∧N

第二步:計算圖的連通矩陣CMN×N= ｛cmi，j｜cmi，j∈ ｛0，1｝｝N×N，當(dāng)且僅當(dāng)c+i，j≠0時cmi，j=1，表示（i，j）之間有路徑相連通。

第三步:求構(gòu)造矩陣DM，其第i行包含了頂點vi所連通的所有頂點名稱，根據(jù)構(gòu)造矩陣可計算出各連通分支包含的頂點以及相應(yīng)的連通子圖。

1.3 連通分支并行處理的提出

在認(rèn)知無線電網(wǎng)絡(luò)中，連通分支可以反映認(rèn)知用戶之間的干擾約束關(guān)系，分屬于不同連通分支的認(rèn)知用戶之間不會存在直接或者間接的干擾約束，對某個連通子圖的著色不會影響其他子圖的著色。因此，提出連通分支并行處理方法:同時為W 個連通分支分配頻譜資源，以提高算法的收斂速度。

處理流程如圖1所示。

圖1 連通分支并行處理流程圖

連通分支并行處理方法的性能特點:

1）通用性強。從圖1可知:系統(tǒng)總拓?fù)鋱DG的分解于分配頻譜前完成，故可用不同的分配算法同時為各連通分支分配頻譜資源，這些算法包括現(xiàn)有圖論模型下的List-Coloring算法、CSGC算法、SAP算法等。該處理方法能結(jié)合不同的圖論算法來有效分配頻譜。

2）系統(tǒng)帶寬收益較大。設(shè)各連通分支對應(yīng)的最優(yōu)分配矩陣分別為A1，A2，…，AW，由于各連通分支內(nèi)的頻譜分配是獨立進行的，相互之間不會產(chǎn)生任何干擾，因此，系統(tǒng)總拓?fù)涞淖顑?yōu)分配矩陣A與（A1，A2，…，AW）T等價，即 A= （A1，A2，…，AW）T.采用該方法分配頻譜不會造成系統(tǒng)帶寬收益的損失。

3）時間開銷較小。利用該方法，在每次的分配循環(huán)中都可以同時對圖G的W 個連通子圖完成一次頻譜分配，頻譜分配的時間開銷取決于各連通分支所需分配時間的最大值，所有分支完成分配的時間開銷為T連通=，遠(yuǎn)小于順序分配W 個連通子圖所需要的時間T總=Tw.其中，Tw為連通分支G（Vw）分配頻譜的時間開銷。

2.連通分支并行方法應(yīng)用實例

以SAP算法為研究對象，探討連通分支并行方法的實例應(yīng)用，驗證其有效性。假設(shè)在研究區(qū)域的一個分配周期內(nèi)，認(rèn)知系統(tǒng)的網(wǎng)絡(luò)拓?fù)浔３植蛔儯臻e頻譜資源可分成一系列正交子頻帶，頻帶間無干擾。SAP算法基于CSGC研究多個正交子頻帶的同時分配，一定程度上提高了頻譜分配的收斂速度。

基于SAP算法的連通分支并行處理應(yīng)用實例的基本原理是:依據(jù)系統(tǒng)內(nèi)認(rèn)知用戶之間的干擾拓?fù)鋱DG，按照連通分支求解算法得到圖G的各個連通分支G（Vw），1≤w ≤W，對于每個連通分支G（Vw），根據(jù)SAP算法的效益函數(shù)和分配準(zhǔn)則并行分配頻譜資源。

算法流程如圖2所示。

該實例算法包含雙重并行:第一，連通分支的并行。由于對某個連通分支內(nèi)的認(rèn)知用戶分配頻譜時不會對其他分支造成干擾，因此，各連通分支內(nèi)的頻譜分配可以同時實施；第二，頻帶的并行。對單個連通分支而言，M個正交子頻帶可以并行分配給該連通分支內(nèi)的認(rèn)知用戶，相互之間無干擾影響。這樣，每次循環(huán)至多能同時對圖G的W 個頂點完成一次資源分配，分配的收斂時間為單個連通分支完成分配所需時間的最大值，而SAP算法每次循環(huán)只能對圖G的一個頂點完成一次頻譜分配，其時間開銷為系統(tǒng)總拓?fù)渫瓿煞峙渌枰臅r間，即各個連通分支完成分配所需時間的總和。因此，基于SAP算法的連通分支并行處理應(yīng)用實例分配頻譜的時間開銷遠(yuǎn)小于原SAP算法，進一步有效提高了頻譜分配的收斂速度。

圖2 算法流程圖

3.仿真結(jié)果與分析

現(xiàn)對SAP算法和以SAP算法為研究對象的連通分支并行處理應(yīng)用實例（以下簡稱連通分支算法）進行MATLAB仿真。采用的分配準(zhǔn)則為協(xié)作式最大化系統(tǒng)帶寬總和（CMSB）準(zhǔn)則和非協(xié)作式最大化系統(tǒng)帶寬總和（NMSB）準(zhǔn)則［12］。仿真參數(shù)如表1、表2所示。為檢驗算法的準(zhǔn)確性，仿真結(jié)果取1000次隨機拓?fù)湎骂l譜分配結(jié)果的均值。

表1 仿真參數(shù)

表2 頻帶效益等級

3.1 時間開銷

為簡化比較，假設(shè)每次分配循環(huán)的執(zhí)行時間為t，則算法的時間開銷為總的分配循環(huán)次數(shù)乘以t.圖3是SAP算法與連通分支算法各自時間開銷占CSGC算法時間開銷的比例，從圖中可以看出，連通分支算法的比例曲線顯著低于SAP算法，表明連通分支算法的時間開銷低于SAP算法。

圖3 頻譜分配時間開銷

3.2 系統(tǒng)收益

算法帶來的系統(tǒng)帶寬收益用系統(tǒng)在一個分配周期內(nèi)的帶寬總收益（單位為10kbit／period）來衡量，可表示為·bn，m，仿真結(jié)果如圖4所示。從圖中可以看出，在CMSB、NMSB準(zhǔn)則下，兩種算法的系統(tǒng)帶寬收益均重合為一條曲線，說明連通分支算法得到的系統(tǒng)帶寬總收益與SAP算法的收益相同。

以上仿真結(jié)果表明:基于SAP算法的連通分支并行處理應(yīng)用實例的系統(tǒng)效益與原SAP算法相同，但是卻進一步顯著降低了頻譜分配的時間。

圖4 系統(tǒng)帶寬總收益

該應(yīng)用實例的探究結(jié)果表明:通過并行處理連通分支實現(xiàn)時間開銷降低的方法是快速有效的，且能夠保證算法原有的系統(tǒng)效益。

4.結(jié) 論

采用并行原理與圖論連通分量理論，提出了一種基于連通分支并行處理的快速頻譜分配新方法，有效解決了目前動態(tài)頻譜分配圖論算法普遍存在時間開銷過大的瓶頸問題。該方法能結(jié)合不同的圖論算法來有效分配頻譜資源，其特點是在一次分配過程中，同時并行處理多個連通分支內(nèi)的認(rèn)知用戶，在不影響系統(tǒng)原有效益的前提下，大大縮短了整個系統(tǒng)頻譜分配的時間。最后以圖論的SAP算法為研究對象，對所提出的連通分支并行處理方法進行了應(yīng)用驗證。仿真結(jié)果表明:采用連通分支并行處理方法的SAP算法，其系統(tǒng)效益與原SAP算法一致，但顯著降低了頻譜分配的時間開銷，更加適應(yīng)快變的認(rèn)知無線電環(huán)境。

［1］MITOLA J，GERALD Q，MAGUIR J R.Cognitive radio:making software radios more personal［J］.IEEE Personal Communications，Aug，1999:13-18.

［2］王 超，劉 濤，杜利平，等.一種新的認(rèn)知無線電主用戶信號識別方法［J］.電波科學(xué)學(xué)報，2009，24（6）:1119-1123.WANG Chao，LIU Tao，DU Liping，et al.A new method for recognizing the primary user in cognitive radio［J］，Chinese Journal of Radio Science，2009，24（6）:1119-1123.（in Chinese）

［3］WANG Wei，LIU Xin.List-coloring based channel allocation for open-spectrum wireless networks［C］／／The 62nd IEEE Vehicular Technology Conference.［s.n.］:May 2005，1:690-694.

［4］ZHENG Haitao，PENG Chunyi.Collaboration and fairness in opportunistic spectrum access［C］／／IEEE International Conference on Communication.［s.n］:May 2005，5:3132-3136.

［5］ZHANG Beiwei，HU Kunyuan，ZHU Yunlong.Spectrum allocation in cognitive radio networks using swarm intelligence［C］／／Second Intenational Conference on Communication Software and Networks，2010.Feb.2010:8-12.

［6］CAO L，ZHENG H.Distributed spectrum allocation via local bargaining［C］／／IEEE Sensor and Ad Hoc Communications and Networks 2005，Sept.2005:475-486.

［7］PENG Chunyi，ZHENG Haitao ZHAO Ben Y..Utilization and fairness in spectrum assignment for opportunistic spectrum access［J］.Mobile Networks and Applications，May 2006，11（4）:555-576.

［8］HE Shibiao，ZHANG Xinchun，GE Lijia，et al.Research of dynamic spectrum allocation based on service demand［C］／／2010Second International Conference on Networks Security Wireless Communications and Trusted Computing，June 2010，2:348-351.

［9］ZHANG Jianwu，ZHAO Qi，ZOU Jingyuan.Advanced graph-coloring spectrum allocation algorithm for cognitive radio［C］／／2009International Conference on Wireless Communications，Networking and Mobile Computing，Sep.2009:1-4.

［10］GE Yang，SUN Jun，SHAO Shixiang，et al.An improved spectrum allocation algorithm based on proportional fairness in cognitive radio networks ［C］／／IEEE International Conference on Communication Technology（ICCT），Dec.2010:742-745.

［11］樊 路，劉玉濤，譚學(xué)治，等.認(rèn)知無線電中基于極大獨立集的頻譜分配算法［J］，科學(xué)技術(shù)與工程，2009，9（16）:4645-4648.FAN Lu，LIU Yutao，TAN Xuezhi，et al.Spectrum allocation algorithm based on maximal independent set in cognitive radio networks［J］.Science Technology and Engineering，Aug.2009，9（16）:4645-4648.（in Chinese）

［12］廖楚林，陳 劼，唐友善，等.認(rèn)知無線電中的并行頻譜分配算法［J］.電子與信息學(xué)報，2007，29（7）:1608-1611.LIAO Chulin，CHEN Jie，TANG Youxi，et al.Parallel algorithm of spectrum allocation in cognitive radio［J］.Journal of Electronics＆Information Technology.2007，29（7）:1608-1611.（in Chinese）

［13］徐俊明.圖論及其應(yīng)用［M］.第2版.合肥:中國科學(xué)技術(shù)大學(xué)出版社，2004.8.

［14］廖楚林.認(rèn)知無線電系統(tǒng)的頻譜分配算法研究［D］.成都:電子科技大學(xué)碩士學(xué)位論文，2007.