The interference problem in multi-channel wireless networks

Alexandru Popa, National Institute for Informatics (ICI) and the University of Bucharest, Romania

Abstract: In a multi-channel wireless network, each node is able to use multiple non-overlapping frequency channels, by having more network interface cards. The use of many channels inside the same network can significantly improve overall performance; interference from neighboring nodes can be decreased substantially, when nodes do not need to use the same radio channel for every link.

The scenario of two or more NICs per node with fixed channels imposes some limitations to the assignment of channels on each interface. In order to set up a link between two nodes, both of them have to have at least one of their interfaces set to the same channel. On the other hand, links inside an interference range should use as many different channels as possible. Thus, the channels need to be assigned carefully in order to both keep every required link possible and maximize useful bandwidth throughout the network.

We model the channel assignment problem as a type of edge coloring problem: given a graph G, the edges have to be colored so that there are at most q different colors incident to each vertex. Here, vertices, edges and colors represent network nodes, links and channels, respectively. A coloring that satisfies this constraint, is called an edge q-coloring. We study two problems:

a) maximize the total number of distinct colors used.

b) the maximum size of a color group (i.e. set of edges identically colored) is minimized.

For each of these two problems we present polynomial time exact algorithms, approximation algorithms and hardness results.