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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Nobuo FUNABIKI, Toru NAKANISHI, Tokumi YOKOHIRA, Shigeto TAJIMA, Teruo HIGASHINO, "A Quasi-Solution State Evolution Algorithm for Channel Assignment Problems in Cellular Networks" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 5, pp. 977-987, May 2002, doi: .
Abstract: For efficient use of limited electromagnetic wave resource, the assignment of communication channels to call requests is very important in a cellular network. This task has been formulated as an NP-hard combinatorial optimization problem named the channel assignment problem (CAP). Given a cellular network and a set of call requests, CAP requires to find a channel assignment to the call requests such that three types of interference constraints between channels are not only satisfied, but also the number of channels (channel span) is minimized. This paper presents an iterative search approximation algorithm for CAP, called the Quasi-solution state evolution algorithm for CAP (QCAP). To solve hard CAP instances in reasonable time, QCAP evolutes quasi-solution states where a subset of call requests are assigned channels and no more request can be satisfied without violating the constraint. QCAP is composed of three stages. The first stage computes the lower bound on the channel span for a given instance. After the second stage greedily generates an initial quasi-solution state, the third stage evolutes them for a feasible channel assignment by iteratively generating best neighborhoods, with help of the dynamic state jump and the gradual span expansion for global convergence. The performance of QCAP is evaluated through solving benchmark instances in literature, where QCAP always finds the optimum or near-optimum solution in very short time. Our simulation results confirm the extensive search capability and the efficiency of QCAP.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_5_977/_p
Copier
@ARTICLE{e85-a_5_977,
author={Nobuo FUNABIKI, Toru NAKANISHI, Tokumi YOKOHIRA, Shigeto TAJIMA, Teruo HIGASHINO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Quasi-Solution State Evolution Algorithm for Channel Assignment Problems in Cellular Networks},
year={2002},
volume={E85-A},
number={5},
pages={977-987},
abstract={For efficient use of limited electromagnetic wave resource, the assignment of communication channels to call requests is very important in a cellular network. This task has been formulated as an NP-hard combinatorial optimization problem named the channel assignment problem (CAP). Given a cellular network and a set of call requests, CAP requires to find a channel assignment to the call requests such that three types of interference constraints between channels are not only satisfied, but also the number of channels (channel span) is minimized. This paper presents an iterative search approximation algorithm for CAP, called the Quasi-solution state evolution algorithm for CAP (QCAP). To solve hard CAP instances in reasonable time, QCAP evolutes quasi-solution states where a subset of call requests are assigned channels and no more request can be satisfied without violating the constraint. QCAP is composed of three stages. The first stage computes the lower bound on the channel span for a given instance. After the second stage greedily generates an initial quasi-solution state, the third stage evolutes them for a feasible channel assignment by iteratively generating best neighborhoods, with help of the dynamic state jump and the gradual span expansion for global convergence. The performance of QCAP is evaluated through solving benchmark instances in literature, where QCAP always finds the optimum or near-optimum solution in very short time. Our simulation results confirm the extensive search capability and the efficiency of QCAP.},
keywords={},
doi={},
ISSN={},
month={May},}
Copier
TY - JOUR
TI - A Quasi-Solution State Evolution Algorithm for Channel Assignment Problems in Cellular Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 977
EP - 987
AU - Nobuo FUNABIKI
AU - Toru NAKANISHI
AU - Tokumi YOKOHIRA
AU - Shigeto TAJIMA
AU - Teruo HIGASHINO
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E85-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2002
AB - For efficient use of limited electromagnetic wave resource, the assignment of communication channels to call requests is very important in a cellular network. This task has been formulated as an NP-hard combinatorial optimization problem named the channel assignment problem (CAP). Given a cellular network and a set of call requests, CAP requires to find a channel assignment to the call requests such that three types of interference constraints between channels are not only satisfied, but also the number of channels (channel span) is minimized. This paper presents an iterative search approximation algorithm for CAP, called the Quasi-solution state evolution algorithm for CAP (QCAP). To solve hard CAP instances in reasonable time, QCAP evolutes quasi-solution states where a subset of call requests are assigned channels and no more request can be satisfied without violating the constraint. QCAP is composed of three stages. The first stage computes the lower bound on the channel span for a given instance. After the second stage greedily generates an initial quasi-solution state, the third stage evolutes them for a feasible channel assignment by iteratively generating best neighborhoods, with help of the dynamic state jump and the gradual span expansion for global convergence. The performance of QCAP is evaluated through solving benchmark instances in literature, where QCAP always finds the optimum or near-optimum solution in very short time. Our simulation results confirm the extensive search capability and the efficiency of QCAP.
ER -