The F/DR-D-10 Algorithm: A Novel Heuristic Strategy to Solve the Minimum Span Frequency Assignment Problem Embedded in Mobile Applications

Abstract

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%.

Keywords

• NP-hard problem
• channel assignment problem
• frequency assignment problem
• minimum span frequency assignment problem
• heuristic algorithms