We formulate the joint power and channel allocation problem (JPCAP) for device to device (D2D) communication as a cost minimization problem, where cost is defined as a linear combination of the number of channels used and total power requirement. We first show that JPCAP is NP-hard and then propose a greedy channel and power allocation (GCPA) algorithm to assign channels and powers to the links. We design GCPA in such a fashion that there exists an order of the links for which it produces optimum solution. Finally using GCPA we develop a randomized algorithm (RA) that increase the optimum hitting probability by an exponential factor of total number of links. Through simulation, we evaluate the performance of RA and show that RA outperforms an existing approach.

The channel assignment problem in mobile networks can be modeled as a temporal graph coloring problem where a temporal graph represents a sequence of graphlets generated over a regular interval of time. The cost of coloring a graphlet is defined as a function of number of colors used in the current graphlet and the number of color changes from the previous graphlet. A differential coloring technique is proposed which first finds the minimum number of vertices that requires recoloring and then recolor them. A prediction based and a random coloring based approaches are proposed to reduce the cost. In prediction based approach, we predict a graph which is a supergraph of the graph representing the union of current and next k graphlets and then color it. Whereas, in random coloring we color the graphlets individually. We have shown that both approaches perform better than an existing SNAP algorithm.

This paper presents a probabilistic greedy algorithm for solving the channel assignment problem (CAP) in cellular networks. We took each call as a vertex of a complete edge weighed graph, termed as CAP graph, where an edge weight represents the minimum frequency separation needed between the calls represented by the terminal vertices of that edge. Our objective is to assign non-negative integers representing colors or frequencies to the vertices of the CAP graph such that the required span (maximum frequency - minimum frequency) is minimized while satisfying the frequency separation constraints represented by the edge weights. We begin with a probabilistic ordering of the vertices and apply frequency exhaustive strategy to color them. During the coloring, when color of a vertex exceeds the maximum color of previously allocated vertices, we apply a forced assignment phase to reduce the so far obtained span. Finally we propose an iterative compression phase to further reduce the span obtained from applying the frequency exhaustive strategy with forced assignment phase. The proposed polynomial time algorithm is then applied over the well-known benchmark instances and the obtained spans are measured. The obtained results show that the proposed algorithm performs better that the existing assignment strategies with respect to deviation from optimality and computation time. The time taken by our algorithm is less than 1.77 seconds (HP Z400 Workstation) even for the most difficult benchmark instances and thus is very much suitable where fast channel assignment is of primary importance while a marginal deviation from optimality may be tolerated.