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