Graph coloring based physical-cell-ID assignment for LTE networks

Autoconfiguration of the radio parameters is a key feature for next generation mobile networks. Especially for LTE the NGMN Forum has brought it up as a major requirement. It is indispensable that algorithms used for autoconfiguration terminate quickly and do not cause infinite iterative reconfigurations within the network. Reference signal sequences are among the most important radio parameters for LTE, which are comparable to scrambling codes in 3G networks. In LTE they additionally serve as Cell Identifiers on the Physical Layer. Each cell is assigned one of the 504 available Physical Cell Identifiers. For proper operation the assignment has to be as well collision as also confusion free. Due to the high number and the layered structure of the cells within the network such an assignment is a complex task. In addition to this complexity each change of the Physical Cell ID of an operational cell causes a service interruption in the cell, which has to be avoided. The approach presented maps the ID assignment problem to the well known and well understood problem of graph coloring. It is shown that an efficient initial assignment even for complex networks is possible. Cells added during the subsequent network growth, can already be confused when inserted into the network. In this case the IDs of the operational cells causing the confusion must be changed. As a next logical step the incremental approach shows how the properties of the colored graph can be used for extending the network with new cells, with only minimal interruption while still retaining the properties of a colored graph.