Andrew Chickadel CSC-3990 Research
Topic Proposal

__Topic:__

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

__Description:__

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.

__Motivation:__

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.

__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. [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; http://www.cs.ucsb.edu/~ebelding/txt/infocom06.pdf. **

*[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 **

*[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,” A**

*[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.]*