On some sufficient conditions for distributed QoS support in wireless networks

Abstract

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 distributed implementations which have low communication overhead and low processing complexity. Row constraints are known to be sufficient, and we introduce the notion of the induced star number of a graph and show that this quantity determines the performance of this condition. We further investigate this problem for some special classes of networks and interference models such as unit disk networks and primary interference constraints. We determine the exact worst-case performance of some distributed algorithms for admission control and thereby show that they can be arbitrarily far away from optimal; we then show that these algorithms are within a bounded factor away from optimal for some well known classes of networks and interference models.