優(yōu)化解決移動通信中的信道分配問題

優(yōu)化解決移動通信中的信道分配問題

摘要由于可用的移動通信的頻帶寬度是有限的，優(yōu)化信道分配的問題變的越來越重要。通過優(yōu)化可以大大提高系統(tǒng)容量，并且減少通信間的干擾，從而改善了通信質(zhì)量，提高客戶的滿意度。在本論文中，我們通過基因算法(GA)，在信道數(shù)量有限的條件下，解決移動通信網(wǎng)絡(luò)中的頻率分配問題。信道分配問題是個很復(fù)雜的優(yōu)化問題。模擬結(jié)果表明基因算法(GA)可以進(jìn)一步提高由其它算法獲得的結(jié)果。關(guān)鍵詞基因算法，信道分配，信道干擾1．介紹在移動通信中，提供給用戶和無線網(wǎng)絡(luò)基站之間通信的頻帶寬度是有限的。因此，隨著手機(jī)用戶的普及，這個有限的資源成為移動通信系統(tǒng)發(fā)展的瓶頸。為滿足信噪比要求，本文從以下三種基本的干擾：同信道干擾，同區(qū)域干擾，鄰道干擾考慮來設(shè)計(jì)網(wǎng)絡(luò)。無線頻率傳播和預(yù)期的通信量作為某些信道分配給某個區(qū)域時是否會產(chǎn)生干擾的決定因素。通信量也可以用來預(yù)測每個區(qū)域內(nèi)所需要的信道數(shù)目。信道分配問題可以分為兩類。第一類：在滿足整個系統(tǒng)無干擾的情況下，最小化所需的信道數(shù)，以節(jié)約有效的頻率資源。這就是參考[1]中提到的信道分配問題1(CAP1).第二類：在大多數(shù)實(shí)際應(yīng)用中，無法提供足夠可用的信道確保無干擾的信道分配，只能最小化整個系統(tǒng)內(nèi)的干擾，滿足各區(qū)域?qū)π诺罃?shù)量上的需求。這就是參考[1]中提到的信道分配問題2(CAP2)。近幾年來，一些啟發(fā)式算法(,,)等多種算法被用來解決信道分配問題。但由于算法的一些局限，往往結(jié)果并不理想?；蛩惴℅A的本質(zhì)：全局性概率搜索算法,是可行的搜索技術(shù)，用定長的線性串對問題的解進(jìn)行編碼，通過復(fù)制、交叉和變異等遺傳操作改變個體的結(jié)構(gòu)。個體作為搜索對象。根據(jù)適應(yīng)度進(jìn)行選擇，決定個體是否參加復(fù)制、交叉等遺傳操作，得到的返回值后，代入適應(yīng)度函數(shù)求出子染色體樹的適應(yīng)度(適應(yīng)度：表示了個體產(chǎn)生的效益，是個體優(yōu)秀程度的度量)。取適應(yīng)度最大的作為最優(yōu)子個體。已經(jīng)有大量的例子使用基因算法GA來解決信道分配問題.例如,參考文獻(xiàn)[12],[19],[20],[21],[22]使用基因算法來解決信道分配問題1(CAP1)。[23]和[24]用公式描述了CAP2,但是它們只對無干擾的情況感興趣。參考文獻(xiàn)[16]中依據(jù)基因算法給出了解決信道分配問題2的獨(dú)特的公式，在本論文中，就依據(jù)這個公式，將無干擾條件作為軟限制條件(Softconstraint)，而將各個小區(qū)所需要的信道數(shù)作為硬限制條件。我們用十個基準(zhǔn)問題來進(jìn)行模擬仿真，并將結(jié)果與其它算法獲取的結(jié)果相比較。2．信道分配問題假設(shè)一個無線通信網(wǎng)絡(luò)，它有N個小區(qū)和M個通信信道。小區(qū)i的信道需求為Di個信道。電磁波的傳播方式可以決定在頻域中兩個信道之間能保證沒有干擾的最小距離。這些最小的距離存儲在的對稱矩陣C中。我們回顧一下Smith和Palaniswami提出CAP2的數(shù)學(xué)模型：其中;.如果,就是說小區(qū)j和i分別分配到信道k和信道l。分配所引起的干擾程度可以由張量中的一個元素進(jìn)行計(jì)算，其中是信道k和信道l在頻域中的絕對距離。當(dāng)時，干擾的程度最大。干擾隨著兩信道間距的增大而減小。減小整個網(wǎng)絡(luò)中的干擾程度的問題就可簡化，即：最小化：(1)限制條件：(2)(3)上述提到鄰近因子張量P是一個三維矩陣。立方體正前平面對角線被置0的矩陣C。張量的第三向線成線性減少，因此張量的有效深度為矩陣C的最大對角線值，它由遞歸方法生成：(4)3仿真結(jié)果在我們的仿真試驗(yàn)中，采用了參考文獻(xiàn)[16]推薦的方法，初始化一組滿足限制條件的個體。每個個體是一個的矩陣的解。每一行代表一個小區(qū)內(nèi)的分配方案。每一行內(nèi)的1的數(shù)量代表了分配給該小區(qū)的信道數(shù)目。根據(jù)前面介紹的基因算法，進(jìn)行行間交叉，行內(nèi)變異的算法。這樣，每次生成的新解都可滿足限制條件。我們用等式(1)來評估每個個體的適應(yīng)度，并根據(jù)適應(yīng)度來選擇用于生成下一個族群的個體。問題族群大小交叉可能性變異可能性表1用于基因算法仿真中的參數(shù)我們用在參考文獻(xiàn)中的實(shí)驗(yàn)問題來檢測基因算法的效果.用于試驗(yàn)的問題可以分為三類.第一類包括問題EX1和EX2，分別有4和5個信道.第二類問題(HEX1—HEX4)是基于由21個正六邊形小區(qū)構(gòu)成的網(wǎng)絡(luò)。最后一類問題(KUNZ1---KUNZ4)是引用KUNZ在中使用的一個臨近芬蘭首都赫爾辛基的覆蓋面積為24*21平方千米的網(wǎng)絡(luò)。在下表中，我們用基因算法獲得的結(jié)果和其它一些傳統(tǒng)算法獲得的結(jié)果進(jìn)行比較。這些算法包括：綜合代數(shù)模型系統(tǒng)(GeneralAlgebraicModelingSystem(GAMS),傳統(tǒng)的最速下降算法(steepestdescent(SD)),隨機(jī)模擬退火算法(stochasticsimulatedannealing(SSA)),原始的Hopfield神經(jīng)網(wǎng)絡(luò)(theoriginalHopfieldnetwork(HN)(withouthill-climbing),帶爬坡的Hopfield神經(jīng)網(wǎng)絡(luò)算法(thehill-climbingHopfieldnetwork(HCHN)),自組神經(jīng)網(wǎng)絡(luò)算法(theself-organizingneuralnetwork(SONN)),和隨機(jī)無秩序模擬退火算法(stochasticchaoticsimulatedannealing(SCSA)).上述算法獲得的最小價(jià)值和均值(Av)是運(yùn)行10次的計(jì)算結(jié)果，為便于比較，本文的統(tǒng)計(jì)結(jié)果同樣做了10次實(shí)驗(yàn)仿真后所得。方法GAGAMSSDssahnhcnnsonn問題MinAvMinMinAvMinAvMinAvMinAv結(jié)論和討論基站號BaseStationNo.信道數(shù)Channels信道分配Assignmentchannels1105,7,9,11,13,19,21,25,27,292112,5,7,11,15,17,19,21,23,27,29391,3,6,9,16,20,25,28,30457,11,19,27,29594,8,10,12,14,18,22,24,26645,19,21,29758,10,12,22,24874,8,10,14,18,22,26942,15,17,231081,3,6,13,16,20,28,30

表的信道道分配.最小干擾值為19基站號信道數(shù)信道分配1220,832611,22,30,35,43,743237,59426,165226,87646,18,51,757416,29,53,7981335,9,25,33,38,45,50,55,58,65,69,72,879193,7,15,18,24,27,41,49,52,57,61,63,66,70,78,81,84,89,9010712,20,29,32,46,73,7611438,69,80,9112424,44,51,8213712,20,30,47,60,69,8014414,32,35,4315919,23,26,40,62,67,77,82,8516141,13,17,21,28,31,36,42,47,60,64,75,80,9117717,34,39,44,54,68,861824,1419258,7920410,19,27,3521213,29

表的信道分配.最小干擾值為17表3和4列出了由基因算法產(chǎn)生的實(shí)際的的兩個問題的信道分配方案.KUNZ1，HEX2的結(jié)論中:結(jié)果”0”代表無干擾分配。我們可以看出對于HEX2和KUNZ1我們獲得了比其帶爬坡的Hopfield神經(jīng)網(wǎng)絡(luò)算法(thehill-climbingHopfieldnetwork(HCHN))中更好的數(shù)據(jù).在仿真過程中,一些參數(shù),例如交叉操作機(jī)率,變異操作機(jī)率和族群大小都需要去設(shè)定.我們是通過反復(fù)試驗(yàn)來設(shè)定這些參數(shù)的.到目前為止，許多研究者已經(jīng)研究了在保證無干擾情況下最小化所需信道數(shù)的問題。而本論文則是針對那些實(shí)際可用信道數(shù)少于無干擾所需信道數(shù)的實(shí)際問題，研究在有限的信道的條件下來最小化生成干擾的的可行性方案,這將會很有實(shí)際應(yīng)用價(jià)值.基因算法是一個有趣的方法，它是從點(diǎn)到點(diǎn)的全局搜索,在解決優(yōu)化組和問題時，可快速獲取更優(yōu)的解?；鶞?zhǔn)問題的仿真結(jié)果表明基因算法可得到比其它方法更理想的結(jié)果,即在滿足需求限制的條件下，使得信道分配帶來更少的干擾的解決方案.更高級的基因算法諸如并行基因算法(parallelGA)和微基因算法(microGA)可以在短時間內(nèi)解決信道分配問題2,得到更好的結(jié)果.基因算法(GA)特別適合于在高速并行計(jì)算機(jī)上運(yùn)算.目標(biāo)函數(shù)和限制條件可同時執(zhí)行,對整個族群操作運(yùn)算,通過交叉和變異操作生成選取新一代適應(yīng)度更高的子族群參數(shù)。因此對硬件性能要求高，直接關(guān)系到運(yùn)行時間長短,效率問題.在一臺高速并行機(jī)上，基因算法預(yù)計(jì)能以幾K倍的速度處理很多問題，K是入口尺寸大小。即使要并行的評估的個別問題功能有效性,也可在最短時間內(nèi)獲得最佳解決辦法。REFERENCES參考文獻(xiàn)1K.Smith,“Solvingcombinatorialoptimizationproblemsusingneuralnetworks,”dimerfation,UniversityofMelboume,Australi41996.2D.Kunz,‘‘SuboptidsolutibniobtainedbytheHopfield-Tankneuralnetworkalgorithm”,BiologicnlCybernetics,,pp.l29-133,1991.3F.BOX,~‘‘Aheuristictechniqueforissigningfrequenciestomobile:radionets,”IEEETrans.Veh.Techno/.,vol.VT-27,,pp..57-64,1978.-~4M.:Duque&to&D.KunzandB.Ruber,“Staticanddynamicchannelassignmentusingsimulatedannealing,”NeuralNehvorkrinTelecommunications.B.YuhasandN.&sari,E&.Boston,MA:Kluwer,1994.5M.Sengokq“Telephonetrafficinamobileradiocomunicationsystemusingdynamicfrequencyassignments,’’IEEETrans.Veh.Technol..,no.2,pp.270-278,1980.6A.Camst,“Homogeneousdistributionoffrequenciesinaregularhexagonalcellsystem,”IEEETrans.Veh.Technol.,vol.31.no.3,pp.132-144,1982.7A.Gamst,“Somelowerboundsforaclassoffrequencyassignmentproblems,’’IEEETrans.Veh.Technol.,,,pp.8-14,1986.8K.SmithandM.Palaniswami,“StaticindDynamicChannelAssignmentusingNeuralNetworks”,IEEEJoumlonSelectedAreasinCommunications,vol.15,no.2,pp.238-249,1997.9E.Falkenauer,Geneticalgorithmsandgrouping,England:Wiley,1998.10R.Matbarand1.Mattfeldt,”Channelassignmentincellularradionetworks”,IEEETrans.Veh.Technoi.,,,Feb1993.11.S.H.Park,P.W.Dowd,andN.M.Nasrabadi,“Channelassignmentincellularradiousinggeneticalgorithm”,WirelessPersona:Commun,,,,12D.BeckmannandU.Killat,“Anewstrategyfortheapplicationofgeneticalgorithmstothechannelassignmentproblem”,IEEETrans.,vol.48,no.4,,July,1999.13E.DavidGoldberg,Geneticalgorithmsin,andmachinelearning.Reading,Mass.:Addison-WesleyPub.Co.,1989.14K.Deb,“Multi-objectiveOptimizationUsingEvolutionaryAlgorithms”,JohnWiley&Sons,2001.15LawrenceDavis,HandbookofGeneticAlgorithms.NewYorkVanNosbandReinhold,1991.16K.A.Smith,“Ageneticalgorithmforthechannelassignmentproblem.”IEEEGlobalTechnohaConference,vol.4,1998.17DonaldE.Knuth,TheArtofcomputerprogramming:FundnmentalAlgorithms.nirdEdition.Reading,Mass:Addison-WelseyPub.Co.,1997I8T.Kohonen,“Self-organizedformationoftopologicallycorrectfeaturemaps,”,vol.43,pp.59-69,1982.19A.ThavarajahandLam,“Heuristicapproachforoptimalchannelassignmentincellularmobilesystems,”IEEProceedingsCommunications,vol.1463,pp.196-200,June,1999.20G.ChahbortyandB.ChaLborty,“Ageneticalgorithmapproachtosolvechannelassignmentproblem~incellularradionetworks,”Proc.I999IEEEMidnight-SunWorkshoponS