International audience

International audience

We present a unifying framework that bridges Bayesian asymptotics and information theory to analyze the asymptotic Shannon capacity of general large-scale MIMO channels including ones with nonlinearities or imperfect hardware.We derive both an analytic capacity formula and an asymptotically optimal input distribution in the large-antenna regime, each of which depends solely on the single-output channel’s Fisher information through a term we call the(tilted) Jeffreys factor. We demonstrate how our method applies broadly to scenarios with clipping, coarse quantization (including 1-bit ADCs), phase noise, fading with imperfect CSI, and even optical Poisson channels. Our asymptotic analysis motivates a practical approach to constellation design via a compander-like transformation. Furthermore, we introduce a low-complexity receiver structure that approximates the log-likelihood by quantizing the channel outputs into finitely many bins, enabling near-capacity performance with computational complexity independent of the output dimension. Numerical results confirm that the proposed method unifies and simplifies many previously intractable MIMO capacity problems and reveals how the Fisher information alone governs the channel’s asymptotic behavior.

We consider linear stochastic bandits where the set of actions is an ellipsoid. We provide the first known minimax optimal algorithm for this problem. We first derive a novel information-theoretic lower bound on the regret of any algorithm, which must be at least $\Omega(\min(d \sigma \sqrt{T} + d \|\theta\|_{A}, \|\theta\|_{A} T))$ where $d$ is the dimension, $T$ the time horizon, $\sigma^2$ the noise variance, $A$ a matrix defining the set of actions and $\theta$ the vector of unknown parameters. We then provide an algorithm whose regret matches this bound to a multiplicative universal constant. The algorithm is non-classical in the sense that it is not optimistic, and it is not a sampling algorithm. The main idea is to combine a novel sequential procedure to estimate $\|\theta\|$, followed by an explore-and-commit strategy informed by this estimate. The algorithm is highly computationally efficient, and a run requires only time $O(dT + d^2 \log(T/d) + d^3)$ and memory $O(d^2)$, in contrast with known optimistic algorithms, which are not implementable in polynomial time. We go beyond minimax optimality and show that our algorithm is locally asymptotically minimax optimal, a much stronger notion of optimality. We further provide numerical experiments to illustrate our theoretical findings. The code to reproduce the experiments is available at \url{https://github.com/RaymZhang/LinearBanditsEllipsoidsMinimaxCOLT}.

Motivated by distributed multi-armed bandit, we introduce the two-player L-armed "bandit channel" with independent Bernoulli rewards, where users choose actions (input) and observe rewards (output). We derive a bound on the error exponent as a minimum of two types of errors that we then analyze separately. We further study the mutual information and show that the support of the optimal input distribution is a subset of the three best arms. We also compute the Shannon upper bound of the capacity as a special case of a two-way channel. In the case of identically distributed arms, the upper and lower bounds are very close.

We study the placement of virtual functions aimed at minimizing the cost. We propose a novel algorithm, using ideas based on multi-armed bandits. We prove that these algorithms learn the optimal placement policy rapidly, and their regret grows at a rate at most$O(N M \sqrt{T \ln T})$while respecting the feasibility constraints with high probability, where$T$is total time slots,$M$is the number of classes of function and$N$is the number of computation nodes. We show through numerical experiments that the proposed algorithm both has good practical performance and modest computational complexity. We propose an acceleration technique that allows the algorithm to achieve good performance also in large networks where computational power is limited. Our experiments are fully reproducible, and the code is publicly available.

We consider a stochastic multi-armed bandit problem with i.i.d. rewards where the expected reward function is multimodal with at most $m$ modes. We propose the first known computationally tractable algorithm for computing the solution to the Graves-Lai optimization problem, which in turn enables the implementation of asymptotically optimal algorithms for this bandit problem.

In this work, we investigate the capacity of multi-antenna fading channels with 1-bit quantized output per receive antenna. Specifically, leveraging Bayesian statistical tools, we analyze the asymptotic regime with a large number of receive antennas. In the coherent case, where the channel state information (CSI) is known at the receiver’s side, we characterize the asymptotic capacity and derive the exact scaling in the extreme regimes of signal-to-noise ratio (SNR) and the number of transmit antennas. In the non-coherent case, where the CSI is unknown but remains constant duringTsymbol periods, we first obtain the exact asymptotic capacity for$T\le 3$. Then, we propose a scheme involving uniform signaling in the covariance space and derive a non-asymptotic lower bound on the capacity for an arbitrary block sizeT. Furthermore, we propose a genie-aided upper bound where the channel is revealed to the receiver. We show that the upper and lower bounds coincide whenTis large. In the low SNR regime, we derive the asymptotic capacity up to a vanishing term, which, remarkably, matches our capacity lower bound.

We generalize McDiarmid's inequality for functions with bounded differences on a high probability set, using an extension argument. Those functions concentrate around their conditional expectations. We illustrate the usefulness of this generalized inequality on a few examples. We further extend the results to concentration in general metric spaces.

In this work, we investigate the capacity of a block fading one-bit multi-antenna channel without a priori channel state information. We consider the asymptotic regime with a large number of receive antennas. We show that the capacity scales as$\frac{1}{2}\begin{pmatrix}T\\ 2\end{pmatrix}\log(\alpha_{\text{snr},T}n_{\mathrm{r}})$under the peak power constraint$\mathsf{snr}$and with coherence block size$T$. In particular, we derive the exact form of$\alpha_{\text{snr},T}$for$T=2$and$T=3$. Furthermore, for an arbitrary value of$T$, we derive a lower bound of$\alpha_{\text{snr},T}$by proposing a low-complexity signaling scheme. We also obtain a closed-form expression of$\alpha_{\text{snr},T}$when$\mathsf{snr}$is small.

We consider Thompson Sampling (TS) for linear combinatorial semi-bandits and subgaussian rewards. We propose the first known TS whose finite-time regret does not scale exponentially with the dimension of the problem. We further show the mismatched sampling paradox: A learner who knows the rewards distributions and samples from the correct posterior distribution can perform exponentially worse than a learner who does not know the rewards and simply samples from a well-chosen Gaussian posterior. The code used to generate the experiments is available at https://github.com/RaymZhang/CTS-Mismatched-Paradox

We address the problem of data detection for the multiple-input multiple-output (MIMO) channel employing one-bit quantizers at the receiver, taking into account different settings of channel state information (CSI) at the receiver (CSIR). In the first part and under perfect CSI conditions, we propose a two-step low-complexity data detection algorithm that reduces the maximum likelihood (ML) search space. The key idea is based on constructing a list of constellation points exploiting the Hessian matrix of the log-likelihood function. We convert the original detection problem under binary observations into the classical integer least-squares optimization enabling direct use of efficient sphere-decoding algorithms. This method is then extended to the multi-bit case along with an assessment of the computational complexity. In the second part, we focus on a real channel model and assume only the availability of statistical CSIR. We formulate the optimal detection metric under a pilot training scheme and present the main challenges in its evaluation, then employ the Laplace method to retrieve an approximation in closed form. We demonstrate through numerical experiments near-optimality of our proposed solutions in terms of vector error rates with respect to oracle lower bounds on their corresponding ML metric. Finally, we also investigate the performance in practical spatially correlated massive MIMO channels.

We study contextual linear bandit problems under feature uncertainty; they are noisy with missing entries. To address the challenges of the noise, we analyze Bayesian oracles given observed noisy features. Our Bayesian analysis finds that the optimal hypothesis can be far from the underlying realizability function, depending on the noise characteristics, which are highly non-intuitive and do not occur for classical noiseless setups. This implies that classical approaches cannot guarantee a non-trivial regret bound. Therefore, we propose an algorithm that aims at the Bayesian oracle from observed information under this model, achieving $\tilde{O}(d\sqrt{T})$ regret bound when there is a large number of arms. We demonstrate the proposed algorithm using synthetic and real-world datasets.

We propose a novel algorithm for multi-player multi-armed bandits without collision sensing information. Our algorithm circumvents two problems shared by all state-of-the-art algorithms: it does not need as an input a lower bound on the minimal expected reward of an arm, and its performance does not scale inversely proportionally to the minimal expected reward. We prove a theoretical regret upper bound to justify these claims. We complement our theoretical results with numerical experiments, showing that the proposed algorithm outperforms state-of-the-art in practice.

We consider combinatorial semi-bandits with uncorrelated Gaussian rewards. In this article, we propose the first method, to the best of our knowledge, that enables to compute the solution of the Graves-Lai optimization problem in polynomial time for many combinatorial structures of interest. In turn, this immediately yields the first known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits.

In this paper we consider Thompson Sampling for combinatorial semi-bandits. We demonstrate that, perhaps surprisingly, Thompson Sampling is sub-optimal for this problem in the sense that its regret scales exponentially in the ambient dimension, and its minimax regret scales almost linearly. This phenomenon occurs under a wide variety of assumptions including both non-linear and linear reward functions in the Bernoulli distribution setting. We also show that including a fixed amount of forced exploration to Thompson Sampling does not alleviate the problem. We complement our theoretical results with numerical results and show that in practice Thompson Sampling indeed can perform very poorly in some high dimension situations.

Stochastic Rank-One Bandits are a simple framework for regret minimization problems over rank-one matrices of arms. The initially proposed algorithms are proved to have logarithmic regret, but do not match the existing lower bound for this problem. We close this gap by first proving that rank-one bandits are a particular instance of unimodal bandits, and then providing a new analysis of Unimodal Thompson Sampling (UTS). We prove an asymptotically optimal regret bound on the frequentist regret of UTS and we support our claims with simulations showing the significant improvement of our method compared to the state-of-the-art.

We consider a Device-to-Device (D2D) aided multicast channel, where a base station (BS) wishes to convey a common message to many receivers and these receivers cooperate with each other. We analyze the performance of a two-phase cooperative multicasting scheme requiring only statistical channel knowledge at the BS. Our analysis reveals that, as the number of receivers K grows, the two-phase scheme guarantees an average multicast rate of 1/2 log2(1 + β ln K) with high probability for any β1.

We propose a novel resource allocation scheme for Ultra- Reliable and Low Latency communication (URLLC) traffic in the uplink of 5G systems. We consider industrial scenarios where a set of machines transmit packets intermittently to a central controller via a base station. We consider contention-based access in realistic scenarios where the delay budget and the 5G New Radio (NR) design allows the reception of few Acknowledgements (ACK), but always waiting for ACKs before retransmission is insufficient to ensure high reliability. This may be seen as a problem of Automatic Repeat Request (ARQ) with delayed feedback. The goal is to minimize the expected number of retransmissions subject to a reliability constraint within a delay budget. We derive the optimal policy that exploits the tradeoff between waiting for the ACK and achieving the target reliability.

Rate Adaptation (RA) is a fundamental mechanism in 802.11 systems. It allows transmitters to adapt the coding and modulation scheme as well as the MIMO transmission mode to the radio channel conditions, to learn and track the (mode, rate) pair providing the highest throughput. The design of RA mechanisms has been mainly driven by heuristics. In contrast, we rigorously formulate RA as an online stochastic optimization problem. We solve this problem and present G-ORS (Graphical Optimal Rate Sampling), a family of provably optimal (mode, rate) pair adaptation algorithms. Our main result is that G-ORS outperforms state-of-the-art algorithms such as MiRA and Minstrel HT, as demonstrated by experiments on a 802.11n network test-bed. The design of G-ORS is supported by a theoretical analysis, where we study its performance in stationary radio environments where the successful packet transmission probabilities at the various (mode, rate) pairs do not vary over time, and in non-stationary environments where these probabilities evolve. We show that under G-ORS, the throughput loss due to the need to explore sub-optimal (mode, rate) pairs does not depend on the number of available pairs. This is a crucial advantage as evolving 802.11 standards offer an increasingly large number of (mode, rate) pairs. We illustrate the superiority of G-ORS over state-of-the-art algorithms, using both trace-driven simulations and test-bed experiments.

We consider coded caching over the fading broadcast channel, where the users, equipped with a memory of finite size, experience asymmetric fading statistics. It is known that a naive application of coded caching over the channel at hand performs poorly especially in the regime of a large number of users due to a vanishing multicast rate. We overcome this detrimental effect by a careful design of opportunistic scheduling policies such that some utility function of the long-term average rates should be maximized while balancing fairness among users. In particular, we propose a threshold-based scheduling that requires only statistical channel state information and one-bit feedback from each user. More specifically, each user indicates via feedback whenever its SNR is above a threshold determined solely by the fading statistics and the fairness requirement. Surprisingly, we prove that this simple scheme achieves the optimal utility in the regime of a large number of users.

We consider a device-to-device (D2D) aided multicast channel, where a transmitter wishes to convey a common message to many receivers and these receivers cooperate with each other. We propose a simple computationally efficient scheme requiring only statistical channel knowledge at transmitter. Our analysis in general topologies reveals that, when the number of receivers$K$grows to infinity, the proposed scheme guarantees a multicast rate of$\frac{1}{2}\log_{2}(1+\beta\ln K)$with high probability for any$\beta < \beta^{\star}$where$\beta^{\star}$depends on the network topology. This scheme undergoes a phase transition at threshold$\beta^{\star}\ln K$where transmissions are successful/unsuccessful with high probability when the SNR is above/below this threshold. We also analyze the outage rate of the proposed scheme in the same setting.

We consider coded caching over the fading broadcast channel, where the users, equipped with a memory of finite size, experience asymmetric fading statistics. It is known that a naive application of coded caching over the channel at hand performs poorly especially in the regime of a large number of users due to a vanishing multicast rate. We overcome this detrimental effect by a careful design of opportunistic scheduling policies such that some utility function of the long-term average rates should be maximized while balancing fairness among users. In particular, we propose a threshold-based scheduling that requires only statistical channel state information and one-bit feedback from each user. More specifically, each user indicates via feedback whenever its SNR is above a threshold determined solely by the fading statistics and the fairness requirement. Surprisingly, we prove that this simple scheme achieves the optimal utility in the regime of a large number of users. Numerical examples show that our proposed scheme performs closely to the scheduling with full channel state information, but at a significantly reduced complexity.

We consider the multiple-input multiple-output (MIMO) communication channel impaired by phase noises at both the transmitter and receiver. We focus on the maximum likelihood (ML) detection problem for uncoded single-carrier transmission. We derive an approximation of the likelihood function, based on which we propose an efficient detection algorithm. The proposed algorithm, named self-interference whitening (SIW), consists in: 1) estimating the self-interference caused by the phase noise perturbation; 2) whitening the said interference; and 3) detecting the transmitted vector. While the exact ML solution is computationally intractable, we construct a simulation-based lower bound on the error probability of ML detection. Leveraging this lower bound, we perform extensive numerical experiments demonstrating that SIW is, in most cases of interest, very close to optimal with moderate phase noise. More importantly and perhaps surprisingly, such near-ML performance can be achieved by applying only twice the nearest neighbor detection algorithm. In this sense, our results reveal a striking fact: near-ML detection of phase noise corrupted MIMO channels can be done as efficiently as for conventional MIMO channels without phase noise.

We consider content delivery over fading broadcast channels. A server wants to transmit K files to K users, each equipped with a cache of finite size. Using the coded caching scheme of Maddah-Ali and Niesen, we design an opportunistic delivery scheme where the long-term sum content delivery rate scales with the number of users in the system. The proposed delivery scheme combines superposition coding together with appropriate power allocation across sub-files intended to different subsets of users. We analyze the long- term average sum content delivery rate achieved by two special cases of our scheme: 1) a selection scheme that chooses the subset of users with the largest weighted rate, and 2) a baseline scheme that transmits to all K users using the scheme of Maddah-Ali and Niesen. We prove that coded caching with appropriate user selection is scalable since it yields a linear increase of the average sum content delivery rate.

We consider the problem of accurately estimating the reliability of workers based on noisy labels they provide, which is a fundamental question in crowdsourcing. We propose a novel lower bound on the minimax estimation error which applies to any estimation procedure. We further propose Triangular Estimation (TE), an algorithm for estimating the reliability of workers. TE has low complexity, may be implemented in a streaming setting when labels are provided by workers in real time, and does not rely on an iterative procedure. We prove that TE is minimax optimal and matches our lower bound. We conclude by assessing the performance of TE and other state-of-the-art algorithms on both synthetic and real-world data.

This paper introduces and addresses a wide class of stochastic bandit problems where the function mapping the arm to the corresponding reward exhibits some known structural properties. Most existing structures (e.g. linear, lipschitz, unimodal, combinatorial, dueling,...) are covered by our framework. We derive an asymptotic instance-specific regret lower bound for these problems, and develop OSSB, an algorithm whose regret matches this fundamental limit. OSSB is not based on the classical principle of ``optimism in the face of uncertainty'' or on Thompson sampling, and rather aims at matching the minimal exploration rates of sub-optimal arms as characterized in the derivation of the regret lower bound. We illustrate the efficiency of OSSB using numerical experiments in the case of the linear bandit problem and show that OSSB outperforms existing algorithms, including Thompson sampling

We investigate streaming over multiple links. A file is split into small units called chunks that may be requested on the various links according to some policy and received after some random delay. After a start-up time called pre-buffering time, received chunks are played at a fixed speed. There is starvation if the chunk to be played has not yet arrived. We provide lower bounds (fundamental limits) on the starvation probability of any policy. We further propose simple, order-optimal policies that require no feedback. For general delay distributions, we provide tractable upper bounds for the starvation probability of the proposed policies, allowing to select the pre-buffering time appropriately. We specialize our results to: 1) links that employ Carrier Sense Multiple Access (CSMA) or opportunistic scheduling at the packet level; 2) links shared with a primary user; and 3) links that use fair rate sharing at the flow level. We consider a generic model, so that our results give insight into the design and the performance of media streaming over: 1) wired networks with several paths between the source and the destination; 2) wireless networks featuring spectrum aggregation; and 3) multi-homed wireless networks.

We investigate streaming over multiple links. We provide lower bounds on the starvation probability of any policy and simple, order-optimal policies with matching and tractable upper bounds.

This paper investigates stochastic and adversarial combinatorial multi-armed bandit problems. In the stochastic setting under semi-bandit feedback, we derive a problem-specific regret lower bound, and discuss its scaling with the dimension of the decision space. We propose ESCB, an algorithm that efficiently exploits the structure of the problem and provide a finite-time analysis of its regret. ESCB has better performance guarantees than existing algorithms, and significantly outperforms these algorithms in practice. In the adversarial setting under bandit feedback, we propose CombEXP, an algorithm with the same regret scaling as state-of-the-art algorithms, but with lower computational complexity for some combinatorial problems.

We investigate multi-armed bandits with budgets, a natural model for ad-display optimization encountered in search engines. We provide asymptotic regret lower bounds satisfied by any algorithm, and propose algorithms which match those lower bounds. We consider different types of budgets: scenarios where the advertiser has a fixed budget over a time horizon, and scenarios where the amount of money that is available to spend is incremented in each time slot. Further, we consider two different pricing models, one in which an advertiser is charged for each time her ad is shown (i.e., for each impression) and one in which the advertiser is charged only if a user clicks on the ad. For all of these cases, we show that it is possible to achieve O(log(T)) regret. For both the cost-per-impression and cost-per-click models, with a fixed budget, we provide regret lower bounds that apply to any uniformly good algorithm. Further, we show that B-KL-UCB, a natural variant of KL-UCB, is asymptotically optimal for these cases. Numerical experiments (based on a real-world data set) further suggest that B-KL-UCB also has the same or better finite-time performance when compared to various previously proposed (UCB-like) algorithms, which is important when applying such algorithms to a real-world problem.

Algorithms for learning to rank Web documents, display ads, or other types of items constitute a fundamental component of search engines and more generally of online services. In such systems, when a user makes a request or visits a web page, an ordered list of items (e.g. documents or ads) is displayed; the user scans this list in order, and clicks on the first relevant item if any. When the user clicks on an item, the reward collected by the system typically decreases with the position of the item in the displayed list. The main challenge in the design of sequential list selection algorithms stems from the fact that the probabilities with which the user clicks on the various items are unknown and need to be learned. We formulate the design of such algorithms as a stochastic bandit optimization problem. This problem differs from the classical bandit framework: (1) the type of feedback received by the system depends on the actual relevance of the various items in the displayed list (if the user clicks on the last item, we know that none of the previous items in the list are relevant); (2) there are inherent correlations between the average relevance of the items (e.g. the user may be interested in a specific topic only). We assume that items are categorized according to their topic and that users are clustered, so that users of the same cluster are interested in the same topic. We investigate several scenarios depending on the available side-information on the user before selecting the displayed list: (a) we first treat the case where the topic the user is interested in is known when she places a request; (b) we then study the case where the user cluster is known but the mapping between user clusters and topics is unknown. For both scenarios, we derive regret lower bounds and devise algorithms that approach these fundamental limits.

In this paper, we investigate dynamic channel and rate selection in cognitive radio systems that exploit a large number of channels free from primary users. In such systems, transmitters may rapidly change the selected (channel, rate) pair to opportunistically learn and track the pair offering the highest throughput. We formulate the problem of sequential channel and rate selection as an online optimization problem and show its equivalence to a structured multiarmed-bandit problem. The structure stems from inherent properties of the achieved throughput as a function of the selected channel and rate. We derive fundamental performance limits satisfied by any channel and rate adaptation algorithm and propose algorithms that achieve (or approach) these limits. In turn, the proposed algorithms optimally exploit the inherent structure of the throughput. We illustrate the efficiency of our algorithms using both test-bed and simulation experiments, in both stationary and nonstationary radio environments. In stationary environments, the packet successful transmission probabilities at the various channel and rate pairs do not evolve over time, whereas in nonstationary environments, they may evolve. In practical scenarios, the proposed algorithms are able to track the best channel and rate quite accurately without the need for any explicit measurement of and feedback on the quality of the various channels.

We consider stochastic multi-armed bandit problems where the expected reward is a Lipschitz function of the arm, and where the set of arms is either discrete or continuous. For discrete Lipschitz bandits, we derive asymptotic problem specific lower bounds for the regret satisfied by any algorithm, and propose OSLB and CKL-UCB, two algorithms that efficiently exploit the Lipschitz structure of the problem. In fact, we prove that OSLB is asymptotically optimal, as its asymptotic regret matches the lower bound. The regret analysis of our algorithms relies on a new concentration inequality for weighted sums of KL divergences between the empirical distributions of rewards and their true distributions. For continuous Lipschitz bandits, we propose to first discretize the action space, and then apply OSLB or CKL-UCB, algorithms that provably exploit the structure efficiently. This approach is shown, through numerical experiments, to significantly outperform existing algorithms that directly deal with the continuous set of arms. Finally the results and algorithms are extended to contextual bandits with similarities.

We consider stochastic multi-armed bandits where the expected reward is a unimodal function over partially ordered arms. This important class of problems has been recently investigated in (Cope 2009, Yu 2011). The set of arms is either discrete, in which case arms correspond to the vertices of a finite graph whose structure represents similarity in rewards, or continuous, in which case arms belong to a bounded interval. For discrete unimodal bandits, we derive asymptotic lower bounds for the regret achieved under any algorithm, and propose OSUB, an algorithm whose regret matches this lower bound. Our algorithm optimally exploits the unimodal structure of the problem, and surprisingly, its asymptotic regret does not depend on the number of arms. We also provide a regret upper bound for OSUB in non-stationary environments where the expected rewards smoothly evolve over time. The analytical results are supported by numerical experiments showing that OSUB performs significantly better than the state-of-the-art algorithms. For continuous sets of arms, we provide a brief discussion. We show that combining an appropriate discretization of the set of arms with the UCB algorithm yields an order-optimal regret, and in practice, outperforms recently proposed algorithms designed to exploit the unimodal structure.

Rate Adaptation (RA) is a fundamental mechanism in 802.11 systems. It allows transmitters to adapt the coding and modulation scheme as well as the MIMO transmission mode to the radio channel conditions, and in turn, to learn and track the (mode, rate) pair providing the highest throughput. So far, the design of RA mechanisms has been mainly driven by heuristics. In contrast, in this paper, we rigorously formulate such design as an online stochastic optimisation problem. We solve this problem and present ORS (Optimal Rate Sampling), a family of (mode, rate) pair adaptation algorithms that provably learn as fast as it is possible the best pair for transmission. We study the performance of ORS algorithms in stationary radio environments where the successful packet transmission probabilities at the various (mode, rate) pairs do not vary over time, and in non-stationary environments where these probabilities evolve. We show that under ORS algorithms, the throughput loss due to the need to explore sub-optimal (mode, rate) pairs does not depend on the number of available pairs. This is a crucial advantage as evolving 802.11 standards offer an increasingly large number of (mode, rate) pairs. We illustrate the efficiency of ORS algorithms (compared to the state-of-the-art algorithms) using simulations and traces extracted from 802.11 test-beds.

An important topic in performance evaluation of wireless networks is the modeling of inter-cell interference, to predict the distribution of the Signal to Interference plus Noise Ratio (SINR) in the network. The classical hexagonal model is generally intractable and requires extensive numerical calculations. Two approaches have been shown to produce tractable, closed-form formulas: Poisson networks (the interfering Base Stations (BSs) locations form a Poisson process) and fluid networks (the interfering BSs are replaced by a continuum of infinitesimal interferers). Compared to network measurements, the fluid model is known to be optimistic, while the Poisson model is pessimistic. We show that fluid networks are equivalent to dense Poisson networks. We show a Central Limit Theorem (CLT)-like result: the difference of interference predicted by the two models is Gaussian for dense networks with a known mean and variance. These results provide a justification of the fluid model. Furthermore, there is an interesting duality: for dense networks, all results proven for Poisson networks hold for fluid networks and vice-versa.

In dense wireless networks, inter-cell interference highly limits the capacity and quality of service perceived by users. Previous work has shown that approaches based on frequency reuse provide important capacity gains. We model a wireless network with Inter-Cell Interference Coordination (ICIC) at the flow level where users arrive and depart dynamically, in order to optimize quality of service indicators perceivable by users such as file transfer time for elastic traffic. We propose an algorithm to tune the parameters of ICIC schemes automatically based on measurements. The convergence of the algorithm to a local optimum is proven, and a heuristic to improve its convergence speed is given. Numerical experiments show that the distance between local optima and the global optimum is very small, and that the algorithm is fast enough to track changes in traffic on the time scale of hours. The proposed algorithm can be implemented in a distributed way with very small signaling load.

The adoption of autonomic features in network management becomes a necessity to cope with the increasing complexity of the telecommunications ecosystem. The purpose of this paper is to present the concept of Unified Management Framework (UMF) developed in the FP7 UniverSelf project. The core of UMF comprises three functional blocks, namely Governance, Coordination and Knowledge which allow to efficiently operate autonomic mechanisms such as SON functionalities in the radio access network. These are denoted as Network Empowerment Mechanisms (NEMs) that, by means of policies, enforce operator business and operation objectives. The paper focuses on the Coordination core block of UMF, and its instantiation to the problem of SON coordination for managing LTE-Advanced a Heterogeneous Network (HetNet) with relays. Prototype description and results are described so as to illustrate the value and applicability of the proposed framework.

This paper introduces self-optimization for wireless networks taking into account flow-level dynamics. Users arrive and leave the network according to a traffic model. Elastic traffic is considered here. The developed solutions self-optimize the network stability region using user feedback (measurements). The use case considered is cell size optimization. An algorithm is given, and its convergence is proven using stochastic approximation techniques. Convergence points are characterized, allowing performance gains to be evaluated rigorously. Performance gains are evaluated numerically, showing an important increase of the network capacity.

As plug-and-play devices, femtocells are expected to be self-managed, empowered by self-organization functionalities. This paper presents a Self-organizing networks (SON) process for off-loading macrocell traffic towards Open Subscriber Group (OSG) femtocells. The off-loading process comprises two SON functionalities: the first configures the femtocell transmitted pilot power, which depends on the received macrocell pilot power and the density of femtocells. The femtocell pilot powers are chosen using a look-up table generated through an off-line queuing theory based analysis. To mitigate interference from femtocells with different transmission powers, a self-optimizing Inter-Cell Interference Coordination (ICIC) functionality is activated. The performance gain of the self-organizing mechanisms is evaluated using a large scale network simulator. It is shown that in dense femtocell deployment, the SON off-loading can bring about considerable capacity gain.

We study, in this work, optimal sleep/wake up schemes for the base stations of network-operated femto cells deployed within macro cells for the purpose of offloading part of its traffic. Our aim is to minimize the energy consumption of the overall heterogeneous network while preserving the Quality of Service (QoS) experienced by users. We model such a system at the flow level, considering a dynamic user configuration, and derive, using Markov Decision Processes (MDPs), optimal sleep/wake up schemes based on the information on traffic load and user localization in the cell, in the cases where this information is complete, partial or delayed. Our results quantify the energy consumption and QoS perceived by the users in each of these cases and identify the tradeoffs between those two quantities. We also illustrate numerically the optimal policies in different traffic scenarios.

Relay stations are an important component of heterogeneous networks introduced in the LTE-Advanced technology as a means to provide very high capacity and QoS all over the cell area. This paper develops a self-organizing network (SON) feature to optimally allocate resources between backhaul and station to mobile links. Static and dynamic resource sharing mechanisms are investigated. For stationary ergodic traffic we provide a queuing model to calculate the optimal resource sharing strategy and the maximal capacity of the network analytically. When traffic is not stationary, we propose a load balancing algorithm to adapt both the resource sharing and the zones covered by the relays based on measurements. Convergence to an optimal configuration is proven using stochastic approximation techniques. Self-optimizing dynamic resource allocation is tackled using a Markov Decision Process model. Stability in the infinite buffer case and blocking rate and file transfer time in the finite buffer case are considered. For a scalable solution with a large number of relays, a well-chosen parameterized family of policies is considered, to be used as expert knowledge. Finally, a model-free approach is shown in which the network can derive the optimal parameterized policy, and the convergence to a local optimum is proven.

This paper shows a Self-organizing networks (SON) algorithm for interference coordination in downlink Orthogonal Frequency-Division Multiple Access (OFDMA) networks. A distributed algorithm is introduced with a proof of convergence for a static user population. The algorithm uses closed-form formulas for the transmit powers update, and is therefore computationally light. The proposed algorithm is applied to a 117 cells dynamic network simulator with a File Transfer Protocol (FTP) service, showing significant performance gains over a Reuse 1. The Quality of Service (QoS) of cell-edge users improves without degrading the QoS of other users. The trade-off between Block Call Rate (BCR), which is the proportion of users rejected by admission control, and cell-edge users throughput is shown, and a simple method for the network operator to manage it is provided.

This paper proposes two novel contributions: a fast statistical method for scheduling gain calculation is introduced, and we show how it can be combined with queuing theory and real network measurements in order to calculate the flow-level performance of a cellular network that uses Proportional Fair (PF) scheduling. A statistical method to evaluate the scheduling gain is proposed and a proof of its convergence is given. This method is three orders of magnitude faster than full system simulation. Based on these results, a queuing theory analysis is performed and is applied to the pedestrian A 3km/h channel model and LMMSE receiver. The evaluation uses drive tests measurements to reflect the realistic distribution of radio conditions. The derived flow-level performance of PF scheduling, including blocking rate, outage rate and flow throughput, is of major interest for network operators.