  Given a wireless network where some pairs of communication links interfere
with each other, we study sufficient conditions for determining whether a given
set of minimum bandwidth Quality of Service (QoS) requirements can be
satisfied. We are especially interested in algorithms which have low
communication overhead and low processing complexity. The interference in the
network is modeled using a conflict graph whose vertices are the communication
links in the network. Two links are adjacent in this graph if and only if they
interfere with each other due to being in the same vicinity and hence cannot be
simultaneously active. The problem of scheduling the transmission of the
various links is then essentially a fractional, weighted vertex coloring
problem, for which upper bounds on the fractional chromatic number are sought
using only localized information. We present some distributed algorithms for
this problem, and discuss their worst-case performance. These algorithms are
seen to be within a bounded factor away from optimal for some well known
classes of networks and interference models.
