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

MATHEMATICAAPPLICATA2006,19(1):13413831,1,2(1.,100080;2.,100044):.,,.:;;NP2:O221.2AMS(2000):90C30:A:100129847(2006)01201342051.,.,.,..,.,[3];[4];[2].[3],.2.,M,iLi,ij(C/I)():Rij=GijPiLik=1GkjPk-GijPi,Pii,Gkjkj,,.:1),;2),0PiPmax.(L1+L2++LM):3:2005203224:(70221001,60373012):,,,,,:.©1994-2007ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.()Ri1=Gi1PiLik=1GkjPk-GijPi,Rij=GijPiLik=1GkjPk-GijPi,RiLi=GiLiPiLik=1GkjPk-GijPi.,k=1,2,,M;i=1,2,,M.,,,,.:(i);(ii),;(iii).,()():x={xi}Rn,axib,i=1,2,,n,m()r1x1(+r2x2+r3x3++rn-1xn-1+rnxn),r2x2(r1x1+r3x3++rn-1xn-1+rnxn),rnxn(r1x1+r2x2+r3x3++rn-1xn-1),a,b,,ri,i=1,2,,n,.(),mai1xi+ai2x2++ainxnbi,i=1,2,,m,x={xi}Rn.NP2(ai,bi01),2[1].().3.,(),r1r2rn.S(x)=1+ni=1rixi,X={xRn|axib,i=1,2,,n}.rjxjijrixi()j.,jrjxjS(x).x3X()s,xXs,x3(),s.X3().x3X()j,rjxjijrixi.rjbaijri.(1)5311:©1994-2007ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.=1,2,,n.,()s=0.()s0,().1()s0,x3X3s.X1={xX3|xs}.,X1.fX3Q,xX3i,i+1(ji+1),g(x)=i.ŠxX3g(x),g(Šx)=t=max{g(x)|xX3}.,ts.t=s,,ŠxX1,X1.t=s.,ts.,jst+1jj,j+1,rt+1Šxt+1S(Šx),rjŠxjS(Šx).(2)()x={xi},xi=a,S(Šx)/rt+1,Šxi,i=j,i=t+1,ij,t+1.(2),xjxt+1Šxt+1;xX.(1),rt+1xt+1rjŠxj.rt+1rj,rt+1Šxt+1rjxj.S(x)=S(Šx)-1+(rt+1Šxt+1-rjxj)-1+(rjŠxj-rt+1xt+1)S(Šx).xXt+1.j,Šxx.xX3,g(x)t+1;Šx.t=s..1()1sn,x3={x3i}X3x3i=a,i=s+1,s+2,,n,1)1ks,x3i=a,i=1,2,,k,rix3i=S(x3i),i=k+1,k+2,,s,2)rix3i=S(x3i),i=1,2,,s,3)x3i=a,i=1,2,,s.X2={xX1|xi=a,i=s+1,s+2,,n}.X2.1X1ª,ŠxX1.()x={xi},xi=Šxi,a,is,is.S(x)S(Šx).,is,rixi=rixiS(Šx)S(x).xX2.ŠxX2,.(1):1ksxk=a,xia,i=k+1,k+2,,s.X3{xX2|xi=a,i=1,2,,k;xia,i=k+1,k+2,,s}.6312006©1994-2007ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.()x={xi},xi=Šxi,a,ik,ik.S(x)S(Šx).,ik,rixi=riŠxiS(Šx)S(x);ik,{ri},rixi=riarka=rkŠxkS(Šx)S(x).xX3.X4={xX3|xk+1s}.ŠxX3S(x).ŠxX4.,Šx|X4.j,kjs,j,rjŠxjS(Šx).()x={xi},xi=maxS(Šx)rj,+Šxj2,Šxi,i=j,ij.,xj(+Šxj)/2a.xjS(Šx)/rj(+Šxj)/2,xjŠxjS(Šx)S(x).xX3,Šx.,X4(),(1).(2):xs=a.(1)X3{xi=a}(),(2).(3):1ksxk=a.X4={xX2|x1s}.(1)X4X4.X4(),(3)..,.1()s=n,x3={x3i}X31)rix3i=S(x3i),i=1,2,,n,2)1kn,x3i=a,i=1,2,,k,rix3i=S(x3i),i=k+1,k+2,,n.4.1,(),X4.xX4,rixi=S(x),i=k+1,k+2,,s.S(x),S(x)=1+(a(r1+r2++rk+rs+1+rs+2++rn)+(s-k)S(x)).rixi=a1+ki=1ri+ni=s+1ri1-1+(s-k)-1.(3)7311:©1994-2007ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.().j(1);j,()0.,11().sk1ksn,xi=a,i=1,2,,k,s+1,s+2,,n.,(3)xj,j=k+1,k+2,,s.,axib.,(),s.;,().s(k),:s({1,2,,n}),O(logn)s;s,kO(n),kO(n).O(n2logn).:[1]AmaldiE,KannV.Thecomplexityandapproximabilityoffindingmaximumfeasiblesubsystemsoflinearrelations[J].TheoreticalComputerScience,1995,147:181210.[2]WuQ.PerformanceofoptimumtransmitterpowercontrolinCDMAcellularradiosystems[J].IEEE.TransactionsonVehicularTechnology,1999,48(2):571575.[3]ZanderJ.Performanceofoptimumtransmitterpowercontrolincellularradiosystems[J].IEEE.Transac2tionsonVehicularTechnology,1992,41(1):5762.[4]ZanderJ.Distributedcochannelinterferencecontrolincellularradiosystems[J].IEEE.TransactionsonVehicularTechnology,1992,41(3):305311.AlgorithmforOptimalTransmitterPowerControlinCellularRadioSystemsSHANGSong2pu1,HUXiao2dong1,LIXu2(1.AcademyofMathematicsandSystemScience,ChineseAcademyofSciences,Beijing100080,China;2.ModernCommunicationInstitute,BeijingJiaotongUniversity,Beijing100044,China)Abstract:Thispaperstudiestheproblemofoptimalpowercontroloftransmittersincel2lularradiosystems.Wefirsttransformthisproblemintoaspecialcaseoftheproblemoffind2ingasolutionsatisfyingmaximalnumberoflinearinequalities,andthenwegiveacompletedescriptionoftheoptimalsolutiontothisnewcombinatorialoptimizationproblem.Intheendwegiveapolynomialtimealgorithmforsolvingthisproblem.Keywords:Transmitterpowercontrol;Polynomial2timealgorithm;NP2hardproblems8312006©1994-2007ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.