Citation
Sivarajan, Kumar N. (1990) Spectrum efficient frequency assignment for cellular radio. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd11082007105043
Abstract
NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract is included in .pdf document.
In this thesis, we first describe some results on the following generalized chromatic number problem that has its origin in cellular radio (the frequency assignment problem with cochannel constraints only): Given a graph G with vertices V = [...] and an nvector M = [...] of nonnegative integers (the requirement vector), find the minimum number of colors, [...](G, M), required to assign [...] distinct colors to vertex [...], [...], such that adjacent vertices are assigned disjoint sets of colors. We develop a lower bound on [...](G, M), which generalizes and strengthens the wellknown bound [...] n for the usual chromatic number. We show that this bound is sharp for a number of interesting graphs (e.g., perfect graphs and odd cycles), but not for all graphs  the Grotzsch graph being a counterexample. We also give examples of the application of this bound to frequency assignment in cellular radio.
In the presence of constraints other than just cochannel constraints (e.g., adjacent channel and cosite constraints), the frequency assignment problem is a further generalization of the graph coloring problem. We describe some heuristic algorithms for frequency assignment in cellular radio that we developed by suitably adapting some of the ideas previously introduced in heuristic graph coloring algorithms. These algorithms have yielded optimal, or nearoptimal assignments, in many cases.
We then describe some dynamic channel assignment algorithms for cellular systems that we have developed. In addition to having a considerable advantage over fixed channel assignment in the range of blocking probabilities of interest in current cellular systems (24%), these algorithms are feasible for implementation in these systems. Some of these dynamic channel assignment algorithms are also shown to give good performance under overload (heavy traffic conditions).
Finally, we discuss various methods of computing interference probabilities and the formulation of compatibility constraints on channel assignment based on these calculations. We also formulate the channel assignment problem as one of coloring hypergraphs, instead of graphs, and show that, in the case of dynamic channel assignment, this leads to a considerable increase in the carried traffic for the same blocking probability and the same maximum probability of interference.
Item Type:  Thesis (Dissertation (Ph.D.)) 

Degree Grantor:  California Institute of Technology 
Division:  Engineering and Applied Science 
Major Option:  Electrical Engineering 
Thesis Availability:  Restricted to Caltech community only 
Research Advisor(s): 

Thesis Committee: 

Defense Date:  16 May 1990 
Record Number:  CaltechETD:etd11082007105043 
Persistent URL:  http://resolver.caltech.edu/CaltechETD:etd11082007105043 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  4463 
Collection:  CaltechTHESIS 
Deposited By:  Imported from ETDdb 
Deposited On:  05 Dec 2007 
Last Modified:  26 Dec 2012 03:08 
Thesis Files
PDF (Sivarajan_kn_1990.pdf)
 Final Version
Restricted to Caltech community only See Usage Policy. 3025Kb 
Repository Staff Only: item control page