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 apply the vertex-coloring and edge-coloring graph problem to address channel assignment.  By investigating the vertex and edge-coloring problems, increasingly more efficient coloring algorithms can be identified and explored.

Better algorithms will yield more effective channel selection and decreased interference.



Interference is a major drawback of wireless networks.  An interesting approach can be found by investigating the practical applications of the general vertex-coloring or edge-coloring problem to reduce signal collision and interference.  The coloring problem is theoretical.  The purpose of “coloring” is to assign separate channels of radio frequency.  It is important to note that the number of radio frequencies available is not infinite, and there are also efforts to determine a lower bound of channels that can be used in a given wireless network.  Research is needed for developing more efficient, feasible, and practical “coloring” or channel assignment algorithms.




R. Battiti, A. A. Bertossi, M. A. Bonuccelli, “Assigning Codes in Wireless Networks: Bounds and Scaling Properties,” Wireless Networks, May 1999, pp. 195-209. [The authors explain interference or packet “collision” in great detail.  This paper explores algorithms for special-case network topologies as well as general case topologies.  This paper presents new upper and lower bounds for the coloring problem.  The authors also develop a graph of what they call “scaling law” which compares scaled curves and real curves for a given number of stations.]


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

[This paper investigates weighted coloring on triangular lattices.  The authors use basic cases for approaching the “channel assignment problem” as they refer to it, equating it to a weighted coloring problem.  The result of the paper yields a hardness result and an efficient algorithm.  These results are achieved by developing a proof for a hardness theorem and a proof for an “ algorithmic approximation.”]


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 paper determines that channel assignment can be computed locally so long as the particular node knows its relative position.  The paper’s results can be extended to three other known coloring problems.]


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 channel assignment in co-located and mesh wireless networks.  The authors devise an updated algorithm and  protocol addressing interference in mesh networks.  The paper contains real testing scenarios which the authors have documented in the paper using various charts and graphs.  The tests yielded a 40% improvement over static channel assignment.]


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 utilized in a wireless network for purposes of reducing interference.  The authors note the differences between spectrum analysis and simple channel assignment.  The main focus of this paper is to establish bounds for the spectrum in use in a given network.  The authors develop an algorithm which respects the bounds they discovered with regard to hexagonal grids.]


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. 

[This relatively recent paper addresses multi-channel wireless networks and explores how to centralize the process of channel assignment.  The authors propose one of the first “multi-channel multi-hop” wireless ad-hoc network using construction of a network where each node has multiple wireless network interface adapters.  The authors test their results using real networks in multiple test scenarios.  They produce a result that they claim to be eight times faster than conventional ad-hoc networks.]


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’ proposals involve new methods of channel re-use for assignment.  The authors establish a proven hardness result for the weighted graph coloring problem as being NP-hard and improved channel assignment algorithms.  In this paper, the authors evaluate their results by using an in-building wireless test network.  The test results are detailed in the paper.]