Speaker: Sixia Chen
Day:  Wednesday, 4/02/2008
Room: ITEB 336
Time: 1:00-2:00pm

Title: Distance-1 Constrained Channel Assignment in Single
Radio Wireless Mesh Networks

Abstract: This paper addresses channel assignment and random medium
access design for single-radio multi-channel mesh networks. We first
introduce D1C-CA, Distance-1 Constrained Channel Assignment. D1C-CA
statically assigns channels to a set of links as a function of
physical connectivity, contention, and the unique gateway
functionality of mesh networks. To design D1C-CA, we model the channel
assignment problem as a new form of graph edge coloring in which edges
at distance one are constrained. We prove that the problem is
NP-complete and design an efficient heuristic solution for mesh
networks. Second, we design an asynchronous control-channel-based MAC
protocol that solves multi-channel coordination problems and employs
the proposed channel assignment algorithm.

Reference:  E. Aryafar, O. Gurewitz and E. Knightly, "Distance-1
Constrained Channel Assignment in Single Radio Wireless Mesh
Networks," in Proceedings of IEEE INFOCOM 2008, Phoenix, AZ, April
2008.