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 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.

__Motivation:__

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.

__Resources:__

**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 G _{w},
is 3-colorable, the authors conclude a hardness result of NP-complete. The maximum number of vertices of a complete
subgraph of G_{w} 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; http://www.cs.ucsb.edu/~ebelding/txt/infocom06.pdf. **

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

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