TY - JOUR
T1 - The F/DR-D-10 Algorithm
T2 - A Novel Heuristic Strategy to Solve the Minimum Span Frequency Assignment Problem Embedded in Mobile Applications
AU - Páez-Rueda, Carlos Iván
AU - Fajardo, Arturo
AU - Pérez, Manuel
AU - Yamhure, German
AU - Perilla, Gabriel
N1 - Publisher Copyright:
© 2023 by the authors.
PY - 2023/10/11
Y1 - 2023/10/11
N2 - Wireless communication supports various real-world applications, such as aeronautical navigation, satellite and TV broadcasting, wireless LANs, and mobile communications. The inherent characteristics of the electromagnetic spectrum impose constraints on telecommunication channels and their frequency bandwidths within mobile networks. A persistent challenge in these applications is providing high-demand services to mobile users, where frequency assignment problems, also known as channel assignment problems, assume significance. Researchers have developed several modeling approaches to address different facets of this problem, including the management of interfering radio signals, the assessment of available frequencies, and optimization criteria. In this paper, we present improved algorithms for solving the Minimum Span Frequency Assignment Problem in mobile communication systems using the greedy optimization approach known as F/DR. We solved and evaluated twenty well-known benchmark cases to assess the efficacy of our algorithms. Our findings consistently demonstrate that the modified algorithms outperform the F/DR approach with comparable computational complexity. The proposed algorithm notably achieves the following benchmarks: The modified algorithms consistently produce at least one local optimum better than the traditional algorithm in all benchmark tests. In 95% of the benchmarks evaluated, the probability of discovering a local optimum value (calculated by the modified algorithm) that is better than or equal to the one found by the conventional algorithm exceeds 50%.
AB - Wireless communication supports various real-world applications, such as aeronautical navigation, satellite and TV broadcasting, wireless LANs, and mobile communications. The inherent characteristics of the electromagnetic spectrum impose constraints on telecommunication channels and their frequency bandwidths within mobile networks. A persistent challenge in these applications is providing high-demand services to mobile users, where frequency assignment problems, also known as channel assignment problems, assume significance. Researchers have developed several modeling approaches to address different facets of this problem, including the management of interfering radio signals, the assessment of available frequencies, and optimization criteria. In this paper, we present improved algorithms for solving the Minimum Span Frequency Assignment Problem in mobile communication systems using the greedy optimization approach known as F/DR. We solved and evaluated twenty well-known benchmark cases to assess the efficacy of our algorithms. Our findings consistently demonstrate that the modified algorithms outperform the F/DR approach with comparable computational complexity. The proposed algorithm notably achieves the following benchmarks: The modified algorithms consistently produce at least one local optimum better than the traditional algorithm in all benchmark tests. In 95% of the benchmarks evaluated, the probability of discovering a local optimum value (calculated by the modified algorithm) that is better than or equal to the one found by the conventional algorithm exceeds 50%.
KW - NP-hard problem
KW - channel assignment problem
KW - frequency assignment problem
KW - heuristic algorithms
KW - minimum span frequency assignment problem
UR - http://www.scopus.com/inward/record.url?scp=85175084907&partnerID=8YFLogxK
U2 - 10.3390/math11204243
DO - 10.3390/math11204243
M3 - Article
AN - SCOPUS:85175084907
SN - 2227-7390
VL - 11
JO - Mathematics
JF - Mathematics
IS - 20
M1 - 4243
ER -