On minimum-collisions assignment in heterogeneous self-organizing networks

Minimum-collisions assignment (MCA), in a wireless network, is the distribution of a finite resource set, such that the number of neighbor cells which receive common elements is minimized. In classical operator deployed networks, resources are assigned centrally. Heterogeneous networks contain user deployed cells, therefore centralized assignment is problematic. MCA includes orthogonal frequency bands, time slots, and physical cell identity (PCI) allocation. MCA is NP-complete, therefore a potential-game-theoretic model is proposed as a distributed solution. The players of the game are the cells, actions are the set of PCIs and the cost of a cell is the number of neighbor cells in collision. The price of anarchy and price of stability are derived. Moreover the paper adapts a randomized-distributed-synchronous-update algorithm, for the case, when the number of PCIs is higher than the maximum degree of the neighbor relations graph. It is proven that the algorithm converges to a optimal pure strategy Nash equilibrium in finite time and it is robust to node addition. Simulation results demonstrate that the algorithm is sub-linear in the size of the input graph, thus outperforms best response dynamics.