How Many Probing Rounds Does a Dense Wireless Network Need?

Before a wireless scheduler can decide which links should transmit together, it has to learn their channels. It does this by probing: each link sends a short known signal, called a pilot, and the receiver measures it. Probing costs airtime. It can be done in one big parallel batch, one link at a time, or in a few rounds where each round's choices depend on what earlier rounds revealed. Theory on "limited adaptivity" says a few rounds recover most of the value of fully sequential probing. That theory assumes, however, that probing many items at once costs nothing beyond waiting. Over a shared radio medium this assumption fails. Links probed at the same time reuse pilot resources, their pilots collide, and each measurement gets noisier as the network gets denser. This note proposes to measure, model and exploit this tension. Our hypothesis is that in interference-limited networks the best number of adaptive rounds is set by pilot interference, not by the combinatorics of the scheduling problem. That optimum should shift sharply, and possibly non-monotonically, with how densely the network is deployed.

The practical payoff is a rule for how a device-to-device or small-cell scheduler should split its probing budget across rounds as a function of node density. The scientific payoff is the first adaptivity-gap analysis in which the act of gathering information degrades the information gathered. By adaptivity gap we mean the ratio between the best policy that reacts to each observation and the best policy that commits to all its probes up front.

Core Claim

Three bodies of work frame the problem, and none of them covers it. The first sets the benchmark for the combinatorial side. Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions proves that when element states are independent and the feasible sets are downward-closed, a committed probe set loses at most a factor of 3 against the best adaptive policy for monotone submodular objectives. Stochastic Submodular Cover with Limited Adaptivity treats rounds as a resource and shows $r$ rounds give an $\tilde{O}(Q^{1/r})$ approximation for covering objectives.

The second body of work motivates the proposal by pricing probing on the physical layer. Queueing stability and CSI probing of a TDD wireless network with interference alignment charges a fixed airtime fraction $\theta$ per probed pair. It shows the resulting $L\theta$ overhead can make interference alignment worse than simple time-sharing. Its probing duration is fixed, though, and it never asks about sequential probing. User-Centric Association and Feedback Bit Allocation for FDD Cell-Free Massive MIMO shows that imperfect channel knowledge leaves residual interference that caps sum rate at high SNR.

The third body of work supplies the application regime. ITLinQ: A new approach for spectrum sharing schedules dense device-to-device links by activating sets in which treating interference as noise is near-optimal. It does this one-shot and assumes channel knowledge. Percolation and Connectivity on the Signal to Interference Ratio Graph shows that interference makes network behaviour non-monotone in density.

The observation that joins them is simple. If link scheduling is modelled with a conflict graph, the feasible sets are independent sets, which are downward-closed. Summed link rates are additive. So Gupta et al.'s factor-3 bound already applies in the idealized model where probes are free and exact. What breaks it in practice is that a probing batch of size $k$ run within one pilot slot produces measurements whose quality depends on $k$ and on density. Probing $k$ links on orthogonal pilots costs $k\theta$, the same airtime as $k$ sequential probes, and gains no adaptivity. The interesting regime is therefore spatial pilot reuse: concurrent probes share pilot resources at some reuse density $\rho$, pay $\theta$ per round, and suffer contamination.

For a Poisson field of concurrent pilots, the mean pilot interference grows linearly in $\rho$, so the estimation signal-to-interference ratio of a probed link behaves like

$$\mathrm{SIR}_{\text{est}}(\rho) \approx \frac{P g}{\sigma^2 + \rho\, P\, c_\alpha},$$

where $P$ is pilot power, $g$ the link's direct gain, $\sigma^2$ the noise power, and $c_\alpha$ the standard Poisson-field interference constant for path-loss exponent $\alpha$. The linear dependence on $\rho$ comes from Campbell's theorem for the mean of a Poisson shot-noise field.

An $r$-round policy with batches $B_1,\dots,B_r$ then trades two costs against each other. More rounds cost airtime $r\theta$ out of a unit frame. Bigger batches cost estimation quality, which turns into wrong activation decisions and leaked interference. Our central claim is that the achieved net rate $V(r,\lambda)$, at node density $\lambda$, has an interior maximizer $r^*(\lambda)$. We expect three regimes. In sparse networks $r^*=1$, because pilots rarely collide and one batch suffices. In moderately dense networks $r^*$ grows, because adaptivity lets later rounds skip links already ruled out by strong neighbours. In very dense networks $r^*$ falls back toward few rounds, because the network is so interference-limited that few links can be active and cheap statistical selection wins. This inverted-U prediction is falsifiable, and to our knowledge nothing in the literature makes it.

Research Program

The work has three parts.

The first is a simulator and problem definition. Links are dropped as a Poisson field of transmitter–receiver pairs, as in the ITLinQ evaluation, with Rayleigh fading. A frame has unit length. A probing round costs $\theta$, and within a round the policy chooses which links to probe and at what pilot reuse. Measurement noise follows the contaminated-estimation model above. As a robustness check, we will also use pilot-based estimation from the differentiable Sionna-based library PyJama, which models pilot-based channel estimation over realistic urban channels. After probing, the scheduler activates a set of links using ITLinQ's test on the estimated gains. The score is realized sum rate times the remaining fraction of the frame, $(1-r\theta)$.

The second part is a family of policies. At one end is the fully committed policy: one batch, everything probed at once. At the other is sequential greedy probing. In between are $r$-round policies that pick each batch from the posterior over unprobed links. We will implement the risk-free hybrid of Adaptive Greedy versus Non-Adaptive Greedy for Influence Maximization. That hybrid follows a fixed ordering but skips elements made useless by earlier observations. Here it means skipping links already blocked by a strong activated neighbour. That paper shows adaptive greedy can fall about 37% short of non-adaptive greedy through an "information trap". We will test whether local channel feedback in dense networks produces the analogous effect, where a scheduler commits early to a strong link that knocks out many neighbours.

The third part is theory for a stylized model. We keep the conflict-graph abstraction, independent Bernoulli-like link qualities, and a noisy-observation channel whose noise grows with batch reuse. We will try to extend the stem argument of Gupta et al. to show a bound of the form "gap ≤ 3 × (loss from contamination at reuse $\rho$)". From that bound we want a closed-form $r^*(\lambda)$ under the linear-interference approximation. We do not expect the idealized theory to cover the true SIR constraint, which is not downward-closed in a clean way. The theory's job is to predict the location of the optimum, which simulation then checks.

Baselines

The naive reference point is probe everything once. All links are probed in a single maximally-reused batch, then ITLinQ selects links on the noisy estimates. This is what a latency-minimizing designer would deploy, and it is the $r=1$ end of our family.

The strongest existing scheduling method is ITLinQ itself, run with genie channel knowledge and no probing cost, which gives an upper reference. It is also run with probing charged at $\theta$ per link on orthogonal pilots, which is the honest deployable version. ITLinQ is the right competitor because it is designed for exactly this dense device-to-device regime. It reports over 100% sum-rate gain over FlashLinQ with 4096 links at $\eta=0.7$, and a gap to capacity often below 1.2 bits (ITLinQ). We will reproduce that setting (4096 links, $\eta=0.7$) and first confirm we recover a gain of similar size over a FlashLinQ-style scheduler under genie knowledge before adding probing. Beating the deployable ITLinQ means higher net sum rate at matched $\theta$ and matched 5th-percentile link rate.

The third baseline is queue-aware Max-Weight scheduling with a fixed probing fraction, following Queueing stability and CSI probing. The file reports no numerical result for its stability-region shrinkage in this setting. Its role is to show whether adapting how many rounds beats adapting which scheme at a fixed overhead. It will be run on the same arrivals and fading traces.

The fourth baseline is a learned topology-aware scheduler of the kind in Link Scheduling using Graph Neural Networks. That paper reports approximation ratios above 0.98 for its centralized search and roughly a 50% reduction in the suboptimality gap of greedy for its distributed version. Those figures are for independent-set approximation with known weights, not probing. We give it the same estimated channel inputs and the same training compute as our policy tuning.

The key ablation holds everything fixed except pilot contamination. We turn it off by charging orthogonal pilots at $k\theta$ per batch, and we separately turn off adaptivity by forcing the batch composition to be chosen up front. If the inverted-U in $r^*$ survives with contamination off, our claimed mechanism is wrong.

All policies share the same drops, fading realizations, a tuning budget of equal grid size over their free parameters (reuse density, $\eta$, batch schedule), and are evaluated on held-out drops.

Why not just…?

Why not just use orthogonal pilots so probes never interfere? Then a batch of $k$ probes costs $k\theta$ of airtime, exactly what $k$ sequential probes cost. Batching buys nothing except fewer decision points, and the problem collapses to choosing when to stop probing. This is a real design option, and it is included as the ablation above. If orthogonal-pilot sequential stopping matches our reused multi-round policies across densities, the proposal's premise fails and we will report that.

Why not just skip probing and schedule on long-term statistics? Committing without observations is the zero-round policy. For stopping-type goals such as "find a usable link", Probing to Minimize shows committed policies can be arbitrarily worse than adaptive ones. For our maximization objective the loss is bounded but not small. It is also density-dependent through fading diversity: ITLinQ notes that Rayleigh fading can enlarge the feasible sets. We include a statistics-only ITLinQ run, and if it comes within a few percent of the best probed policy at high density, that confirms the "very dense" arm of our prediction rather than refuting it.

Why not just train a neural scheduler end to end on noisy channel inputs? It might learn good behaviour, but it would not say how many rounds to use or why. It also cannot be trained without first building the probing simulator we propose. We treat it as a baseline, and a strong learned scheduler that matches us would be a useful outcome. Its learned round usage could then be compared against the predicted $r^*(\lambda)$.

Proposed Experiments

The decisive experiment sweeps density $\lambda$ across the sparse, moderate and heavily interference-limited regimes, at several probe costs $\theta$. At each point we record net sum rate against the number of rounds $r$, and the empirical ratio between the best sequential policy and the one-batch policy. The core claim is supported if three things hold. First, $r^*(\lambda)$ is interior at moderate density. Second, it moves in the direction predicted by the linear-interference formula as $\theta$ and path-loss exponent vary. Third, the effect vanishes in the orthogonal-pilot ablation.

A second check looks for the information trap. We compare adaptive greedy, non-adaptive greedy and the skip-hybrid, and test whether adaptive greedy underperforms at high density while the hybrid never does.

A third check rebuilds the moderate-density point in PyJama with realistic pilot estimation, to confirm that the idealized contamination model does not create the optimum artificially.

Beyond these checks, the natural extension is an online version that learns contamination levels as it probes, building on the cost-aware sensing policies of Cost-Aware Learning and Optimization for Opportunistic Spectrum Access. That work is single-user and assumes independent channels; the multi-user version we propose removes both assumptions.