Abstract
The channel assignment problem has become increasingly important in mobile telephone communication. Since the usable range of the frequency spectrum is limited, the optimal assignment problem of channels has become increasingly important. Recently Genetic Algorithms (GAs) have been proposed as new computational tools for solving optimization problems. GAs are more attractive than other optimization techniques, such as neural networks or simulated annealing, since GAs are generally good at finding an acceptably good global optimal solution to a problem very quickly. In this paper, a new channel assignment algorithm using GAs is proposed. The channel assignment problem is formulated as an energy minimization problem that is implemented by GAs. Appropriate GAs operators such as reproduction, crossover and mutation are developed and tested. In this algorithm, the cell frequency is not fixed before the assignment procedures as in the previously reported channel assignment algorithm using neural networks. The average generation numbers and the convergence rates of GAs are shown as a simulation result. When the number of cells in one cluster are increased, the generation numbers are increased and the convergence rates are decreased. On the other hand, with the increased minimal frequency interval, the generation numbers are decreased and the convergence rates are increased. The comparison of the various crossover and mutation techniques in a simulation shows that the combination of two points crossover and selective mutation technique provides better results. All three constraints are also considered for the channel assignments: the co-channel constraint, the adjacent channel constraint and the co-site channel constraint. The goal of this paper is the assignment of the channel frequencies which satisfied these constraints with the lower bound number of channels.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J.-S. Kim, S. H. Park, P. W. Dowd, and N. M. Nasrabadi, “Genetic algorithm approach to the channel assignment problem,” in Proc. 1995 Asia-Pacific Conference on Communications, pp. 564–567, Jun. 14–16 1995.
J.-S. Kim, S. H. Park, P. W. Dowd, and N. M. Nasrabadi, “A modified hopfield network approach for cellular radio channel assignment,” in Proc. 45th IEEE Vehicular Technology Conference, pp. 589–593, Jul. 26–28 1995.
J.-S. Kim, S. H. Park, P. W. Dowd, and N. M. Nasrabadi, “Comparison of two optimization techniques for channel assignment in cellular radio network,” in Proc. IEEE International Conference on Communications, pp. 1850–1854, Jun. 18–22 1995.
A. Gamst and W. Rave, “On frequency assignment in mobile automatic telephone systems,” in Proc. IEEE GLOBECOM' 82, pp. 309–315, 1982.
N.Funabiki and Y.Takefuji, “A neural network parallel algorithm for channel assignment problems in cellular radio networks,” IEEE Transactions on Vehicular Technology, vol. VT-41, pp. 430–436, Nov. 1992.
W. K.Hale, “Frequency assignment: Theory and applications”, Proceedings of IEEE, vol. 68, pp. 1497–1514, Dec. 1980.
M. R.Garey and D. S.Johnson, Computers and Intractability: A Guid to the Theory of NP-Completeness. New York: W.H.Freeman and Co., 1979.
D.Kunz, “Channel assignment for cellular radio using neural networks,” IEEE Transactions on Vehicular Technology, vol. VT-40, pp. 188–193, Feb. 1991.
P. T. H.Chan, M.Palaniswami, and D.Everitt, “Neural network-based dynamic channel assignment for cellular mobile communication systems,” IEEE Transactions on Vehicular Technology, vol. VT-43, pp. 279–288, May 1994.
M.Duque-Anton, D.Kunz, and B.Ruber, “Channel assignment for cellular radio using simulated annealing,” IEEE Transactions on Vehicular Technology, vol. VT-42, pp. 14–21, Feb. 1993.
J. E.Dayhoff, Neural Network Architectures: an Introduction. New York, NY: Van Nostrand Reinhold, 1990.
J. J.Hopfield and D. W.Tank, “Neural computation of decisions in optimization problems,” Biological Cybernetics, vol. 52, pp. 141–152, 1985.
S.Kirkpatrick, C. D.Gelatt, and M. P.Vecchi, “Optimization by simulated annealing,” Science, vol. 220, pp. 671–680, May 1983.
D.Beasley, D. R.Bull, and R. R.Martin, “An Overview of Genetic Algorithms: Part I, Fundamentals,” University Computing, vol. 15, no. 2, pp. 58–69, 1993.
J. H.Holland, Adaptation in Natural and Artificial Systems. Cambridge, MA: MIT Press, 1975.
D. E.Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. New York: Addison Wesley, 1989.
A. K.Bhattacharjya, D. E.Becker, and B.Roysam, “A genetic algorithm for intelligent imaging from quantum-limited data,” Signal Processing, vol. 28, pp. 335–348, 1992.
Z.Michalewicz, “A step towards optimal topology of communication networks,” Proc. of SPIE, vol. 1470, pp. 112–122, Apr. 1991.
R.Chandrsekharam, S.Subhramanian, and S.Chaudhury, “Genetic algorithm for node partitioning problem and applications in VLSI design,” IEE Proceedings E, vol. 140, pp. 255–260, Sept. 1993.
A. V. Sannier and E. D. Goodman, “Midgard:a genetic approach to adaptive load balancing for distributed systems,” in Proc. of 5 th International Conference on Machine Learning, pp. 174–180, June 1988.
G. Syswerda, “Uniform crossover in genetic algorithm,” in Proc. of International Conference on Genetic Algorithms, pp. 2–9, 1989.
A.Gamst, “Some lower bounds for a class of frequency assignment problems,” IEEE Transactions on Vehicular Technology, vol. VT-35, pp. 8–14, Feb. 1986.
K. N. Sivarajan, R. J. McEliece, and J. W. Ketchum, “Channel assignment in cellular radio,” in Proc. 39th IEEE Vehicular Technology Conference, pp. 846–850, May 1989.
J.-S. Kim, S. H. Park, P. W. Dowd, and N. M. Nasrabadi, “Cellular radio channel assignment using a modified Hopfield network,” IEEE Transactions on Vehicular Technology, (Submitted and Revised), 1994.
J.Zoellner and C.Beall, “A breakthrough in spectrum conserving frequency assignment technology,” IEEE Transactions on Electromagnetic Compatibility, vol. EMC-19, pp. 313–319, Aug. 1977.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kim, J.S., Park, S., Dowd, P. et al. Channel assignment in cellular radio using genetic algorithms. Wireless Personal Communications 3, 273–286 (1996). https://doi.org/10.1007/BF00354875
Issue Date:
DOI: https://doi.org/10.1007/BF00354875