关键词 基因算法，信道分配，信道干扰
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 modified
genetic algorithm,” IEEE Trans. Vehicular Technology,vol. 47, no. 1, pp. 163-172, Feb., 1998.
