Sending Uncertain Futures in a Beacon: Decision-Aware Heatmaps for Predictive Routing

Drones and vehicles that relay data for each other must guess where their neighbors will be when a packet arrives, because by the time a position update crosses a few radio hops the node has already moved. Today's predictive routing protocols make that guess with a single future path, either a pre-planned polynomial flight path or a Kalman-filter estimate. Real motion often branches instead: at an intersection a vehicle turns left or right, and a drone can dodge an obstacle on either side. A neural motion forecaster can represent this branching as a heatmap, a grid of probabilities over future positions. That grid runs into two problems. It is too large to fit in a small radio beacon. And coarsening it to fit introduces quantization error, meaning positions get snapped to cell centers, which can flip the one question routing actually asks: will this neighbor still be within radio range at time $t$?

We propose to compress a node's predicted future-position heatmap into a beacon-sized message that preserves routing decisions rather than positions. The message is a sparse list of coarse cells. Each cell carries a probability weight and a sub-cell offset that points to the local center of mass. The sender spends its limited bytes on refining exactly the cells that straddle the radio-range circles of its current neighbors, because those are the only cells where coarse quantization can change a link-availability answer. Receivers integrate the message over range disks to get calibrated link probabilities and pick the next hop from those probabilities. The two sentences to tell a colleague are these: routing needs the probability that a link exists, not a point estimate of position. That probability is exactly computable from a coarse grid everywhere except in the cells cut by the range boundary, so those are the only cells worth paying bytes to refine.

Core Claim

Let $p_i(x,t)$ be node $i$'s predicted distribution over its position $x$ at future time $t$, let $y_j(t)$ be neighbor $j$'s predicted position, and let $R$ be the radio range. The quantity a forwarding rule needs is the link probability

$$P_{ij}(t) = \int_{\lVert x - y_j(t)\rVert \le R} p_i(x,t)\,dx .$$

Suppose $p_i$ is replaced by a grid in which each cell keeps its true mass. Every cell lying wholly inside or wholly outside the disk is still counted exactly. The error in $P_{ij}(t)$ is therefore bounded by the total mass in cells that the disk boundary crosses:

$$\lvert \hat P_{ij}(t) - P_{ij}(t) \rvert \le \sum_{c \,\cap\, \partial D_j(t) \neq \emptyset} m_c ,$$

where $m_c$ is the mass of cell $c$ and $\partial D_j(t)$ is the circle of radius $R$ around $y_j(t)$. This bound turns beacon design into a small allocation problem. The sender splits or offset-annotates the high-mass cells that straddle its neighbors' range circles, and it leaves everything else coarse. Our claim is that, at a fixed beacon size, this decision-aware encoding produces fewer wrong link decisions and higher packet delivery than two alternatives spending the same bytes: uniform-resolution grids, and mass-driven refinement. The gain should be largest where motion is genuinely multimodal. We also predict that it collapses to parity with simple parametric predictors when motion is smooth and pre-planned.

The per-cell offset also addresses a known failure of soft-argmax decoding. Integral Human Pose Regression computes a heatmap's expected coordinate to remove grid snapping. This raised high-precision [email protected] on MPII from 17.2% to 29.3%. Over a two-peaked distribution, however, the same expectation lands in the empty space between the peaks. We take the expectation only within each transmitted cell, or within each connected cluster of cells, in the spirit of the offset heads of Exploiting Offset-guided Network for Pose Estimation and Tracking (a 2.1 AP gain from the offset branch on COCO) and Towards Accurate Multi-person Pose Estimation in the Wild. This yields sub-cell precision per mode without averaging across modes.

Relation to Prior Work

Four predictive routing protocols motivate the problem, and all four assume a single future. Traj-Q-GPSR builds a two-hop neighbor table from pre-planned mission paths and learns forwarding with Q-learning. It names uncertain and asynchronous trajectories as its open limitation, and we address that directly. T-OLSR puts cubic-polynomial trajectory coefficients into HELLO and topology-control frames. MP-QGRD uses an Extended Kalman Filter, which assumes Gaussian noise around one nominal path, and adapts beacon intervals to predicted link lifetime. The earlier kinematic and mobility-model predictors of Zhu et al. and Sarafijanovic-Djukic et al. are also point predictors. We keep their message-passing structure but replace the single path with a compressed distribution. Their parametric predictors serve as baselines, not straw men.

Three works supply methods we reuse. THOMAS is the closest existing work. It decodes trajectory heatmaps coarse-to-fine, refining only the highest-probability cells, and reaches 0.5 m resolution while evaluating about 1.2% of grid points. It runs 128 agents in 31 ms. Its refinement criterion is probability mass, its output stays inside a perception stack, and it never meets a byte budget or a routing decision. Our refinement criterion is decision sensitivity: mass on range boundaries. We use a THOMAS-style decoder as the source of $p_i$. The integral and offset heads above supply the sub-cell decoding.

Two tokenized or binned approaches constrain the design. STARE tokenizes trajectories into S2 cells, and GeoCLIP argues that bin-based geolocation caps precision at bin centers. Both warn that fixed cells alone lose intra-cell motion, which is why every transmitted cell carries an offset.

Research Program

The system has three parts. The first is the predictor. We train a heatmap forecaster in the style of THOMAS to output $p_i(x,t)$ at a handful of horizons matched to multi-hop transit times, roughly 0.5 to 3 s. THOMAS was evaluated at 3.0 s, so longer horizons need their own validation.

The second is the encoder, which runs on the sender. It starts from a coarse grid and keeps the top cells by mass. It then greedily spends the remaining beacon bytes. Each step either splits a boundary-straddling cell or adds an offset to it, choosing the one that most reduces the summed bound above over current neighbors, with each neighbor weighted by how recently it was heard. The output is a fixed-format list of cell index, quantized weight, optional offset, and split flags, sized to budgets of 64, 128 and 256 bytes per horizon.

The third is the receiver. It computes $\hat P_{ij}(t)$ by exact disk-cell intersection over the received list. It chooses the next hop by maximizing expected geographic progress weighted by link probability over the packet's expected transit time. For the destination intercept point it keeps each mode separately rather than averaging them, and it forwards toward the mode with the highest weight × reachability. We deliberately keep forwarding as a transparent expected-utility rule instead of a new Q-learner. Any gain can then be attributed to the representation, and the same link probabilities can later be fed into Traj-Q-GPSR's state space.

The analysis question is when decision-aware refinement matters. We will measure how decision error scales with byte budget under three motion regimes: smooth mission flight, branching urban vehicle traffic, and aggressive maneuvering. We will also check whether the bound's ranking of cells predicts the empirical error.

Baselines

The naive reference is last-known-position GPSR, which forwards toward the most recent beacon coordinate. It is the point from which every protocol in the file measures its gains. T-OLSR reports GPSR at 67% packet delivery ratio (PDR) against about 98% for T-OLSR in an 8-node sparse MATLAB FANET, and Traj-Q-GPSR reports up to 23% lower packet loss than GPSR in ns-3. These numbers come from different simulators, so we re-run GPSR in ours rather than import them.

The strongest parametric competitors are point predictors. We will include linear kinematics, the cubic-polynomial beacon of T-OLSR, and the EKF predictor of MP-QGRD. MP-QGRD reports a 10% PDR gain and 30% latency reduction over QMR, QGeo and GPSR. We extend the EKF variant to send its covariance, so it computes a Gaussian link probability through the same receiver rule. That makes it a fair comparison of distribution shape rather than of forwarding logic.

The strongest learned competitor is a mixture of $K$ trajectory hypotheses. It uses the same forecaster as our method, takes its top $K$ modes, fits each with a polynomial, and sends a weight and variance per mode. No reported result found on Lacuna for mixture-of-trajectories beacons in FANET or VANET routing. We therefore build it ourselves and tune $K$ and variance precision on the same validation traces and under the same byte budgets.

The ablations isolate our key ingredient. The first is a uniform-resolution grid at the same byte count. The second is THOMAS-style mass-driven refinement at the same byte count, which separates "where to refine" from "whether to refine." The third is our encoder with offsets removed. The fourth is our encoder with global soft-argmax decoding instead of per-cell expectation, which tests the mode-collapse argument.

Every method gets the same predictor checkpoint where applicable, the same mobility traces, the same beacon interval and MAC settings, and an equal hyperparameter search budget. Beating the field means two things together. First, a statistically significant PDR gain, over at least 20 seeds, against the tuned $K$-mode mixture at 128 bytes or fewer on the branching-traffic regime. Second, no loss relative to the EKF on the smooth-mission regime.

Why not just…?

Why not just send a Kalman filter estimate or a polynomial, as T-OLSR and MP-QGRD do? These representations are compact and free of grid snapping, and on smooth pre-planned flights we expect them to match us. Our experiments include that regime specifically to show it. Their weakness is shape, not precision. A single Gaussian around a mean path assigns high link probability to the space between two branches, where the node will not be. The per-regime results will show whether this matters in practice, not merely in principle. If the covariance-EKF matches us on branching traffic too, the claim fails.

Why not just send the top-$K$ modes as a mixture of polynomials or Gaussians? This is the real threat. It is compact, continuous and multimodal, and with small $K$ it may win whenever each branch is itself tightly concentrated. Our method should win only when modes are broad or oddly shaped, so that their mass spreads across range boundaries in ways a Gaussian misplaces. Examples are wide intersection spreads or evasive maneuvers. The head-to-head at equal bytes across regimes settles this. We report the break-even point honestly. If the mixture wins everywhere, the correct conclusion is that decision-aware evaluation, not heatmaps, is the contribution, and we will say so.

Why not just raise grid resolution uniformly? With a fixed beacon budget, finer uniform cells mean fewer cells, and truncated tails then silently drop modes. The uniform-grid ablation at equal bytes measures this directly. Onboard compute is a secondary concern, since the AI-routing review A Review of AI-enabled Routing Protocols for UAV Networks flags compute cost on small drones, but the binding constraint here is the radio payload.

Why not just beacon more often? Predictive states are reported to cut control overhead by up to 90% (Xue et al.), and MP-QGRD's adaptive beaconing reduced energy by 15%. Faster beaconing still cannot foresee a turn that has not happened yet. We include a GPSR variant with 4× beacon rate and report its bytes-on-air alongside PDR.

Proposed Experiments

For branching vehicle motion we use the Interaction dataset (v1.2), treating recorded agents as radio nodes in a simulated VANET with range $R$ swept from 50 to 300 m. The predictor is trained THOMAS-style on the standard split. THOMAS reports 2.4% scene collision rate on validation, and our re-implementation should come close before routing results are trusted.

For aerial motion we use BonnMotion and ns-3 scenarios matching Traj-Q-GPSR, with two trace types: pre-planned missions, and missions with injected random replanning events. We also add trajectories from The Blackbird Dataset, where estimation drift rises from 0.55% to 1.94% as speed goes from 1.12 to 3.08 m/s. Blackbird is recorded in an 11 m arena, so we treat it as a source of maneuver shapes. We spatially rescale it and state that rescaling as a caveat.

Metrics are chosen for each level of the system. Link-probability calibration is measured with Brier score and reliability curves on "neighbor within $R$ at $t$." Wrong-link-decision rate covers both forwarding to a node that turns out to be out of range and discarding one that turns out to be reachable. Network outcomes are PDR, end-to-end delay, and control bytes per second. The empirical correlation between the bound and realized error tests the design principle itself.

There are three decisive checks. First, at 128 bytes on Interaction intersections, the full encoder must beat both mass-driven refinement and the tuned $K$-mode mixture on wrong-link-decision rate; otherwise decision-aware allocation is not buying anything. Second, removing offsets or switching to global soft-argmax must measurably worsen calibration on multimodal scenes, confirming the per-mode expectation argument. Third, on smooth mission traces the EKF and polynomial baselines should tie with us. If we instead win large there, it would suggest a simulation artifact, and we would investigate before claiming anything.