Application of graph coloring algorithms to scheduling in CDMA and TDMA packet radio networks

摘要

The paper deals with a conflict free scheduling in packet radio networks with Time Division Multiple Access - TDMA, and Code Division Multiple Access - CDMA. Introducing adequate graph models for TDMA and CDMA, the scheduling problem is reduced to a graph coloring problem. Applicability of different graph coloring algorithms to scheduling is checked, and recommendations are made which algorithm to choose. An improvement of DSATUR algorithm has been proposed. A model for testing TDMA/CDMA networks has been proposed.