On the Complexity of Scheduling in Wireless Networks

We consider the problem of throughput-optimal scheduling in wireless networks subject to interference constraints. We model the interference using a family of -hop interference models, under which no two links within a -hop distance can successfully transmit at the same time. For a given , we can obtain a throughput-optimal scheduling policy by solving the well-known maximum weighted matching problem. We show that for , the resulting problems are NP-Hard that cannot be approximated within a factor that grows polynomially with the number of nodes. Interestingly, for geometric unit-disk graphs that can be used to describe a wide range of wireless networks, the problems admit polynomial time approximation schemes within a factor arbitrarily close to 1. In these network settings, we also show that a simple greedy algorithm can provide a 49-approximation, and the maximal matching scheduling policy, which can be easily implemented in a distributed fashion, achieves a guaranteed fraction of the capacity region for "all ." The geometric constraints are crucial to obtain these throughput guarantees. These results are encouraging as they suggest that one can develop low-complexity distributed algorithms to achieve near-optimal throughput for a wide range of wireless networks.

Scheduling link transmissions in a wireless network so as to optimize one or more of the performance objectives (e.g., throughput, delay, or energy) has been the topic of paramount interest over the past several decades. In their seminal work, Tassiulas and Ephremides [1] characterized the capacity region of constrained queuing systems, such as a wireless network. They developed a queue length-based scheduling scheme that is throughput-optimal, that is, it stabilizes the network if the user rates fall within the capacity region of the network. Unlike wireline networks, where all links have fixed capacities, the capacity of a wireless link can be influenced by channel variation due to fading, changes in power allocation or routing, changes in network topology, and so forth. Thus, the capacity region of a wireless network can vary due to changes in power allocation or routing. To efficiently utilize the wireless resources, one must therefore develop algorithms that can perform jointly routing, link scheduling, and power control under possibly varying channel conditions and network topology. This has spurred recent interest in developing cross-layer optimization algorithms (see, e.g., [2–5]).

Motivated by the works on fair resource allocation in wireline networks [6, 7], researchers have also incorporated congestion control into the cross-layer optimization framework [8–10]. The congestion control component controls the rate at which users inject data into the network to ensure that the user rates fall within the capacity region.

Most of the above cross-layer optimization problems have been shown to exhibit a mathematical decomposition [2, 8]. To elaborate, the cross-layer optimization problem can be decomposed into multiple subproblems, where each subproblem corresponds to optimization across a single layer. The subproblems are loosely coupled through parameters that correspond to congestion prices or queue lengths at the individual links.

The main component of all these cross-layer optimization schemes is the optimal scheduler that solves a very difficult global optimization problem of the form:

where denotes the set of wireless links; is the vector of link rates , ; is the congestion price or possibly some function of queue length at link ; is the capacity region of the network.

The main difficulty in solving the above optimization problem is that the capacity region depends on the network topology and, in general, has no easy representation in terms of the power constraints at the individual links or nodes. The above optimization problem is, in general, NP-Complete and Nonapproximable.

In this paper, we consider a class of scheduling problems that we term Maximum Weighted -Valid Matching Problems (MWKVMPs). These problems arise as simplifications to the scheduling problem specified by (1). The basic idea is to limit the interference to only hops, where is a positive integer. By varying , one can capture the interference characteristics of a broad range of wireless networks.

The rest of the paper is organized as follows. The model, problem formulation, related works, motivation, and main contributions of this work are presented in the next section. Some hardness and approximability results for the class of scheduling problems that we consider are presented in Section 3. We then restrict our attention to geometric unit-disk graphs that naturally model the connectivity graph of wireless networks, and develop approximation schemes for our scheduling problems in Section 4. By focusing on the throughput performance in Section 5, we reduce the complexity of scheduling schemes further, and show that a distributed maximal matching algorithm achieves a provable throughput guarantee. The geometric constraints of graphs remain crucial to obtain the throughput guarantees. Finally, we provide concluding remarks in Section 6.

We consider a set of wireless nodes, each communicating over a single wireless interface. We assume that all transmissions are carried out over the same wireless channel, and therefore interfere with each other. We assume that all transmissions from a node are carried out at the same power level (which can be different for different nodes). We connect two nodes with an (undirected) edge if each of them can successfully receive from the other, provided no other node in the network transmits at the same time. The set of (undirected) edges so formed is denoted by . Note that the existence of an edge between two nodes depends on the power allocated to the nodes, noise variances, as well as coding and modulation schemes. Our emphasis on bidirectional edges stems from the fact that most network and transport layer protocols assume bidirectional communications between the nodes. We also note that our main results can easily be extended to settings where directed edges are allowed between the nodes.

We next introduce the class of scheduling problems we consider in this paper. We first introduce some notation. Let be an undirected graph (connectivity graph of a wireless network, in our case) having as the set of vertices (nodes) and as the set of edges (link). A matching is a set of edges no two of which share a common vertex. We now generalize this concept of matching to -valid matchings for an integer .

Let denote the minimum number of hops between vertices . Letting denote the set of nonnegative integers, we define a distance function as follows: for two edges , , let

We call a set of edges a "-valid matching" if for all with , we have . Observe that the concept of matching discussed before is equivalent to the concept of -Valid matching in this new terminology. Let denote the set of -Valid matchings of the graph . We consider the following scheduling problems:

where denotes the weight of edge . Note that the weight of each edge is a positive, but otherwise arbitrary, number that can possibly depend on many factors (e.g., congestion price, supported rate, queue length). The above class of problems will henceforth be referred to as Maximum Weighted -Valid Matching Problems (MWKVMPs). When all edge weights are set to unity, we obtain the following class of problems:

where denotes the cardinality of the set . In the sequel, we refer to these problems as Maximum -Valid Matching Problems (MKVMPs).

We note that the scheduling problems specified by (3) are natural simplifications of the complex scheduling problem specified by (1). This is because for a given , by satisfying the -hop interference constraints one can guarantee a certain fixed data rate at a given edge. The weight of each edge can then be determined as some function of the rate it supports and the congestion price at the edge. The scheduling problem specified by (1) then corresponds to MWKVMP for that particular value of . For simplicity of notation, we did not explicitly show the dependence of edge weights on in (3).

From the above discussion, it is not surprising to see that MWKVMPs can represent the scheduling problem specified by (1) under a wide variety of interference models. Below we discuss two widely used interference models that can be obtained as special cases of the interference constraints in (3).

Node-Exclusive (or Primary) Interference Model

This is a commonly used model for Bluetooth and FH-CDMA networks [11, 12]. Under this model, the set of edges that transmit simultaneously must constitute a matching. Then the scheduling problems specified by (3) and (4) correspond to the classical Maximum Weighted Matching Problem (MWMP) and the Maximum Matching Problem (MMP), respectively. Both these problems can be solved in polynomial time [13].

IEEE 802.11-Based Interference Model

This is a commonly used model for IEEE 802.11-based wireless networks [9, 14], under which the chosen set of edges must constitute a 2-Valid matching. It models the communication under the RTS/CTS-based scheme of IEEE 802.11 DCF (see Figure 1). Note that the sender and the receiver exchange RTS and CTS messages preventing their neighboring nodes from participating in a communication, which is equivalent to saying that the chosen set of communicating node pairs must constitute a 2-Valid matching.

In general, we use the term "-hop interference model," under which a scheduler should provide a -valid matching. The node-exclusive and IEEE 802.11-based interference models correspond to the -hop interference model with and , respectively.

2.1. Related Work

The -hop interference model has been studied in many different contexts due to its simplicity [1, 4, 8, 12, 15–17]. A polynomial time link scheduling algorithm has been developed in [12], and distributed schemes that guarantee a throughput within a constant factor of the optimal have been developed in [8, 15]. Recently, a class of throughput-optimal scheduling policies, called pick-and-compare, has been proposed [16, 17]. Although they achieve the throughput-optimality with a low complexity, they result in causing significantly long queue lengths, which in turn results in high delays, and for practical buffer sizes, can result in low throughput performance [18].

In [9], the performance of maximal scheduling schemes has been studied under the -hop interference model. It has been shown that the maximal scheduling schemes achieve a throughput within a factor of of the capacity region, where denotes the maximum link degree. In [15], the maximal scheduling schemes are shown to achieve at least a factor of of the optimal throughput, where is the interference degree of the connectivity graph (see Definition 11). It also has been shown in [19, 20] that random access scheduling policies can achieve comparable performance.

The MKVMP for is often known as the induced matching problem, which has been shown to be NP-Hard [21]. The work of [14] is closest in spirit to our work. The authors consider the induced matching problem from the perspective of carrying out maximum number of simultaneous transmissions. They study the approximability of the induced matching problem for general as well as specific kinds of graphs, and develop a distributed constant factor Polynomial-Time Approximation Scheme (PTAS) for the induced matching problem under geometric unit-disk graphs.

However, most previous studies are limited to the -hop or -hop interference model. It has been observed through simulations in [22] that, under different network settings, the -hop interference model with can better capture the network interference constraints. For the detailed results, we refer to our technical report [22].

2.2. Main Contributions

From a theoretical perspective, we provide several results on the hardness and approximability of MWKVMP and MKVMP for . Although some of these results have previously been obtained for , to the best of our knowledge no prior work has studied MWKVMP or MKVMP for . Since weighted matching problems arise in a variety of contexts, these results might find applications in other fields (e.g., VLSI) as well.

From a wireless networking perspective, we provide a Polynomial-Time Approximation Scheme (PTAS) for MWKVMP restricted to geometric unit-disk graphs, which can be used to represent the connectivity graph of a wide range of wireless networks. We also characterize the performance of "natural" greedy scheme under the same class of graphs. Although it has been known that the greedy scheme yields a constant factor approximation to MWKVMP, we are more interested in specific performance bounds of the scheme for all . We note that both PTAS and the greedy algorithm can be used to construct scheduling policies that achieve a constant fraction of the capacity region under -hop interference models, but they can be implemented in a limited class of wireless networks (e.g., wireless mesh networks) due to high complexity and requirement for centralized control.

We complement the results by showing that the maximal scheduling policy that can be implemented in a distributed manner with a low complexity achieves a guaranteed fraction of the capacity region. These results are encouraging as they indicate that one can develop distributed algorithms to achieve near optimal throughput in case of a wide range of wireless networks. Finally, we observe that the topological constraints of the underlying graphs play a critical role to guarantee the throughput performance, and that the maximal scheduling policy can achieve an arbitrarily small fraction of the capacity region in general network graphs.

We now formulate the decision problems KVMP and WKVMP corresponding to MKVMP and MWKVMP, respectively, and prove that they are NP-Complete. We also show that MKVMP and MWKVMP cannot be approximable within in polynomial time while we can approximate them within . We begin with the following definitions.

Definition 1.

For a given graph and number , KVMP is a decision process that determines whether has a -valid matching of size .

Definition 2.

For a given graph , number , and weight , WKVMP is a decision process that determines whether has a -valid matching of size and total weight .

The following theorem shows that WKVMP, which also implies that KVMP.

Theorem 3.

WKVMP for all .

Proof.

Given a certificate in the form of a list of edges, it can easily be verified in polynomial time whether that list corresponds to a set of edges that are at a distance of or more from each other and have a total weight of or not. Thus, whether the set of edges constitute a -valid matching of size with a total weight of can be verified in polynomial time. Hence, WKVMP NP.

We next show that KVMP is NP-Hard, which implies that the decision problem WKVMP is NP-Hard as well.

Theorem 4.

KVMP is NP-Hard for .

Proof.

The proof uses a novel technique reducing 3-CNF-SAT problem to KVMP [23]. Since their result is stronger, MKVMP, and hence KWMVMP, are Nonapproximable for .

We now analyze the approximability of MKVMP for . We have the following result.

Theorem 5.

Let be a constant such that . Then, MKVMP (and hence, MWKVMP) for is not approximable within for any , unless . Further, it is not approximable within for any , unless is equivalent to Zero-error Probabilistic Polynomial time problems [24].

Before we prove Theorem 5, we introduce some terminology. Consider a graph . A subset of vertices is termed "independent" provided that no two vertices in the set have an edge between them. The classical Maximum Independent Set Problem (MISP) is to find an independent subset of vertices of maximum possible cardinality. Note that we can easily convert MKVMP (4) to MISP by mapping an edge to a vertex and connecting two vertices when corresponding two edges are within -hop distance. Hastad [25] has shown that MISP is not approximable within for any unless NP P, and it is not approximable within for any unless NP ZPP. We are now ready to prove Theorem 5.

Proof.

We show that given a graph , we can construct a graph in polynomial time such that a -valid matching of has cardinality no smaller than that of the maximum independent set of . Then we show that both and are , which is equal to . Finally, we will show that given a -valid matching in , one can obtain an independent set of vertices in with the same cardinality in polynomial time.

Suppose that MKVMP admits a polynomial time -approximation scheme (PTAS). Given a graph , one can construct the corresponding graph in polynomial time, and use the PTAS for MKVMP to obtain a -valid matching of size at least times the cardinality of any maximum independent set of . Then we can map it back to an independent set of vertices in with the same cardinality, in polynomial time. This would then result in a -approximation scheme for MISP of , which, in view of the results in [25], would imply Theorem 5.

We next discuss how to construct the graph from in polynomial time. We first consider even .

(1)For each vertex in , we place a pair of vertices , and connect them with an edge.

(2)For each edge in , we connect the vertices through a sequence of edges and vertices. Let the vertices be denoted by with being the vertex adjacent to vertex .

We denote the resultant graph as . Figure 2 illustrates an example of a graph along with the constructed graph when . It is straightforward to see that the graph can be constructed in polynomial (in and ) time. Also, we have

Now, suppose that constitutes an independent set of vertices in . It is then clear that constitutes a -valid matching in . To see this, observe that since constitutes an independent set of vertices in , we have for all with . Hence, by the construction of , we have for . Then it follows that the graph has a -valid matching of cardinality not smaller than the cardinality of the maximum independent set of .

It remains to show that given a -valid matching in , one can, in polynomial time, obtain an independent set of vertices in with the same cardinality. To this end, we propose a systematic construction method in Algorithm 1.

It is easy to see that the running time of Algorithm 1 is bounded above by a polynomial in and . We check that the resulting set from Algorithm 1 is indeed an independent set in . It suffices to show that for all . Suppose that there exist two vertices such that . It then follows that there must exist edges such that , which contradicts our assumption that is a -valid matching.

Next, we discuss how to construct the graph for and odd. We make a minor change in the construction of the graph. In the first step, instead of placing a pair of vertices for each vertex , we now place a triplet of vertices (see Figure 3), and connect the pairs of vertices and with an edge. In the second step, for each edge , we connect the vertices through a sequence of edges and vertices. We denote the resulting graph as . We now have

Similarly, we can check that the graph has a -valid matching of cardinality no smaller than the cardinality of the maximum independent set of . Suppose constitutes an independent set of vertices in . We have for all with in . Then by the construction of , we have for all , and the result follows.

We show that given a -valid matching in , we can obtain an independent set of vertices in with the same cardinality in polynomial time. The construction algorithm is the same as Algorithm 1, except for the following three lines:

(i)Line 4: if   is of the form or   then

(ii)Line 8: else if   is of the form   then

(iii)Line 11: if    then

We check that the resulting set is an independent set in as follows. Suppose that is not an independent set. Then there exist two vertices such that . Then by the construction of , there must exist two edges such that for , which contradict our assumption that is a -valid matching. The running time of the algorithm is also bounded above by a polynomial in and .

For , we can construct the graph as in case, and prove the corresponding results accordingly. We omit the details.

Algorithm 1:Constructing an independent set in from a -valid matching in , when is even ().

 

 while    do

  Pick an edge

  if   is of the form   then

   

 else if   is of the form then

   

  else if   is of the form   then

   

   else if   is of the form   then

   if    then

    

   else

    

   end if

  end if

  

end while

From and in the above proof, the following result follows from Theorem 5.

Corollary 6.

MKVMP (and hence, MWKVMP) for is not approximable within for any , unless . Further, it is not approximable within for any , unless .

Corollary 6 gives a lower bound on the approximation ratio of any polynomial time approximation algorithm for MWKVMP or MKVMP. The next result we have is opposite in flavor: it shows that there exists a polynomial time algorithm for MWKVMP whose approximation ratio is no worse than .

Theorem 7.

MWKVMP can be approximated within a factor of .

The following Corollary is an immediate consequence of Theorem 7.

Corollary 8.

MKVMP can be approximated within a factor of .

We define the Vertex Weighted Maximum Independent Set Problem (VWMISP), which is the following variation of the Maximum Independent Set Problem (MISP). Let denote the weight of vertex . VWMISP is to find an independent set of vertices that maximizes . It is shown in [26] that VWMISP is approximable within . We now proceed to the proof of Theorem 7.

Proof.

Given a network graph , we construct a graph from in polynomial time, and approximately solve VWMISP in using the results of [26]. We can then obtain the corresponding -valid matching in from the independent set in .

We first construct from as follows. For each edge , we generate a vertex in with weight . If two edges satisfy , we connect the corresponding vertices with an edge. The resulting graph is often called the conflict graph of . Clearly, we have , and we can construct the conflict graph in polynomial time. From the construction, it is clear that for a -valid matching in , there exists an independent set of vertices in with the same weighted sum, and vice versa.

Now, using the results of [26], we can approximate VWMISP in polynomial time and obtain an independent set in with weight at least times the weight of an optimal independent set. From the independent set in , we can reconstruct a -valid matching in with the same weight due to , in polynomial time.

In this section, we focus on the MWKVMP problem for an important class of network graphs. In particular, we are interested in geometric unit-disk graphs, under which the connectivity and the interference constraints are determined by the location of vertices. Specifically, the vertices are placed on a plane, two vertices are connected if and only if their distance is no greater than , and also interfere with each other if and only if their distance is no greater than . Geometric graphs have been used extensively in the literature to model the connectivity of wireless networks [27, 28]. In this section, we show that MWKVMP can be approximated within a constant factor in case of unit-disk graphs. We also note that the results can also be extended to some other geometric graphs including the quasi-unit-disk graphs [29].

We start with redefining -valid matching in geometric graphs. Let denote the Euclidean distance between two nodes . We define the distance between edges and -valid matching accordingly as (2), for , we let

A set of edges is said to be a "-valid matching" if for all with , we have . We also denote the set of -valid matchings of the graph by .

4.1. PTAS for MWKVMP

Several NP-complete problems are known to admit PTAS when restricted to planar or geometric graphs. In [30], PTASs are developed for various NP-complete problems restricted to planar graphs. NC-approximation schemes for various NP-Hard and PSPACE-Hard problems restricted to geometric graphs are developed in [31]. Following the approach in [31], we now show that MWKVMP and, therefore, MKVMP admits a constant factor PTAS when restricted to geometric graphs. We present the polynomial time approximation algorithm for the completeness.

Consider a geometric graph with , specified using the coordinates of its vertices in the plane. We now present an algorithm that yields a -valid matching with weight at least times the weight of an optimal -valid matching in polynomial time, where is a constant, and can be chosen to be arbitrarily small.

The basic technique is the following. Given any , we calculate the smallest possible that satisfies . We divide the plane into grids of width and height , and denote each grid by as shown in Figure 4. Each grid is left (top) closed and right (bottom) open. For each , we partition the set of edges into disjoint sets by removing edges whose two end-vertices are within such that . For , let be the smallest subset of such that all edges in are of the form for some . Also, let , , and let . For each subgraph , we find a -valid matching of size at least times the size of the optimal -valid matching in . Observe that since each subgraph has been separated by , the union of -valid matchings for subgraphs is a -valid matching for the graph . Using arguments similar to [31, 32], we then show that each iteration returns a -valid matching with weight at least times the weight of an optimal -valid matching in . Our algorithm is is described in detail in Table , and achieves of the optimal performance. For the detailed analysis, we refer to our technical report [22].

Algorithm 2 has complexity of (see [22]). Hence, even for a small , the complexity is likely to be a high-order polynomial of and becomes a major obstacle to its implementation in practice. In the next subsection, we show that a natural greedy algorithm with a lower complexity can approximate MWKVMP within a constant factor under geometric unit-disk graphs.

Algorithm 2:A (1+)-approximation scheme for MWKVMP

 Find the smallest such that .

 Divide the plane into grids of width and height . Each grid is denoted by .

 for   to   do

  Partition into disjoint sets by removing edges whose two end-vertices are within such

     that .

 Let denote the subgraph induced by with , and let .

for   to   do

  for   to   do

   Partition into disjoint sets by removing edges whose two end-vertices are within

      such that .

   Let denote the subgraph induced by with , and let .

     for   to   do

    Obtain an optimal -valid matching .

     end for

    

  end for

   , where

 end for

  

  , where

end for

4.2. Greedy Approach for MWKVMP

We study the performance of the greedy scheduling scheme illustrated in Algorithm 3. Note that the algorithm is greedy in the sense that it schedules links in decreasing order of the weight. Some other works uses the term "greedy'' for a simpler scheme that schedules a set of links that no other links can be added to without violating the interference constraints. In this paper, we denote such a scheme by "maximal scheduling'', and differentiate from our greedy algorithm. It is well known that this greedy approach yields a -approximation algorithm for MWMP in general network graphs under the -hop interference model [33], and a constant approximation algorithm in planar graphs under the -hop interference model [34]. However, the performance can be much worse for . In this section, we characterize the performance of the greedy approach in geometric unit-disk graphs by providing a lower bound for "all ." We begin with some definitions.

Algorithm 3:Greedy weighted -valid matching algorithm

 Arrange edges of in descending order of weight as

  

 

 for   to   do

  if   is a -valid matching  then

   

  end if

 end for

Definition 9.

The -hop interference set of an edge , denoted by , is the set of edges such that .

Definition 10.

The -hop interference degree of an edge , denoted by , is defined as

Definition 11.

The -hop interference degree of the graph , denoted by , is defined as

The following is the main result of this subsection.

Theorem 12.

The weight of the matching returned by Algorithm 3 is always within a factor of the weight of an optimal matching. Further, there exists a graph for which the above ratio is tight.

Proof.

Let be the edge added to the matching during the first step by the greedy algorithm. Then, we have for all . Now, the optimal matching can contain at most edges belonging to , each with a weight no larger than . Let be the edge added to the matching during the second step by the greedy algorithm. Then, we have for all , where denotes the set consisting of elements of that are not in . Moreover, the optimal matching can contain at most edges belonging to , each with a weight no larger than .

For , let . Arguing as above, it can be shown that during the th step, the greedy algorithm adds an edge to the matching that satisfies

and the optimal matching contains no more than edges belonging to . Let denote the last edge added to the matching by the greedy algorithm, and let denote the optimal matching. From the above discussion, it is clear that for , we have

Note that by convention . Summing over , we obtain that

proving the first part of Theorem 12.

To prove the second part, we consider a network graph as shown in Figure 5. Let denote the link at the center. In this example, we have . One possible matching obtained using the greedy algorithm is shown in Figure 5(a). Note that the weight of this matching is . However, the weight of an optimal matching is as shown in Figure 5(b). Thus, the greedy algorithm may return a matching whose weight is off by a factor of in comparison to the weight of an optimal matching.

Clearly, Figure 5 shows that can be of the order of in general graphs, and correspondingly, the performance of Algorithm 3 can be arbitrarily small when compared with the optimal performance. However, if the network graphs are governed by some geometric constraints, we can show that Algorithm 3 approximates the optimal scheduler by a constant.

Theorem 13.

The weight of the matching returned by Algorithm 3 is within a factor of of the weight of an optimal matching in case of geometric unit-disk graphs.

Proof.

From Theorem 12, it suffices to show that for any geometric unit-disk graph . To this end, we show that for all edges .

At a time slot, let denote a -valid matching chosen by Algorithm 3. We consider the set of edges for an edge . For each edge , we draw a disk of radius centered at the mid-point of . Let denote two edges in with . If there are no such pair of edges, then we have . Otherwise, it is clear from , two disks and do not intersect with each other as shown in Figure 6.

Now we consider a large disk of radius centered at the mid-point of . Since we have for all edges , all disks should be contained in . However, since no two disks intersect, the number of disks in is bounded by

for all . Hence, we have for all edge , which implies that .

Note that Algorithm 3 has complexity of and can be implemented in a distributed manner [35].

Remark 14.

The above results imply that PTAS of Algorithm 2 and the greedy algorithm of Algorithm 3 achieves a guaranteed fraction of weights. Let denote a class of scheduling policies such that at each time slot, the weight of chosen schedule is no less than . Then Algorithms 2 and 3 belong to with and , respectively. This property needs to be highlighted since distributed rate control algorithms that can deliver the performance of scheduling policy to end-users have been recently developed [8].

Polynomial time algorithms developed in the earlier section can be used to construct scheduling policies that achieve a constant fraction of the capacity region. For example, it can be easily shown that a scheduling policy that belongs to achieves at least , where denotes the capacity region of the underlying network graph.

Although PTAS and the greedy algorithm achieve a guaranteed fraction of the capacity region, they require centralized control and/or a high complexity, which restrict their practical implementation within a limited class of wireless networks. In this section, we focus on throughput performance of scheduling policies. We show that even simpler scheduling policies that can be easily implemented in a distributed fashion have a provable throughput guarantee. Specifically, we show that the maximal scheduling policy of [8, 15] which is an scheduling policy can also achieve a guaranteed fraction of the capacity region in geometric unit-disk graphs, when all transmissions are carried out at certain fixed rates (i.e., rate control is not exercised).

5.1. Distributed Implementation for Geometric Unit-Disk Graphs

We start with the following definition of the maximal scheduling policy.

Definition 15.

A subset of edges is a maximal schedule if each edge either has an empty queue, or satisfies . A scheduling policy is said to be a maximal scheduling policy if it chooses one of the maximal schedules for transmission at each time slot.

In words, the maximal scheduling policy ensures that if there are any packets waiting to be transmitted over an edge , then either or one of edges that interfere with is scheduled for transmission. Note that an optimal solution to MWKVMP and the greedy algorithm are one of maximal scheduling policies while PTAS of Algorithm 2 is not a maximal scheduling policy.

Now we consider a network with single-hop fixed-rate sessions. Let denote the capacity region of the network, that is, the set of session arrival rates for which the network can be stabilized under some scheduling policy. We have the following theorem.

Theorem 16.

In geometric unit-disk graphs under the -hop interference model, any maximal scheduling policy can stabilize the network system for any set of session arrival rates within .

Proof.

It has been shown in [15] that any maximal scheduling policy achieves at least fraction of the capacity region. In other words, it stabilizes the network system for any set of arrival rates within . From Theorem 13, we have that in geometric unit-disk graphs, and hence, the result follows.

Note that a simple distributed maximal scheduling policy can be developed by extending the randomized maximal scheduling of [8] to the -hop interference model. In this case, the complexity of the policy will be .

Remark 17.

Theorem 16 implies that the maximal scheduling policy can achieve in the sense of time average. It can be contrasted with the results of PTAS and the greedy algorithm provided in Section 4, where they guarantee a constant fraction of weights at each time slot. Their average performance can be higher than the guaranteed fraction of weights. For example, it has been recently shown that the greedy algorithm achieves [36].

5.2. Throughput Guarantees in Nongeometric Network Graphs

The results provided in the previous section are encouraging as they indicate that one can develop simple distributed algorithms whose worst-case throughput is a nonvanishing fraction of the capacity region. Note that the results are obtained by admitting an arbitrarily small fraction of weights at a time slot, on the basis of geometric properties of unit-disk graphs. Although we have shown in Corollary 6 that MWKVMP cannot be approximated within a constant factor in general network graphs, it still remains unclear whether a simple distributed algorithm like the maximal scheduling policy can achieve a constant fraction of the capacity region in general network graphs. In the following, we show that the geometric constraints are indeed crucial to achieve the constant fraction of capacity region. To elaborate, we show that the greedy algorithm (and thus, the maximal scheduling policy as well) can achieve an arbitrarily small fraction of the capacity region in general network graphs.

We begin with some definitions. For a graph , we consider a subset of edges , and denote the set of all possible matching matchings on by . Also let denote the convex hull of set , that is,

Recently, it has been shown in [36, 37] that for a vector and all , we can construct an arrival rate such that the queues of all edges in keep increasing under the greedy scheduling algorithm of Algorithm 3. Note that the optimal scheduler can serve the arrival rate if . Therefore, in order to show that the greedy algorithm achieves no greater than , it suffices to find a subset and two vectors such that , where implies a component-wise inequality, that is, for all .

Now we provide a systematic construction of network graphs such that we can find a subset of edges and two vectors satisfying with . Once we find those two vectors, we have the upper bound of the performance of the greedy algorithm.

Lemma 18.

There is a network graph under the -hop interference model with such that two vectors with satisfy for .

Proof.

We first describe our systematic construction of a graph, and then find two vectors in a subset of edges of the constructed network graph. Note that these two vectors should be a combination of maximal matchings in the subset of edges and one must be component-wise greater than the other by a factor of .

We construct the network graph with and as follows.

Phase 1 (horizontal edges; see Figure 7(a) for an example of and ).

() Start with (or if is odd) vertices. Place vertices on a cycle and name them in counter-clockwise order as . Connect each vertex to its immediate neighbor for , where represents a modular addition by .

() Make the circle a centerless wheel by connecting each vertex to the opposite vertex for . All vertices can be connected because is an even number. Let denote the constructed wheel graph.

() Connect and using -hop edges for . That is, for each , add vertices between and , say , and connect them in sequence with edges for . Also, add edges and . If or , connect and directly.

() Repeat () with and for .

() Construct another wheel graph by duplicating , and name vertices on the wheel of accordingly with superscript .

Phase 2 (vertical edges; see Figure 7(b) for an example of and ).

() Connect and using -hop edges for all . That is, for each , add vertices between and , and connect them with edges for .

(2) Repeat () with and for .

As an example, all horizontal edges and a part of vertical edges of are shown in Figures 7(a) and 7(b).

Let be the set of edges inside two wheels, that is, for . Let and . Links in are presented as solid black lines in Figure 7(a). Note that edges constructed in () and () of Phase 1 and in () and () of Phase 2 are designed to control interference among edges within and between wheels. If an edge is active in (or in ), then edges constructed by () and () of Phase 1 allow at most other edges to be active in (or in ). Hence, we can activate at most edges in each wheel (see Figure 7(c)). However, the inter-wheel interference by vertical edges may reduce the number of active edges. In () and () of Phase 2, we have constructed vertical edges per each vertex of each wheel. Since the vertical edges have -hop, an active edge in can interfere with edges in and vice versa. Assume that edges and are active in and , respectively. We can have at most more active edges in each wheel, that is, in and in . However, if we choose edges and such that interferes with all edges of in , and interferes with all edges of in , then we have only two active edges as a maximal matching in , that is, and (two red lines in Figure 7(d)). We design the network graph carefully such that a maximal matching can include from active edges to two active edges.

Now, we find two convex combinations of maximal matchings in that one is component-wise greater than the other by . Consider two sets of maximal matchings; one with maximal matchings of active edges and the other with maximal matchings of 2 active edges. We first let where and each maximal matching with includes active edges and for all . For the other vector, let where and each maximal matching with includes only two edges and . Note that 's and 's are valid maximal matchings in All active edges in are either activated or interfered, and all active edges satisfy the interference constraints. Figures 7(c) and 7(d) illustrate an instance of and in , respectively. Active edges are colored in red. To clearly show the interference in Figure 7(d), we color a vertex in black if it is interfered by the active edge in the upper wheel, and in gray if it is interfered by the active edge in the lower wheel.

Using the scheduling of or , each edge in is served exactly once during a unit time for by or for by . Since (or if is odd), we obtain that for all edge and thus, .

Lemma 18 immediately implies the following proposition.

Proposition 19.

Under the -hop interference model, Algorithm 3 can achieve an arbitrarily small fraction of the optimal throughput.

Proof.

From Lemma 18 and the techniques of [37], we can find a traffic arrival with for all such that the system is unstable under the greedy scheduling algorithm. However, the optimal scheduling policy can support , which follows that the achievable rate of the greedy algorithm is not greater than . Since can be arbitrarily large from our graph construction, the performance ratio can be arbitrarily small.

Proposition 19 lets us know that it is hard, if possible, to characterize the performance limits of the greedy algorithm (and thus the maximal scheduling policy as well) in arbitrary network graphs under the -hop interference model.

We consider the problem of throughput-optimal scheduling in wireless networks subject to interference constraints, which are modeled using a family of -hop interference models. Under the assumption that each node transmits at a fixed power level (which can be different for different nodes), the optimal scheduling problems are shown to be weighted matching problems with constraints determined by the -hop interference model. These weighted matching problems are termed Maximum Weighted -Valid Matching Problems (MWKVMPs).

For , MWKVMP corresponds to the well-studied Maximum Weighted Matching Problem (MWMP) in the literature, which can be solved in polynomial time. We show that MWKVMP is NP-Hard for all and provided upper and lower bounds on its approximability.

By restricting the problem to geometric unit-disk graphs, under which connectivities are determined by geometric distance between nodes, we show that MWKVMP admits a PTAS within a factor arbitrarily close to , and the "natural" greedy matching algorithm yields a 49-approximation to the optimal solution for all . We emphasize that both PTAS and the greey scheduling schemes achieve a guaranteed fraction of weights at every time slot. Combining these with the results in [8], it follows that both can be used to develop a joint solution of scheduling and rate control with provable (end-to-end) performance guarantees with multihop traffics.

However, since PTAS and the greedy algorithm have a polynomial time complexity and require centralized control, their implementations in practice are restricted within a limited class of wireless networks. We complement these results by further focusing on the throughput performance of scheduling policies. Specifically, we show that the maximal scheduling policy that is amenable to distributed implementation achieves fraction of the capacity region under a setting with single-hop traffic and fixed rate transmissions. These results are encouraging as they indicate that one can develop simple distributed algorithms whose worst-case throughput is a nonvanishing fraction of the optimal throughput in the case of a wide class of wireless networks. Finally, we highlight that the geometric constraints are crucial for the maximal scheduling policy to achieve the throughput guarantees. We show that even the greedy scheduling algorithm, in the worst case, can result in an arbitrarily small efficiency without these constraints.

This work has been supported in part by the NSF Awards CNS-0626703 and CNS-0721236, and the ARO MURI Award W911NF-08-1-0238, USA, and in part by the New Professor Research Program of KUT (2010), Korea.

1. L Tassiulas, A Ephremides, Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control 37(12), 1936–1948 (1992). Publisher Full Text

2. L Xiao, M Johansson, SP Boyd, Simultaneous routing and resource allocation via dual decomposition. IEEE Transactions on Communications 52(7), 1136–1144 (2004). Publisher Full Text

3. MJ Neely, E Modiano, CE Rohrs, Power allocation and routing in multibeam satellites with time-varying channels. IEEE/ACM Transactions on Networking 11(1), 138–152 (2003). Publisher Full Text

4. L Tassiulas, A Ephremides, Jointly optimal routing and scheduling in packet radio networks. IEEE Transactions on Information Theory 38(1), 165–168 (1992). Publisher Full Text

5. RL Cruz, AV Santhanam, Optimal routing, link scheduling and power control in multi-hop wireless networks. Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '03), April 2003, 702–711

6. FP Kelly, AK Maulloo, D Tan, Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society 49(3), 237–252 (1998)

7. H Yaïche, RR Mazumdar, C Rosenberg, A game theoretic framework for bandwidth allocation and pricing in broadband networks. IEEE/ACM Transactions on Networking 8(5), 667–678 (2000). Publisher Full Text

8. X Lin, NB Shroff, The impact of imperfect scheduling on cross-layer rate control in wireless networks. Proceedings of the Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '05), March 2005 3, 1804–1814

9. X Wu, R Srikant, Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks. Proceedings of the 25th Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '06), April 2006

10. AL Stolyar, Maximizing queueing network utility subject to stability: greedy primal-dual algorithm. Queueing Systems 50(4), 401–457 (2005). Publisher Full Text

11. B Miller, C Bisdikian, Bluetooth Revealed: The Insider's Guide to an Open Specification for Global Wireless Communications (Prentice-Hall, 2000)

12. B Hajek, G Sasaki, Link scheduling in polynomial time. IEEE Transactions on Information Theory 34(5), 910–917 (1988). Publisher Full Text

13. HN Gabow, Data structures for weighted matching and nearest common ancestors with linking. Proceedings of the Symposium on Discrete Algorithms (SODA '90), 1990

14. H Balakrishnan, CL Barrett, VSA Kumar, MV Marathe, S Thite, The distance-2 matching problem and its relationship to the MAC-layer capacity of ad hoc wireless networks. IEEE Journal on Selected Areas in Communications 22(6), 1069–1079 (2004). Publisher Full Text

15. P Chaporkar, K Kar, X Luo, S Sarkar, Throughput and fairness guarantees through maximal scheduling in wireless networks. IEEE Transactions on Information Theory 54(2), 572–594 (2008)

16. E Modiano, D Shah, G Zussman, Maximizing throughput in wireless networks via gossiping. Performance Evaluation Review 34(1), 27–38 (2006). Publisher Full Text

17. S Sanghavi, L Bui, R Srikant, Distributed link scheduling with constant overhead. Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems (Sigmetrics '07), June 2007, 313–324

18. G Sharma, C Joo, NB Shroff, Distributed scheduling schemes for throughput guarantees in wireless networks. Proceedings of the 44th Annual Allerton Conference on Communications, Control, and Computing, September 2006

19. X Lin, SB Rasool, Constant-time distributed scheduling policies for ad hoc wireless networks. IEEE Transactions on Automatic Control 54(2), 231–242 (2009)

20. C Joo, NB Shroff, Performance of random access scheduling schemes in multi-hop wireless networks. Proceedings of the 26th Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '07), May 2007, 19–27

21. LJ Stockmeyer, VV Vazirani, NP-completeness of some generalizations of the maximum matching problem. Information Processing Letters 15(1), 14–19 (1982). Publisher Full Text

22. C Joo, G Sharma, RR Mazumdar, NB Shroff, On the complexity of scheduling in wireless networks (Korea University of Technology and Education, 2010) (http://netlab, 2010), . kut.ac.kr webcite

23. G Sharma, RR Mazumdar, NB Shroff, Maximum weighted matching with interference constraints. Proceedings of the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom '06), March 2006, 70–74

24. J Gill, Computational complexity of probabilistic turing machines. SIAM Journal on Computing 6(4), 675–695 (1977). Publisher Full Text

25. J Håstad, Clique is hard to approximate within . Acta Mathematica 182(1), 105–142 (1999). Publisher Full Text

26. MM Halldórsson, Approximations of weighted independent set and hereditary subset problems. Journal of Graph Algorithms and Applications 4(1), 1–16 (2000)

27. SO Krumke, MV Marathe, SS Ravi, Models and approximation algorithms for channel assignment in radio networks. Wireless Networks 7(6), 575–584 (2001). Publisher Full Text

28. SH Teng, in Points, spheres, and separators, a unified geometric approach to graph separators, Ph, ed. by . D. thesis (School of Computer Science, Carnegie Mellon University, CMU-CS-91-184, Pittsburgh, Pa, USA, August 1991)

29. F Kuhn, R Wattenhofer, A Zollinger, Ad-hoc networks beyond unit disk graphs. Proceedings of the 1st ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC '03), September 2003, San Diego, Calif, USA, 69–78

30. BS Baker, Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM 41(1), 153–180 (1994). Publisher Full Text

31. HB Hunt III., MV Marathe, V Radhakrishnan, SS Ravi, DJ Rosenkrantz, RE Stearns, NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. Journal of Algorithms 26(2), 238–274 (1998). Publisher Full Text

32. DS Hochbaum, W Maass, Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM 32(1), 130–136 (1985). Publisher Full Text

33. D Avis, A survey of heuristics for the weighted matching problem. Networks 13(4), 475–493 (1983). Publisher Full Text

34. S Ramanathan, EL Lloyd, Scheduling algorithms for multihop radio networks. IEEE/ACM Transactions on Networking 1(2), 166–177 (1993). Publisher Full Text

35. J-H Hoepman, Simple distributed weighted matchings (http://arxiv), . org/abs/cs/0410047v1 webcite

36. C Joo, X Lin, NB Shroff, Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks. Proceedings of the Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '08), April 2008, 1103–1111

37. C Joo, X Lin, NB Shroff, Performance limits of greedy maximal matching in multi-hop wireless networks. Proceedings of the 46th IEEE Conference on Decision and Control (CDC '07), December 2007, 1128–1133