Upper and lower bounds of Choice Number for successful channel assignment in cellular networks

A cellular network is often modeled as a graph and the channel assignment problem is formulated as a coloring problem of the graph. Cellular graphs are used to model hexagonal cell structure of a cellular network. Assuming a 2-band buffering system where the interference does not extend beyond two cells away from the call originating cell, we study a version of the channel assignment problem in cellular graphs that been studied only minimally. In this version, each node has a fixed set of frequency channels where only a subset of which may be available at a given time for communication (as other channels may be busy). Assuming that only a subset of frequency channels are available for communication at each node, we try to determine the size of the smallest set of free channels in a node that will guarantee that each node of the cellular graph can be assigned a channel (from its own set of free channels) that will be interference free in a two band buffering system. The mathematical abstraction of this problem is known as the Choice Number computation problem and is closely related to the List Coloring problem in Graph Theory. In this paper we establish a lower and an upper bound of the distance-2 Choice Number of cellular graphs. In addition we also conduct extensive experimentation to study the impact of the availability of the number of free channels in a node to the percentage of the total number of nodes in the network that can be assigned an interference free channel in a two band buffering system.