Channel assignment algorithms in cellular radio networks

Citation

Deora, Sanjeev K. (1995) Channel assignment algorithms in cellular radio networks. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/1nxh-ak43. https://resolver.caltech.edu/CaltechETD:etd-09172007-153727

Abstract

In this thesis, we study and compare the performance of several distributed channel assignment algorithms (CAAs) in a cellular system. The CAA which is used to assign a channel to a new call greatly influences the amount of traffic the system can support. We are interested in the design and analysis of algorithms which perform well, but at the same time are relatively easy to implement. In this thesis, we have analyzed the performance of a very simple CAA which we call the Timid Algorithm, in the limiting case of a large number of channels. We have been able to show that, under a plausible mathematical hypothesis, the algorithm is asymptotically optimal, where "asymptotically" refers to a system with a large number of channels. This is very surprising as there are algorithms of much higher complexity which provably do not have this property.

The Timid Algorithm is asymptotically optimal, but it requires a large number of channels for a satisfactory performance. We looked at some algorithms which retain the simplicity of the Timid algorithm but which can be expected to give a good performance even with a smaller number of channels. We called one such algorithm the Modified DCAA. We present some simulation results which show that this algorithm gives a reasonably good performance even when the number of channels is small. One of the ways to increase the capacity of a cellular system is through the use of micro-cells. The Modified DCAA, because of its distributed nature and low complexity, is particularly suitable for such microcellular systems.

We also present a method for computing the upper bound on the performance of any CAA in a cellular system with adjacent channel constraints. The method, although computationally intensive, may be useful for determining how close an algorithm's performance is to the optimal performance.

Finally, we discuss ways of obtaining the set of "allowable" states for a system. We also present some "measurement-based" algorithms and compare their performance with "prediction-based" algorithms.

Thesis Files