Abstract:

In this talk, we address a basic question in wireless
communication: How long does it take to satisfy an arbitrary set
of wireless communication requests? This problem is known as the
wireless scheduling problem. This is a question of spatial reuse,
to avoid interference between requests.

A key issue is the choice of the model of interference. The model of
choice for engineers -- the physical or SINR model -- has been viewed
as too complex, so most worst-case analysis has been performed in less
realistic models.

We shall show that the SINR model is actually quite robust, allowing
for elimination of several parameters, and making it amenable for
analytic treatment.  We will discuss several recent results, including
the first constant factor approximation for scheduling arbitrary links
under fixed transmission power.  This is joint work with Roger
Wattenhofer of ETH Zurich.