PaperlayerView exact revision on arXiv

Source-linked AI summary

Spatial Deep Learning for Wireless Scheduling

Wei Cui, Kaiming Shen, Wei Yu

arXiv:1808.01486v3eess.SPcs.ITcs.LG

TL;DR

Dense wireless scheduling is difficult because conventional methods require extensive channel estimation and computationally hard optimization. This paper learns schedules from geographic locations using spatial convolutions and feedback, achieving near-optimal sum-rate performance and competitive proportional-fairness utility while generalizing across layouts and densities.

  • Problem

    Conventional scheduling requires estimating many interfering channels and solving computationally complex optimization problems in dense networks.

  • Method

    The paper uses unsupervised deep learning with geographic spatial convolutions, feedback stages, and binary reweighting for proportional-fair scheduling without explicit CSI.

  • Results

    The spatial learning approach achieves more than 92% of FPLinQ's average sum rate in all presented cases without explicitly knowing the channels.

  • Takeaways & Limitations

    The learned scheduler generalizes to larger layouts and different link densities without further training, while the proportional-fair extension achieves near-optimal network utility.

Abstract

from arXiv · show

The optimal scheduling of interfering links in a dense wireless network with full frequency reuse is a challenging task. The traditional method involves first estimating all the interfering channel strengths then optimizing the scheduling based on the model. This model-based method is however resource intensive and computationally hard because channel estimation is expensive in dense networks; furthermore, finding even a locally optimal solution of the resulting optimization problem may be computationally complex. This paper shows that by using a deep learning approach, it is possible to bypass the channel estimation and to schedule links efficiently based solely on the geographic locations of the transmitters and the receivers, due to the fact that in many propagation environments, the wireless channel strength is largely a function of the distance dependent path-loss. This is accomplished by unsupervised training over randomly deployed networks, and by using a novel neural network architecture that computes the geographic spatial convolutions of the interfering or interfered neighboring nodes along with subsequent multiple feedback stages to learn the optimum solution. The resulting neural network gives near-optimal performance for sum-rate maximization and is capable of generalizing to larger deployment areas and to deployments of different link densities. Moreover, to provide fairness, this paper proposes a novel scheduling approach that utilizes the sum-rate optimal scheduling algorithm over judiciously chosen subsets of links for maximizing a proportional fairness objective over the network. The proposed approach shows highly competitive and generalizable network utility maximization results.

I. INTRODUCTION

Wireless link scheduling must select compatible links under interference, but model-based methods require costly channel estimation and difficult nonconvex discrete optimization. The paper proposes learning schedules from geographic locations and evaluates this approach against established optimization and heuristic benchmarks.

  • Motivation: Dense full-reuse networks require selecting mutually compatible links to limit interference while maximizing network utility.Nearby simultaneously active links can produce significant interference.
  • Limitations of traditional scheduling: Model-based scheduling estimates direct and interfering channels before optimizing the schedule, requiring substantial resources in dense networks.The approach also faces pilot contamination and repeated channel estimation within each coherence block.
  • Limitations of traditional scheduling: Nonconvex rate functions and binary scheduling variables make the resulting optimization a computationally complex integer programming problem.This complexity challenges real-time implementation even when full channel knowledge is available.
  • Proposed approach: Spatial deep learning learns scheduling from neighboring transmitter and receiver locations, using geographic spatial convolutions and multiple stages instead of exact channel estimates.The approach is motivated by interference patterns being largely determined by relative node locations in many deployment scenarios.
  • Evaluation scope: The proposed architecture targets a large portion of the state-of-the-art sum rate without explicit CSI and is trained unsupervised for comparison with benchmarks including FPLinQ.The paper considers both equal-weight sum-rate maximization and adaptive-weight scheduling for network utility and fairness.

III. DEEP LEARNING BASED LINK SCHEDULING FOR SUM-RATE MAXIMIZATION

For sum-rate scheduling, the paper replaces full CSI with geographic location information and learns schedules from spatial representations of transmitter-receiver layouts. The input scales linearly with the number of links, while the network represents link densities on a geographic grid.

  • III. Deep learning based link scheduling for sum-rate maximization: The sum-rate setting uses equal weights, making it simpler than weighted rate-sum scheduling while still requiring selection of links from path-loss and geographic information.The objective is to determine which subset of links should be scheduled using location-derived information.
  • A. Learning Based on Geographic Location Information: Geographic location information replaces O(N^2) CSI entries as the neural-network input, reducing the input scaling to O(N).The location input consists of transmitter and receiver coordinates for each link.
  • A. Learning Based on Geographic Location Information: Using geographic locations as a CSI substitute relies on channel gains being largely determined by distance-dependent path-loss and location in relevant deployment environments.The paper identifies outdoor, rural, and remote settings as especially compatible with this assumption, while fast fading makes CSI a stochastic function of location.
  • A. Learning Based on Geographic Location Information: The proposed learning target is the mapping from geographic location information to binary scheduling decisions, rather than the traditional mapping from CSI to schedules.This design bypasses explicit channel input to the neural network.
  • B. Transmitter and Receiver Density Grid as Input: Continuous transmitter and receiver coordinates are quantized into an M × M grid by assigning each endpoint to a cell indexed by its row and column.Each link is represented by the grid-cell indices of its transmitter and receiver.
  • B. Transmitter and Receiver Density Grid as Input: Two M × M density matrices count active transmitters and receivers in each cell, with the activation pattern initialized to all ones and updated iteratively.These matrices provide the spatial representation used as the schedule changes.

C. Novel Deep Neural Network Structure

The network combines spatial convolutions of transmitter and receiver density grids with fully connected mappings to learn per-link scheduling features and outputs.

  • C. Novel Deep Neural Network Structure: The iterative forward path combines a geographic convolution stage with a fully connected stage for each transmitter-receiver pair.The convolution captures neighboring interference patterns, while the fully connected network models the nonlinear schedule mapping.
  • 1) Convolution Stage:: Spatial filters operate on transmitter and receiver density grids to estimate interference each link causes and receives from neighboring links.The resulting quantities are denoted TxINT_i and RxINT_i, with each link’s own transmitter and receiver excluded from the respective convolution sums.
  • 1) Convolution Stage:: Trained convolution filters learn distance-dependent channel coefficients and exhibit circular symmetry with radial decay.The filter value at a transceiver’s relative location can also provide the direct channel strength for that link.
  • 2) Fully Connected Stage:: Each link’s fully connected feature vector includes interference estimates, direct channel strength, layout-wide strength bounds, and the previous iteration’s output.The output x_i is a relaxed scheduling variable or continuous power value in [0, 1].
  • 2) Fully Connected Stage:: Minimum and maximum direct channel strengths characterize the strength range when D2D pairwise distances are roughly uniform.For nonuniform distances, percentile values such as the 10th and 90th percentiles may reduce sensitivity to outliers.

3) Feedback Connection:

Feedback iterations update interference estimates using the previous continuous activation vector before final binary scheduling decisions are produced. Shared per-link components make the model scalable and distributable under a homogeneity assumption.

  • 3) Feedback Connection:: Each feedback iteration rebuilds the density grids from the previous continuous activation vector so deactivated links no longer contribute to subsequent interference estimates.The network repeats this forward computation for a fixed number of iterations and experimentally converges within a small number of iterations.
  • 3) Feedback Connection:: After the fixed iterations, the final continuous outputs are quantized into binary values representing scheduling decisions.The quantized output is denoted Q in the overall network depiction.
  • 3) Feedback Connection:: Per-link neural networks are decoupled at the fully connected stage, enabling distributed scheduling, while fixed convolution filters cover neighboring non-negligible interferers.The overall model is therefore scalable with respect to network size.
  • 3) Feedback Connection:: Tied convolution and neural-network weights assume similar propagation environments across links, allowing direct reuse without adjustment or retraining as layouts and link counts grow.This reuse claim is explicitly conditioned on the stated homogeneity assumption.

D. Training Process

The model is trained unsupervised on randomly deployed networks to maximize sum rate, then discretizes learned power variables into scheduling decisions. Stochastic feedback addresses oscillatory updates, and tests show performance above 92% of FP across examined distance distributions.

  • Training setup: Unsupervised training maximizes target sum rate over randomly located links with varied transmitter-receiver distance distributions.The training set uses 800,000 layouts of 50 D2D pairs, with dmin and dmax sampled to vary link distances.
  • Training setup: Scheduling decisions are obtained by discretizing optimized power variables, while continuous outputs preserve gradient flow during training.The resulting unsupervised process effectively performs sum-rate power control before converting outputs into binary activation decisions.
  • Symmetry breaking: Parallel staged updates can cause mutually interfering links to oscillate between activation and deactivation instead of converging to a good schedule.For two closely located links, simultaneous updates can repeatedly turn both links off and then back on, although one should remain active.
  • Symmetry breaking: A 50% stochastic feedback rule breaks update symmetry by independently choosing updated or old activation entries during both training and testing.The mechanism feeds back updated entries with 50% probability and old entries with 50% probability.
  • Testing: More than 92% of FP average sum rate is achieved across all presented test distance distributions without explicitly knowing the channels.The spatial learning method also outperforms the greedy heuristic and other benchmarks by large margins.
  • Testing: The learned schedules remain close to FP outputs across tested cases, whereas greedy scheduling can be suboptimal because it never revisits earlier activations.Greedy scheduling activates the strongest links first and can prematurely commit to poor decisions.

B. Generalizability to Arbitrary Topologies

The spatial network is designed around local estimates of direct channel strength and aggregate interference, supporting evaluation on larger layouts and different link densities without retraining.

  • Generalization scope: Local spatial estimates suggest that the trained network can extend beyond its original layout dimensions and link distributions.The estimates use information from a local region surrounding each link’s transmitter and receiver.
  • Generalization scope: Generalization is evaluated on larger layouts at fixed density and on layouts with altered link density, using 500 random layouts per test.No further neural-network training is performed for these evaluations.

1) Generalizability to Layouts of Large Sizes:

The network generalizes to larger and denser layouts, retaining near-optimal scheduling under moderate density increases, but performance and convergence degrade at extreme density and under fast fading.

  • Large layouts: Layouts expand to 2.5 km by 2.5 km and 1,250 links while preserving link density and distance distribution.The resulting sum rates are reported relative to FP.
  • Large layouts: The neural network generalizes well to larger dimensions, with performance very close to FP while using location information rather than CSI.Greedy also performs well in these larger layouts but requires CSI.
  • Different densities: With up to a 4-fold increase in interfering-link density, the neural network remains near optimal and especially outperforms greedy scheduling in sparse networks.The density experiment varies the number of links from 10 to 500 in a fixed 500 m by 500 m region.
  • Different densities: At 500 links or more, convergence becomes harder and performance drops; further density increases may require training data with higher density.One reported case requires 50 iterations to reach satisfactory rate performance.
  • Fast fading: Under Rayleigh fast fading, performance drops relative to CSI-based FP and greedy, but matches FP that excludes fast-fading knowledge.The network is trained without fading, while fading is introduced only in testing.
  • Complexity: For fixed layout size, FPLinQ and greedy have O(N^2) complexity, whereas the neural network scales as O(N).The neural-network scaling assumes a fixed geographic region size.

2) Experimental Verification:

Experiments report a substantial runtime advantage for the spatial network, while comparing training strategies and extending the method toward proportional-fair scheduling.

  • Runtime verification: The neural network’s measured computation time is approximately constant and several orders of magnitude below FP for large D2D layouts.The comparison uses a GPU for the parallel neural network and a CPU for sequential FP and greedy implementations.
  • Runtime verification: The complexity comparison depends on implementation, and customized spatial convolutions could reduce the neural network’s runtime constant.The reported TensorFlow convolution computes across the entire geographic area rather than only locations of interest.
  • Runtime verification: The proposed method combines near-optimal scheduling with O(N) geographic-location inputs instead of O(N^2) channel-state information.The conclusion emphasizes this advantage for large networks after training on layouts with 50 links.
  • Training comparison: Unsupervised training generally performs better than supervised training when link distances are similar because many distinct local optima can confuse supervised learning.Supervised learning is competitive for the 2 m–65 m distance distribution, while direct sum-rate optimization is often better for more general distributions.
  • Proportional fairness: Sum-rate scheduling favors shorter or low-interference links, motivating a proportional-fair objective for practical scheduling.The paper frames fairness through long-term average rates and a concave utility, using U(·)=log(·) for proportional fairness.
  • Proportional fairness: Proportional fairness is approximated by a sequence of weighted sum-rate problems whose weights are updated each time slot.The weights can take any positive real values, making direct incorporation into one neural network difficult.

B. Challenge in Learning to Maximize Weighted Sum Rate

Learning proportional-fair schedules directly from weights is difficult because small weight changes can cause abrupt schedule changes. The paper instead approximates proportional weights with binary weights, then applies sum-rate scheduling to the selected subset.

  • Learning challenge: Small changes in proportional-fair weights can produce drastic changes in FP schedules, making the weight-to-schedule mapping highly sensitive.The challenge is amplified by sharp local optima and the non-uniform sequence of weights encountered during scheduling.
  • Proposed approach: The proposed method emulates weighted sum-rate maximization by applying the sum-rate neural network over a judiciously chosen subset of links.This reuses the network’s ability to generalize across topologies while avoiding direct learning of the full weight-to-schedule mapping.
  • Binary reweighting: Candidate links are shortlisted using proportional-fair weights alone, after which deep learning refines the scheduling decision.The shortlist can be viewed as approximating proportional-fair weights with a binary vector whose entries are 0 or 1.
  • Binary reweighting: The binary approximation prioritizes higher-weight links by selecting the number of largest entries that maximizes the normalized dot product with the original weight vector.Geometrically, the selected binary vector is closest in angle to the normalized proportional-fair weight vector.
  • Binary reweighting: After sorting the weights, the method sets the largest k entries to 1 and the remainder to 0, then performs sum-rate optimization over the selected links.The value of k is found by linear search using the binary-approximation objective.

D. Utility Analysis of Binary Reweighting Scheme

The paper analyzes binary reweighting as an approximation to proportional-fair utility. The analysis links the scheme to a utility with similar trends, while identifying threshold adaptation and saturation as important limitations.

  • Utility interpretation: The binary reweighting scheme is a heuristic for fair scheduling, and its rigorous analysis is challenging.The paper provides a justification through a utility-function interpretation rather than a rigorous analysis.
  • Fixed-threshold scheme: With a fixed threshold θ > 0, binary weights select links according to whether their original weights exceed that threshold.The original weights are related to users’ long-term average rates through wi = 1/¯Ri.
  • Utility interpretation: A reverse sigmoid function is introduced to mimic the sharp reverse-step transition of the fixed-threshold binary weights.The parameter κ controls the steepness of the resulting function of the average rate.
  • Utility interpretation: The corresponding utility is derived from the weight relationship wi = U′(¯Ri), with α and β acting only as scaling and offset parameters.The paper states that these parameters do not affect scheduling performance.
  • Comparison with proportional fairness: The fixed-threshold utility follows the same trend as proportional-fair utility, as illustrated for θ = 0.1 in Fig. 10.The comparison concerns the binary weighting scheme’s utility and the log-utility proportional-fair function.
  • Scope and limitation: The analysis is approximate because the proposed scheme adapts its threshold at each step rather than keeping it fixed.Unlike proportional-fair utility, the binary-reweighting utility saturates above the threshold instead of growing logarithmically.

VI. PERFORMANCE OF PROPORTIONAL FAIRNESS SCHEDULING

The evaluation applies binary reweighting to proportional-fair scheduling by repeatedly solving sum-rate problems over selected link subsets. Across same-size, same-density layouts, the approach achieves strong utility and favorable low-rate fairness, using geographic information without explicit CSI.

  • Evaluation setup: The evaluation tests proportional-fair scheduling across layouts with fixed size and link density, larger layouts at the same density, and larger layouts at different densities.Testing uses distinct layouts scheduled over finite time slots, with mean rates computed by averaging instantaneous rates.
  • Evaluation setup: Mean link rates are averaged over time, and each link utility is the logarithm of its mean rate in Mbps.Network utility is the sum of these link utilities, averaged across distinct layouts.
  • Method: The proposed method solves a sum-rate maximization problem over a subset of links using binary reweighting in each time slot.The comparison includes Max Weight and Weighted Greedy baselines in addition to previously described schemes.
  • Evaluation setup: The same-size evaluation uses 500m × 500m layouts containing 50 D2D links across four link-distance distributions.The tested distributions include 30–70m, 2–65m, 10–50m, and fixed 30m distances.
  • Results: The proposed deep learning method with binary reweighting achieves excellent log-utility values relative to FP and noticeably exceeds Weighted Greedy without explicit CSI.The CDF of mean rates is also reported for the 30–70m link-distance case.
  • Results: The method has better CDF performance than FP in the low-rate regime but a worse mean rate beyond the 80-percentile range.The paper attributes this trade-off to the binary reweighting scheme’s implicit utility being higher at low rates and saturating at high rates.

2) Performance on Larger Layouts with Same Link Density:

The neural network is evaluated on larger layouts with unchanged or different link density, without further training. It remains competitive with established methods while using geographic information and binary weight approximations.

  • Performance on Larger Layouts with Same Link Density:: For larger layouts with the same link density, testing uses two link-distance settings: uniform 2–65m and fixed 30m.The results are summarized in the proportional-fairness evaluation for larger layouts.
  • Performance on Larger Layouts with Same Link Density:: Under proportional fairness, spatial deep learning generalizes well to larger layouts and remains competitive with FP and Weighted Greedy.The method uses only O(N) geographic location information as input together with binary weight approximation.
  • Performance on Larger Layouts with Same Link Density:: On layouts with different link densities, the neural network competes well with FP in log utility and significantly outperforms Weighted Greedy.This evaluation averages sum log utility over 10 testing layouts and includes a 200-link, fixed-30m case visualized by a mean-rate CDF.
  • VII. CONCLUSION: The paper reports near-optimal sum-rate scheduling based on geographic spatial convolution and feedback stages, eliminating costly channel estimation in certain network environments.The architecture estimates interfering-neighbor density and progressively adjusts link activity patterns.
  • VII. CONCLUSION: The neural network generalizes to larger layouts and different link densities without further training, providing a computational-complexity advantage on larger wireless networks.The comparison is made against traditional optimization algorithms and competing heuristics.
  • VII. CONCLUSION: Binary reweighting extends the method to proportional-fair scheduling, achieving near-optimal network utility while retaining the ability to bypass CSI.The conclusion frames this as preserving the method’s geographic-information advantage.
Loading 1808.01486v3…