Back to BMAC Page
Routing and Link Scheduling in Ad Hoc Networks
Packet-scheduling is a particular challenge in wireless networks
due to interference from nearby transmissions. We use a
combinatorial abstraction for radio interference, based
on distance-2 matching in a graph, and develop algorithms
for packet scheduling and routing. Our main goal is to
develop a unified protocol that has provable performance
guarantees for the MAC and routing layers together.
We present polylogarithmic/constant factor approximation algorithms
for various families of disk graphs (which capture the geometric
nature of wireless-signal propagation), as well as near-optimal
approximation algorithms for general graphs. Our algorithms are
based on a generalization of the classical result of Leighton,
Maggs and Rao, coupled with a new notion of congestion for
disk graphs. We also consider
the problem of computing a distance-2 matching in disk
graphs, and obtain distributed algorithms that give
a constant factor approximation, in logarithmic number of
rounds, even in the presence of radio interference.
Biography
V.S. Anil Kumar is currently a Technical Staff Member at the Los
Alamos National Laboratory. He got a Ph.D. in Computer Science
from the Indian Institute of Science, Bangalore, India. After that he
was a postdoc at the Max-Planck Institut for Computer Science,
Saarbrucken, Germany. He is interested in randomized and approximation
algorithms, mobile computing, combinatorial optimization and algorithmic
game theory.
Back to BMAC Page