Sequential packing algorithm for channel assignment under cochanneland adjacent-channel interference constraint

摘要

Generally, the channel-assignment problem (CAP) for mobilencellular systems is solved by graph-coloring algorithms. Thesenalgorithms, though sometimes can yield an optimal solution, do notnsupply any information on whether an optimal solution has been found ornbow far away it is from the optimum. In view of these undesirablenfeatures, two relevant results are presented. First, a lower bound fornthe minimum number of channels required to satisfy a given call-trafficndemand is derived. This lower bound is tighter than the existing onesnunder certain conditions and can be used as a supplement for othernapproximate algorithms. Second, we propose an efficient heuristicnalgorithm to solve this problem. Although the CAP is nondeterministicnpolynomial (NP) complete in general, our algorithm provides an optimalnsolution for a special class of network topologies. For the generalncase, promising results are obtained, and numerical examples show thatnour algorithm has a better performance than many existing algorithms