PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient User Association and Wireless Scheduling with Shorter Time-Scale Rate Adaptation

Xiaoyi Wu, Huacheng Zeng, Bin Li

arXiv:2609.09387v1cs.NI

TL;DR

Wireless user association and scheduling must be coordinated with faster rate adaptation while pursuing throughput and fairness. The paper combines virtual-queue and UCB weights in a MaxWeight-type algorithm, and establishes regret and fairness guarantees alongside a lower-complexity pick-and-compare alternative.

  • Problem

    Joint user association and scheduling with rate adaptation across different time scales remains underexplored, despite the need to maximize throughput while meeting user fairness requirements.

    Source: §I · p. 1

  • Method

    A MaxWeight-type algorithm combines virtual queues and UCB estimates for association and scheduling, while selected users use UCB to choose rates on a shorter time scale.

    Source: §I · p. 2

  • Results

    The algorithm achieves O(√K log K) regret over K frames and zero cumulative fairness violation after a certain number of frames.

    Source: §I · p. 2

  • Takeaways & Limitations

    A pick-and-compare alternative reduces the computational complexity of the MaxWeight-type algorithm, and simulations use real-world data.

    Source: §I · p. 2, §VII · p. 10

Abstract

from arXiv · show

Rate adaptation is a crucial mechanism in IEEE 802.11 networks and next-generation cellular systems. Since the time scale for rate adaptation is typically much shorter than that for user association and scheduling, we investigate a joint design of wireless user association and scheduling and rate adaptation across different time scales to maximize cumulative network throughput while ensuring desired fairness among users. We develop a MaxWeight-type user association and scheduling algorithm that integrates virtual queues -- tracking each user's scheduling debt to maintain fairness -- and Upper Confidence Bound (UCB) estimates in its weight measure. Each selected user then employs the UCB algorithm for rate adaptation on a short time scale. Our theoretical findings reveal that the proposed algorithm achieves cumulative regret that grows with the square root of the time horizon up to a logarithmic factor and results in zero cumulative fairness violation after a certain number of time frames. Furthermore, since the MaxWeight-type algorithm involves evaluating all the feasible schedules that can be exponential to the number of users due to the interference constraints, leading to high computational complexity, we introduce a low-complexity alternative utilizing the so-called pick-and-compare (PC) approach. We demonstrate the effectiveness of both algorithms through simulations based on real-world data traces.

I. INTRODUCTION

The paper jointly addresses user association, scheduling, and rate adaptation across different time scales to maximize throughput while meeting user fairness requirements. It combines MaxWeight scheduling with virtual queues and UCB estimates, and situates this design against prior single-link rate adaptation and fairness-constrained scheduling work.

I. INTRODUCTION

  • Association and scheduling operate more slowly than rate adaptation, so the design must coordinate user–AP assignments, scheduling, and rate choices while pursuing throughput and fairness.More frequent reassignment can improve responsiveness to channel conditions but incurs handover costs.Source: §I · p. 1
  • MaxWeight combines virtual queues tracking fairness with UCB estimates for association and scheduling, while selected users use UCB to choose transmission rates.The paper presents simulations using realistic wireless data and identifies the pick-and-compare algorithm as a lower-complexity alternative.Source: §I · p. 2
  • The proposed algorithm achieves O(√K log K) cumulative regret over K frames and zero cumulative fairness violation after a certain number of frames.A pick-and-compare alternative reduces the computational complexity of the MaxWeight-type algorithm.Source: §I · p. 2

A. Rate Adaptation and MAB

  • Rate adaptation has been modeled as a bandit with transmission rates as arms; later work explored contextual learning and cross-rate reward correlations, yet these algorithms remain unintegrated with slower-timescale wireless user scheduling.Source: A. Rate Adaptation and MAB · p. 2

B. Wireless Scheduling with Constraints

  • Wireless scheduling research studies throughput and fairness, but prior fairness-constrained bandit methods do not directly fit this setting’s distinct scheduling and rate-adaptation time scales.The paper distinguishes fairness in scheduling fractions, tracked through virtual queues, from max-min rate fairness; its setting also has unknown statistics and exploration costs.Source: B. Wireless Scheduling with Constraints · pp. 2–3

III. SYSTEM MODEL

The system fixes user–AP assignments for each frame while users adapt transmission rates slot by slot. It seeks maximum cumulative expected throughput subject to per-user scheduling-fraction requirements, with frame length trading adaptability against handover overhead.

III. SYSTEM MODEL

  • Frame length T trades more frequent reassessment of user–AP pairings against increased handovers and their overhead.Assignments stay fixed within each frame and are updated at frame boundaries.Source: §III · p. 3
  • Feasible schedules select simultaneously served user–AP pairs subject to interference and access constraints.Each user associates with at most one AP, and each AP has a limit on users served per frame.Source: §III · p. 3
  • Each selected user chooses among M transmission rates in every slot, with success outcomes modeled as i.i.d. and having unknown means.The success probability represents acknowledged reception and implicitly captures fading, coding, and inter-AP interference; users served simultaneously by the same AP are assumed interference-free.Source: §III · pp. 3–4
  • The objective is to maximize cumulative expected throughput while scheduling each user for at least its required fraction λn of time on average.With known throughput statistics, a randomized stationary schedule provides the stated optimization benchmark.Source: §III · p. 4
  • Cumulative regret measures the throughput gap between the known-statistics optimal policy and the algorithm, so minimizing it maximizes the algorithm’s expected accumulated throughput.The comparison is over consecutive K frames.Source: §III · pp. 4–5

IV. ALGORITHM DESIGN AND PERFORMANCE ANALYSIS

OUTTA combines virtual queues for scheduling fairness with UCB rate estimates across frame and slot time scales. Its analysis bounds cumulative fairness violation and regret, with zero cumulative fairness violation after a threshold number of frames under the stated condition.

IV. ALGORITHM DESIGN AND PERFORMANCE ANALYSIS

  • OUTTA uses virtual queues at the scheduling time scale for fairness and UCB at the slot time scale to learn each user’s best rate.The rate-learning component addresses the exploration–exploitation tradeoff while seeking minimum cumulative regret.Source: §IV · p. 5
  • A user’s virtual queue grows when unscheduled and shrinks when scheduled, signaling how urgently that user should be served in later frames.The queue tracks the user’s scheduling debt relative to its fairness requirement.Source: §IV · p. 5
  • The UCB estimate uses the number of transmissions at each AP–user–rate combination, encouraging exploration when that rate has few observations.An untried rate receives the highest priority; the estimate is truncated because success probabilities are at most 1.Source: §IV · p. 5
  • OUTTA initially emphasizes virtual queues to secure fairness, then increases emphasis on UCB weights to reduce regret.Its increasing ηk balances queue lengths and UCB estimates; choosing ηk requires the slackness constant, which may be unavailable in practice.Source: §IV · p. 5
  • The fairness bound applies when εk ≤ δ/2 eventually, while the regret proposition requires εk ≤ δ.The fairness analysis uses virtual-queue drift and bounds the expected queue length before deriving cumulative violation.Source: §IV · p. 6
  • OUTTA achieves zero cumulative fairness violation for K ≥ g2(N, δ, rM), and the required number of frames is independent of frame size T.The condition in the proposition holds once εk ≤ δ/2 for all sufficiently large k; the amount of cumulative violation grows linearly with T.Source: §IV · p. 6

K + LMNT log(KT)

The regret bound makes OUTTA’s approximation ratio approach one as the horizon grows, though the realized ratio depends on instance-specific throughput statistics. The discussion also addresses time-scale analysis, frame size, and applicability across MAC/PHY layers.

K + LMNT log(KT)

  • The drift-plus-penalty analysis decouples user decisions from rate adaptation to handle their different time scales in the regret bound.Source: K + LMNT log(KT) · p. 6
  • The regret upper bound increases with frame size T, although trace simulations show only marginal impact because users have sufficient time to identify their best transmission rates.Source: K + LMNT log(KT) · p. 6
  • The guarantees apply across diverse MAC/PHY layers because the technology enters the analysis only through feasible set S and success probabilities.Source: K + LMNT log(KT) · p. 6
  • Reg(KT)=O(√K log K) while OPT(KT)=Θ(K), so OUTTA’s approximation ratio approaches 1 as K grows, matching the order of the classical UCB bound.The ratio’s gap from 1 is Reg(KT)/OPT(KT).Source: K + LMNT log(KT) · p. 6
  • The ratio is horizon-dependent because its gap comes from learning unknown success probabilities with UCB estimates, rather than fixed decision-rule suboptimality.The UCB exploration bonus decays as observations accumulate, yielding an O(√K log K) accumulated shortfall rather than a linear one.Source: K + LMNT log(KT) · p. 6
  • The regret rate is instance-independent, but its numerical value depends on unknown throughput statistics through OPT(KT), and its explicit constants are worst-case.The paper reports the guarantee as a rate and gives the realized ratio on real-world traces.Source: K + LMNT log(KT) · p. 6

V. LOW-COMPLEXITY ALGORITHM DESIGN

OUTTA’s MaxWeight design can require evaluating an exponentially large set of feasible schedules under interference constraints. PC-OUTTA reduces this search by comparing one randomly selected feasible schedule with the previous frame’s schedule.

V. LOW-COMPLEXITY ALGORITHM DESIGN

  • Interference constraints can make the feasible schedule set exponential in the number of users, making OUTTA’s exhaustive weight maximization computationally costly.Source: §V · p. 7
  • PC-OUTTA randomly selects one feasible schedule per frame and compares its weight with the previous frame’s schedule, reducing comparison steps from |S| to one.The remaining PC-OUTTA design is similar to OUTTA.Source: §V · p. 7
  • The frame-based association and scheduling design decreases switching overhead from frequent user handoffs between APs.Source: §V · p. 7

VI. SIMULATIONS

Trace-driven simulations evaluate OUTTA and PC-OUTTA using measurements from a 60 GHz mmWave testbed. Both reach an empirical approximation ratio of about 0.74 within the simulated horizon, while PC-OUTTA trades slower fairness recovery for lower computational cost.

VI. SIMULATIONS

  • In the 60 GHz testbed, researchers sequentially measured 30 AP–user links; simulations used 10 users, three APs, and nine selectable rates.Slackness δ was varied over 0.05, 0.1, and 0.15.Source: §VI · pp. 7–8

1) OUTTA:

  • OUTTA exceeds each user's desired scheduling fraction across frame sizes and achieves zero cumulative fairness violation; larger frames delay that point and increase violation, while regret is sublinear and nearly frame-size-insensitive.Its empirical approximation ratio reaches about 0.74 within the simulated horizon and rises with horizon.Source: 1) OUTTA · p. 8, Figure 6 · p. 9, Figure 7 · p. 9

2) PC-OUTTA:

  • ρ ≈0.74 within the simulated horizon for both PC-OUTTA and OUTTA, with PC-OUTTA at substantially lower computational cost but slower to reach zero fairness violation.The approximation ratio increases toward 1 with horizon; PC-OUTTA has larger cumulative regret and is more sensitive to frame size.Source: 2) PC-OUTTA · pp. 8, 10, Figure 10 · p. 10

VII. CONCLUSION

  • The paper concludes that OUTTA achieves O(√K log K) cumulative regret and eventually zero cumulative fairness violation, while PC-OUTTA offers a lower-complexity alternative.Both algorithms were evaluated in simulations based on real-world data traces.Source: §VII · p. 10

APPENDIX A PROOF OF PROPOSITION 1

The proof uses virtual-queue drift to establish a negative-drift condition above a threshold, then bounds the time index at which the stated slackness condition holds.

APPENDIX A PROOF OF PROPOSITION 1

  • For any 0 < ϵk ≤ δ/2, if V(kT) ≥ Wk, Lemma 1 states that the absolute drift of V(kT) is bounded by 3N.Wk ≜ (6N + Nδ2 + 4ηkNLTrM)/δ.Source: Appendix A · p. 10
  • The proof uses that schedules stay fixed within a frame and virtual queue lengths update only at frame beginnings.Source: Appendix A · p. 11
  • The index k′ is the minimum integer with ϵk ≤ δ/2, and the proof bounds it by a quantity proportional to 1/δ².The stated bound is k′ ≤ (4rMLN^1.5 + 1)2/δ².Source: Appendix A · p. 11

APPENDIX B PROOF OF PROPOSITION 2

The proof decomposes OUTTA's regret into scheduling and rate-adaptation terms, then bounds these components using the algorithm's selection rules and confidence estimates.

APPENDIX B PROOF OF PROPOSITION 2

  • The proof rewrites OUTTA's regret as a sum of components and bounds the scheduling contribution using the algorithm's schedule choice.The schedule maximizes a weight combining virtual queue lengths and estimated rate rewards.Source: Appendix B · pp. 11–13
  • The rate-adaptation contribution is analyzed through counts of user–AP–rate selections and confidence events, with Chernoff–Hoeffding bounds used for deviations.The proof defines H as the number of times a user uses a given rate and AP, and separates terms G1 through G4.Source: Appendix B · pp. 13–14
  • The proof combines the component bounds to obtain the desired regret result.Source: Appendix B · pp. 14–15

APPENDIX C PROOF OF LEMMA 1

The proof bounds the change in virtual-queue norms and uses the resulting Lyapunov drift condition to show negative drift when the potential is sufficiently large.

APPENDIX C PROOF OF LEMMA 1

  • The proof bounds the change in the queue-vector norm using concavity of the square root and inequalities relating vector norms.It also uses the L1 norm to bound the vector norm and bounds positive-part squares by ordinary squares.Source: Appendix C · pp. 15–16
  • The proposed OUTTA schedule is compared with a schedule maximizing the virtual-queue-weighted user allocation when deriving the drift bound.Source: Appendix C · pp. 15–16
  • For ϵk ≤ δ/2, the drift of V(kT) is at most −δ/4 once V(kT) reaches the stated threshold Wk.Source: Appendix C · p. 16
Loading 2609.09387v1…