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

趙鵬博，呂　娜，陳柯帆

(空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，陜西 西安 710077)

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

趙鵬博，呂娜，陳柯帆

(空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，陜西 西安 710077)

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

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

0引言

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

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

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

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

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

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

1.1信道資源結(jié)構(gòu)

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

圖1　時頻信道資源結(jié)構(gòu)圖Fig 1　Structure diagram of time frequency channel resources

因此，假設(shè)第k用戶需要傳輸?shù)臄?shù)據(jù)量為Rk，資源分配應(yīng)該滿足以下關(guān)系

(1)

1.2資源分配原則

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

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

通過以上定義可知

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

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

(2)

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

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

2)節(jié)點(diǎn)k不在該資源塊上接收數(shù)據(jù)；

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

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

1.3效用函數(shù)

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

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

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

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

(3)

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

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

(4)

式中Imin為業(yè)務(wù)最低的指標(biāo)需求。

1.4問題描述

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

目標(biāo)函數(shù)

(5)

(6)

(7)

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

2資源分配算法

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

2.1PSO

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

設(shè)粒子群在一個n維空間中搜索，由M個粒子組成種群X={X1,X2,…,XM}，其中,每個粒子所處的位置Xi={xi1,xi2,…,xin}都表示問題的一個解。粒子通過不斷調(diào)整自己位置xid來搜索新解。每個粒子都能記住自己搜索的最優(yōu)解，記為Pid，以及整個粒子群的最優(yōu)解，記為Pgd。每個粒子的速度，記為Vi={vi1,vi2,…,vin}。每次粒子的更新由自身的經(jīng)驗(yàn)和群體最優(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為粒子數(shù)量；i為粒子編號；w為慣性權(quán)重，表示粒子保持之前速度的程度；r1，r2是兩個均勻分布在[0,1]區(qū)間的隨機(jī)數(shù)；η1，η2為學(xué)習(xí)因子，分別自身成功經(jīng)驗(yàn)和群體最優(yōu)值對粒子的影響度。

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

(10)

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

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

(11)

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

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

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

(12)

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

(13)

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

其中，Vis中的(aqm,bqm)表示將其第m項(xiàng)變?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算法如下所示。其中，最大迭代次數(shù)為50～100；學(xué)習(xí)因子η1，取值為2；慣性權(quán)重w取值為1；粒子群中粒子數(shù)量取值為50。

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

Begin

1)初始化粒子群

2)賦值最大迭代次數(shù)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)根據(jù)式(13)計算粒子適應(yīng)度Ui

9)根據(jù)式(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仿真結(jié)果與分析

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

表1　仿真參數(shù)設(shè)定

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

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

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

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

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

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

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

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

4結(jié)論

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

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

參考文獻(xiàn):

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

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

[3]王挺,馮輝.正交頻分多址接入系統(tǒng)中接收能耗優(yōu)化的二維時頻資源分配算法[J].復(fù)旦大學(xué):自然科學(xué)版,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]王韜,張彥波.基于信譽(yù)與權(quán)重機(jī)制的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] 宋亞楠.基于效用的網(wǎng)絡(luò)資源分配研究[D].北京：清華大學(xué),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

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

中圖分類號：TP 391.9

文獻(xiàn)標(biāo)識碼：A

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

作者簡介:

趙鵬博(1992-)，男，碩士研究生，研究方向?yàn)檐娛潞娇胀ㄐ拧?/p>