On Optimal and Near-Optimal Schemes for Channel Assignment in Cellular Networks using Genetic Algorithm

摘要

The Channel Assignment Problem (CAP) deals with assigning frequency channels to the cells (within a minimum bandwidth) satisfying the frequency separation constraints for avoiding channel interference. In its most general form, this problem is NP-complete. Here, we first show that the minimum bandwidth required for assigning channels to a seven-node subgraph of a hexagonal cellular network with all nodes within distance two from each other, is lower than that given in [1] for a 2-band buffering system (where the channel interference does not extend beyond two cells). Given that, for avoiding channel interference, s_1 and s_2 are the minimum frequency separations between two cells at distance 1 and 2 apart respectively (s_1 ≥ s_2), we show that this minimum bandwidth is (s_1 + 5s_2), if s_2 ≤ s_1 ≤ 2s_2, and (2s_1 + 3s_2, if s_1 ≥ 2s_2, in contrast to (2s_1 + 4s_2) for all cases as shown in [1]. Next, we present an algorithm for solving the channel assignment problem in its general form using the Elitist model of Genetic Algorithm (EGA). It gives an optimal assignment (with bandwidth equal to the lower bound) when s_1 ≤ s_2. For other cases, the assignment using this algorithm requires a bandwidth of 8s_2 for s_2 < s_1 ≤ 2s_2, 4s_1 for 2s_2 ≤ s_1 ≤ 3s_2, and (2s_1 + 6s_2) for s_1 ≥ 3s_2. The improvement in the bandwidth provided by the proposed algorithm over that in [1] lies between 1 and 4/3.