Journal article
On Characterizing the Local Pooling Factor of Greedy Maximal Scheduling in Random Graphs
IEEE/ACM transactions on networking, v 24(4), pp 2086-2099
Aug 2016
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
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-Rényi (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.
Metrics
16 Record Views
Details
- Title
- On Characterizing the Local Pooling Factor of Greedy Maximal Scheduling in Random Graphs
- Creators
- Jeffrey Wildman - Drexel UniversitySteven Weber - Drexel University
- Publication Details
- IEEE/ACM transactions on networking, v 24(4), pp 2086-2099
- Publisher
- IEEE
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Electrical and Computer Engineering
- Web of Science ID
- WOS:000382358700012
- Scopus ID
- 2-s2.0-84938796089
- Other Identifier
- 991019167321204721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Computer Science, Hardware & Architecture
- Computer Science, Theory & Methods
- Engineering, Electrical & Electronic
- Telecommunications