Skip to Main content Skip to Navigation

Apprentissage distribué dans les jeux pour les réseaux sans fil

Abstract : In this thesis, we address the issue of optimal design and management of wireless networks, which have become crucial with the increasing demand for data. Centralized approaches are becoming infeasible, while distributed learning in games is a promising distributed approach. Particularly, potential games are attractive as the players of the game can distributively optimize a potential function. We extend this notion to near and noisy potential games, and study the convergence of learning algorithms in these frameworks. We then apply the obtained theoretical results to wireless networks. In a first part, we prove that under certain conditions Log-linear Learning Algorithm (LLA) and Binary LLA (BLLA) converge to the global minimum of the potential function in near potential games. We then prove the convergence of BLLA in noisy-potential games for fixed and decreasing temperature. We provide a sufficient number of estimation samples that guarantees the convergence for both bounded and unbounded noise. A key enabler for analyzing the convergence of the proposed algorithms is the resistance of trees in a Perturbed Markov Chain (PMC). We develop new rules to simplify the calculation of the resistance of trees. In a second part, we apply our results to practical problems in wireless networks. We first consider load balancing in heterogeneous cellular networks and propose a distributed algorithm to minimize an alpha-fairness objective function that captures various network performance and fairness criteria. The near-potential game approach allows us to decrease the size of base station's neighborhood, with which it has to exchange information. In this context, we also propose a new annealing schedule for LLA adapted to finite time horizons. Next, we apply BLLA to Channel Assignment Problem (CAP) in Device-to-Device (D2D) networks. Because of the rate estimation noise, the noisy-potential game framework naturally arises. Moving on from potential games, we address a general constrained submodular maximization problem. We model it as a finite game with players having limited or no information about their neighborhood. We characterize the performance of the greedy algorithm and we provide the best information graph for a given number of players and information edges.
Complete list of metadata
Contributor : ABES STAR :  Contact
Submitted on : Wednesday, January 12, 2022 - 3:59:08 PM
Last modification on : Friday, January 14, 2022 - 3:31:46 AM
Long-term archiving on: : Wednesday, April 13, 2022 - 11:20:01 PM


Version validated by the jury (STAR)


  • HAL Id : tel-03523335, version 1


Mohammed Shabbir Ali. Apprentissage distribué dans les jeux pour les réseaux sans fil. Réseaux et télécommunications [cs.NI]. Télécom ParisTech, 2017. Français. ⟨NNT : 2017ENST0030⟩. ⟨tel-03523335⟩



Record views


Files downloads