徐金玉，柳 平

(1.揭陽職業(yè)技術(shù)學(xué)院，廣東揭陽 522000;2.汕頭大學(xué)，廣東汕頭 515000)

0 引言

隨著無線移動通信的快速發(fā)展，無線頻譜資源的利用顯得越來越緊張，人們對無線寬帶通信技術(shù)的應(yīng)用提出了更高的要求，頻譜資源利用問題成為人們關(guān)注的熱點。為了滿足用戶對系統(tǒng)服務(wù)質(zhì)量(quality of service，QoS)的要求，當(dāng)前無線網(wǎng)絡(luò)管理模式都采用固定頻譜分配制度，即特定的通信業(yè)務(wù)享有頻譜管理部門所授權(quán)的特定頻譜。通過文獻［1－4］分析得出目前頻譜的使用現(xiàn)狀:大量時間里，許多頻譜處于空閑狀態(tài)，還有許多頻譜只獲得了部分使用，剩下的少量頻譜使用十分擁擠。從而文獻［3］提出了“頻譜空洞”的概念:分配給主用戶，在特定時間段和空間地理位置并不使用的頻譜。文獻［5］和［6］研討了探測頻譜空洞的方法，文獻［7］研究了如何合理地使用頻譜空洞為人類帶來新的效益。認(rèn)知無線電的產(chǎn)生為無線通信領(lǐng)域的可持續(xù)發(fā)展開啟了新的篇章。當(dāng)前大部分研究主要集中在利用動態(tài)頻譜分配算法解決無線頻譜利用率低的問題。Ian F.Akyildiz和LeeWon－Yeo在文獻［8］中列舉了無線頻譜共享技術(shù)面臨的巨大挑戰(zhàn)，其一在于如何探測用戶對頻譜的需求，文獻［9］提出了協(xié)作模式下的頻譜感知方法，文獻［10］提出了一種檢測頻譜感知效率的標(biāo)準(zhǔn);其二在于如何建立一個有效的中央控制系統(tǒng)管理頻譜分配，而其中關(guān)鍵就在于分配算法。

隨著認(rèn)知無線電的深入研究，基于圖論著色理論的認(rèn)知無線電網(wǎng)絡(luò)的頻譜分配算法已經(jīng)有了不少成果，提出了圖論著色(list coloring，LC)頻譜分配算法［11］，顏色敏感的圖論著色(color sensitive graph coloring，CSGC)頻譜分配算法［12］及 2 種改進算法［13－14］，分布式局部議價頻譜分配算法［15］，并行頻譜分配算法［16］。List－Coloring 算法比較類似于傳統(tǒng)蜂窩小區(qū)的小區(qū)間的頻率規(guī)劃，目標(biāo)是最大化復(fù)用因子，但是List－Coloring算法未考慮認(rèn)知無線電系統(tǒng)頻譜分配中頻譜效益的差異性和干擾的頻譜差異性。CSGC算法則考慮這兩種差異性，并給出復(fù)合圖的帶權(quán)重的List－Coloring算法，然而CSGC算法存在運算量過大的問題，并隨著用戶數(shù)和頻譜數(shù)的增加成非線性增加，而且不考慮用戶的實際需求，導(dǎo)致頻譜分配的實際效率不高。分布式局部議價的分配方法假設(shè)初始分配是全局最優(yōu)，之后的每次分配利用前一次分配的信息，只對局部變動的拓?fù)溥M行議價分配以達到最優(yōu)，從而減少運算開銷。并行頻譜分配算法降低了分配的時間開銷，適應(yīng)了認(rèn)知無線電空閑頻譜快速時變的特點?；谛枨蟮母倪M算法更好地滿足了系統(tǒng)的需求，但是該算法僅限于一個循環(huán)周期，當(dāng)頻譜資源不足時，即使某用戶等待時間很長，該算法仍無法滿足此用戶的需求。基于用戶等待時間的頻譜分配改進算法使用戶有趨于均衡的機會使用頻譜，保證了系統(tǒng)的公平性，但是忽略了用戶的實際要求，可能出現(xiàn)帶寬需求很小的用戶卻分配到很大帶寬的情況，造成頻譜資源浪費，降低了頻譜的利用率。

本文提出基于用戶等待時間和帶寬需求的改進CSGC算法，從認(rèn)知用戶的利益出發(fā)，兼顧用戶等待時間和帶寬需求。一方面保證等待時間長的用戶使用頻譜的優(yōu)先權(quán)和弱勢用戶的分配權(quán)，提高了系統(tǒng)的公平性;另一方面，在主用戶釋放頻譜資源充足的情況下，使分配結(jié)果最大化滿足用戶帶寬需求，提高系統(tǒng)的頻譜利用率，而在頻譜資源匱乏時，適當(dāng)犧牲部分系統(tǒng)效益，加速分配過程，擴大分配用戶數(shù)，達到效益和公平性的平衡。

1 基于用戶等待時間和帶寬需求的改進CSGC算法

1.1 頻譜分配數(shù)學(xué)模型

為了便于量化分析，建立圖論著色數(shù)學(xué)模型［11］，我們定義以下數(shù)量關(guān)系:其中 i表示用戶，j表示頻譜。

1 )空閑矩陣L。L=(li，j)代表空閑矩陣，即用戶可使用的頻譜矩陣。當(dāng)li，j=1，表示頻譜j對用戶i是可用的;否則，li，j=0，表示頻譜j對用戶i是不可用的。

2 )效益矩陣B。B=(bi，j)代表效益矩陣。即用戶i使用頻譜j給系統(tǒng)帶來的效益，實際研究過程中，用實際效益矩陣 LB=(li，j·bi，j)，代表實際情況下頻譜j對用戶i的效益，即頻譜j對用戶i可用則產(chǎn)生效益為bi，j，否則，即頻譜 j對用戶 i不可用時產(chǎn)生的效益為0。

3 )用戶帶寬需求矩陣Λ。Λ =(λi)代表用戶帶寬需求矩陣，即用戶i需要的帶寬是λi。用戶需求是指用戶的長期需求。

10 )用戶等待次數(shù)。在某個用戶從系統(tǒng)開始分配直到其帶寬需求獲得滿足或者分配結(jié)束這一時間段內(nèi)系統(tǒng)分配的次數(shù)，它表示此用戶為了獲得足夠帶寬需要等待時間的長度。

1.2 算法分配目標(biāo)

本算法的目的:在頻譜資源比較充分時，對頻譜進行有效分配，使系統(tǒng)總效益最大化;當(dāng)頻譜資源比較緊張時，在保持系統(tǒng)總效益損失不大的情況下，使所有認(rèn)知用戶未獲得滿足的帶寬需求總和最小化，兩種情況的分配均保證以下2個要求。

1 )弱勢用戶在付出較長的等待時間后將會獲得分配機會。

2 )當(dāng)認(rèn)知用戶的帶寬需求獲得滿足后系統(tǒng)不再對其進行分配。從而系統(tǒng)將在滿足當(dāng)前用戶的帶寬需求的前提下，盡量預(yù)備更多空閑頻譜用以分配給新加入系統(tǒng)的用戶。定義I表示認(rèn)知用戶總數(shù)，J表示可用頻譜總數(shù)，數(shù)學(xué)描述如下。

在頻譜資源充分的情況下有

1.3 算法思想及步驟

盡管認(rèn)知用戶伺機地使用主用戶所釋放的頻譜資源，但是，在保證主用戶的權(quán)益的前提下，認(rèn)知用戶的接入提高了系統(tǒng)的頻譜利用率。所以，作為認(rèn)知無線電系統(tǒng)中的一種特定的用戶，我們有必要考慮認(rèn)知用戶的利益?；谟脩舻却龝r間和帶寬需求的改進CSGC算法就是從考慮用戶的等待時間公平性和頻譜需求的實際出發(fā)的。

算法設(shè)計過程中，以等待時間為切入點，頻譜分配的整體思想是盡量保證等待時間更長的用戶的優(yōu)先權(quán)。

以頻譜需求為切入點，我們考慮3種情況。

1 )當(dāng)頻譜滿足用戶的需求時，用戶退出分配。

3 )當(dāng)用戶未獲得任何頻譜資源時，等待時間加1。如此循環(huán)，通過更新節(jié)點，檢測新用戶的到來。保證等待時間長的用戶優(yōu)先獲得頻譜，而且最終使用戶的頻譜需求獲得滿足。

我們定義掃描周期T代表2次掃描之間的間隔時間，程序執(zhí)行時間t代表從上一次更新節(jié)點信息到當(dāng)前時刻的間隔時間，用戶等級矩陣GR中等級最高的頂點，其對應(yīng)等級為gm。初始化系統(tǒng)后，算法步驟如下。

步驟1 更新節(jié)點信息，檢測新用戶，建立圖論著色數(shù)學(xué)模型［11］以及相關(guān)矩陣和變量。

步驟2 判斷圖G［11］是否為空，若為空，等待時間t=T，即等待下一個掃描周期;若非空，進入步驟3。

步驟3 搜索用戶等級矩陣GR中等級最高的頂點，其對應(yīng)等級為gm。并按照分配準(zhǔn)則計算其標(biāo)簽值以及可用顏色。

步驟4 搜索標(biāo)簽值最大的頂點i。

步驟5 判斷標(biāo)簽值最大的頂點i是否唯一。若唯一，對其分配相應(yīng)的顏色j，即效益不等按效益分配;否則，隨機選擇一個頂點對其分配相應(yīng)的顏色j，即效益相等隨機分配。

步驟6 更新頂點i需求，重新賦值計算用戶i獲得分配后的帶寬需求 λi= λi－wi，j。

步驟7 拓?fù)涓隆?/p>

①將j色從與頂點i以j色邊相連的頂點的關(guān)聯(lián)頻譜列表中刪除，并刪除圖G中這些頂點的j色邊，即刪除此次分配出的頻譜并且更新干擾情況。

②更新此用戶i的等待時間為

③刪除λi≤0的頂點，即刪除帶寬需求得到滿足的用戶。

④其余頂點的等待時間遞增1

步驟8 判斷是否需要進行節(jié)點更新。若需要，轉(zhuǎn)步驟1，否則，判斷圖G是否為空。若為空，轉(zhuǎn)步驟 1;否則，轉(zhuǎn)步驟3。算法流程圖如圖1。

圖1 基于用戶等待時間和帶寬需求的改進CSGC算法Fig.1 Improved CSGC algorithm based on waiting time and bandwidth requirement

2 算法仿真分析

下面通過本文算法、CSGC算法以及2種改進CSGC算法，分別對頻譜資源充足和匱乏進行仿真。參考IEEE 802.22的認(rèn)知無線電區(qū)域網(wǎng)提案，用帶寬速率表示效益和需求。仿真參數(shù)如表1所示。

表1 仿真參數(shù)設(shè)置Tab.1 Simulation parameters

用戶的個數(shù)可以代表頻譜資源的緊張程度。10個用戶意味著頻譜資源空閑，40個用戶則反之。

為了方便比較，本文算法只設(shè)置了一個周期內(nèi)的仿真。通過反復(fù)實驗，得到用戶等待時間(首次獲得分配的等待時間和總等待時間)，系統(tǒng)總帶寬以及未滿足需求總量的累積分布函數(shù)。下面是在協(xié)作模式下，根據(jù)頻譜資源的充分與否，對結(jié)果的分析。

2.1 弱勢用戶獲得首次分配的等待次數(shù)

當(dāng)系統(tǒng)中存在效益很小的認(rèn)知用戶，如果采用系統(tǒng)效益最大化準(zhǔn)則，可能造成此用戶始終不能獲得分配。實際上，系統(tǒng)的用戶是不斷更新變化的，如果不能盡快對弱勢用戶進行分配，一旦用戶信息更新，弱勢用戶可能仍然處在分配的弱勢地位，那么在下個分配周期中他可能仍然不能獲得分配機會。因此，文獻［14］提出，弱勢用戶獲得首次分配機會而付出的等待時間(waiting times for the first assignment，WFA)是衡量分配效果的重要指標(biāo)。通過以下的仿真分析可知，如果采用CSGC算法，或者2種改進算法，均有較大可能出現(xiàn)弱勢用戶不能獲得分配的情況，但是本文算法基本可以避免此類情形的發(fā)生。仿真時，設(shè)置10個用戶，其中一個弱勢用戶，20個頻帶，每個頻帶對弱勢用戶的效益都是最低效益3 025 bit/period。

如圖2所示，在資源充足時，將系統(tǒng)分配次數(shù)限制在20次以內(nèi)，則本文算法在此時間段內(nèi)將頻譜分配給弱勢用戶使用概率是75%，退出改進算法的概率是35%，基于用戶等待時間的改進CSGC算法(時間改進算法)的概率是30%，而CSGC算法則不到10%。如果將系統(tǒng)分配次數(shù)限制在25次以內(nèi)，CSGC算法的概率增加到10%以上，時間改進算法接近50%，退出改進算法增加到70%，而本文算法則增加到95%，基本能保證弱勢用戶獲得分配。同時發(fā)現(xiàn)，即使資源充足，時間改進算法和CSGC算法也不能保證弱勢用戶的分配權(quán)。

圖2 頻譜資源充足時4種算法關(guān)于弱勢用戶獲得首次分配的等待次數(shù)的累積分布Fig.2 Cumulative distribution ofweak user's WFA with adequate bands

如圖3所示，在資源緊張時，時間改進算法只有不到30%的概率可以保證弱勢用戶的分配權(quán)，CSGC算法為60%，退出改進算法為75%，但是本文算法則有95%以上的幾率保證對弱勢用戶進行分配，而且只需要用較短時間就可以辦到。如果將系統(tǒng)分配次數(shù)限制在100次以內(nèi)，另外3種算法在此時間段內(nèi)將頻譜分配給弱勢用戶使用概率都不超過20%，但是本文算法則接近60%，如果將次數(shù)提高到110次，則其余算法的分配效果略有提高，不超過50%，但是本文算法達到95%。

圖3 頻譜資源不足時4種算法關(guān)于弱勢用戶獲得首次分配的等待次數(shù)的累積分布Fig.3 Cumulative distribution of weak user's WFA with inadequate bands

2.2 未滿足需求總量的累積分布比較

圖4表示了未滿足需求總量(total dnsatisfied demand，TU)的分布概率。具體地說，CSGC算法使未滿足需求總量，即TU小于10 kbit/period的可能性約為20%，小于30 kbit/period的可能性約為60%，而本文算法使TU小于10 kbit/period的可能性約為45%，小于30 kbit/period的可能性約為80%，以此類推。以縱軸為目標(biāo)，在等概率的條件下，本文算法在滿足用戶需求的性能方面與CSGC算法相比有顯著的提高，而基于用戶等待時間的改進算法但是和2種改進算法相比，在未滿足需求總量小于10 kbit/period時分配效果較差，高于20 kbit/period后差距不大。

圖4 頻譜資源充足時未滿足需求總量的累積分布Fig.4 Cumulative distribution of TU with adequate bands

從圖5可以發(fā)現(xiàn)，在頻譜資源不足時，關(guān)于未滿足需求總量，相比退出改進算法和CSGC算法，本文算法的效果有所下降，但比時間改進算法有顯著提高。這是因為本文算法從公平性的角度考慮，犧牲了部分用戶的需求用于滿足弱勢用戶。雖然系統(tǒng)的未滿足需求的總量有所增加，但是綜合2.1節(jié)的分析(弱勢用戶獲得分配的機會很大，意味著其他認(rèn)知用戶也有很大可能獲得分配的機會)可知，通過降低通信質(zhì)量的方法，本文算法可使更多用戶可以使用頻譜資源。

圖5 頻譜資源不足時未滿足需求總量的累積分布Fig.5 Cumulative distribution of TU with inadequate bands

2.3 系統(tǒng)總帶寬的累計分布比較

如圖6所示，在資源充足時，本文算法分配出的系統(tǒng)總帶寬(total bandwith，TB)顯著小于GSGC算法，和退出改進算法比較接近，相比時間改進算法較小，但這并不意味著分配的效果降低。實際上，根據(jù)2.2節(jié)中對資源充足情形的仿真可知，時間改進算法會造成大量用戶不能獲得足夠帶寬，而本文算法則不存在此問題，通過合理選擇頻譜資源對認(rèn)知用戶進行分配，使用戶的需求得到滿足。

圖6 頻譜資源充足時4種算法關(guān)于系統(tǒng)總帶寬的累積分布Fig.6 Cumulative distribution of TB with adequate bands

如圖7所示，與資源充足時的總帶寬情況相比，退出改進算法的分配效率相對其余3種算法下降，本文算法則相對提高，時間改進算法和CSGC算法基本不變。

圖7 頻譜資源不足時4種算法關(guān)于系統(tǒng)總帶寬的累積分布Fig.7 Cumulative distribution of TB with inadequate bands

2.4 用戶等待次數(shù)總和

如圖8所示，在資源充足時，對于所有用戶總的等待次數(shù)(total waiting times，TW)，CSGC 算法較差，因為此算法會將頻譜分配給帶寬需求已經(jīng)滿足的認(rèn)知用戶，退出改進算法和時間改進算法的區(qū)別不大，但相比本文算法效果較好。其原因在于:退出算法以滿足多數(shù)用戶的需求為目的，但是在2.1節(jié)的仿真分析中我們知道，此算法可能導(dǎo)致弱勢用戶不能獲得分配機會，可以理解為通過犧牲少量弱勢用戶加速分配;而時間改進算法由于產(chǎn)生總帶寬較少，而且大多數(shù)用戶需求沒有獲得滿足，同樣可以認(rèn)為犧牲較大效益換取分配進程的加快。

圖8 頻譜資源充足時用戶等待次數(shù)總和的累積分布Fig.8 Cumulative distribution of TW with adequate bands

通過以上的分析，在頻譜資源不足時，本文算法犧牲了部分效益，但在控制用戶等待時間方面，本文算法有顯著提高。如圖9所示，本文算法將用戶等待次數(shù)限制在2 200以內(nèi)的概率達到90%以上，而2種改進算法在相同的限制下只能到達60%左右，CSGC算法更是不足10%。由此得出，系統(tǒng)資源不足時，本文算法可以在相對少的時間內(nèi)完成頻譜分配。

圖9 頻譜資源不足時用戶等待次數(shù)總和的累積分布Fig.9 Cumulative distribution of TW with inadequate bands

對于頻譜資源充足的情況，本文算法在犧牲極小部分用戶總帶寬需求的情況下，高效分配系統(tǒng)資源，更快捷地把信道更為合理的分配給用戶，并且保證等待時間較長的用戶的分配優(yōu)先權(quán)，避免出現(xiàn)弱勢用戶。而對于頻譜資源不足的情況，本文算法犧牲部分系統(tǒng)總效益和用戶帶寬總需求，在相對少的時間內(nèi)將頻譜分配給更多的用戶使用，同時弱勢用戶在付出比較少的等待時間后可以獲得部分頻譜使用權(quán)，有效提高頻譜分配的公平性。

3 結(jié)論

認(rèn)知無線電為解決頻譜資源二次利用問題提供了一個可行的方案。頻譜分配過程中，在主用戶利益不受損害的情況下，盡可能多地考慮次用戶的實際利益。本文中我們第一次兼顧用戶等待時間和實際帶寬需求，在算法設(shè)計過程中，以用戶的等待時間和用戶獲得分配的情況為參考，通過對用戶等待等級賦權(quán)的方式保證等待時間長的用戶的優(yōu)先權(quán)，保證了弱勢用戶的分配權(quán);另外，以用戶的實際需求為參考，通過積累和退出的機制保證頻譜分配的高效性，即利用相對少的總帶寬滿足相對的多的用戶需求，節(jié)約頻譜資源。最后通過仿真分析，結(jié)果表明:本文算法保證了弱勢用戶的分配權(quán)，有效地滿足了用戶的需求，提升了系統(tǒng)的公平性，提高了頻譜利用率。

［1］Federal Communications Commission.Spectrum Policy Task Force［EB/OL］.(2002－12－03)［2009－01－15］.http://www.fcc.gov/sptf/files/SEWGFinaleport_1.pdf.

［2］MITOLA J.Cognitive radio for flexible mobilemultimedia Communications［EB/OL］.(1999－11－15)［2008－12－11］.http://ieeexplore. ieee. org/stamp/stamp. jsp?tp =＆arnumber=819467＆tag=1.

［3］NEEL J，REED J，GLLESR.Convergence of cognitive radio networks［C］//Proceedings of IEEE Wireless Communications and Networking Conference，2004.［s.l.］:IEEE Press，2004，4:2250－2255.

［4］STAPLE G，WERBACH K.The end of spectrum scarcity［J］.IEEE Spectrum，2004，41(3):48－52.

［5］HAYKIN S.Cognitive radio:brain－empowered wireless communications［J］.IEEE Journal on Selected Areas in Communications，2005，23(2):201－220.

［6］CABRICD，MISHRA S，BRODERSEN R.Implementation issues in spectrum sensing for cognitive radios［C］//Proceeding of the 38th Asilomar Conference Record on Singnals，Systems and Computers，Berkeley:［s.n.］，2004:772－776.

［7］KRISHNAMURTHY S，THOPPIAN M，VENKATESAN S，et al.Control channel based MAC－Layer configuration，routing and situation awareness for cognitive radio networks［C］//IEEE Military Communications Conference，2005，Dallas:［s.n.］，2005:455－460.

［8］IAN A，AKYILDIZ F，LEEW.Survey on spectrum management in cognitive radio networks［J］.Cognitive radio Communications and Networks，2008，46(4):40－57.

［9］ZHENG H，PENG C.Collaboration and fairness in opportunistic access［C］//Proceeding of the 40th Annual IEEE International Conference on Communications(ICC)，Seoul:［s.n.］，2005:3131－3138.

［10］繆殿飛，鄭寶玉.協(xié)作頻譜感知在認(rèn)知網(wǎng)絡(luò)中的應(yīng)用［J］.重慶郵電大學(xué)學(xué)報:自然科學(xué)版，2008，20(6):663－666.

MIAO Dian－fei，ZHENG Bao－yu.Cooperative spectrum sensing in cognitive radio network［J］. Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2008，20(6):663－666.

［11］WANGW，LIU X.List－Coloring based channelallocation for open－spectrum wireless networks［C］//The 62nd IEEE vehicular technology conference(VTC).2005，Dallas:［s.n.］，2005:690－694.

［12］PENG C，ZHENG H，ZHAO B.Utilization and fairness inpectrum assignment for opportunistic spectrum access［J］.ACM mobile networks and applications(MONET)，2006，11(4):554－576.

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

LIAO Chu－lin.Research of spectrum allocation in cognitive radio network［D］.Chengdu:University of Electronic Science and Technology of China，2007:58－76.

［14］柳平，張敏.基于用戶等待時間的頻譜分配改進算法［J］. 廣東通信技術(shù)，2009，11(6):17－20.

LIU Pin，ZHANG Min.Research of spectrum allocation based on user waiting time in cognitive radio network［J］.Guangdong Communication Technology，2009，11(6):17－20.

［15］莫文承.認(rèn)知無線電頻譜分配算法研究［D］.西安:西安電子科技大學(xué)，2008:40－62.

MO Wen－cheng.Research of spectrum allocation algorithm in cognitive radio［D］.Xi'an:Xidian university，2008:40－62.

［16］CHEN X，BIE Z，WUW.Detection efficiency of cooperative spectrum sensing in cognitive radio network［J］.Journal of China Universities of Posts and Telecommunications，2008，15(3):1－7.

(編輯:田海江)