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.
As mentioned, checking LoP conditions can be computationally prohibitive, particularly under arbitrary interference models. Therefore, algorithms to easily estimate or bound ( ) and ( ) are of interest and immediate use in studying GMS stability. Joo @cite_9 provide a lower bound on ( ) by the inverse of the largest interference degree of a nested sequence of increasing subsets of links in (G ), and provide an algorithm for computing the bound. Li @cite_18 refine this algorithm to provide individual per-link bounds on ( ). Under the primary interference model, Joo @cite_30 show that ( (2 -1) ) is a lower bound for ( ). Leconte @cite_31 , Li @cite_18 , and Birand @cite_8 note that a lower bound for ( ) is derived from the ratio of the min- to max-cardinality maximal schedules.
@cite_30 @cite_18 @cite_8 @cite_9 @cite_31
2106717724 2063925036 2039917366 1995120351 2017161886
Greedy maximal matching (GMM) is an important scheduling scheme for multi-hop wireless networks. It is computationally simple, and has often been numerically shown to achieve throughput that is close to optimal. However, to date the performance limits of GMM have not been well understood. In particular, although a lower bound on its performance has been well known, this bound has been empirically found to be quite loose. In this paper, we focus on the well-established node-exclusive interference model and provide new analytical results that characterize the performance of GMM through a topological notion called the local-pooling factor. We show that for a given network graph with single-hop traffic, the efficiency ratio of GMM (i.e., the worst-case ratio of the throughput of GMM to that of the optimal) is equal to its local-pooling factor. Further, we estimate the local-pooling factor for arbitrary network graphs under the node-exclusive interference model and show that the efficiency ratio of GMM is no smaller than d* 2d* - 1 in a network topology of maximum node-degree d*. Using these results, we identify specific network topologies for which the efficiency ratio of GMM is strictly less than 1. We also extend the results to the more general scenario with multi-hop traffic, and show that GMM can achieve similar efficiency ratios when a flow-regulator is used at each hop. One of the major challenges in wireless networking is how to optimize the link scheduling decisions under interference constraints. Recently, a few algorithms have been introduced to address the problem. However, solving the problem to optimality for general wireless interference models is known to be NP-hard. The research community is currently focusing on finding simpler suboptimal scheduling algorithms and on characterizing the algorithm performance. In this paper, we address the performance of a specific scheduling policy called Longest Queue First (LQF), which has gained significant recognition lately due to its simplicity and high efficiency in empirical studies. There has been a sequence of studies characterizing the guaranteed performance of the LQF schedule, culminating at the construction of the σ-local pooling concept by In this paper, we refine the notion of σ-local pooling and use the refinement to capture a larger region of guaranteed performance. 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 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. In this paper, we derive new bounds on the throughput efficiency of Greedy Maximal Scheduling (GMS) for wireless networks of arbitrary topology under the general k -hop interference model. These results improve the known bounds for networks with up to 26 nodes under the 2-hop interference model. We also prove that GMS is throughput-optimal in small networks. In particular, we show that GMS achieves 100 throughput in networks with up to eight nodes under the 2-hop interference model. Furthermore, we provide a simple proof to show that GMS can be implemented using only local neighborhood information in networks of any size.