Title

On An Optimal Algorithm For Channel Assignment In Cellular Networks

Abstract

A cellular network is often modelled as a graph and the channel assignment problem is formulated as a coloring problem of the graph. Sen et al. (1998) introduced the notion of cellular graphs that models the hexagonal cell structure of a cellular network. Assuming a k-band buffering system where the interference does not extend beyond k cells away from the call originating cell, we provided two different formulations of the channel assignment problem: Distance-k chromatic number problem and k-band chromatic bandwidth problem. The channel assignment algorithms presented in Sen et al. were non-optimal. In this paper we provide: (i) a new algorithm for the distance-k chromatic number problem that is optimal and (ii) a near optimal algorithm for the 2-band chromatic bandwidth problem that has a performance bound of 4/3. The complexity of the algorithms is O(p), where p is the number of cells.

Publication Date

1-1-1999

Publication Title

IEEE International Conference on Communications

Volume

2

Number of Pages

1147-1151

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/ICC.1999.765476

Socpus ID

84977862247 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84977862247

This document is currently not available here.

Share

COinS