Scalable Interference Graph Learning for Low-Latency Wi-Fi Networks using Hashing-based Evolution Strategy

This paper proposes a scalable interference graph learning framework that combines an evolution strategy with deep hashing to efficiently optimize RTWT slot assignments for low-latency Wi-Fi 7 networks, significantly improving slot efficiency, reducing packet loss, and accelerating training and inference times in dense environments.

The Gist

Imagine a massive, high-tech factory floor where hundreds of tiny robots (the Wi-Fi devices) need to talk to a central brain (the Access Points) to report their status. They need to do this constantly, instantly, and without a single mistake. If a robot misses a beat, a machine might overheat, or a robot might crash into a wall.

In the old days, these robots used a "shout-first" method (called CSMA/CA). They would all try to talk at once. If two robots spoke simultaneously, their voices would clash, causing a mess. They'd have to wait, back off, and try again. This caused delays and accidents.

Wi-Fi 7 introduced a new rule: The "Quiet Schedule" (RTWT).
Instead of shouting, every robot gets a specific time slot to speak. If Robot A speaks at 10:00, Robot B waits until 10:01. This eliminates the shouting matches.

The Problem:
But here's the catch: In a factory with 1,000 robots, you can't give every single robot its own unique minute. That would take forever! You want to pack them in. You want Robot A and Robot B to speak at the same time if they are far enough apart that they won't hear each other. But if they are close, they need different slots.

Figuring out who can share a slot and who can't is like trying to solve a giant, moving puzzle. If you get it wrong, the robots crash. If you get it too conservative (giving everyone their own slot), the schedule drags on too long, and the data becomes outdated.

The Paper's Solution: "The Smart Scheduler"
The authors propose a new system called Scalable Interference Graph Learning (IGL). Think of it as a super-smart traffic controller that learns the perfect schedule on the fly. Here is how it works, broken down into simple concepts:

1. The "Traffic Light" Map (The Interference Graph)

Imagine drawing a map where every robot is a dot. If two robots are close enough to cause a crash if they talk at the same time, you draw a red line connecting them.

• The Goal: Color the dots so that no two dots connected by a red line have the same color.
• The Meaning: Each color represents a "time slot." If two dots have the same color, they can talk together safely.
• The Challenge: In a factory with 1,000 robots, there are nearly 1,000,000 possible pairs to check. Drawing all those lines by hand (or with old math rules) is impossible and slow.

2. The "Evolutionary Coach" (Evolution Strategy)

Usually, to teach a computer to solve a puzzle, you tell it exactly which move was wrong (e.g., "You connected Robot A and B, but they shouldn't have been"). But in a network of 1,000 robots, you can't tell the computer which specific connection caused the problem. It's like trying to find a single bad apple in a truckload by tasting every apple individually.

Instead, the authors use an Evolution Strategy (ES).

• The Analogy: Imagine a coach training a team of athletes. Instead of telling the coach exactly which muscle to move, the coach tries a random new training routine.
  • If the team runs faster, the coach keeps that routine.
  • If the team runs slower, the coach throws it away.
• How it works here: The computer tries thousands of random "schedules." It looks at the overall result (Did the factory run smoothly? Did we use fewer time slots?). It doesn't care which specific robot caused the issue; it just knows if the whole system got better or worse. Over time, it evolves the perfect schedule without needing to know the tiny details of every single connection.

3. The "Magic Filter" (Deep Hashing)

Even with the Evolution Coach, checking 1,000,000 pairs of robots takes too long. The computer would get tired and slow down before it could react to a robot moving.

The authors added a Deep Hashing Function (DHF).

• The Analogy: Imagine a library with millions of books. You need to find books that are similar. Instead of reading every book to compare them, you put a "barcode" on each book based on its cover and title.
  • If two barcodes look very similar, you know the books are likely similar.
  • You only compare the books with similar barcodes. You ignore the rest.
• How it works here: The system quickly assigns a "hash code" to every robot based on where it is and how it's moving. It only checks the pairs of robots that have similar codes (meaning they are likely to interfere). It ignores the pairs that are far apart.
• The Result: This acts like a filter, reducing the work the computer has to do by 8 times. It makes the system fast enough to react in real-time.

The Results: Why It Matters

When they tested this in a simulation of a massive factory:

• Efficiency: They reduced the number of time slots needed by 25%. This means the robots can report their status much faster, keeping the factory running in "real-time."
• Reliability: They reduced lost messages (packet loss) by 30% in moving environments.
• Speed: The system could calculate the schedule 3 to 8 times faster than previous methods.

In a Nutshell

This paper teaches a computer how to manage a chaotic crowd of Wi-Fi devices. Instead of using rigid, pre-written rules, it uses a trial-and-error learning method (Evolution) to find the best schedule, and a smart filter (Hashing) to ignore the noise. The result is a Wi-Fi network that is faster, more reliable, and smart enough to handle thousands of devices without getting confused.

Technical Summary

Here is a detailed technical summary of the paper "Scalable Interference Graph Learning for Low-Latency Wi-Fi Networks using Hashing-based Evolution Strategy."

1. Problem Statement

The paper addresses the challenge of scheduling transmissions in Wi-Fi 7 networks, specifically for Industrial IoT (IIoT) applications requiring periodic, reliable, and low-latency communication.

• Context: Wi-Fi 7 introduces the Restricted Target Wake Time (RTWT) mechanism, which assigns specific time slots to stations (STAs) to eliminate contention and interference.
• Core Challenge: Determining the optimal RTWT slot assignment in dense networks is difficult.
  • Scalability: Traditional interference graph models rely on human intuition or fixed rules, lacking flexibility. Graph Neural Networks (GNNs) struggle to distinguish specific interfering pairs in large networks and often fail to minimize the total number of slots (chromatic number).
  • Credit Assignment: In large networks, it is computationally infeasible to determine which specific STA pair (edge) caused a performance drop. Gradient-based methods (like Policy Gradient) fail because they require explicit edge-wise feedback, which is unavailable; the reward is only available at the network level (e.g., total slots used or packet loss rate).
  • Complexity: The number of STA pairs grows quadratically ($O(K^2)$) with the number of stations ($K$), making training and inference for large-scale networks (e.g., 1,000+ STAs) computationally prohibitive.

2. Methodology

The authors propose a Scalable Interference Graph Learning (IGL) framework that combines a Neural Network (NN) with an Evolution Strategy (ES) and Deep Hashing (DHF).

A. Problem Formulation as Graph Coloring

The slot assignment problem is transformed into a graph coloring problem:

• Graph Construction: STAs are vertices; edges represent contention or interference. If an edge exists between STA $i$ and $j$, they must be assigned different colors (slots).
• Objective: Find an optimal binary graph structure (edge definitions) such that the graph's chromatic number (minimum slots, $Z$) is minimized while satisfying reliability constraints (packet loss < threshold).
• IGL Task: Train a Neural Network to learn the function $\mu(S_i, S_j)$ that maps STA states (path loss, location) to optimal edge values (0 or 1).

B. Evolution Strategy (ES) for Training

To solve the credit assignment problem (lack of edge-wise feedback), the paper replaces gradient-based backpropagation with an Evolution Strategy:

• Mechanism: Instead of calculating gradients for individual edges, the ES algorithm perturbs the parameters of the NN (specifically the Edge Generator) with Gaussian noise.
• Reward Signal: A single network-wide reward is calculated based on the resulting graph's performance (minimizing slots $Z$ while maintaining reliability $r_k \ge \hat{r}$).
• Update: The NN parameters are updated based on the correlation between the perturbation and the resulting reward. This avoids the need to estimate gradients for millions of edges individually.

C. Deep Hashing Function (DHF) for Scalability

To address the quadratic complexity ($O(K^2)$) of processing all STA pairs:

• Concept: The DHF uses a neural network to embed STA states into short binary hash codes.
• Locality Sensitivity: STAs that are likely to contend or interfere (geometrically close) are trained to have similar hash codes.
• Bucketing (Inference): During online operation, the system only generates edges for STA pairs that fall into the same "hash bucket" (i.e., have matching bits in their hash codes). This drastically reduces the number of pairs processed.
• Batching (Training): During training, the ES algorithm only evaluates a subset of STAs selected via the hashing mechanism, allowing for curriculum learning (starting with small batches and increasing size).

D. Network Architecture

The IGL Neural Network consists of three main components:

1. State Embedding (SENN): Uses LSTMs to encode variable-length sequences of AP path losses and locations into fixed-dimensional vectors.
2. Predictors (PCNN & PHNN): Predict whether a pair is "contending" or "hidden" based on embeddings (pre-trained via supervised/unsupervised learning).
3. Edge Generator (EGNN): Takes the embeddings and predicted indicators to output the final binary edge value. This is the only part trained via ES.

3. Key Contributions

1. First IGL Formulation for RTWT: The paper is the first to frame RTWT slot minimization as an interference graph learning task, preserving pairwise interference information unlike GNNs which aggregate features.
2. ES-Based Optimization: It introduces an Evolution Strategy to train the graph generator, solving the credit assignment problem in large networks where gradient-based methods (PG/DPG) fail due to the lack of edge-wise feedback.
3. Deep Hashing for Complexity Reduction: It integrates Deep Hashing to filter STA pairs, reducing the training and inference complexity from $O(K^2)$ to a manageable subset, enabling scalability to networks with 1,000+ STAs.
4. System-Level Validation: The framework is implemented and tested in NS-3 with standard-compliant Wi-Fi 7 RTWT mechanisms, providing realistic performance metrics.

4. Simulation Results

The authors evaluated the framework using NS-3 with 1,000 STAs and 100 APs in a factory setting.

• Slot Efficiency: The proposed IGL reduced the number of required time slots by 25% compared to human intuition-based graph models (IFG/CHG).
• Reliability: It reduced packet losses by up to 30% in dynamic (mobile) environments compared to non-selective processing schemes.
• Training & Inference Speed:
  • Training Time: Reduced by 4x compared to processing all pairs.
  • Inference Time: Reduced by 8x for graph construction and 3x for total online slot assignment time.
• Algorithm Comparison: The ES-based approach achieved 4–10x higher reward signals (better slot/reliability trade-off) compared to Policy Gradient (PG) and Deterministic Policy Gradient (DPG) baselines, which failed to converge effectively.
• Mobile Scenarios: In mobile scenarios, the DHF-bucketing approach (IGL-B) responded faster to network changes, resulting in significantly lower packet loss than non-selective methods.

5. Significance

This work provides a critical solution for the deployment of Wi-Fi 7 in dense IIoT environments.

• Scalability: It overcomes the "curse of dimensionality" in interference modeling, making it feasible to manage thousands of devices without prohibitive computational costs.
• Practicality: By eliminating the need for explicit edge-wise feedback, the method is applicable to real-world networks where measuring every interference pair is impossible.
• Performance: It demonstrates that learning-based, adaptive interference graphs outperform static, rule-based models, offering a path toward truly deterministic, low-latency wireless industrial control.

The paper concludes that while the current framework is centralized, it lays the groundwork for future distributed implementations and extensions to other resource allocation schemes like OFDMA and MU-MIMO.