Given a wireless network where some pairs of communication l inks interfere with each other, we study suﬃcient conditions for determining whethe r a given set of minimum bandwidth Quality of Service (QoS) requirements can be sati sﬁed. We are especially interested in distributed implementations which have low c ommunication overhead and low processing complexity. Row constraints are known to be s uﬃcient, and we introduce the notion of the induced star number of a graph and show that t his quantity determines the performance of this condition. We further investigate t his problem for some special classes of networks and interference models such as unit dis k networks and primary interference constraints. We determine the exact worst-ca se performance of some dis- tributed 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. Index terms — Quality of service (QoS), admission control, distributed algorithms, inter- ference, wireless networks, conﬂict graph, link schedulin g. Contents 1 Introduction 2 1.1 Model and problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Prior work and our contributions . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Row constraints 6 2.1 Row constraint polytope and induced star number . . . . . . . . . . . . . . 7 2.2 A strengthening of the row constraints . . . . . . . . . . . . . . . . . . . . . 8 3 Degree and mixed conditions 10 4 Clique constraints 14 5 Examples 15 5.1 Primary interference model . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.2 Unit disk networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 6 Concluding remarks 18 ∗The author was with the ECE Department, University of Wiscon sin at Madison, Madison, WI 53706, USA. Correspondence address: ashwin.ganesan@gmail.com . 1 1. Introduction In recent years there has been an increasing interest in usin g data networks to support a wide variety of applications, each requiring a diﬀerent Quality of Service (QoS). For example, real-time applications such as voice, video and industrial control are time-sensitive and require that the delay be small, while for other data applica tions the sender may require that a constant, minimum bit-rate service be provided. In th e simplest and lowest level of service, such as the one provided in the Internet Protocol se rvice model, the network makes a best-eﬀort to deliver data from the source to destination, but it makes no guarantees of any kind, so it is possible that packets can get dropped, de layed, or delivered out of order. However, this basic level of service is insuﬃcient fo r many data applications such as videoconferencing that also have a minimum bandwidth requi rement. We consider in this work applications requiring a minimum bandwidth quality-o f-service. Consider a wireless communication network where nodes (whi ch represent wireless devices such as laptops, phonoes, routers, sensors, etc) wish to com municate with each other using a shared wireless medium. Any given pair of nodes may make a req uest for a dedicated point- to-point link between them that supports their required bit -rate Quality of Service. The objective of the the admission control mechanism is to decide whether the desired service can be provided, given the available resources, without dis rupting the service guaranteed to previously admitted demands. This mechanism needs to tak e into account the fact that nodes in the same vicinity contend for the shared wireless me dium and hence can cause interference if simultaneously active. Also, for reasons s uch as low communication overhead and scalability, it is desired that this decision be made in s ome decentralized fashion. Thus, each node may have access only to information pertaining to i ts local neighborhood and not about the entire communication network. These two requirem ents - that the decision take into account interference due to neighboring nodes and that it be made in a decentralized manner - are crucial aspects of the particular problem we stu dy. If a decision to admit a demand is made, the scheduling problem is to schedule the transmissions of the various nodes so as to provide the service level that was guaranteed. The focus of most of our work here is on the admission control problem and not the sche duling problem. For an introduction to the ﬂow admission control problem, see [1]. More formally, the wireless network model and desired QoS ar e speciﬁed as follows. Let V be a set of nodes and L⊆V×Vbe a set of communication links. Each link ( i,j)∈Lmakes a demand (to transmit information from itoj) at a rate of f(u,v) b/s. The total bandwidth of the shared wireless medium available for the communicati on network G= (V,L) isCb/s. The main problem studied here is to determine whether a set of demands ( f(ℓ) :ℓ∈L) can be satisﬁed. Of course, if all the links can be simultaneo usly active, the set of demands (f(ℓ) :ℓ∈L) can be satisﬁed as long as each individual demand is at most C. However, due to interference eﬀects nodes in the same vicinity contend fo r the shared wireless medium and hence cannot be active at the same time. For example, in IE EE 802.11 MAC protocol- based networks, any nodes adjacent to node ior to node jare required to be idle while the communication ( i,j) takes place. (The reason for this constraint is that when th e communication from utovtakes place, valso sends acknowledgement of the receipt of information back to u, so nodes adjacent to vcannot receive information from other nodes during this time due to interference.) We will use a more gene ral interference model which includes this special case and which is still tractable enou gh for further study. 2 The interference in the network is modeled using a conﬂict graph . Given a network graph G= (V,L), deﬁne its conﬂict graph to be GC= (L,L′), where two links ℓ1andℓ2are adjacent in the conﬂict graph if and only if they cannot be sim ultaneously active. This interference model has been studied recently by a number of a uthors; for example, see Jain et al [10], Hamdaoui and Ramanathan [9], and Gupta, Musacchi o and Walrand [5]. A special case of this model, where two links are considered to be interfering if and only if they are incident (in the network graph) to a common node, has been studied earlier by Hajek [6], Hajek and Sasaki [7], and Kodialam and Nadagopal [ 11]. While we will study the more general model, it still does not incorporate parame ters such as the actual signal- to-interference-and-noise ratio at the receiver node in it s decision making process. In our work below we will also revisit the special case just mention ed and obtain some new results in the distributed setting. The notion of a conﬂict or interference graph was introduced earlier, outside the context of wireless networks, by Chaitin [3] for solving the register a llocation problem. A register is a high-speed memory location on a computer’s CPU and the regis ter set is usually of a very limited size and much faster compared to ordinary memory. Du ring the register allocation phase of compiling, a decision needs to be made as to which val ues to keep in registers and which to keep in memory at each point in the object code. One ap proach is for the compiler to construct a conﬂict graph, where the vertices of this grap h correspond to values, and there is an edge between two vertices if and only if the two val ues are simultaneously live at some point in the code. A coloring of a graph is an assignmen t of one color to each vertex so that adjacent nodes are assigned diﬀerent colors. If it is not possible to color the conﬂict graph using rcolors, where ris the number of registers available for use, then one of the nodes (variables) is moved to memory and deleted from t he conﬂict graph, and a valid coloring is again attempted. Many commercial and rese arch compilers use a coloring approach on the conﬂict graph to solve the register allocati on problem. In the context of wireless networks, the notion of coloring t he conﬂict graph has been used to study the spectrum allocation problem in cellular co mmunications [8]. In this setting, the vertices of the conﬂict graph correspond to bas e stations. Two vertices are adjacent iﬀ the corresponding base stations are close enoug h to interfere while using the same frequency. Each base station represents its area of ser vice (such as a hexagonal region in the plane) and makes a demand for a certain number of freque ncies which is proportional to the traﬃc demand for that region. The frequency assignmen t problem is to assign a set of frequencies (colors) to each base station, so that the demand for each base station is met, so that interfering base stations are assigned nonov erlapping sets, and so that the minimum number of frequencies is used. This problem is essen tially equivalent to a problem sometimes referred to as the weighted vertex coloring probl em. In the admission control problem studied in this work, the ve rtices of the conﬂict graph correspond to links in the communication network. The quali ty-of-service metric is speciﬁed in terms of the bandwidth desired by each link. This gives ris e to one demand value for each vertex of the conﬂict graph, and this value could pos sibly be non-integral. The admission control problem is then to determine whether thes e demands can be satisﬁed using a speciﬁed amount of resource (total available bandwidth). This problem is diﬀerent from the classical weighted vertex coloring problem in some ways . First, fractional solutions to the coloring problem are also admissible, as indicated by the li near programming formulation 3 given below. Second, our emphasis is on decisions that can be made in a decentralized manner, i.e. using only localized information. Finally, th e conﬂict graph sometimes has additional structure derived from the structure of the link s in the network or the interference model. The admission control problem studied here is essent ially that of obtaining, using only localized information, an upper bound on the resource r equired to satisfy a demand pattern. The scheduling problem, which we do not study here, concerns how these resources are actually allocated or managed. This paper is organized as follows. The admission control pr oblem studied here is formulated precisely in Section 1.1. Decentralized solutions to this p roblem are then studied: Section 2 is on the row constraints, Section 3 is on the degree and mixed conditions, and Section 4 is on the clique constraints. These results provide suﬃcient con ditions and distributed algorithms for admission control. The main new results here concern the worst-case performance of these algorithms. Finally, in Section 5 the results obtai ned thus far are applied to some speciﬁc examples such as unit disk networks and network s with primary interference constraints. In order to keep this paper as self-contained a nd accessible as possible, we recall along the way some of the known results and their proof s from the literature. 1.1. Model and problem formulation We ﬁrst state the ﬂow control problem formally. Then, in orde r to avoid repeating trivialities throughout the paper, we will present an equivalent reformu lation of the problem that ignores many of the constants and variables and involves jus t the essential details. We will work only with this reformulation in the rest of this paper. LetG= (V,L) be a network graph, where L⊆V×V. Each link ℓ∈Lhas a maximum transmission capacity of Cℓb/s, and there is a demand to use that link at some rate f(ℓ) b/s. The total available bandwidth of the shared wireless medium isCb/s. The conﬂict graph GC= (L,L′) speciﬁes which pairs of links interfere with each other. Th e main problem we study is to determine, using only localized information, whether the set of demands (f(ℓ) :ℓ∈L) can be satisﬁed. More precisely, an independent set of a gra phGC= (L,L′) is a subset I⊆Lof elements that are pairwise nonadjacent. If the set of link s that are simultaneously active is an independent set, then these lin ks cause no interference with each other and can have (a part of) their demands satisﬁed during t he same time slot. Let I(GC) denote the set of all independent sets of GC. [Note that this set can grow exponentially with the size of the graph. For example, a graph on nvertices consisting of n/3 disjoint triangles has 3n/3≈1.4nmaximal independent sets.] A schedule is a map t:I(Gc)→R≥0. The schedule assigns to each independent set Ija time duration tj=t(Ij), which speciﬁes the fraction of time that the links in Ijare active. A schedule tis said to satisfy a set of demands ( f(ℓ) :ℓ∈L) if, for each ℓ∈L,/summationtext Ij:ℓ∈IjtjCl≥f(ℓ), and if the duration of the schedule/summationtext Ijtjis at most 1. A schedule is said to be optimal if it satisﬁes the demand of all the links and has minimum duration. A schedule t, as deﬁned above, can be implemented as follows. We construc t a periodic schedule with period Tseconds, say, where we can choose Tarbitrarily. Then divide the time axis into frames of duration T, and further subdivide each frame into subintervals of length tjT. The schedule is implemented by letting the set of links Ijbe active during the subinterval of duration tjT. During this subinterval each link ℓ∈Ijtransmits at its 4 maximum transmission rate Cℓ. It is seen that if the schedule tsatisﬁes the demand vector, then so does this implementation. We shall assume throughou t that the entries of vectors (Cℓ) and ( f(ℓ)) are all rational numbers. Since the linear program deﬁnin g the duration of an optimal schedule has a rational optimal solution, it can b e assumed that the schedule t is a map into the rationals. Let Kbe the least common multiple of the denominators of tj. Then, divide the time axis into frames of duration T, and further subdivide each frame into Ksubintervals of equal length. Suppose Mj=Ktj; then in each frame, we let the links Ij be active for Mjtime slots; we let each link ℓ∈Ijtransmit at its maximum transmission rateCℓduring each time slot when it is active. Such an implementati on meets the demands satisﬁed by the schedule t. Reformulation. Suppose we are given a network graph G= (V,L) and a conﬂict graph that speciﬁes which links interfere with each other. Let τ(ℓ) denote the amount of time when link ℓdemands to be active. A link demand vector ( τ(ℓ) :ℓ∈L) is said to be feasible within time duration [0 ,T] if there exists a schedule of duration at most Tthat satisﬁes the demands. We will often assume, for simplicity o f exposition, that T= 1. Note that a schedule is a map t:I(Gc)→R≥0that assigns to each independent set Ijof the conﬂict graph a time duration t(Ij). A link ℓis then active for total duration/summationtext j:ℓ∈Ijt(Ij). The ﬂow admission problem is to determine whether there exis ts a schedule of duration at mostTthat satisﬁes the link demand vector τ. The scheduling problem is to realize such a schedule. We are interested in solutions that can be implem ented using only localized information and with low processing cost. Notation. It will be convenient to use the following notation. Let G= (V,E) be a simple, undirected graph. For v∈V, Γ(v) denotes the neighbors of v.α(G) denotes the maximum number of vertices of Gthat are pairwise nonadjacent. For V′⊆V,G[V′] denotes the induced subgraph whose vertex-set is V′and whose edge-set is those edges of Gthat have both endpoints in V′. For any τ:V→Rand any W⊆V, deﬁne τ(W) :=/summationtext v∈Wτ(v). 1.2. Prior work and our contributions The take oﬀ point for our work is the prior work of [5] and [9]. T heir work proves that certain distributed algorithms provide suﬃcient conditio ns for admission control. They call these conditions the row constraints [5] (or rate condition [9]), the degree condition [9], mixed condition [9], and scaled clique constraints [5]. Fur thermore, for unit disk networks, the scaled clique constraints are shown to be a factor of 2.1 a way from optimal [5]. The main results of this paper are along the following lines: the exact worst-case perfor- mance of these distributed admission control mechanisms is characterized and it is thereby shown that these mechanisms can be arbitrarily far away from optimal; we then show that for some well known classes of networks and interference mod els, these distributed algo- rithms are actually within a bounded factor away from optima l. The classes of networks and interference models we study include unit disk networks and networks with primary interference constraints. More speciﬁcally, we introduce the notion of the induced sta r number of a graph and show that it determines the exact worse-case performance of the r ow constraints. This implies, for example, that for unit disk networks there is a simple and eﬃc ient distributed admission control anddistributed scheduling mechanism which is at most a factor o f 5 away from 5 optimal, and for networks with primary interference constr aints this mechanism is at most a factor of 2 away from optimal. The performance of two other s uﬃcient conditions - namely the degree condition and mixed condition - is also studied. F inally, the results obtained thus far are applied to some speciﬁc classes of networks and inter ference models. For example, it is seen that the scaled clique constraints are at most a facto r of 1.25 away from optimal for networks with primary interference constraints. It is also seen that the diﬀerent suﬃcient conditions studied here are in general incomparable (each c ondition is neither stronger nor weaker than the others). 2. Row constraints We now present a suﬃcient condition for ﬂow admission contro l that can be implemented distributedly. Given a conﬂict graph GC= (L,L′), link demand vector ( τ(ℓ) :ℓ∈L) and T, a suﬃcient condition for feasibility is given by the follow ing result (see [9, Thm. 1], [5, Thm. 1]): Proposition 1. Ifτ(ℓ)+τ(Γ(ℓ))≤Tfor each ℓ∈L, then the demand vector (τ(ℓ) :ℓ∈L) is feasible within duration T. Proof : Pick any ordering of the links ℓ1,ℓ2,... ,ℓ m. Assign link ℓ1the time interval J1= [0,τ(ℓ1)], and initialize Jj=φ, j= 2,... ,m . For each i= 1,... ,k , assume ℓihas already been assigned time interval Ji⊆[0,T]. Here, Jineed not be one continuous time interval; it can be a union of disjoint intervals, but its overall lengt h isτ(ℓi). Since τ(ℓk+1) + τ(Γ(ℓk+1))≤T, it follows that τ(ℓk+1)+τ(Γ(ℓk+1)∩{ℓ1,... ,ℓ k})≤T. Hence, it is possible to assign to ℓk+1some subset Jk+1⊆[0,T] which is nonoverlapping with the intervals already assigned to the neighbors of ℓk+1and which has duration τ(ℓk+1). We can repeat this procedure for the remaining links ℓk+2,... ,ℓ m, in turn. These constraints are called the row constraints in [5] and t he rate condition in [9]. Let A= [aij] be the 0-1 valued n×nadjacency matrix of GCwhere aij= 1 iﬀ i=jorℓi andℓjare interfering. Let 1denote the vector whose every entry is 1. Then the suﬃcient condition above is equivalent to the condition Aτ≤T1on the rows of A, hence the name row constraints . Since these constraints depend on the ﬂow rate (the demand) of the neighboring links, it is called the rate condition in [9], where the autho rs also study a degree condition which depends only on the number of neighboring links rather than on their actual demand values. We chose to use the phrase row constraints (rather th an the rate condition) because all these results also apply in a general context where the va riables τ(l) need not refer to only rate values, or even just time durations, but to any dema nd for resources by competing entities, where the competition is modeled by a conﬂict grap h. The proof of Proposition 1 also gives a very eﬃcient algorith m for checking feasibility. It provides both a distributed admission control mechanism as well as a distributed scheduling algorithm: when a link ℓithat is currently inactive makes a demand to be active for dur ation τ(ℓi), the admission control mechanism can be implemented eﬃcie ntly by just checking the condition above for ℓiand its neighbors. The information required by a link to chec k this condition is just its demand and the demand of its neighbors. Furthermore, the distributed scheduling algorithm that meets the demand for link ℓineeds to know only the time intervals already assigned to the neighbors of ℓiin order to determine the time interval for ℓi. 6 It is known (cf. [9, Thm. 5]) that this suﬃcient condition is a lso necessary if the conﬂict graph is the disjoint union of complete graphs. Indeed, if a g iven set of links are pairwise interfering, then the duration of an optimal schedule for th ose links is equal to the sum of their individual demands. It turns out that the converse i s also true: the suﬃcient condition above becomes necessary only if the conﬂict graph is the disjoint union of complete graphs. To prove this, suppose that the conﬂict graph is conn ected but not complete. Then there exist three links ℓ1,ℓ2andℓ3such that ℓ1andℓ2interfere, ℓ2andℓ3interfere, but ℓ1andℓ3do not interfere (otherwise, the relation of two links being interfering would be an equivalence relation and the conﬂict graph would be com plete). The link demand vector (1 −ε,ε,1−ε,0,... ,0) is feasible within duration [0,1] but does not satisfy the row constraint for ℓ2. This proves the converse. We shall show that this observati on - that the row constraints above are also a necessary condition if a nd only if the conﬂict graph is the disjoint union of complete graphs - can be deduced from a more general result (cf. Theorem 3). 2.1. Row constraint polytope and induced star number In order to quantify how far the row constraints are from opti mal, it will be useful to introduce its associated polytope. Given a conﬂict graph, l etPIdenote its independent set polytope. This polytope is deﬁned as the convex hull of the ch aracteristic vectors of the independent sets of the graph. Note that PIis exactly equal to the set of all link demand vectors which are feasible within one unit of time. For the gi ven conﬂict graph, let Prow denote the set of all link demand vectors that satisfy the row constraints for T= 1; that is, Prow:={τ≥0 :τ(ℓi) +τ(Γ(ℓi))≤1∀i}. Since the row constraints are suﬃcient, Prow⊆PI. Also, note that βProw={τ:τ(ℓi) + τ(Γ(ℓi))≤β}. Deﬁne the scaling factor βrow:= inf {β≥1 :PI⊆βrowProw}. Equivalently, βrow= sup τ∈PImax i{τ(ℓi) +τ(Γ(ℓi))}. SoProw⊆PI⊆βrowProw, andβrowis the smallest scaling factor which converts the suﬃcient condition into a necessary one. It has been pointed out (cf. [5]) that the row constraints can be arbitrarily far away from optimal. For example, suppose the network consists of links ℓ1,... ,ℓ d+1, where ℓ1interferes with each of ℓ2,... ,ℓ d+1and there is no interference between the remaining links. Th en the conﬂict graph is a star graph. The link demand vector ( ε,1−ε,... , 1−ε) is feasible within one unit of time, but the row constraint for ℓ1has value τ(ℓ1) +τ(Γ(ℓ1)) =ε+ (1−ε)d which can be made arbitrarily close to dasεapproaches 0. This shows that βrow≥d. We prove next that the opposite inequality also holds, i.e. the row constraints can be a factor saway from the optimal schedule time for some demand vector on ly if the conﬂict graph contains a star on ⌈s+ 1⌉vertices as an induced subgraph. Deﬁnition 2. Theinduced star number of a graph His deﬁned by σ(H) := max v∈V(H)α(H[Γ(v)]). 7 Hence, the induced star number of a graph is the number of leaf vertices in the maximum sized star of the graph. This number determines exactly how c lose the row constraints are to optimal in the worst case: Theorem 3. LetGCbe a conﬂict graph. The exact worst-case performance of the r ow constraints is given by βrow=σ(GC). Proof: It has already been pointed out above that βrow≥σ(GC). To prove the opposite inequality, suppose τ∈PIand let ℓibe any link with demand τ(ℓi) =δ∈(0,1). It suﬃces to show that τ(ℓi) +τ(Γ(ℓi))≤σ(GC). Since links in Γ( ℓi) must be scheduled at time intervals disjoint from those of ℓiand since τ∈PI, there exists a schedule satisfying the demands of just the links Γ( ℓi) which has duration at most 1 −δ. The maximum number of pairwise non-interfering links in Γ( ℓi) isσ(GC), and so at most σ(GC) links can be simultaneously active during any time interval of this peri od of duration 1 −δ. Hence, τ(Γ(ℓi))≤σ(GC)(1−δ). So τ(ℓi) +τ(Γ(ℓi))≤δ+σ(GC)(1−δ)≤σ(GC). It was mentioned that the row constraints are also necessary conditions if and only if the conﬂict graph is the disjoint union of complete graphs. This observation follows as a special case of Theorem 3: the row constraints which are suﬃcient con ditions are also necessary iﬀProw=PI, which is the case iﬀ σ(GC) = 1, which is the case iﬀ each component of GC is a complete graph. While the induced star number of a graph c an be arbitrarily large, for special classes of networks studied in the literature th is quantity is bounded by a ﬁxed constant. This happens to be in the case for unit disk graphs a nd for networks with primary interference constraints. We examine these special cases i n Section 5. 2.2. A strengthening of the row constraints We saw above that the row constraints are a suﬃcient conditio n for feasibility of a link demand vector, and the performance of this distributed algo rithm is determined by the induced star number σ(GC). We now show that a slight improvement to σ(GC)−1 can be obtained. For simplicity of exposition, we shall assume in t his section that GCis connected; if this is not the case we can work with each connected compone nt separately and the results here still apply. Recall that the row constraint corresponding to link ℓiis that the sum total of the demand τ(ℓi) and the demands of allits interfering neighbors τ(Γ(ℓi)) not exceed the available resource T. It is easy to see that all the links in the network, except for any one designated link, say ℓ1, can ignore the demand of up to oneof its interfering neighbors. Proposition 4. Given a network and its conﬂict graph GC, pick any designated link ℓ1∈L. A suﬃcient condition for τto be feasible within duration Tis that τ(ℓi) +τ(Γ(ℓi)) ≤T, i= 1 τ(ℓi) +{τ(Γ(ℓi))−min ℓj∈Γ(ℓi)τ(ℓj)} ≤ T, i= 2,... ,m. Proof: Suppose the inequalities in the assertion are satisﬁed. Ord er the links, starting with ℓ1, as follows. Let ℓ2be any link adjacent (in GC) toℓ1, letℓ3be any link adjacent to ℓ1orℓ2. Given ℓ1,... ,ℓ r, letℓr+1be any link adjacent to one of the previous links. An ordering ℓ1,ℓ2,... ,ℓ mof all the links is thus obtained. The scheduling mechanism a ssigns 8 time intervals to these links in reverse order, starting wit hℓm. Assign the time interval [0,τ(ℓm)] toℓm. Once the links ℓm,ℓm−1,... ,ℓ r+1have been scheduled, by the inequality above for ℓrthe demand τ(ℓr) can also be satisﬁed because ℓrhas at least one neighbor in {ℓ1,... ,ℓ r−1}which has not yet been scheduled. Finally, ℓ1can also be scheduled because of the inequality above for ℓ1. Note that this suﬃcient condition is equivalent to the row co nstraints when GCis complete. This is because the inequality for i= 1 becomes τ(L)≤T, which implies that the set of inequalities for i= 2,... ,m are also satisﬁed. If GCis not complete, then it is possible to do away with the notion of a designated link (i.e. every link can ignore the demand of up to one of its neighbors), provided the conﬂict graph is not of one exceptional type - the odd cycle. The proof is by reducing to the previous case by sho wing that the scheduling mechanism can always ﬁnd a designated link for which the cond itions above are essentially satisﬁed. Proposition 5. Suppose GCis not complete. Then the set of constraints τ(ℓi) +{τ(Γ(ℓi))−min ℓj∈Γ(ℓi)τ(ℓj)} ≤ T, i = 1,... ,m is a suﬃcient condition for τto be feasible within duration TifGCis not an odd cycle. Fur- thermore, the smallest scaling factor that converts this su ﬃcient condition into a necessary one is equal to exactly σ(GC)orσ(GC)−1, depending on the structure of GC. Proof: Letr≥1 be the minimum number of vertices of GCwhose removal disconnects GC into more than one connected component. We consider three ca ses, depending on the value ofr(this proof method is from [2]): r= 1: Let ℓ1be a cutvertex of GC, so that the removal of ℓ1produces s≥2 connected components G1,... ,G s. Let ℓ1be the designated link of the network. Since each Giis connected to ℓ1and by the inequalities of the condition, the demand of each l ink in L−{ℓ1} can be satisﬁed, using the scheduling mechanism given in an e arlier proof. It remains to show that the demand of ℓ1can also be satisﬁed. Indeed, note that ℓ1has neighbors ℓaand ℓbinG1andG2, respectively, where ℓaandℓbare nonadjacent. Hence, the time slots of the schedule in G1can be permuted so that the time interval assigned to ℓais a subset of that assigned to ℓb(or, in case τ(ℓa)> τ(ℓb), the time slots can be permuted so that the time interval assigned to ℓbis a subset of that assigned to ℓa). Now ℓ1can be scheduled as well since two of its neighbors have been assigned overlapping in tervals. r≥3: Since GCis not complete, there exist ℓ1,ℓ2andℓ3such that ℓ1is adjacent to both ℓ2andℓ3while ℓ2andℓ3are nonadjacent. Since r≥3,GC− {ℓ2,ℓ3}is connected. First assign ℓ2andℓ3the time intervals [0 ,τ(ℓ2)] and [0 ,τ(ℓ3)], respectively. By the inequalities of the condition, we can now schedule the remaining links ℓ4,... ,ℓ min some order, with ℓ1as the designated link of the connected graph GC− {ℓ2,ℓ3}. Finally, ℓ1can also be scheduled since two of its neighbors have been assigned over lapping intervals. r= 2: Let ∆ denote the maximum degree of a vertex of GC. If ∆ ≤2, then the graph is either an odd cycle or an even cycle. If GCis an even cycle, say ( ℓ1,... ,ℓ 2k), then a feasible schedule is obtained by assigning to each link of odd index ithe time interval [0 ,τ(ℓi)] and to each link of even index ithe time interval [ T−τ(ℓi),T]. IfGCis an odd cycle, say (ℓ1,... ,ℓ 2k+1), note that the demand vector ( τ(ℓi) = 1/2,∀ℓi∈L) satisﬁes the inequalities of the condition but is not feasible within duration T. So now assume ∆ ≥3. There exist ℓ1andℓ2such that ℓ2is a cutvertex of GC−{ℓ1}. So suppose the removal of this cutvertex 9 decomposes GC− {ℓ1,ℓ2}into connected components G1,... ,G s. Now ℓ1has neighbors ℓa andℓbinG1andG2, respectively. Note that ℓaandℓbare nonadjacent and GC− {ℓa,ℓb} is connected. As before, we can assign time intervals [0 ,τ(ℓa)] and [0 ,τ(ℓb)] toℓaandℓb, respectively, then schedule all the remaining links with ℓ1as the designated link, and ﬁnally schedule ℓ1as well. This proves the suﬃciency of the condition. We now determine the performance βrow 2of this distributed algorithm, where βrow 2de- notes the smallest scaling factor which converts this suﬃci ent condition into a necessary one, i.e., replacing Tbyβrow 2Tin the inequalities above produces a set of necessary condit ions. Letσdenote σ(GC). Now GCcontains the star graph on some nodes ℓ1,... ,ℓ σ+1as an in- duced subgraph, with ℓ1as the center node. For these nodes, the demand ( ε,1−ε,... , 1−ε) is feasible within one unit of time, and the left-hand-side o f the inequality for ℓ1given in the suﬃcient condition evaluates to ε+ (σ−1)(1−ε), which can be made arbitrarily close toσ−1. Hence, βrow 2≥σ−1. Also, since this suﬃcient condition is stronger than the row constraints, βrow 2≤βrow=σ. So we have that σ−1≤βrow 2≤σ. LetS⊆Ldenote the vertices ℓofGCthat can induce a maximum sized star of GC with some of their neighbors, i.e. S:={ℓ∈L:α(GC[Γ(ℓ)]) =σ}; here α(G) denotes the maximum size of an independent set of G. (It suﬃces to consider just these vertices because the remaining vertices have a smaller value of α(GC[Γ(ℓ)]), and hence the left hand side of the inequalities in the condition evaluate to at most σ.) If the degree of every vertex in S is exactly σ, then βrow 2=σ−1, as we just showed. However, suppose the degree of some vertex ℓ′inSis at least σ+ 1, where {ℓ1,... ,ℓ σ+1}are the neighbors of ℓ′and the ﬁrst σ of these neighbors form an independent set. Then the demand v ector for ( ℓ′,ℓ1,... ,ℓ σ+1) given by ( ε,1−ε−ε/2,... ,1−ε−ε/2,ε/2) is feasible within one unit of time, but the left-hand-side of the inequality for ℓ′given in the condition can be made arbitrarily close toσ. Hence βrow 2≥σin this case. It follows that βrow 2equals σorσ−1, according as whether the degree of any vertex in Sexceeds or doesn’t exceed σ. 3. Degree and mixed conditions It was shown that the row constraints provided a simple, dist ributed suﬃcient condition for feasibility of a given demand vector. In this condition, there was exactly one constraint associated with each link, namely, the sum total of the deman d of the link and demands of its neighbors not exceed the available resource. We now desc ribe an even simpler condition. We call this the degree condition since it requires knowing, for each link, the demand of that link and just the number (not actual demands) of links interfering with it. Suppose link ℓiinterferes with exactly d(ℓi) other links, i.e. in the conﬂict graph ℓihas degree d(ℓi). Then, the following result provides another suﬃcient con dition for admission control [9]: Proposition 6. A given demand vector (τ(ℓi) :ℓi∈L)is feasible within duration Tif τ(ℓi)(d(ℓi) + 1) ≤Tfor each ℓi∈L. Proof: Suppose the inequalities in the assertion are satisﬁed. Ord er the links so that τ(ℓ1)≤ τ(ℓ2)≤...≤τ(ℓm). Assign ℓ1the time interval [0 ,τ(ℓ1)]. Assume links ℓ1,... ,ℓ rhave al- ready been assigned time intervals satisfying their demand s. It follows from τ(ℓr+1)(d(ℓr+1)+ 1)≤Tand the chosen ordering of the links that τ(ℓr+1) +τ(Γ(ℓr+1)∩ {ℓ1,... ,ℓ r})≤T. 10 Hence, it is possible to assign to ℓr+1a subset of [0 ,T] of length τ(ℓr+1) which is disjoint from the intervals already assigned to its neighbors. It fol lows by induction that the demand vector is feasible. The degree condition and the row constraints are seen to be eq uivalent when all links have the same demand value. Also, note that while the admission co ntrol mechanism speciﬁed by the degree condition can be implemented distributedly, t he scheduling mechanism given in the proof above requires ordering all the links according to their demand values, which is global information. We will see more examples of such cond itions where the admission control mechanism is distributed but the scheduling mechan ism realizing a feasible schedule is not distributed. The degree condition is quite loose (far away from optimal) i n that it admits a given demand vector τonly if τ(ℓi)≤0.5Tfor each ℓi(this is because, since GCis connected, we have d(ℓi)≥1), and more generally, only if τ(ℓi)≤T/(d(ℓi) + 1) for each ℓi∈L. In particular, when the demand values of the various links are asymmetric - i n the sense that some links have small demand values, while others have demand values cl ose to the maximum possible T- then the demand vector will not be admitted by the degree con dition even if it really is feasible. The performance of the degree condition is determined, not s urprisingly, by the maximum degree of a vertex in the conﬂict graph. More precisely, deﬁn e Pdegree:={τ≥0 :τ(ℓi)(d(ℓi) + 1) ≤1,∀i}. Then Pdegree ⊆PIby Proposition 6. Deﬁne βdegree:= inf {β≥1 :PI⊆βPdegree}. Let ∆( GC) denote the maximum degree of a vertex in GC. Lemma 7. For any conﬂict graph GC, the exact worst-case performance of the degree condition is given by βdegree(GC) = ∆( GC) + 1. Proof: Letℓ1be a link having exactly dneighbors ℓ2,... ,ℓ d+1in the conﬂict graph. For these d+ 1 links, the demand vector τ= (1−ε,ε/d,... ,ε/d ) is feasible within one unit of time, and τ(ℓ1)(d+ 1) = d+ 1−ε(d+ 1) can be made arbitrarily close to d+ 1. Hence, βdegree(GC)≥∆(GC) + 1. Now suppose τis feasible within one unit of time, and let ℓibe any link. Then, τ(ℓi)≤1, and so τ(ℓi)(d(ℓi) + 1) ≤1(∆(GC) + 1). Hence, τ∈(∆(GC) + 1)Pdegree. This implies that the suﬃcient degree condition is also nece ssary (and hence optimal) iﬀ GCis the empty graph, i.e. iﬀ no two links interfere with each ot her. It is possible to combine the row constraints and degree constraints to get a s uﬃcient condition which is strictly stronger, as shown in [9]: Proposition 8. A link demand vector τis feasible within duration Tif min{τ(ℓi) +τ(Γ(ℓi)), τ(ℓi)(d(ℓi) + 1) } ≤T,∀ℓi∈L. 11 Proof: Suppose the inequalities in the condition are satisﬁed. Ord er the links so that τ(ℓ1)≤... ,τ(ℓm). Assign ℓ1the time interval [0 ,τ(ℓ1)]. Suppose ℓ1,... ,ℓ rhave already been assigned time intervals satisfying their demands. By t he inequality in the condition forℓr+1, either τ(ℓi) +τ(Γ(ℓi))≤Torτ(ℓi)(d(ℓi) + 1) ≤T; in either case, ℓr+1can also be scheduled, as was shown in the earlier proofs where one of the se conditions is satisﬁed. As introduced in [9], we call this suﬃcient condition the mixed condition . Consider the conﬂict graph GCon the three links {ℓ1,ℓ2,ℓ3}, where ℓ1is adjacent to each of ℓ2andℓ3, andℓ2andℓ3are nonadjacent. Let T= 1. Note that the link demand vector (0 .9,0.1,0.1) satisﬁes the row constraints but not the degree constraints , and the demand (0 .3,0.5,0.5) satisﬁes the degree constraints but not the row constraints . Hence these two conditions are incomparable. Also, the demand (0 .3,0.6.0.6) satisﬁes neither the row nor the degree constraints but does satisfy the mixed condition. Finally, the demand (1 /3 +ε,1/3,1/3) is feasible but does not satisfy the mixed condition. (This las t example proves that the mixed condition is optimal (and hence, also necessary) iﬀ GCis the disjoint union of complete graphs, i.e. iﬀ σ(GC) = 1, an observation which we can also deduce from a more gener al result; cf. Theorem 9.) These examples show that, in general , Prow,Pdegree/notsubsetoreql(Prow∪Pdegree)/notsubsetoreqlPmixed/notsubsetoreqlPI, where Pmixed:={τ: min{τ(ℓi) +τ(Γ(ℓi)), τ(ℓi)(d(ℓi) + 1) } ≤1,∀ℓi∈L}. Letβmixed denote the smallest scaling factor that converts the suﬃcie nt mixed condition into a necessary one; hence, given the conﬂict graph GC= (L,L′) and its independent set polytope PI, we have that Pmixed⊆PI⊆βmixedPmixedand βmixed= sup τ∈PImax ℓi∈Lmin{τ(ℓi) +τ(Γ(ℓi)), τ(ℓi)(d(ℓi) + 1) }. Theorem 9. The worst-case performance of the mixed condition is bounde d as 1 +σ(GC) 2≤βmixed ≤σ(GC), where σ(GC)denotes the induced star number of GC. Moreover, the lower and upper bounds are tight; the star graphs realize the lower bound, and there exist graph sequences for which βmixedapproaches the upper bound arbitrarily closely. Proof: Since the mixed condition is satisﬁed whenever the row const raints are satisﬁed, βmixed≤βrow, and so the upper bound follows from Theorem 3. To prove the lower bound, suppose GC= (L,L′) is a star graph on vertices L= (x,y1,... ,y η), where xis the center vertex and the leaf vertices yiform an independent set. We show that for this GCand its independent set polytope PI, sup τ∈PImax ℓi∈Lmin{τ(ℓi) +τ(Γ(ℓi)), τ(ℓi)(d(ℓi) + 1) }=1 +η 2. It can be assumed that η≥2, for if η= 1 then GCis complete and so βmixed= 1 by the optimality of the mixed condition in this case. Set τ(x) =:δ∈[0,1]. In order to maximize max ℓi∈Lmin{τ(ℓi) +τ(Γ(ℓi)), τ(ℓi)(d(ℓi) + 1) } 12 overτ∈PI,τ(yi) can be set to equal its maximum possible value of 1 −δ, fori= 1,... ,η . The mixed condition evaluated at yi∈Lis bounded as min{τ(ℓi) +τ(Γ(ℓi)), τ(ℓi)(d(ℓi) + 1) } ≤τ(ℓi) +τ(Γ(ℓi)) = (1 −δ) +δ= 1. Butβmixed ≥1 trivially. Hence, to determine the worst-case performanc e of the mixed condition, it suﬃces to evaluate the mixed condition at just x∈L: βmixed = sup δ∈[0,1]min{τ(x) +τ(Γ(x)), τ(x)(d(x) + 1) } = sup δ∈[0,1]min{δ+η(1−δ), δ(1 +η)}. Note that δ+η(1−δ)≤δ(1 +η) iﬀδ≥1/2. It can be seen that the optimum is attained atδ= 1/2, giving βmixed=1+η 2for this star graph on 1 + ηvertices. The lower bound thus follows, and it has also been shown that t he class of star graphs realize this lower bound. We now construct a sequence of graphs for which βmixedapproaches the upper bound in the limit. We do this by determining the exact value of βmixedfor a wider class of graphs which includes the class of star graphs as a special case. The property that GC= (L,L′) needs to satisfy is that it has some x∈Lthat is adjacent to every other element of Land such that the removal of xdisconnects GCinto a disjoint union of complete graphs, i.e., x has degree |L| −1 and σ(GC−x) = 1. We now claim the following: Suppose GC= (L,L′) is such that x∈Lis adjacent to all other members of Land the removal of xproduces disjoint complete graphs on vertex sets L1,... ,L η. Then βmixed=η(1 +/summationtext|Li|) η+/summationtext|Li|. To prove this claim, suppose GC= (L,L′),x∈L, and L1,... ,L ηsatisfy the conditions of the claim. Recall that βmixed= sup τ∈PImax ℓi∈Lmin{τ(ℓi) +τ(Γ(ℓi)), τ(ℓi)(d(ℓi) + 1) }. Letτ(x) =:δ∈[0,1]. In order to maximize max ℓi∈Lmin{τ(ℓi) +τ(Γ(ℓi)), τ(ℓi)(d(ℓi) + 1) } overτ∈PI, assign demands to the elements of L1,... ,L ηarbitrarily so that τ(Li) = 1−δ,i= 1,... ,η . For this τ, the row constraint at each y∈Lievaluates to exactly 1 and the mixed condition at each yevaluates to at most 1. Since βmixed≥1,βmixedis determined by the value of the mixed condition at just x: βmixed = sup δ∈[0,1]min{τ(x) +τ(Γ(x)), τ(x)(d(x) + 1) } = sup δ∈[0,1]min{δ+ (1−δ)η , δ(1 +/summationdisplay |Li|)}. It is a straightforward computation to show that δ+(1−δ)η≤δ(1+/summationtext|Li|) iﬀδ≥η η+P|Li| and that βmixedattains its optimal value ofη(1+P|Li|) η+P|Li|when δ=η η+P|Li|. This proves the claim. 13 Note that the case of |Li|= 1,∀i, makes GCa star graph, whereas letting |L1|approach inﬁnity gives that βmixedapproaches the upper bound of σ(GC). This proves that the upper bound in the assertion is sharp. One general class of graphs that includes the star graphs, th e even and odd cycles, the complete graphs and bipartite graphs are those that satisfy the following property: for each vertex ℓ∈Lin the graph GC= (L,L′), the neighbors of ℓinduce a disjoint union of complete graphs. For this general class of graphs there is a s imple expression for the exact value of βmixed: Theorem 10. Suppose GC= (L,L′)satisﬁes σ(GC[Γ(ℓ)])≤1,∀ℓ∈L. Let d(ℓ)denote the number of neighbors of ℓand let ηℓdenote the number of connected components induced by the neighbors of ℓ. Then βmixed= max ℓ∈Lηℓ(1 +d(ℓ)) ηℓ+d(ℓ). This result implies that if GCis a star graph, a bipartite graph, or a cycle graph, then the exact worst-case performance of the mixed condition is βmixed=1+∆( GC) 2. The proof of Theorem 10 is similar to the proof of the claim in the previous proof and so the details are omitted. The simplest example of a graph that does not satisf y the conditions of Theorem 10 is the graph K4−e(one edge removed from the complete graph on 4 vertices). For this graph, a straightforward but lengthy computation yields βmixed= 1.6. 4. Clique constraints A necessary condition for a given link demand vector to be fea sible can be obtained as follows. Suppose there exists a schedule of duration 1 satis fying demand τ. Then if Kis a clique in the conﬂict graph, the time intervals assigned to t he distinct links in Kmust be disjoint, hence τ(K)≤1. Thus, a necessary condition for τto be feasible within duration Tis that τ(K)≤Tfor every maximal clique Kin the conﬂict graph. These constraints are called clique constraints [5]. As before, we can associate a polytope with this necessa ry condition; deﬁne Pclique:={τ:τ(K)≤1,∀K} ⊇PI, where Kruns over all the cliques (or equivalently, over just all the maximal cliques) of the conﬂict graph. A perfect graph is one for which every induced subgraph has it s chromatic number equal to its clique number. It is known that PI=Pcliquefor a graph if and only if the graph is perfect. Using the notion of the imperfection ratio of graphs, bounds on the suboptimality of clique constraints were obtained [5] for the case of unit disk graph s. More precisely, given a conﬂict graph GCand demand vector τ, letT∗(τ) denote the minimum duration of a schedule satisfying τ(the optimal value of this linear program is also the smalles tβsuch thatτ∈βPI, and T∗(1) is often referred to as the fractional chromatic number of GC). LetTclique(τ) denote the maximum value of τ(K) over all cliques Kin the conﬂict graph; soTclique(τ)≤T∗(τ). The imperfection ratio of a graph GCis deﬁned as imp(GC) := sup τ/ne}ationslash=0{T∗(τ)/Tclique(τ)}. 14 This quantity has been studied in [4]; it is ﬁnite and is achie ved for any given graph. In the deﬁnition above, for a given demand vector τ, the numerator speciﬁes the exact amount of resource required to satisfy the demand, as determined by an optimal, centralized algorithm. The denominator speciﬁes a lower bound on the resource requi red to satisfy the demand, as determined by a particular distributed algorithm (the cl ique constraints). Their ratio is the factor by which the distributed algorithm is away from op timal for the given demand vector. The imperfection ratio, which maximizes this ratio over all demand patterns, is then the worst-case performance of the distributed algorit hm. This argument is made more precise in the next proof. The following general result is implicit in [5] (where the au thors focus on unit disk graphs) and in [4]: Proposition 11. The largest scaling factor which converts the necessary cli que constraints into a suﬃcient condition is 1/imp(GC); i.e. the worst-case performance of the clique constraints is given by sup{β≤1 :βPclique⊆PI}=1 imp(GC); and1 imp(GC)Pclique⊆PI⊆Pclique. Proof: Suppose τ∈1 imp(GC)Pclique. Then τ(K)≤1 imp(GC)for all cliques K. SoT∗(τ)≤ imp(GC)Tclique(τ)≤imp(GC)1 imp(GC)≤1. So τ∈PI. Now suppose β >1/imp(GC). It suﬃces to show that βPclique/notsubseteqlPI. Since imp( GC)> 1/β, there exists a τsuch that T∗(τ)/Tclique(τ)>1/β. Deﬁne ˜ τ:=β Tclique(τ)τ. Then ˜τ∈βPclique, butT∗(˜τ) =β Tclique(τ)T∗(τ)>1. 5. Examples In this section we apply the results obtained so far to some sp ecial classes of networks and interference models. In Section 5.1, we examine a model of in terference called primary interference constraints, which has been well-studied in t he literature for the centralized setting; we examine the distributed version of the problem h ere. In Section 5.2 we look at the unit disk model, which is quite popular and widely used by researchers in the sensor networks community to model the topology of a network. 5.1. Primary interference model Given a network G= (V,L), suppose two links are considered to be interfering iﬀ they share one or more endvertices in common. We refer to this kind of interference as primary interference. This interference model arises, for example , from the assumption that each node can communicate to only one other node at any given time. This interference model is perhaps the most well studied in the literature; for examp le, see [6], [7], [11]. The conﬂict graph for such a network is called a line graph . Note that in this kind of interference model, if link ℓ1interferes with each of ℓ2,ℓ3andℓ4, and ℓ2doesn’t interfere with ℓ3, then ℓ4 must interfere with exactly one of ℓ2orℓ3. So we obtain a well-known result that if the 15 conﬂict graph GCis a line graph then σ(GC)≤2. It follows that for such networks the row constraints will be at most a factor 2 away from optimal. More speciﬁcally, for this interference model, the row cons traints on the conﬂict graph can be reformulated on the network graph G= (V,L) as follows. Suppose link ℓiis incident between nodes uiandvi. Given link demand vector τ, letτ(u) denote the sum of the demands of all links incident in Gto node u. Then the row constraint τ(ℓi) +τ(Γ(ℓi))≤T in the conﬂict graph GC= (L,L′) is equivalent to the constraint τ(ui) +τ(vi)−τ(ℓi)≤T in the network graph. This equivalence yields the following suﬃcient condition: Corollary 12. LetG= (V,L)be a network graph, and suppose two links interfere if and only if they are incident to a common node. Then (τ(ℓ) :ℓ∈L)is feasible within duration Tif for each ℓ={u,v},τ(u) +τ(v)−τ(ℓ)≤T. This suﬃcient condition is a factor of at most 2 away from optimal. Remark. In the case of primary interference constraints, upper boun ds on the minimum scheduling time can be obtained immediately by using upper b ounds on the chromatic index of multigraphs; for example, see some of the results in [6], [11]. We note here a reverse implication: the row constraints above (and its pro of) can be used to obtain an upperbound on the chromatic index of multigraphs. More prec isely, let G= (V,L) be a simple undirected graph. Let d{u,v}denote the number of parallel edges between vertices uandv. This deﬁnes a multigraph ( G,d). A proper edge-coloring is an assignment of colors to edges so that any two edges that share one or more endvertic es in common are assigned diﬀerent colors. The chromatic index of a multigraph is the m inimum number of colors required to properly color its edges. Let d(u) denote the number of edges incident to u∈V. Then, Corollary 12 implies that: the chromatic index of the m ultigraph ( G,d) is bounded from above by max ℓ={u,v}(d(u) +d(v)−d{u,v}). Another distributed algorithm that can be used in networks h aving primary interference constraints is given by the clique constraints. Trivially, a necessary condition for τto be feasible within duration Tis that τ(K)≤Tfor all cliques Kin the conﬂict graph. By Proposition 11, the performance of the clique constraints i s determined by the imperfection ratio of the conﬂict graph. It is known that the imperfection ratio of a line graph is at most 1.25 [4, Prop. 3.8]. This means that a suﬃcient conditio n forτto be feasible wtihin duration Tis that 1 .25τ(K)≤Tfor all cliques Kin the conﬂict graph. Since GCis a line graph, each clique KinGCcorresponds either to a set of links K⊆Lthat are all incident to a common node in the network graph G= (V,L) or to a set of three links that form a triangle in the network graph. For v∈V, letτ(v) denote the sum of the demands of all links incident to vin the network graph. The following result provides an eﬃcie nt, distributed algorithm for admission control: Theorem 13. LetG= (V,L)be a network graph, and suppose two links interfere if and only if they are incident to a common node. Then (τ(ℓ) :ℓ∈L)is feasible within duration Tifτ(v)≤0.8T,∀v∈Vandτ(uv) +τ(vw) +τ(uw)≤0.8T,∀u,v,w ∈V. This suﬃcient condition is a factor of at most 1.25 away from optimal. An important aspect of this result is that, though the number of maximal cliques in a general graph can grow exponentially with the size of the gra ph, the number of maximal 16 cliques in a line graph grows only polynomially in the size of the graph. This is because the maximal cliques in a line graph correspond to one of two di ﬀerent types of cliques, as mentioned above, and there are only a polynomial number of su ch cliques, as can be veriﬁed by just counting the number of possible cliques of these two t ypes by examining the network graph. Thus, unlike for general graphs, for line graphs the c lique constraints provide an eﬃcient distributed algorithm for checking feasibility of a given demand vector. It is possible to construct examples to show that the suﬃcien t conditions provided by Corollary 12 and Theorem 13 are incomparable, i.e. the sets Prowand 0 .8Pclique are (inclusionwise) incomparable. We omit these details. 5.2. Unit disk networks One assumption that is often used by researchers in the senso r networks community to model the topology of a wireless sensor network is the unit disk ass umption. In this model, all nodes are assumed to have the same transmission power and are equip ped with omnidirectional antennas; equivalently, the transmission range for each no de is a disk of constant radius centered at that node. By scaling the axes, the radius can be a ssumed to be 1, hence the nameunitdisk network for such models. Thus, in this model two nodes ca n communicate with each other iﬀ unit disks centered at their locations int ersect. Not all network topologies can be realized with this model: the topology of unit disk net works is very restricted, since if nodes aandbare close to each other, and nodes bandcare close to each other, then a andcare not too far away from each other and hence are also likely t o be connected. A graph is called a unit disk graph if it can be realized as the t opology of some unit disk network, i.e. if there exist locations on the Euclidean plan e - one location corresponding to each vertex of the graph - such that unit disks centered at a pa ir of locations intersect if and only if the corresponding vertices of the graph are adjac ent. It is known that the induced star number of a unit disk graph is at most 5. To prove this result, suppose some vertex uof a unit disk graph has 6 or more neighbors. Divide the unit disk region centered at uinto six sectors of 60 degrees each. Then at least two of the vertices adjacent to umst lie in the same sector and hence at a distance of at most one unit from each other. Hence ucannot have 6 or more neighbors that are pairwise nonadjacen t. An example of an interference model for which the conﬂict gra ph is a unit disk graph is given in [5]. In such cases the following result applies. Corollary 14. If the conﬂict graph is a unit disk graph, then the row constra ints are at most a bounded factor of 5 away from optimal. A bound on the performance of another distributed algorithm (the scaled clique constraints) is known for the case where the conﬂict graph is a unit disk gra ph. By Proposition 11, the performance of the clique constraints is determined by the i mperfection ratio of the conﬂict graph. It is known that the imperfection ratio of a unit disk g raph is at most 2.1 [4, Prop. 3.3]. In other words, the clique constraints are neces sary conditions (ie. Pclique⊆ PI) and scaling the clique constraints by a factor of 1/2.1 give s a suﬃcient condition for admission control (ie. 0 .46Pclique⊆PI). This yields the following result [5, Thm. 2]: 17 Corollary 15. Suppose the conﬂict graph is a unit disk graph. Then, a demand vector τ is feasible within duration Tifτ(K)≤0.46Tfor all cliques Kin the conﬂict graph. It is possible to construct examples to show that the suﬃcien t conditions provided by Corollary 14 and Corollary 15 are incomparable, i.e. the set sProwand 0 .46Pcliqueare (inclusionwise) incomparable. We omit these details. 6. Concluding remarks The exact worst-case performance of some suﬃcient conditio ns for admission control was studied. The results here imply that for some special classe s of networks and interfer- ence models, there exist simple, eﬃcient, distributed admi ssion control mechanisms and scheduling mechanisms whose performance is within a bounde d factor away from that of an optimal, centralized mechanism. Acknowledgements Thanks are due to professor Parmesh Ramanathan for suggesti ng this direction of scaling the suﬃcient conditions.