⚡ electrical engineering

SIG-SDP: Sparse Interference Graph-Aided Semidefinite Programming for Large-Scale Wireless Time-Sensitive Networking

This paper proposes SIG-SDP, a sparse interference graph-aided semidefinite programming framework that leverages signal sparsity and a matrix multiplicative weights algorithm to efficiently minimize time slots and packet loss in large-scale wireless time-sensitive networks with near-linear computational complexity.

Original authors: Zhouyou Gu, Jihong Park, Branka Vucetic, Jinho Choi

Published 2026-06-02

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zhouyou Gu, Jihong Park, Branka Vucetic, Jinho Choi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a busy factory floor filled with hundreds of robots (the "users") that need to send status updates to a central control room (the "base stations"). These updates are critical: if a robot doesn't report its temperature or location on time, the whole factory could crash, or a robot might crash into a wall.

To keep things safe, the robots must send their messages in a specific order. However, there's a problem: if two robots try to talk at the exact same time, their voices overlap, and the control room can't hear either of them clearly. This is called interference.

The goal of this paper is to answer a tricky question: How can we organize the robots so they all get their messages through quickly and reliably, using the fewest possible time slots?

If we give every robot its own private time slot, the line gets incredibly long, and messages get delayed. If we let too many robots share a slot, they drown each other out. Finding the perfect balance is a math puzzle so hard that even supercomputers struggle with it when there are thousands of robots.

The Problem with Old Methods

Previous ways of solving this were like trying to organize a massive concert by checking every single possible seating arrangement. It worked, but it took so long that by the time the organizers figured out the plan, the concert had already started, and the robots were already moving. The math was too slow for real-time use.

The New Solution: SIG-SDP

The authors propose a new system called SIG-SDP. Think of it as a smart, efficient traffic controller that uses two main tricks:

1. The "Distance Rule" (Sparse Interference Graphs)

In a huge factory, a robot in the far corner doesn't care about a robot in the opposite corner; their voices are too quiet to interfere. The old methods treated every robot as if it could interfere with every other robot, which is like assuming everyone in a stadium is shouting at everyone else.

The new system realizes that interference is sparse (mostly empty). It only pays attention to the robots that are actually close enough to hear each other. It draws a map (a graph) where lines only connect robots that are neighbors. By ignoring the distant, silent pairs, the math becomes much simpler and faster.

2. The "Smart Guessing Game" (Matrix Multiplicative Weights)

Once the system knows which robots are neighbors, it needs to figure out the schedule. Instead of brute-forcing the answer, it plays a game:

The Adversary: Tries to find the worst-case scenario where robots interfere the most.
The Solver: Tries to find a schedule that minimizes that interference.

They take turns adjusting the schedule. The solver learns from the adversary's attacks, getting smarter with every round. Because the system only focuses on the "active" neighbors (thanks to the Distance Rule), this game finishes incredibly fast.

How It Works in Real Life

The paper describes an "Online Architecture," which is like a live traffic update system:

Measure: The system constantly listens to the factory to see who is close to whom.
Calculate: While the robots are still working with the old schedule, the system runs its fast math in the background to design a new schedule.
Switch: As soon as the new schedule is ready, the robots switch to it.

The Results

The paper claims this new method is a game-changer:

Speed: It solves the scheduling problem up to 10 times faster than previous advanced math methods.
Reliability: It reduces "dropped messages" (packet loss) by up to 100 times compared to simpler, less smart methods.
Scalability: It works well even when the factory grows from 100 robots to 1,000, whereas older methods would crash or take forever.

The Catch

The paper admits one limitation: If the robots are moving extremely fast (like a race car track), the math might take just a little too long to catch up with the chaos. In those high-speed scenarios, a simpler, less perfect method might actually be better because it's instant. But for most industrial settings where robots move at a walking pace, this new system is the most reliable and efficient way to keep the factory running smoothly.

Technical Summary: SIG-SDP for Large-Scale Wireless Time-Sensitive Networking

Problem Statement
The paper addresses the challenge of minimizing the number of time slots required for transmissions in Wireless Time-Sensitive Networking (WTSN) for Industrial Internet of Things (IIoT) applications, while ensuring high reliability under interference constraints. In WTSN, users (e.g., sensors) must transmit status updates with strict latency and reliability requirements. Existing approaches often assign separate slots to each user to avoid interference, leading to excessive delays in large-scale networks. Conversely, allowing multiple users to share slots introduces interference, which can degrade Signal-to-Interference-plus-Noise Ratios (SINR) and cause decoding failures.

Formulating the optimal slot assignment as an integer programming problem to minimize the slot count ( $Z$ ) subject to SINR and association constraints is NP-hard. While Semidefinite Programming (SDP) relaxation offers a polynomial-time approach to approximate solutions, standard SDP solvers (e.g., Primal-Dual Interior Point or ADMM) suffer from high polynomial complexity relative to the number of users. This computational burden leads to delayed solutions, rendering them unsuitable for dynamic networks where interference conditions change rapidly.

Methodology: The SIG-SDP Framework
The authors propose the Sparse Interference Graph-Aided Semidefinite Programming (SIG-SDP) framework, which leverages the inherent sparsity of interference graphs to reduce computational complexity. The methodology consists of three core components:

Sparse Interference Graphs and Bounds:
The framework constructs two graphs based on network states: an association graph ( $G_{asso}$ ) indicating users connected to the same Base Station (BS), and an interference-power graph ( $G_{intp}$ ) representing measurable interference between users. Due to signal attenuation, these graphs are sparse (users only interfere with nearby neighbors). The authors derive theoretical upper and lower bounds for the minimum number of slots ( $Z^*$ ) using the chromatic numbers of these graphs and the maximum degree ( $\Omega$ ) of the interference graph. This allows the search for $Z^*$ to be confined within a narrow range rather than an unbounded space.
SDP Relaxation and Binary Search:
The integer slot assignment problem is relaxed into a Semidefinite Programming Constraint Satisfaction Problem (CSP). The binary decision of whether two users share a slot is represented by the inner product of vectors in a Positive Semidefinite (PSD) matrix $X$ . The framework employs a binary search algorithm within the derived bounds to find the minimum feasible $Z$ . For each candidate $Z$ , the system solves the SDP CSP to obtain a relaxed PSD matrix, which is then rounded to integer slot assignments using a randomized rounding technique based on random hyperplane cuts.
Sparsity-Accelerated Matrix Multiplicative Weights (MMW) Solver:
To solve the SDP CSP efficiently, the authors implement a Matrix Multiplicative Weights (MMW) algorithm. Unlike traditional solvers that process the entire matrix, the MMW approach exploits graph sparsity by only updating elements corresponding to interfering user pairs. The algorithm is formulated as a two-player zero-sum game:
- Adversary Player: Adjusts dual variables (constraint weights) using a "hedge rule" to maximize weighted constraint violations.
- Solution Player: Updates the primal PSD matrix using matrix exponentials to minimize these violations.
  The solver utilizes randomized sketching to approximate the matrix exponential, maintaining a low-rank structure that aligns with the problem's geometry. This reduces the per-iteration complexity from polynomial to near-linear with respect to the number of users.
Online Architecture:
An online architecture is designed to deploy the framework in dynamic networks. The solver runs in parallel with network transmissions, using real-time path gain measurements to update slot assignments. While the solver computes new assignments, the network continues operating with previous assignments, ensuring continuous service.

Key Contributions

First Sparse Interference Graph-Aided SDP: The paper introduces the first framework (SIG-SDP) that explicitly exploits interference graph sparsity to accelerate SDP for WTSN. It derives reduced search ranges for the minimum slot count based on graph chromatic numbers.
Novel SDP Relaxation: The authors design an SDP relaxation specifically for minimizing status update periodicity in WTSN, differing from existing methods that assume fixed periodicity.
MMW Solver Implementation: The work implements an MMW-based solver for interference management, providing an alternative to standard PDIP and ADMM solvers. The authors prove the convergence of the duality gap and demonstrate that the algorithm converges in approximately 100 iterations regardless of network size.
Scalability and Performance: The framework achieves near-linear computational complexity ( $O(K)$ ) with respect to the number of users ( $K$ ), making it highly scalable for large networks.

Simulation Results
Simulations conducted on networks with up to 675 users demonstrate the following:

Complexity: The SIG-SDP framework converges with near-linear complexity, scaling significantly better than existing polynomial-complexity SDP methods.
Computation Time: The framework is up to 10 times faster in computation than comparable SDP methods (like ADMM) that disregard sparsity.
Reliability: The proposed method reduces packet loss rates by up to 100 times compared to linear relaxation methods and 10 times compared to heuristic approaches (e.g., greedy max-weight scheduling).
Dynamic Performance: In dynamic networks with mobile users, the framework outperforms low-complexity heuristics for slow-moving users. However, as user speed and interference variability increase, the performance gap narrows due to the latency introduced by the solver's computation time, highlighting the trade-off between optimization quality and responsiveness.

Significance and Claims
The paper claims that SIG-SDP offers a scalable solution for interference management in large-scale WTSN, addressing the critical bottleneck of high computational complexity in existing SDP approaches. By exploiting the physical reality of signal attenuation (sparsity), the framework enables the minimization of time slots while maintaining stringent reliability constraints. The authors note that while the framework significantly outperforms heuristics in static or slow-moving scenarios, its effectiveness in highly dynamic environments is limited by computation time. They suggest that future work could integrate deep learning or spectral graph methods to achieve "one-shot" mappings, further reducing latency, and explore adaptive power control to mitigate unmeasurable interference.