粒子群優(yōu)化的時頻聯(lián)合資源分配算法*

趙鵬博，呂　娜，陳柯帆

(空軍工程大學 信息與導航學院，陜西 西安 710077)

粒子群優(yōu)化的時頻聯(lián)合資源分配算法*

趙鵬博，呂娜，陳柯帆

(空軍工程大學 信息與導航學院，陜西 西安 710077)

摘要:針對航空通信環(huán)境中正交頻分多址系統(tǒng)的資源分配問題，在信道資源有限的約束條件下，以最大化用戶節(jié)點的效用總和為目標，提出了一種基于粒子群優(yōu)化(PSO)的時頻聯(lián)合資源分配算法。該算法采用離散變量來編碼粒子位置，并針對離散空間構建新的基于概率信息的粒子速度和位置更新算法。仿真結果表明：所提出的資源分配算法在效用總和、公平性等方面優(yōu)于現(xiàn)有資源分配算法。

關鍵詞：正交頻分多址；資源分配；粒子群優(yōu)化；效用函數

0引言

與航空通信中不斷增長的大數據相矛盾的是有限的通信資源。為了提升航空通信中的吞吐量和緩解通信資源緊張的局面，聯(lián)邦航空局(FAA)和歐安局(EUROCONTROL)建議未來航空通信系統(tǒng)中的物理層采用頻譜利用率更高的正交頻分復用(orthogonal frequency division multiplexing，OFDM)技術?；贠FDM技術的正交頻分多址(orthogonal frequency division multiple access，OFDMA)因其高的傳輸速率和靈活的接入方式備受人們關注。

目前,關于OFDMA系統(tǒng)的資源分配文獻主要從優(yōu)化子載波、功率、用戶協(xié)同等角度研究如何提升系統(tǒng)的性能。文獻[1]中引入預留機制的多小區(qū)OFDMA系統(tǒng)資源分配方案，引入移動資源預留，改善了在頻繁切換過程中導致服務質量差的現(xiàn)象。文獻[2]中提出了基于服務質量(QoS)的協(xié)作OFDMA系統(tǒng)無線資源分配算法，通過建立效用函數模型，聯(lián)合功率、載波分配和中繼選擇使得效用最大，從而提升了對異質業(yè)務的支持能力，保證了用戶之間的公平性，但是算法中沒有對于業(yè)務類型進行區(qū)分。文獻[3]中，提出一種正交頻分多址接入系統(tǒng)中接收能耗優(yōu)化的二維時頻資源分配算法，可以獲得較高的資源分配效率。

從目前文獻的研究現(xiàn)狀來看[4～7]，為了解決OFDMA系統(tǒng)中吞吐量和業(yè)務公平性這一對矛盾，人們引入效用(uti-lity)理論來衡量通信中各個業(yè)務的滿期程度[8,9]。文中以系統(tǒng)中所有用戶不同業(yè)務的總效用最大為優(yōu)化目標，解決在時幀長度受限條件下的信道資源分配問題。

通信中每種業(yè)務根據自身特點對應不同的效用函數，此時資源分配問題需要轉化成為凸優(yōu)化問題來求解，在這類問題的求解中，啟發(fā)式智能算法是一條有效的路徑，如粒子群優(yōu)化(particle swarm optimization，PSO)算法。

本文基于航空環(huán)境下，結合OFDMA中資源分配靈活的特點，利用PSO算法，提出一種基于PSO的時頻聯(lián)合資源分配算法(PSO for allocation algorithm in two dimensional resources,PSO-TDR)。

1時頻信道資源分配模型與問題

1.1信道資源結構

航空通信中時分多址(time division multiple access，TDMA)是一種基于時隙的信道資源劃分方式，本文在時隙劃分信道資源的基礎上結合OFDMA系統(tǒng)子載波資源劃分靈活的特點，提出了一種時頻信道資源的劃分方式，如圖1。

圖1　時頻信道資源結構圖Fig 1　Structure diagram of time frequency channel resources

因此，假設第k用戶需要傳輸的數據量為Rk，資源分配應該滿足以下關系

(1)

1.2資源分配原則

在通信中，收發(fā)數據一般分為二種情況：1)發(fā)送方不知道接收節(jié)點，發(fā)送方以廣播的形式發(fā)送數據，編隊內的所有成員接收信息，根據需求取舍信息；2)發(fā)送方明確需要接收信息的節(jié)點，這種情況下傳播可分為組播和單播兩種形式。為了提升信道資源的利用率，執(zhí)行分配算法的節(jié)點要明確所有用戶的需求。

在每個時幀中，資源塊RS是其基本組成單位，每個資源塊位置由(t,f)確定，其中,t確定資源塊的時隙位置，f確定資源塊頻率位置。對于任意發(fā)送方k，D(k)表示需要接收k信息的所有集合，l(k,j)表示發(fā)送方與接收方之間的傳輸鏈路，在廣播和組播的條件下j表示一個集合，在單播條件下j只表示一個用戶。為了明確通信中各個節(jié)點對信道的需求情況，用C(k,j,t,f)表示信息傳輸鏈路l(k,j)對資源塊(t,f)的占用情況，n(k,j)表示分配給傳輸鏈路(k,j)的資源塊數量。

通過以上定義可知

C(k,j,t,f)∈{0,1},

?j∈D(k)，?t=1,2,…，T，?f=1,2,…,w

(2)

編隊中飛機采用半雙工工作模式，在同一個資源塊中只能完成接收或發(fā)送數據，因此,將一個RS分配給鏈路l(k,j)需滿足以下的約束條件：

1)該資源塊RS還沒有分配給k和集合j中的任何一個；

2)節(jié)點k不在該資源塊上接收數據；

3)集合j中的所有節(jié)點不能在該資源塊上傳輸數據；

4)占用同一時隙的不同發(fā)送節(jié)點不能在同一個通信鏈路中。

1.3效用函數

用戶通過業(yè)務量確定占用資源塊的數量后，可以根據自身業(yè)務類型的特點動態(tài)調整資源塊時隙和占用載波的位置，不同的分配方案帶來不同的性能指標。

各類型業(yè)務對于性能指標的滿意程度可以用效用表示，使用效用函數可衡量資源分配方案的優(yōu)劣，不同類型的業(yè)務和用戶對應不同的效用函數[11]。文中業(yè)務類型分為兩類，一類是彈性業(yè)務，另一類是嚴格實時性業(yè)務。

彈性業(yè)務的效用函數可以表示為[12]

U(I)=1-e-akI,R≥0

(3)

式中ak=-(ln 0.1)/ck，ck為性能指標的目標值，在達到目標性能指標時用戶的效用為0.9。在性能指標很低時，效用會隨著性能指標的提升迅速上升；隨著性能指標的提升，效用的增長變得緩慢。

在嚴格實時性業(yè)務中，效用函數可以表示如下

(4)

式中Imin為業(yè)務最低的指標需求。

1.4問題描述

在引入效用函數后，信道資源優(yōu)化的目標轉化為最大化效用總和的問題。優(yōu)化的問題表示如下：

目標函數

(5)

(6)

(7)

式(6)和式(7)保證每個資源塊最多分配給一個用戶。

2資源分配算法

現(xiàn)將信道資源分配問題轉化成尋找效用函數最大值的離散變量優(yōu)化問題。

2.1PSO

粒子群算法中每個優(yōu)化問題的解都被看成一個粒子[15]。首先,在可行解空間中隨機初始化一群粒子，每個粒子均為優(yōu)化問題的一個可行解，且解空間中運動，并追隨當前的最優(yōu)粒子在解空間中進行搜索。在PSO算法中，通過粒子本身的最優(yōu)解和整個種群數目前的最優(yōu)解這兩個極值完成粒子的迭代更新。

設粒子群在一個n維空間中搜索，由M個粒子組成種群X={X1,X2,…,XM}，其中,每個粒子所處的位置Xi={xi1,xi2,…,xin}都表示問題的一個解。粒子通過不斷調整自己位置xid來搜索新解。每個粒子都能記住自己搜索的最優(yōu)解，記為Pid，以及整個粒子群的最優(yōu)解，記為Pgd。每個粒子的速度，記為Vi={vi1,vi2,…,vin}。每次粒子的更新由自身的經驗和群體最優(yōu)值共同決定，其速度和位置更新公式為

vid(t+1)=wvid(t)+η1r1(Pid(t)-xid(t))+η2t2(Pgd(t)-xid(t))

(8)

xid(t+1)=xid(t)+vid(t+1)，i∈1,2,…,M

(9)

式中M為粒子數量；i為粒子編號；w為慣性權重，表示粒子保持之前速度的程度；r1，r2是兩個均勻分布在[0,1]區(qū)間的隨機數；η1，η2為學習因子，分別自身成功經驗和群體最優(yōu)值對粒子的影響度。

在問題為最大化優(yōu)化問題時，在每次迭代中每個粒子根據下面公式更新個體最優(yōu)值

(10)

式中f(g)為需要優(yōu)化的函數，用來評估粒子的適應程度。

而群體的最優(yōu)值為

(11)

2.2基于PSO的資源優(yōu)化算法

為了解決文中離散問題的優(yōu)化問題，需要使用離散粒子群優(yōu)化(DPSO)，DPSO用于資源優(yōu)化的步驟如下。根據用戶對于資源塊的需求，將用戶m占用資源塊的需求離散為空間的向量，第i個粒子可以表示為

Xi{(ai1,bi1),(ai2,bi2),…，(ain,bin),…,(aiM,biM)}，ain∈{0,1,…,T}，bin∈{0,1,…,W}

(12)

對應的ain=t,bin=w表示用戶k占用第t時隙中的第w載波，根據用戶k占用資源塊帶來的通信指標量化出用戶效用Ik，則粒子的適應度定義為所有用戶的效用綜合

(13)

定義1粒子位置相減更新速度

其中，Vis中的(aqm,bqm)表示將其第m項變?yōu)?aqm,bqm)；而-1表示沒有變化。

定義2粒子位置和速度相加更新位置

給定粒子位置Xi={(ai1,bi1),(ai2,bi2),…，(aiM,biM)}和速度Vc={(ac1,bc1),(ac2,bc2)，…，(acM,bcM)}，定義它們位置與速度相加為新的位置操作為Xj=Xj+Xc={(aj1,bj1),(aj2,bj2),…,(ajM,bjM)}，其中

基于以上定義最終得到DPSO算法如下所示。其中，最大迭代次數為50～100；學習因子η1，取值為2；慣性權重w取值為1；粒子群中粒子數量取值為50。

DPSO算法實現(xiàn)過程如下

Begin

1)初始化粒子群

2)賦值最大迭代次數Max_iterations

3)t=1

4)while t≤Max_interations do

5)for each particle i do

6)采用式(8)更新粒子速度vid(t)

7)采用式(9)更新粒子位置xid(t)

8)根據式(13)計算粒子適應度Ui

9)根據式(10)更新粒子個體最優(yōu)Pid(t)

10)end for

11)采用式(11)更新群體最優(yōu)Pgd(t)

12)t=t+1

13)end while

14)得到最優(yōu)解

End

3仿真結果與分析

仿真中結合航空通信環(huán)境與業(yè)務特點，假設通信中業(yè)務分為彈性業(yè)務和嚴格實時性2種，每個平臺一次只收發(fā)一種業(yè)務，每個節(jié)點中業(yè)務量從1M逐漸增加到2M。仿真中參數的詳細設定見表1。

表1　仿真參數設定

圖2表示兩類業(yè)務時延隨通信節(jié)點數量變化的趨勢。從仿真中可以看出，隨著通信中節(jié)點數量從10增加到15，嚴格實時性業(yè)務時延維持在10 ms以內。根據彈性業(yè)務的效用函數可以看出，隨著通信節(jié)點數量的增加，為了保證整個通信系統(tǒng)的效用函數最大化，通過在一定范圍降低通信性能保證整個通信系統(tǒng)效用值最大化。

圖2　兩種業(yè)務的平均時延Fig 2　Average delay of two different business

圖3顯示了隨著通信節(jié)點數量變化，PSO—TDR算法的迭代收斂性以及效用總和的變化趨勢。從仿真的結果可以看出：在節(jié)點數固定條件下，效用總和隨著迭代次數增加而增加，但在較高的迭代次數時，效用總和逐漸飽和。這反映出在最初的迭代過程中，粒子通過快速地移動尋找最優(yōu)解，在迭代多次之后逐漸收斂到最優(yōu)解。圖中還顯示出，隨著通信中節(jié)點的增加，效用總和也在增加，但當節(jié)點數量達到14及以上時，效用總和變化不是很明顯。該現(xiàn)象說明，在通信中當節(jié)點達到一定程度通信的容量將達到飽和。

圖3　DPSO算法迭代的收斂性Fig 3　Convergence property of DPSO algorithm iteration

圖4顯示了隨節(jié)點數量變化，TDMA分配方式與PSO—TDR算法效用總和的變化趨勢。從仿真結果可以看出:在節(jié)點數量在11以內時，TDMA分配方式效用總和略高于本文PSO—TDR分配算法；在節(jié)點數量大于11時，TDMA分配方式效用總和低于文中提出的PSO—TDR分配算法效用總和。這是因為TDMA是固定分配方式，隨著節(jié)點數量增加，分配給每個節(jié)點的時隙確定，因此，效用函數總和基本保持穩(wěn)定；相比之下，本文的PSO—TDR分配方式有較大的靈活性，因此，隨著節(jié)點數量的增加，本文PSO—TDR分配算法的效用總和高于TDMA分配方式的效用總和。

圖4　兩種分配方式效用總和對比Fig 4　Utility sum comparison of two different allocation modes

圖5是隨著通信中節(jié)點數量變化各節(jié)點平均接入概率的比較。公平性指數是指在一個時幀中各節(jié)點成功接入的概率。由圖顯示，在節(jié)點數量小于13時，TDMA分配方式的公平性指數為1，在節(jié)點數量大于12時，TDMA分配方式公平性指數迅速惡化；本文的PSO—TDR算法公平指數一直維持在0.9附近。這是因為隨著節(jié)點數量的增加，本文分配方式為了追求效用的最大化，會通過動態(tài)調整分配使得接近目標性能，使得公平性指數達到提高。

圖5　兩種分配方式下公平指數對比Fig 5　Fairness index comparison of two differentallocation modes

4結論

針對航空通信環(huán)境中OFDMA系統(tǒng)的資源分配問題，在信道資源有限的條件下，提出了一種基于PSO的時頻聯(lián)合資源分配算法。該算法在收發(fā)約束條件下合理分配各節(jié)點占用信道資源，將不同分配方案下的性能指標作為效用函數輸入，效用函數總和最大化作為目標函數，尋找最優(yōu)的分配方案。通過仿真，文中提出的基于PSO的時

頻聯(lián)合資源分配算法在效用總和以及公平性方面都優(yōu)于TDMA分配方案。

參考文獻:

[1]劉蓓,邱玲.引入預留機制的多小區(qū)OFDMA系統(tǒng)資源分配方案[J].中國科學技術大學學報,2013,43(1):50-56.

[2]張丹華,陶曉明.基于QoS保證的協(xié)作OFDMA系統(tǒng)無線資源分配算法[J].清華大學學報：自然科學版,2011,51(7):999-1003.

[3]王挺,馮輝.正交頻分多址接入系統(tǒng)中接收能耗優(yōu)化的二維時頻資源分配算法[J].復旦大學:自然科學版,2008,47(6):724-730.

[4]Wang T,Vandendorpe L.WSR maximized resource allocation in multiple DF relays aided OFDMA downlink transmission[J].IEEE Trans on Signal Process,2011,59(8):3964-3976.

[5]Li H X.Dynamic resource allocation in OFDMA-based DF co-operative relay network[J].Wireless Personal Communications,2012,62(3):655-670.

[6]Pan Y W,Nix A,Beach M.Distribute resource allocation for OFDMA-based relay networks[J].IEEE Trans on Veh Technol,2011,60(3):919-931.

[7]王韜,張彥波.基于信譽與權重機制的WSNs信道資源分配算法[J].傳感器與微系統(tǒng),2015,34(7):107-109.

[8]Liu C,Zhang S,Qin X.Utility-based resource allocation in OFDMA relay networks with service differentiation[C]∥IEEE WCNC,Cancum,Quintana Roo,2011:72-77.

[9]Fathi M,Taheri H.Utility-based resource allocation in orthogonal frequency division multiple access networks[J].Iet Communications,2010,4(12):1463-1470.

[10] Song G,Li Y G.Gross-layer optimization for OFDM wireless networks—part I:Theoretical framework[J].IEEE Trans on Wireless Commun,2005,4:614-624.

[11] 宋亞楠.基于效用的網絡資源分配研究[D].北京：清華大學,2013.

[12] 張偉.基于粒子群優(yōu)化的三維測向交叉地位算法[J].傳感器與微系統(tǒng),2014,33(5):141-147.

Time frequency joint resources allocation algorithm based on particle swarm optimization*

ZHAO Peng-bo,Lü Na,CHEN Ke-fan

(School of Information and Navigation,Air Force Engineering University,Xi’an 710077,China)

Abstract:Aiming at problem of resource allocation in orthogonal frequency division multiple access(OFDMA)systems in aviation communication environment is investigated，in order to maximize the sum of utility of all users under constraint of channel resource,a time frequency joint resource allocation algorithm based on particle swarm optimization(PSO)is proposed.The algorithm uses discrete variable to encode particle position,and new updating algorithm of particle velocity and particle positions based on probability information are constructed for discrete space.Simulation results show that the proposed algorithm is superior to existing algorithms sum of utility and fairness.

Key words:orthogonal frequency division multiple access(OFDMA)；resource allocation；particle swarm optimization(PSO)；utility function

DOI:10.13873/J.1000—9787(2016)05—0135—04

收稿日期：2016—03—16

*基金項目：航空基金資助項目(20140196003)；航天科技創(chuàng)新基金資助項目(CASC020302)

中圖分類號：TP 391.9

文獻標識碼：A

文章編號：1000—9787(2016)05—0135—04

作者簡介:

趙鵬博(1992-)，男，碩士研究生，研究方向為軍事航空通信。