Resource Allocation for Underlaying Device-to-Device Communications Using Maximal Independent Sets and Knapsack Algorithm

In this paper, we address the resource allocation problem of device-to-device (D2D) communications underlaying orthogonal frequency division multiple access (OFDMA) based cellular systems by exploiting the efficiency that comes from an ensemble of graph theory and Knapsack problem. It is possible to construct the conflict graph of the D2D pairs by finding the maximal independent sets. Then, we use those independent sets as inputs to Knapsack problem iteratively in order to find D2D groups which allocate the subchannels. In Knapsack problem, we consider a maximum interference level that the base station is exposed at each subchannel. We illustrate that the proposed resource allocation method significantly outperforms graph coloring in terms of average data rate for the high number of underlaying D2D pairs in cellular systems.