A Graph-coloring based resource allocation algorithm for D2D communication in cellular networks

This paper considers the resource allocation problem for device-to-device (D2D) communication underlaying cellular networks. In particular, we consider a system scenario where the number of D2D users is larger than that of cellular users. To address this scenario, we propose to not only allow one D2D pair to share the resources of multiple cellular users, but also allow one cellular user to share its resources with multiple D2D pairs. We formulate the resource allocation problem as a mixed integer non-linear programming (MINLP) problem with the objective to maximize the system capacity. To solve the problem, we propose a heuristic Graph-coloring resOurce ALlocation (GOAL) algorithm based on a graph-coloring approach, where the D2D pairs in the system are viewed as a set of vertexes and the resources of cellular users are viewed as a set of colors. To support resource allocation, GOAL introduces the concept of the interference negligible distance (INS) to identify those D2D pairs can simultaneously share the same spectrum resources of cellular users, and the concept of the signal to interference ratio (SIR) limited area (SLA) to identify a set of D2D pairs that cannot share the spectrum resources of a particular cellular user. Simulation results show that the proposed GOAL algorithm can significantly improve the system capacity and accommodate more D2D users.