Spectrum efficient frequency assignment for cellular radio

Citation

Sivarajan, Kumar N. (1990) Spectrum efficient frequency assignment for cellular radio. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/q2qb-hh14. https://resolver.caltech.edu/CaltechETD:etd-11082007-105043

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 co-channel constraints only): Given a graph G with vertices V = [...] and an n-vector 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 well-known 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 co-channel constraints (e.g., adjacent channel and co-site 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 near-optimal 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 (2-4%), 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.

Thesis Files