移动通信系统中的最优功率控制算法

上传者：饶丰
|
上传时间：2015-05-06
|
密次下载

移动通信系统中的最优功率控制算法

应　用　数　学

MATHEMATICAAPPLICATA2006,19(1):134～138

3移动通信系统中的最优功率控制算法

尚松蒲1,胡晓东1,李旭2

(1.中国科学院数学与系统科学研究院,北京100080;2.北京交通大学现代通讯研究所,北京100044)

摘要:本文研究了移动通信系统中的功率最优控制问题.题的最优解的性质研究,关键词:;2:90C30

:A文章编号:100129847(2006)0120134205

1.引言

更高的系统容量和通信质量,始终为数字蜂窝移动通信系统追求的目标.为实现这一目标,可采用合理分配系统资源方式.在数字蜂窝移动通信中,可供使用的资源包括无线信道、功率以及空间等.本文针对其中的功率资源的控制策略以及算法进行分析和研究.功率控制的主要目的是为抑制多址干扰,从而达到提高系统容量和节约系统能源的目的.功率控制的研究角度和策略多种多样,如文[3]的最佳功率控制性能分析;文[4]集中式功率控制策略;文[2]的分布式功率控制策略等等.本文在文献[3]的基础上对最佳功率控制模型和策略进行简化、数学建模研究以及算法分析,以求提高控制策略和算法的实用性.

2.数学模型

设在给定时刻及给定区域内,同时存在M个小区,第i个小区存在Li个用户,则第i个小区内的第j个用户接收到的载干比(C/I)为(假设背景噪声很小):

Rij=∑LiGkjPk-GijPik=1,

其中Pi为第i个基站发射的功率,Gkj为第k个基站到第j个用户的路径损耗,该路径损耗均值服从对数正态分布,瞬时值服从瑞利分布.在最佳功率分配时要满足:

1)业务用户的载干比必须大于等于目标载干比,设为γ;

2)基站发射机的发射功率小于等于最大发射功率,即0≤Pi≤Pmax.因此我们可以建立如下(L1+L2+…+LM)个方程组:

3收稿日期:2005203224

基金项目:国家自然科学基金资助项目(70221001,60373012)

作者简介:尚松蒲,男,汉,河南人,博士,研究方向:组合优化

内容需要下载文档才能查看

第1期尚松蒲等:

内容需要下载文档才能查看

移动通信系统中的最优功率控制算法135

Ri1=∑

∑LiGkjPk-GijPik=1γ,≥…(Ⅰ)Rij=Li

k=1GkjPk-GijPiγ,≥

…

RiLi=GiLPi∑LiGkjPk-GijPik=1γ

内容需要下载文档才能查看

≥.

在上面的不等式组中,k=1,2,…,M;i=1,2,…,M.这里我们不妨将链路增益近似为某时刻的测量值,简化为常数,这样通过增加一定的裕度使结果控制在精度允许的范围内,并可以大大地简化问题,提高控制策略和算法的实用性和可用性.:

(i);

(ii)功率控制的相关理论结果,(iii).

)转化成如下的数学问题(Ⅱ):求(Ⅰ

n={xi}∈R,a≤xi≤b,i=1,2,…,n,

使得mα(r1x1≥+r2x2+r3x3+…+rn-1xn-1+rnxn),

α(r1x1r2x2≥+r3x3+…+rn-1xn-1+rnxn),(Ⅱ)…

α(r1x1+r2x2+r3x3+…+rn-1xn-1

内容需要下载文档才能查看

)rnxn≥

)是最中有尽可能多的不等式成立,这里a,b,α,ri,i=1,2,…,n,都是大于零的常数.问题(Ⅱ

大可满足线性不等式组问题的一个特殊情形,即任意给定m组不等式

ai1xi+ai2x2+…+ainxn≥bi,i=1,2,…,m,

求x={xi}∈Rn使得有尽可能多的不等式成立.这一问题是NP2难解的(即使ai,bi只取0或者1),不过它存在一个具有近似比为2的多项式时间算法[1].在本文中我们将给出求解问题(Ⅱ)的一个简单的多项式时间算法.

3.最优解的性质

)中,r1≥r2≥…≥rn.记为叙述方便,不失一般性我们假设在问题(Ⅱ

nS(x)=rixi,X={x∈R|a≤xi≤b,i=1,2,…,n}.∑1+αi=1

α∑)的第j个不等式.显然,第j个不等式成立等价于我们称rjxj≥rx为问题(Ⅱi≠jii

rjxj≥S(x).n

)中的s个不等式,且任意x∈X最多只能满足s个不等式,　　如果x3∈X能满足问题(Ⅱ

)的最优解,s为最优值.记X3为问题(Ⅱ)的最优解的集合.那么我们称x3为问题(Ⅱ

)中的第j个不等式,那么我们有rjxj≥α∑如果有x3∈X能满足问题(Ⅱrx.由此i≠jii

可得

αrjb≥a

i≠jr.∑i(1)

136应　用　数　学2006因此,我们可以对j=1,2,…,n分别检查上面的不等式是否成立.如果都不成立,那么问题(Ⅱ)的最优值s=0.我们下面主要讨论当问题(Ⅱ)的最优值s>0时,问题(Ⅱ)的最优解的性质和如何求出最优解.

)的最优值为s>0,则存在一个最优解x3∈X3它满足前s个不等引理1　若问题(Ⅱ

式.

证　令X1={x∈X3|x满足前s个不等式}.显然,要证明引理只需证明X1不是空集.我们引入函数f∶X3→Q,如果x∈X3能满足前i个不等式,而不能满足第i+1个不等式(但是有可能满足第j>i+1个不等式),那么定义g(x)=i.

3现在取??x∈X使得g(x)达到最大值,即

g(??x)=t=max{g(x)|x∈X}.3

显然,t≤s.如果t=s,那么,??x∈X1,X1非空.下面我们用反证法证明一定有t=s.假设不然,t<s.那么,存在j>s且t+1<j使得前j,而第j+1,即rt+1??x1<,jj(??x.(2)

){xi我们定义问题(xi′=

xi,??i=j,i≠j,t+1.S(??x)/rt+1,　i=t+1,

根据不等式(2),可以得到xj≥xt+1′>??xt+1;因此有x′∈X.根据不等式(1),还可以得到rt+1xt+1′≤rj??xj.再由rt+1≥rj,可以推出rt+1??xt+1≥rjxj′.据此我们得到

(rt+1??)-(rj??)≤S(??xt+1-rjxj′xj-rt+1xt+1′x).1+α1+α

这样我们知道x′∈X使得第t+1不等式成立.同时注意到除了第j个不等式以外,??x满足的)=S(??S(x′x)-

)≥t+1;而这与??不等式x′也都满足.故x′∈X3,且g(x′x的取法相矛盾.因此t=s.证毕.

)的最优值为1≤s<n,则存在一个最优解x3={xi3}∈X3使得xi3定理1　若问题(Ⅱ

=a,i=s+1,s+2,…,n,且或者

1)存在1≤k<s,使得xi3=a,i=1,2,…,k,且rixi3=S(xi3),i=k+1,k+2,…,s,或者

2)rixi3=S(xi3),i=1,2,…,s,或者

3)xi3=a,i=1,2,…,s.

证　首先令

X2={x∈X1|xi=a,i=s+1,s+2,…,n}.

)的一个新解我们来证明X2不是空集.根据引理1知X1≠??,现任取??x∈X1.定义问题(Ⅱ

x′={xi′},其中

xi′=xi,??

a,i≤s,i>s.　

)≤S(??).故有x′∈X2.下面我显然S(x′x).因此,当i≤s时,rixi′=rixi≥S(??x)≥S(x′

们任取??x∈X2,并考虑三种不同情形.

情形(1):存在1≤k<s使得xk=a,且xi>a,i=

内容需要下载文档才能查看

k+1,k+2,…,s.令

X3≡{x∈X2|xi=a,i=1,2,…,k;xi>a,i=k+1,k+2,…,s}.

第1期尚松蒲等:移动通信系统中的最优功率控制算法137

)的一个新解x′={xi′我们来证明X3不是空集.定义问题(Ⅱ},其中

xi′=

)≤S(??显然S(x′x).因此,当i>k时,有

);rixi′=ri??xi≥S(??x)≥S(x′

xi,??a,

i>k,i≤k.

而当i≤k时,根据{ri}的单调性,有

).rixi′=ria≥rka=rk??xk≥S(??x)≥S(x′

故有x′∈X3.

再令

X4={x∈X3|x使得从第k+1个到第s个不等式等号成立}.

选取??x∈X3使得S(x)达到最小值.我们用反证法证明??x∈X4.如若不然,??xX4.那么存

)的一个在j,k<j≤s,使得第j个不等式的等号不成立,即rj??xjS(??x).(Ⅱ新解x′={xi′},其中

irxi,??

i≠j.

注意,xj(??xj)2>a.而不论xj′等于S(??x)/rj还是等于(α+??xj)/2,都可以得出xj′<

).所以x′)xj和S(????x)>S(x′∈X3,而这与??x的取法矛盾.显然,X4中的所有解都是问题(Ⅱ的最优解,且满足定理中的条件(1).

)的情形(2):xs=a.用情形(1)中证明X3不是空集的方法可以证明{xi=a}是问题(Ⅱ

一个最优解,显然它满足定理中的条件(2).

情形(3):不存在1≤k≤s使得xk=a.令X4′={x∈X2|x使得从第1个到第s个不等式等号成立}.用情形(1)中证明X4不是空集的方法可以证明X4′不是空集.显然X4′中的

)的最优解,且满足定理中的条件(3).证毕.解都是问题(Ⅱ

仿照上述定理的证明,我们可以得到下面的推论.

)的最优值s=n,则存在一个最优解x3={xi3}∈X3使得推论1　若问题(Ⅱ

1)rixi3=S(xi3),i=1,2,…,n,或者

2)存在1≤k<n,使得xi3=a,i=1,2,…,k,且rixi3=S(xi3),i=k+1,k+2,…,

4.求最优解的算法

)的最优解,我们只需找到X4中的一个元素根据定理1的证明,我们知道要找到问题(Ⅱ

即可.

对于x∈X4,我们有

rixi=S(x),i=k+1,k+2,…,s.

根据S(x)的定义,可得

(a(r1+r2+…+rk+rs+1+rs+2+…+rn)+(s-k)S(x)).S(x)=

1+α由此可得

rixi=a

内容需要下载文档才能查看

1+k

i=1

∑r

i=s+1

∑r

(s-k)1-1+α

-1

.(3)

138应　用　数　学

内容需要下载文档才能查看

2006据此,我们可以证明下面的定理.

)可以在多项式时间内求得最优解.定理2　问题(Ⅱ

证　首先我们可以判断是否存在j使得不等式(1)成立;假若没有这样的j,我们可知问)的最优值为0.排除了这种特殊的情况,我们可以根据定理1和推论1来确定问题(Ⅱ)题(Ⅱ

的最优值和最优解.

我们可以先取定s和k使得1≤k≤s≤n,并令xi=a,i=1,2,…,k,s+1,s+2,…,n.然后,根据等式(3)得出xj,j=k+1,k+2,…,s.最后,判断所得到的这个解是否满足约束条

)的一个可行解,这时可以增大s的值.再重复此过程件a≤xi≤b.若满足,便得到了问题(Ⅱ

)的一个最优解.以得到更好的可行解;否则,当前的可行解就是问题(Ⅱ

为了尽可能快地找到最大的s值(及其相应的k值),我们可以利用二分搜索方法:每一次把s的当前可能取值范围缩小一半(初始时这个范围为{1,2,…,n}),很显然用O(logn)次搜索即可确定s;对于每一个固定的s,k的选择范围为O(n),kO(n)次运算.因而整个过程可以通过O(n2logn)次运算完成.

参考文献:

[1]　offindingmaximumfeasiblesubsystemsoflinear

ComputerScience,1995,147:181～210.

[2]　WuQ.PerformanceofoptimumtransmitterpowercontrolinCDMAcellularradiosystems[J].IEEE.

TransactionsonVehicularTechnology,1999,48(2):571～575.

[3]　ZanderJ.Performanceofoptimumtransmitterpowercontrolincellularradiosystems[J].IEEE.Transac2

tionsonVehicularTechnology,1992,41(1):57～62.

[4]　ZanderJ.Distributedcochannelinterferencecontrolincellularradiosystems[J].IEEE.Transactionson

VehicularTechnology,1992,41(3):305～311.

AlgorithmforOptimalTransmitterPowerControl

inCellularRadioSystems

SHANGSong2pu,HUXiao2dong,LIXu112

(1.AcademyofMathematicsandSystemScience,ChineseAcademyofSciences,Beijing100080,China;2.ModernCommunicationInstitute,BeijingJiaotongUniversity,Beijing100044,China)

Abstract:Thispaperstudiestheproblemofoptimalpowercontroloftransmittersincel2lularradiosystems.Wefirsttransformthisproblemintoaspecialcaseoftheproblemoffind2ingasolutionsatisfyingmaximalnumberoflinearinequalities,andthenwegiveacompletedescriptionoftheoptimalsolutiontothisnewcombinatorialoptimizationproblem.Intheendwegiveapolynomialtimealgorithmforsolvingthisproblem.