Distributed Frequency Assignment Using Hierarchical Cooperative Multi-Agent System

Jamal Elhachimi, Zouhair Guenoun
DOI: 10.4236/ijcns.2011.411089                

Abstract

Recent demand for wireless communication continues to grow rapidly as a result of the increasing number of users, the emergence of new user requirements, and the trend to new access technologies. At the same time, the electromagnetic spectrum or frequencies allocated for this purpose are still limited. This makes solving the frequency assignment problem more and more critical. In this paper, a new approach is proposed using self-organizing multi-agent systems to solve distributed dynamic channel-assignment; it concerns distribution among agents which task is to assign personal station to frequencies with respect to well known constraints. Agents only know their variables and the constraints affecting them, and have to negotiate to find a collective solution. The approach is based on a macro-level management taking the form of a hierarchical group of distributed agents in the network and handling all RANs (Regional Radio Access Network) in a localized region regardless of the operating band. The approach defines cooperative self-organization as the process leading the collective to the solution: agents can change the organization by their own decision to improve the state of the system. Our approach has been tested on PHEADEPHIA benchmarks of frequency assignment Problem. The results obtained are equivalent to those of current existing methods with the benefits that our approach shows more efficiency in terms of flexibility and autonomy.

Keywords

Dynamic Frequency Assignment, Optimization Problem, Multi-Agent System, Artificial Intelligence

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	M. da S. Maximiano, M. A. Vega-Rodríguez, J. A. Gómez-Pulido and J. M. Sánchez-Pérez, “A Hybrid Differential Evolution Algorithm to Solve a Real-World Frequency Assignment Problem,” International Multiconference on Computer Science and Information Technology, Wisia, 20-22 October 2008, pp. 201-205. doi:10.1109/IMCSIT.2008.4747240
[2]	M. Yokoo and K. Hirayama, “Frequency Assignment for Cellular Mobile Systems Using Constraint Satisfaction Techniques,” Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, Vol. 1713, 1999, pp. 490-491.
[3]	A. Gamst, “Some Lower Bounds for a Class of Frequency Assignment Problems,” IEEE Transactions on Vehicular Technology, Vol. 35, No. 1, 1986, pp. 8-14. doi:10.1109/T-VT.1986.24063
[4]	J. K. Hao, R. Dorne and P. Galinier, “Tabu Search for Frequency Assignment in Mobile Radio Networks,” Journal of Heuristics, Vol. 4, No. 1, 1998, pp. 47-62. doi:10.1023/A:1009690321348
[5]	K. N. Sivarajan, R. J. McEliece and J. W. Ketchum, “Channel Assignment in Cellular Radio,” Proceedings of 39th IEEE Vehicular Technology Society Conference, San Francisco, 1-3 May 1989, pp. 846-850. doi:10.1109/VETEC.1989.40173
[6]	N. Funabiki, N. Okutani and S. Nishikawa, “A Three- stage Heuristic Combined Neural Network Algorithm for Channel Assignment in Cellular Mobile Systems,” IEEE Transactions on Vehicular Technology, Vol. 9, No. 2, 2000, pp. 397-403.
[7]	M. Carlsson and M. Grindal, “Automatic Frequency Assignment for Cellular Telephones Using Constraint Satisfaction Techniques,” Proceedings of the Tenth International Conference on Logic Programming, MIT Press Cambridge, 1993, pp. 647-663.
[8]	W. K. Hale, “Frequency Assignment: Theory and Application,” Proceedings of the IEEE, Vol. 68, No. 12, 1980, pp. 1497-1513. doi:10.1109/PROC.1980.11899
[9]	S. Hurley, D. H. Smith and S. U. Thiel, “FASoft: A System for Discrete Channel Frequency Assignment,” Radio Science, Vol. 32, No. 5, 1997, pp. 1921-1939. doi:10.1029/97RS01866
[10]	D. H. Smith, S. Hurley and S. U. Thiel, “Improving Heuristics for the Frequency Assignment Problem,” European Journal of Operational Research, Vol. 107, No.1, 1998, pp. 76-86. doi:10.1016/S0377-2217(98)80006-4
[11]	D. Kunz, “Channel Assignment for Cellular Radio Using Neural Networks,” IEEE Transactions on Vehicular Technology, Vol. 40, No. 1, 1991, pp. 188-193. doi:10.1109/25.69987
[12]	N. Funabiki and Y. Takefuji, “A Neural Network Parallel Algorithm for Channel Assignment Problems in Cellular Radio Networks,” IEEE Transactions on Vehicular Technology, Vol. 41, No. 4, 1992, pp. 430-437. doi:10.1109/25.182594
[13]	J. Elhachmi and Z. Guenoun, “Frequency Assignment for Cellular Mobile Systems Using a Hybrid Tabu Search,” Journal of Telecommunications, Vol. 8, No. 1, 2011, pp. 11-15.
[14]	A. R. Mishra, “Fundamentals of Cellular Network Planning and Optimisation: 2G/2.5G/3G... Evolution to 4G,” Wiley, Hoboken, pp. 21-54. 2004. doi:10.1002/0470862696
[15]	F. Luna, C. Blum, E. Alba and A. J. Nebro, “ACO vs EAs for Solving a Real-World Frequency Assignment Problem in GSM Networks,” ACM, New York, pp. 94-101,
[16]	FCC, ET Docket No. 03-322 Notice of Proposed Rule Making and Order, December 2003.
[17]	F. Luna, A. J. Nebro, E. Alba and J. J. Durillo, “Solving Large-Scale Real-World Telecommunication Problems Using a Grid-Based Genetic Algorithm,” Engineering Optimization, Vol. 40, No. 11, 2008, pp. 1067-1084. doi:10.1080/03052150802294581
[18]	F. Cornet, “Etude d’un Problème D’Allocation de Fré- Quences par Systèmes Multi-Agents Adaptatifs,” Research Master IARCL Report, Université Paul Sabatier, Toulouse, June 2006.
[19]	J. Elhachmi and Z. Guenoun, “A Multi-Agent System for Resource Management in GSM Cellular Networks,” International Symposium on Distributed Computing and Artificial Intelligence, Advances in Intelligent and Soft Computing, Vol. 91, 2011, pp. 99-106. doi:10.1007/978-3-642-19934-9_13
[20]	R. Haralick and G. L. Elliot, “Increasing Tree Search Efficiency for Constraint Satisfaction Problems,” Artificial Intelligence, Vol. 14, No. 1, 1980, pp. 263-313. doi:10.1016/0004-3702(80)90051-X