Abstract
With the limited number of communication frequencies and the increasing number of users, the problem of communication frequencies assignment without interference is more than ever at the heart of the development of cellular networks. This paper reports a heuristic assignment based on the scheduling of the cells and the scheduling of the maximum stables of the dependency graph of the cells network. The purpose of the maximum stables scheduling is to assign without interference a maximum number of frequencies to cells while the purpose of the cells scheduling is to minimize the number of the used frequencies. Therefore aim of the heuristic is to satisfy a maximum number of connection requests with a minimum number of frequencies. The heuristic is implemented and its performance evaluated for the well known network test Philadelphia-benchmark.
Co-author Ye Xu was in LITA from April to September 2014 for her Master 2 Thesis in Computer Science at the University of Lorraine.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chakraborty, G.: An Efficient Heuristic Algorithm for Channel Assignment Problem in Cellular Radio Networks. IEEE Trans. Veh. Technol. 50 (2001)
Aardal, K.I., et al.: Models and Solution Techniques for Frequency Assignment Problems. ZIB-Report 01–40 (2001)
Yu, F., Bar-Noy, A., Basu, P., Ramanathan, R.: Algorithms for channel assignment in mobile wireless networks using temporal coloring. In: Proceedings of the 16th ACM International Conference on Modeling, Analysis & Simulation of Wireless and Mobile Systems, pp. 49–58 (2013)
Martín, H.J.A.: Solving Hard Computational Problems Efficiently: Asymptotic Parametric Complexity 3-Coloring Algorithm. PLoS ONE 8(1), e53437 (2013). doi:10.1371/journal.pone.0053437
Gavril, F.: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph. doi:10.1137/0201013
Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit Disk Graphs. Ann. Discret. Math. 48, 165–177 (1991)
Hurley, S., Smith, D.H., Thiel, S.U.: FAsoft: A system for discrete channel frequency assignment. Radio Science 32(5), 1921–1939 (1998)
Balasundaram, B., Butenko, S.: Graph domination, coloring and cliques in telecommunications. In: Handbook of Optimization in Telecommunication (2006)
Alzoubi, K.M., Wan, P.-J., Frieder, O.: Weakly-connected dominating sets and sparse spanners in wireless ad hoc networks. In: Proceedings of ICDCS, pp. 96–104 (2003)
Luna, F., et al.: Optimization algorithms for large-scale real-world instances of the frequency assignment problem. Soft. Comput. 15, 975–990 (2011)
Björklund, P., Värbrand, P., Yuan, D.: Optimized planning of frequency hopping in cellular networks. J. Computers and Operations Research 32(1), 169–186 (2005)
Zhang, Y.-B., Zhao, Y.-C., Xiong, H.: A tabu search algorithm for frequency assignment problem in wireless communication networks. In: Proceedings of Wicom 2009, pp. 2848–2851 (2009)
Parsapoor, M., Bilstrup, U.: Ant colony optimization for channel assignment problem in a clustered mobile ad hoc network. In: Tan, Y., Shi, Y., Mo, H. (eds.) ICSI 2013, Part I. LNCS, vol. 7928, pp. 314–322. Springer, Heidelberg (2013)
Alba, E.: Parallel Metaheuristics: A New Class of Algorithms. John Wiley & Sons, Inc. (2005)
Vidyarthi, G., Ngom, A., Stojmenovic, I.: A hybrid channel assignment approach using an efficient evolutionary strategy in wireless mobile networks. IEEE Trans. Veh. Technol. 54, 1887–1895 (2005)
Colombo, G.: A genetic algorithm for frequency assignment with problem decomposition. J. of Mobile Network Design and Innovative Archive 1(2), 102–112 (2006)
Luna, F., Nebro, A.J., Alba, E.: Durillo, J-J.: Large-Scale Real-World Telecommunication Problems Using a Grid-Based Genetic Algorithm. Engineering Optimization 40(11), 1067–1084 (2008)
Ngo, C.Y., Li, V.O.K.: Fixed channel assignment in cellular radio networks using a modified genetic algorithm. IEEE Trans. Veh. Technol. 47, 163–172 (1998)
Maximiano, M.-D., Vega-Rodriguez, M.A., Gomez Pilido, J.A., Sánchez-Pérez, J.M.: A hybrid differential evolution algorithm to solve a real-world frequency assignment problem. In: Proc. of International Multiconference on Computer Science and Information Technology, Wisia, pp. 201–205 (2008)
Elhachmi, J., Guenoun, Z.: Distributed Frequency Assignment Using Hierarchical Cooperative Multi-Agent System. Int. J. Communications, Network and System Sciences 4, 727–734 (2011)
Funabiki, N., Okutani, N., Nis, S.: A Three-stage Heuristic Combined Neural Network Algorithm for Channel Assignment in Cellular Mobile Systems. IEEE Trans. Veh. Technol. 9(2), 397–403 (2000)
Nemhauser, G., Wolsey, L.: Integer and Combinatorial Optimization. J. Wiley & Sons, Inc. (2014)
Aardal, K., van Hoesel, S.P.M., Koster, A.M.C.A., Mannino, C., Sassano, A.: Models and solution techniques for frequency assignment problems. Quarterly Journal of the Belgian, French and Italian Operations Research Societies 1(4), 261–317 (2003)
Das, A.K., et al.: Optimization models for fixed channel assignment in wireless mesh networks with multiple radios. In: Proceedings of IEE SECON, pp. 463–474 (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Xu, Y., Sakho, I. (2015). Frequencies Assignment in Cellular Networks. In: Nguyen, N., Trawiński, B., Kosala, R. (eds) Intelligent Information and Database Systems. ACIIDS 2015. Lecture Notes in Computer Science(), vol 9011. Springer, Cham. https://doi.org/10.1007/978-3-319-15702-3_21
Download citation
DOI: https://doi.org/10.1007/978-3-319-15702-3_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-15701-6
Online ISBN: 978-3-319-15702-3
eBook Packages: Computer ScienceComputer Science (R0)