PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Embedding based Wireless Link Scheduling with Few Training Samples

Mengyuan Lee, Guanding Yu, Geoffrey Ye Li

arXiv:1906.02871v3eess.SPcs.NI

TL;DR

D2D link scheduling is a difficult combinatorial problem traditionally requiring accurate CSI and substantial computation. The paper uses distance-based graph embeddings and a classifier to schedule links without CSI, reporting near-optimal performance with hundreds of training layouts and competitiveness across scenarios. The authors also identify equal-weight and shadowing settings as limitations of the current method.

  • Problem

    D2D link scheduling is generally NP-hard, while traditional methods require accurate CSI and prior CSI-free spatial learning requires hundreds of thousands of training layouts.

  • Method

    The method represents D2D pairs and interference links as a graph, computes distance-based low-dimensional node embeddings, and uses supervised or unsupervised learning with classifier-based scheduling and K-nearest-neighbor graphs.

  • Results

    The method achieves 95.21% of FPLinQ’s sum rate with 500 training layouts without explicitly knowing CSI, while topology generalization incurs 2.24% and 3.42% average-sum-rate losses for 10 and 100 D2D pairs.

  • Takeaways & Limitations

    Graph embedding is promising for wireless optimization tasks whose outcomes depend mainly on network topology, when graph representations and features are carefully designed.

  • Takeaways & Limitations

    The current method assumes equal D2D-pair weights and its performance drops significantly when shadowing is introduced in testing channels.

Abstract

from arXiv · show

Link scheduling in device-to-device (D2D) networks is usually formulated as a non-convex combinatorial problem, which is generally NP-hard and difficult to get the optimal solution. Traditional methods to solve this problem are mainly based on mathematical optimization techniques, where accurate channel state information (CSI), usually obtained through channel estimation and feedback, is needed. To overcome the high computational complexity of the traditional methods and eliminate the costly channel estimation stage, machine leaning (ML) has been introduced recently to address the wireless link scheduling problems. In this paper, we propose a novel graph embedding based method for link scheduling in D2D networks. We first construct a fully-connected directed graph for the D2D network, where each D2D pair is a node while interference links among D2D pairs are the edges. Then we compute a low-dimensional feature vector for each node in the graph. The graph embedding process is based on the distances of both communication and interference links, therefore without requiring the accurate CSI. By utilizing a multi-layer classifier, a scheduling strategy can be learned in a supervised manner based on the graph embedding results for each node. We also propose an unsupervised manner to train the graph embedding based method to further reinforce the scalability and generalizability and develop a K-nearest neighbor graph representation method to reduce the computational complexity. Extensive simulation demonstrates that the proposed method is near-optimal compared with the existing state-of-art methods but is with only hundreds of training samples. It is also competitive in terms of scalability and generalizability to more complicated scenarios.

I. INTRODUCTION

D2D link scheduling is an NP-hard, non-convex problem whose traditional solutions require accurate CSI and can be computationally impractical. The paper proposes graph embedding with distance-based features, limited training layouts, unsupervised learning, and K-nearest-neighbor representations to address these constraints.

  • D2D scheduling selects a subset of mutually interfering links to maximize network utility, but no efficient global optimal algorithm is available for dense networks.
  • Traditional optimization methods require accurate CSI, while optimal methods can have exponential worst-case complexity and sub-optimal methods may suffer from multiple local optima.
  • The proposed graph embedding method represents each D2D pair as a node, learns low-dimensional features from interference topology without CSI estimation, and classifies each pair as active or inactive.
  • Hundreds of training network layouts are reported to achieve near-optimal performance without accurate CSI, addressing the large-data requirement of prior spatial learning.
  • The method uses distance-based node and edge features with uniform quantization, reducing feature dimension for graph embedding.
  • The paper adds unsupervised training for scalability and a K-nearest-neighbor graph representation to reduce computational complexity.

II. WIRELESS LINK SCHEDULING IN D2D NETWORKS

The D2D system models transmitter–receiver pairs in a shared-bandwidth network and formulates scheduling as selecting active links to maximize weighted sum rate under interference. This produces a difficult combinatorial optimization problem that motivates an ML-based alternative without CSI.

  • The system contains L randomly located D2D pairs, each with a transmitter, receiver, bounded pairwise distance, and fixed transmit power.
  • All D2D pairs reuse the full bandwidth, so activating many links simultaneously can cause severe interference and reduce data rates.
  • Scheduling selects a subset of D2D pairs for activation to maximize the overall network throughput.
  • With weighted instantaneous sum rate as the objective, each pair’s weight can encode fairness or priority determined in advance.
  • The resulting problem is combinatorial and difficult, while traditional approaches require accurate CSI and prior ML methods without CSI require many training layouts.

III. GRAPH EMBEDDING BASED WIRELESS LINK SCHEDULING

The paper models the D2D network as a fully connected weighted directed graph and uses node-level graph embeddings to support binary link-activation decisions. Structure2vec iteratively incorporates node features, directed edge weights, and neighborhood information into low-dimensional representations.

  • Each D2D pair is represented as a node and each interference link as a directed edge, producing a fully connected weighted directed graph.
  • Graph embedding converts graph data into a low-dimensional vector for a node, edge, substructure, or whole graph; here, node embeddings support activation decisions.
  • Structure2vec initializes node embeddings and updates them iteratively using node features, neighboring nodes, edge weights, and a nonlinear mapping.
  • After T iterations, each node embedding contains information from its T-hop neighborhood determined by graph topology.
  • Compared with kernel-based extraction, structure2vec uses learnable nonlinear mappings without requiring a large kernel matrix and can be trained with fewer layouts.

2) Structure2Vec for Wireless Link Scheduling:

For wireless scheduling, the paper adapts structure2vec by combining communication features, incoming interference, and neighboring embeddings, while quantizing continuous distances into discrete one-hot features. The resulting embeddings provide inputs for scheduling classification without relying on exact CSI.

  • The embedded mean-field implementation uses ReLU as its nonlinear feature mapping and jointly learns weight matrices with the binary classification task.
  • For the fully connected graph, two embedding iterations are usually sufficient to propagate node features across the graph, although the update rule is heuristic.
  • The graph embedding stage is designed to produce node representations that capture communication ability, received interference, and interference caused to neighboring D2D pairs.
  • The chosen features use distances because scheduling does not necessarily require exact CSI and is substantially determined by relative transmitter–receiver locations.
  • Because continuous link distances do not fit the discrete feature structure directly, the method quantizes distances before constructing node and edge features.
  • Using q bits, uniform quantization divides the range into 2^q intervals and represents each interval with a 2^q-dimensional one-hot vector.

C. Multi-layer Classifier for Wireless Link Scheduling

The method uses graph embeddings to represent each D2D pair and a multi-layer classifier to predict link activation. Embedding and classifier parameters are jointly learned for scheduling.

  • Each D2D pair is represented by a p-dimensional embedding vector reflecting its communication ability and interference pattern.
  • The classifier treats link scheduling as binary classification, predicting whether each D2D pair should be activated.Its output indicates activation or non-activation probabilities.
  • The overall network combines graph embedding with multi-layer classification, with embedding parameters W and classifier parameters F.
  • Discriminative training jointly learns W and F in a supervised manner for the ultimate scheduling task.
  • Training labels are scheduling results generated by FPLinQ, where each binary label indicates whether a D2D link is activated.

IV. PERFORMANCE TEST RESULTS

The evaluation uses simulated D2D networks, neural-network tuning, and FPLinQ-generated training labels. Performance is assessed with classifier accuracy and normalized average sum rate on held-out layouts.

  • Simulation Setup: The experiments use a 500 m by 500 m area containing 50 D2D pairs under the ITU-1411 short-range outdoor channel model.
  • Simulation Setup: FPLinQ outputs after 100 iterations are used to generate training data because prior experiments found their numerical performance satisfactory.
  • Simulation Setup: Classifier accuracy measures agreement with FPLinQ scheduling patterns, while average sum rate is normalized by FPLinQ's achieved sum rate.
  • Simulation Setup: The experiments tune hidden-layer size, embedding dimension, and iteration count by hold-out validation.The reported results average performance over 1,000 testing network layouts.

B. Convergence Performance

With 500 training layouts, classifier accuracy and average sum rate converge rapidly, although the two metrics can occasionally mismatch. The experiments also examine training-data requirements and comparisons with existing algorithms.

  • Convergence Performance: 30-40 training epochs are sufficient for average sum rate and classifier accuracy to converge with 500 training network layouts.
  • Convergence Performance: Higher classifier accuracy mostly corresponds to higher average sum rate, but occasional mismatches produce lower sum rate despite higher accuracy.
  • Impact of the Number of Training Network Layouts: Small training datasets are preferred because labeled layouts can be difficult and expensive to obtain in wireless communication systems.
  • Impact of the Number of Training Network Layouts: Using fewer training layouts generally provides faster training and lower memory consumption for real-time implementation.
  • Comparison with Existing Methods: With 500 training layouts, the proposed method achieves 95.21% of FPLinQ's sum rate without explicitly knowing CSI.
  • Comparison with Existing Methods: Compared with spatial learning, the method uses far fewer layouts while incurring a 3.15% sum-rate loss relative to FPLinQ.Spatial learning uses 800,000 training layouts and reaches 98.36% of FPLinQ's sum rate.

E. Scalability to Scenarios with Different Topologies

The method remains effective as network topology changes, but performance depends on pairwise-distance diversity and feature quantization. Increasing network size is handled more robustly than collapsing all pairwise distances to one value.

  • Scalability to Scenarios with Different Numbers of D2D Pairs: Doubling the number of D2D pairs from 50 to 100 decreases average sum rate by only 2.95%.
  • Scalability to Scenarios with Different Numbers of D2D Pairs: The method remains acceptable for scenarios with 500 links using only 500 training network layouts.
  • Scalability to Scenarios with Different Numbers of D2D Pairs: Hyperparameters selected on the 50-pair scenario can be applied to larger scenarios with satisfactory results.
  • Scalability to Scenarios with Different Pairwise Distances: Performance deteriorates as the pairwise-distance distribution interval decreases because node-feature diversity also decreases.
  • Scalability to Scenarios with Different Pairwise Distances: When every pairwise distance is 30 m, the graph has no node features and only edge features, making scheduling harder to learn.
  • Impact of the Number of Quantization Bits: Classifier accuracy and average sum rate initially improve with more quantization bits, then fluctuate beyond a threshold.Additional bits increase feature information and model complexity; excessive bits introduce redundancy.
  • Impact of the Number of Quantization Bits: Choosing quantization bits requires balancing model complexity against scheduling performance.

G. Generalizability to Scenarios with Different Topologies

The proposed method generalizes across D2D network topologies when the quantization-bit count is fixed, with small average sum-rate losses for smaller and larger networks. Shadowing reduces performance because the method uses distance information, while training with matching shadowing provides little additional gain.

  • Generalizability to Different Topologies: Fixing q = 3, a model trained with 500 samples from 50 D2D pairs generalizes to scenarios with 10 and 100 pairs.The reported average sum-rate losses are 2.24% and 3.42%, respectively.
  • Impact of Shadowing: The proposed method uses distance information for link scheduling, so shadowing is not directly learned as a feature.Shadowing changes the labels while leaving the graphical model unchanged.
  • Impact of Shadowing: With shadowing, average sum rate decreases as shadowing standard deviation increases.The comparison uses 50 D2D pairs, q = 3, and averages performance over 1,000 testing layouts.
  • Impact of Shadowing: Training with matching shadowing improves average sum rate by less than 1% compared with training without shadowing.The paper reports that full-training and generalization performances remain very close.
  • Impact of Shadowing: Including shadowing information in node and edge features, or communication-link CSI in node features, is proposed as future work.The paper identifies this as a way to address performance loss under stochastic channel effects.
  • Computational Complexity: The method has similar computational complexity to FPLinQ, does not require explicit CSI, and uses fewer training layouts than spatial learning.It is not computationally competitive with spatial learning, which has lower complexity under fixed region size.

V. DISCUSSION AND FURTHER IMPROVEMENT

The discussion identifies training-objective selection, scalability, and computational complexity as key issues, then introduces unsupervised learning to optimize sum rate directly and improve scalability across pairwise-distance distributions.

  • Discussion and Further Improvement: The authors identify three issues: matching the training goal to network utility, strengthening scalability, and reducing computational complexity.These questions motivate the further improvements presented in this section.
  • Unsupervised Learning: Unsupervised learning directly maximizes sum rate, avoids FPLinQ-generated labels, and may improve performance when pairwise-distance intervals are small.The graph representation, embedding, and classifier remain unchanged; the training process is modified.
  • Unsupervised Learning: The embedding parameters and classifier parameters are learned together in the unsupervised manner.The training dataset contains graph representations without corresponding scheduling results.
  • Unsupervised Learning: The unsupervised objective combines reciprocal sum rate with a penalty for full activation to avoid a local optimum activating all links.The penalty is particularly relevant when equal-distance links provide insufficient node-feature variation.

2) Performance Test:

Unsupervised learning has little effect on scalability across different numbers of D2D pairs but improves scalability across pairwise-distance distributions. A K-nearest neighbor graph is introduced to reduce embedding complexity.

  • Performance Test: Using 500 training layouts and q = 3, the unsupervised method is evaluated on 1,000 testing layouts across pair counts and pairwise distances.The experiments compare supervised and unsupervised training under the same wireless-system and graph-embedding parameters.
  • Performance Test: For different numbers of D2D pairs, unsupervised and supervised learning differ by less than 0.7% in average sum rate.The result indicates no meaningful scalability advantage across pair counts.
  • Performance Test: For different pairwise-distance distributions, unsupervised learning generally achieves higher sum rate than supervised learning.The performance gain increases as the pairwise-distance interval decreases.
  • Performance Test: 7.06%: average sum rate increases with unsupervised learning when all pairwise distances are 30 m.This is the largest specific gain reported in the presented pairwise-distance cases.
  • Comparison between Supervised and Unsupervised Learning: Unsupervised learning converges more slowly and requires more training time, whereas supervised learning avoids the full activation problem.The paper concludes that the learning method should be selected according to the practical setting.
  • K-Nearest Neighbor Graph: A K-nearest neighbor graph replaces the fully connected graph to reduce graph-embedding computational complexity.The representation considers only the top K nearest transmitters to each D2D pair’s receiver because distant interference can be negligible.

2) Performance Test:

The K-nearest neighbor graph representation preserves performance while reducing the complexity of graph embedding-based scheduling. Tests also indicate stronger scalability with more D2D pairs, but limited scalability across pairwise distances remains a boundary of the current method.

  • Impact of the values of K: Around 81% classifier accuracy and 95% average sum rate were maintained across K values with 50 D2D pairs.The test used q = 3, 500 training layouts, and 1,000 testing layouts.
  • Impact of the values of K: The K-nearest neighbor representation reduces computational complexity without performance loss by retaining dominant interference information.This finding follows the comparison with the fully-connected graph representation.
  • Scalability Test: The 10-nearest neighbor method performs similarly for 30 and 50 links and slightly better than the fully-connected method for larger networks.The reported average sum rates are very close for 30 and 50 links, while the advantage increases with more D2D pairs.
  • Scalability Test: The method has limited scalability for different pairwise distances, while asymmetric K-nearest neighbor graphs can increase node diversity in such scenarios.The paper identifies limited pairwise-distance scalability as a current limitation and motivates K-nearest neighbor representations as a reinforcement.
Loading 1906.02871v3…