Simulated annealing variants for self-organized resource allocation in small cell networks

• Small cell networks can be effectively modeled using planar graphs.
• Distributed graph coloring can enable self-organized orthogonal resource allocation.
• Simulated annealing variants are important metaheuristics for distributed coloring of planar graphs.

This paper discusses the application of simulated annealing (SA) based meta-heuristics to self-organized orthogonal resource allocation problems in small cell networks (SCN)s, for static and dynamic topologies. We consider the graph coloring formulation of the orthogonal resource allocation problem, where a planar graph is used to model interference relations in a SCN comprising of randomly deployed mutually interfering cells. The aim is to color the underlying conflict graph in a distributed way, for which different variants of SA such as SA with focusing heuristic (i.e., limiting the local moves only to the cells that are in conflict), and fixed temperature, are investigated. For static topologies, distributed algorithms are used, in which no dedicated message-passing is required between the cells, except for the symmetrization of conflict graph. To enable distributed SA in dynamic topologies, a distributed temperature control protocol based on message-passing is considered. Different aspects relevant to self-organizing cellular networks are analyzed using simulations. These include the number of cells with resource conflicts, number of resource reconfigurations required by the cells to resolve the conflicts, requirements on dedicated message-passing between the cells, and sensitivity to the temperature parameter that guides the stochastic search process. Simulation results indicate that the considered algorithms are inherently suitable for SCNs, thereby enabling efficient resource allocation in a self-organized way. Furthermore, the underlying concepts and the key conclusions are general, and relevant to other problems that can be solved by distributed graph coloring.

Figure optionsDownload as PowerPoint slide