- 相關(guān)推薦
優(yōu)化解決移動(dòng)通信中的信道分配問(wèn)題
摘要 由于可用的移動(dòng)通信的頻帶寬度是有限的，優(yōu)化信道分配的問(wèn)題變的越來(lái)越重要。通過(guò)優(yōu)化可以大大提高系統容量，并且減少通信間的干擾，從而改善了通信質(zhì)量，提高客戶(hù)的滿(mǎn)意度。在本論文中，我們通過(guò)基因算法(GA)，在信道數量有限的條件下，解決移動(dòng)通信網(wǎng)絡(luò )中的頻率分配問(wèn)題。信道分配問(wèn)題是個(gè)很復雜的優(yōu)化問(wèn)題。模擬結果表明基因算法(GA)可以進(jìn)一步提高由其它算法獲得的結果。 關(guān)鍵詞 基因算法，信道分配，信道干擾 1．介紹 在移動(dòng)通信中，提供給用戶(hù)和無(wú)線(xiàn)網(wǎng)絡(luò )基站之間通信的頻帶寬度是有限的。因此，隨著(zhù)手機用戶(hù)的普及，這個(gè)有限的資源成為移動(dòng)通信系統發(fā)展的瓶頸。為滿(mǎn)足信噪比要求，本文從以下三種基本的干擾：同信道干擾，同區域干擾，鄰道干擾考慮來(lái)設計網(wǎng)絡(luò )。 無(wú)線(xiàn)頻率傳播和預期的通信量作為某些信道分配給某個(gè)區域時(shí)是否會(huì )產(chǎn)生干擾的決定因素。通信量也可以用來(lái)預測每個(gè)區域內所需要的信道數目。信道分配問(wèn)題可以分為兩類(lèi)。第一類(lèi)：在滿(mǎn)足整個(gè)系統無(wú)干擾的情況下，最小化所需的信道數，以節約有效的頻率資源。這就是參考[1]中提到的信道分配問(wèn)題1(CAP1).第二類(lèi)：在大多數實(shí)際應用中，無(wú)法提供足夠可用的信道確保無(wú)干擾的信道分配，只能最小化整個(gè)系統內的干擾，滿(mǎn)足各區域對信道數量上的需求。這就是參考[1]中提到的信道分配問(wèn)題2 (CAP2)。近幾年來(lái)，一些啟發(fā)式算法（Heuristic Approach）([2],[3],[4])等多種算法被用來(lái)解決信道分配問(wèn)題。但由于算法的一些局限，往往結果并不理想�；蛩惴℅A的本質(zhì)：全局性概率搜索算法,是可行的搜索技術(shù)，用定長(cháng)的線(xiàn)性串對問(wèn)題的解進(jìn)行編碼，通過(guò)復制、交叉和變異等遺傳操作改變個(gè)體的結構。個(gè)體作為搜索對象。根據適應度進(jìn)行選擇，決定個(gè)體是否參加復制、交叉等遺傳操作，得到的返回值后，代入適應度函數求出子染色體樹(shù)的適應度(適應度：表示了個(gè)體產(chǎn)生的效益，是個(gè)體優(yōu)秀程度的度量)。取適應度最大的作為最優(yōu)子個(gè)體。 已經(jīng)有大量的例子使用基因算法GA來(lái)解決信道分配問(wèn)題.例如, 參考文獻 [12], [19], [20], [21], [22] 使用基因算法來(lái)解決信道分配問(wèn)題1 (CAP1)。[23] 和 [24] 用公式描述了CAP2, 但是它們只對無(wú)干擾的情況感興趣。參考文獻[16]中依據基因算法給出了解決信道分配問(wèn)題2的獨特的公式，在本論文中，就依據這個(gè)公式，將無(wú)干擾條件作為軟限制條件(Soft constraint) ，而將各個(gè)小區所需要的信道數作為硬限制條件。我們用十個(gè)基準（benchmark）問(wèn)題來(lái)進(jìn)行模擬仿真，并將結果與其它算法獲取的結果相比較。 2．信道分配問(wèn)題 假設一個(gè)無(wú)線(xiàn)通信網(wǎng)絡(luò )，它有N個(gè)小區和M個(gè)通信信道。小區i的信道需求（由預期的通信量求出）為Di個(gè)信道。電磁波的傳播方式可以決定在頻域中兩個(gè)信道之間能保證沒(méi)有干擾的最小距離。這些最小的距離存儲在 的對稱(chēng)矩陣C中。我們回顧一下Smith 和Palaniswami[4]提出CAP2的數學(xué)模型： 其中 ; . 如果 ,就是說(shuō)小區j和i分別分配到信道k 和信道l。分配所引起的干擾程度可以由張量 中的一個(gè)元素進(jìn)行計算，其中 是信道k和信道l在頻域中的絕對距離。當 時(shí)，干擾的程度最大。干擾隨著(zhù)兩信道間距的增大而減小。減小整個(gè)網(wǎng)絡(luò )中的干擾程度的問(wèn)題就可簡(jiǎn)化，即：最小化： (1)限制條件： (2) (3) 上述提到鄰近因子張量P是一個(gè)三維矩陣。立方體正前平面對角線(xiàn)被置0的矩陣C。張量的第三向線(xiàn)成線(xiàn)性減少，因此張量的有效深度為矩陣C的最大對角線(xiàn)值，它由遞歸方法生成： (4) 3 仿真結果 在我們的仿真試驗中，采用了參考文獻[16]推薦的方法，初始化一組滿(mǎn)足限制條件的個(gè)體。每個(gè)個(gè)體是一個(gè)的矩陣的解。每一行代表一個(gè)小區內的分配方案。每一行內的1的數量代表了分配給該小區的信道數目。根據前面介紹的基因算法，進(jìn)行行間交叉，行內變異的算法。這樣，每次生成的新解都可滿(mǎn)足限制條件。我們用等式(1)來(lái)評估每個(gè)個(gè)體的適應度，并根據適應度來(lái)選擇用于生成下一個(gè)族群的個(gè)體。 問(wèn)題 族群大小 交叉可能性 變異可能性EX1 40 0.75 0.3 EX2 60 0.85 0.2 HEX1 100 0.7 0.4 HEX2 120 0.65 0.35 HEX3 140 0.8 0.4 HEX4 140 0.85 0.35 KUNZ1 80 0.75 0.25 KUNZ2 120 0.7 0.2 KUNZ3 120 0.8 0.3 KUNZ4 140 0.7 0.35 表1 用于基因算法仿真中的參數 我們用在參考文獻[8]中的實(shí)驗問(wèn)題來(lái)檢測基因算法的效果.用于試驗的問(wèn)題可以分為三類(lèi).第一類(lèi)包括問(wèn)題EX1和EX2，分別有4和5個(gè)信道.第二類(lèi)問(wèn)題 (HEX1—HEX4)是基于由21個(gè)正六邊形小區構成的網(wǎng)絡(luò )。最后一類(lèi)問(wèn)題(KUNZ1---KUNZ4)是引用KUNZ在[8]中使用的一個(gè)臨近芬蘭首都赫爾辛基的覆蓋面積為24*21平方千米的網(wǎng)絡(luò )。在下表中，我們用基因算法獲得的結果和其它一些傳統算法獲得的結果進(jìn)行比較。這些算法包括：綜合代數模型系統(General Algebraic Modeling System (GAMS), 傳統的最速下降算法(steepest descent (SD) ), 隨機模擬退火算法(stochastic simulated annealing (SSA) ),原始的Hopfield神經(jīng)網(wǎng)絡(luò )(the original Hopfield network (HN)(without hill-climbing), 帶爬坡的Hopfield神經(jīng)網(wǎng)絡(luò )算法(the hill-climbing Hopfield network (HCHN) ), 自組神經(jīng)網(wǎng)絡(luò )算法( the self-organizing neural network (SONN)),和隨機無(wú)秩序模擬退火算法(stochastic chaotic simulated annealing (SCSA) ). 上述算法獲得的最小價(jià)值（Min）和均值(Av)是運行10次的計算結果，為便于比較，本文的統計結果同樣做了10次實(shí)驗仿真后所得。 方法 GA GAMS SD ssa hn hcnn sonn 問(wèn)題 Min Av Min Min Av Min Av Min Av Min Av Av Min EX1 0 0 2 0 0.6 0 0 0 0.2 0 0.0 0 0.4 EX2 0 0 3 0 1.1 0 0.1 0 1.8 0 0.8 0 2.4 HEX1 46 47.7 54 55 56.8 49 50.7 48 49.0 48 48.7 52 53.0 HEX2 17 18.4 27 25 28.9 19 20.4 19 21.2 19 19.8 24 28.5 HEX3 76 76.5 89 84 88.6 79 82.9 79 81.6 78 80.3 84 87.2 HEX4 16 17.5 31 26 28.2 17 20.1 20 21.6 27 18.9 22 29.1 KUNZ1 19 19.8 28 22 24.4 21 21.6 21 22.1 20 21.1 21 22.0 KUNZ2 29 29.4 39 26 28.1 32 33.2 32 32.8 30 31.5 33 33.4 KUNZ3 13 13 13 15 17.9 13 13.9 13 13.2 13 13.0 14 14.4 KUNZ4 0 7 3 5.5 1 1.8 1 0.4 0 0.1 1 2.2 4.結論和討論 基站號Base Station No. 信道數Channels 信道分配Assignment channels 1 10 5, 7,9,11,13,19,21,25,27,29 2 11 2,5,7,11,15,17,19,21,23,27,29 3 9 1, 3,6,9,16,20,25,28,30 4 5 7, 11,19,27,29 5 9 4,8,10,12,14,18,22,24,26 6 4 5,19,21,29 7 5 8, 10,12,22,24 8 7 4, 8, 10, 14,18,22,26 9 4 2,15,17,23 10 8 1,3,6,13,16,20,28,30 表3.KUNZ1的信道道分配.最小干擾值為19 基站號 信道數 信道分配 1 2 20, 83 2 6 11, 22, 30,35,43,74 3 2 37, 59 4 2 6, 16 5 2 26, 87 6 4 6,18,51,75 7 4 16,29,53,79 8 13 3 5,9,25,33,38,45,50,55,58,65,69,72,87 9 19 3,7,15,18,24,27,41,49,52,57,61,63,66,70,78,81,84,89,90 10 7 12,20,29,32,46,73,76 11 4 38,69,80,91 12 4 24,44,51,82 13 7 12,20,30,47,60,69,80 14 4 14,32,35,43 15 9 19, 23, 26,40,62,67,77,82,85 16 14 1,13,17,21,28,31,36,42,47,60,64,75,80,91 17 7 17,34,39,44,54,68,86 18 2 4, 14 19 2 58,79 20 4 10, 19, 27, 35 21 2 13, 29
表4.HEX2的信道分配.最小干擾值為17
表3和4列出了由基因算法產(chǎn)生的實(shí)際的的兩個(gè)問(wèn)題的信道分配方案.KUNZ1，HEX2的結論中:結果”0”代表無(wú)干擾分配。我們可以看出對于HEX2和KUNZ1我們獲得了比其帶爬坡的Hopfield神經(jīng)網(wǎng)絡(luò )算法(the hill-climbing Hopfield network (HCHN) )[8]中更好的數據. 在仿真過(guò)程中,一些參數,例如交叉操作機率,變異操作機率和族群大小都需要去設定.我們是通過(guò)反復試驗來(lái)設定這些參數的.到目前為止，許多研究者已經(jīng)研究了在保證無(wú)干擾情況下最小化所需信道數的問(wèn)題。而本論文則是針對那些實(shí)際可用信道數少于無(wú)干擾所需信道數的實(shí)際問(wèn)題，研究在有限的信道的條件下來(lái)最小化生成干擾的的可行性方案,這將會(huì )很有實(shí)際應用價(jià)值. 基因算法是一個(gè)有趣的方法，它是從點(diǎn)到點(diǎn)的全局搜索,在解決優(yōu)化組和問(wèn)題時(shí)，可快速獲取更優(yōu)的解�；鶞蕟�(wèn)題的仿真結果表明基因算法可得到比其它方法更理想的結果,即在滿(mǎn)足需求限制的條件下，使得信道分配帶來(lái)更少的干擾的解決方案. 更高級的基因算法諸如并行基因算法(parallel GA)和微基因算法(micro GA)可以在短時(shí)間內解決信道分配問(wèn)題2,得到更好的結果. 基因算法(GA)特別適合于在高速并行計算機上運算.目標函數和限制條件可同時(shí)執行,對整個(gè)族群操作運算,通過(guò)交叉和變異操作生成選取新一代適應度更高的子族群參數。 因此對硬件性能要求高，直接關(guān)系到運行時(shí)間長(cháng)短,效率問(wèn)題.在一臺高速并行機上， 基因算法預計能以幾K倍的速度處理很多問(wèn)題，K是入口尺寸大小。即使要并行的評估的個(gè)別問(wèn)題功能有效性,也可在最短時(shí)間內獲得最佳解決辦法。REFERENCES 參考文獻 1 K. Smith, “Solving combinatorial optimization problems using neural networks,” Ph.D. dimerfation, University of Melboume, Australi4 1996. 2 D. Kunz, ‘‘Suboptid solutibni obtained by the Hopfield-Tank neural network algorithm”, Biologicnl Cybernetics, vol.65, pp. l29-133,1991. 3 F. BOX,~‘‘A heuristic technique for issigning frequencies to mobile:radio nets,” IEEE Trans. Veh. Techno/., vol. VT-27,no.2,pp..57-64,1978. - ~ 4 M.:Duque&to& D. Kunz and B. Ruber, “Static and dynamic channel assignment using simulated annealing,”Neural Nehvorkr in Telecommunications. B. Yuhas and N.&sari, E&. Boston, MA:Kluwer, 1994. 5 M. Sengokq “ Telephone traffic in a mobile radio comunication system using dynamic frequency assignments,’’IEEE Trans. Veh. Technol.. vo1.29, no. 2, pp. 270-278,1980. 6 A. Camst, “Homogeneous distribution of frequencies in a regular hexagonal cell system,” IEEE Trans. Veh. Technol.,vol. 31. no. 3,pp. 132-144,1982. 7 A. Gamst, “Some lower bounds for a class of frequency assignment problems,’’ IEEE Trans. Veh. Technol., vo1.35, no.I ,pp. 8- 14,1986. 8 K. Smith and M. Palaniswami, “Static ind Dynamic Channel Assignment using Neural Networks”, IEEE Jouml on Selected Areas in Communications, vol. 15, no. 2,pp. 238-249,1997. 9 E. Falkenauer, Genetic algorithms and grouping problems.Chichester, England: Wiley, 1998. 10 R. Matbar and 1. Mattfeldt, ” Channel assignment in cellular radio networks”, IEEE Trans. Veh. Technoi., Vo1.42,pp.1421, Feb 1993. 11 .S.Kitq S. H. Park, P. W. Dowd, and N. M. Nasrabadi,“Channel assignment in cellular radio using genetic algorithm”, Wireless Persona: Commun, vo1.3, 110.3, pp.273-286, Aug.1996. 12 D. Beckmann and U. Killat, “A new strategy for the application of genetic algorithms to the channel assignment problem”, IEEE Trans. Veh.Technol., vol. 48, no. 4, pp.1261-1269, July, 1999. 13 E. David Goldberg, Genetic algorithms in search.optimization, and machine learning. Reading, Mass.: Addison-Wesley Pub. Co., 1989. 14 K. Deb, “Multi-objective Optimization Using Evolutionary Algorithms”, John Wiley & Sons, 2001. 15 Lawrence Davis, Handbook of Genetic Algorithms. New York VanNosbandReinhold, 1991. 16 K. A. Smith, “A genetic algorithm for the channel assignment problem.” IEEE Global Technoha Conference,vol. 4, 1998. 17 Donald E. Knuth, The Art of computer programming: Fundnmental Algorithms. n i r d Edition. Reading, Mass: Addison-Welsey Pub. Co., 1997 I8 T. Kohonen, “Self-organized formation of topologically correct feature maps, ”Biol.Cybern., vol. 43, pp. 59-69, 1982. 19 A. Thavarajah and W.H. Lam, “Heuristic approach for optimal channel assignment in cellular mobile systems,” IEE Proceedings Communications, vol. 146 3,pp. 196-200, June, 1999. 20 G. Chahborty and B. ChaLborty, “A genetic algorithm approach to solve channel assignment problem ~in cellular radio networks,” Proc. I999 IEEE Midnight-Sun Workshop on Soft Computing Methods in Industrial Applications, pp.3439, 1999. 21 M. Williams, “Making the best use of the airways:an important requirement for militaty communications,”Electronics & Communication Engineering Joumal.v01.12, no.2, pp.75-83, April, 2000. 22 F.J. Jaimes-Romero, D. Munoz-Rodriguez, and S.Tekinay, “Channel assignment in cellular systems using genetic algorithms,” IEEE 46th Vehicular Technology Conference, vol. 2, pp.741 -745, 1996. 23 W. K. Lai and G. G. Coghill, “Channel assignment through evolutionary optimization,” IEEE Transactions on Vehicular Technology, vo1.45, no.1, pp.91 -96, Feb.,1996. 24 C.Y. Ngo and V.0.K Li, “Fixed channel assignment in cellular radio networks using a modifiedgenetic algorithm,” IEEE Trans. Vehicular Technology,vol. 47, no. 1, pp. 163-172, Feb., 1998.【優(yōu)化解決移動(dòng)通信中的信道分配問(wèn)題】相關(guān)文章：
基于DSP的信道譯碼算法優(yōu)化03-19
談直放站在移動(dòng)通信中的應用03-18
淺談直放站在移動(dòng)通信中的應用03-04
一種移動(dòng)通信信道模擬器的設計與實(shí)現03-18
管理的核心是解決人的問(wèn)題03-18