優(yōu)化解決移動通信中的信道分配問題
時間：
唐芳1由 分享
摘要 由于可用的移動通信的頻帶寬度是有限的，優(yōu)化信道分配的問題變的越來越重要。通過優(yōu)化可以大大提高系統(tǒng)容量，并且減少通信間的干擾，從而改善了通信質(zhì)量，提高客戶的滿意度。在本論文中，我們通過基因算法(GA)，在信道數(shù)量有限的條件下，解決移動通信網(wǎng)絡中的頻率分配問題。信道分配問題是個很復雜的優(yōu)化問題。模擬結(jié)果表明基因算法(GA)可以進一步提高由其它算法獲得的結(jié)果。
關鍵詞 基因算法，信道分配，信道干擾
1．介紹
在移動通信中，提供給用戶和無線網(wǎng)絡基站之間通信的頻帶寬度是有限的。因此，隨著手機用戶的普及，這個有限的資源成為移動通信系統(tǒng)發(fā)展的瓶頸。為滿足信噪比要求，本文從以下三種基本的干擾：同信道干擾，同區(qū)域干擾，鄰道干擾考慮來設計網(wǎng)絡。
無線頻率傳播和預期的通信量作為某些信道分配給某個區(qū)域時是否會產(chǎn)生干擾的決定因素。通信量也可以用來預測每個區(qū)域內(nèi)所需要的信道數(shù)目。信道分配問題可以分為兩類。第一類：在滿足整個系統(tǒng)無干擾的情況下，最小化所需的信道數(shù)，以節(jié)約有效的頻率資源。這就是參考[1]中提到的信道分配問題1(CAP1).第二類：在大多數(shù)實際應用中，無法提供足夠可用的信道確保無干擾的信道分配，只能最小化整個系統(tǒng)內(nèi)的干擾，滿足各區(qū)域?qū)π诺罃?shù)量上的需求。這就是參考[1]中提到的信道分配問題2 (CAP2)。近幾年來，一些啟發(fā)式算法（Heuristic Approach）([2],[3],[4])等多種算法被用來解決信道分配問題。但由于算法的一些局限，往往結(jié)果并不理想。
基因算法GA的本質(zhì)：全局性概率搜索算法,是可行的搜索技術，用定長的線性串對問題的解進行編碼，通過復制、交叉和變異等遺傳操作改變個體的結(jié)構。個體作為搜索對象。根據(jù)適應度進行選擇，決定個體是否參加復制、交叉等遺傳操作，得到的返回值后，代入適應度函數(shù)求出子染色體樹的適應度(適應度：表示了個體產(chǎn)生的效益，是個體優(yōu)秀程度的度量)。取適應度最大的作為最優(yōu)子個體。
已經(jīng)有大量的例子使用基因算法GA來解決信道分配問題.例如, 參考文獻 [12], [19], [20], [21], [22] 使用基因算法來解決信道分配問題1 (CAP1)。[23] 和 [24] 用公式描述了CAP2, 但是它們只對無干擾的情況感興趣。參考文獻[16]中依據(jù)基因算法給出了解決信道分配問題2的獨特的公式，在本論文中，就依據(jù)這個公式，將無干擾條件作為軟限制條件(Soft constraint) ，而將各個小區(qū)所需要的信道數(shù)作為硬限制條件。我們用十個基準（benchmark）問題來進行模擬仿真，并將結(jié)果與其它算法獲取的結(jié)果相比較。
2．信道分配問題
假設一個無線通信網(wǎng)絡，它有N個小區(qū)和M個通信信道。小區(qū)i的信道需求（由預期的通信量求出）為Di個信道。電磁波的傳播方式可以決定在頻域中兩個信道之間能保證沒有干擾的最小距離。這些最小的距離存儲在 的對稱矩陣C中。我們回顧一下Smith 和Palaniswami[4]提出CAP2的數(shù)學模型：
其中 ; . 如果 ,就是說小區(qū)j和i分別分配到信道k 和信道l。分配所引起的干擾程度可以由張量 中的一個元素進行計算，其中 是信道k和信道l在頻域中的絕對距離。當 時，干擾的程度最大。干擾隨著兩信道間距的增大而減小。減小整個網(wǎng)絡中的干擾程度的問題就可簡化，即：
最小化：
(1)
限制條件：
(2)
(3) 上述提到鄰近因子張量P是一個三維矩陣。立方體正前平面對角線被置0的矩陣C。張量的第三向線成線性減少，因此張量的有效深度為矩陣C的最大對角線值，它由遞歸方法生成：
(4)
3 仿真結(jié)果
在我們的仿真試驗中，采用了參考文獻[16]推薦的方法，初始化一組滿足限制條件的個體。每個個體是一個的矩陣的解。每一行代表一個小區(qū)內(nèi)的分配方案。每一行內(nèi)的1的數(shù)量代表了分配給該小區(qū)的信道數(shù)目。根據(jù)前面介紹的基因算法，進行行間交叉，行內(nèi)變異的算法。這樣，每次生成的新解都可滿足限制條件。我們用等式(1)來評估每個個體的適應度，并根據(jù)適應度來選擇用于生成下一個族群的個體。
問題 | 族群大小 | 交叉可能性 | 變異可能性 |
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 用于基因算法仿真中的參數(shù)
我們用在參考文獻[8]中的實驗問題來檢測基因算法的效果.用于試驗的問題可以分為三類.第一類包括問題EX1和EX2，分別有4和5個信道.第二類問題 (HEX1—HEX4)是基于由21個正六邊形小區(qū)構成的網(wǎng)絡。最后一類問題(KUNZ1---KUNZ4)是引用KUNZ在[8]中使用的一個臨近芬蘭首都赫爾辛基的覆蓋面積為24*21平方千米的網(wǎng)絡。在下表中，我們用基因算法獲得的結(jié)果和其它一些傳統(tǒng)算法獲得的結(jié)果進行比較。這些算法包括：綜合代數(shù)模型系統(tǒng)(General Algebraic Modeling System (GAMS), 傳統(tǒng)的最速下降算法(steepest descent (SD) ), 隨機模擬退火算法(stochastic simulated annealing (SSA) ),原始的Hopfield神經(jīng)網(wǎng)絡(the original Hopfield network (HN)(without hill-climbing), 帶爬坡的Hopfield神經(jīng)網(wǎng)絡算法(the hill-climbing Hopfield network (HCHN) ), 自組神經(jīng)網(wǎng)絡算法( the self-organizing neural network (SONN)),和隨機無秩序模擬退火算法(stochastic chaotic simulated annealing (SCSA) ). 上述算法獲得的最小價值（Min）和均值(Av)是運行10次的計算結(jié)果，為便于比較，本文的統(tǒng)計結(jié)果同樣做了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.結(jié)論和討論
基站號Base Station No. | 信道數(shù)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
基站號 | 信道數(shù) | 信道分配 |
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)生的實際的的兩個問題的信道分配方案.KUNZ1，HEX2的結(jié)論中:結(jié)
果”0”代表無干擾分配。我們可以看出對于HEX2和KUNZ1我們獲得了比其帶爬坡的Hopfield神經(jīng)網(wǎng)絡算法(the hill-climbing Hopfield network (HCHN) )[8]中更好的數(shù)據(jù). 在仿真過程中,一些參數(shù),例如交叉操作機率,變異操作機率和族群大小都需要去設定.我們是通過反復試驗來設定這些參數(shù)的.
到目前為止，許多研究者已經(jīng)研究了在保證無干擾情況下最小化所需信道數(shù)的問題。而本論文則是針對那些實際可用信道數(shù)少于無干擾所需信道數(shù)的實際問題，研究在有限的信道的條件下來最小化生成干擾的的可行性方案,這將會很有實際應用價值.
基因算法是一個有趣的方法，它是從點到點的全局搜索,在解決優(yōu)化組和問題時，可快速獲取更優(yōu)的解?；鶞蕟栴}的仿真結(jié)果表明基因算法可得到比其它方法更理想的結(jié)果,即在滿足需求限制的條件下，使得信道分配帶來更少的干擾的解決方案.
更高級的基因算法諸如并行基因算法(parallel GA)和微基因算法(micro GA)可以在短時間內(nèi)解決信道分配問題2,得到更好的結(jié)果. 基因算法(GA)特別適合于在高速并行計算機上運算.目標函數(shù)和限制條件可同時執(zhí)行,對整個族群操作運算,通過交叉和變異操作生成選取新一代適應度更高的子族群參數(shù)。 因此對硬件性能要求高，直接關系到運行時間長短,效率問題.
在一臺高速并行機上， 基因算法預計能以幾K倍的速度處理很多問題，K是入口尺寸大小。即使要并行的評估的個別問題功能有效性,也可在最短時間內(nèi)獲得最佳解決辦法。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.
5M. 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 modified
genetic algorithm,” IEEE Trans. Vehicular Technology,vol. 47, no. 1, pp. 163-172, Feb., 1998.