PaperlayerView exact revision on arXiv

Source-linked AI summary

Structuring and Merging Deletion Demands on Crowdsourced Channel Knowledge Maps

Zihao Ding, Jun Huang

arXiv:2610.22589v1cs.NI

TL;DR

Faults can corrupt measurements in a channel knowledge map, but removing whole terminals discards their good measurements and raw reports needed for sample-level deletion are gone. SWEEP groups structured deletion demands into campaigns that clear an aggregated ledger and re-sound affected grids, bounding the extra good measurements cleared. In simulation and on a USRP testbed, it clears at most 5.1% of good measurements, compared with up to 86.8% for terminal removal or rollback.

  • Problem

    Faulty measurements must be forgotten from a channel knowledge map, but removing whole terminals loses their good measurements and raw reports for sample-level deletion are unavailable.

    Source: §I · p. 1

  • Method

    SWEEP executes structured deletion units by clearing an aggregated ledger and re-sounding affected grids, grouping pending demands into campaigns under an over-deletion bound.

    Source: §I · p. 1

  • Results

    At most 5.1% of good measurements are cleared by SWEEP in simulation and on the USRP testbed, versus up to 86.8% for terminal removal or rollback.

    Source: §I · p. 2, B. Experimental Results · p. 6

  • Takeaways & Limitations

    The approach bounds over-deletion when demands are merged into shared campaigns.

    Source: §I · p. 1

Abstract

from arXiv · show

A base station can build a channel knowledge map (CKM) from the uplink pilots of its terminals and sweep only the beams that the map ranks highest. A fault at a terminal or at the base station corrupts the measurements taken while it lasts, and the map must then forget them. Removing the whole terminal discards its good measurements, and the raw reports needed to remove samples are gone. We define the structured deletion unit (SDU), which names the terminals, rounds, grids, and bands to forget. We propose \underline{S}tructured \underline{W}iping with \underline{E}nvelope-bounded \underline{E}xecution \underline{P}artitioning (\method{}), which executes an SDU by clearing blocks of an aggregated ledger and re-sounding the affected grids. \method{} merges pending demands so that one campaign serves several, and it bounds what the smallest SDU containing a group clears beyond the demands. We prove that a merged execution leaves no named measurement in the map, that demands differing only in their intervals are best merged in contiguous runs, and that the greedy merge is within a factor $1+\ln Q$ of the best grouping over its candidates. In simulation and on a USRP testbed, \method{} clears at most 5.1\% of the good measurements, against up to 86.8\% when whole terminals are removed or the map is rolled back to an earlier block.

I. INTRODUCTION

Faults can corrupt terminal measurements in a channel knowledge map, while whole-terminal removal discards good data and raw reports are unavailable for sample-level deletion. SWEEP groups structured deletion demands into bounded-overreach campaigns; simulations and a USRP testbed show substantially less good-measurement loss than terminal removal or rollback.

I. INTRODUCTION

  • A structured deletion unit names the terminals, rounds, grids, and bands to forget when faulty measurements are discovered after the fact.Removing a whole terminal discards its good measurements, while the raw reports needed for sample-level deletion are unavailable.Source: §I · p. 1
  • Merged demands can cover unnamed measurements because their smallest containing SDU may include gaps or combinations beyond either demand.Repeated campaigns also cost airtime, and prior approaches do not bound how far merged deletion may overreach.Source: §I · p. 1
  • SWEEP executes each structured deletion unit by clearing an aggregated ledger and re-sounding affected grids, then groups demands into envelope-bounded campaigns.It uses dynamic programming for demands differing only in intervals, greedy grouping otherwise, and flushes the queue when liability reaches a threshold.Source: §I · p. 1
  • SWEEP formulates demand merging as a covering problem that minimizes pilot-slot campaign cost subject to a per-group over-deletion bound.The paper proves named measurements are removed, contiguous groups are optimal for interval-only differences, and greedy merging is within 1 + ln Q of the best candidate grouping.Source: §I · pp. 1–2
  • At most 5.1% of good measurements are cleared by SWEEP in simulation and on the USRP testbed, versus up to 86.8% for terminal removal or rollback.The introduction also reports simulation-specific clearing of at most 2.6%.Source: §I · p. 2

II. SYSTEM MODEL AND PROBLEM FORMULATION

The system model describes a base station serving terminals across bands and grids, measuring per-beam uplink gains and maintaining a block-based ledger. Its map narrows beam selection to highly ranked beams in valid grid-band pairs, trading fewer pilot slots for some SNR loss.

A. System Model

  • The base station serves K terminals over bands F using an M-antenna uniform linear array, B receive beams, and a service area partitioned into grids X.Source: A. System Model · p. 2
  • Each round, terminals report their grid and send an uplink pilot on every band.Source: A. System Model · p. 2
  • For each band, the base station measures a B-entry gain vector for each terminal.Source: A. System Model · p. 2
  • The measured gains use the channel scaled by declared transmit power; calibrated terminals have actual-to-declared power ratio one, and calibrated base-station receive chains have identity residual-phase matrices.Source: A. System Model · p. 2
  • The base station retains per-grid, per-band, per-block sums and counts in its ledger, while terminals keep their own reports and diagnostics locally.Source: A. System Model · p. 2
  • A grid-band pair is valid once its accumulated count reaches nmin; otherwise, the base station sweeps all B beams.Source: A. System Model · p. 2
  • For a valid pair, beam selection sweeps the L beams with the largest map entries, where L is much smaller than B.Source: A. System Model · p. 2
  • Using the map saves B − L pilot slots per selection at the cost of SNR loss, while λ_x,f denotes the beam-selection traffic requested per round.Source: A. System Model · p. 2

B. Problem Formulation

A structured deletion unit (SDU) names which terminals, rounds, grids, and bands the base station must forget. Because the ledger cannot separate terminals within a block, execution clears whole blocks, re-sounds affected grid–band pairs, and may over-delete beyond the demands.

B. Problem Formulation

  • An SDU specifies terminals, a round interval, grids, and bands; power, positioning, and receive-chain faults produce different combinations of these fields.Power faults name one terminal across all grids and bands; positioning faults name one terminal and selected grids; receive-chain faults name all terminals on one band.Source: B. Problem Formulation · p. 2
  • Because the ledger cannot separate terminals within a block, the base station clears every block holding a named measurement and re-sounds affected grid–band pairs.Terminals in those pairs sweep all beams until nmin new measurements are collected, after which the base station broadcasts the new map.Source: B. Problem Formulation · p. 2
  • A group's envelope is the smallest SDU containing its members, but it can also clear unnamed blocks, such as blocks between demand intervals.The base station covers all demands with groups whose over-deletion stays within η; groups may share a demand because cleared blocks remain cleared.Source: B. Problem Formulation · pp. 2–3, Figure 2 · p. 3

III. SWEEP: STRUCTURED WIPING WITH ENVELOPE-BOUNDED EXECUTION PARTITIONING

The direct covering problem is difficult because the ledger lacks the locations needed to price groups, the queue has 2^Q possible subsets, and queued measurements remain in use. SWEEP addresses these constraints through three modules.

III. SWEEP: Structured Wiping with Envelope-Bounded Execution Partitioning

  • The base station cannot price a group from the ledger alone because the needed terminal reporting locations are not recorded.The covering problem ranges over 2^Q queue subsets while measurements named by queued demands remain in the map.Source: §III · p. 3
  • SWEEP is designed to address the pricing, search-space, and still-in-use measurement challenges of the covering problem.The paper organizes its three modules in Sections III-A, III-B, and III-C.Source: §III · p. 3
  • Figure 4 shows when each of SWEEP's three modules runs.Source: §III · p. 3

A. Block Ledger and Footprints

The block ledger aggregates reports by grid, band, and block without retaining per-terminal records. At a queue flush, temporary terminal footprints support deletion, after which clearing and re-sounding restore the map from the remaining ledger entries.

A. Block Ledger and Footprints

  • The base station stores each block's gain-vector sums and report counts by grid and band, using |X||F|(B + 1) numbers per block regardless of the number of terminals.Block length W sets deletion time resolution: smaller W reduces whole-block clearing for misaligned intervals but requires more storage.Source: A. Block Ledger and Footprints · p. 3
  • When the queue is flushed, named terminals provide temporary footprints of their reported blocks, which the base station combines with ledger counts to evaluate candidate SDUs.Footprints are deleted after the flush, and terminals never named in a demand send nothing, so the base station holds no trace of them.Source: A. Block Ledger and Footprints · p. 3
  • After clearing an SDU's blocks, the base station invalidates affected pairs below nmin and re-sounds them; new reports fall outside the named intervals.Removing each ledger entry's sum and count together leaves exactly the map that a ledger without those blocks would produce.Source: A. Block Ledger and Footprints · p. 3

B. Envelope-Bounded Merge

SWEEP builds candidate groups from pairs of demands and greedily covers the queue, while using an exact dynamic program when demands share terminals, grids, and bands. Its merge choices balance shared campaign cost against envelope over-deletion.

B. Envelope-Bounded Merge

  • SWEEP forms candidate groups from demand pairs by including demands inside their envelope and dropping candidates that violate (C1).The resulting candidate set covers the queue; groups whose envelopes require three demands to span may fail the over-deletion bound when η is small.Source: B. Envelope-Bounded Merge · p. 3
  • A transmitter fault within a receiver fault's band and interval joins its envelope at no cost, whereas spanning the receiver fault across another band is worthwhile only when that band holds few measurements.Source: B. Envelope-Bounded Merge · p. 3
  • When demands share terminals, grids, and bands, SWEEP sorts them by start round and solves the interval grouping problem exactly by dynamic programming.The dynamic program's optimality is established by Proposition 2.Source: B. Envelope-Bounded Merge · pp. 3–4
  • Otherwise, SWEEP greedily selects the candidate with the least cost per uncovered demand until all demands are covered.It executes demands one by one with repeated fixed overhead, while merging all demands can clear long interval gaps; SWEEP merges only groups whose envelopes stay within η.Source: B. Envelope-Bounded Merge · p. 4
  • Both procedures use ledger counts and footprints and evaluate at most Q^2 candidates or runs.Source: B. Envelope-Bounded Merge · p. 4

C. Liability-Triggered Flush

SWEEP flushes the pending queue when its total liability reaches a threshold, then merges and executes campaigns. The threshold trades more frequent, smaller merges against longer use of named measurements while they wait.

C. Liability-Triggered Flush

  • A flush collects footprints, runs the merge, executes the selected campaigns, and empties the queue once total liability reaches threshold θ.Each pending demand accrues liability at a rate equal to traffic served by its grid–band pairs.Source: C. Liability-Triggered Flush · p. 4
  • A small θ flushes often and merges little, while a large θ merges more but lets named measurements serve longer.A receiver fault names every pair on its band and therefore triggers a flush almost at once.Source: C. Liability-Triggered Flush · p. 4
  • Under the stated Poisson-arrival, independent-liability, and queue-independent flush-cost assumptions, a liability threshold minimizes long-run average flush cost plus liability.Demands arriving during a flush wait for the next one, and SWEEP transmits only footprints and selected-group campaigns; its merge is polynomial in Q.Source: C. Liability-Triggered Flush · p. 4

IV. THEORETICAL ANALYSIS

The analysis establishes that merged campaigns remove every named measurement, and gives optimality and approximation guarantees for grouping and flushing. These guarantees are conditional where the demand intervals have a specified structure or the flush-cost assumptions apply.

IV. THEORETICAL ANALYSIS

  • A merged campaign clears every block holding a member demand’s named measurement, leaving the map equal to one whose ledger never received those cleared blocks.The ledger updates depend on its entries’ sums and counts, both of which clearing removes.Source: §IV · p. 4
  • When demands share terminals, grids, and bands and have non-nested intervals aligned to block boundaries, an optimal grouping uses consecutive-start-round runs, found with O(Q^2) evaluations.The proof replaces groups with feasible runs and partitions them without increasing cost or over-deletion.Source: §IV · p. 4
  • The greedy cover costs at most (1 + ln Q) times the best cover over candidate groups, and is optimal for the full problem under Proposition 2’s conditions.The candidate construction contains the optimal runs in that special case.Source: §IV · p. 4
  • With Poisson arrivals, identically distributed independent liability rates, and flush costs independent of timing, an optimal queue-based rule flushes when total liability reaches a threshold.The threshold rule follows because waiting cost grows with total liability while flushing has a state-independent cost.Source: §IV · p. 4

V. PERFORMANCE EVALUATION

The evaluation uses both a simulated urban channel and a USRP lab testbed to assess map quality, deletion, and execution cost. It varies demand, ledger, and grid conditions in the reported figures.

A. Experimental Setup

  • The simulation models a 100 × 100 m urban area divided into 20 × 20 grids, with ray-traced channels and 50 walking terminals reporting for 400 rounds.It uses two bands, 16 BS antennas, 32 beams, four map candidates, and W = 5.Source: A. Experimental Setup · pp. 4–5
  • The evaluation figures vary η, demand arrival rate, block length W, fault overlap, queue size Q, and grid count while tracking pilot, deletion, ledger, or SNR measures.The scalability figure compares merge time and gap to exhaustive search as Q grows, and pilot slots and SNR loss as grids grow.Source: Figure 6 · p. 5, Figure 7 · p. 6
  • The USRP testbed uses a four-port USRP-2955 BS and three carried USRP-2900 terminals on fixed routes across 12 one-meter grids in a 55 m2 lab.Faults are injected as gain, wrong-grid, and receive-channel phase errors.Source: A. Experimental Setup · p. 5
  • Evaluation measures traffic-weighted SNR loss and hit rate, alongside deletion, waiting, and execution-cost measures including pilot slots and liability.The compared baselines include SISA, ERASER, FedRecover, Crab, ST-REM, and Retrain.Source: A. Experimental Setup · pp. 5–6

B. Experimental Results

SWEEP clears substantially fewer good measurements than terminal removal or rollback in the reported evaluation, while its pilot-slot and over-deletion outcomes vary with merging and system conditions.

B. Experimental Results

  • At most 2.6% of good measurements in simulation and 5.1% on the testbed are cleared by SWEEP, versus up to 86.8% for FedRecover and Crab.SWEEP clears the fewest good measurements in every fault group.Source: B. Experimental Results · p. 6
  • Under mixed faults, SWEEP uses the fewest pilot slots and has liability 3, compared with 4889 for ERASER.Its SNR loss is closest to Retrain under receiver and mixed faults; SISA uses fewer pilot slots under receiver faults but clears 13.0%.Source: B. Experimental Results · p. 6
  • Raising η to 20% saves up to 13.6% of pilot slots for less than 0.8 points of over-deletion, while SWEEP uses 20.6% to 32.1% fewer pilot slots than SISA at every arrival rate.Each doubling of W halves ledger size and raises over-deletion; the greedy merge stays within 8.6% of exhaustive search.Source: B. Experimental Results · p. 6

VI. CONCLUSION

The conclusion reports that SDUs remove transmitter and receiver faults without discarding whole terminals or rolling back the map. SWEEP keeps over-deletion bounded and clears at most 5.1% of good measurements, compared with up to 86.8% for the alternatives.

VI. CONCLUSION

  • The study addresses forgetting faulty measurements in a crowdsourced channel knowledge map.Source: §VI · p. 6
  • 5.1% of good measurements at most are cleared by SWEEP, versus up to 86.8% for removing whole terminals or rolling back the map.The comparison is reported for simulation and a USRP testbed.Source: §VI · p. 6
  • SWEEP merges transmitter- and receiver-fault demands into re-sounding campaigns while keeping over-deletion within a bound.Source: §VI · p. 6
Loading 2610.22589v1…