Title: Frequency Assignment in FDMA-based Wireless Networks

Speaker: Sunil Shende
         Dept. of CS
         Rutgers University, Camden.

Abstract: 

Wireless networks for telecommunications and mobile computing have become
commonplace. In such a network, the coverage area is divided into cells and
communication across cells or within cells is accomplished by using channels
(or frequency subbands) from specified portions of the EM spectrum. The limited
range of available frequencies is to be allocated and shared among individual
calls in the network so as to minimize radio interference among spatially
proximate calls. In this talk, we focus on a simple hexagonal-lattice based
model for a wireless network using frequency division multiplexing
(FDMA). Channel allocation problems in this framework - under reasonable
abstractions of interference constraints - can be posed as graph multicoloring
problems.  

Such coloring problems, even when limited to the hexagon graph model, are
intractable and hence, exact solutions are extremely hard to find in reasonable
time. However, we show that it is possible to obtain fast, constant-factor
approximations to optimal assignment for both offline and online versions of
the problem. The talk will survey a few of the algorithms used to obtain the
approximations, and provide an brief overview of some lower bounds on
approximability in this setting.


Biosketch:

Sunil Shende did undergraduate work in Computer Science at the Indian Institute
of Technology at Kanpur (1979-1984) prior to obtaining a doctorate at the 
University of Pennsylvania in 1990. From 1990 through 1998, he was on the
faculty of the CS&E dept. at the University of Nebraska in Lincoln. 
He is currently an Associate Professor in the Department of Computer Science at
Rutgers University, Camden. His research interests are in resource management
in wireless networks; inteconnection network configuration, routing and
scheduling; image encoding and compression; and online algorithm design.