The study of the optimality of low-complexity greedy scheduling techniques in wireless communications networks is a very complex problem. The Local Pooling (LoP) factor provides a single-parameter means of expressing the achievable capacity region (and optimality) of one such scheme, greedy maximal scheduling (GMS). The exact LoP factor for an arbitrary network graph is generally difficult to obtain, but may be evaluated or bounded based on the network graph’s particular structure. In this paper, we provide rigorous characterizations of the LoP factor in large networks modeled as Erdős–Renyi (ER) and random geometric (RG) graphs under the primary interference model. We employ threshold functions to establish critical values for either the edge probability or communication radius to yield useful bounds on the range and expectation of the LoP factor as the network grows large. For sufficiently dense random graphs, we find that the LoP factor is between 1 2 and 2 3, while sufficiently sparse random graphs permit GMS optimality (the LoP factor is 1) with high probability. We then place LoP within a larger context of commonly studied random graph properties centered around connectedness. We observe that edge densities permitting connectivity generally admit cycle subgraphs that form the basis for the LoP factor upper bound of 2 3. We conclude with simulations to explore the regime of small networks, which suggest the probability that an ER or RG graph satisfies LoP and is connected decays quickly in network size.
Sufficient conditions for the optimality of Greedy Maximal Scheduling (GMS) employed on a network graph (G(V,E) ) were produced by Dimakis and Walrand @cite_12 and called Local Pooling (LoP). The GMS algorithm (called Longest Queue First, LQF @cite_12 ) consists of an iterated selection of links in order of decreasing queue lengths, subject to pair-wise interference constraints. Computing whether or not an arbitrary graph (G ) satisfies LoP consists of solving an exponential number of linear programs (LPs), one for each subset of links in (G ). Trees are an example of one class of graphs proved to satisfy LoP. While LoP is necessary and sufficient under deterministic traffic processes, a full characterization of the graphs for which GMS is optimal under random arrivals is unknown.
@cite_12
2099797040 2039917366 2148282413 1995120351
Due to its low complexity, Greedy Maximal Scheduling (GMS), also known as Longest Queue First (LQF), has been studied extensively for wireless networks. However, GMS can result in degraded throughput performance in general wireless networks. In this paper, we prove that GMS achieves 100 throughput in all networks with eight nodes or less, under the two-hop interference model. Further, we obtain performance bounds that improve upon previous results for larger networks up to a certain size. We also provide a simple proof to show that GMS can be implemented using only local neighborhood information in networks of any size. Efficient operation of wireless networks and switches requires using simple (and in some cases distributed) scheduling algorithms. In general, simple greedy algorithms (known as Greedy Maximal Scheduling, or GMS) are guaranteed to achieve only a fraction of the maximum possible throughput (e.g., 50 throughput in switches). However, it was recently shown that in networks in which the Local Pooling conditions are satisfied, GMS achieves 100 throughput. Moreover, in networks in which the σ-Local Pooling conditions hold, GMS achieves σ throughput. In this paper, we focus on identifying the specific network topologies that satisfy these conditions. In particular, we provide the first characterization of all the network graphs in which Local Pooling holds under primary interference constraints (in these networks, GMS achieves 100 throughput). This leads to a linear-time algorithm for identifying Local-Pooling-satisfying graphs. Moreover, by using similar graph-theoretical methods, we show that in all bipartite graphs (i.e., input-queued switches) of size up to 7 × n, GMS is guaranteed to achieve 66 throughput, thereby improving upon the previously known 50 lower bound. Finally, we study the performance of GMS in interference graphs and show that in certain specific topologies, its performance could be very bad. Overall, the paper demonstrates that using graph-theoretical techniques can significantly contribute to our understanding of greedy scheduling algorithms. In this paper, we characterize the performance of an important class of scheduling schemes, called greedy maximal scheduling (GMS), for multi-hop wireless networks. While a lower bound on the throughput performance of GMS is relatively well-known in the simple node-exclusive interference model, it has not been thoroughly explored in the more general K-hop interference model. Moreover, empirical observations suggest that the known bounds are quite loose, and that the performance of GMS is often close to optimal. In this paper, we provide a number of new analytic results characterizing the performance limits of GMS. We first provide an equivalent characterization of the efficiency ratio of GMS through a topological property called the local-pooling factor of the network graph. We then develop an iterative procedure to estimate the local-pooling factor under a large class of network topologies and interference models. We use these results to study the worst-case efficiency ratio of GMS on two classes of network topologies. First, we show how these results can be applied to tree networks to prove that GMS achieves the full capacity region in tree networks under the K-hop interference model. Second, we show that the worst-case efficiency ratio of GMS in geometric network graphs is between 1 6 and 1 3. In this paper, we characterize the performance of an important class of scheduling schemes, called greedy maximal scheduling (GMS), for multihop wireless networks. While a lower bound on the throughput performance of GMS has been well known, empirical observations suggest that it is quite loose and that the performance of GMS is often close to optimal. In this paper, we provide a number of new analytic results characterizing the performance limits of GMS. We first provide an equivalent characterization of the efficiency ratio of GMS through a topological property called the local-pooling factor of the network graph. We then develop an iterative procedure to estimate the local-pooling factor under a large class of network topologies and interference models. We use these results to study the worst-case efficiency ratio of GMS on two classes of network topologies. We show how these results can be applied to tree networks to prove that GMS achieves the full capacity region in tree networks under the K -hop interference model. Then, we show that the worst-case efficiency ratio of GMS in geometric unit-disk graphs is between 1 6 and 1 3.