A Caltech Library Service

Channel assignment algorithms in cellular radio networks


Deora, Sanjeev K. (1995) Channel assignment algorithms in cellular radio networks. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/1nxh-ak43.


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.

Item Type:Thesis (Dissertation (Ph.D.))
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • McEliece, Robert J.
Thesis Committee:
  • McEliece, Robert J. (chair)
  • Goldsmith, Andrea Jo
  • Blanchard, John
  • Simon, Marvin K.
  • Vaidyanathan, P. P.
Defense Date:23 May 1995
Record Number:CaltechETD:etd-09172007-153727
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:3587
Deposited By: Imported from ETD-db
Deposited On:09 Oct 2007
Last Modified:16 Apr 2021 22:09

Thesis Files

PDF (Deora_sk_1995.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page