離散二進制粒子群優化的頻譜分配算法研究

孔令榮，王 昊，殷慧婷，李 冰

(1.南京理工大學泰州科技學院，江蘇 泰州 225300；2.東南大學集成電路學院，江蘇 南京 210096)

0 引言

美國學者Joseph Mitola博士在軟件無線電的基礎上，經過提煉和升華，于1999年首次提出認知無線電(cognitive radio，CR)這一術語[1]。認知無線電技術通過感知周圍的電磁環境的變化，實時調整自身通信參數，以適應不斷更新的環境。

頻譜是一種不可再生的寶貴資源，無線通信技術的快速發展受到頻譜短缺的制約[2]。為了更好地對頻譜分配問題開展研究，許多文獻提出了各種頻譜分配模型，包括圖論著色模型、博弈論模型與定價拍賣模型等[3-4]。頻譜分配問題實際上可以歸結為一個NP-hard約束優化問題[5]，頻譜分配的最優策略依靠傳統的算法很難實現。離散二進制粒子群優化算法作為一種智能算法，在穩定性與尋優性能方面具備一定的優勢。本文在充分研究了該算法的基礎上，將其應用到頻譜感知與分配中，采用線性減少慣性權重系數，并通過仿真分析驗證了算法的可行性，證明其可以有效地解決頻譜分配問題[6-8]。

1 頻譜分配模型

本文研究的感知用戶與主用戶共存于同一區域中，以宏基站或者家庭基站作為主用戶。就通信范圍而言，宏基站要大于家庭基站。感知用戶以無線接入站點的方式接入，它的發射功率可以隨時調整。本文采用動態頻譜分配策略，Overlay接入模式，即若授權用戶接入某頻段，則感知用戶一律不可接入。

1.1 頻譜分配的圖論模型

基于圖論模型的頻譜分配示意圖如圖1所示。

圖1 頻譜分配示意圖Fig.1 Spectrum allocation diagram

主用戶個數為P，感知用戶個數為N，隨機分布在X×Y的平面內；可用頻譜個數為M，它們之間是完全正交的，也隨機分布于無線傳感網絡系統中。感知用戶能夠在同一時刻使用多個頻譜，但其前提是不對其他主用戶和感知用戶造成干擾。假設主用戶為p，p=1，2，…，P；感知用戶為n，n=1，2，…，N，它們在頻譜m(m=1,2,…,M)覆蓋范圍分別是以自身為圓心作圓形區域，其半徑分別是dpm和dnm。假設用戶和用戶間的距離是決定它們之間干擾的唯一因素，如果某一個感知用戶n和某一個感知用戶k在某個頻譜上覆蓋范圍發生交集，則可以認為感知用戶n和k之間有干擾存在，那么這個頻譜不能被感知用戶n和k使用。如圖1所示，在主用戶p沒有進行通信的情況下，頻譜m可以同時允許感知用戶1、2、3接入，但是假如感知用戶1和2同時接入頻譜m，則會產生干擾[9-11]。

以上的圖論模型也可以轉換為圖的著色問題，可以認為是對無向加權圖G=(V，EC，LB)進行著色。其中，G的頂點是V，代表著認知無線網絡中感知用戶的集合；圖的邊的集合是EC，代表感知用戶在使用某一頻譜時和它的相鄰用戶間的干擾約束關系；每個頂點的顏色列表和權重用LB表示，代表感知用戶對頻譜的可用性以及收益權重。

1.2 認知無線傳感網絡頻譜分配矩陣

通過可用頻譜矩陣、網絡效益矩陣、頻譜干擾矩陣和分配矩陣這4個矩陣，可實現頻譜狀態的標識和分配，從而實現頻譜分配。假定在某一個無限傳感網絡中，感知用戶的個數為N，通過認知無線電頻譜感知獲得了M個頻帶。根據1.1節所介紹的圖論模型，對相關矩陣可作如下定義。

①可用頻譜矩陣。

該矩陣定義為：L={ln,m|ln,m∈{0,1}}N×M,l≤n≤N,l≤m≤M。其為N×M矩陣。0或1表示每一個元素，可用頻譜矩陣描述感知用戶是否可以使用該頻帶，即指頻譜與感知用戶之間的可用關系。假如ds(n,m)

②網絡效益矩陣。

網絡效益矩陣定義為：B={bn,m}N×M。它也是N×M矩陣。它所描述的含義是頻帶m被感知用戶n使用時，無線傳感網絡所能得到的網絡效益。網絡吞吐量、網絡最大流量以及頻譜利用率等物理量都可以用來表示網絡效益。相同的頻譜資源被不同的感知用戶所使用時獲得的網絡效益往往不一樣，這是因為每個感知用戶采用的通信調制方式和發送功率均不相同。假如感知用戶無法接入頻帶m，此時ln,m=0，則一定有bn,m=0。

③頻譜干擾矩陣。

頻譜干擾矩陣定義為C={cn,k,m|cn,k,m∈[0,1]}N×M，它是N×M×M三維矩陣。通常需要依靠頻譜干擾矩陣，來描述感知用戶n和k同時使用頻帶m時是否會產生干擾。如果cn,k,m=1，表示感知用戶n和k同時使用頻帶m時會產生干擾；反之，則表示無干擾。當cn,k,m=1時，表示感知用戶n和k能夠同時使用頻帶m，也就是說該頻帶必然能夠分別被用戶n和k所使用，即表示存在制約關系：cn,k,m≤ln,m≤lk,m。當n=k時，cn,k,m=1-ln,m，只通過可用頻譜矩陣L確定。

④分配矩陣。

1.3 頻譜分配性能指標

在認知無線傳感網頻譜分配模型中，尋找頻譜分配方案的過程就是使網絡效益函數達到最大值的過程。本文運用最大效益(max sum reward，MSR)和最大比例公平(max proportional fair，MPF)這兩種不同的網絡效益函數作為頻譜分配性能指標。

①最大網絡效益。

UMSR(R)定義為：

(1)

其目標是不考慮感知用戶之間是否公平分配，而專注于使總網絡效益達到最大。

②最大比例公平網絡效益。

UMPF(R)定義為：

(2)

該網絡效益函數考慮了用戶之間的公平性。其實質是如果存在另一種頻譜分配方案，則其相關的用戶效益將弱于該網絡效益。

2 基于離散二進制粒子群的頻譜分配

2.1 基本粒子群算法

粒子群算法(particle swarm optimization，PSO)由Kennedy和Eberhart提出，其應用于連續空間的優化計算，是一種群智能進化算法。粒子自身的目標函數與種群整體評價函數可以對粒子自身的位置信息與速度信息作出相應的調整、斷判及更新，并作出動態的調整。

假定在一個D維搜索空間之中，一粒子群由m個粒子所組成。其中：第i粒子的空間位置可以表示為xi=(xi1,xi2,…,xiD)T,i=1,2,…,m；第i個粒子所經歷的最好位置稱為其個體歷史最好位置，記為pi=(pi1,pi2,…,piD)T，i=1,2,…,m；相應的適應值為個體最好適應值Fi。每個粒子均具有各自的飛行速度，可以表示為vi=(vi1,vi2,…,viD)T,i=1,2,…,m。用全局歷史最好位置表示所有粒子經歷過的最好位置，可以表示為pg=(pg1,pg2,…,ggd)，相應的適應值就是全局歷史最優適應值。

在基本PSO算法中，對于第t代粒子，其第d維(1≤d≤D)元素速度、位置更新迭代式為：

(3)

(4)

式中：ω為慣性權重；c1與c2為學習因子；r1與r2為兩個隨機數，其變化取值范圍是[0,1]。

[Xd,min,Xd,max]表示第d維粒子元素的位置變化范圍，[Vd,min,Vd,max]表示第d維粒子元素的速度變化范圍。在算法迭代過程中，假如某一維粒子元素的Xid或Vid超出了邊界值，那么就令Xid或Vid等于邊界值。

2.2 離散二進制粒子群算法

PSO算法最初用于對連續空間問題進行優化。離散二進制粒子群(binary particle swarm optimization，BPSO)算法作為基本粒子群算法的改進，其頻譜分配矩陣各值為0或1，屬于離散二進制數。在BPSO算法中，粒子定義為一組由0、1組成的二進制向量。速度值vid通過預先設計的S形限幅轉換函數Sig(vid)轉換為粒子元素xid取“1”的概率。速度值vid越大，則粒子元素位置xid取“1”的可能性越大，反之則越小。

(5)

(6)

式中：Sig(vid)為Sigmoid函數。通常，為防止速度過大，令vid∈[vidmin,vidmax]，使概率值不會過于接近0或1，保證算法能以一定的概率從一種狀態躍遷到另一種狀態，防止算法早熟。

慣性權重系數ω決定了粒子先前速度對當前速度的影響程度，起到了平衡算法全局搜索和局部搜索能力的作用。當ω的取值范圍為[0.9，1.2]時，算法優化性能較好。本文采用慣性權重ω的自適應策略，即隨著迭代的進行，線性減少權重ω。線性減少權重系數ω的公式為：

(7)

式中：ωmax和ωmin分別為最大慣性權重系數和最小慣性權重系數;t為運行的迭代數，即第t代時的權重系數值;tmax為最大運行迭代數。

慣性權重系數ω越大，表明全局探索能力越強，能探索更大的新空間；慣性權重系數ω越小，表明局部探索能力越強，能在最優解附近精細探索空間。隨著迭代的進行，線性地減少慣性權重系數ω，可以使得粒子群算法在迭代的初期有較強的探索能力，從而探索新的區域；而在后期又有較好的收斂性，可以在最優解附近精細搜索。

2.3 頻譜分配算法步驟

基于BPSO算法的頻譜分配步驟如下。

④按照式(3)和式(4)，更新粒子速度和位置信息；利用式(5)和式(6)，將位置離散二進制化。

⑤重復執行步驟③。

⑥判斷是否滿足終止條件。如果滿足，則終止算法；反之，重新執行步驟④。

3 試驗驗證

試驗驗證采用Matlab仿真平臺。BPSO參數設置c1=c2=2，ω的取值范圍為0.9～1.2，迭代次數為200。仿真40次，取仿真結果平均值。

改變主用戶數、信道數、感知用戶數，觀察與網絡效益、最大比例公平網絡效益關系，如圖2和圖3所示。

圖2 迭代次數與網絡效益關系圖Fig.2 Relationship between numbers of iterations and network benefit

圖3 迭代次數與最大比例公平網絡效益關系圖Fig.3 Relationship between numbers of iterations and maximum proportion fair networks benefit

圖2(a)和圖2(b)信道數、感知用戶數相同，主用戶數不同。如果主用戶數增加，那么可用信道空閑率會減少，從而減少感知用戶占用信道的機率，降低整體網絡效益。同理，圖3(b)和圖3(a)相比，主用戶數增加，最大比例公平網絡效益降低。

圖2(a)和圖2(c)主用戶數、感知用戶數相同，信道數不同，表明通過增加可用信道空閑數量使感知用戶占用信道的機率大大增加，整體網絡效益得到大幅度提高。同理，圖3(c)和圖3(a)相比，空閑信道數增加，最大比例公平網絡效益提高。

圖2(a)和圖2(d)主用戶數、信道數相同，感知用戶數不同。雖然感知用戶數量的增加使感知用戶之間的競爭變得激烈，但另一方面使得可用信道的利用率也有所提高，其結果是使得整體網絡效益略有提高。但是由于各感知用戶之間競爭激烈，同時受到頻譜資源的限制，圖3(d)和圖3(a)相比，空閑信道數增加，最大比例公平網絡效益降低。

將本文BPSO算法與遺傳算法(genetic algorithm，GA)、敏感圖著色法(color sensitive graph coloring algorithm，CSGC)進行比較。

圖4為使用BPSO、GA和CSGC三種算法仿真網絡效益隨迭代次數變化的關系曲線。取主用戶數為20，信道數為10，感知用戶數為20。BPSO算法的網絡效益迭代后穩定在231，GA穩定在189，CSGC穩定在165。在相同迭代次數下，采用BPSO算法可獲得較高的網絡效益，優于GA和CSGC算法。

圖4 網絡效益變化曲線Fig.4 Variation curves of network benefit

圖5為使用BPSO、GA和CSGC三種算法仿真最大比例公平網絡效益隨迭代次數變化關系曲線。取主用戶數為20，信道數為10，感知用戶數為20。BPSO算法的最大比例公平網絡效益迭代后穩定在1.4，GA穩定在0.95，CSGC穩定在0.4。在相同迭代次數下，采用BPSO算法獲得的最大比例公平網絡效益優于GA和CSGC算法。

圖5 最大比例公平網絡效益變化曲線Fig.5 Variation curves of maximum proportional fair network benefit

4 結束語

本文借助圖論模型，將頻譜分配問題轉換為網絡效益與分配矩陣尋優問題。采用離散二進制粒子群優化算法，以網絡效益、最大比例公平網絡效益為目標函數，尋找最優分配矩陣。通過改變主用戶數、信道數和感知用戶數，經過多次Matlab仿真試驗，證明了本文提出的基于離散二進制粒子群頻譜分配算法相比于遺傳算法和敏感著色法，可以獲得更高的網絡效益和最大比例公平網絡效益，并有效提高網絡吞吐量。該研究具有一定的實用價值和應用前景。

參考文獻:

[1] MITOLA J.Cognitive radio for flexible mobile multimedia communications[C]//IEEE International Workshop on Mobile Multimedia Communications,1999:3-10.

[2] GOSCINIAK I.A new approach to particle swarm optimization algorithm[J].Expert Systems with Applications，2015，42(2)：844-854.

[3] EBERHART R C，KENNEDY J.A new optimizer using particle swarm theory[C]//Proceedings of the Sixth International Symposium on Micro-Machine and Human Science,1995：39-43.

[4] TANGY，WANG Z，FANG J.Feedback learning particle swarm optimization[J].Applied Soft Computing，2011，11(8)：4713-4725.

[5] PENG C，ZHENG H，ZHAO B Y.Utilization and fairness in spectrum assignment for opportunistic spectrum access[J].Mobile Networks and Applications，2006，11(4)：555-576.

[6] EBERHART R C，SHI Y.Particle swarm optimization：developments，applications and resources[C]//Proceedings of Evolutionary Computation，2001：81-86.

[7] CLERC M,KENNEDY J.The Particle Swarm-explosion，stability，and convergence in multidimensional complex space[J].IEEE Transactions on Evolutionary Computation，2002，6(1)：58-73.

[8] HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[C]//Hawaii International Conference on System Sciences，2000：8020.

[9] JUN Z,YUN B.Analytical optimization for collaborative double-threshold energy detection in cognitive radio network[J].Journal of Information and Computational Science，2012，9(13)：3875-3882.

[10]JINJ， XUH B， RENC J.Superposition-based cooperative spectrum sensing in cognitive radio networks[C]//In Proceedings of 2010 International Conference on Computer Application and System Medeling(ICCASM),2010：342-346.

[11]GUO J， SONG T， WU M， et al.An improved weighted cooperative spectrum sensing in cognitive radio networks[C]//International Conference on Consumer Electronics，2013：113-116.