In the thesis, we address the fundamental problem of opportunistic spectrum access in a multi-channel communication system. Specifically, we consider a communication system in which a user has access to multiple channels, but is limited to sensing and transmitting only on one at a given time. We explore how the smart user should exploit past observations and the knowledge of the stochastic properties of these channels to maximize its transmission rate by switching channels opportunistically. Formally, we provide a generic analysis on the opportunistic spectrum access problem by casting the problem into the restless multi-armed bandit (RMAB) problem, one of the most well-known generalizations of the classic multi-armed bandit (MAB) problem, which is of fundamental importance in stochastic decision theory. Despite the significant research efforts in the field, the RMAB problem in its generic form still remains open. Until today, very little result is reported on the structure of the optimal policy. Obtaining the optimal policy for a general RMAB problem is often intractable due to the exponential computation complexity. Hence, a natural alternative is to seek a simple myopic policy maximizing the short-term reward. Therefore, we develop three axioms characterizing a family of functions which we refer to as regular functions, which are generic and practically important. We then establish the optimality of the myopic policy when the reward function can be expressed as a regular function and the discount factor is bounded by a closed-form threshold determined by the reward function. We also illustrate how the derived results, generic in nature, are applied to analyze a class of RMAB problems arising from multi-channel opportunistic access. Next, we further investigate the more challenging problem where the user has to decide the number of channels to sense in each slot in order to maximize its utility (e.g., throughput). After showing the exponential complexity of the problem, we develop a heuristic v-step look-ahead strategy. In the developed strategy, the parameter v allows to achieve a desired tradeoff between social efficiency and computation complexity. We demonstrate the benefits of the proposed strategy via numerical experiments on several typical settings.

Dans cette thèse, nous abordons le problème fondamental de l'accès au spectre opportuniste dans un système de communication multi-canal. Plus précisément, nous considérons un système de communication dans lequel un utilisateur a accès à de multiples canaux, tout en étant limité à la détection et la transmission sur un sous-ensemble de canaux. Nous explorons comment l'utilisateur intelligent exploite ses observations passées et les propriétés stochastiques de ces canaux afin de maximiser son débit. Formellement, nous fournissons une analyse générique sur le problème d'accès au spectre opportuniste en nous basant sur le problème de `restless multi-bandit’ (RMAB), l'une des généralisations les plus connues du problème classique de multi-armed bandit (MAB), un problème fondamental dans la théorie de décision stochastique. Malgré les importants efforts de la communauté de recherche dans ce domaine, le problème RMAB dans sa forme générique reste encore ouvert. Jusqu'à aujourd'hui, très peu de résultats sont connus sur la structure de la politique optimale. L'obtention de la politique optimale pour un problème RMAB général est intraçable dû la complexité de calcul exponentiel. Par conséquent, une alternative naturelle est de se focaliser sur la politique myopique qui maximise la récompense à immédiate, tout en ignorant celles du futur. Donc, nous développons trois axiomes caractérisant une famille de fonctions que nous appelons fonctions régulières, qui sont génériques et pratiquement importantes. Nous établissons ensuite l'optimalité de la politique myopique lorsque la fonction de récompense peut être exprimée comme une fonction régulière et le facteur de discount est borné par un seuil déterminé par la fonction de récompense. Nous illustrons également l'application des résultats pour analyser une classe de problèmes RMAB dans l'accès opportuniste. Ensuite, nous étudions un problème plus difficile, où l'utilisateur doit configurer le nombre de canaux à accéder afin de maximiser son utilité (par exemple, le débit). Après avoir montré la complexité exponentielle du problème, nous développons une stratégie heuristique v-step look-ahead. Dans la stratégie développée, le paramètre v permet de parvenir à un compromis souhaité entre l'efficacité sociale et de la complexité de calcul. Nous démontrons les avantages de la stratégie proposée via des simulations numériques sur plusieurs scénarios typiques. / In the thesis, we address the fundamental problem of opportunistic spectrum access in a multi-channel communication system. Specifically, we consider a communication system in which a user has access to multiple channels, but is limited to sensing and transmitting only on one at a given time. We explore how the smart user should exploit past observations and the knowledge of the stochastic properties of these channels to maximize its transmission rate by switching channels opportunistically. Formally, we provide a generic analysis on the opportunistic spectrum access problem by casting the problem into the restless multi-armed bandit (RMAB) problem, one of the most well-known generalizations of the classic multi-armed bandit (MAB) problem, which is of fundamental importance in stochastic decision theory. Despite the significant research efforts in the field, the RMAB problem in its generic form still remains open. Until today, very little result is reported on the structure of the optimal policy. Obtaining the optimal policy for a general RMAB problem is often intractable due to the exponential computation complexity. Hence, a natural alternative is to seek a simple myopic policy maximizing the short-term reward. Therefore, we develop three axioms characterizing a family of functions which we refer to as regular functions, which are generic and practically important. We then establish the optimality of the myopic policy when the reward function can be expressed as a regular function and the discount factor is bounded by a closed-form threshold determined by the reward function. We also illustrate how the derived results, generic in nature, are applied to analyze a class of RMAB problems arising from multi-channel opportunistic access. Next, we further investigate the more challenging problem where the user has to decide the number of channels to sense in each slot in order to maximize its utility (e.g., throughput). After showing the exponential complexity of the problem, we develop a heuristic v-step look-ahead strategy. In the developed strategy, the parameter v allows to achieve a desired tradeoff between social efficiency and computation complexity. We demonstrate the benefits of the proposed strategy via numerical experiments on several typical settings.

L'utilisation intensive des services de données mobiles a de plus en plus augmenté la consommation de ressources sur les réseaux sans fil. La ressource principale utilisée pour la communication sans fil est le spectre de fréquence. À mesure que le trafic de données augmente brusquement, de nouvelles bandes du spectre de fréquences ne sont pas disponibles dans la même proportion, ce qui rend le spectre de fréquence de plus en plus rare et saturé. Plusieurs propositions ont été présentées pour optimiser l'allocation des canaux de fréquences afin d'atténuer les interférences entre les liaisons proches qui transmettent des données. Beaucoup d'entre eux utilisent un critère unique et ne considèrent pas le comportement de l'utilisateur pour guider le processus d'allocation de canaux. Les utilisateurs ont des cycles de routine et un comportement social. Ils passent au travail, à l'école, utilisent leurs appareils mobiles générant du trafic de données, et rencontrent des amis formant des groupes. Ces caractéristiques peuvent être explorées pour optimiser le processus d'allocation des canaux.Cette thèse présente une stratégie d'allocation de canaux pour les réseaux sans fil basée sur le comportement de l'utilisateur. Notre contribution principale consiste à considérer certaines caractéristiques du comportement de l'utilisateur, telles que la mobilité, le trafic et la popularité dans le processus d'allocation des canaux. De cette façon, nous priorisons l'allocation de canaux pour les nœuds qui resteront dans le réseau dans une fenêtre de temps future, avec un trafic plus élevé dans le réseau, et avec plus de popularité. Nous adoptons une approche distribuée qui permet de limiter le nombre de messages échangés dans le réseau tout en répondant rapidement aux changements de la topologie du réseau. Dans notre évaluation des performances, nous considérons des scénarios dans des réseaux ad hoc et véhiculaires, et nous utilisons des modèles de mobilité synthétique, tels que SLAW et Manhattan grid, et l'ensemble de données de traces de ville de Cologne. Dans les scénarios, nous comparons notre mécanisme avec différents types de techniques : une centralisée (nommée TABU), une autre aléatoire (nommée RANDOM), une avec la plus grande distance spectrale (appelée LD) et une avec un seul canal (appelée SC). Nous évaluons les métriques telles que le débit agrégé, le débit de livraison des paquets et le délai de bout en bout.Les simulations envisageant un scénario ad hoc avec un routage monodiffusion montrent que notre stratégie présente des améliorations en termes de débit de l'ordre de 14,81% par rapport à RANDOM et de 16,28% par rapport à l'allocation de canal LD. Dans le scénario véhiculaire, notre stratégie montre des gains de taux de livraison de paquets de l'ordre de 11,65% et de 17,18% par rapport aux méthodes RANDOM et SC, respectivement. Dans ces deux scénarios, la performance de notre stratégie est proche de la limite supérieure donnée par l'approche centralisée de TABU, mais avec l’envoie de moins des messages. / The intensive use of mobile data services has increasingly increased resource consumption over wireless networks. The main resource used for wireless communication is the frequency spectrum. As data traffic rises sharply, new bands of the frequency spectrum are not available in the same proportion, making the frequency spectrum increasingly scarce and saturated. Several proposals have been presented to optimize frequency channel allocation in order to mitigate interference between nearby links that are transmitting data. Many of them use a single criterion and does not consider the user behavior to guide the channel allocation process. Users have routine cycles and social behavior. They routinary move to work, to school, use their mobile devices generating data traffic, and they meet with friends forming clusters. These characteristics can be explored to optimize the channel allocation process.This thesis presents a channel allocation strategy for wireless networks based on user behavior. Our main contribution is to consider some characteristics of the user behavior, such as mobility, traffic, and popularity in the channel allocation process. In this way, we prioritize the channel allocation for the nodes that will remain in the network in a future time window, with higher traffic in the network, and with more popularity. We adopt a distributed approach that allows limiting the number of messages exchanged in the network while quickly responding to changes in the network topology. In our performance evaluation, we consider scenarios in ad hoc and vehicular networks, and we use some synthetic mobility models, such as SLAW and Manhattan grid, and the traces dataset of Cologne city. In the scenarios, we compare our mechanism with different types of approaches: i.e., a centralized (named TABU), a random (named RANDOM), a with largest spectral distance (named LD), and a with single channel (named SC). We evaluate metrics such as aggregated throughput, packet delivery rate, and end-to-end delay. Simulations considering ad hoc scenario with unicast routing show that our strategy presents improvements in terms of throughput at the order of 14.81% than RANDOM and 16.28% than LD channel allocation. In vehicular scenario, our strategy shows gains of packet delivery rate at the order of 11.65% and 17.18% when compared to RANDOM and SC methods, respectively. In both scenarios, the performance of our strategy is close to the upper bound search of the TABU centralized approach, but with lower overhead.