In this paper we study a dynamic version of capacity maximization in the physical model of wireless communication. In our model, requests for connections between pairs of points in Euclidean space of constant dimension $d$ arrive iteratively over time. When a new request arrives, an online algorithm needs to decide whether or not to accept the request and to assign one out of $k$ channels and a transmission power to the channel. Accepted requests must satisfy constraints on the signal-to-interference-plus-noise (SINR) ratio. The objective is to maximize the number of accepted requests.
Using competitive analysis we study algorithms using distance-based power assignments, for which the power of a request relies only on the distance between the points. Such assignments are inherently local and particularly useful in distributed settings. We first focus on the case of a single channel. For request sets with spatial lengths in $[1,\Delta]$ and duration in $[1, \Gamma]$ we derive a lower bound of $\Omega(\Gamma\cdot\Delta^{d/2})$ on the competitive ratio of any deterministic online algorithm using a distance-based power assignment. Our main result is a near-optimal deterministic algorithm that is $O\left(\Gamma\cdot\Delta^{(d/2)+\varepsilon} right)$-competitive, for any constant $\varepsilon > 0$.
Our algorithm for a single channel can be generalized to $k$ channels. It can be adjusted to yield a competitive ratio of $O\left(k \cdot\Gamma^{1/k'}\cdot\Delta^{(d/2k'')+\varepsilon}\right)$ for any factorization $(k', k'')$ such that $k' \cdot k'' = k$. This illustrates the effectiveness of multiple channels when dealing with unknown request sequences. In particular, for $\Theta(\log \Gamma \cdot \log \Delta)$ channels this yields an $O(\log\Gamma\cdot\log \Delta)$-competitive algorithm. Additionally, we show how this approach can be turned into a randomized algorithm, which is $O(\log\Gamma\cdot\log \Delta)$-competitive even for a single channel. Finally, we show the robustness of our results by extending all upper bounds from Euclidean to doubling metrics.