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

ABSTRACT

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 as 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.

REFERENCES

• 1: Hamid Akhavan et al., "Next Generation Mobile Networks - Beyond HSPA & EVDO - Whitepaper," Tech. Rep., NGMN Ltd. - www.ngmn.org, 2006.
• 2: "Socrates - FP7 - http://www.fp7-socrates.org," 02.12.2008.
• 3: 3GPP, "3GPP TS 36.211 V8.4.0," Technical Specification Release 8, 3GPP, 09 2008.
• 4: 3GPP, "3GPP R3-082218," TDOC Automatic Physical Layer Cell Identity Allocation, 3GPP, 08 2008.
• 5: 3GPP, "3GPP S5-081185," TDOC Automatic Physical Cell ID Assignment, 3GPP, 07 2008.
• 6: M. et al. Amirijoo, "Neighbor cell relation list and measured cell identity management in lte," Network Operations and Management Symposium, 2008. NOMS 2008. IEEE, pp. 152--159, April 2008.
• 7: Andreas Eisenblätter, "Assigning Frequencies in GSM Networks," Tech. Rep., 2003.
• 8: R. M. Karp, "Reducibility among combinatorial problems," in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds., pp. 85--103. Plenum Press, 1972.
• 9: D. J. A. Welsh and M. B. Powell, "An upper bound for the chromatic number of a graph and its application to timetabling problems," The Computer Journal, vol. 10, no. 1, pp. 85--86, 1967.
• 10: "Graph Coloring Algorithm - http://web.cecs.pdx.edu/posj/graph/graph.html," 02.12.2008.
• 11: "Base Station List - http://gsm.schnurstein.de/download/senderliste_obdg.kmz," 01.09.2008.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.m MISCELLANEOUS

General Terms:
Algorithms, Management, Reliability

Keywords:
LTE, graph coloring, management, physical cell ID