Channel assignment in mobile networks based on geometric prediction and random coloring

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.