Task-Oriented Network Ranging via Joint Graph and Schedule Design

Zijian Zhang, Yuan ShenarXiv 2026 · arXiv

TL;DR

The paper introduces Sparse Signal-Multiplexing Network Ranging (S-SM-NR), a framework that jointly optimizes which node distances to measure and when nodes transmit or listen. By measuring only the "task-essential" distances needed for localization rather than every possible pair, the authors significantly reduce ranging time and improve positioning accuracy in mobile environments.

What Problem Does This Paper Address?

Network localization—determining the positions of multiple nodes in a space—is fundamental for everything from warehouse robotics to cooperative drone swarms. Most systems rely on "ranging," where nodes exchange wireless signals to measure distances between one another.

The bottleneck is latency. Traditional protocols often attempt "complete ranging," measuring distances between every single pair of nodes. As the network grows, the number of required signal exchanges explodes quadratically. In mobile scenarios, this long ranging cycle is a killer: by the time the system finishes measuring all distances, the nodes have already moved, making the resulting position estimates inaccurate.

The authors ask: Can we design a ranging schedule that only measures what is necessary for localization, and can we do it concurrently to save time?

Methods

The authors propose the S-SM-NR framework, which moves away from fixed ranging protocols toward a "task-oriented" approach.

  1. Joint Graph and Schedule Design: Instead of treating "which links to measure" and "when to transmit" as separate problems, S-SM-NR optimizes them together. It defines a sparse task graph (a subset of all possible links) that is just dense enough to ensure the network is "globally rigid"—meaning its shape is uniquely determined by those distances.
  2. Connectivity Condition: The paper proves a critical theoretical link: for a network with a reference node to be localizable in 2D, the task graph must be 2-vertex-connected. This means the graph remains connected even if any single node is removed.
  3. Algorithm 1 (Closed-Form Design): The authors provide a practical algorithm that constructs a cycle-based task graph and a balanced transmit–listen schedule. It ensures that for every required distance, there are rounds where one node transmits while the other listens, and vice versa, all while respecting the "receiver capacity" (how many concurrent signals a node can handle).
The S-SM-NR framework overview, from localization requirements to position estimation.

Datasets

The paper uses numerical simulations rather than a static dataset to evaluate performance under dynamic conditions.

  • Setup: 20 to 160 nodes randomly distributed in a 300m × 300m area.
  • Parameters: Receiver capacity ($K_{max}$) varied from 1 to 16; node speeds up to 8 m/s.
  • Error Model: A Gaussian timestamp-error model with clock-frequency deviations (clock skew) to simulate real-world asynchronous hardware.

Key Insights and Ideas

  • Sparsity is Sufficient: You don't need a fully connected graph for localization. A sparse graph like a cycle (where each node only measures its immediate neighbors) can provide enough geometric constraints if designed correctly.
  • The Latency-Accuracy Link: In mobile networks, the "fresher" the data, the better the accuracy. By shortening the ranging cycle, S-SM-NR provides a more consistent "snapshot" of the network, which drastically reduces the Root-Mean-Square Error (RMSE) caused by node movement during measurement.
  • Signal Multiplexing: Even with half-duplex radios (which can't transmit and receive at the same time), clever scheduling allows multiple nodes to transmit concurrently without missing the signals they need to hear.
Illustration of how a joint design (b) can achieve localization in fewer rounds than a prescribed task graph (a) by selecting more efficient links.

Key Results

  • Drastic Round Reduction: In a 100-node network with a receiver capacity of 4, S-SM-NR required only 27 rounds per cycle. In contrast, standard sequential ranging (SM-NR) required 101 rounds, and a concurrent complete-ranging scheme (CC-SM-NR) required 52 rounds.
  • Superior Accuracy: At a node speed of 8 m/s, S-SM-NR achieved a position RMSE of 4.77m, while the baselines lagged behind at 8.83m and 18.79m.
  • Scalability: The number of rounds in S-SM-NR grows linearly with the number of nodes, making it much more suitable for large-scale deployments than traditional methods.

Limitations and Future Work

  • Physical Connectivity: The theoretical minimum round count assumes "complete physical connectivity" (every node can hear every other node). While the simulations tested sparser physical graphs, the theoretical bounds might need adjustment for highly obstructed environments.
  • Reference Node Dependency: The current scheme relies on a single reference node to initiate broadcasts and compensate for clock skews. Future work could explore multi-reference or fully distributed synchronization to improve robustness.
  • Dynamic Scheduling: The current design is "closed-form" and static. Adapting the schedule in real-time as nodes move in and out of range remains an open challenge.

Summary updated

Abstract

Measuring inter-node distances is the basis for network localization, whereas acquiring node positions does not require a fully connected graph of distances. Existing complete-ranging protocols for network localization require every node pair to exchange signals, which prolongs the ranging cycle. In this paper, we propose sparse signal-multiplexing network ranging (S-SM-NR), a task-oriented framework that adapts the transmit-listen schedule to the ranging task required by network localization. First, we establish the S-SM-NR framework by formulating the joint design of the task graph and the transmit-listen schedule. Then, we analyze the minimum round count required by S-SM-NR and establish a connectivity condition for network localization. Subsequently, we develop a closed-form joint design that constructs the sparse task graph and the balanced transmit-listen schedule. In particular, the joint design can achieve the minimum round count under the complete physical connectivity. Finally, simulations show that the proposed S-SM-NR scheme reduces the occupied-round count and improves the localization accuracy by shortening the ranging cycle.
BibTeX
@misc{zhang2026task,
  author = {Zijian Zhang and Yuan Shen},
  title = {{Task-Oriented Network Ranging via Joint Graph and Schedule Design}},
  year = {2026},
  eprint = {2611.24702},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.24702},
}
Figure