Algorithme d’ordonnancement de processus en c (fcfs)

Remerciements

Je voudrais dans un premier temps remercier, mon directeur de mémoire Monsieur Nsiri Bechir , ……, pour sa patience, sa disponibilité et surtout ses judicieux conseils, qui ont contribué à alimenter ma réflexion, qui m’a guidé avec beaucoup d’attention dans la réalisation de ce mémoire de mastère. Je le remercie pour les discussions fructueuses et les conseils avisés et pour l’aide appropriée dans la rédaction de ce rapport.

Enfin, j’exprime mes vifs remerciements aux membres du jury d’avoir accepté d’évaluer ce travail.

Mille Merci…

Dédicaces

Je dédie ce travail…
A l’homme de ma vie, mon exemple éternel, mon soutien moral et source de joie et de bonheur, celui qui s’est toujours sacrifié pour me voir réussir, que dieu te garde dans son vaste paradis, à toi
mon père.
A la lumière de mes jours, la source de mes efforts, la flamme de mon cœur, ma vie et mon bonheur ;
maman que j’adore.
Aux personnes dont j’ai bien aimé la présence dans ce jour; je dédie ce travail dont le grand plaisir leurs revient en premier lieu pour leurs conseils, aides, et encouragements. Je leurs souhaite tout le bonheur du monde et la réussite dans tous les domaines ;
à tous mes frères et mes sœurs
En signe d’amour, de reconnaissance et de gratitudes pour les soutiens et les sacrifices dont il a fait preuve à mon égard ;
à monfiancaille
Aux personnes qui m’ont toujours aidé et encouragé, qui étaient toujours à mes côtés, et qui m’ont accompagnaient durant mon chemin d’études supérieures, mes aimables amis, collègues d’étude, et frères de cœur,
Ghofrane et Helmi

A toute la famille, tous ceux que j’aime et tous ceux qui m’aiment.

Merci…

…Zeineb

Abréviation

AMC: Adaptive Modulation and Coding
AMRF: Accès Multiple par Répartition en Fréquence
AWGN : Additive White Gaussian Noise
BS: Base Station
BER: Bit Error Rate
CDMA: Code Division Multiple Access
CRC: Cyclic Redundancy Check
CQI: Channel Quality Indicator
dB :(décibéles)
DM: Deadline Monotone
DRR : Déficit Round Robin
EDF: Earliest Deadline First
eNB : envolved NodeB
FCFS: First-Come First-Served
FIFO: first In First Out
FDMA: Frequency Division Multiple Access
HDR: High Dynamic Range
HPF: Highest Priority First
IEEE: Institute of Electrical and Electronics Engineers
LLF: Least Laxity First
LST: Least Slack Time
LTE: Long Term Evolution
MCS: Modulation and Coding Scheme
MS: Mobile Station
OFDM: Orthogonal Frequency Division Multiplexing
OFDMA: Orthogonal Frequency-Division Multiple Access
OS : Opirating System
PAPS: Premier Arrivé Premier Servi
PDCCH: Physical Downlink Control Channel
PFS: Proportional Fair Scheduling
QAM: Quadrature Amplitude Modulation
QoS: Quality of Service
QPSK: Quadrature Phase Shift Keying
RB: Resource Block
Rmin; The minimum rate demanded by users
RMS: Rate Monotonic scheduling
RR: Round Robin
SI: System Information
SJF: Shortest Job First
SINR: Le rapport Signal-Interférence-plus-bruit
SNR: Signal to

Noise Ratio
SRT: Shortest Remaining Time
AMRT: Accès Multiple à Répartition dans le Temps
TIC : Technologie de l’Iinformation et de la Communication
TTI: Transmission Time Interval
UC : Unité Central
UE: User Equipment
UIT: Union Internationale des Télécommunications
UMTS: Universal mobile Telecommunications System
WLAN: Wireless Local Area Network
WRR: Weighted Round Robin
3GPP:3rd generation partnership project

Introduction général

Contexte de travail
L’évolution et la coexistence de plusieurs technologies de réseaux sans fil offrent à l’utilisateur un environnement riche qui, s’il est judicieusement exploité, peut garantir de meilleures QoS pour les différents systèmes.
Les appareils sans fil sont contraints de fonctionner dans une certaine bande de fréquences. Chaque bande a une bande passante associée, qui correspond simplement à la quantité d\’espace de fréquence dans la bande.
Un grand nombre de mathématiques, de théorie de l\’information et de traitement du signal peuvent être utilisés pour montrer que des tranches à bande passante plus élevée peuvent être utilisées pour transmettre plus d\’informations. L\’utilisation d\’un spectre radioélectrique est rigoureusement contrôlée par les autorités de réglementation par le biais de processus d\’autorisation. Chaque plage de fréquences comporte un indicateur de bande et chaque plage de fréquences se comporte différemment et remplit différentes fonctions. Le spectre des fréquences est partagé par les utilisateurs civils, gouvernementaux et militaires de tous les pays, conformément aux règlements radio de l’Union internationale des télécommunications (UIT).

Cependant, l’exploitation de plusieurs interfaces radio se heurte à différentes problématiques dont l’affaiblissement de signal entre l’émetteur et le récepteur, les effets de masque dus à la présence d’obstacles et la perte du chemin et l’effet d’évanouissement, ont nécessité de revoir un certain nombre de procédures réseau dont l’ordonnancement des paquets sur les différentes interfaces et le routage multi-chemin de ces paquets qui peuvent traverser des réseaux et domaines différents avec des paramètres de QoS disparates.
Ce mémoire traite de l\’effet de nombreux types d\’algorithmes d\’ordonnancement ; comme l’algorithme Round Robin RR , Max Rate et proportional fair scheduling PFS, sur la performance de la liaison descendante, en termes de débit et de mesures d\’équité à l\’aide d\’un simulateur de niveau MATLAB.
Problématique
L\’utilisation des ondes radio comme support réseau peuvent présenter un certain nombre de problèmes de propagation susceptibles d\’interrompre la liaison radio, tels que
L\’affaiblissement du signal, à la distance entre l\’émetteur et le récepteur.
Les effets de masque, dus à la présence d\’obstacles sur le chemin de transmission.
L\’évanouissement (fading), du aux multiples réceptions du signal émis, dont les phases se superposent de façon constructives ou destructives.
Dans chaque réseau auquel plusieurs utilisateurs accèdent simultanément, il est nécessaire de coordonner la transmission pour éviter les collisions. Donc le canal commun doit être partagé par plusieurs utilisateurs et il est souhaitable de trouver une solution efficace pour partager le canal couramment utilisé. Un exemple très simple pour éviter le problème des collisions consiste à attribuer à chaque utilisateur son propre canal. Cependant, normalement, cette solution est loin d\’être optimale et il n\’est généralement pas possible de la mettre en œuvre en raison de limitations techniques. Nous avons donc besoin d\’approches plus sophistiquées pour répartir les ressources partagées entre les utilisateurs. L’ordonnanceur sert a résoudre ses problèmes par l’implémentation du différentes algorithmes d’ordonnancement.
Contribution
Dans cet article, nous présentons les performances de deux algorithmes d\’ordonnancement tels que Round Robin et Max Rate en termes d\’équité et de capacité du système. Nous pouvons voir que le planificateur RR favorise la priorité à l’équité entre tous les utilisateurs, quel que soit le débit du système. D\’autre part, le Max Rate est utilisé pour maximiser la capacité du système sans tenir compte de l\’équité entre les utilisateurs. À partir des résultats obtenus, nous proposons d’utiliser un planificateur mixte RR et Max pour optimiser les performances du système et de garanti l’équité entre les utilisateurs.
Organisation du manuscrit
Le travail présenté dans ce manuscrit est organisé en quatre chapitres.
Dans le premier chapitre \” Etude de l’art : Généralité sur l’ordonnancement \”, nous présentons
le cadre générale du la notion d’ordonnancement et discutons des différents algorithmes d’ordonnancement dans des différentes axes de recherches.

Dans le deuxième chapitre \”Etude des techniques d’ordonnancement dans un contexte radio mobile \”, nous allons présenter une synthèse des méthodes et techniques de les différents formalismes des techniques d’ordonnancement dans un contexte radio mobile.
de notre contribution en utilisant les algorithmes génétiques.
Dans le troisième chapitre \”Evaluation des performances des algorithmes d’ordonnancement dans un contexte radio mobile \”. Nous allons discuter les différentes principes de fonctionnement des algorithmes d’ordonnancement dans un contexte radio mobile avec une étude comparative entre ces performances.
Dans le quatrième chapitre \”Amélioration des performances d’un ordonnanceur dans un contexte Radio mobile\”. Nous allons présenter notre contribution avec l\’étude expérimentale que nous avons réalisé pour l’implémentation de notre approche.
Une conclusion générale et perspectives à la fin.

Chapitre 1 :

Etude de l’art
Généralité sur l’ordonnancement

Introduction
Pendant les années 1980 le système d’information est nié dans les domaines d’informatiques et des télécommunications ; le concept de système d\’information s\’applique maintenant à l\’ensemble des organisations, privées ou publiques. Il coordonne grâce à l\’information les activités de l\’organisation et lui permet ainsi d\’atteindre ses objectifs. Il est le véhicule de la communication dans l\’organisation. De plus, le SI (système d\’information) représente l\’ensemble des ressources (les hommes, le matériel, les logiciels) organisées pour : collecter, stocker, traiter et communiquer les informations. Ainsi la réponse à ces besoins s’avère difficile à traiter et provoques quelques problèmes de recherche opérationnelle d’allocation des ressources, planification des données, emploi du temps, etc.)
En effet, l’ordonnancement robuste joue un rôle essentiel dans divers contextes, en informatique, en administration, en production. Dans certaines situations, nous disposons d’informations précises sur l’utilisation future d’un système à concevoir, ce qui nous permet d’envisager, dès la phase de conception, un ensemble d’ordonnancements possibles des activités. Dans ce cas, il serait intéressant de baser les choix de conception sur les résultats des ordonnancements, mais à condition qu’ils soient robustes face aux évènements incertains qui pourraient survenir dans le futur. Sans cela, la confiance accordée aux performances des ordonnancements serait faible et le risque en les utilisant en conception serait alors très fort. Ainsi, pour être utilisés à des fins de conception, les ordonnancements proposés doivent être robustes afin de garantir le maintien de leurs performances face aux incertitudes.
Système d’information
I.1. Présentation
Un système d\’information (SI)[1], est un système organisé pour le collecte, l\’organisation, le stockage et la communication d\’ informations . Plus précisément, il s’agit de l’étude des réseaux complémentaires que les personnes et les organisations utilisent pour collecter, filtrer, traiter, créer et distribuer des données.
De plus, un système d\’information (SI) est un groupe de composants qui interagissent pour produire des informations.
Le système d\’information peut également être décrit comme une combinaison de matériel, de logiciels, de données, de processus métier et de fonctions pouvant être utilisés pour accroître l\’efficacité et la gestion d\’une organisation.
Le Système d\’information est l\’expression utilisée pour décrire un système automatisé (qui peut être appelé système d\’information informatisé), qu\’il soit manuel, qui couvre les personnes, les machines ou les méthodes organisées pour collecter, traiter, transmettre et diffuser des données représentant des informations pour l\’utilisateur ou le client.
Un système d\’information informatique est un système qu\’une branche de la science composée de personnes et d\’ordinateurs traite ou interprète des informations. Le terme est également parfois utilisé dans des sens plus restreints pour désigner uniquement le logiciel utilisé pour exécuter une base de données informatisée ou pour désigner uniquement un système informatique.
Un système d\’information est une étude académique des systèmes avec une référence spécifique à l\’information et aux réseaux complémentaires de matériel et de logiciel que les personnes et les organisations utilisent pour collecter, filtrer, traiter, créer et distribuer des données . L\’accent est mis sur un système d\’information ayant une frontière définitive, les utilisateurs, les processeurs, le stockage, les entrées, les sorties et les réseaux de communication susmentionnés.
Tout système d\’information spécifique vise à soutenir les opérations, la gestion et la prise de décision.
Un système d\’information est la technologie de l\’information et de la communication (TIC ) utilisée par une organisation, ainsi que la manière dont les personnes interagissent avec cette technologie pour soutenir les processus métier.
Certains auteurs établissent une distinction claire entre les systèmes d\’information, les systèmes informatiques et les processus métier .
Les systèmes d’information comprennent généralement une composante TIC, mais ne concernent pas uniquement les TIC, mais se concentrent plutôt sur l’utilisation finale des technologies de l’information. Les systèmes d\’information sont également différents des processus métier, ils aident à contrôler les performances des processus métier.
Un système d’information est considéré comme un type particulier de système de travail ; telle qu’un système de travail est un système dans lequel des personnes ou des machines exécutent des processus et des activités en utilisant des ressources pour produire des produits ou des services spécifiques pour les clients.
Un système d\’information est un système de travail dont les activités sont consacrées à la capture, à la transmission, au stockage, à la récupération, à la manipulation et à l\’affichage d\’informations.
À ce titre, les systèmes d’information interagissent avec les systèmes de données d’ une part et les systèmes d’activité de l’autre part.
Un système d\’information est une forme de système de communication dans lequel les données représentent et sont traitées comme une forme de mémoire sociale.
Un système d\’information peut également être considéré comme un langage semi- formel qui prend en charge la prise de décision et l\’action humaines.
Les systèmes d’information sont l’objet principal de l’étude de l’ informatique organisationnelle. Silver et al. (1995) ont fourni deux points de vue sur les systèmes d’information, notamment les logiciels, le matériel, les données, les personnes et les procédures. [2] Zheng a fourni une autre vue du système d\’information qui ajoute également des processus et des éléments essentiels du système tels que l\’environnement, les limites, les objectifs et les interactions. L’ Association for Computing Machinery définit «les spécialistes des systèmes d’information comme étant axés sur l’intégration de solutions informatiques et de processus métiers pour répondre aux besoins d’information des entreprises et autres entreprises».
Il existe différents types de systèmes d\’information, par exemple: les systèmes de traitement des transactions , les systèmes d\’aide à la décision , les systèmes de gestion des connaissances , les systèmes de gestion de l\’ apprentissage , les systèmes de gestion de bases de données et les systèmes d\’information de bureau.
Les technologies de l\’information sont essentielles à la plupart des systèmes d\’information. Elles sont généralement conçues pour permettre aux humains de réaliser des tâches pour lesquelles le cerveau humain n\’est pas bien adapté: gérer de grandes quantités d\’informations, effectuer des calculs complexes et contrôler plusieurs processus simultanés.
Les six composants qui doivent être réunis pour produire un système d’information sont les suivants: (les systèmes d’information sont des procédures organisationnelles et n’ont pas besoin d’ordinateur ou de logiciel, ces données sont erronées) (un système comptable un système d\’information).
Matériel: Le terme matériel désigne les machines. Cette catégorie comprend l\’ordinateur lui-même, souvent appelé unité centrale de traitement (CPU), et tout son équipement d\’assistance. Parmi les supports, les équipements sont des périphériques d\’entrée et de sortie, des périphériques de stockage et des appareils de communication.
Logiciel: Le terme logiciel désigne les programmes informatiques et les manuels (le cas échéant) qui les prennent en charge. Les programmes informatiques sont des instructions lisibles par machine qui dirigent les circuits des composants matériels du système pour fonctionner de manière à produire des informations utiles à partir des données. Les programmes sont généralement stockés sur un support d\’entrée / sortie, souvent un disque ou une bande.
Données: Les données sont des faits utilisés par les programmes pour produire des informations utiles. À l\’instar des programmes, les données sont généralement stockées sous une forme lisible par ordinateur sur disque ou bande jusqu\’à ce que l\’ordinateur en ait besoin.
Procédures: Les procédures sont les politiques qui régissent le fonctionnement d\’un système informatique. \”Les procédures sont pour les gens ce que le logiciel est au matériel\” est une analogie commune qui est utilisée pour illustrer le rôle des procédures dans un système.
Personnes: Chaque système a besoin de personnes pour être utile. L\’élément le plus négligé du système est souvent celui des personnes, probablement le composant qui influence le plus la réussite ou l\’échec des systèmes d\’information. Cela inclut «non seulement les utilisateurs, mais aussi ceux qui exploitent et entretiennent les ordinateurs, ceux qui gèrent les données et ceux qui supportent le réseau d’ordinateurs». [3].
Feedback: c\’est un autre composant du SI qui définit qu\’un SI peut recevoir un retour d\’information (bien que ce composant ne soit pas nécessaire pour fonctionner).
Les données constituent le pont entre le matériel et les personnes. Cela signifie que les données que nous collectons ne sont que des données jusqu\’à ce que nous impliquions des personnes. À ce stade, les données sont maintenant des informations.
Types de système d’information
La vue « classique » des systèmes d\’information trouvés dans les manuels [4] dans les
années 1980 était une pyramide des systèmes qui reflètent la hiérarchie de l\’organisation, généralement des systèmes de traitement des transactions au bas de la pyramide, suivi par les systèmes d\’information de gestion , aide à la décision systèmes , et se terminant par des systèmes d’information exécutifs au sommet. Bien que le modèle pyramidal reste utile depuis sa formulation, un certain nombre de nouvelles technologies ont été mises au point et de nouvelles catégories de systèmes d’information ont vu le jour, certaines ne correspondant plus facilement au modèle pyramidal initial.

Figure 1 : Le model pyramidale [1] Voici quelques exemples de tels systèmes:
Entrepôts de données
Progiciel de Gestion Intégré
Systèmes d\’entreprise
Systèmes experts
Moteurs de recherche
Système d\’information géographique
Système d\’information mondial
Bureautique
II. Ordonnancement (Scheduling)
II.1. Définition
Les problèmes d\’ordonnancement se rencontrent dans différents domaines, dès lors qu\’il est nécessaire d\’organiser et/ou de répartir le travail entre plusieurs entités. Plusieurs définitions ont été proposées pour le problème d\’ordonnancement et nous tirons de la littérature les définitions ci-dessous de l’ordonnancement, on en cite:
« Ordonnancement concerne l\’affectation de ressources limitées aux tâches dans le temps, c\’est un processus de prise de décision dont le but est d\’optimiser un ou plusieurs objectifs ».[8] Eric pinson Eric pinson. 88, le définit comme étant « L\’organisation dans le temps de l\’exécution d\’un projet ».
Pour Norman Sadeh Norman Sadeh 91, c\’est « l\’allocation dans le temps de ressources permettant l\’exécution d\’un ensemble de tâches ».
Pour Gotha  Gotha 93, c\’est « programmer des exécutions des tâches en leur allouant les ressources requises et en fixant leur dates de début ».
Un ensemble de règles qui spécifient quel utilisateur est autorisé à transmettre et quel utilisateur est autorisé à recevoir à chaque créneau temporel.
L’ordonnancement est le fait d\’ordonner des tâches à exécuter selon certaines contraintes. Ces tâches peuvent être l’exécution d\’opération sur les entrées-sorties ou le traitement de processus. Les contraintes peuvent être temporelles ou dimensionnelles.
L’ordonnancement occupe une place particulière dans la gestion informatisée des flux. C’est généralement le point de rencontre entre un système hiérarchise et informatise de production et le système de production lui-même. C’est le lieu de l’interface entre l’élaboration globale de la commande et la partie opérationnelle. La gestion de production crée les ordres de fabrication qui déterminent globalement ce qui doit être fait dans une période donnée.
L’ordonnancement consiste à prévoir l’enchainement de toutes les opérations élémentaires nécessaires à la réalisation de ces ordres de fabrication sur les ressources de production, tout en tenant compte des ressources secondaires (telles que les operateurs, les outillages, etc.), des contraintes extérieures (maintenance préventive, calendrier de travail, etc.) et de l’existant (taches en cours de réalisation, etc.).
Pour conclure, dans un réseau de communication sans fil, un ordonnanceur est le planificateur contrôle l\’allocation des ressources temps-fréquence partagées entre les utilisateurs à chaque instant. Le planificateur est situé dans la station de base et des ressources de liaison montante et de liaison descendante lui sont attribuées. Le programmateur détermine à quel utilisateur les ressources partagées (temps et fréquences) pour chaque TTI (1 ms) doivent être allouées pour la réception de la transmission .
Donc, il consiste à la bonne gestion des ressources dans un même système ( canal).

Nous pouvons distinguer deux catégories de problèmes d’ordonnancement. En fonction du degré de connaissance que l’on a du problème à résoudre, on parlera de :
Problème statique: lorsque les taches à ordonner sur une période ainsi que l’état initial de l’atelier sont connus au début de la période.
Problème dynamique: lorsque les décisions sont à prendre sur la période mais toutes les taches à réaliser sur cette période ne sont pas connues au début de la période.

De plus, un ordonnancement se décompose en deux parties toujours présentes dans l’atelier, mais pouvant revêtir une importance variable :
L’ordonnancement prédictif : consiste à prévoir \”à priori\” un certain nombre de décisions en fonction de données prévisionnelles et d’un modèle de l’atelier.
l’ordonnancement réactif : consiste à adapter les décisions prévues en fonction de l’état courant du système et des déviations entre la réalité et le modèle (ce qui est prévu en théorie)
II.2. Objectifs
L’ordonnanceur tente d\’établir une répartition appropriée des ressources avec certains objectifs tels que :
Acheminer le maximum d’informations vers leurs destinataires.
Optimisation de l’efficacité spectrale afin de maximiser le débit global du système.
Assurer l’équité et la différentiation de services entre les utilisateurs et garantir la QoS requise pour les différentes applications.
Permettre une allocation d’unités de ressources aux utilisateurs avec un débit plus élevé que possible et une certaine équité entre utilisateurs (trouver un compromis entre équité et débit).
Valider a priori la possibilité d\’exécuter l\’application en respectant ces contraintes
Permettre le respect de ces contraintes, lorsque l\’exécution se produit dans un mode courant
Permettre de borner les effets d\’incidents ou de surcharges.
III. Etude comparative des algorithmes d’ordonnancement
III.1. Introduction
L’ordonnancement est la programmation dans le temps de l’exécution d’une série de tâches (ou activités, opérations) sur un ensemble de ressources physiques (humaines et techniques), cherchant à optimiser certains critères, financiers ou technologiques, et en respectant les contraintes de fabrication et d’organisation (Gotha, 2002; Esquirol et Lopez, 1999).
Cette définition de l’ordonnancement ne permet pas de voir le nombre important de problèmes que ce domaine comprend. En effet, l’ordonnancement est lié à plusieurs secteurs de recherches et d’activités très variés. En informatique, le choix des tâches à envoyer aux processeurs se modélise comme un problème d’ordonnancement. En production, l’ordonnancement consiste à déterminer les séquences d’opérations à réaliser sur les différentes machines de l’atelier. En gestion de projet, ordonnancer, c’est déterminer les dates d’exécution des activités constituant le projet. Chacun de ces contextes nécessite la détermination des caractéristiques propres des tâches et des ressources, le type des décisions à prendre, les modalités d’exécution des tâches par les ressources, qui déterminent des contraintes sur les décisions et aussi les différents critères à optimiser.
On peut trouver plusieurs algorithmes d\’ordonnancement indépendants chacun gère une ou plusieurs ressources (pas les mêmes): CPU, Disques, Réseau (en particulier à Qualité de Service), Mémoire (swap, pages), etc.
Dans cette partie, consiste comme état de l’art, nous discutons des différents algorithmes d’ordonnancement dans quelques axes de recherches.

III.2. Ordonnancements des processus
Dans un système multiutilisateur, plusieurs processus peuvent être présents en mémoire centrale en attente d\’exécution. Si plusieurs processus sont prêts, le système d\’exploitation doit gérer l\’allocation du processeur aux différents processus à exécuter. C\’est l\’ordonnanceur (scheduler) [20] qui s\’acquitte de cette tâche.
Un ordonnanceur fait face à deux problèmes principaux :
Le choix du processus à exécuter,
Le temps d\’allocation du processeur au processus choisi.
Un ordonnancement constitue une solution au problème d\’ordonnancement. Il est défini par le planning d\’exécution des tâches (« ordre » et « calendrier ») et d\’allocation des ressources et vise à satisfaire un ou plusieurs objectifs. Un ordonnancement est très souvent représenté par un diagramme de Gantt.
III.2.1. Types d\’ordonnanceurs
Il est possible de distinguer trois types d\’ordonnanceurs : à long terme, à moyen terme et à court terme. Leurs principales fonctions sont les suivantes:
À long terme : L\’ordonnanceur fait la sélection de programmes à admettre dans le système pour leur exécution. Les programmes admis deviennent des processus à l\’état prêt. L\’admission dépend de la capacité du système (degré de multiprogrammation) et du niveau de performance requis.
À moyen terme : Il fait la sélection de processus déjà admis à débarquer ou rembarquer sur la mémoire. Il effectue ses tâches de gestion en fonction du degré de multiprogrammation du système, et aussi des requêtes d\’E/S des périphériques.
À court terme : L\’ordonnanceur à court terme a comme tâche la gestion de la file des processus prêts. Il sélectionne en fonction d\’une certaine politique le prochain processus à exécuter. Il effectue aussi le changement de contexte des processus. Il peut implanter un ordonnancement préemptif, non préemptif, ou coopératif. L\’ordonnanceur est activé par un événement : interruption du temporisateur, interruption d\’un périphérique, appel système ou signal.
III.2.2. Objectifs de l\’ordonnanceur d\’un système multiutilisateur
Les objectifs d\’un ordonnanceur d\’un système multiutilisateur sont, entre autres :
Assurer que chaque processus en attente d\’exécution reçoive sa part de temps processeur.
Minimiser le temps de réponse.
Utiliser le processeur à 100%.
Utilisation équilibrée des ressources.
Prendre en compte des priorités.
Être prédictibles.
Généralement l’objectif de l’ordonnanceur consiste à identifier le processus utilisé qui conduira al meilleur performance possible de système.
III.2.3. Critères d’ordonnancement
L’objectif d’un algorithme d’ordonnancement consiste à identifier le processus qui conduira à la meilleure performance possible du système [21]. Certes, il s’agit là d’une évaluation subjective dans laquelle entrent en compte différents critères à l’importance relative variable. La politique d’ordonnancement détermine l’importance de chaque critère. Un certain nombre d’algorithmes ont fait leur preuve dans la mise en œuvre d’une politique d’ordonnancement.
La liste qui suit passe en revue des critères d’ordonnancement fréquemment utilisés.
Utilisation de l’UC : Pourcentage de temps pendant lequel l’UC exécute un processus. L’importance de ce critère varie généralement en fonction du degré de partage du système.
Utilisation répartie : Pourcentage du temps pendant lequel est utilisé l’ensemble des ressources (outre l’UC, mémoire, périphérique d’E/S…)
Débit : Nombre de processus pouvant être exécutés par le système sur une période de temps donnée.
Temps de rotation : durée moyenne qu’il faut pour qu’un processus s’exécute. Le temps de rotation d’un processus comprend tout le temps que celui-ci passe dans le système. Il est inversement proportionnel au débit.
Temps d’attente : durée moyenne qu’un processus passe à attendre. Mesurer la performance par le temps de rotation présente un inconvénient : Le temps de production du processus accroît le temps de rotation ; Le temps d’attente représente donc une mesure plus précise de la performance.
Temps de réponse : Temps moyen qu’il faut au système pour commencer à répondre aux entrées de l’utilisateur.
Equité : degré auquel tous les processus reçoivent une chance égale de s’exécuter.
Priorités : attribue un traitement préférentiel aux processus dont le niveau de priorité est supérieur.

III.2.4. Ordonnancement coopératif
Ordonnancement coopératif ou bien ordonnanceurs non préemptifs ou sans réquisition [20] c’est un ordonnancement jusqu’à achèvement : le processus élu garde le contrôle jusqu’à épuisement du temps qui lui a été alloué même si des processus plus prioritaires ont atteint la liste des Prêts.
III.2.4.1. L’algorithme FIFO (First In First Out)
On l’appel aussi le Premier Arrivé est le Premier Servi PAPS (ou First-Come First-Served FCFS). L\’ordonnancement est fait dans l\’ordre d\’arrivée en gérant une file unique des processus sans priorité ni réquisition : chaque processus s’exécute jusqu’à son terme ; le processus élu est celui qui est en tête de liste des Prêts : le premier arrivé. Cet algorithme est facile implanter, mais il est loin d\’optimiser le temps de traitement moyen.
Exemple :
Considérons cinq travaux A, B, C, D et E, dont les temps d\’exécution et leurs arrivages respectifs sont donnés dans le tableau suivant :

Tableau 1 : Exemple des données d’ordonnancement
Processus Temps d’exécution Temps d’arrivage
A 3 0
B 6 1
C 4 4
D 2 6
E 1 7

L’évolution de l’utilisation du processus au cours du temps peut être présentée par un digramme de Gantt comme suit :

Figure 2 : Représentation par diagramme de Gantt l’algorithme FIFO

Au temps 0, seulement le processus A est dans le système et il s\’exécute. Au temps 1 le processus B arrive mais il doit attendre qu\’A termine car il a encore 2 unités de temps. Ensuite B s\’exécute pendant 4 unités de temps. Au temps 4, 6, et 7 les processus C, D et E arrivent mais B a encore 2 unités de temps. Une fois que B a terminé, C, D et E entrent au système dans l\’ordre.
Le temps d’exécution pour chaque processus est obtenu soustrayant le temps d\’entrée du processus du temps de terminaison.
Le temps d\’attente est calculé soustrayant le temps d\’exécution du temps de séjour :

Tableau 2 : Temps de séjour et temps d’attente des processus pour l’algorithme FIFO
Processus Temps de séjour Temps d\’attente

A 3-0 = 3 3-3 = 0
B 9-1 = 8 8-6 = 2
C 13-4 = 9 9-4 = 5
D 15-6 = 9 9-2 = 7
E 16-7 = 9 9-1 = 8

Le temps moyen d’exécution est (3+8+9+9+9)/5=7.6
Le temps moyen d\’attente est (0+2+5+7+8)/5=4.4
III.2.4.2. L’algorithme SJF (Shortest Job First)
L\’ordonnancement par ordre inverse du temps d\’exécution (supposé connu à l’avance) : lorsque plusieurs travaux d\’égale importance se trouvent dans une file, l\’Ordonnanceur élit le plus court d\’abord (les travaux les plus cours étant en tête de la file des prêts).
Remarque :
Les ordonnanceurs non préemptifs ne sont pas intéressants pour les systèmes multiutilisateurs car les temps de réponse ne sont pas toujours acceptables.
Exemple :
Considérons le même exemple pour les processus A, B, C, D, E ; le diagramme de Gantt correspond a cet algorithme est comme ceci :

Figure 3 : Représentation par diagramme de Gantt l’algorithme SJF

Donc pour la stratégie SJF nous aurons la séquence d’exécution A, B, E, D, C
Le temps de séjour et le temps d’attente sa sera :
Tableau 3 : Temps de séjour et temps d’attente des processus pour l’algorithme SJF
Processus Temps de séjour Temps d\’attente

A 3-0 = 3 3-3 = 0
B 9-1 = 8 8-6 = 2
E 10-7 = 3 3-1 = 2
D 12-6 = 9 6-2 = 4
C 16-4 = 12 12-4 = 8

Le temps moyen d’exécution est (3+8+3+9+12)/5=6.4
Le temps moyen d\’attente est (0+2+2+4+8)/5=3.4
III.2.5. Ordonnancement préemptif ou avec réquisition
L\’Ordonnancement préemptif ou avec réquisition [20] c\’est un ordonnanceur distribue le temps du processeur entre les différents processus. Dans un système préemptif, à l\’inverse d\’un système collaboratif, l\’ordonnanceur peut interrompre à tout moment une tâche en cours d\’exécution pour permettre à une autre tâche de s\’exécuter.
Dans un système d\’exploitation multitâche préemptif, les processus ne sont pas autorisés à prendre un temps non défini pour s\’exécuter dans le processeur. Une quantité de temps définie est attribuée à chaque processus ; si la tâche n\’est pas accomplie avant la limite fixée, le processus est renvoyé dans la pile pour laisser place au processus suivant dans la file d\’attente, qui est alors exécuté par le processeur. Ce droit de préemption peut tout aussi bien survenir avec des interruptions matérielles. Le temps d\’allocation du processeur au processus est appelé quantum. Cette commutation entre processus doit être rapide, c\’est-à-dire, exiger un temps nettement inférieur au quantum.
Le processeur, à un instant donné, n\’exécute réellement qu\’un seul processus, mais pendant une seconde, le processeur peut exécuter plusieurs processus et donne ainsi l\’impression de parallélisme (pseudo-parallélisme).
Problèmes :
Choix de la valeur du quantum.
Choix du prochain processus à exécuter dans chacune des situations suivantes :
Le processus en cours se bloque (passe à l\’état Attente).
Le processus en cours passe à l\’état Prêt (_n du quantum…).
Un processus passe de l\’état Attente à l\’état Prêt (_n d\’une E/S).
Le processus en cours se termine.
III.2.5.1. L’algorithme du temps restant le plus court (SRT : Shortest Remaining Time)
L’algorithme du temps restant le plus court, est la version préemptive de l’algorithme SJF. Chaque fois qu’un nouveau processus est introduit dans la file des processus à ordonnancer, l’Ordonnanceur compare la valeur estimée du temps de traitement restant à celle du processus en cours d’ordonnancement. Si le temps de traitement du nouveau processus est inférieur, le processus en cours d’ordonnancement est préempte. Tout comme l’algorithme SJF, l’algorithme SRT favorise les travaux courts : les travaux longs en revanche peuvent être victimes de famine.
Exemple : Considérons deux processus A et B telle que :

Tableau 4 : Exemple des données d’ordonnancement.
Processus Temps d’exécution Temps d’arrivage
A 15 0
B 4 2

Le diagramme de Gantt correspond a cet algorithme est comme ceci :

Figure 4 : Représentation par diagramme de Gantt l’algorithme SRT.

Tableau 5 : Temps de séjour et temps d’attente des processus pour l’algorithme SRT
Processus Temps de séjour Temps d\’attente

A 21-0 = 21 21-15 = 6
B 8-2 = 6 6-6=0

Le temps moyen d’exécution est (21+6)/2=3.5
Le temps moyen d\’attente est (6+0)/2=3
III.2.5.2. L’algorithme Round Robin

C B A

Processus suspendu
Figure 5 : ordonnancement circulaire [20]

Il s\’agit d\’un algorithme ancien, simple et fiable. Le processeur gère une liste circulaire de processus. Chaque processus dispose d\’un quantum de temps pendant lequel il est autorisé à s\’exécuter. Si le processus actif se bloque ou s\’achève avant la fin de son quantum, le processeur est immédiatement alloué à un autre processus. Si le quantum s\’achève avant la fin du processus, le processeur est alloué au processus suivant dans la liste et le processus précédent se trouve ainsi en queue de liste. La commutation de processus (overhead) dure un temps non nul pour la mise à jour des tables, la sauvegarde des registres. Un quantum trop petit provoque trop de commutations de processus et abaisse l\’efficacité du processeur. Un quantum trop grand augmente le temps de réponse en mode interactif. On utilise souvent un quantum de l\’ordre de 100 ms.
Exemple :
Nous considérons même exemple avec les processus A et B avec un quantum du temps Q=3 ms, alors le résultat avec diagramme de Gantt est comme ceci :

Figure 6 : Représentation par diagramme de Gantt l’algorithme RR.

Tableau 6 : Temps de séjour et temps d’attente des processus pour l’algorithme RR.
Processus Temps de séjour Temps d\’attente

A 21-0 = 21 21-15 = 6
B 12-2 = 10 10-6= 4

Le temps moyen d’exécution est (21+10)/2=15.5
Le temps moyen d\’attente est (6+4)/2=5
II.2.5.3. L’algorithme HPF (Highest Priority First)
Exemple :
Nous considérons les 5 cinq processus A, B, C, D, E avec le temps et la priorité d\’exécution qui ont montré dans le tableau suivant :

Tableau 7 : Exemple des données d’ordonnancement
Processus Temps d’exécution Priorité
A 10 3
B 1 1
C 2 4
D 1 5
E 5 2

Le résultat avec diagramme de Gantt est comme ceci :

Figure 7 : Représentation par diagramme de Gantt l’algorithme HPF

Tableau 8 : Temps d’attente des processus pour l’algorithme HPF.
Processus Temps d\’attente

B 0
E 1
A 6
C 16
D 18

Le temps moyen d\’attente est (0+1+6+16+18)/5=8.2
III.2.6. Résumé

Avantages
Inconvenient

Ordonnancement coopératif ou sans réquisition
First In First Out (FIFO)19 Facile à comprendre et à programmer.
Intrinsèquement équitable pour des processus équivalents.
OK pour les systèmes de batch. Grande variance des critères d’ordonnancement
Effet d’accumulation.
– Mauvais algorithme pour les systèmes en temps partagé.
– Le temps d\’attente moyen est souvent assez long.
– Petit processus attend un grand processus

L’algorithme Shortest Job First (SJF)19
Temps moyen d’attente minimal.
OK pour les systèmes de batch.
On favorise les processus courts ce qui augmente le débit de processus traités et donc la réactivité. Difficulté de calculer la longueur des cycles.
– Implémentation difficile, car il n’existe aucune manière pour connaître le cycle suivant du processeur.
– Risques de famine (un processus trop long pourrait ne jamais être exécuté s\’il y a toujours un plus court).

Ordonnancement préemptif ou avec réquisition L’algorithme Shortest Remaining Time (SRT )
Adapté aux systèmes temps partagé.
C’est une variante de l’algorithme SJF. Cet algorithme est non implantable parce qu’il suppose, entre autres, connu le temps d’exécution réel de chaque processus pour pouvoir calculer le temps restant.
L’algorithme Round Robin (RR) Adapté aux systèmes temps partagé.
Eviter la famine.
– Simple et facile à implémenter.
– Chaque processus a la même chance d\’exécution
– Gestion de tous les processus sans priorité
Sans famine. Dépend de la longueur de la tranche de temps même FCFS, si la tranche de temps est infiniment grande
– La fréquente commutation de contexte.

Algorithme avec ou sans réquisition L’algorithme Highest Priority First (HPF)
Facile à utiliser, convivial .
Vieillissement ; à mesure que le temps augmente, la priorité du processus augmente.
Adapté à une application avec des exigences de temps et de ressources variables. Un processus de priorité basse risque de ne pas être servi (problème de famine).
Si le système tombe en panne, tous les processus de faible priorité sont perdus.
Blocage indéfinie ou famine

III.3. Ordonnancements en temps réel
L’ordonnancement temps réel pour les architectures multiprocesseurs a connu un regain d’intérêt ces dix dernières années qui se sont traduit par un très grand nombre de publications scientifiques. Sur vingt ans, plus de cinquante politiques d’ordonnancement ont été proposées et ont été accompagnées de nombreuses études sur leurs propriétés. Depuis la synthèse de Davis et Burns (2011) [22], une dizaine de nouveaux algorithmes ont été développés. La grande profusion de publications rend difficile une vue synthétique dans ce domaine.
Pour des raisons de place, les politiques exposées se limitent au cas d’architectures à processeurs identiques, un lecteur intéressé par la prise en compte d’autres types d’architecture peut consulter les publications de Funk (2004) et plus récemment de Yang et Anderson (2014). De même, les politiques d’ordonnancement dites partitionnées sont rapidement abordées. Ce sujet ayant peu évolué depuis quelques années, un lecteur souhaitant approfondir ce point peut consulter l’article de Davis et Burns (2011).
Les systèmes temps réel en informatique sont conçues pour fournir des résultats dans un cadre du temps spécifique et le système doit délivrer des résultats exactes et dans des délais imposes. Donc il doit avoir des contraintes du temps fixe et des réponses bien définies et le traitement doit être fait dans les limites contraintes si non le système échouera.
III.3.1. Critères de classification
Instant ou l’ordre d’exécution est décidé : hors-ligne / enligne
Ordonnancements « enligne »
Les décisions d’ordonnancement sont prises au cours de l’exécution.
A l’exécution, l’ordonnanceur implante un algorithme d’ordonnancement permettant de savoir à tout instant quel tâche exécuter : besoin d’un exécutif multitâche.
Généralement, ordonnancements conduits par la priorité.
Ordonnancements « hors-ligne »
Un ordonnancement hors ligne est pré-calculé avant exécution puis est exécuté avec ou sans préemption.
A contraintes strictes ou souples
Respect des contraintes garanties à 100% ou tolérance.
Statiques ou dynamiques
Ordonnancement fixe ou réévaluation en ligne.

Possibilité d’interruption d’une tâche par une autre : préemptif / non préemptif
Un ordonnanceur préemptif peut interrompre une tâche au profit d\’une tâche plus prioritaire.
Un ordonnanceur non préemptif n\’arrête pas l\’exécution de la tâche courante.
Tâches dépendantes ou indépendantes
Les tâches indépendantes ne partagent que le processeur
Les tâches dépendantes partagent d\’autres ressources ou sont reliées par des contraintes de précédence
Optimalité : quel est le « meilleur » ordonnancement optimal
Algorithme qui produit un ordonnancement pour tout ensemble de tâches ordonnançables (si un algorithme le fait, lui le fait aussi)

Figure 8 :Types d’ordonnancement
III.3.2. Les types de tâches temps-réel [23] Les tâches périodiques : – activation à intervalles réguliers,
A échéances sur requêtes si Di = Ti (ex : Relevé de température)
Les tâches apériodiques/sporadiques : activation à des instants irréguliers, intervalle de temps entre deux activations borné (sporadiques) ou non (apériodiques), à contraintes relatives (ex : Requête sur une borne de service), à contraintes strictes (ex : Arrêt d’urgence).
Notations
ri : date de réveil moment du déclenchement de la 1ere requête d\’exécution
Ti : période d’exécution
Ci : durée d’exécution maximale (capacité)
Di : délai critique: délai maximum acceptable pour son exécution
di = ri + Di : date d’échéances (si tache a contraintes strictes)
L = Di – Ci : laxité

Figure 9 :Les modèles canonique des taches temps réel ti (Ci, Ti, Di).

III.3.3. Ordonnancement à priorités fixes (statiques)
III.3.3.1. Rate Monotonic (RM)
L\’ordonnancement à taux monotone (en anglais, rate-monotonic scheduling [24]) a été introduit par Liu & Layland en 1973. C’est un algorithme d\’ordonnancement temps réel en ligne à priorité constante (statique)., consiste a attribué des priorités élevé aux taches de fréquences plus élevé c\’est-à-dire à la tâche qui possède la plus petite période et de priorité faible aux taches de fréquences faible et bien sur l’ordonnanceur choisit d’exécuter les taches des priorités élevé en spécifiant la période et le temps de calcul requis par la tache.
RMS est optimal dans le cadre d\’un système de tâches périodiques, synchrones, indépendantes et à échéance sur requête avec un ordonnanceur préemptif. De ce fait, il n\’est généralement utilisé que pour ordonnancer des tâches vérifiant ces propriétés.
Exemple :

Figure10 : Représentation graphique d’ exemple d’algorithme d’ordonnancement RM

Propriété: RM est optimal dans la classe des algorithmes à priorités fixes pour des tâches périodiques indépendantes à échéances sur requêtes (Di=Ti)
Condition de faisabilité:
Condition nécessaire : U=∑_(i=1)^n▒Ci/Ti ≤1
Condition suffisante : U=∑_(i=1)^n▒Ci/Ti ≤n(2^(1⁄n)-1)
III.3.3.2. Deadline Monotonic (DM)
L’ordonnancement « Deadline Monotone » [25] est une politique d\’attribution de priorité utilisée avec l\’ ordonnancement préemptif à priorité fixe .
Avec une affectation prioritaire monotone , les tâches se voient attribuer des priorités en fonction de leurs délais . La tâche avec le délai le plus court se voit attribuer la priorité la plus élevée.
L\’attribution de priorité monotone à l\’échéance n\’est pas optimale pour la planification non préemptive à priorité fixe.
Une politique d\’affectation de priorité fixe P est considérée comme optimale si aucun ensemble de tâches ne peut être planifié en utilisant une politique d\’attribution de priorité différente qui n\’est pas également programmable en utilisant la politique d\’attribution de priorité P.
Exemple :

Figure 11 : Représentation graphique d’ exemple d’algorithme d’ordonnancement DM
Propriété: DM est optimal dans la classe des algorithmes à priorités fixes pour des tâches périodiques indépendantes à échéances sur requêtes (Di ≤ Ti).
Condition de faisabilité:
Condition nécessaire : U=∑_(i=1)^n▒Ci/Ti ≤1
Condition suffisante : U=∑_(i=1)^n▒Ci/Di ≤n(2^(1⁄n)-1)
Ordonnancement à priorités fixes (statiques)
Intérêts :
Mécanisme simple
S’implante naturellement dans les OS du marché
Inconvénients :
Hypothèses restrictives
Indépendance des tâches impérative pour l’utilisation des conditions de faisabilité
Borne supérieure pour le facteur d’utilisation du processeur.
RM pénalise les tâches rares mais urgentes (grande périodicité = petite priorité).
DM sera meilleur pour les tâches dont l\’échéance est très inférieure à la période.
III.3.4. Ordonnancement à priorités dynamiques
III.3.4.1. Earliest Deadline First (EDF)
C’est un algorithme d\’ordonnancement préemptif, à priorité dynamique, utilisé dans les systèmes temps réel. Il attribue une priorité à chaque requête en fonction de l\’échéance de cette dernière selon la règle: Plus l\’échéance (\”échéance proche = préparation en premier\”) d\’une tâche est proche, plus sa priorité est grande. De cette manière, au plus vite le travail doit être réalisé, au plus il a de chances d\’être exécuté.[26] Exemple :
Figure 12 : Représentation graphique d’ exemple d’algorithme d’ordonnancement EDF
Propriété: EDF est optimal dans la classe des algorithmes à priorités dynamiques pour des tâches périodiques indépendantes à échéances sur requêtes (Di ≤ Ti).
Condition de faisabilité:
Si Di =Ti
Condition nécessaire et suffisante: U=∑_(i=1)^n▒Ci/Ti ≤1
Si Di ≤ Ti
Condition suffisante : U=∑_(i=1)^n▒Ci/Di ≤1
III.3.4.2. Least Laxity First
Appelé aussi Least Slack Time (LST) base. C’est un algorithme basé sur des priorités dynamiques. La priorité d’une tâche est inversement proportionnelle à sa laxité dynamique. Autrement dit la tâche de plus haute priorité à l’instant t dispose de la plus petite laxité, et à chaque instant, la tâche la plus prioritaire est celle dont la laxité L(t) = D(t) – C(t)
est la plus petite.[27] Exemple:

Figure 13 : Représentation graphique d’ exemple d’algorithme d’ordonnancement LLF
Propriété : LLF est optimal dans la classe des algorithmes préemptifs pour des tâches périodiques indépendantes telles que Di ≤ Ti

Condition de faisabilité:
Si Di =Ti
Condition nécessaire et suffisante: U=∑_(i=1)^n▒Ci/Ti ≤1
Si Di ≤ Ti
Condition suffisante : U=∑_(i=1)^n▒Ci/Di ≤1
L’ordonnancement à priorités dynamiques
Intérêts :
Simplicité de mise en œuvre
Optimisation de l’usage des ressources
Bien adapté aux tâches périodiques à courtes échéances
Inconvénients :
Indépendance des tâches impératives pour l’utilisation des conditions de faisabilité
Instabilité en cas de surcharge (EDF)
Nombreux changements de contexte dans certains cas (LLF)
Difficilement implantable dans les OS actuels
III.5. Résumé
Avantages
Inconvenient

Priorité fixe /Statique

Rate Monotonic Scheduling (RMS)
Simple à comprendre (et à retenir!).
Facile à mettre en œuvre (attribution de priorité statique / fixe).
Stable: bien que certaines tâches moins prioritaires ne respectent pas les délais, d\’autres peuvent respecter les délais. Utilisation du processeur \”inférieure\”.
Ne traiter que des tâches indépendantes.
Analyse d\’ordonnancement non précise.
Mais ce ne sont pas vraiment des inconvénients, ils peuvent être corrigés (+++) Nous pouvons résoudre tous ces problèmes sauf une utilisation \”inférieure\”.

Deadline Monotonic Scheduling (DMS) Identiques à RMS. pénalise les tâches à périodes longues mais urgentes (à échéance courte). DMS est meilleur dans ce cas là
Identiques à RMS.

Priorité dynamique

Earliest Deadline First Scheduling (EDFS)
Cela fonctionne pour tous les types de tâches: périodique ou non périodique.
C\’est simple et fonctionne bien en théorie.
Test de programmabilité simple: U <= 1.
Optimal.
Meilleure utilisation du processeur. Difficile à mettre en œuvre dans la pratique.
Il n’est pas très souvent adopté en raison de l’attribution dynamique des priorités (coûteux à trier la file d’attente en ligne), ce qui n’a rien à voir avec les périodes de tâches.
Notez que toute tâche peut avoir la plus haute priorité.
Non stable: si une instance de tâche ne parvient pas à respecter son échéance, le système n\’est pas prévisible, toute instance d\’une tâche peut échouer.

Least Laxity First Scheduling(LLFS)
Meilleur qu’EDF dans le cas de si le temps d’exécution est connu. Meilleur qu’EDF dans le cas de si le temps d’exécution est connu.
Conclusion
Dans ce chapitre, nous avons élaboré un état de l’art concernant l’ordonnancement en générale, nous avons vu les différents algorithmes d’ordonnancement dans divers axes de recherches telle que l’ordonnancement des processus et en temps réel mais ainsi nous concentrerons sur la notion d’ordonnancement dans un contexte radio mobile.

Chapitre 2 :

Etude des techniques d’ordonnancement dans un contexte radio mobile

Introduction
L\’internet a connu une croissance remarquable ces dernières années. Cette croissance n\’a pas résumé aux réseaux fixes mais a gagné récemment les réseaux mobiles. Les réseaux sans fil, initialement conçus pour transférer exclusivement des services voix, s\’adaptent progressivement à ces changements pour transporter des services data. Avec un besoin grandissant pour accéder à ces nouveaux services, proposer des méthodes performantes pour gérer la ressource radio et fournir des garanties de performance aux services data mobiles est désormais d\’une importance capitale. Dans le domaine des réseaux fixes, augmenter la capacité revient à rajouter des câbles et des fibres optiques. Les communications mobiles, elles sont contraintes de se partager une ressource naturelle restreinte, fluctuante à cause des évanouissements du canal radio et entachée d\’erreurs. Des efforts significatifs ont été déployés pour augmenter l\’efficacité du spectre mobile faisant ainsi face aux caractéristiques uniques du canal mobile et à une demande croissante pour un accès haut débit à l\’Internet mobile.
Elaborer des mécanismes efficaces de gestion d\’une ressource radio rare et variable est loin d\’être évident. Cependant, plusieurs méthodes ont été proposées dans la littérature et ont fait preuve dans la pratique de leur efficacité, à savoir, les politiques d\’ordonnancement, le contrôle d\’admission, la gestion d\’interférence, la détection multiutilisateurs, l\’utilisation d\’antennes dites intelligentes, le codage du canal, le contrôle de puissance, les algorithmes d\’adaptation etc. Notre travail s\’est concentré sur les techniques d\’ordonnancement.
Dans ce chapitre, nous nous intéressons à l\’allocation de ressources radio autrement appelée scheduling ou ordonnancement dans un système radio mobile. Il est considéré comme l’une des fonctions essentielles de ce dernier et forme une fonctionnalité clé de l’interface radio pour ses performances et pour le maintien de la qualité de service envers l’utilisateur. Donc nous allons nous chercher à comprendre les contraintes et les besoins des systèmes radio mobile et ainsi nous allons voir les différentes techniques d’ordonnancement.
Model du système et énonce le problème
I.1. Système radio mobile
Le réseau radio mobile est aujourd\’hui un domaine en pleine effervescence. Pendant la dernière décennie, les évolutions des télécommunications ont donné naissance à une nouvelle gamme de services qui dépasse les services classiques afin de satisfaire l’accroissement du nombre des utilisateurs et les exigences des taux de données élevés.
Les systèmes radiofréquences sans fil permettent l\’identification sans contact, transmettent des flux numériques à hauts débits en temps réel (UMTS, 4G-5G, Wifi), relient de très longues distances (troposphère, satellites) etc.
Comprendre les propriétés et les mécanismes de propagation des ondes radioélectriques dans l\’environnement de ces systèmes est nécessaire à leur connaissance générale et à leur mise en œuvre appropriée.
Une onde radioélectrique, communément abrégé en onde radio, est une onde électromagnétique dont la fréquence est inférieure à 300 GHz, soit une longueur d\’onde dans le vide supérieure à 1 millimètre.
Le domaine des radiocommunications est réglementé par l\’Union internationale des télécommunications (UIT ) qui a établi un règlement des radiocommunications dans lequel on peut lire la définition suivante :
Les ondes radioélectriques ou ondes hertziennes : « ondes électromagnétiques dont la fréquence est par convention inférieure à 300 GHz, se propageant dans l\’espace sans guide artificiel », elles sont comprises entre 9 kHz et 300 GHz qui correspond à des longueurs d\’onde 33 km à 1 mm1. Les ondes de fréquence inférieure à 9 kHz sont des ondes radio, mais ne sont pas réglementées.
Les ondes de fréquence supérieure à 300 GHz sont classées dans les ondes infrarouges car la technologie associée à leur utilisation est actuellement de type optique et non électrique, cependant cette frontière est artificielle car il n\’y a pas de différence de nature entre les ondes radio, les ondes lumineuses et les autres ondes électromagnétiques (exemples : micro-onde, radar, etc.).
De nombreuses réglementations concernent le partage des fréquences pour différents usages, certains usages ou encore l\’exposition de travailleurs à certains champs électromagnétiques, dont via la réglementation européenne.
La norme sur les bandes de fréquences est décrite dans les règlements de la radio de l\’Union internationale des télécommunications, voir le tableau 9.
Tableau 9 : Spectre radiofréquence
Désignation international
Désignation francophone Fréquence
Longueur d’onde
ELF (Extremely Low Frequency) EBF (Extrêmement Basse Fréquence) 3Hz to 30Hz 100’000km to 10’000km
SLF (Super Low Frequency) SBF (Super basse Fréquence) 30Hz to 300Hz 10’000km to 1’000km
ULF (Ultra Low Frequency) UBF (Ultra Basse Fréquence) 300Hz to 3000Hz 1’000km to 100km
VLF (Very Low Frequency) TBF (Très Basse Fréquence) 3KHz to 30KHz 100km to 10km
LF (Low Frequency) BF (Basse Fréquence) 30KHz to 300KHz 10km to 1km
MF (Medium Frequency) MF (Moyenne Fréquence) 300KHz to 3000KHz 1km to 100m
HF (High Frequency) HF (Haute Fréquence) 3MHz to 30MHz 100m to 10m
VHF (Very High Frequency) THF (Tres Haute Fréquence) 30MHz to 300MHz 10m to 1m
UHF (Ultra High Frequency) UHF (Ultra Haute Fréquence) 300MHz to 3000MHz 1m to 10cm
SHF (Super High Frequency) SHF (Super Haute Fréquence) 3GHz to 30GHz 10cm to 1cm
EHF (Extremely High Frequency) EHF (Extrêmement Haute Fréquence) 30GHz to 300GHz 1cm to 1mm

Les réseaux sans fil ne remplacent pas les réseaux fixes. Le principal avantage de la mobilité est que l\’utilisateur du réseau se déplace. Les serveurs et un autre équipement de centre de données doivent accéder aux données, mais l\’emplacement physique du serveur est sans importance. Tant que le serveur ne bouge pas, ils peuvent aussi être connectés à des fils qui ne bougent pas [5].
La vitesse des réseaux sans fil est limitée par la bande passante disponible. À moins que les autorités de réglementation ne soient disposées à agrandir les bandes de fréquences sans licence, la vitesse des réseaux sans fil est limitée.
L\’utilisation d\’ondes radio comme support réseau pose plusieurs problèmes. Les spécifications des réseaux câblés sont conçues de manière à ce qu\’un réseau fonctionne tant qu\’il respecte les spécifications. Les ondes radio peuvent présenter un certain nombre de problèmes de propagation susceptibles d\’interrompre la liaison radio, tels que les interférences par trajets multiples et les ombres.

I.2. Caractérisation des canaux
Les communications sans fil se font par la transmission d\’ondes électromagnétiques entre un émetteur et un récepteur. La propagation de ces ondes radio dans un milieu est faire face à plusieurs perturbations extérieurs (présence d\’obstacles, de réflexions, etc.) et une plainte de phénomène et généralement décomposer en plusieurs éléments :
L\’affaiblissement du signal, à la distance entre l\’émetteur et le récepteur.
Les effets de masque, dus à la présence d\’obstacles sur le chemin de transmission.
L\’évanouissement (fading), du aux multiples réceptions du signal émis, dont les phases se superposent de façon constructives ou destructives.

Le spectre radioélectrique représente l’ensemble des fréquences radios utilisées pour la transmission de données sans fil, ils subissent des détériorations dues aux phénomènes de propagation. Pour ce la, une utilisation efficace du canal de transmission passe par le choix et la mise en œuvre d\’un certain nombre de techniques de modulation, de codage et d\’accès multiple, et par le dimensionnement des canaux qui supportent les communications et la spécification des bandes utilisées, des débits binaires, des puissances émises et des procédures d\’accès et de transmission. Ajouter à cela, les fréquences est une ressource rare.[6] Au niveau physique, la bande passante est divisée en « canaux » cette répartition se fait soit de manière fréquentielle, temporelle ou par code. Les canaux physiques sont ensuite partagés entre les communications au moyen d\’un protocole d\’accès. Dans la littérature, plusieurs protocoles d\’accès au canal ont été proposés. Ils sont généralement classifiés en quatre grandes catégories : accès aléatoire, technique d\’allocation fixe ou statique, accès à la demande et techniques hybrides.
De point de vue politique d\’accès multiple, il existe deux types de canaux dans les réseaux mobiles [5]:
le canal du lien descendant (de la station de base vers le mobile).
le canal du lien montant (du mobile vers la station de base).
Dés lors que la station de base possède le contrôle total des canaux descendants, le problème est moins critique que pour le cas du sens montant.
La conception, l\’évaluation et l\’installation efficaces d\’un réseau radio nécessitent une caractérisation précise du canal. Les caractéristiques des canaux varient d\’un environnement à l\’autre et les caractéristiques particulières déterminent la possibilité d\’utiliser une technique de communication proposée dans un environnement d\’exploitation donné. Une caractérisation précise du canal pour chaque bande de fréquence et un modèle mathématique détaillé du canal permettent au concepteur ou à l\’utilisateur d\’un système sans fil de prédire la couverture du signal, le débit de données réalisable et les performances spécifiques des schémas de signalisation et de réception.
Pour les applications de radio mobile, le canal varie en fonction du temps car le mouvement entre l\’émetteur et le récepteur entraîne des changements de chemin de propagation. Il convient de noter que, puisque les caractéristiques du canal dépendent de la position relative de l\’émetteur et du récepteur, la variance temporelle est équivalente à la variance spatiale. La variation temporelle du canal est caractérisée par le spectre de puissance Doppler .
Pour tout système radio mobile, il faut définir une technique d’accès qui permet une gestion des ressources radio disponibles afin d\’assurer une transmission de données à haute vitesse avec mobilité pour la communication mobile. La technologie d\’accès radio choisie est L’OFDMA [7] (ou orthogonal frequency-division multiple access) est une technique de multiplexage et de codage des données utilisée principalement dans les réseaux de téléphonie mobile de 4éme génération.
Ce codage radio associe les multiplexages en fréquence et temporel ; c\’est-à-dire les modes « accès multiple par répartition en fréquence » (AMRF ou en anglais FDMA) et « accès multiple à répartition dans le temps » (AMRT ou en anglais TDMA), en raison du haut degré de flexibilité dans l\’allocation des ressources radio aux équipements utilisateurs (UE) et de sa robustesse à la sélectivité des canaux multi-trajets.

Figure 14: Les techniques d\’accès multiples[7] Le succès des technologies de type 3G et 4G qui permet aux utilisateurs d’avoir accès à un réseau internet mobile, a conduit à un élargissement des réseaux de télécommunication. Ces réseaux ont favorisé l’intégration des services innovants et ont offert un débit approprié, permettant aux opérateurs de répondre à des besoins spécifiques.

I.3. Problématique
Deux aspects fondamentaux de la communication sans fil rendent le problème difficile et intéressant. Ces aspects ne sont pas généralement aussi importants dans la communication filaire :
Le premier est le phénomène d\’évanouissement: la variation temporelle des forces du canal due à l\’effet à petite échelle des évanouissements par trajets multiples, ainsi que des effets à plus grande échelle tels que l\’affaiblissement du chemin via l\’atténuation des distances et les obstacles.
Deuxièmement, contrairement au monde câblé où chaque paire émetteur-récepteur peut souvent être considérée comme une liaison point à point isolée, les utilisateurs sans fil communiquent par voie hertzienne et les communications sans fil présentent des interférences importantes. L\’interférence peut être entre des émetteurs communiquant avec un récepteur commun (par exemple, une liaison montante d\’un système cellulaire), entre des signaux provenant d\’un seul émetteur vers plusieurs récepteurs (par exemple, liaison descendante d\’un système cellulaire) ou entre différents couples émetteurs-récepteurs dans différentes cellules). La gestion des évanouissements et des interférences est essentielle pour la conception des systèmes de communication sans fil.
Dans chaque réseau auquel plusieurs utilisateurs accèdent simultanément, il est nécessaire de coordonner la transmission pour éviter les collisions. Donc le canal commun doit être partagé par plusieurs utilisateurs et il est souhaitable de trouver une solution efficace pour partager le canal couramment utilisé. Un exemple très simple pour éviter le problème des collisions consiste à attribuer à chaque utilisateur son propre canal. Cependant, normalement, cette solution est loin d\’être optimale et il n\’est généralement pas possible de la mettre en œuvre en raison de limitations techniques. Nous avons donc besoin d\’approches plus sophistiquées pour répartir les ressources partagées entre les utilisateurs.
L\’utilisation simultanée de plusieurs interfaces radio sur ces terminaux semble attractive et intéressante. En effet, elle permettrait d’augmenter les débits pour l’utilisateur grâce à l’utilisation parallèle de plusieurs canaux radio. Elle permettrait également une mobilité verticale (i.e. mobilité entre réseaux d’accès hétérogènes) sans couture en garantissant la continuité des flux et donc des sessions.
Cependant, l’exploitation de plusieurs interfaces radio se heurte à différentes problématiques et nécessite de revoir un certain nombre de procédures réseau dont l’ordonnancement des paquets sur les différentes interfaces et le routage multi-chemin de ces paquets qui peuvent traverser des réseaux et domaines différents avec des paramètres de QoS disparates.
De manière générale, l’utilisation simultanée de plusieurs interfaces nécessite des solutions nouvelles au niveau des différentes couches protocolaires aussi bien sur le plan de donnée que sur le plan de contrôle.
Nous proposons par la suite une solution pour résoudre ces problèmes.
L’ordonnancement dans un contexte radio mobile
II.1. Principe
La transmission en système radio mobile repose sur des canaux partagés dont l’accès est géré d’une façon dynamique en fonction des paramètres de qualité de service (QoS) et celle du canal perçue par l’UE. L’accès au canal est déterminé par le scheduler en fonction des décisions suivantes :
• Quels sont les l\’équipements terminaux UE qui peuvent être servis à chaque TTI ?
• Quel est le nombre ainsi que la position des ressources en temps/fréquence qui doivent être allouées à chaque utilisateurs servi ?

Figure 15: Modèle simplifié d\’un ordonnancement des paquets [40]

La figure 15 présente le fonctionnement d’ordonnancement des paquets en liaison descendante. En général, l\’ensemble du processus peuvent être divisé en une séquence d\’opérations répétées chaque intervalle du temps TTI:
En premier lieu l\’eNodeB ,placé au niveau la station du base SB, est l\’entité responsable de la planification des utilisateurs actifs actuels, envoi des signalisations de control vers le canal PDCCH (Physical Downlink Control Channel) qui va les transmettre par la suite vers le (s)l\’équipement(s) terminaux UEs ( User Equipement).
Chaque UE actif décode les signaux de référence, calcule le SNR ( Signal Noise Ratio) et le CQI (Channel Quality Indicator) et le renvoie à l\’eNB.
Sur la base des informations CQI et des contraintes de qualité de service, l\’eNodeB attribue les ressources radio disponibles aux UE actifs.
Le module AMC (Adaptive Modulation and Coding) choisit les meilleurs schémas de modulation (c\’est-à-dire QPSK, 16-QAM ou 64-QAM) selon la valeur de CQI (voir tableur 10) pour la transmission de données vers des UE programmés.
Les informations sur ces utilisateurs, les RB attribués et le meilleur MCS (Modulation and Coding Scheme) sélectionné sont envoyés aux UE via le canal PDCCH.
Chaque UE lit la charge utile PDCCH et, au cas où elle est programmée, accède à la charge utile PDSCH appropriée.
Tableau 10 : Indicateur de qualité de canal CQI

Indice de CQI
Modulation
Code du taux (*1024)
Efficacité
0 Pas de transmission
1 QPSK 78 0.1523
2 QPSK 120 0.2344
3 QPSK 193 0.3770
4 QPSK 308 0.6016
5 QPSK 449 0.8770
6 QPSK 602 1.1758
7 16QAM 378 1.4766
8 16QAM 490 1.9141
9 16QAM 616 2.4063
10 64QAM 466 2.7305
11 64QAM 567 3.3223
12 64QAM 666 3.9023
13 64QAM 772 4.5234
14 64QAM 873 5.1152
15 64QAM 948 5.5547

II.2. Buffer
Buffer est un mot anglais se traduisant généralement par tampon.[9] En électronique, un buffer est un montage spécifique destiné à amplifier le courant de sortie d\’un circuit, permettant de raccorder plus d\’utilisateurs sur la sortie de ce circuit.
En informatique, buffer est le terme anglais équivalent à mémoire tampon, une zone de mémoire virtuelle ou de disque dur utilisée pour stocker temporairement des données, notamment entre deux processus ou deux pièces d\’équipement ne fonctionnant pas à la même vitesse. Par exemple une vidéo de Youtube est stockée temporairement dans le buffer, et ensuite le navigateur lit cette vidéo. Une fois la vidéo terminée, cette partie du buffer allouée est vidée.
Une autre approche est de partir avec un ordonnancement déterministe de durée minimale et d’y ajouter des tampons de temps. Les durées des activités utilisées pour l’ordonnancement déterministe sont les durées moyennes. L’insertion de tampons de temps protège l’arrangement prévu des activités contre un retard dans l’exécution d’une activité. Cependant, cela augmente la durée totale du projet, c’est-à-dire que cela engendre une détérioration de la qualité de l’ordonnancement.
Les schémas d\’allocation de ressources conventionnels dans un système sans fil sont généralement basés sur la priorité de l\’utilisateur [10]. Ils sont conçus en fonction de l\’état des canaux de l\’utilisateur et de la garantie de qualité de service afin d\’optimiser le débit global du système. Toutefois, l’équité entre les utilisateurs est une autre considération de conception essentielle, même si elle sacrifie généralement le débit du système et / ou viole les exigences de qualité de service. Certains schémas d\’allocation de ressources basés sur la gestion des tampons peuvent améliorer certaines de ces mesures de performance. Le problème d\’allocation des ressources dans le système sans fil a été largement abordé dans certaines littératures, mais il est toujours difficile de concevoir un système d\’allocation des ressources prenant en compte les tampons afin d\’améliorer les performances, garantissant ainsi la qualité de service et obtenir l\’équité.
Dans le cadre de la planification des utilisateurs, en considérant que la taille maximale du tampon fini, la priorité de file d\’attente de chaque utilisateur est classée en fonction de sa durée de vie restante ou de sa probabilité de dépassement de file d\’attente estimée en appliquant le principe de grande déviation. En ce qui concerne l\’allocation de RBs, un algorithme basé sur la mesure en ligne pour l\’allocation dynamique de RB est proposé pour ajuster les taux de service des files d\’attente d\’utilisateurs afin de garantir la qualité de service. L\’objectif est d\’améliorer le débit total du système le plus grand possible tout en garantissant la qualité de service aux différents utilisateurs et en garantissant une certaine équité.
L’accès multiple par répartition orthogonale de la fréquence (OFDMA)[11] est devenue une technologie essentielle dans les communications sans fil à large bande. Des système tels que l’évolution à long terme 3 GPP (LTE), IEEE802.16d (WiMAX fixe), IEEE 802.16e (mobile WiMAX), LTE-Advanced et IEEE802.16m ont adopté l’OFDMA comme technique d’accès multiple pour les interfaces hertziennes en liaison descendante et liaison montante.
Dans la conception des systèmes d’accès sans fil mentionnés, les méthodes d’évaluation et les modèles jouent un rôle clé. Il existe des publications dans la littérature qui ont déjà indiqué que les résultats de performance des algorithmes ou des fonctions améliorant dans les systèmes OFDMA dépendent de manière significative du modèle de trafic considéré. A cet égard ; l’alliance des réseaux mobiles de prochaine génération ( Next Generation Mobile Networks NGMN) et l’Institut des ingénieurs électriciens et électroniques ( Institute of Electrical and Elenctronic Engineers IEEE) ont proposé des méthodologies d’évaluation pour le réseaux d’accès sans fil de prochaine génération. En outre, des modèles d’évaluation du projet de partenariat de troisième génération 3GPP peut être trouve, par exemple dans l’article [12] :
Modèle de tampon complet : il s’agit d’une version simplifiée de trafic reçu/transmis par un utilisateur dans une session de données. Elle se caractérise par deux faits : le nombre d’utilisateurs dans la cellule est constant et les tampons des flux des données des utilisateurs ont toujours une quantité illimitée de données à transmettre. Le modèle de tampon complet a été largement adopté dans l’OFDMA dans les enquêtes basées sur la simulation et théoriques en raison de sa simplicité
Modèle de tampon fini : il s’agit d’une version simplifiée du type de trafic interactif ou d’arrière-plan. Il comprend à la fois un processus d’arrivé de l’utilisateur (naissance) et un départ de l’utilisateur (décès). Avec ce modèle de trafic, un utilisateur reçoit une charge utile finie à transmettre ou à recevoir à son arrivée et il quitte le système une fois la transmission ou la réception de la charge utile termine. Le processus d’arrive des utilisateurs de ce modèle capture le fait que les utilisateurs du réseau ne sont pas actifs simultanément, mais deviennent actifs lorsqu’ils démarrent une session de données nécessitant le téléchargement de données. Ce modèle a été moins largement adopté.
II.3. Les critères de développement d’ordonnanceur
En effet, dans le cadre du contexte considérer dans ce rapport, plusieurs nouveaux critères peuvent être considère pour développer un ordonnanceur efficace tels que:
Le rapport Signal-Interférence-plus-bruit (SINR).
Les retards de paquets.
Équité.
Débit.
Le taux d’erreurs binaire (BER).
L’état de canal.
II.3.1. Le rapport Signal-Interférence-plus-bruit (SINR),
Le rapport signal sur bruit est un indicateur de la qualité de la transmission d\’une information. C\’est le rapport des puissances entre :
le signal d\’amplitude maximale pour laquelle la distorsion à la sortie reste inférieure à une valeur limite.
le bruit de fond, information non significative correspondant en général au signal présent à la sortie du dispositif en l’absence d\’un signal à l\’entrée. Il s\’exprime généralement en décibels (dB).
La plupart du temps, l\’information est transmise par un signal électrique ou radioélectrique. L’Académie conseille les expressions rapport signal à bruit ou rapport signal sur bruit, on utilise aussi parfois l\’abréviation SNR du terme anglais signal-to-noise ratio.
Le niveau maximal d\’un signal est limité par les capacités techniques du dispositif utilisé. Quand ces limites sont atteintes, les signaux sont transmis avec une déformation involontaire appelée distorsion, qui croît progressivement. On définit le niveau maximal en spécifiant la distorsion maximale admissible.
On peut améliorer le rapport signal sur bruit d\’un dispositif en augmentant la valeur maximale du signal. Cependant, souvent, à partir d\’un certain point les mesures prises pour augmenter la valeur maximale se répercutent aussi sur le bruit de fond du signal.
II.3.2. Les retards de paquets « Delay »
Dans un environnement sans fil en temps réel, chaque paquet est généré par les applications est associé à un délai. Si le système ne peut pas allouer suffisamment de ressources pour servir le paquet avant la date limite, le paquet sera supprimé. Différentes applications ont des exigences de délai différentes qui devraient être garanties par le système afin de maintenir certaines probabilités de paquets perdus. Par rapport au réseau câblé, il est plus difficile de fournir des garanties de qualité de service dans le réseau sans fil en raison de la limitation des ressources, des caractéristiques d\’erreur et de la mobilité.
La planification de la bande passante disponible pour différents services est une tâche non triviale. Certaines applications, par exemple vidéo, nécessitent une grande quantité de bande passante et sont très sensibles au délai, alors que d\’autres, par ex. la voix, nécessitent une quantité relativement faible de bande passante avec des exigences de délai moins strictes. Ces applications doivent toutes être satisfaites si le système dispose de suffisamment de ressources pour prendre en charge et maintenir la qualité de service de chaque application individuelle.
Dans un environnement sans fil, tout paquet peut être abandonné principalement pour les raisons suivantes: pas assez de ressources pour envoyer un paquet critique, qualité de canal sans fil, ou collision des paquets provenant de différentes applications.
Afin d\’assurer la disponibilité des créneaux horaires, il y a une BS qui alloue les ressources du système. Il y a une file d\’attente dans la mémoire de messages pour conserver les paquets prêts à envoyer. Si la station de base informe une station mobile que le nombre d\’intervalles de temps disponibles, la station mobile sélectionne certains paquets de la file d\’attente pour la transmission. La station de base programmera la bande passante disponible à différentes stations mobiles, comme nous allons voir au chapitre 3 selon quelque différentes algorithmes.
II.3.3. Equité « Fairness »
[6]Le problème de l\’équité survient chaque fois qu\’une quantité donnée de ressources doit être partagée par un certain nombre d\’utilisateurs. Dans un environnement sans fil, en raison de variations aléatoires, nous devons distinguer l\’équité temporelle (ce qui signifie que chaque utilisateur obtient une part équitable des ressources système) et l\’équité utilitaire (ce qui signifie que chaque utilisateur obtient une part de la capacité globale). Bien que l\’équité temporelle soit égale à l\’équité utilitaire dans un environnement filaire, elle peut être sensiblement différente dans un environnement sans fil.
La planification équitable est un algorithme de planification pour un tel système dans lequel l\’ utilisation du ressource est répartie de manière égale entre les utilisateurs du système ou les groupes. Une méthode courante d\’implémentation logique de la stratégie d\’ordonnancement du partage équitable consiste à appliquer de manière récursive la stratégie d\’ ordonnancement circulaire à chaque niveau d\’abstraction
L\’équité est une propriété souhaitable du réseau sans fil car elle offre une protection entre les utilisateurs. Cela signifie que le flux de trafic d\’un utilisateur mal intentionné ne peut pas affecter le flux de trafic d\’un autre utilisateur.
II.3.4. Débit «Throughput »
Il existe un intérêt considérable au sein de l\’industrie en ce qui concerne la spécification des performances des données sans fil. Dans cette partie, nous allons discuter de l\’une des propriétés les plus importantes du système d\’information, le débit. Le débit est généralement considéré dans un cadre qui optimise les performances du système et mesure la quantité d\’informations pouvant être transmises et reçues par unité de temps avec une probabilité d\’erreur négligeable[13]. Nous évaluerons et trouverons les disciplines de planification avec les meilleures performances.

C’est la quantité de données qui peut être transmise par unité de temps. Il est considéré comme le principal indicateur de la qualité du réseau vu par les applications non temps réel. Aujourd’hui, ce paramètre et largement limité par les réseaux d’accès de type radio, où les ressources disponibles, malgré leur croissance d’une génération à une autre, restent limitées et coûteuses.
Pour concevoir et déployer un WLAN, une procédure de déploiement précise est nécessaire pour assurer une couverture et une fonctionnalité réseau suffisantes (capacité, interférence, etc.). Alors que les équipements de réseau sans fil sont souvent classés en fonction de leur débit de signalisations normalisées, le débit de données réel ou les données transmises ne représentent souvent qu\’une fraction du maximum théorique du débit de signalisation. Les recherches menées dans l’article [14] ont montré que les performances de débit des utilisateurs changent radicalement lorsque les points d\’accès ou les clients sont situés à proximité d\’un émetteur brouilleur ou lorsque la planification des fréquences n\’est pas soigneusement effectuée. Le débit de données peut également être limité en raison d\’un certain nombre de facteurs importants liés à l\’environnement et au produit, notamment: la distance entre les périphériques WLAN, les points d\’accès et les cartes d\’interface réseau.
II.3.5. Le taux d’erreurs binaire (BER)
Le taux d\’erreur ou B.E.R., abréviation de l\’expression anglaise Bit Error Rate, désigne une valeur, relative au taux d\’erreur, mesurée à la réception d\’une transmission numérique, relative au niveau d\’atténuation et/ou de perturbation d\’un signal transmis. Ce phénomène survient également lors de l\’échantillonnage (numérisation), lors de la lecture et de la sauvegarde des données (CD-R, DVD-R, disque dur, RAM…).
Ce taux détermine le nombre d\’erreurs apparues entre la modulation et juste après la démodulation du signal. Ce taux d’erreur ne tient généralement pas compte du codage des données sauf dans le cas d\’une norme de transmission combinant modulation et correction d\’erreur (exemple : QPSK). La cause des perturbations, donc de l\’augmentation du taux d\’erreur, peut être multiple : équipement ou réseau défectueux, pointage incorrect d\’une antenne, interférences, longueur des câbles, etc.
Le taux d\’erreur (BER) s\’exprime en puissance négative. Par exemple, 10-3 signifie que l\’on a en moyenne une erreur binaire pour mille bits transmis. Le taux d’erreurs binaire (BER) et le taux d’erreur binaire résiduel : Ce sont des indicateurs importants qui reflètent la qualité finale du lien et qui affectent directement les performances des applications sur le réseau. Si certains taux d’erreurs binaires peuvent être corrigés par des mécanismes de type CRC (Cyclic Redundancy Check), les applications ne sont pas toutes égales devant ce paramètre. En effet, les applications transactionnelles ou de transfert de fichier restent les plus exigeantes et nécessitent souvent des retransmissions afin de garantir l’intégrité des données.
II.3.6. L’état de canal
Dans les réseaux sans fil, les conditions du canal varient en fonction du temps en raison de la décoloration et de l\’observation [15]. Différents utilisateurs sans fil rencontrent des conditions de canal différentes à un moment donné. Cela donne lieu à l’effet de diversité multi-utilisateurs: lorsque de nombreux utilisateurs s’affaiblissent de manière indépendante, il est fort probable que certains utilisateurs disposent d’un canal puissant. En n\’autorisant que les utilisateurs à transmettre, la ressource de canal partagé est utilisée de la manière la plus efficace et le débit total du système est maximisé. De tels mécanismes de planification sont appelés opportunistes, car ils tirent parti des conditions de canal favorables lors de l\’attribution de créneaux horaires aux utilisateurs. Si les exigences de service de tous les utilisateurs sont flexibles, de tels mécanismes de planification opportunistes peuvent entraîner une utilisation du spectre plus élevée et un débit de système accru. Néanmoins, dans la pratique, plusieurs considérations doivent être prises en compte avant de réaliser de tels gains.
Pour mettre en œuvre l\’idée d\’une planification opportuniste dans un système réel, deux questions doivent être abordées: l\’équité et les exigences de service des utilisateurs. En réalité, les statistiques de canal des différents utilisateurs ne sont pas symétriques et, par conséquent, un schéma conçu uniquement pour maximiser le débit global peut être très biaisé, en particulier lorsque des utilisateurs sont très éloignés de la station de base. Par exemple, autoriser uniquement les utilisateurs proches de la station de base à transmettre peut entraîner un débit très élevé, mais sacrifie la transmission des autres utilisateurs. En outre, une stratégie de planification ne devrait pas concerner uniquement la maximisation des débits moyens à long terme, car, dans la pratique, les applications peuvent avoir des utilitaires et des contraintes de service différents. Par exemple, pour les applications en temps réel, la principale préoccupation est la latence: si les variations de canal sont trop lentes, un utilisateur peut devoir attendre longtemps avant de pouvoir transmettre. Lors de la conception d\’un algorithme de planification, le défi consiste à résoudre ces problèmes tout en exploitant le gain de diversité multiutilisateurs inhérent à un système. L’amélioration de l’efficacité de l’utilisation du spectre est importante, en particulier pour fournir un service de données à haut débit.
Cependant, la possibilité d\’exploiter de manière opportuniste des débits de données plus élevés introduit le problème du compromis entre l\’efficacité des ressources sans fil et les niveaux de satisfaction des utilisateurs.
Le système cellulaire lui-même doit également satisfaire à certaines exigences pour extraire les avantages de la diversité multiutilisateurs. La station de base doit avoir accès à des mesures de qualité de canal: dans la liaison descendante, chaque récepteur doit suivre son propre rapport signal sur bruit (SNR) et renvoyer ces informations à la station de base. La station de base doit pouvoir programmer les transmissions entre les utilisateurs sur une courte période et adapter les débits de données des utilisateurs à la qualité instantanée des canaux. Ces fonctionnalités sont déjà présentes dans la conception de nombreux systèmes haute vitesse (HDR) 3.5G. C’est la raison pour laquelle l’ordonnancement opportuniste a reçu beaucoup d’attention récemment.
Il existe des points de départ et des hypothèses communs qui peuvent être discutés :
Modèles de trafic – Afin d\’évaluer le service reçu par un utilisateur dans un système qui utilise une planification opportuniste, il est nécessaire de décrire le trafic offert au niveau du flux.
Cependant, les performances de planification ont été principalement évaluées au niveau des paquets, en supposant qu\’il existe un retard de traitement infini des paquets dans chaque file d\’attente. De plus, l\’analyse de performance est souvent effectuée en supposant une population d\’utilisateurs statique.

C\’est également le cas dans certains des articles que nous avons interrogés, même s\’il est clair qu\’il n\’est pas satisfaisant de supposer que la population d\’utilisateurs est indépendante de l\’algorithme de planification. Par exemple, un algorithme de planification qui fournit un débit élevé aux utilisateurs ayant des conditions de canal favorables aura tendance à satisfaire plus rapidement les demandes de service de ces utilisateurs. En conséquence, l\’algorithme serait laissé à une population d\’utilisateurs avec une fraction plus élevée d\’utilisateurs avec des conditions de canal médiocres. Dans [Agrawal02] [16], un système de communication sans fil avec un nombre constant d\’utilisateurs a été pris en compte, avec une hypothèse implicite sur le nombre illimité de paquets en attente. En outre, dans [Andrews05][16].
Les auteurs supposent que, pour chaque flux, il existe toujours des données disponibles pour le service [17]. [Kushner03] [18] fait un pas en avant: bien que l’hypothèse de l’arriéré infini soit utilisée pour obtenir les principaux résultats de l’étude, les auteurs fournissent une extension de l’analyse présentée qui donne un aperçu de la performance des Aucune hypothèse particulière sur le processus d\’arrivée n\’a été donnée. [Borst05] [19] se concentre sur les performances au niveau du flux dans un paramètre dynamique avec des demandes de service de taille finie aléatoires. Les processus d’arrivée de session sont supposés être Poisson. La notion de demande de service de taille finie a permis aux auteurs de considérer les performances perçues par l\’utilisateur en termes de temps de réponse pour les transferts de fichiers, par exemple, par opposition aux retards des paquets individuels, ce qui se produit supposition.
Hypothèses liées aux canaux – Nous abordons les hypothèses sur deux aspects du canal: disponibilité des informations sur l\’état des canaux et méthode d\’accès aux canaux. Une connaissance parfaite de l\’état du canal a souvent été supposée dans la littérature qui étudie la performance de la planification opportuniste.
Bien que les systèmes 3G utilisent des mécanismes d\’estimation de canal et de rapport, les informations d\’état du canal disponibles pour la station de base ne sont pas parfaites: elles sont retardées et souvent obsolètes.
De plus, le mécanisme d\’estimation de canal proprement dit introduit des erreurs d\’estimation de canal au niveau de la station mobile. [Andrews05] [16], [Kushner03] [18] et [Borst05] [19] supposent que la connaissance parfaite du canal est disponible sur la station de base. Cela signifie pratiquement que, à chaque instant, le programmateur opportuniste sait exactement quels sont les taux réalisables pour toutes les stations mobiles. Les implications d\’une telle hypothèse n\’ont pas été discutées. [Agrawal02] [16] considère cependant trois cas: une connaissance parfaite des canaux, des connaissances imparfaites et aucune connaissance.
Notez toutefois que \”aucune connaissance\” suppose toujours que les informations sur le débit de données pouvant être atteint en régime permanent pour chaque station mobile sont disponibles à la station de base. En ce qui concerne la méthode d\’accès au canal, [Andrews05] [17] et [Borst05] [19] supposent un multiplexage par répartition dans le temps; c\’est-à-dire qu\’un seul utilisateur est autorisé à transmettre à la fois. La même hypothèse est valable pour la plupart des analyses présentées dans [Kushner03] [18] , cependant, une extension au cas où il y a plusieurs canaux (ou plusieurs antennes d\’émission) est également donnée. [Agrawal02] [16] considère à la fois le cas où plusieurs utilisateurs sont sélectionnés pour la transmission à la fois et le cas TDM.
Contraintes de service – Aucune exigence ou contrainte de service spécifique n’a été prise en compte dans la plupart des articles interrogés. La seule exception est [Andrews05] [17] , qui considère les contraintes de qualité de service les plus simples possibles: garanties de débit minimum et maximum. Au lieu des exigences de service, les articles interrogés se concentrent principalement sur l\’utilitaire de l\’utilisateur. Puisque [Kushner03] [18]et [Borst05] [19]analysent les performances du programmateur Fair proportionnel, ils se concentrent sur la fonction utilitaire logarithmique. [Agrawal02] [16] et [Andrews05] [17] considèrent un cas plus général d\’une fonction d\’utilité croissante arbitraire strictement concave.
Conclusion
L\’ordonnancement est l\’un des plus importants mécanismes de gestion de ressources dans les réseaux mobile, qui permet de déterminer à quel utilisateur il convient de transmettre dans un intervalle de temps donné. C\’est un élément déterminant dans la conception puisqu\’il répartit l\’allocation du canal entre les utilisateurs et ainsi, d\’une manière générale, détermine le comportement global du système. Un débit optimal du système peut être obtenu en affectant toutes les ressources radio à l\’utilisateur avec les meilleures conditions radio du canal, néanmoins un ordonnanceur, en pratique, devrait avoir plusieurs niveaux d\’équité. Ainsi, en choisissant différents algorithmes d\’ordonnancement, les opérateurs peuvent adapter sur mesure le comportement du système à leurs besoins. Alors, il n\’est pas nécessaire de standardiser les algorithmes utilisés, au lieu de cela, les opérateurs peuvent choisir différents critères. La prédiction de la qualité du canal, la capacité de la cellule, ainsi que des classes différentes de priorités de trafic sont des exemples d\’informations sur lesquels l\’ordonnanceur pourrait baser ses décisions.
C’est ce que nous allons le découvrir par la suite dans le chapitre suivant.

Chapitre 3 :

Evaluation des performances des algorithmes d’ordonnancement dans un contexte radio mobile

Introduction
Comme les appareils mobiles sont disponibles et populaires, le réseau sans fil constitue une nouvelle base pour le service Internet. Cependant, certains problèmes peuvent être ignorés sur le réseau câblé. En revanche, le réseau sans fil est assez limité par rapport au réseau filaire au niveau bande passante. Cette restriction provient de la variation de l’état des canaux, comme la mobilité des utilisateurs mobiles, l’évanouissement par trajets multiples et l’observation. a cause du déficience de la bande passante; il n\’asse pas facile de respecter les besoins de qualité de service pour les utilisateurs mobile. [30].En effet, une planification efficace des données est nécessaire pour éviter la restriction de la transmission des données.
Dans ce chapitre, nous expliquons l\’allocation et la planification des ressources en liaison descendante pour les réseaux sans fil à large bande basés sur OFDM. Nous présentons un cadre de gestion des ressources inter-couches optimisé par l\’optimisation de l\’utilitaire. Il comprend une architecture de gestion des ressources et de qualité de service, des algorithmes d\’allocation des ressources, une planification multi canal basée sur les taux et les délais qui exploitent les informations sur les canaux et les files d\’attente sans fil et l\’exploration théorique des mécanismes fondamentaux tels que l’équité, et le débit [31]. Différents algorithmes d\’ordonnancement ont été proposés qui fonctionnent dans différents scénarios. L\’objectif est d\’améliorer le débit de plusieurs utilisateurs de données par paquets partageant un canal de liaison descendante sans fil tout en préservant l\’équité.[5] Les algorithmes d\’ordonnancement pour les réseaux de données par paquets sans fil exploitent le fait que les canaux de propagation entre les BS et les MS qu\’ils desservent s\’estompent de manière indépendante en programmant la transmission aux MS lorsque leurs canaux sont bons, donnant lieu à une diversité multiutilisateur [31].
Comme nous avons cité précédemment le système considéré est un système OFDM avec accès multiple par répartition en fréquence (FDMA) et accès multiple par répartition dans le temps (TDMA). Des informations d\’état de canal parfait sont supposées à la fois à la MS et à la BS, c\’est-à-dire que le gain de canal sur chaque sous-porteuse dû à la perte de trajet, à l\’ombrage et aux évanouissements par trajets multiples est supposé connu.
Chaque sous-transporteur ne peut être utilisé par qu’un seul utilisateur à la fois. L\’allocation de sous-porteuse est effectuée à la BS et les utilisateurs sont informés des sous-porteuses choisies pour eux. Considérons un système avec K utilisateurs, N sous-transporteurs et le temps divisé en intervalles de temps. A chaque créneau temporel, chaque utilisateur de programmation k transmettra sur la sous-porteuse allouée. Des algorithmes d\’allocation de puissance égaux sont pris en compte, ce qui répartit simplement la puissance de transmission également parmi les sous-porteuses. L\’objectif est de trouver une allocation de sous-porteuse, qui permette à chaque utilisateur de satisfaire ses exigences de débit, en maximisant le débit sans pour autant être juste. Le système est montré dans la figure suivante [5]:

Figure16 : Système de transmission à transmission multiples

Diversité multiutilisateurs
Quelle que soit la génération de systèmes de communication, l’évanouissement des canaux et le grand nombre d’utilisateurs constituent toujours des obstacles à une communication fiable. Les concepteurs de systèmes utilisent différents types de schémas de codes de modulation pour améliorer la qualité de la communication dans le scénario d\’évanouissement [32]. D’une part, au lieu d’éviter les évanouissements, nous pouvons les exploiter en utilisant des techniques de diversité multiutilisateurs[33] pour traiter ces deux problèmes en même temps. Dans le système avec de nombreux utilisateurs avec des canaux , à n\’importe quel moment, certains utilisateurs ont toujours de meilleurs canaux que d\’autres. En choisissant le meilleur ou les meilleurs utilisateurs à transmettre, nous pouvons allouer les ressources système à de bons utilisateurs pour obtenir une bonne performances de capacité en termes de taux d’erreur binaire.
Pour maximiser la capacité totale d\’information, ils ont montré que la stratégie optimale consiste à programmer à tout moment l\’utilisateur ayant le meilleur canal à transmettre à la BS. Le gain de diversité provient du fait que dans un système avec de nombreux utilisateurs, dont les canaux varient indépendamment, il y a probablement un utilisateur dont le canal est proche de son pic à tout moment. Le débit global du système est maximisé en allouant à tout moment la ressource de canal commune à l\’utilisateur qui peut le mieux l\’exploiter. Il peut également être considéré comme une forme de diversité de sélection. Par rapport aux systèmes mono-utilisateur, les systèmes multiutilisateurs choisissent non seulement le moment de la transmission, mais choisissent également l’utilisateur à transmettre, de manière à obtenir un gain de diversité supplémentaire. Le gain de diversité multiutilisateurs dépend de la plage dynamique d\’évanouissement et du nombre d\’utilisateurs. Lorsque le nombre total d\’utilisateurs est élevé et que leurs canaux s\’estompent rapidement, le gain de canal effectif est amélioré, de sorte qu\’avec une forte probabilité, un utilisateur dispose d\’un très bon canal à un moment donné. C\’est exactement comme cela que la diversité multiutilisateurs exploite les évanouissements et le grand nombre d\’utilisateurs.
D\’autre part, la diversité multiutilisateurs doit faire face à des défis qui influenceront les performances du système. Comme nous l\’avons décrit ci-dessus, à chaque intervalle de temps, les bons utilisateurs sont choisis pour transmettre.
Cela soulève le premier problème critique, à savoir l’équité entre les utilisateurs. Dans les systèmes pratiques, tous les canaux utilisateur ne sont pas statistiquement symétriques, ce qui signifie que tous les utilisateurs ne rencontrent pas le même scénario d\’évanouissement. Un exemple simple est celui du système cellulaire sans visibilité directe, où le signal dépend fortement de l\’emplacement spécifique de la station de base, de sorte que la qualité du canal varie considérablement entre les utilisateurs [33]. D\’une manière générale, les utilisateurs proches de la station de base sont susceptibles d\’avoir une meilleure qualité de canal que ceux éloignés de la station de base. Cela signifie que les utilisateurs proches auront plus de chance de communiquer que les utilisateurs éloignés. En utilisant une stratégie de l’algorithme proportional fair que nous allons le voir par la suite, le système peut atteindre une équité asymptotique à long terme. Le planificateur suit le taux de l’utilisateur normalisé par son débit moyen au lieu de suivre uniquement le débit, de sorte que tous les utilisateurs à leur propre pic puissent être disposés à transmettre.
Le deuxième problème est celui que nous avons présenté précédemment, la diversité multiutilisateurs dépend du taux et de la plage dynamique de la fluctuation des canaux. En fait, plus la fluctuation est grande, plus le gain de diversité est grand. Par exemple, si le canal varie trop lentement par rapport à la contrainte de délai de l\’application, le planificateur risque de ne pas pouvoir attendre assez longtemps pour que le canal atteigne son pic [5]. Cependant, au fur et à mesure que le mouvement augmente, le gain de diversité sera réduit par les erreurs dans les estimations de canal fournies au planificateur par le biais du canal de retour, conduisant ainsi à un compromis diversité-gain-mobilité. Pour exploiter la diversité multiutilisateur dans un système de communication réel, il faut prendre en compte deux problèmes principaux: l\’équité et le retard. En général, les statistiques des canaux des utilisateurs sont différentes, et une politique d\’ordonnancement consistant à toujours donner le canal au meilleur utilisateur peut conduire à des injustices. En fait, les utilisateurs d\’une cellule sont généralement placés à des distances différentes de la station de base et les caractéristiques d\’observation changent d\’un emplacement à l\’autre, de sorte qu\’il est plus probable que la station de base transmettra toujours à l\’utilisateur le plus proche. Le retard n\’est pas une limite stricte comme c\’est le cas pour les applications vocales mais nous devons néanmoins assurer une QoS aux utilisateurs, par exemple, sous la forme d\’un délai moyen maximum des paquets.[5] Comme une combinaison de tous les problèmes que nous avons mentionnés, différents algorithmes de planification équitable sont comparés et il est également montré que le codage spatio-temporel rend le système plus robuste et offre un gain de performance en cas d\’erreurs de retour.
Algorithme Round Robin
Round Robin (RR) [5]est l\’un des algorithmes de planification les plus simples, qui attribue des tranches de temps à chaque MS, à parts égales et dans l\’ordre, en traitant toutes les MS avec la même priorité. La planification RR est à la fois simple et facile à mettre en œuvre, et sans famine.
Dans les réseaux sans fil, où de nombreuses stations partagent un canal, cet algorithme fournit à chaque MS une transmission ou une réception sur le canal partagé à intervalles réguliers. Cela peut faire de RR un algorithme équitable.
Cependant, comme il est beaucoup moins efficace que d’autres algorithmes tels que PFS ou Max rate (comme nous les verrons respectivement par la suite), il sera difficile à fournir un très bon service à la MS. La BS subira également une capacité réduite du réseau.
C’est une stratégie classique d’allocation des ressources radio, l’algorithme alloue la même quantité de ressource aux utilisateurs en partageant le temps, par conséquent, le débit diminue considérablement vue, que tous les utilisateurs du système utilisent les ressources radio suivant un quantum de temps.
Avec Round Robin (Tourniquet), l’ordonnanceur parcourt les files d’attente en séquence et prend le premier élément de chaque file. Si une file est vide, l’ordonnanceur passe à la file suivante. Le principe de round robin est adapté à l\’isolement de flux grâce à la distribution des paquets entre plusieurs files d\’attente. L\’équité offerte par le mécanisme dépend de la taille moyenne des paquets dans chaque file : une file contenant des paquets deux fois plus gros que les autres obtient deux fois plus de bande passante.
Une variante du Round Robin est définie dans [28]. Il s\’agit de la technique DRR (Déficit round robin) qui est une variation du bit-à-bit round-robin, un modèle théorique d\’ordonnancement prenant en compte la taille des paquets [29]. Dans cet algorithme, la variable quantum est chargée de limiter le nombre d\’octets transmis dans chaque file lors du passage de l\’ordonnanceur. Si la taille du paquet en tête de la file est supérieure au quantum, le paquet n\’est pas transmis et les jetons sont accumulés pour être utilisés lors du prochain passage.
La technique Weighted Round Robin (WRR) est aussi une autre variante, qui en introduisant la notion de poids sur les classes de service peut offrir une distribution différenciée de la bande passante. Dans les mécanismes de round robin cette variable détermine le nombre d\’octets à soustraire de chaque file d\’attente à chaque passage de l\’ordonnanceur. Par exemple, en utilisant l\’algorithme de DRR décrit précédemment, une pondération de flux peut être facilement mise en œuvre si l\’on attribue des valeurs de quantum différentes pour chaque service.

Algorithme Max Rate
[5]Le planificateur de Max Rate transmet toujours à chaque TTI à l\’utilisateur ayant le plus grand SNR, de sorte qu\’ils sont à un taux maximal, ils sont tous en même temps. Le programmateur Max Rate offre un débit plus élevé que toute autre politique de planification possible, mais il ignore totalement l’équité. Dans les environnements sans fil, le canal des utilisateurs peut être très différent en raison des distances éventuellement différentes de la station de base, bien que les deux canaux fluctuent en raison de l\’évanouissement dû à la propagation par trajets multiples. Ainsi, toujours choisir l\’utilisateur le plus fort serait très injuste.
Le SNR reçu du signal du nième sous-porteuse du kième utilisateur à la TTI peut être exprimé par [34]:
SNR_(k,n) (t)= (S_(k,n) (t) 〖 H〗_(k,n) (t))/(N_(0 ) B/N) (1)
Où S_(k,n) (t) et 〖 H〗_(k,n) (t) sont la puissance de transmission attribuée et le gain de canal sur le n-ième sous-porteuse à la TTI respectivement, N0 est la densité spectrale de puissance de AWGN , B est la largeur de bande et N est le nombre de sous-porteuses.
Le débit de données instantané de chaque utilisateur est déterminé et la BS sert chaque utilisateur à ce rythme. Le taux de service instantané sur le nième sous-opérateur à la TTI est obtenu par :
R_(k,n) (t) = B⁄N log_2⁡〖(1+SNR)〗 (2)
Où R_(k,n) (t)est le kième taux de transmission de l\’utilisateur à la TTI, B est la largeur de bande totale et N est le nombre de sous-porteuses [34].
[35] Une stratégie de planification de Max rate peut être tentante, car elle optimise l\’utilisation des ressources sur un réseau donné, mais ne permet pas de maximiser les bénéfices pour l\’opérateur de réseau. Les niveaux de satisfaction de la clientèle restent bas en raison du grand nombre de clients connaissant des pannes de service longues ou permanentes.
Une équité proportionnelle entraînerait une réduction du débit, mais la famine serait évitée.
L\’équité maximale devrait se traduire par un débit encore plus faible, mais un niveau plus élevé d\’ équité , ce qui signifie que la qualité de service obtenue par chaque flux de données serait encore plus stable.
Algorithme Proportional Fair
Pour mettre en œuvre l’idée de diversité multiutilisateurs dans un système réel, on est immédiatement confronté à deux problèmes: l’équité et le débit. Dans l’idéal, lorsque les statistiques d’évanouissement des utilisateurs sont les mêmes, la stratégie ci-dessus maximise non seulement la capacité totale du système mais également le débit des utilisateurs individuels. En réalité, les statistiques ne sont pas symétriques; il y a des utilisateurs plus proches de la BS avec un meilleur SNR moyen; il y a des utilisateurs qui sont stationnaires et d\’autres qui bougent.. En outre, la stratégie ne concerne que la maximisation des débits moyens à long terme; En pratique, il existe des exigences de latence, auquel cas les débits moyens sur l\’échelle de temps de retard constituent la mesure de performance présentant un intérêt. Le défi consiste à résoudre ces problèmes tout en exploitant le gain de diversité multiutilisateurs inhérent à un système dont les utilisateurs ont des conditions de canal variables et indépendantes.[5] Un algorithme de planification simple a été conçu pour relever ce défi, l\’algorithme de planification équitable proportionnelle (PFS)[5]. C’est un algorithme de planification basé sur le compromis . Il repose sur le maintien d’un équilibre entre deux intérêts concurrents: essayer de maximiser le débit total du réseau [filaire / sans fil] tout en offrant à tous les utilisateurs un niveau de service minimal. Cela se fait en attribuant à chaque flux de données un débit de données ou une priorité de planification (en fonction de la mise en œuvre) inversement proportionnelle à la consommation de ressources prévue.[36] L\’algorithme de planification fonctionne comme suit :
Le retour de la qualité de canal de l’utilisateur k dans le temps TTI vers la station de base BS est un débit de données demandé Rk, n (t), qui désigne que la sous-porteuse du kème utilisateur peut actuellement prendre en charge.
L\’algorithme PFS assure le suivi du débit moyen Tk,n (t) de chaque utilisateur sur chaque sous-porteuse dans une fenêtre de longueur passée tc. Les paramètres tc signifient le compromis entre équité et débit. La valeur de tc varie du l’intervalle ]∞,1] Dans l\’intervalle de temps t, l\’algorithme PFS transmet à chaque sous-porteuse à l\’utilisateur K la plus grande valeur de J calculée comme suit:
J= R_(k,n)/T_(k,n) (3)
Le débit moyen Tk,n(t) peut être mis à jour à l\’aide d\’un filtre passe-bas à pondération exponentielle
T_(k,n) (t+1){█((1-1/T_c ) T_(k,n) (t)+1/T_c R_(k,n) (t) @ @ @(1-1/T_c ) T_(k,n) (t) )┤ (4)

Dans ce rapport, l\’algorithme PFS est utilisé en prenant indépendamment les sous-porteuses. Donc, nous devons calculer ce que l\’utilisateur a la plus grande valeur donnée par l\’équation (3) à chaque sous-porteuse et créneau horaire afin d\’attribuer cette sous-porteuse à cet utilisateur.
En outre, nous devons mettre à jour le débit moyen des utilisateurs par l’équation (4) pour chaque sous-porteuse et chaque intervalle de temps. Ainsi, l\’algorithme PFS traite les sous-porteuses indépendamment les unes des autres et nous devons mettre à jour le système à chaque intervalle de temps.
Cet algorithme ne prend pas dans les exigences de taux d\’utilisateurs et d\’allocation de puissance conventionnelle n\’est pas considéré parce qu\’il a quelques points faibles qui dégradent les performances du système lorsqu\’il est utilisé dans un environnement hétérogène de canal utilisateur [5][37].
L’algorithme PFS s’avère comme un algorithme équitable et en même temps transmet pour tous les utilisateurs avec le canal statistiquement plus fort. Donc la figure 17 présente la réponse en fréquence de trois utilisateurs. Ainsi, l\’algorithme programme un utilisateur lorsque sa qualité de canal instantanée est élevée par rapport à sa propre condition de canal moyenne sur l\’échelle de temps tc. En bref, les données sont transmises à un utilisateur lorsque son canal est proche de ses propres pics. Les avantages de la diversité multiutilisateurs peuvent toujours être extraits car les canaux des différents utilisateurs fluctuent indépendamment, de sorte que si le nombre d\’utilisateurs est suffisant, il y aura probablement un utilisateur proche de son pic à la fois.

Figure17 : Réponse du canal de fréquence pour trois utilisateurs.

Le paramètre tc
Le paramètre tc est lié à l\’échelle de temps de latence de l\’application. Les pics sont définis par rapport à cette échelle de temps.
La plus grande valeur de tc est tc = ∞ [34], dans ce cas les ressources d\’allocation selon l\’algorithme PFS sont décidées uniquement par SNR instantané, conduisant à un débit maximal du système et à de mauvaises caractéristiques d\’équité. En revanche, la valeur inférieure du paramètre tc est tc = 1 dans cette situation, la planification se rapproche de l’algorithme Round Robin dans l\’intervalle de temps t. Par conséquent, tc signifie le compromis entre équité et débit.
Dans la Figure suivante l\’équité du système en termes de fairness vs. tc se base sur trois algorithmes différents, PFS, RR et Max Rate. Comme il apparait, si Équité = 1, tous les utilisateurs partagent exactement la même quantité de ressources et si Équité = 0 se produit lorsqu\’un seul utilisateur consomme toute la quantité de ressources.[38]

Figure 18 : Équité du système vs. au paramètre tc.[38] Les planificateurs Round Robin et Max Rate sont indépendants du paramètre tc. Comme on peut le voir sur la figure 18, si tc = 1, l\’équité est maximiser et le comportement du planificateur Proportional Fair a tendance à avoir un comportement de type Round Robin. Mais, si tc tend vers l\’infini, il y a une réduction de l\’équité et le comportement du Proportional Fair proportionnel a tendance à avoir un comportement de Max Rate. [38]

Figure 19 : throughut du système vs. au paramètre tc.[5] Par contre, dans la figure 19 paramètre throughut vs. tc est montré. Comme nous l’avons déjà dit, les algorithmes Max Rate et RR sont indépendants du paramètre tc et représentent les limites de comportement. L\’algorithme Max Rate représente le plus grand débit et l\’algorithme RR représente le plus petit débit. Comme on peut le voir sur la figure 19 si tc tend vers l\’infini, il y a une augmentation du débit et le comportement de PFS tend au comportement de Max Rate, mais si ct tend vers 1, le débit et le comportement de PFS Comportement RR.
RÉSULTATS DE SIMULATION ET DISCUSSION
Dans cette section, nous allons simuler et discuter des performances des trois algorithmes de planification, tels que RR, PFS et Max-Rate, qui ont été comparées pour l’allocation des ressources de systèmes et encore ont été utilisés pour renforcer les conclusions sur l’équité du système, le délai et le débit. Les performances de ces algorithmes sont analysées et comparées à l\’aide de simulations informatiques MATLAB.
V.1. Description du modèle
Dans ce rapport, nous considérons la transmission en liaison descendante d\’un système OFDM multiutilisateurs. Nous supposons que la bande passante globale B est divisée en N sous-porteuses orthogonales à bande étroite.
Chaque MS mesure le gain de canal de chaque sous-porteuse et renvoie les informations d\’état de canal à la BS via un canal de retour séparé. Nous supposons que l\’estimation de canal peut être effectuée parfaitement et que le canal de retour est sans erreur. Le flux de données de chaque utilisateur sélectionné est ensuite modulé par un schéma de modulation approprié qui peut être pris en charge dans l\’état de canal donné et la puissance de transmission allouée de la sous-porteuse est obtenu par l’équation (1).
Dans les systèmes OFDM multiutilisateurs, un algorithme d\’allocation de ressources décide quel utilisateur utiliser avec quelle puissance pour chaque sous-porteuse. Ici, on suppose que la puissance de transmission totale est limitée à S. Une fois que les ressources sont allouées aux utilisateurs, le débit de données instantané de chaque utilisateur est déterminé et la BS sert chaque utilisateur à ce rythme. Selon la théorie de l\’information, le taux de service instantané sur la nième sous-porteuse à la troisième tranche de temps est obtenu par l’équation (2).
V.2. Résultats de la simulation
[5]Dans les simulations, il existe 16 sous-porteuses pour le système OFDM et la fréquence porteuse est de 2,4 GHz. Afin de montrer comment fonctionnent les différents algorithmes de planification, nous ne simulons que quatre utilisateurs et en supposant une distribution uniforme de l’utilisateur. Le tableau 10 montre les paramètres de simulation.
Tableau 10 : Paramètres de simulations
Paramètres Valeurs
Time slot 16
Sous-porteuses 16
fc (GHz) 2.4
Tc 20 et 100’000
Utilisateurs 4
Vitesse mobile (km / h) 3

Figure 20: affectation des ressources blocs pour chaque utilisateurs utilisant les algorithmes RR, PFS et Max Rate

La fig. 20 montre l’affectation des RB alloués par trame pour chaque utilisateurs utilisant les algorithmes précités. Comme nous pouvons voir que l\’algorithme RR alloue tous les RB d’une manière équitable à tous les utilisateurs a chaque TTI, et aussi nous pouvons distingué sur la figure 21(a) le bon affectation des sous porteuses aux utilisateurs pour chaque tranche du temps, enfaite l’algorithme RR accorder tous les sous porteuse à un utilisateur chaque intervalle de temps .
Par contre avec l’algorithme Max rate qui s’avère un algorithme non équitable puisque il favorise les canal avec une valeur de CQI plus élevé. Comme le montre la figure 20, ce planificateur attribue un numéro différent du RB pour chaque utilisateur afin de maximiser le débit moyen de système. Et comme me montre la figure 21 (b) ; l’utilisateur avec une valeur plus élevé du CQI est le plus dominant.
Et concernant le planificateur PFS essaie de trouver un équilibre entre l’équité et le débit. Le planificateur proposé effectue un compromis entre l’équité du système et le débit avec l’allocation des RB aux utilisateurs ayant la meilleure condition de canal en respectant l’approche de l’équité. Mais avec la stratégie PFS lorsque la valeur du paramètre tc est élevé presque toutes les RB attribues au utilisateurs caractérisés par son force de canal ; et les résultats changent lorsque nous prenons un paramètre tc plus faibles.(figure 20 et figure 21 (c)).

(a) (b)

(c)

Figure 21: affectation des sous porteuses aux utilisateurs chaque TTI en utilisant les algorithmes RR, PFS et Max Rate
Fairness (équité)
VI.1. Définition
L\’équité d\’un système, des utilisateurs d\’un système ou d\’un algorithme d’ordonnancement n’est pas généralement exprimée en termes de valeur quantitative. Au contraire, l\’équité est généralement exprimée en termes plus larges. Généralement, un système est jugé « équitable » ou « inéquitable » selon que le système répond ou non à certains critères. Ces critères sont généralement en termes de débit ou de délai. Par exemple, un algorithme de planification peut être considéré comme inéquitable si un utilisateur reçoit un débit inférieur à X bits/s. Un autre exemple pourrait être qu\’un système est jugé équitable si la probabilité qu\’un utilisateur rencontre un retard supérieur à t est inférieure à p ; Si la probabilité est supérieure à p, le système est inéquitable . La raison derrière ces définitions proposées est de voir si une valeur pour «l\’équité» d\’un système ou d\’un algorithme d\’ordonnancement peut être définie de la même manière que Shannon qui a défini une valeur pour «l\’équité» d\’une source. La valeur de l\’équité devrait également avoir un sens du point de vue mathématique et sémantique. La définition de Shannon était basée sur les probabilités d’événements. En comparaison, les mesures d\’équité proposées sont fondées sur les proportions des ressources allouées [39].
VI.2. Remarques
Les définitions ci-dessus donnent des propriétés intéressantes:
1. Lorsqu\’un utilisateur consomme exactement son équité part de ressources (c’est-à-dire une proportion de 1 / N), la valeur de l\’équité pour cet utilisateur sera l\’unité.
2. Au fur et à mesure que la quantité de ressources consommée par un utilisateur augmente, les autres utilisateurs du système s’en trouvent de plus en plus nombreux. Ainsi, cet utilisateur devient moins équitable (ou plus inéquitable) .
3. À l\’inverse, un utilisateur consommant moins de ressources, il cède des ressources en faveur des autres utilisateurs du système. Par conséquent, cet utilisateur devient beaucoup plus équitable (ou moins inéquitable).
4. Dans la limite où un utilisateur consomme toutes les ressources disponibles, tous les autres utilisateurs du système seront l\’utilisateur gourmand pour être moins équitables (ou plus inéquitables).
5. De même, dans la limite où un utilisateur ne consomme aucune ressource, cet utilisateur cède toutes ses ressources méritées en faveur des autres utilisateurs. Ainsi, il n\’y a pas de moyen possible pour cet utilisateur d\’être très équitable (ou moins injuste).
6. La valeur de l\’équité moyenne du système de N utilisateurs varie de 0 à 1. En outre, la valeur maximale de l\’unité n\’est atteinte que lorsque tous les utilisateurs du système consomment exactement leur part des ressources (c\’est-à-dire p1 = p2 =…= p3 =1/N). Le minimum de zéro apparaît dans la limite lorsqu\’un utilisateur consomme toutes les ressources allouées alors que les autres utilisateurs N-1 sont privés de ressources.
7. De même, l\’iniquité moyenne se situe entre 1 et l\’infini, les valeurs extrêmes inférieure et supérieure étant observées dans les mêmes conditions que les valeurs maximale et minimale respectivement pour l\’équité moyenne. En d\’autres termes, une valeur d\’unité ne résultera que si tous les utilisateurs consomment leur part de ressources, et l\’infini résultera si un seul utilisateur consomme toutes les ressources allouées.
La figure 21 montre une comparaison entre les trois algorithmes en fonction de critère d’équité. Nous utilisons l\’algorithme RR comme référence, car cette politique permet d\’obtenir les meilleurs résultats en termes d\’équité. La performance de ces algorithmes est analysée et comparée à travers les simulations informatiques MATLAB.

Figure 21 : Équité du système par rapport à l\’utilisateur à l\’aide de la méthode RR,PFS et Max rate

Comme nous avons cité précédemment l’algorithme Max Rate est l’algorithme le plus inéquitable car elle alloue la ressource système aux utilisateurs disposant du canal le plus puissant et desservant les utilisateurs qui demandent le service max (en utilisant la meilleure valeur CQI). Comme nous pouvons le voir sur la Fig.21, la valeur d’équité est dépasse pas 0.6 enfaite c’est une valeur est très faible par rapport au planificateur Fair proportionnel et au planificateur Round Robin.
L’algorithme PFS est indépendant des exigences de débit, de sorte que les résultats obtenus dans ces trois scénarios différents sont plus ou moins les mêmes. Comme nous pouvons voir sur la Fig.21, l\’algorithme PFS a un bon comportement car, comme nous l\’avons vu précédemment, avec un paramètre tc faible, cet index de maintenance de l\’algorithme est équitable sans impliquer le débit du système.
Throughput ( Débit)
VII.1. Définition
Comme nous avons vue dans le premier chapitre le throughut est le taux de production ou la vitesse à laquelle quelque chose peut être traitée.
En effet, la performance, par exemple le débit, d\’un utilisateur dépend de la condition de canal qu\’il expérimente, ainsi, une performance différente est obtenue lorsque la même ressource (par exemple, radiofréquence) est attribuée à différents utilisateurs. Par exemple, si l\’on considère une cellule avec deux utilisateurs: le premier utilisateur est proche de la BS et bénéficie ainsi de bonnes conditions de canal et le second utilisateur est au bord de la cellule et supporte donc des mauvaises conditions de canal dues à une perte de chemin significative et une interférence élevée des cellules voisines. Si la même quantité de ressources (puissance, tranches de temps, etc.) est attribuée aux deux utilisateurs, il est probable que le débit du premier utilisateur sera beaucoup plus important que celui du second utilisateur.
Dans la fig. 22 les algorithmes seront comparés en fonction des critères de débit. L\’algorithme Max Rate est utilisé comme référence car cette stratégie permet d\’obtenir les meilleurs résultats sur la capacité du système.

Figure 22: Débit du système par rapport à l\’utilisateur à l\’aide de la méthode RR,PFS et Max rate

La capacité du système obtenue par la stratégie RR atteint la valeur la plus faible car cet algorithme ne prend pas en compte la diversité multiutilisateurs et alloue toutes les sous-porteuses à un utilisateur chaque in intervalle de temps. Comme montrent les figures fig. 22 fig.23 la valeur du débit du système est assez faible ne dépasse pas 2.5Mbps ( fig.22) et le débit total pour chaque utilisateur n’atteint pas 0.5 Mbps ( fig. 23)
L\’algorithme Max Rate, en fonction du débit du système, atteint le meilleur résultat ( fig.23), car cet algorithme alloue des ressources système aux utilisateurs disposant du canal le plus puissant et optimise le débit du système. Plus le nombre d\’utilisateurs dans le système est élevé, plus le débit du système est élevé, il a abouti plus que 4.5Mbps ( fig. 22) car il est beaucoup plus probable de trouver un canal plus fort lorsqu\’il y a beaucoup plus d\’utilisateurs.
Ces deux algorithmes représentent les limites du débit du système.
L\’algorithme PFS exploite le fait que le canal de propagation entre BS et MSs est indépendamment l\’un de l\’autre, donnant lieu à une diversité multiutilisateurs. Comme on peut le voir sur la Fig. 21 , cet algorithme a un bon comportement car il atteint un bon niveau de débit du système sans compromettre l’équité. Dans ce cas, les utilisateurs sont en concurrence pour des ressources qui ne sont pas directement basées sur leurs SNR, mais seulement après la normalisation par leur débit moyen respectif ( fig.22). Comme nous l’avons déjà dit, plus les utilisateurs du système étaient gros, plus le débit du système était élevé ( fig.21). Parce que renforcer l’utilisateur est beaucoup plus probable. Mais la valeur atteinte avec cette politique est inférieure à la valeur obtenue par la politique Max Rate en raison de l’équité de la maintenance.

Figure 22 : Débit total pour chaque utilisateur à l\’aide du planificateur RR, PFS et Max, cinq utilisateurs
Delay ( Retard)
Le délai de planification est un terme de la modélisation du transport qui fait référence à une différence entre l\’heure d\’arrivée ou de départ souhaitée et l\’heure réelle. Malgré l\’utilisation du \”délai\”, il peut faire référence à une différence dans la direction précoce ou tardive.
En effet, l’ordonnancement a été conçu et utilisé pour optimiser l’équité et les performances. Comme indiqué précédemment, il existe un conflit entre la garantie de la qualité et l’équité des données, lorsque nous en maximisons l’un peut nuire à un autre. En tant que programmateur, il y a deux options lorsque l\’équité doit être appliquée lorsque de nouveaux emplois sont soumis; Prévoyez les tâches existantes ou attendez que les tâches en cours soient terminées. Bien que la prévention des tâches permette d’assurer l’équité immédiatement.
Le planificateur choisit quel nœud exécuter le travail en tête de ligne. Si les nœuds disponibles ne contiennent pas de données locales pour le travail, il les laisse attendre et évalue les travaux suivants.
Conclusion
Dans ce chapitre, nous avons appris à connaître différents algorithmes d’ordonnancement dans un système radio mobile, nous avons présenté les performances de trois algorithmes d\’ordonnancement tels que Round Robin, Proportional Fairness et Max rate en termes d\’équité et de capacité du système.
Nous pouvons voir que le planificateur RR favorise la priorité à l’équité entre tous les utilisateurs, quel que soit le débit du système.
D\’autre part, le planificateur Max Rate est utilisé pour maximiser la capacité du système sans tenir compte de l\’équité entre les utilisateurs. Mais, à partir des résultats obtenus, on observe également que l’algorithme Proportional Fairness opère un compromis entre l’équité du système et le débit.

Chapitre 4 :

Amélioration des performances d’un ordonnanceur dans un contexte Radio mobile

Introduction
Le présent chapitre va nous permettre de spécifier les objectifs théoriques de notre solution. Il s’agit de fournir une vue d’ensemble sur la contribution. Et par la suite, nous allons implémenter le modèle proposé, tout en analysant les résultats aboutis.
Aperçu synthétique de la contribution
A notre connaissance, comme nous avons vue dans le chapitre précédent, les deux algorithme RR et Max rate fonctionnent du façon contraire. D’une part l’algorithme RR sert à maximiser l’équité et minimiser le débit ; d’autre part, l’algorithme Max rate sert a maximiser le débit et minimiser l’équité.
Donc à partir des résultats obtenus, nous proposons une combinaison entre les deux algorithmes précités, dont l’objectif de trouver une compromis entre l’équité et le débit. Donc notre bute est d’assurer un system de bon performance avec équité acceptable. C\’est-à-dire tout les utilisateurs ont eu la chance d’être servis de fonctionner et avec un débit supportable.

Bibliographie

https://en.wikipedia.org/wiki/Information_system
Silver, M. S., Markus, M. L., & Beath, C. M. (1995). The information technology interaction model: A foundation for the MBA core course. MIS quarterly, 361-390.
kroenke, David (2015). MIS Essentials (Quatrième édition). Boston: Pearson. p. dix.
Laudon, KC et Laudon, (1988) JP Management Information Systems, (2e édition), Macmillan,
Martinez, A. B. (2006). Evaluation of multiuser scheduling algorithm in OFDM for different services. Master of Science in Electronics report.
Bejaoui, T. (2005). Gestion des ressources et qualité de service dans les réseaux mobiles multimédias (Doctoral dissertation, Paris 11).
https://fr.wikipedia.org/wiki/Orthogonal_frequency-division_multiplexing
https://d1n7iqsz6ob2ad.cloudfront.net/document/pdf/537dcd1b5dc42.pdf: caractéristique du problème d’ordonnancement
https://fr.wikipedia.org/wiki/Buffer
Zhu, R., & Yang, J. (2015). Buffer-aware adaptive resource allocation scheme in LTE transmission systems. EURASIP Journal on Wireless Communications and Networking, 2015(1), 176.
Ameigeiras, P., Wang, Y., Navarro-Ortiz, J., Mogensen, P. E., & Lopez-Soler, J. M. (2012). Traffic models impact on OFDMA scheduling design. EURASIP Journal on Wireless Communications and Networking, 2012(1), 61.
Access, E. U. T. R. (2010). Further advancements for E-UTRA physical layer aspects. 3GPP Technical Specification TR, 36, V2.
Bi, Q., Huang, C. Y., Li, P., & Newbury, M. E. (2003). Measures of wireless data performance. Bell Labs technical journal, 7(3), 219-223.
Marzetta, T. L., & Hochwald, B. M. (1999). Capacity of a mobile multiple-antenna communication link in Rayleigh flat fading. IEEE transactions on Information Theory, 45(1), 139-157.
Vukadinovic, V., & Drogou, E. Opportunistic Scheduling in Wireless Networks. Performance analysis of communication networks, Project Report.
Agrawal, R., & Subramanian, V. (2002, October). Optimality of certain channel aware scheduling policies. In Proceedings of the Annual Allerton Conference on Communication Control and Computing (Vol. 40, No. 3, pp. 1533-1542). The University; 1998.
Andrews, M., Qian, L., & Stolyar, A. (2005, March). Optimal utility based multi-user throughput allocation subject to throughput constraints. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE (Vol. 4, pp. 2415-2424). IEEE.
Kushner, H. J., & Whiting, P. A. (2004). Convergence of proportional-fair sharing algorithms under general conditions. IEEE transactions on wireless communications, 3(4), 1250-1259.
Borst, S. (2005). User-level performance of channel-aware scheduling algorithms in wireless data networks. IEEE/ACM Transactions on Networking (TON), 13(3), 636-647.
http://www.groupes.polymtl.ca/inf3600/documentation/notes/NotesDeCours/chap8.pdf
https://www.technologuepro.com/Systemes-Exploitation/Ordonnancement-des-processus.pdf
Chéramy, M., Hladik, P. E., & Déplanche, A. M. (2015). Algorithmes pour l’ordonnancement temps réel multiprocesseur. Journal Européen des Systèmes Automatisés (JESA), 48(7-8), 613-639.
http://pagesperso.lina.univ-nantes.fr/info/perso/permanents/queudet/docs/Module_E4_Partie_Ordo.pdf
https://fr.wikipedia.org/wiki/Rate-monotonic_scheduling
https://en.wikipedia.org/wiki/Deadline-monotonic_scheduling
https://fr.wikipedia.org/wiki/Earliest_deadline_first_scheduling
Capozzi, F., Piro, G., Grieco, L. A., Boggia, G., & Camarda, P. (2013). Downlink packet scheduling in LTE cellular networks: Key design issues and a survey. IEEE Communications Surveys & Tutorials, 15(2), 678-700.
Shreedhar, M., & Varghese, G. (1996). Efficient fair queuing using deficit round-robin. IEEE/ACM Transactions on networking, 4(3), 375-385.
Demers, A., Keshav, S., & Shenker, S. (1990). Analysis and simulation of a fair queueing algorithm. Internetworking: Research and experience, 1(1), 3-26.
Kim, J., Lee, D., Hwang, G., & Oh, C. (2001). A new scheduling algorithm for data services in HDR system: weight-gap first scheduling. In Info-tech and Info-net, 2001. Proceedings. ICII 2001-Beijing. 2001 International Conferences on (Vol. 2, pp. 329-334). IEEE.
Song, G., & Li, Y. (2005). Utility-based resource allocation and scheduling in OFDM-based wireless broadband networks. IEEE Communications magazine, 43(12), 127-134.
Bai, H., & Atiquzzaman, M. (2003). Error modeling schemes for fading channels in wireless communications: A survey. IEEE Communications Surveys & Tutorials, 5(2).
Zeng, R. (2012). Multi-user Diversity Systems with Application to Cognitive Radio. Arizona State University.
Nsiri, B., Nasreddine, M., Ammar, M., Hakimi, W., & Sofien, M. (2014). Modeling and performance evaluation of scheduling algorithms for downlink LTE cellular network. ENIT Tunis, Tunisia
https://en.wikipedia.org/wiki/Maximum_throughput_scheduling
https://en.wikipedia.org/wiki/Proportionally_fair
Seo, H., & Lee, B. G. (2004, December). A proportional-fair power allocation scheme for fair and efficient multiuser OFDM systems. In Global Telecommunications Conference, 2004. GLOBECOM\’04. IEEE (Vol. 6, pp. 3737-3741). IEEE.
Bechir, N., Nasreddine, M., Mahmoud, A., Walid, H., & Sofien, M. (2014). Novel Scheduling Algorithm for 3GPP Downlink LTE Cellular Network. Procedia Computer Science, 40, 116-122.
Elliott, R. (2002). A measure of fairness of service for scheduling algorithms in multiuser systems. In Electrical and Computer Engineering, 2002. IEEE CCECE 2002. Canadian Conference on (Vol. 3, pp. 1583-1588). IEEE.