Andrew Chickadel                                      CSC-3990 Research Topic Proposal


An Approach to Channel Assignment in Wireless Networks: Vertex-Coloring and Edge-Coloring



The purpose of this research is to investigate vertex-coloring and edge-coloring graph methods that address the channel assignment problem for wireless networks.  Interference in wireless networks is commonly represented as an interference graph, with nodes representing wireless devices and edges representing potential interference between the endpoint nodes.  The problem of reducing collisions and signal interference is modeled as a coloring problem on the interference graph.  Nodes of different colors in the graph will be assigned separate channels of radio frequency.  Efficient coloring algorithms will lead directly to an effective channel selection method that lowers the wireless interference.



Signal interference is a major drawback of wireless networks.  This interference, or collision, could be reduced by careful assignment of communication channels of different radio frequencies to nodes in the network.  It is important to note that the number of radio frequencies is finite, and therefore, it is important to minimize the number of channels allocated to a specific network.  Current research efforts seek to determine a lower bound for the number of channels that can be used in a given wireless network.  Coloring methods that use a smallest number of channels address both issues of interference reduction and communication channels required.



C. McDiarmid, B. Reed, “Channel Assignment and Weighted Coloring,” Networks, Aug. 2000, vol. 36, no. 2, pp. 114-117.

[For purposes of reducing interference, this paper investigates weighted graph coloring, that is, assigning non-negative weights for each graph vector based on bandwidth usage demands. Each graph’s vertices are assigned different channels via coloring, and, colored properly, no two adjacent vertices can be colored the same.  Adjacent vertices, as defined in the paper, have a Euclidian distance of 1.  The authors only consider the most basic cases with respect to minimum separation.  The graphs are triangular lattices with hexagonal cells.  The authors express particular and exclusive interest in the coloring of finite induced subgraphs of the triangular lattice.  For an algorithm determining if such an induced subgraph of the triangular lattice G with a corresponding weight vector w, forming a graph Gw, is 3-colorable, the authors conclude a hardness result of NP-complete.  The maximum number of vertices of a complete subgraph of Gw can be found in polynomial time with each clique in G having no more than 3 vertices.  The authors found a local polynomial-time algorithm for coloring vertices on an induced subgraph of the triangular lattice G which uses no more than 4/3 times the number of colors presented by the corresponding number of clique vertices.  The authors note that for a 9-cycle graph, which is an induced subgraph of the triangular lattice, there is a 9/8 ratio of chromatic number to clique number.  One open question is whether or not the 9/8 ratio is the worst possible.  In addition, an open question remains in the possibility of improving on the 4/3 ratio for larger bandwidth demands.]



A. A. Bertossi, C. M. Pinotti, R. B. Tan, “Efficient use of radio spectrum in wireless networks with channel separation between close stations,” Workshop on Discrete Algorithms and Methods for MOBILE Computing and Communications and Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 2000, pp. 18-27.

[This paper equates two separate distinct coloring problems to the issue of interference.  The authors investigate optimal channel assignment with a minimal number of channels.  The problem requires that adjacent nodes be assigned channels that are at least 2 apart.  Additionally, in order for the same channel to be used on two vertices, those vertices must be 3 apart if following the criteria for the L(2,1) coloring problem and 4 apart if following the criteria for the L(2,1,1) coloring problem.  One problem formally defined in the paper is the channel assignment problem with separation (CAPS) which determines proper separation distance in order to reuse channels.  The CAPS problem is known in the paper to be NP-hard for general graphs.  The authors determine that, so long as a particular node in a graph knows its relative position, there is an algorithm for computing channel assignment locally which has an order of constant time for all networks except binary trees, which require logarithmic time.  One open question the authors identify is solving for an optimal solution for the general graph coloring problem with arbitrary channel reuse distance.]



K.N. Ramachandran, E. M. Belding, K.C. Almeroth, M.M. Buddhikot, “Interference-Aware Channel Assignment in Multi-Radio Wireless Mesh Networks,” Apr. 2006; 

[This recent paper addresses dynamic channel assignment in co-located and mesh wireless networks.  Rather than static assignment which assigns channels to transmitters one after another without any particular regard, dynamic assignment is the process of assigning channels based on the amount of interference received at each transmitter.  In order to address an arising problem of network topology alteration as a result of dynamic assignment, the authors introduce a fix by implementing a default radio channel throughout the entire network.  The default channel prevents nodes from being lost or disconnected should a vital connecting node fail or undergo a channel reassignment.  Through a process called link redirection, the default channel can carry both control traffic and data traffic until channels are reassigned and the connection is restored.  The authors equate the channel assignment problem for mesh networks to the list coloring problem, which happens to be NP-complete.  The authors are thus restricted to an approximation algorithm for channel assignment..  Their algorithm implements a breadth-first-search approach to award higher priority to the gateway nodes and assigns channels based on this priority. Subsequently, other nodes are assigned channels in decreasing levels of priority until the last nodes are reached.  The authors claim an excess of 40% improvement over static channel assignment in scenarios where one source at a time sends traffic to the gateway.  However, they admit that there is not substantial improvement in channel assignment in dense environments where the interference footprint is significantly larger.  There is future work in improving the performance in dense settings.]



S. Khanna, K. Kumaran, “On Wireless Spectrum Estimation and Generalized

Graph Coloring,” INFOCOM '98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, Apr 1998, vol. 3, pp. 1273-1283.

[This paper investigates the radio spectrum, that is, the minimum number of frequencies, required in a wireless network for purposes of eliminating interference.  The authors define the demand of a node as a set of colors or channels to be assigned to a  given node, such that interfering nodes do not share the same channel.  The authors note the difference between spectrum analysis and simple channel assignment as determining the minimum number of frequencies to assign rather than indiscriminately assigning any number of channels.  The main focus of this paper is to establish bounds for the spectrum in use in a given network. This problem is referred to as the wireless spectrum estimation problem.  The authors prove that for bipartite graphs, the bounds are tight and equal to the clique number, which is the number of nodes in the largest clique in the graph.  For perfect graphs, the authors prove that there is an exact lower bound of 4.5d where d is the demand value.  The authors determine that their algorithm for wireless spectrum estimation runs in polynomial time.  Some open questions remain in how to tighten the bounds generally for all graph types and how to develop more efficient algorithms for channel assignment.]


A. Mishra, S. Banerjee, W. Arbaugh, “Weighted Coloring Based Channel Assignment for WLANs,” ACM SIGMOBILE Mobile Computing and Communications Review, July 2005, vol. 9, no. 3, pp. 19-31.

[This is a recent paper which examines the weighted graph coloring problem to produce more efficient channel assignments in wireless networks.  The authors establish the weighted graph coloring problem and the constant approximation problem to be NP-hard, and they propose improved distributed channel assignment algorithms.  One of the authors’ two weighted channel assignment techniques involves a non-collaborative, greedy assumption that the access point will attempt to eliminate interference on its own within its own coverage area.  This algorithm is referred to as Hminmax and has two steps.  The first step is the initialization step where channels are assigned, and the second step is the optimization step where interference is reduced incrementally by determining the channel that simply would result in the least interference and performing the appropriate channel reassignment.  The other technique the authors present is a collaborative effort among access points.  In this paper, the authors evaluate their results by using an in-building wireless test network.  In scenarios testing the authors’ weighted channel assignment techniques with 3 non-overlapping channels yield a 45.5% reduction in interference in sparse networks.  Tests of the authors’ algorithms in dense topologies with non-overlapping channels yield up to a 56% reduction in interference.  In moderately-sized networks with partially overlapping channels, the authors achieve a 40% reduction in interference.  One area of future work  the authors note is to handle 802.11b and 802.11g access points together in the same coverage area, overlapping the interference graphs for each.]



Related Resources:

R. Battiti, A. A. Bertossi, M. A. Bonuccelli, “Assigning Codes in Wireless Networks: Bounds and Scaling Properties,” Wireless Networks, May 1999, pp. 195-209.


A. Raniwala, K. Gopalan, T. Chiueh, “Centralized Channel Assignment and Routing Algorithms for Multi-Channel Wireless Mesh Networks,” ACM SIGMOBILE Mobile Computing and Communications Review, Apr 2004, vol. 8 no. 2, pp. 50-65.