La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A Quasi-Solution State Evolution Algorithm for Channel Assignment Problems in Cellular Networks Un algorithme d'évolution d'état de quasi-solution pour les problèmes d'attribution de canaux dans les réseaux cellulaires

Nobuo FUNABIKI, Toru NAKANISHI, Tokumi YOKOHIRA, Shigeto TAJIMA, Teruo HIGASHINO

  • Vues en texte intégral

    0

  • Citer

Résumé:

Pour une utilisation efficace d'une ressource limitée en ondes électromagnétiques, l'attribution de canaux de communication aux demandes d'appel est très importante dans un réseau cellulaire. Cette tâche a été formulée comme un problème d'optimisation combinatoire NP-difficile appelé problème d'affectation de canal (Code postal). Étant donné un réseau cellulaire et un ensemble de demandes d'appel, CAP nécessite de trouver une affectation de canal aux demandes d'appel telle que trois types de contraintes d'interférence entre canaux soient non seulement satisfaites, mais également le nombre de canaux (étendue du canal) est minimisé. Cet article présente un algorithme d'approximation de recherche itérative pour CAP, appelé algorithme d'évolution d'état quasi-solution pour CAP (QCAP). Pour résoudre les instances CAP difficiles dans des délais raisonnables, QCAP évolue états de quasi-solution où un sous-ensemble de demandes d'appel se voit attribuer des canaux et aucune autre demande ne peut être satisfaite sans violer la contrainte. QCAP est composé de trois étapes. La première étape calcule la limite inférieure de l'étendue du canal pour une instance donnée. Après que la deuxième étape ait généré avidement un état initial de quasi-solution, la troisième étape les fait évoluer pour une attribution de canal réalisable en générant de manière itérative les meilleurs voisinages, avec l'aide du saut d'état dynamique et de l'expansion progressive de la portée pour la convergence globale. Les performances de QCAP sont évaluées en résolvant des instances de référence dans la littérature, où QCAP trouve toujours la solution optimale ou presque optimale en très peu de temps. Nos résultats de simulation confirment la capacité de recherche étendue et l’efficacité de QCAP.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.977-987
Date de publication
2002/05/01
Publicisé
ISSN en ligne
DOI
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories

Auteurs

Mots-clés

Table des matières