覃玉榮 胡虹梅

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

引 言

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

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

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

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

1.連通分支并行方法

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

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

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

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

1.2 連通分支的求解

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

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

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

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

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

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

處理流程如圖1所示。

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

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

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

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

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

2.連通分支并行方法應用實例

以SAP算法為研究對象，探討連通分支并行方法的實例應用，驗證其有效性。假設在研究區(qū)域的一個分配周期內(nèi)，認知系統(tǒng)的網(wǎng)絡拓撲保持不變，空閑頻譜資源可分成一系列正交子頻帶，頻帶間無干擾。SAP算法基于CSGC研究多個正交子頻帶的同時分配，一定程度上提高了頻譜分配的收斂速度。

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

算法流程如圖2所示。

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

圖2 算法流程圖

3.仿真結果與分析

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

表1 仿真參數(shù)

表2 頻帶效益等級

3.1 時間開銷

為簡化比較，假設每次分配循環(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，仿真結果如圖4所示。從圖中可以看出，在CMSB、NMSB準則下，兩種算法的系統(tǒng)帶寬收益均重合為一條曲線，說明連通分支算法得到的系統(tǒng)帶寬總收益與SAP算法的收益相同。

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

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

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

4.結 論

采用并行原理與圖論連通分量理論，提出了一種基于連通分支并行處理的快速頻譜分配新方法，有效解決了目前動態(tài)頻譜分配圖論算法普遍存在時間開銷過大的瓶頸問題。該方法能結合不同的圖論算法來有效分配頻譜資源，其特點是在一次分配過程中，同時并行處理多個連通分支內(nèi)的認知用戶，在不影響系統(tǒng)原有效益的前提下，大大縮短了整個系統(tǒng)頻譜分配的時間。最后以圖論的SAP算法為研究對象，對所提出的連通分支并行處理方法進行了應用驗證。仿真結果表明:采用連通分支并行處理方法的SAP算法，其系統(tǒng)效益與原SAP算法一致，但顯著降低了頻譜分配的時間開銷，更加適應快變的認知無線電環(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］王 超，劉 濤，杜利平，等.一種新的認知無線電主用戶信號識別方法［J］.電波科學學報，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］樊 路，劉玉濤，譚學治，等.認知無線電中基于極大獨立集的頻譜分配算法［J］，科學技術與工程，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］廖楚林，陳 劼，唐友善，等.認知無線電中的并行頻譜分配算法［J］.電子與信息學報，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］徐俊明.圖論及其應用［M］.第2版.合肥:中國科學技術大學出版社，2004.8.

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