An efficient code assignment algorithm for multihop spread spectrum packet radio networks

Multihop spread-spectrum packet radio networks (PRNs) with a large number of stations would require a large number of codes, even with code reuse beyond the interference range. It is important to find an efficient algorithm for assigning as few codes to the PRN stations as possible, since the smaller the number of codes used the smaller the bandwidth needed. The code assignment problem in transformed to the familiar graph coloring problem. A heuristic code assignment algorithm, making use of some special properties of PRNs, is designed. A lower bound on the chromatic number, which is the minimum number of codes required, is obtained. The performance of this algorithm is assessed by making comparisons to the bound as well as to one of the best heuristics for graph coloring