杜文峰，劉亞濤，明仲，隋銀雪

（深圳大學(xué) 計(jì)算機(jī)與軟件學(xué)院，廣東 深圳 518060）

1 引言

隨著無線通信技術(shù)的快速發(fā)展，無線頻譜資源變得十分稀缺，已經(jīng)無法滿足日益增長的無線通信技術(shù)需求。然而，根據(jù)美國FCC于2003年對無線頻譜使用情況的調(diào)查報(bào)告[1]，可以發(fā)現(xiàn)已分配的授權(quán)頻譜的資源利用率普遍在 15%～85%范圍內(nèi)波動(dòng)。2009年，中國移動(dòng)研究院無線技術(shù)研究所對授權(quán)頻譜的利用情況進(jìn)行了實(shí)測，結(jié)果表明已分配的授權(quán)頻譜資源的利用率很低，多半頻段的利用率不足5%，甚至出現(xiàn)空白頻段[2]。因此，如何提高授權(quán)頻段的重復(fù)利用率，緩解當(dāng)前無線網(wǎng)絡(luò)帶寬資源緊缺的現(xiàn)狀，成為當(dāng)前無線通信領(lǐng)域亟待解決的問題。認(rèn)知無線電 (CR, cognitive radio)正是在這樣的環(huán)境下提出的一種頻譜資源共享技術(shù)[3]。

認(rèn)知無線電通過實(shí)時(shí)感知外部頻譜的使用情況，發(fā)現(xiàn)并利用閑置的授權(quán)頻段（稱為“頻譜空穴”）進(jìn)行數(shù)據(jù)傳輸，實(shí)現(xiàn)頻譜資源的動(dòng)態(tài)共享。在認(rèn)知無線電網(wǎng)絡(luò)中存在著2類用戶：主用戶(PU, primary user)和認(rèn)知用戶(CU, cognitive user)。主用戶是在指定頻段上的法定授權(quán)用戶；認(rèn)知用戶沒有任何頻譜使用授權(quán)，只是伺機(jī)占用主用戶未使用的授權(quán)頻段進(jìn)行通信。

目前，已有部分研究針對認(rèn)知無線電的頻譜分配過程展開了討論，通過分析多個(gè)相互競爭的認(rèn)知用戶之間的關(guān)系，將授權(quán)頻譜分配給滿足一定條件的認(rèn)知用戶使用?？梢园l(fā)現(xiàn)，現(xiàn)有的頻譜分配算法在分配過程中主要以特定的目標(biāo)函數(shù)為指導(dǎo)，并未考慮到頻譜分配過程的公平性。此類算法在分配過程中以最大化目標(biāo)性能為主導(dǎo)，可能將頻譜資源優(yōu)先分配給部分競爭力較強(qiáng)的認(rèn)知用戶，導(dǎo)致其他競爭力較弱的認(rèn)知用戶由于可用頻譜被占用而無法接入。而此時(shí)，另外一些授權(quán)頻譜資源由于沒有認(rèn)知用戶接入而繼續(xù)空置，產(chǎn)生“餓死”現(xiàn)象。

然而，在認(rèn)知無線電網(wǎng)絡(luò)環(huán)境中，由于不同認(rèn)知用戶的接入方式或發(fā)射功率不一定相同，處于同一授權(quán)頻譜覆蓋范圍內(nèi)的多個(gè)認(rèn)知用戶在接入和使用頻譜的過程中可能出現(xiàn)干擾或者能夠共享使用。同時(shí)，授權(quán)頻譜分配的先后次序也將影響頻譜分配的最終結(jié)果。本文正是在此基礎(chǔ)上，針對認(rèn)知用戶在接入授權(quán)頻譜的競爭過程中所產(chǎn)生的沖突進(jìn)行分析，提出了一種基于干擾消減的頻譜分配算法(IESA, interference elimination based spectrum allocation algorithm)。該算法通過消減認(rèn)知用戶在接入頻譜過程中存在的干擾，增加能夠同時(shí)接入授權(quán)頻譜的認(rèn)知用戶數(shù)量。同時(shí)，本算法將各個(gè)認(rèn)知用戶的可用頻譜信息結(jié)合到頻譜分配過程中，對分配過程的公平性進(jìn)行了優(yōu)化。

本文的后續(xù)內(nèi)容組織如下：第2節(jié)介紹了當(dāng)前認(rèn)知無線電頻譜分配問題的研究現(xiàn)狀；第3節(jié)使用圖論方式對頻譜分配過程進(jìn)行建模；本文提出的頻譜分配算法將在第4節(jié)給出；第5節(jié)對比了本算法與顏色敏感圖著色算法的運(yùn)行性能，并給出了模擬仿真結(jié)果；第6節(jié)是結(jié)束語。

2 相關(guān)研究

在認(rèn)知無線電網(wǎng)絡(luò)中，認(rèn)知用戶由于所處位置不同，可能被多個(gè)授權(quán)頻譜所覆蓋，能夠感知和接入多個(gè)授權(quán)頻譜。

目前，針對認(rèn)知無線電頻譜分配方面的文章主要以圖著色理論模型為基礎(chǔ)。文獻(xiàn)[4]提出了基于列表著色的分布式貪婪算法，以最大頻譜分配數(shù)量為目標(biāo)，將認(rèn)知用戶同其他認(rèn)知用戶所產(chǎn)生干擾的數(shù)量定義為該認(rèn)知用戶的度，并優(yōu)先對度較小的認(rèn)知用戶進(jìn)行頻譜分配。以認(rèn)知用戶之間的干擾度來進(jìn)行頻譜分配能夠優(yōu)化認(rèn)知用戶占用頻譜的數(shù)量，但分配結(jié)果中有可能出現(xiàn)一個(gè)用戶占用多個(gè)頻譜的情況，導(dǎo)致其他多個(gè)認(rèn)知用戶無法接入。同時(shí)，該算法缺乏對干擾和頻譜效益的差異性討論；Haitao Zheng等在文獻(xiàn)[5]中利用不同認(rèn)知用戶在使用頻譜資源時(shí)所產(chǎn)生的效益和干擾差異性，提出了一種以最大效益為目標(biāo)的顏色敏感圖著色算法(CSGC,color sensitive graph coloring algorithm)。該算法將頻譜效益與用戶干擾度的比值定義為標(biāo)號，并優(yōu)先對標(biāo)號最大的節(jié)點(diǎn)進(jìn)行分配，提高系統(tǒng)的頻譜效益。然而，在該算法中產(chǎn)生頻譜效益較大的認(rèn)知用戶往往由于競爭優(yōu)勢搶占產(chǎn)生頻譜效益較小的認(rèn)知用戶所能夠使用的頻譜資源，無法保證認(rèn)知用戶的最大頻譜接入數(shù)量；文獻(xiàn)[6]中設(shè)計(jì)了一種啟發(fā)式規(guī)則來進(jìn)行頻譜分配和頻譜資源調(diào)度，實(shí)現(xiàn)了以網(wǎng)絡(luò)公平性為目標(biāo)的頻譜共享。Anh Tuan Hoang等在文獻(xiàn)[7]中采用功率控制方法來計(jì)算不同認(rèn)知用戶的信噪比，通過降低認(rèn)知用戶對授權(quán)用戶的干擾，對頻譜使用過程進(jìn)行優(yōu)化。然而，該算法主要針對認(rèn)知用戶接入授權(quán)頻譜的干擾問題進(jìn)行討論，沒有對多個(gè)認(rèn)知用戶同時(shí)接入相同授權(quán)頻譜時(shí)所存在的同頻干擾問題進(jìn)行分析；文獻(xiàn)[8]以認(rèn)知用戶的接入公平性為參考，提出了一種基于流量感知的認(rèn)知無線電網(wǎng)絡(luò)動(dòng)態(tài)頻譜分配算法。該算法通過感知不同節(jié)點(diǎn)的網(wǎng)絡(luò)流量，有選擇地為認(rèn)知用戶進(jìn)行頻譜分配，在一定程度上提高了認(rèn)知用戶使用頻譜資源的公平性；文獻(xiàn)[9]通過建模認(rèn)知用戶和主用戶的行為模式，對認(rèn)知用戶阻塞主用戶，以及同主用戶產(chǎn)生接入沖突的概率進(jìn)行預(yù)測。通過將不同認(rèn)知用戶分配到不同的授權(quán)頻段，能夠在一定程度上提高網(wǎng)絡(luò)的吞吐量，同時(shí)保證頻譜分配的公平性。

可以發(fā)現(xiàn)，目前已有的頻譜分配算法主要以系統(tǒng)最大頻譜效益為目標(biāo)，優(yōu)先將可用頻譜分配給產(chǎn)生較大頻譜效益的認(rèn)知用戶。盡管該類算法能夠有效地解決接入沖突問題，但仍缺少對多個(gè)認(rèn)知用戶共享同一頻譜問題的討論。同時(shí)，現(xiàn)有部分頻譜分配算法優(yōu)先對滿足一定目標(biāo)的認(rèn)知用戶進(jìn)行頻譜分配，可能導(dǎo)致其他認(rèn)知用戶由于可用頻譜被占用，而另外一些可用授權(quán)頻譜資源由于沒有被接入而繼續(xù)空置的情況，限制了接入到可用授權(quán)頻譜中的認(rèn)知用戶數(shù)量。

另外，已有的頻譜分配算法主要強(qiáng)調(diào)認(rèn)知用戶之間的同頻干擾，不允許多個(gè)認(rèn)知用戶共享接入同一個(gè)授權(quán)頻譜。然而，由于認(rèn)知用戶的接入方式或發(fā)射功率不一定相同，處于同一授權(quán)頻譜覆蓋范圍內(nèi)的多個(gè)認(rèn)知用戶在接入和使用頻譜的過程中由于互不干擾，可能共享使用該頻譜。本文以認(rèn)知節(jié)點(diǎn)的發(fā)射功率，即信號傳輸距離為例來定義不同認(rèn)知用戶之間的同頻干擾。當(dāng)認(rèn)知用戶之間的距離低于一定閾值時(shí)，同一頻譜覆蓋范圍內(nèi)的認(rèn)知用戶將由于接入干擾而不能共享該頻譜資源；反之，當(dāng)認(rèn)知用戶之間的距離超過某一閾值時(shí)，認(rèn)知用戶的頻譜接入過程將不存在干擾，可以共享該授權(quán)頻譜進(jìn)行通信，如圖1所示。認(rèn)知節(jié)點(diǎn)1和認(rèn)知節(jié)點(diǎn)2可以同時(shí)接入授權(quán)頻段A，而認(rèn)知節(jié)點(diǎn)3與認(rèn)知節(jié)點(diǎn)1和認(rèn)知節(jié)點(diǎn)2在接入頻譜過程中將產(chǎn)生同頻干擾。

圖1 認(rèn)知無線電網(wǎng)絡(luò)頻譜覆蓋及接入

為了進(jìn)一步優(yōu)化認(rèn)知無線電網(wǎng)絡(luò)的頻譜分配過程，使得多個(gè)互不干擾的認(rèn)知用戶能夠共享同一授權(quán)頻段，并且保證頻譜分配過程中的公平性，本文在已有認(rèn)知無線電干擾消除問題分析的基礎(chǔ)上，進(jìn)一步針對同頻干擾消除問題進(jìn)行優(yōu)化，通過對能夠共享同一授權(quán)頻譜的多個(gè)認(rèn)知用戶情況進(jìn)行分析，結(jié)合頻譜干擾和頻譜效益的差異性，在增加認(rèn)知用戶接入數(shù)量的同時(shí)提高系統(tǒng)的頻譜利用率。

3 系統(tǒng)模型與假設(shè)

假設(shè)認(rèn)知無線電網(wǎng)絡(luò)中的授權(quán)頻譜可以劃分為M個(gè)互不干擾的正交頻段，即信道，且每個(gè)信道的傳輸頻率和覆蓋范圍各不相同。其中，信道j用SRj表示，1≤j≤M。認(rèn)知無線電網(wǎng)絡(luò)中存在著N個(gè)認(rèn)知節(jié)點(diǎn)，每個(gè)認(rèn)知節(jié)點(diǎn)代表一個(gè)認(rèn)知用戶。其中，第i個(gè)認(rèn)知節(jié)點(diǎn)用CRi表示，1≤i≤N；認(rèn)知用戶由于所處位置不同，則可能處于多個(gè)授權(quán)頻譜的覆蓋范圍內(nèi)。認(rèn)知用戶可以接入到其可感知的任何一個(gè)可用授權(quán)頻譜進(jìn)行通信。認(rèn)知用戶之間由于接入技術(shù)或傳輸距離等原因，在接入同一信道時(shí)可能會(huì)產(chǎn)生頻譜干擾。

同時(shí)，本文假設(shè)在頻譜分配過程中，認(rèn)知無線電網(wǎng)絡(luò)環(huán)境不發(fā)生改變，即認(rèn)知用戶的位置、可用授權(quán)頻段不發(fā)生變化。

為了描述認(rèn)知無線電網(wǎng)絡(luò)的頻譜分配過程，本文同樣利用圖著色理論來描述整個(gè)認(rèn)知無線電網(wǎng)絡(luò)場景。類似文獻(xiàn)[5]，本文引入了可用矩陣、效益矩陣、干擾矩陣和分配矩陣。同時(shí)，本文對干擾矩陣進(jìn)行了擴(kuò)展，使其能夠更好地描述現(xiàn)實(shí)環(huán)境。

1) 可用矩陣L={li,j|li,j∈{0, 1}}N×M, 1≤i≤N,1≤j≤M，是關(guān)于認(rèn)知用戶和授權(quán)頻譜資源可用關(guān)系的二維矩陣。其中，行標(biāo)i表示認(rèn)知用戶 CRi，列標(biāo)j表示授權(quán)頻段SRj。如果認(rèn)知用戶CRi可以接入授權(quán)頻譜SRj，則記li,j=1；否則，記li,j= 0。

2) 效益矩陣B與可用矩陣L對應(yīng)，以bi,j表示認(rèn)知用戶CRi接入頻譜資源SRj時(shí)所產(chǎn)生的頻譜效益。若CRi無法接入頻譜SRj，即當(dāng)li,j= 0時(shí)，記bi,j= 0。

3)干擾距離矩陣θ={θi}, 1≤i≤M，用實(shí)數(shù)表示不同授權(quán)頻段的干擾閾值大小，是關(guān)于授權(quán)頻譜干擾閾值的一維向量。其中，θi表示授權(quán)頻段 SRi所能忍受的干擾閾值。

4) 干擾矩陣C用三維矩陣C={ci,j,k}M×N×N表示任何2個(gè)認(rèn)知用戶在共享某一授權(quán)頻譜資源時(shí)的干擾度。其中，行標(biāo)i代表授權(quán)頻段SRi，j，k分別代表認(rèn)知用戶CRj和認(rèn)知用戶CRk。

同時(shí)，與CSGC算法只是簡單地用0,1表示干擾矩陣元素值的方法不同，本文用區(qū)間[0,1]內(nèi)的實(shí)數(shù)值代替干擾矩陣的元素值。若認(rèn)知用戶無法同時(shí)接入某一授權(quán)頻譜，則認(rèn)為這些認(rèn)知用戶在該頻譜上的干擾度為 1；如果認(rèn)知用戶可以共享某一授權(quán)頻譜，且認(rèn)知用戶之間的距離小于對應(yīng)授權(quán)頻譜的干擾距離，則令認(rèn)知用戶在該頻譜上的干擾度為干擾距離與實(shí)際距離的比值；相反，如果認(rèn)知用戶之間的距離大于該授權(quán)頻譜的干擾距離，則令認(rèn)知用戶在該頻譜上的干擾度值為0。

5) 分配矩陣A記錄了頻譜分配算法的運(yùn)行結(jié)果，用矩陣A={ai,j|ai,j∈{0, 1}}N×M表示，1≤i≤N,1≤j≤M。如果認(rèn)知用戶CRi分配到頻譜資源SRj，則記ai,j=1；否則，ai,j= 0。

根據(jù)上述數(shù)學(xué)描述，可以把認(rèn)知無線電網(wǎng)絡(luò)抽象成圖論模型G=(V,E,B)。頂點(diǎn)V代表認(rèn)知用戶集合；邊的集合E記錄能夠同時(shí)接入某一授權(quán)信道時(shí)發(fā)生干擾的2個(gè)認(rèn)知用戶之間的關(guān)系；集合B表示各個(gè)頂點(diǎn)可選的顏色集合(即可用頻譜資源列表)和各個(gè)顏色所對應(yīng)的權(quán)重(即頻譜效益)。

4 基于干擾消減的頻譜分配算法

為了充分利用可用頻譜資源，保證能夠共享同一頻譜資源的認(rèn)知用戶數(shù)量最大化，本算法首先對可共享同一頻譜資源的認(rèn)知用戶進(jìn)行頻譜分配，然后再將剩余的可用頻譜資源分配給尚未獲得頻譜資源的認(rèn)知用戶。

根據(jù)可用矩陣L和干擾矩陣C的定義，可以得到以下結(jié)論。

定理1 當(dāng)li,m+lj,m≤1時(shí)，必定滿足cm,i,j=0。

定理2 當(dāng)cm,i,j=1時(shí)，認(rèn)知用戶CRi和認(rèn)知用戶CRj在共同使用授權(quán)頻譜SRm時(shí)產(chǎn)生干擾，且必定存在li,m=lj,m=1。

定義能夠接入同一授權(quán)頻段而不發(fā)生干擾的 2個(gè)認(rèn)知用戶為共享用戶對?？梢园l(fā)現(xiàn)，當(dāng)且僅當(dāng)li,m+lj,m＞1，且cm,i,j=0時(shí)，認(rèn)知用戶CRi和認(rèn)知用戶CRj可以共享授權(quán)頻譜SRm，構(gòu)成一個(gè)共享用戶對，記為＜CRi, CRj＞。

由于認(rèn)知用戶在指定頻段下的干擾關(guān)系是對稱的，將干擾矩陣C指定頻譜下三角部分值為0的元素置為1，將值為1的元素置為0，除去對角線上的元素后，可以得到所有值為1的元素所對應(yīng)的行標(biāo)和列標(biāo)構(gòu)成了該頻譜下的所有共享用戶對。

然而，由于認(rèn)知用戶可能處于多個(gè)授權(quán)頻譜的覆蓋范圍之內(nèi)，多個(gè)共享用戶對在接入同一授權(quán)信道時(shí)可能存在相互干擾，以及不同共享用戶對中出現(xiàn)認(rèn)知用戶重疊。為了充分利用頻譜資源，必須對共享用戶對進(jìn)行再次優(yōu)化，得到能夠共享某一授權(quán)頻譜資源的最多認(rèn)知用戶集合。因此，本文進(jìn)一步將能夠同時(shí)共享同一頻譜的所有認(rèn)知用戶所組成的集合定義為在該頻譜下的最大共享獨(dú)立集；記授權(quán)頻譜SRm的最大共享獨(dú)立集用Gm表示。

為了最大化地利用授權(quán)頻譜資源，必須找出每個(gè)頻段中互不產(chǎn)生干擾的所有認(rèn)知用戶，并獲取各個(gè)授權(quán)頻譜對應(yīng)的最大共享獨(dú)立集。因此，本算法首先對各個(gè)頻譜下的所有共享用戶對進(jìn)行遍歷。

假設(shè)＜CRi, CRj＞為頻譜SRm下的共享用戶對。在遍歷過程開始時(shí)，可以認(rèn)為授權(quán)頻段SRm的最大共享獨(dú)立集的初始值Gm={CRi, CRj}。

假設(shè)授權(quán)頻段SRm的所有共享用戶對中存在認(rèn)知用戶 CRk，1≤k≤N,k≠i,k≠j，且定義認(rèn)知用戶CRk的沖突度為該節(jié)點(diǎn)與頻譜SRm的當(dāng)前最大共享獨(dú)立集Gm中元素發(fā)生干擾的數(shù)量。

可以發(fā)現(xiàn)，認(rèn)知用戶CRk與當(dāng)前最大共享獨(dú)立集Gm可能存在以下3種場景，如圖2所示。圖中，圓圈中的字母i，j，k分別表示認(rèn)知用戶CRi，CRj和CRk，字母m表示頻譜資源SRm；實(shí)線表示其兩端的認(rèn)知用戶在使用頻譜資源時(shí)存在干擾，而虛線表示其兩端的認(rèn)知用戶可以同時(shí)共享該頻譜資源。

圖2 授權(quán)頻譜SRm下的認(rèn)知用戶共享沖突

為了構(gòu)建最大共享獨(dú)立集，本算法針對以上 3種情況進(jìn)行了區(qū)分處理。

1) ?CRi∈Gm，CRj∈Gm，i≠j，且?cm,i,k=1，cm,j,k=1

認(rèn)知用戶CRk與共享獨(dú)立集Gm中的2個(gè)認(rèn)知用戶CRi、CRj均存在沖突，如圖2(a)所示。CRk與集合Gm的沖突度為2，集合Gm內(nèi)的元素保持不變。

2) ?CRi∈Gm，i≠j，且?CRj∈Gm，滿足cm,i,k=0，cm,j,k=1

認(rèn)知用戶CRk只與獨(dú)立集Gm中的一個(gè)認(rèn)知用戶存在沖突，即CRk與集合Gm的沖突度為1，如圖2(b)所示。此時(shí)，本算法將比較認(rèn)知用戶 CRj和認(rèn)知用戶 CRk在頻譜 SRm下產(chǎn)生的頻譜效益。若bj,m＞bk,m，則集合Gm保持不變；否則，以認(rèn)知用戶CRk替換認(rèn)知用戶 CRj，Gm=Gm－{CRj}+{CRk}。

3) ? CRi∈Gm，滿足cm,i,k=0

此時(shí)，認(rèn)知用戶CRk與獨(dú)立集Gm中的所有認(rèn)知用戶均不存在沖突，即CRk與集合Gm的沖突度為 0，如圖 2(c)所示。此時(shí)，本算法將把認(rèn)知用戶CRk歸入頻譜 SRm的最大共享獨(dú)立集，即Gm=Gm+{CRk}。

以上過程不斷迭代，直至所有的共享認(rèn)知用戶遍歷結(jié)束，得到頻譜SRm的最大共享獨(dú)立集。

由于最大共享獨(dú)立集中的認(rèn)知用戶在接入同一頻譜時(shí)不存在相互干擾，為了有效利用頻譜資源，本算法優(yōu)先為含有認(rèn)知用戶數(shù)量最多的最大共享獨(dú)立集中的認(rèn)知用戶分配頻譜，即將頻譜資源同時(shí)分配給最大共享獨(dú)立集中的所有認(rèn)知用戶。

設(shè)獨(dú)立集Gmax={CRi, CRj, CRk,…}為包含最多認(rèn)知用戶的最大共享獨(dú)立集，且SRmax為該集合所對應(yīng)的頻譜資源。根據(jù)本算法的執(zhí)行原理，首先將頻譜SRm分配給獨(dú)立集Gmax中的所有認(rèn)知用戶，并在分配矩陣A中設(shè)置相應(yīng)的頻譜分配結(jié)果，即令：

同時(shí)，更新集合Gmax中所有認(rèn)知用戶在可用矩陣L中的頻譜可用性，將可用矩陣L中的對應(yīng)行元素置為0。即

?CRi∈Gmax, ?m, 1≤m≤M,m≠max，則令li,m=0

為共享獨(dú)立集Gmax中的認(rèn)知用戶分配完頻譜資源后，本算法將繼續(xù)查找頻譜 SRmax下與集合Gmax中認(rèn)知用戶產(chǎn)生沖突的所有認(rèn)知用戶，并更新其在頻譜SRmax下的可用狀態(tài)。即

本文對溫州南站中央空調(diào)主機(jī)進(jìn)行智能節(jié)電系統(tǒng)改造，使用環(huán)境溫度保持與原來進(jìn)行節(jié)能改造前完全一致的情況下，改造后可以獲得收益：

對于?n, 1≤n≤N, 且 CRi∈Gmax，若?cmax,i,n= 1,則令ln,max= 0。

然而，由于認(rèn)知用戶可能被多個(gè)授權(quán)頻譜所覆蓋，同一個(gè)認(rèn)知用戶可能出現(xiàn)在不同授權(quán)頻譜的最大共享獨(dú)立集中。因此，本算法進(jìn)一步對頻譜分配過程進(jìn)行優(yōu)化，將已分配到頻譜資源的認(rèn)知用戶從其他授權(quán)頻譜的最大獨(dú)立共享集中刪除。即

對于?m，1≤m≤M，m≠max，若?CRi∈Gmax，且 CRi∈Gm，則Gm=Gm－{CRi}

以上過程不斷迭代，直至將所有已分配到頻譜資源的認(rèn)知用戶從其他授權(quán)頻譜的最大共享獨(dú)立集中刪除為止。

為能夠共享頻譜的認(rèn)知用戶分配頻譜后，本算法將進(jìn)一步為未分配到頻譜資源的其他認(rèn)知用戶分配頻譜資源。令已分配到頻譜資源的認(rèn)知用戶集合為GI= {CRi, CRj, CRk, …}，且所有未分配到頻譜資源的認(rèn)知用戶集合為GII={CRx, CRy, CRz, …}。

在為集合GII內(nèi)的認(rèn)知用戶分配可用頻譜時(shí)，剩余的可用頻譜將隨著頻譜分配過程的進(jìn)行而不斷變化。為此，本文進(jìn)一步定義認(rèn)知用戶在未進(jìn)行頻譜分配時(shí)的可用頻譜為該認(rèn)知用戶的初始可用頻譜；同時(shí)，定義干擾度Dx,m為在集合GII內(nèi)的認(rèn)知用戶CRx與其他認(rèn)知用戶在頻譜SRm中產(chǎn)生的干擾量。

結(jié)合效益矩陣B和干擾矩陣C，可以得到所有未分配到頻譜資源的認(rèn)知用戶的初始可用頻譜和干擾度。即對于?m，1≤m≤M，?CRx∈GII時(shí)，可以得到以下結(jié)論。

結(jié)論1 當(dāng)bx,m=0時(shí)，頻譜SRm不是認(rèn)知用戶CRx的初始可用頻譜，且認(rèn)知用戶CRx在頻譜SRm下的干擾度為0。

令number(CRx)為認(rèn)知用戶 CRx的可用頻譜數(shù)量，結(jié)合可用矩陣L可以得到number(CRx)為

通常，可用頻譜數(shù)量較多的認(rèn)知用戶獲得頻譜的概率相對較高。為了保證更多的認(rèn)知用戶可以接入授權(quán)頻譜，本算法將從集合GII中優(yōu)先選擇可用頻譜數(shù)量最少的認(rèn)知用戶進(jìn)行分配，直到所有認(rèn)知用戶被遍歷，或者所有頻譜資源被分配為止。

令CRmin為所有未分配到頻譜資源的認(rèn)知用戶中可用頻譜數(shù)量最少的認(rèn)知用戶，且其可用頻譜數(shù)量s為

同樣，根據(jù)s值的不同，本算法將對認(rèn)知用戶CRmin進(jìn)行區(qū)分處理。

1) 若s=0，即認(rèn)知用戶CRmin無可用頻譜資源

此時(shí)，認(rèn)知用戶CRmin接入任何一個(gè)初始可用頻譜都會(huì)對其他已分配到頻譜資源的認(rèn)知用戶產(chǎn)生干擾。即對于?m, 1≤m≤M，Dmin,m≥θm。

根據(jù)Dmin,m與θm的關(guān)系，又可以分為2種情況。

a) 對于?m, 1≤m≤M,bmin,m＞0，若干擾度Dmin,m＞θm，則GII=GII－{CRmin}，本算法將不再為認(rèn)知用戶CRmin分配頻譜資源；

b) 對于?m, 1≤m≤M,bmin,m＞0，以及 CRi∈GI，若?Dmin,m=θm，cm,i,min=1，且bmin,m＞bi,m，則將頻譜資源SRm分配給認(rèn)知用戶CRmin，取消認(rèn)知用戶CRi對頻譜SRm的使用權(quán)，即置ai,m=0，amin,m=1；此時(shí)，對認(rèn)知用戶CRmin的分配結(jié)果不會(huì)對其他認(rèn)知用戶造成影響。

2) 若s=1，即僅有唯一的頻譜資源可供認(rèn)知用戶CRmin接入

本算法將把該頻譜資源分配給認(rèn)知用戶CRmin，即對于?m, 1≤m≤M, 若?lmin,m=1，令amin,m=1。

3)s＞1，即認(rèn)知用戶CRmin可以在無干擾的情況下接入多個(gè)可用授權(quán)頻譜

可用矩陣L中存在lmin,1+lmin,2+…+lmin,M＞1。此時(shí)，本算法將找到能夠使認(rèn)知用戶CRmin產(chǎn)生最大頻譜效益的頻譜SRm，并將頻譜SRm被分配給該認(rèn)知用戶。即?m, 1≤m≤M, 且lmin,m=1，使得bmin,m=max(bmin,1×lmin,1,bmin,2×lmin,2,… ,bmin,M×lmin,M)， 則 令amin,m=1。

同時(shí)，本算法將繼續(xù)更新可用矩陣L，將已分配到頻譜資源的認(rèn)知用戶所在行的元素置為0。即

另外，本算法將更新其他認(rèn)知用戶在頻譜SRm中的可用狀態(tài)，即對于?x, 1≤x≤N, 如果?CRx∈GII,且?cm,min,x= 1, 則令lx,m= 0。

最后，將已分配到頻譜資源的認(rèn)知用戶從集合GII中刪除，并將已分配到頻譜資源的認(rèn)知用戶添加到集合GI中。即

以上分配過程不斷迭代，直至集合GII為空或所有授權(quán)頻譜資源被分配完為止。

本算法的核心偽代碼如圖3所示。

當(dāng)前，可以通過集中式和分布式2種方式來實(shí)現(xiàn)上述頻譜分配過程。

1)集中式

如果認(rèn)知無線電網(wǎng)絡(luò)中存在一個(gè)中心調(diào)度節(jié)點(diǎn)負(fù)責(zé)為所有認(rèn)知用戶分配頻譜資源，則本算法的實(shí)施過程將非常直接。中心調(diào)度節(jié)點(diǎn)收集圖中所有節(jié)點(diǎn)的可用頻譜、頻譜效益、接入干擾等信息，并執(zhí)行本文所提出的頻譜分配算法，將分配結(jié)果反饋給所有認(rèn)知用戶。

圖3 算法的核心偽代碼描述

2)分布式

認(rèn)知無線電網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)將向其所有鄰居節(jié)點(diǎn)發(fā)送位置、可用頻譜、頻譜效益等信息，各節(jié)點(diǎn)分別構(gòu)建全網(wǎng)可用矩陣、效益矩陣和干擾矩陣。通過執(zhí)行本文提出的干擾消減算法，各個(gè)節(jié)點(diǎn)將各輪分配結(jié)果反饋給其鄰居，并更新分配矩陣、可用矩陣。該步驟不斷迭代，直到所有頻段資源被分配或者所有認(rèn)知用戶都得到可用頻譜為止。

5 算法性能分析及仿真實(shí)驗(yàn)

根據(jù)前文所述，CSGC算法為了確保系統(tǒng)頻譜效益，在頻譜分配過程中優(yōu)先將頻譜資源分配給標(biāo)號最大的認(rèn)知用戶，其算法復(fù)雜度為O(n2)。本文提出的IESA算法則需要首先找到能夠共享同一頻段的多個(gè)認(rèn)知用戶進(jìn)行頻譜分配，然后再對未分配到頻譜資源的認(rèn)知用戶進(jìn)行頻譜分配，算法復(fù)雜度為O(n2)。因此本算法在復(fù)雜度上相對于CSGC算法并未有實(shí)質(zhì)性的增加。

目前，對認(rèn)知無線電頻譜分配算法的性能評估主要從系統(tǒng)頻譜效益和網(wǎng)絡(luò)公平性等角度進(jìn)行。

1)系統(tǒng)頻譜效益是指所有分配到頻譜資源的認(rèn)知用戶在相應(yīng)頻段上貢獻(xiàn)的頻譜效益總和。

利用分配矩陣A與效益矩陣B，可以得到頻譜分配過程結(jié)束后所取得的系統(tǒng)頻譜效益Usum。

2) 網(wǎng)絡(luò)公平性則體現(xiàn)了將頻譜資源分配給認(rèn)知用戶的均衡程度[9]。

可以發(fā)現(xiàn)，網(wǎng)絡(luò)公平性pa可由用戶分配率表示，即所有分配到頻譜資源的認(rèn)知用戶占系統(tǒng)認(rèn)知用戶總量的比例。其計(jì)算方法如下：

為了驗(yàn)證IESA算法的運(yùn)行性能，本文分別對認(rèn)知用戶數(shù)量多于和少于授權(quán)頻譜總量的場景進(jìn)行了分析。本文采用Java語言對IESA算法與CSGC算法進(jìn)行了模擬實(shí)現(xiàn)，對2種算法的系統(tǒng)頻譜效益和網(wǎng)絡(luò)公平性等性能指標(biāo)進(jìn)行了比較。在模擬過程中，各個(gè)授權(quán)頻譜的頻譜空穴隨機(jī)生成，認(rèn)知用戶之間的干擾度由處于同一授權(quán)頻段的認(rèn)知用戶之間的距離和授權(quán)頻譜的干擾閾值決定。

圖4給出了IESA算法和CSGC算法在授權(quán)頻譜數(shù)量為 10的認(rèn)知無線電網(wǎng)絡(luò)中所對應(yīng)的用戶分配率?？梢钥闯觯?dāng)認(rèn)知用戶數(shù)量大于可用頻譜總數(shù)時(shí)，CSGC算法和IESA算法對認(rèn)知用戶的滿足程度隨著認(rèn)知用戶數(shù)量的增加而下降，但I(xiàn)ESA算法在整個(gè)模擬過程中相對CSGC算法能夠滿足更多認(rèn)知用戶的頻譜接入。當(dāng)M=10，N=35時(shí)，CSGC算法的用戶分配率僅為65%，而IESA算法能夠使85%的認(rèn)知用戶獲得頻譜資源。

圖4M為10的用戶分配率

與此同時(shí)，圖 5給出了 2種頻譜分配算法在M=10時(shí)的系統(tǒng)頻譜效益?？梢钥吹剑?種算法的系統(tǒng)頻譜效益隨著認(rèn)知用戶數(shù)量的增加而不斷遞增。當(dāng)認(rèn)知用戶數(shù)量小于20時(shí)，CSGC算法可以獲得較好的系統(tǒng)頻譜效益。然而，當(dāng)認(rèn)知用戶數(shù)量大于20時(shí)，IESA算法的系統(tǒng)頻譜效益相對較優(yōu)?？梢缘玫剑?dāng)認(rèn)知用戶數(shù)量多于可用授權(quán)頻譜總數(shù)時(shí)，IESA算法可以在獲得較好認(rèn)知用戶接入數(shù)量的同時(shí)，取得較優(yōu)的系統(tǒng)頻譜效益。

圖5M為10的系統(tǒng)頻譜效益

當(dāng)授權(quán)頻譜數(shù)量增加到50，且認(rèn)知用戶的數(shù)量從10增加到50時(shí)，實(shí)驗(yàn)得到2種算法對用戶的分配率均為 100%。因此，當(dāng)認(rèn)知用戶數(shù)量小于系統(tǒng)的可用頻譜總數(shù)時(shí)，IESA算法相對CSGC算法在認(rèn)知用戶接入數(shù)量方面并沒有表現(xiàn)出一定的優(yōu)勢。

圖6給出了2種頻譜分配算法在授權(quán)頻譜總數(shù)大于認(rèn)知用戶數(shù)量時(shí)所取得的系統(tǒng)頻譜效益。當(dāng)授權(quán)頻譜總數(shù)為 50時(shí)，隨著認(rèn)知用戶數(shù)量的不斷增加，CSGC算法所獲得的系統(tǒng)頻譜效益一直呈上升趨勢，且均高于IESA算法所獲得的系統(tǒng)頻譜效益。并且，在認(rèn)知用戶數(shù)量增加的過程中，IESA算法的系統(tǒng)頻譜效益波動(dòng)較大。

圖6M為50的頻譜效益

為了進(jìn)一步驗(yàn)證IESA算法，本文繼續(xù)使用Jing Zhong和Jialiang Li于2009年開發(fā)的認(rèn)知無線電仿真模塊CRCN[10]對NS2進(jìn)行了擴(kuò)展，并分別完成了CSGC算法和IESA算法在NS2下的仿真實(shí)驗(yàn)。

本文主要針對CSGC算法和IESA算法的分組傳輸時(shí)延、分組丟失率、信道干擾量和網(wǎng)絡(luò)吞吐量等參數(shù)進(jìn)行分析。在仿真實(shí)驗(yàn)中，10對認(rèn)知用戶在1 000×1 000的區(qū)域內(nèi)感知并接入3條授權(quán)信道進(jìn)行FTP通信。認(rèn)知節(jié)點(diǎn)的地理位置隨機(jī)生成。

圖7給出了2種頻譜分配算法的實(shí)時(shí)信道干擾量仿真結(jié)果。可以看出，IESA算法中的認(rèn)知用戶在接入相同授權(quán)信道的干擾量與CSGC算法的干擾量差別不太明顯，僅在仿真過程的開始階段和結(jié)束階段有細(xì)微的差別。在3s～7s期間，2種頻譜分配算法的干擾量大致相同。IESA算法在仿真初期的信道干擾量相對較高；在仿真結(jié)束階段，CSGC算法的信道干擾量相對較高。

圖7 實(shí)時(shí)信道干擾量

圖8給出了2種頻譜分配算法在發(fā)送第800個(gè)到第8 000個(gè)數(shù)據(jù)分組過程中被正確接收的數(shù)據(jù)分組的實(shí)時(shí)累積時(shí)延。由于IESA算法是基于沖突消減的分配算法，且在同一信道中來自不同節(jié)點(diǎn)的數(shù)據(jù)分組的沖突退避時(shí)間較短，數(shù)據(jù)分組從發(fā)送到接收的累積時(shí)延都較小。可以看出，在整個(gè)仿真過程中IESA算法相對于CSGC算法在傳輸過程中引入的延遲較低。當(dāng)數(shù)據(jù)分組傳輸數(shù)量達(dá)到6 400個(gè)時(shí)，IESA算法的累積延遲才超過CSGC算法。

圖9給出了CSGC算法和IESA算法在不同時(shí)間段內(nèi)的傳輸分組丟失率?？梢钥吹?，在仿真初始階段，各個(gè)認(rèn)知用戶間由于尚未建立起通信連接，認(rèn)知用戶發(fā)送或接收到的 RTS/CTS控制分組數(shù)量較多；同時(shí)，由于多個(gè)FTP業(yè)務(wù)的啟動(dòng)時(shí)間相對一致，認(rèn)知用戶之間的控制分組發(fā)生沖突的概率較大，網(wǎng)絡(luò)應(yīng)用在2種頻譜分配算法的仿真初期分組丟失率均相對較高。當(dāng)t=4s時(shí)，CSGC算法的分組丟失率達(dá)到最大。傳輸過程啟動(dòng)5s后，不同授權(quán)信道上的數(shù)據(jù)分組不斷積累，導(dǎo)致2種頻譜分配算法的平均分組丟失率略呈上升趨勢?？梢园l(fā)現(xiàn)，在整個(gè)仿真過程中IESA算法的平均分組丟失率都低于CSGC算法。

圖8 分組傳輸?shù)睦鄯e時(shí)延

圖9 通信過程中的分組丟失率

圖10給出了運(yùn)行CSGC算法和IESA算法的認(rèn)知無線電網(wǎng)絡(luò)在仿真過程中的實(shí)時(shí)吞吐量。與傳輸分組丟失率的分布類似，通信初期由于大量控制分組的交互，網(wǎng)絡(luò)吞吐量在短時(shí)間內(nèi)急劇增長。當(dāng)t=4s時(shí)，IESA算法的吞吐量達(dá)到最大值；由于IESA算法在認(rèn)知用戶數(shù)量明顯多于授權(quán)信道數(shù)量時(shí)能夠滿足更多的認(rèn)知用戶的接入需求，在整個(gè)仿真過程中，IESA算法都能取得比CSGC算法更好的運(yùn)行性能。

圖10 不同時(shí)間段的網(wǎng)絡(luò)吞吐量

綜合上述分析和仿真結(jié)果可以看出，CSGC算法的目標(biāo)是在避免干擾的前提下，最大化認(rèn)知無線電網(wǎng)絡(luò)的頻譜效益。在認(rèn)知用戶的接入數(shù)量和頻譜效益之間，CSGC算法更加側(cè)重于認(rèn)知用戶利用所分配到的頻譜資源所獲得的最大頻譜效益。IESA算法則綜合分析了不同認(rèn)知用戶的頻譜共享程度和可用頻譜數(shù)量，以最大化認(rèn)知用戶接入數(shù)量為目標(biāo)。因此，CSGC算法適合于頻譜資源數(shù)量較多或系統(tǒng)對頻譜效益要求較高的場景；而 IESA算法則適合于對認(rèn)知用戶接入數(shù)量要求較高的場景或認(rèn)知用戶數(shù)量明顯大于授權(quán)頻譜總數(shù)的場景。

6 結(jié)束語

本文在綜合分析了認(rèn)知無線電網(wǎng)絡(luò)頻譜接入、頻譜干擾的基礎(chǔ)上，提出了一種基于干擾消減的認(rèn)知無線電頻譜分配算法。該算法通過檢測能夠共享同一授權(quán)頻段的所有認(rèn)知用戶，優(yōu)化了接入授權(quán)頻譜的認(rèn)知用戶數(shù)量。同時(shí)，該算法對未獲得頻譜資源的認(rèn)知用戶按照其可用頻譜數(shù)量進(jìn)行特殊處理，保證了頻譜分配過程的公平性。

模擬和仿真實(shí)驗(yàn)結(jié)果表明，該算法能夠在認(rèn)知用戶數(shù)量較多、可用頻譜緊張的情況下對認(rèn)知無線電網(wǎng)絡(luò)的頻譜分配過程進(jìn)行優(yōu)化，能夠增加接入授權(quán)頻譜的認(rèn)知用戶數(shù)量，在一定程度上提高認(rèn)知無線電網(wǎng)絡(luò)的頻譜效益。

[1] STAPLE G, WERBACH K. The end of spectrum scarcity [J]. IEEE Spectrum, 2004, 41(3):48-52.

[2] 孟祥初. 通信產(chǎn)業(yè)網(wǎng)[EB/OL]. http://www.ccidcom.com/html/chanpinj- ishu/wuxiantongxin/200911/02-80768.html,2009.MENG X C. The usage survey of wireless spectrum[EB/OL].http://www.ccidcom.com/html/chanpinj-ishu/wuxiantongxin/200911/02- 80768.html,2009.

[3] JOSEPH M III, Cognitive radio for flexible mobile multimedia communications [J]. MONET, 2001, 6(5):435-441.

[4] WANG W, LIU X. List-coloring based channel allocation for open-spectrum wireless networks[A]. Proc of the 62nd IEEE Vehicular Technology Conference[C].Dallas, texas, USA, 2005. 690-694.

[5] ZHENG H, PENG C. Collaboration and fairness in opportunistic spectrum access[A]. Proc of the 2005 IEEE International Conference on Communications[C]. Beijing, China, 2005. 3132 -3136.

[6] TANG J, MISRA S. Joint spectrum allocation and scheduling for fair spectrum sharing in cognitive radio wireless networks[J]. The International Journal of Computer Networks, 2008, 52(11):2148-2158.

[7] HOANG A, LIANG Y. Maximizing spectrum utilization of cognitive radio networks using channel allocation and power control[A]. IEEE 64th Vehicular Technology Conference[C]. Singapore, 2006. 1-5.

[8] XIE X, ZHOU T, DONG X. Traffic-demand dynamic spectrum access[A]. Proc of the 4th International Conference on Wireless Communications, Networking and Mobile Computing[C]. Chongqing,China, 2008.1-4.

[9] AHMED W, GAO J, FAUKNER M. Channel allocation for fairness in opportunistic spectrum access networks[A]. Proc of the 2010 IEEE Wireless Communications and Networking Conference[C]. Sydney,Australia, 2010.1-6.

[10] 林闖,李寅,萬劍雄. 計(jì)算機(jī)網(wǎng)絡(luò)服務(wù)質(zhì)量優(yōu)化方法研究綜述[J].計(jì)算機(jī)學(xué)報(bào),2011,34(1):1-14.LIN C, LI Y, WAN J X. Optimization approaches for QoS in computer networks: a survey[J]. Chinese Journal of Computers, 2011,34(1):1-14.

[11] Cognitive radio cognitive network simulator[EB/OL]. http://stuweb.ee.mtu.edu/～ljialian/.