Improving bandwidth in wireless mesh networks
ICE-TCS seminar
Date and time: Tuesday, 4 September 2018 from 12:10 till 13:00
Place: Room V1.04 at Reykjavik University
Speaker: Alex Popa (Faculty of Mathematics and Computer Science, University of Bucharest, Romania)
Title: Improving bandwidth in wireless mesh networks.
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.
