粒子群优化的时频联合资源分配算法*

赵鹏博，吕　娜，陈柯帆

(空军工程大学 信息与导航学院，陕西 西安 710077)

粒子群优化的时频联合资源分配算法*

赵鹏博，吕娜，陈柯帆

(空军工程大学 信息与导航学院，陕西 西安 710077)

摘要:针对航空通信环境中正交频分多址系统的资源分配问题，在信道资源有限的约束条件下，以最大化用户节点的效用总和为目标，提出了一种基于粒子群优化(PSO)的时频联合资源分配算法。该算法采用离散变量来编码粒子位置，并针对离散空间构建新的基于概率信息的粒子速度和位置更新算法。仿真结果表明：所提出的资源分配算法在效用总和、公平性等方面优于现有资源分配算法。

关键词：正交频分多址；资源分配；粒子群优化；效用函数

0引言

与航空通信中不断增长的大数据相矛盾的是有限的通信资源。为了提升航空通信中的吞吐量和缓解通信资源紧张的局面，联邦航空局(FAA)和欧安局(EUROCONTROL)建议未来航空通信系统中的物理层采用频谱利用率更高的正交频分复用(orthogonal frequency division multiplexing，OFDM)技术。基于OFDM技术的正交频分多址(orthogonal frequency division multiple access，OFDMA)因其高的传输速率和灵活的接入方式备受人们关注。

目前,关于OFDMA系统的资源分配文献主要从优化子载波、功率、用户协同等角度研究如何提升系统的性能。文献[1]中引入预留机制的多小区OFDMA系统资源分配方案，引入移动资源预留，改善了在频繁切换过程中导致服务质量差的现象。文献[2]中提出了基于服务质量(QoS)的协作OFDMA系统无线资源分配算法，通过建立效用函数模型，联合功率、载波分配和中继选择使得效用最大，从而提升了对异质业务的支持能力，保证了用户之间的公平性，但是算法中没有对于业务类型进行区分。文献[3]中，提出一种正交频分多址接入系统中接收能耗优化的二维时频资源分配算法，可以获得较高的资源分配效率。

从目前文献的研究现状来看[4～7]，为了解决OFDMA系统中吞吐量和业务公平性这一对矛盾，人们引入效用(uti-lity)理论来衡量通信中各个业务的满期程度[8,9]。文中以系统中所有用户不同业务的总效用最大为优化目标，解决在时帧长度受限条件下的信道资源分配问题。

通信中每种业务根据自身特点对应不同的效用函数，此时资源分配问题需要转化成为凸优化问题来求解，在这类问题的求解中，启发式智能算法是一条有效的路径，如粒子群优化(particle swarm optimization，PSO)算法。

本文基于航空环境下，结合OFDMA中资源分配灵活的特点，利用PSO算法，提出一种基于PSO的时频联合资源分配算法(PSO for allocation algorithm in two dimensional resources,PSO-TDR)。

1时频信道资源分配模型与问题

1.1信道资源结构

航空通信中时分多址(time division multiple access，TDMA)是一种基于时隙的信道资源划分方式，本文在时隙划分信道资源的基础上结合OFDMA系统子载波资源划分灵活的特点，提出了一种时频信道资源的划分方式，如图1。

图1　时频信道资源结构图Fig 1　Structure diagram of time frequency channel resources

因此，假设第k用户需要传输的数据量为Rk，资源分配应该满足以下关系

(1)

1.2资源分配原则

在通信中，收发数据一般分为二种情况：1)发送方不知道接收节点，发送方以广播的形式发送数据，编队内的所有成员接收信息，根据需求取舍信息；2)发送方明确需要接收信息的节点，这种情况下传播可分为组播和单播两种形式。为了提升信道资源的利用率，执行分配算法的节点要明确所有用户的需求。

在每个时帧中，资源块RS是其基本组成单位，每个资源块位置由(t,f)确定，其中,t确定资源块的时隙位置，f确定资源块频率位置。对于任意发送方k，D(k)表示需要接收k信息的所有集合，l(k,j)表示发送方与接收方之间的传输链路，在广播和组播的条件下j表示一个集合，在单播条件下j只表示一个用户。为了明确通信中各个节点对信道的需求情况，用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)

编队中飞机采用半双工工作模式，在同一个资源块中只能完成接收或发送数据，因此,将一个RS分配给链路l(k,j)需满足以下的约束条件：

1)该资源块RS还没有分配给k和集合j中的任何一个；

2)节点k不在该资源块上接收数据；

3)集合j中的所有节点不能在该资源块上传输数据；

4)占用同一时隙的不同发送节点不能在同一个通信链路中。

1.3效用函数

用户通过业务量确定占用资源块的数量后，可以根据自身业务类型的特点动态调整资源块时隙和占用载波的位置，不同的分配方案带来不同的性能指标。

各类型业务对于性能指标的满意程度可以用效用表示，使用效用函数可衡量资源分配方案的优劣，不同类型的业务和用户对应不同的效用函数[11]。文中业务类型分为两类，一类是弹性业务，另一类是严格实时性业务。

弹性业务的效用函数可以表示为[12]

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

(3)

式中ak=-(ln 0.1)/ck，ck为性能指标的目标值，在达到目标性能指标时用户的效用为0.9。在性能指标很低时，效用会随着性能指标的提升迅速上升；随着性能指标的提升，效用的增长变得缓慢。

在严格实时性业务中，效用函数可以表示如下

(4)

式中Imin为业务最低的指标需求。

1.4问题描述

在引入效用函数后，信道资源优化的目标转化为最大化效用总和的问题。优化的问题表示如下：

目标函数

(5)

(6)

(7)

式(6)和式(7)保证每个资源块最多分配给一个用户。

2资源分配算法

现将信道资源分配问题转化成寻找效用函数最大值的离散变量优化问题。

2.1PSO

粒子群算法中每个优化问题的解都被看成一个粒子[15]。首先,在可行解空间中随机初始化一群粒子，每个粒子均为优化问题的一个可行解，且解空间中运动，并追随当前的最优粒子在解空间中进行搜索。在PSO算法中，通过粒子本身的最优解和整个种群数目前的最优解这两个极值完成粒子的迭代更新。

设粒子群在一个n维空间中搜索，由M个粒子组成种群X={X1,X2,…,XM}，其中,每个粒子所处的位置Xi={xi1,xi2,…,xin}都表示问题的一个解。粒子通过不断调整自己位置xid来搜索新解。每个粒子都能记住自己搜索的最优解，记为Pid，以及整个粒子群的最优解，记为Pgd。每个粒子的速度，记为Vi={vi1,vi2,…,vin}。每次粒子的更新由自身的经验和群体最优值共同决定，其速度和位置更新公式为

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]区间的随机数；η1，η2为学习因子，分别自身成功经验和群体最优值对粒子的影响度。

在问题为最大化优化问题时，在每次迭代中每个粒子根据下面公式更新个体最优值

(10)

式中f(g)为需要优化的函数，用来评估粒子的适应程度。

而群体的最优值为

(11)

2.2基于PSO的资源优化算法

为了解决文中离散问题的优化问题，需要使用离散粒子群优化(DPSO)，DPSO用于资源优化的步骤如下。根据用户对于资源块的需求，将用户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项变为(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算法实现过程如下

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)更新粒子个体最优Pid(t)

10)end for

11)采用式(11)更新群体最优Pgd(t)

12)t=t+1

13)end while

14)得到最优解

End

3仿真结果与分析

仿真中结合航空通信环境与业务特点，假设通信中业务分为弹性业务和严格实时性2种，每个平台一次只收发一种业务，每个节点中业务量从1M逐渐增加到2M。仿真中参数的详细设定见表1。

表1　仿真参数设定

图2表示两类业务时延随通信节点数量变化的趋势。从仿真中可以看出，随着通信中节点数量从10增加到15，严格实时性业务时延维持在10 ms以内。根据弹性业务的效用函数可以看出，随着通信节点数量的增加，为了保证整个通信系统的效用函数最大化，通过在一定范围降低通信性能保证整个通信系统效用值最大化。

图2　两种业务的平均时延Fig 2　Average delay of two different business

图3显示了随着通信节点数量变化，PSO—TDR算法的迭代收敛性以及效用总和的变化趋势。从仿真的结果可以看出：在节点数固定条件下，效用总和随着迭代次数增加而增加，但在较高的迭代次数时，效用总和逐渐饱和。这反映出在最初的迭代过程中，粒子通过快速地移动寻找最优解，在迭代多次之后逐渐收敛到最优解。图中还显示出，随着通信中节点的增加，效用总和也在增加，但当节点数量达到14及以上时，效用总和变化不是很明显。该现象说明，在通信中当节点达到一定程度通信的容量将达到饱和。

图3　DPSO算法迭代的收敛性Fig 3　Convergence property of DPSO algorithm iteration

图4显示了随节点数量变化，TDMA分配方式与PSO—TDR算法效用总和的变化趋势。从仿真结果可以看出:在节点数量在11以内时，TDMA分配方式效用总和略高于本文PSO—TDR分配算法；在节点数量大于11时，TDMA分配方式效用总和低于文中提出的PSO—TDR分配算法效用总和。这是因为TDMA是固定分配方式，随着节点数量增加，分配给每个节点的时隙确定，因此，效用函数总和基本保持稳定；相比之下，本文的PSO—TDR分配方式有较大的灵活性，因此，随着节点数量的增加，本文PSO—TDR分配算法的效用总和高于TDMA分配方式的效用总和。

图4　两种分配方式效用总和对比Fig 4　Utility sum comparison of two different allocation modes

图5是随着通信中节点数量变化各节点平均接入概率的比较。公平性指数是指在一个时帧中各节点成功接入的概率。由图显示，在节点数量小于13时，TDMA分配方式的公平性指数为1，在节点数量大于12时，TDMA分配方式公平性指数迅速恶化；本文的PSO—TDR算法公平指数一直维持在0.9附近。这是因为随着节点数量的增加，本文分配方式为了追求效用的最大化，会通过动态调整分配使得接近目标性能，使得公平性指数达到提高。

图5　两种分配方式下公平指数对比Fig 5　Fairness index comparison of two differentallocation modes

4结论

针对航空通信环境中OFDMA系统的资源分配问题，在信道资源有限的条件下，提出了一种基于PSO的时频联合资源分配算法。该算法在收发约束条件下合理分配各节点占用信道资源，将不同分配方案下的性能指标作为效用函数输入，效用函数总和最大化作为目标函数，寻找最优的分配方案。通过仿真，文中提出的基于PSO的时

频联合资源分配算法在效用总和以及公平性方面都优于TDMA分配方案。

参考文献:

[1]刘蓓,邱玲.引入预留机制的多小区OFDMA系统资源分配方案[J].中国科学技术大学学报,2013,43(1):50-56.

[2]张丹华,陶晓明.基于QoS保证的协作OFDMA系统无线资源分配算法[J].清华大学学报：自然科学版,2011,51(7):999-1003.

[3]王挺,冯辉.正交频分多址接入系统中接收能耗优化的二维时频资源分配算法[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].传感器与微系统,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] 张伟.基于粒子群优化的三维测向交叉地位算法[J].传感器与微系统,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)；航天科技创新基金资助项目(CASC020302)

中图分类号：TP 391.9

文献标识码：A

文章编号：1000—9787(2016)05—0135—04

作者简介:

赵鹏博(1992-)，男，硕士研究生，研究方向为军事航空通信。