優化解決移動通信中的信道分配問題

摘要  由于可用的移動通信的頻帶寬度是有限的，優化信道分配的問題變的越來越重要。通過優化可以大大提高系統容量，并且減少通信間的干擾，從而改善了通信質量，提高客戶的滿意度。在本論文中，我們通過基因算法(GA)，在信道數量有限的條件下，解決移動通信網絡中的頻率分配問題。信道分配問題是個很復雜的優化問題。模擬結果表明基因算法(GA)可以進一步提高由其它算法獲得的結果。    關鍵詞  基因算法，信道分配，信道干擾 1．介紹    在移動通信中，提供給用戶和無線網絡基站之間通信的頻帶寬度是有限的。因此，隨著手機用戶的普及，這個有限的資源成為移動通信系統發展的瓶頸。為滿足信噪比要求，本文從以下三種基本的干擾：同信道干擾，同區域干擾，鄰道干擾考慮來設計網絡。    無線頻率傳播和預期的通信量作為某些信道分配給某個區域時是否會產生干擾的決定因素。通信量也可以用來預測每個區域內所需要的信道數目。信道分配問題可以分為兩類。第一類：在滿足整個系統無干擾的情況下，最小化所需的信道數，以節約有效的頻率資源。這就是參考[1]中提到的信道分配問題1(CAP1).第二類：在大多數實際應用中，無法提供足夠可用的信道確保無干擾的信道分配，只能最小化整個系統內的干擾，滿足各區域對信道數量上的需求。這就是參考[1]中提到的信道分配問題2 (CAP2)。近幾年來，一些啟發式算法（Heuristic Approach）([2],[3],[4])等多種算法被用來解決信道分配問題。但由于算法的一些局限，往往結果并不理想�；�因算法GA的本質：全局性概率搜索算法,是可行的搜索技術，用定長的線性串對問題的解進行編碼，通過復制、交叉和變異等遺傳操作改變個體的結構。個體作為搜索對象。根據適應度進行選擇，決定個體是否參加復制、交叉等遺傳操作，得到的返回值后，代入適應度函數求出子染色體樹的適應度(適應度：表示了個體產生的效益，是個體優秀程度的度量)。取適應度最大的作為最優子個體。        已經有大量的例子使用基因算法GA來解決信道分配問題.例如, 參考文獻 [12], [19], [20], [21], [22] 使用基因算法來解決信道分配問題1 (CAP1)。[23] 和 [24] 用公式描述了CAP2, 但是它們只對無干擾的情況感興趣。參考文獻[16]中依據基因算法給出了解決信道分配問題2的獨特的公式，在本論文中，就依據這個公式，將無干擾條件作為軟限制條件(Soft constraint) ，而將各個小區所需要的信道數作為硬限制條件。我們用十個基準（benchmark）問題來進行模擬仿真，并將結果與其它算法獲取的結果相比較。 2．信道分配問題    假設一個無線通信網絡，它有N個小區和M個通信信道。小區i的信道需求（由預期的通信量求出）為Di個信道。電磁波的傳播方式可以決定在頻域中兩個信道之間能保證沒有干擾的最小距離。這些最小的距離存儲在 的對稱矩陣C中。我們回顧一下Smith 和Palaniswami[4]提出CAP2的數學模型： 其中 ; . 如果 ,就是說小區j和i分別分配到信道k 和信道l。分配所引起的干擾程度可以由張量 中的一個元素進行計算，其中 是信道k和信道l在頻域中的絕對距離。當 時，干擾的程度最大。干擾隨著兩信道間距的增大而減小。減小整個網絡中的干擾程度的問題就可簡化，即：最小化：                                    (1)限制條件：                                            (2)                                        (3)     上述提到鄰近因子張量P是一個三維矩陣。立方體正前平面對角線被置0的矩陣C。張量的第三向線成線性減少，因此張量的有效深度為矩陣C的最大對角線值，它由遞歸方法生成：                                (4)                                                    3 仿真結果    在我們的仿真試驗中，采用了參考文獻[16]推薦的方法，初始化一組滿足限制條件的個體。每個個體是一個的矩陣的解。每一行代表一個小區內的分配方案。每一行內的1的數量代表了分配給該小區的信道數目。根據前面介紹的基因算法，進行行間交叉，行內變異的算法。這樣，每次生成的新解都可滿足限制條件。我們用等式(1)來評估每個個體的適應度，并根據適應度來選擇用于生成下一個族群的個體。   問題 族群大小 交叉可能性 變異可能性

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]中的實驗問題來檢測基因算法的效果.用于試驗的問題可以分為三類.第一類包括問題EX1和EX2，分別有4和5個信道.第二類問題 (HEX1—HEX4)是基于由21個正六邊形小區構成的網絡。最后一類問題(KUNZ1---KUNZ4)是引用KUNZ在[8]中使用的一個臨近芬蘭首都赫爾辛基的覆蓋面積為24*21平方千米的網絡。在下表中，我們用基因算法獲得的結果和其它一些傳統算法獲得的結果進行比較。這些算法包括：綜合代數模型系統(General Algebraic Modeling System (GAMS), 傳統的最速下降算法(steepest descent (SD) ), 隨機模擬退火算法(stochastic simulated annealing (SSA) ),原始的Hopfield神經網絡(the original Hopfield network (HN)(without hill-climbing), 帶爬坡的Hopfield神經網絡算法(the hill-climbing Hopfield network (HCHN) ), 自組神經網絡算法( the self-organizing neural network (SONN)),和隨機無秩序模擬退火算法(stochastic chaotic simulated annealing (SCSA) ). 上述算法獲得的最小價值（Min）和均值(Av)是運行10次的計算結果，為便于比較，本文的統計結果同樣做了10次實驗仿真后所得。  方法 GA GAMS SD ssa hn hcnn sonn 問題 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列出了由基因算法產生的實際的的兩個問題的信道分配方案.KUNZ1，HEX2的結論中:結果”0”代表無干擾分配。我們可以看出對于HEX2和KUNZ1我們獲得了比其帶爬坡的Hopfield神經網絡算法(the hill-climbing Hopfield network (HCHN) )[8]中更好的數據. 在仿真過程中,一些參數,例如交叉操作機率,變異操作機率和族群大小都需要去設定.我們是通過反復試驗來設定這些參數的.到目前為止，許多研究者已經研究了在保證無干擾情況下最小化所需信道數的問題。而本論文則是針對那些實際可用信道數少于無干擾所需信道數的實際問題，研究在有限的信道的條件下來最小化生成干擾的的可行性方案,這將會很有實際應用價值. 基因算法是一個有趣的方法，它是從點到點的全局搜索,在解決優化組和問題時，可快速獲取更優的解�；鶞蕟栴}的仿真結果表明基因算法可得到比其它方法更理想的結果,即在滿足需求限制的條件下，使得信道分配帶來更少的干擾的解決方案.    更高級的基因算法諸如并行基因算法(parallel GA)和微基因算法(micro GA)可以在短時間內解決信道分配問題2,得到更好的結果. 基因算法(GA)特別適合于在高速并行計算機上運算.目標函數和限制條件可同時執行,對整個族群操作運算,通過交叉和變異操作生成選取新一代適應度更高的子族群參數。 因此對硬件性能要求高，直接關系到運行時間長短,效率問題.在一臺高速并行機上， 基因算法預計能以幾K倍的速度處理很多問題，K是入口尺寸大小。即使要并行的評估的個別問題功能有效性,也可在最短時間內獲得最佳解決辦法。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.

【優化解決移動通信中的信道分配問題】相關文章：

基于DSP的信道譯碼算法優化03-19

談直放站在移動通信中的應用03-18

淺談直放站在移動通信中的應用03-04

移動IP路由優化研究11-22

一種移動通信信道模擬器的設計與實現03-18

管理的核心是解決人的問題03-18

OFDMA系統中利用信道延時信息進行動態資源分配03-07

淺談裝飾教學需要解決的問題03-01

探討裝飾教學需要解決的問題03-20