Channel Assignment Problem in a Cellular Mobile System and a New Coloring Problem of Networks

Hiroshi TAMURA; Masakazu SENGOKU; Shoji SHINODA; Takeo ABE

Channel Assignment Problem in a Cellular Mobile System and a New Coloring Problem of Networks

Hiroshi TAMURA, Masakazu SENGOKU, Shoji SHINODA, Takeo ABE

Full Text Views

0

Cite this

Summary :

In a cellular mobile system, assigning a channel for a call in a cell so as to achieve high spectral efficiency is an important problem. In usual channel assignment for a cellular mobile system, a channel can be simultaneously assigned to some cells with a constant separation distance. This usual model of a cellular mobile system has been formulated using a graph and it is known that the channel assignment problem is equivalent to the coloring problem of graph theory. Recently, a new channel assignment scheme has been proposed. This scheme takes the degree of interference into consideration. In the scheme, a channel is simultaneously assigned if the CIR (carrier-to-interference ratio) is more than the desired value. In this paper, we formulate this new model using a network and a new coloring problem of networks. The new coloring problem of networks is a generalization of the usual coloring problem of graphs. One of the merits of this formulation is that the degree of cochannel interference between cells can be represented. In the usual formulation using a graph, the degree of cochannel interference between cells can not be represented. Therefore, spectral efficiency in the formulation using a network is higher than spectral efficiency in the formulation using a graph. In this paper, we show that the new coloring problem is an NP-hard problem. Subsequently, we rewrite the new coloring problem of networks to a coloring problem of graphs on some assumptions and consider the relation between the results on the new coloring and the results on the usual coloring.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E74-A No.10 pp.2983-2989

Publication Date: 1991/10/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on JTC-CSCC '90)

Category: Communication Theory

Authors

Hiroshi TAMURA
Masakazu SENGOKU
Shoji SHINODA
Takeo ABE

Keyword

Cite this

Copy

Hiroshi TAMURA, Masakazu SENGOKU, Shoji SHINODA, Takeo ABE, "Channel Assignment Problem in a Cellular Mobile System and a New Coloring Problem of Networks" in IEICE TRANSACTIONS on Fundamentals, vol. E74-A, no. 10, pp. 2983-2989, October 1991, doi: .
Abstract: In a cellular mobile system, assigning a channel for a call in a cell so as to achieve high spectral efficiency is an important problem. In usual channel assignment for a cellular mobile system, a channel can be simultaneously assigned to some cells with a constant separation distance. This usual model of a cellular mobile system has been formulated using a graph and it is known that the channel assignment problem is equivalent to the coloring problem of graph theory. Recently, a new channel assignment scheme has been proposed. This scheme takes the degree of interference into consideration. In the scheme, a channel is simultaneously assigned if the CIR (carrier-to-interference ratio) is more than the desired value. In this paper, we formulate this new model using a network and a new coloring problem of networks. The new coloring problem of networks is a generalization of the usual coloring problem of graphs. One of the merits of this formulation is that the degree of cochannel interference between cells can be represented. In the usual formulation using a graph, the degree of cochannel interference between cells can not be represented. Therefore, spectral efficiency in the formulation using a network is higher than spectral efficiency in the formulation using a graph. In this paper, we show that the new coloring problem is an NP-hard problem. Subsequently, we rewrite the new coloring problem of networks to a coloring problem of graphs on some assumptions and consider the relation between the results on the new coloring and the results on the usual coloring.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e74-a_10_2983/_p

Copy

@ARTICLE{e74-a_10_2983,
author={Hiroshi TAMURA, Masakazu SENGOKU, Shoji SHINODA, Takeo ABE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Channel Assignment Problem in a Cellular Mobile System and a New Coloring Problem of Networks},
year={1991},
volume={E74-A},
number={10},
pages={2983-2989},
abstract={In a cellular mobile system, assigning a channel for a call in a cell so as to achieve high spectral efficiency is an important problem. In usual channel assignment for a cellular mobile system, a channel can be simultaneously assigned to some cells with a constant separation distance. This usual model of a cellular mobile system has been formulated using a graph and it is known that the channel assignment problem is equivalent to the coloring problem of graph theory. Recently, a new channel assignment scheme has been proposed. This scheme takes the degree of interference into consideration. In the scheme, a channel is simultaneously assigned if the CIR (carrier-to-interference ratio) is more than the desired value. In this paper, we formulate this new model using a network and a new coloring problem of networks. The new coloring problem of networks is a generalization of the usual coloring problem of graphs. One of the merits of this formulation is that the degree of cochannel interference between cells can be represented. In the usual formulation using a graph, the degree of cochannel interference between cells can not be represented. Therefore, spectral efficiency in the formulation using a network is higher than spectral efficiency in the formulation using a graph. In this paper, we show that the new coloring problem is an NP-hard problem. Subsequently, we rewrite the new coloring problem of networks to a coloring problem of graphs on some assumptions and consider the relation between the results on the new coloring and the results on the usual coloring.},
keywords={},
doi={},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - Channel Assignment Problem in a Cellular Mobile System and a New Coloring Problem of Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2983
EP - 2989
AU - Hiroshi TAMURA
AU - Masakazu SENGOKU
AU - Shoji SHINODA
AU - Takeo ABE
PY - 1991
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E74-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 1991
AB - In a cellular mobile system, assigning a channel for a call in a cell so as to achieve high spectral efficiency is an important problem. In usual channel assignment for a cellular mobile system, a channel can be simultaneously assigned to some cells with a constant separation distance. This usual model of a cellular mobile system has been formulated using a graph and it is known that the channel assignment problem is equivalent to the coloring problem of graph theory. Recently, a new channel assignment scheme has been proposed. This scheme takes the degree of interference into consideration. In the scheme, a channel is simultaneously assigned if the CIR (carrier-to-interference ratio) is more than the desired value. In this paper, we formulate this new model using a network and a new coloring problem of networks. The new coloring problem of networks is a generalization of the usual coloring problem of graphs. One of the merits of this formulation is that the degree of cochannel interference between cells can be represented. In the usual formulation using a graph, the degree of cochannel interference between cells can not be represented. Therefore, spectral efficiency in the formulation using a network is higher than spectral efficiency in the formulation using a graph. In this paper, we show that the new coloring problem is an NP-hard problem. Subsequently, we rewrite the new coloring problem of networks to a coloring problem of graphs on some assumptions and consider the relation between the results on the new coloring and the results on the usual coloring.
ER -