Développement d'une solution informatique pour la simulation concrète d'un réseau cellulaire appliquée à la comparaison des stratégies d'allocation de canaux

Directrice de projet
Selma BOUMERDASSI
Docteur de l'université de Versailles
Saint-Quentin-En-Yvelines

Le Conservatoire National des Arts et Métiers propose des formations diplômantes permettant à l'individu d'acquérir les connaissances nécessaires à son métier. Il lui permet également de se prendre en charge par le biais des travaux personnels demandés tout au long de la formation.
Merci donc aux enseignants qui m'ont guidé jusqu'à ce stade et merci d'avance à mes futurs professeurs.

Je souhaite remercier M. PINTE Vincent et M. RAE Alistair pour leurs contributions aux réflexions de départ ainsi qu'au support pour les problèmes mathématiques. Tant il est vrai que ce projet a exploité la totalité des unités de valeurs que j'avais acquise cette année et l'année dernière.

Je souhaite évidemment remercier Mme Selma BOUMERDASSI pour le temps qu'elle nous a consacré.

Merci aussi à mes collègues de travail qui m'ont apporté leur soutien au long et difficile travail de rédaction de ce présent document.

Jamais je ne cesserai de penser à toute la compréhension de ma jeune épouse dont le cœur, le corps et l'esprit ont manqué d'attention de ma part ces derniers jours. Qu'elle soit remerciée chaleureusement de sa patience.

Pour finir, je fait un clin d'œil à mes deux petits chats pour leur soutien à ces travaux. Ceux qui n'ont jamais eu à chercher le seul stylo restant caché malicieusement sous une armoire par deux chats à deux heures du matin ne peuvent affirmer avoir eu des chats :-)

La modélisation mathématique d'un réseau cellulaire a l'avantage de permettre des tests dans les même conditions qu'en réalité mais sans les coûts des essais grandeur nature. Le traitement rapide et systématique de l'information par un programme nous permet de le faire.
Pour être sûr de la fiabilité, c'est-à-dire la justesse et la justification, des résultats, ceux-ci doivent reposer sur les contraintes réelles du système simulé. Ces règles ne sont pas transposables directement à un programme (l'objet de cette étude). C'est pourquoi il faut s'attacher à modéliser le système simulé au moyens d'axiomes dont l'ensemble donne la définition formelle du système.

Une fois les bases posées, il faut introduire la variable temps et, partant, la notion d'événements. Avec eux viennent les algorithmes : le programme-simulation devra faire des choix en fonctions d'événements (temporels) survenant de manière imprévisible (probabiliste) sans en connaître l'existence à fortiori et sans en connaître les conséquences à posteriori.
Le programme sera composé d'éléments agissant en concurrence (mobile et ressources) et gérera les canaux alloués aux mobiles. L'analyste ne pourra que donner les paramètres de départ et analyser les résultats sans jamais agir sur la simulation.
La principale difficulté liée aux réseaux cellulaires fait l'intérêt du programme à venir : il n'existe pas de méthode idéale d'allocation de canaux. Cependant, certains sont plus adaptés que d'autres dans certains cas.
L'études de ces cas est le but de la recherche menée.
Les difficultés de la conception sont de définir le cadre spatio-temporel (formalisme et algorithmes) afin de garantir un programme (en Java) juste.

Table des matières

I Introduction 9

I.1 Présentation 9

I.2 Contribution 9

II Modélisation mathématique 11

II.1 Aspect probabiliste 11

II.2 Aspect environnement 12

II.3 Espace vectoriel 16

III Conception de la simulation par ordinateur 20

III.1 Le langage Java 20

III.2 Le paradigme de la programmation objet 22

III.3 Principaux schémas des sous-systèmes 23

III.4 Les techniques d'allocation de canaux 28

IV. Programmation 30

IV.1 Gestion du temps 30

IV.2 Gestion des événements 32

IV. 3 Plate-forme de développement. 34

V. Exploitation de la simulation. Résultats. 35

V.1 Scénarios des simulations 35

V.2 Modélisation d'une autoroute 36

V.3 Résultats des simulations 37

V.4 Interprétations 39

VI. Conclusions 42

V. Annexe 46

V.1 Sorties du programme 46

V.2 Résultats bruts. 52

Il s'agit de reproduire le comportement d'un réseau cellulaire. Cela permet de diminuer les coûts de mise au point puisque les tests réalisés grandeur nature peuvent être fait plus tard et de façon plus précise.

L'objectif de ce simulateur est d'abord centré sur la reproduction la plus fidèle possible des objets simulés. La comparaison des stratégies d'allocation de canaux (précisé plus loin) s'appuie sur cette simulation. Il ne s'agit donc pas d'imiter les conditions d'un réseau cellulaire mais bien d'en reproduire les composantes afin de simuler le système réel.

La complexité de conception des réseaux mobiles actuels rendent cruciales les études théoriques. Celles-ci doivent nous faire comprendre le fonctionnement des réseaux cellulaires et des acteurs qui y participent. Cependant, l'approche théorique se révèle redoutable car de très nombreux paramètres entrent en ligne de compte.

L'intérêt des simulations en général est ici : au lieu de prévoir l'état ou les résultats du système à tout instant, on définit le système à simuler de manière statique. Ensuite il suffit d'introduire le temps sous forme discrète afin d'y opérer une sorte de récurrence : le système simulé évolue pas à pas sous l'influence de règles d'inférences dont la forme informatique est l'algorithme.

Ainsi avec la donnée du système formalisé et la flèche du temps montrée sous forme d'algorithmes on se construit un moyen d'obtenir des résultats en réduisant la difficulté grâce aux ordinateurs.

Toutefois, cette approche induit d'autres aspects qui seront étudiés dans ce présent document. Il faut, en effet, étudier d'abord le paradigme de la simulation pour envisager correctement l'approche du problème.

La simulation possède un aspect « boîte noire ». On définit les données en entrées (taille du réseau cellulaire, canaux disponibles, charge, etc...) et on reçoit les données en sortie. A aucun moment il ne doit influer sur la simulation en dehors de ce qui est prévu.
On arrive à une situation paradoxale. Habituellement le concepteur maîtrise son programme par sa structure et par ce qu'il va en obtenir. Le résultat est déterminé à l'avance.
Dans d'autres cas, le résultat est inconnu comme pour l'exécution d'un calcul complexe. Mais là aussi le concepteur sait ce qui va se passer et ne fait que déléguer la tâche à la machine qui calcule plus vite que lui.

Ici, c'est différent. S'il est exact que l'auteur maîtrise la totalité des composantes intervenant dans le programme, il ne sait pas à l'avance – du moins pas d'après les spécifications formelles du programme – ce qu'il va obtenir en sortie. Pire : il ne sait pas non plus « comment » cela se passe. Il sait juste, ici, qu'il y a des téléphones mobiles et le réseau cellulaire. Le déroulement des événements est laissé au programme qui est donc indépendant de son concepteur.
Tel est d'ailleurs le but recherché puisque c'est la réalité qui est simulée et elle ne dépend pas de qui la voit.

Finalement, le malheureux concepteur ne peut que regarder ce qui entre d'un côté et ce qui sort de l'autre, c'est exactement la même démarche qu'un astronome. Et pourtant, l'univers observé a été crée par le concepteur lui-même !

Comme cela a été dit plus haut, la simulation échappe à son créateur. La raison vient de l'intervention du Hasard, lequel sépare l'observant et l'observé. Il faut faire tourner le système un certain temps pour en avoir les résultats. Et à partir d'un état donné, on ne peut prévoir l'évolution du système à partir des axiomes du programme. Cela reste évidemment possible grâce à la théorie mathématique, mais en dehors du programme et de ses spécifications.

Le hasard est complètement attaché à la notion d'événement, elle-même liée à l'écoulement du temps dans la simulation. Il intervient en fait dès que le système doit faire un choix pour son évolution :

Elle donne les intervalles entre deux appels. Elle est directement fonction de la topologie du réseau et de la charge. La moyenne des tirages est connue à l'avance et constitue le paramètre de cette variable aléatoire mais chaque tirage est, bien sûr, imprévisible.
Des événements obéissent à une loi de Poisson si :

Ces conditions se prêtent bien aux arrivées des nouveaux appels sur un réseau cellulaire car les utilisateurs du réseau n'appellent pas en fonction des autres (sans mémoire) et l'utilisation du réseau reste constante. Évidemment, cette deuxième hypothèse n'est valable qu'un intervalle de temps très court puisqu'en réalité des fluctuations dans l'utilisation du réseau apparaissent, notamment aux heures de pointes. Ceci est la justification du découpage des tests selon la charge du réseau.

Il s'agit du pendant de la loi de Poisson. Elle décrit la durée des communications. Là aussi son paramètre est le temps moyen de communication. Une variable aléatoire en loi Exponentielle possède des valeurs continues et non entières (discrètes) comme Poisson.

C'est la loi la plus simple. Elle apparaît dès qu'on envisage le Hasard. Elle est utilisée pour effectuer des tirages aléatoires et chaque résultat a la même probabilité d'apparaître qu'un autre. Ici elle est utilisée pour obtenir des nombres entiers.

Les probabilités ne sont pas equiréparties comme pour une loi uniforme. Cela permet de favoriser certains tirages.

Ce procédé est utilisé pour l'endroit d'apparition des nouveaux appels. Selon le lieu simulé, il y aura plus d'appels dans certaines zones que dans d'autres.
Le tirage aléatoire pondéré est aussi utilisé pour les probabilités de déplacement des terminaux mobiles. Selon le lieu simulé, les mobiles auront tendance à prendre une direction plutôt qu'une autre.

La structure de données utilisée par la simulation découle directement de l'univers simulé. D'autres structures s'y ajoutent, des artefacts liés à la programmation, mais n'y jouent pas de rôle prépondérant.

Nous allons détailler chacune des composantes informatique d'un réseau cellulaire.

Il s'agit du plus fin repérage d'un mobile. Lorsque deux mobiles sont physiquement dans la même cellule, ils sont situés au même point dans la cellule, le centre. Les distances exactes entre cellules ne sont donc pas prises en compte et cela rend donc hors de portée la simulation d'allocation dynamique de canaux (DCA).
Chaque cellule dispose en outre de propriétés externes : elles lui sont affectées selon les stratégies d'allocation en vigueur et de l'environnement physique simulé. Il s'agit de la probabilité de nouveaux appels dans la cellule et de la probabilité de déplacement à partir de la cellule. On y ajoute aussi le paramètre de la loi Exponentielle définissant la durée de résidence moyenne dans la cellule.

Il organise un groupe de cellule en grappe de sept cellules. Ici il ne sert qu'à structurer le réseau cellulaire. Mais il pourrait servir dans des développements futurs, à l'allocation de ressources. En effet, certaines stratégies d'allocation confient des fréquences aux cellules et aussi aux motifs.

Il regroupe l'ensemble des motifs. Il a une taille finie et a la topologie d'un tore. En d'autres termes, pour éviter les effets de bords (un mobile en bordure du réseau n'aurait que 3 cellules adjacentes au lieu des six usuelles) un mobile partant en dehors des limites du réseau y revient par l'autre côté. De même, avec la stratégie par emprunt de canaux une cellule en manque de canal située « en haut à gauche » peut emprunter un canal à une cellule « en bas à droite ». L'ensemble des coordonnées possibles dans ce réseau forme un espace vectoriel – à la base du fonctionnement du programme – et qui sera explicité plus loin.

Bien qu'en réalité une communication utilise deux fréquences – une servant pour le parcours des données du mobile vers la borne émettrice, l'autre servant pour le retour – Nous nousen tenons à l'utilisation d'un canal qui a l'avantage de simplifier la conception et de ne pas éloigner le modèle de la réalité qu'il simule.
Un canal est soit libre, soit occupé. Il est géré par un allocateur.

Chaque communication utilise deux fréquences, une pour le trajet mobile-borne, l'autre pour le retour. La bande de fréquence utilisable est limitée. Même si mathématiquement on peut diviser cette bande de fréquences en autant de bandes que l'on veut, celles-ci ne peuvent être trop rapprochées sinon, des interférences co-canal [2] apparaissent.

Le problème s'est déjà posé avec les radios. La gamme de fréquence GO (Grandes Ondes), de portée nationale, ne peut accueillir beaucoup de stations de radios. La solution à se problème a été l'utilisation de fréquences plus élevées ayant une portée moindre et l'établissement d'un plan de fréquence.

Ainsi naquit la bande FM (88 Mhz à 108 Mhz). Chaque fréquence de la bande FM est utilisée de nombreuses fois mais en des lieux différents. Une même fréquence correspondra à des radios différentes en des lieux différents. L'inconvénient de cette méthode est qu'une radio voulant émettre sur la France entière sera obligée de changer de fréquences selon les zones à moins que, cas non rencontré, sa fréquence soit libre partout ! Notons que des systèmes tels que RDS permet de régler automatiquement la fréquence lorsqu'on quitte une zone, notamment en voiture.

La solution retenue pour les réseaux de téléphones mobiles est semblable : le mobile dispose d'un canal à proximité d'une borne réceptrice et a la possibilité d'en changer si sa fréquence est occupée par un autre téléphone mobile.

Il s'agit de la raison d'être de ces travaux. La simulation a pour but d'en essayer plusieurs et il s'agit donc de l'un des paramètres d'une simulation.
L'allocateur gère ses canaux et il est le seul à les gérer. Il répond aux demandes des cellules qui elles-même répondent aux demandes des mobiles. Cette stratification sera clarifiée dans la partie II de ce document. Un allocateur peut demander un canal à un autre allocateur.

Il s'agit d'un composant à part dans la simulation. Une fois crées ils échappent à tout contrôle par le programme car ils agissent comme des processus indépendants.
En revanche, ils déclarent d'eux-même les événements qui se déroulent pour eux. Ce sont les scribes qui sont chargés de recueillir ces événements.

Il recueille les événements déclarés par les terminaux mobiles. Il contient donc la totalité de l'état d'une simulation et les résultats à la fin de celle-ci.
Il a notamment la fonction d'arrêter la simulation une fois les critères de stabilité atteints.

Le vecteur permet le positionnement des mobiles, des cellules et des motifs. Il permettrait aussi de positionner d'autres objets si nécessaire.
A une position précise sur le réseau cellulaire correspond un vecteur. L'analogie est parfaite avec les vecteurs couramment utilisés en mathématiques si ce n'est qu'ils ne prennent que des valeurs entières.

Sur le schéma ci-contre est donné l'architecture du réseau cellulaire : il est composé de motifs (une couleur) eux-même composés de cellules. Il est évident qu'on ne peut pas utiliser tel quel le système de vecteurs classique comme on le ferait si les motifs étaient disposés en carrés composés de cellules carrées.

De plus, il faut pouvoir réaliser les opérations suivantes :
- somme de vecteurs
- soustractions de vecteurs
- déplacement d'une direction à partir d'un vecteur
- composer une position en fonction du motif et de la cellule dans le motif, en une position de cellule.
- trouver la position sous forme motif et cellule dans le motif en fonction d'une position de cellule. Il s'agit de l'opération inverse de la précédente.
- déterminer la distance entre deux centres de deux motifs.

Soient deux point A et B du réseau. Le réseau étant par nature fortement connexe, il existe toujours un chemin de longueur finie reliant A et B.
D'autre part, chaque cellule a six voisines ce qui permet de définir les six déplacements unitaires possibles.
Notons ces vecteurs v1, v2, v3, v4, v5, v6. v1 est le vecteur obtenu par le déplacement vers la cellule en haut et à droite ; les autres se déduisent par le déplacement anti-horaire. v0 est le vecteur nul.

Le parcours de A vers B est obtenu par une combinaison linéaire des vecteurs v1 à v6. Cet ensemble de vecteurs est donc générateur de l'ensemble des positions possibles dans le réseau. Mais il n'en forme pas une base.

Ainsi v2 et v3 permettent par composition linéaire de désigner de manière unique chaque déplacement entre cellules puisque { v2, v3 } ne contient pas de vecteurs dépendants.

Appelons

le vecteur dénommé (1,0) et

le vecteur dénommé (0,1).
Soit une cellule désignée Origine du repère tels que ses coordonnées soient (0,0), c'est-à-dire que sa position s'écrit :

.
{ 0,

} forme le repère associé au réseau cellulaire et permet d'associer à chaque cellule une position sous la forme d'un couple d'entiers relatifs.

Une fois défini le repère associé aux cellules, il reste à répéter l'opération pour les motifs.

Soient

les deux vecteurs de bases pour les motifs. Le raisonnement est semblable en tout points au précédent car les motifs sont agencés de manière similaire aux cellules.

Convenons d'une notation pour repérer les motifs [X,Y] et d'une notation pour repérer les cellules (x,y).

La conversion de coordonnées motif en coordonnées cellule est évidente. Par contre, l'inverse va demander plus de précaution du fait de la présence de nombres fractionnaires.

1) Obtention du motif contenant la cellule désignée par le vecteur.
2) Transformer les coordonnées du motif obtenu en coordonnées de vecteur.
3) Soustraire des coordonnées réelles les coordonnées trouvées en 2).

Du fait de l'unicité des coordonnées d'une cellule, il est garanti que l'étape 3 nous fournit un vecteur unitaire unique désignant la cellule dans son motif.

Le problème reste encore de déterminer le motif contenant une cellule donnée.
Sept cas sont possibles, un cas par cellule du motif. Tous calculs faits, il s'avère que les coordonnées du motif soient fournies en prenant l'arrondi entier le plus proche.

// [X,Y] est évidemment converti en vecteur de cellule avant la soustraction.
Fin

Il est évident que la conversion des coordonnées d'un motif (en X, Y) sera aisée.
Si une cellule est caractérisée de la sortie [2,3]4
Avec [2,3] les coordonnées de la cellule et 4 le vecteur unitaire (v4) du déplacement dans le motif, on trouve facilement les coordonnées de la cellule. Il suffit d'appliquer le système d'équation donnant (x,y) en fonction de [X,Y] et d'y additionner le vecteur unitaire correspondant.

Le langage utilisé pour implémenter la simulation est Java. Il présente les avantages suivants :

La version du Jdk (Java Development Kit) utilisée pour le développement est la 1.4 mais le code reste compatible avec la version 1.3.

L'auteur a choisi Java car il ne connaissait pas du tout ce langage, ce projet était une bonne occasion de s'y mettre.
C++ avait été écarté d'emblée du fait de sa toute relative portabilité.
Turbo Pascal avait aussi été écarté puisqu'il n'existe pas de version standard sous Linux et il manque de puissance par rapport à Java.

Le développement de ce projet a suivi le cycle en V. Cependant il y a eu de nombreux retours notamment lorsqu'il a fallu intégrer la gestion des événements en temps réel. Fort heureusement, la conception objet de Java a permis au programme d'évoluer de manière stable. Même s'il a fallu prototyper la simulation juste après le cahier des charges.

En effet, la relative connaissance de Java de l'auteur et les contraintes liées au comportement parallèle des mobiles imposaient d'eux même de réaliser des tests complets avant de commencer concrètement le projet.

Dès lors qu'on commence à imaginer les bases de la simulation on découpe tout à fait
intuitivement le programme en sous-programme et ses composants en objets.

Java, en tant que langage orienté objet, permet de décomposer le problème global en sous problèmes, permettant ainsi un développement cohérent.

Vont suivre une description textuelle et imagée des objets intervenants dans le projet avec leurs liens.

Le programme lance une série de simulation. Chaque simulation reçoit des paramètres externes : la charge, la stratégie et l'environnement physique. A la fin de la simulation, un scribe est retourné par la simulation.
Pendant le déroulement d'une simulation, des nouveaux appels sont lancés à la cadence dictée par la charge. La base du programme est la mise en concurrence des terminaux mobiles et des allocateurs de ressources. Les premiers ont tendance à épuiser les ressources des seconds.

Les événements survenants pour les mobiles sont recueillis par un scribe. L'ensemble des scribes permet d'obtenir les résultats des simulations.

Les mobiles se déplacent dans le réseau de cellule en cellule. Leur temps de résidence dans une cellule dépend de celle-ci. La cellule destination d'un déplacement dépend également de la cellule de départ car il peut exister des directions de déplacement privilégiés.

La gestion en parallèle des mobiles est indispensable au fonctionnement du programme. Le nombre conséquent de mobiles devant coexister dans le même instant peut monter à 1000 unités.
Pour permettre cela, il est fait plusieurs hypothèses :
1) Chaque mobile est incarné par un processus dont il hérite la caractéristique de se mettre à l'état endormi.

2) La durée de traitement est inférieure au temps qu'un mobile est susceptible de passer dans une cellule.

3) Les mobiles en attente consomment très peu de temps processeurs. Normalement c'est le cas : l'ordonnanceur système ne leur accorde que peu de temps à cet état-là.

Nous verrons que le temps de traitement n'est pas à négliger mais qu'il existe une méthode pour le prendre en compte.

Comme il a été dit plus haut, on ne peut pas négliger le temps nécessaire au traitement des demandes de canaux ou de déplacement des mobiles.

A titre d'illustration prenons l'exemple suivant où le processus doit patienter 1500 ms avant de reprendre la main. Le traitement, fait avant l'attente, dure 100 ms.

Chrono test = new Chrono() ; // Lance le chronomètre.
Traitement // dure 100 ms
Sleep(1500)
System.out.println(chrono) ; // Indique qu'il s'est écoulé 1600 ms

Solution 1 : Il faut rectifier l'argument de sleep() par 1400.
Problème : et si la durée de traitement fluctue ?

Avant le traitement il faut calculer l'instant où devra se terminer le sommeil du processus. Ensuite, avant l'exécution de Thread.sleep() il faut calculer l'intervalle de temps séparant l'instant présent de l'instant prévu de réveil.
Cela donne :

Chrono test = new Chrono() ; // Lance le chronomètre.
Long instantFin = Chrono.absolu(1500) ; // conversion en temps absolu.
Traitement() ; // dure un certain temps en ms
sleep(Chrono.relatif(instantFin)) ;
System.out.println(chrono) ; // Indique qu'il s'est écoulé 1500 ms :-)

Chrono.absolu(délai) = System.currentTimeMillis() + délai
Chrono.relatif(instant) = instant - System.currentTimeMillis()
Où System.currentTimeMillis() est le temps absolu délivré par le système.

Ce procédé possède une faille. Si le traitement a une durée plus élevée que le temps d'attente, le calcul relatif – qui comporte une soustraction – renverra une durée négative. Ce qui ne manquera pas de causer des ennuis au programme. D'où l'hypothèse 2 pour le fonctionnement du mobile.
Si ce cas se présente, cela entraîne la non-fiabilité de la simulation. Il est important que la machine hébergeant la simulation soit capable, non pas de faire tourner plus vite la simulation mais de la gérer au plus vite. Les temps totaux pris par la simulation ne sont pas influencé par le simulateur.

Ce composant est incorporé dans le Scribe qui recueille les événements des mobiles, il provoque l'arrêt de l'émission des appels dès que le grade de service tends à se stabiliser.

Lorsqu'un mobile est crée ou lorsqu'il se déplace, il a besoin d'une ressource et il rend de toute façon celle qu'il utilisait. La demande de canal est faite par le mobile lui-même à la cellule. La cellule demande ensuite à son allocateur. L'allocateur renvoie ensuite un canal si possible.
Ce cloisonnement a plusieurs utilités :

- La solidité du code : quoiqu'on fasse au niveau des allocateurs, il n'y a rien à modifier au comportement des mobiles. Les mobiles continueront toujours à demander les canaux aux cellules.
- La généricité du code : Les allocateurs dérivent tous d'une interface Java. La cellule « sait » qu'on lui assignera un allocateur mais elle ne le « sait » que pendant l'exécution. On peut ainsi interchanger les techniques d'allocations pourvu qu'elles utilisent les mêmes méthodes (allocation, libération, ...)
- La flexibilité du code : dans des modes de fonctionnement (non étudiés ici) les canaux ne sont pas tous compatibles entre eux. Nativement, les canaux ne comportent pas de routine de test d'interférence. Grâce aux mécanismes d'héritage de Java, on peut enrichir les canaux de telles fonctionnalités. Ainsi, pour savoir si deux canaux seront compatibles, il suffira de leur demander !

Seules les techniques utilisées dans le cadre de cette simulation seront étudiées. Vous trouverez en [3] tous les détails à ce sujet.

Chaque cellule dispose du même nombre de canaux. Lorsque la cellule ne dispose plus de canaux, les nouveaux appels sont bloqués et les appels des mobiles arrivant sur la cellule sont coupés. La fin de l'appel libère le canal utilisé.

Chaque cellule a un nombre particulier de canaux. Cela offre l'avantage de privilégier les zones à forte densité d'appel. Les performances sont donc meilleures que FCA (simple) si la répartition initiale des canaux est bien faite.
Il faut noter que l'initialisation d'un réseau cellulaire avec un nombre de canaux variable selon les cellules nécessitera le recours à un fichier, et par là, demandera la conception d'un interpréteur pour la lecteur du fichier en entrée.

Cette stratégie peut d'emblée se découper en deux sous-variantes : avec répartition initiale uniforme ou non uniforme. Dans ces deux cas de figure, une cellule dépourvue de canaux et qui reçoit une demande de la part d'un mobile va emprunter un canal à l'une de ses voisines si possible. Une cellule qui reçoit une demande de canal de la part d'une autre cellule ne demandera pas à l'une de ses voisines si elle est elle-même en famine. Cela pourrait engendrer des verrous mortels comme cela sera expliqué dans la partie consacrée à la programmation.

Le premier choix est l'emprunt à la voisine la plus riche. C'est l'option retenue pour cette simulation. On pourrait imaginer qu'il existe d'autres critères : ne pas demander de canal à certaines cellules qui doivent pouvoir accepter une forte montée en charge.

Remarque : cette étude porte sur FCA uniquement. Les techniques FCA non-uniforme et FCA Emprunt de canaux seront croisées !

Il s'agit d'un prolongement de la stratégie précédente : les canaux de la cellule sont divisés en groupes dont l'un reprend les fonctionnalités décrites plus haut. Les autres peuvent être à usage exclusif de la cellule ou réservés pour d'autres cas.
Il ne sera pas implémenté dans le programme.

Ils sont écartés de l'étude. Ces stratégies nécessitent de prendre en compte le calcul d'interférence et donc le positionnement exact des mobiles, ce qui reste hors de portée des vecteurs tels qu'ils ont été décris plus haut.

Une fois les bases théoriques posées et la formalisation du programme de simulation, nous abordons dans cette partie la réalisation concrète du projet. Il n'est évidemment pas question d'effectuer une analyse du code source. En fait, nous allons faire l'inverse.
La démarche sera similaire à celle de la partie précédente : nous allons en déduire les algorithmes nécessaires à la conception. De ce fait, le code Java qui sera montré en exemple se lira exactement comme du pseudo-code d'algorithme.

La charge est l'un des paramètres de chaque simulation. Une fois le réseau cellulaire initialisé (probabilité d'apparition de nouveaux appels, nombre de canaux, etc...), la charge détermine complètement le délai moyen entre deux appels, en fait la loi de Poisson associée.
De même le temps apparaît pour la durée des appels (en loi de Poisson) et pour la durée de résidence dans les cellules.
Le temps permet également de connaître la chronologie des événements survenus aux mobiles. Ainsi peut-on interroger le scribe pour savoir ce qu'il s'est passé car chaque événement se voit marqué de son instant d'arrivé.

System.currentTimeMillis() sera la seule fonction native de Java a être utilisée pour la gestion du temps. Cette méthode retourne un entier dont la définition est « le nombre de millisecondes séparant l'instant présent du mercredi premier janvier 1970. ». Les instants actuels étant supérieurs à cette date, cette valeur peut être considérée comme le temps absolu.

Le programme manipule des durées alors que le système calcule en temps absolu. Cela nécessite des conversions, notamment pour éviter la perte de délai du au traitement.

Comme cela a été dit à l'introduction, le programme doit interagir le moins possible avec ce qu'il simule. Aussi est-il hors de question d'espionner en quelque manières que ce soit l'activité des mobiles.
Ce sont les mobiles eux-mêmes qui prennent le soin d'avertir le scribe dès qu'un événement survient. Voici les événements que réceptionnent les scribes :

Cet événement est déclenché lorsqu'un appel n'est pas bloqué à son lancement. Cela permet de connaître le nombre total d'appels non bloqués.

Déclenché lorsqu'un appel ne peut commencer faute de canal. Avec le nombre d'appels en création, cela donne le total d'appels.

Déclenché par la fin d'un appel. Permet de comptabiliser le nombre d'appels passés sans encombre.

Déclenché par un appel non bloqué mais qui n'a pu trouver de canal en cours de déplacement.

Déclenché par un appel lors de son déplacement. Permet de tracer le parcours du mobile.

Selon la charge, la durée de résidence peut être plus petite que la durée de traitement. Dans ce cas Chrono.attenteJusque(this.chrChgtCellule) lève une exception, laquelle est comptabilisée comme un « plantage ». Le canal éventuellement détenu par le mobile est liberé.

Après l'exécution de la simulation, le scribe permet d'obtenir tous les détails nécessaires : nombre d'appels, blocages, terminaisons, coupures, plantages. Il délivre les taux en rapport avec les mesures ainsi que le grade de service.
Il permet aussi de journaliser les événements afin d'avoir une trace exacte du déroulement de la simulation.

Cela fait bien apparaître que la coupure d'un appel (donc déjà en communication) est plus grave que l'échec de la tentative d'appel. Dans ce cas-là, l'usager peut renouveler son essai.

La plate-forme de développement est un Pc tournant sous Windows 2000. Le kit de développement Java 1.4.0 est utilisé. Jext est l'environnement de développement integré.

Le programme ne possède pas d'interface graphique car le ratio besoin sur temps est insuffisant. Le programme récupère ses entrées pour partie dans un fichier, et pour l'autre dans le code source.

Les résultats sont sortis sur fichiers tandis que les phases d'avancement s'affichent par lignes sur l'écran.

Nous disposons de deux environnement (plat et autoroute), de deux styles de répartition de canaux (homogène ou autoroute) et de deux styles d'allocations (uniforme et emprunt de canaux).

La modélisation d'une autoroute influe sur :
- les probabilité des lieux d'apparition des nouveaux appels.
- les probabilité de direction de déplacement des mobiles.
- les temps de résidence dans les cellules (plus rapide sur autoroute)
- l'affectation idéale des canaux aux cellules (la répartition homogène ne convient pas).

Chaque test sera mené sur un intervalle de charge de 1 à 15 (pas de 2). Cela nous fait donc 8 tests par lignes, soit 48 tests.

Comme chaque simulation prends (d'après les premiers test) au moins 45 minutes, il faut au moins trois jours consécutifs de calculs !

Le réseau cellulaire choisi occupe 3 motifs en largeur et 3 motifs en longueur. L'autoroute (trait rouge) traverse le réseau et croise un échangeur (en rouge également).

Les directions privilégiées sont évidemment celles de l'autoroute et le temps de résidence dans une cellule est d'autant plus petit que la cellule est proche du centre de l'autoroute. Avec une allocation non-uniforme, le plus grand nombre de canaux se retrouve sur l'autoroute et son échangeur.

Les croix signalent les endroits où l'autoroute influe le plus sur les paramètres physiques du réseau.
Les plus représentent une influence moindre.

Il faut noter la présence d'endroits supplémentaire (+ et x) sur le milieu-gauche du schéma afin d'enrichir la modélisation.

Pour la rédaction du fichier de configuration, il faut lire les cellules dans cet ordre : lire les motifs d'abord de gauche à droite puis de bas en haut, pour chaque motif lire les cellules dans le sens horaire en commençant par cellule du milieu puis celle en haut à droite.
Dans les cas où il faut y inclure les voisines (probabilité de déplacement), il faut relever les voisines dans le même ordre mais sans la cellule elle-même (6 voisines à compter).

Il s'agit des trois premières simulations sur un environnement plat :
- allocation simple avec 12 canaux par cellule (U12/S)
- allocation simple avec 24 canaux par cellule (U24/S)
- emprunt de canaux avec 24 canaux par cellule (U24/Ec)

Les trois couleurs représentent chacune une stratégie. Les types de traits (respectivement lignes, points , pointillés) correspondent aux mesures (respectivement blocage, coupure et grade e service).

Ce sont les trois dernières simulations sur une autoroute :
- allocation simple avec 24 canaux par cellule (U24/S)
- répartition des canaux non uniforme (Nu/S)
- répartition des canaux non uniforme et emprunt de canaux (Nu/Ec)

Nous pouvons voir que, contrairement à ce qui est logique, le grade de service diminue dès que la charge dépasse 1. Ceci est dû au fait de la diminution du taux de coupure et l'augmentation toute relative du taux de blocage. La mesure du grade de service n'est donc pas pertinente ici. Elle l'est à des charges plus faibles.
Pour une charge croissante, le grade de service part de 0 et augmente pour arriver à son maximum et tends vers une asymptote.

L'évolution des courbes est sensiblement la même pour chaque stratégie. Si les comparaisons avec la croissance de la charge n'apportent pas d'éléments intéressants, la comparaison par stratégie l'est plus :

En environnement plat, c'est-à-dire sans structure spécifique, la stratégie FCA/Ec montre sa supériorité sur le FCA/S. Le réseau étant mieux exploité en FCA/Ec, les terminaux mobiles qui ont pu commencer leur appel obtiennent plus souvent les fréquences lorsqu'il se déplacent.
Bien que le taux de blocage soit plus grand en FCA/Ec qu'en FCA/S, le grade de service est moins grand en FCA/Ec qu'en FCA/S du fait de l'importance du taux de coupure.

FCA/Ec est donc meilleur que FCA/S.
Cela devrait être vrai quelque soit la charge puisque l'emprunt de canal autorise tout ce qu'autorise la stratégie simple, mais permet en plus d'obtenir un canal si la cellule n'en a plus à fournir.

On remarque les mêmes tendances décrites plus haut. Il est intéressant de constater la différence induite par un réseau cellulaire non homogène.

Contre tout attente, la répartition non-uniforme des canaux aurait dû donner de meilleurs résultats sur un milieu « autoroute ». Ce qui est encore plus marquant est la forte amélioration constatée avec l'ajout de l'emprunt de canaux.

On remarque toutefois la remarquable amélioration due à la stratégie Emprunt de Canaux.

Vu l'intervalle de charge (1-15) nous pouvons constater une étonnante diminution du grade de service quand la charge augmente. En fait, le grade de service est bien en augmentation mais pour des facteurs de charges moindres.

L'observation des taux de blocage et des taux de coupure sont plus éloquents. Dans tous les cas l'on observe que l'augmentation du taux de blocage coïncide avec la diminution du taux de coupure. La charge étant la même dans chacun des tests, la réussite de nombreux nouveaux appels est incompatible avec la fin normale des appels.
Le nombre de canaux étant toujours le même au total (même sur autoroute) il faut faire un compromis entre le nombre de nouveaux appels acceptés et le nombre d'appels qui finissent normalement.

La distinction entre les stratégies se fait donc sur le grade de service (variations faibles quand même) et surtout sur l'évolution des taux de blocage et de coupure.

Sans surprise, la stratégie par emprunt de canaux est la meilleure dans les deux cas de figure. Le taux de coupure et y est le plus bas.
On note aussi l'importance d'une bonne répartition des canaux selon la fréquentation des lieux (cellule) et selon les déplacements constatés. D'autant plus que le déplacement sur autoroute engendre des changements de cellules plus fréquents.

La bonne répartition des canaux en Fca-Nu améliore sensiblement les performances.

La combinaison d'une répartition non-uniforme (adaptée au terrain) et de l'emprunt de canaux donne les meilleurs résultats.

Le cœur de la simulation repose sur le traitement en temps réel du fonctionnement des terminaux mobiles.
Une autre méthode consistait à ne pas faire appel à des processus et à simuler le fonctionnement parallèle à l'aide d'une boucle. Des tests doivent alors être faits pour détecter la possibilité de déplacement, de fin, etc... d'un mobile.

Il existe une dernière méthode qui réunit les avantages des deux autres. On constate en effet qu'il y a un gaspillage de temps dans la première méthode et un gaspillage de ressources processeurs dans l'autre.

Si l'on observe le fonctionnement du présent programme, on peut constater qu'il existe des périodes (courtes) pendant lesquelles rien ne se fait. C'est du temps gaspillé. Il faudrait pouvoir prévoir les périodes d'inactivité.
En fait, si on réduit le déroulement de la simulation à une succession d'événements ordonnés temporellement, on s'aperçoit que le temps n'y a plus d'importance mais que seul compte l'ordre des événements.
Cependant, dans l'état actuel des choses on ne peut pas savoir cela avant de l'avoir fait.

Supposons une simulation avec un seul terminal mobile. Une fois son appel commencé, il se terminera sans problème. Ici, il n'y a pas besoin de savoir combien de temps il s'écoule entre ses différents états car il n'y aurait ni blocage ni coupure d'appel..
Si on introduit un deuxième mobile, trois cas se présentent :

1) Les mobiles se déplacent à chaque fois dans des zones différentes. Le raisonnement d'avant reste valable. Il n'y a ni blocage, ni coupure.

2) Les mobiles se croisent mais il reste à chaque fois assez de canal. Même raisonnement qu'avant.

3) Les mobiles se croisent et à l'un de ces croisements il n'y a pas assez de canal (l'un arrive toujours avant l'autre) pour l'un d'eux. Celui qui n'a pas de canal est soit bloqué s'il s'agit du début de son appel, soit coupé. L'autre peut continuer son appel jusqu'à son terme.

En plus de ces constatations, nous savons que la trajectoire de chaque mobile est indépendante. Ils (dans la réalité) effectueraient leur trajet indépendamment les uns des autres.
Prenons le problème à deux mobiles, et que nous fassions les choses dans cet ordre :

1) On relève les instants où se produisent les événements pour chacun d'eux comme s'il était seul.

2) On ordonne la totalité des événements relevés dans une liste simple en conservant la date de l'événement et le mobile concerné.

3) On parcours la liste en maintenant en mémoire les paramètres des cellules et notamment le nombre de canaux libres et on « exécute » chaque événement en modifiant les ressources comme il se doit.

Le seul cas d'incompatibilité est le refus d'allocation de canal par une cellule. Dans ce cas la communication du mobile est coupée ou bloquée et les événements du mobile dans la liste sont retirés !

A et B sont deux mobiles se trouvant dans un réseau composé de cellules en ligne, numérotée de 1 à 3. Ils ne peuvent se déplacer que de 1 à 2, 2 à 3 ou l'autre sens.

Si on fixe à un le nombre de canaux, A sera coupé au milieu de son appel car il ira dans une cellule déjà occupée par B. D'où l'évolution suivante du nombre de canaux de la cellule 2 :

Le nombre de canaux de la cellule 2 descend en-dessous de zéro. Évidemment, cela signifie que la communication A est coupée.
Et le raisonnement est valable par récurrence sur un nombre quelconque de mobiles.

Scribe : r31982 t23687 b3177 c5118 p0 %b9.933712713401288 %c16.002751547745607 %p0.0 g1.6996122819085735 gs1.695256558581658 mm583 e9.649158694013948E-5

La ligne « Scribe » est la sortie brute, pour vérification, des résultats de la simulation. On peut y lire :

Ce fichier est utile pour connaître le comportement exact pendant la simulation. Il a d'ailleurs été utilisé intensément lors des premiers tests de validation de la simulation.

------------------------------------------------------------------------------------------

[1] Mme BOUMERDASSI Selma.
Thèse du 18 décembre 1998. Université de Versailles, Saint-Quentin-en-Yvelines.

[3] Katzela et Naghshimeh.
Channel Assignment Schemes for Cellular Mobile. Telecommunication Systems – A Comprehensive Survey

Environnement	Répartition des canaux / nombre	Stratégie d'allocation	Commentaire
Plat	Uniforme / 12	Simple	Plat/U12/S Test 12 canaux
Plat	Uniforme / 24	Simple	Plat/U24/S Avec 24 canaux, les performances sont meilleures.
Plat	Uniforme / 24	Emprunt de canaux	Plat/U24/Ec On optimise encore les performances.
Autoroute	Uniforme / 24	Simple	Auto/U24/S Avec l'autoroute, les résultats changent.
Autoroute	Non-uniforme	Simple	Auto/Nu/S On améliore...
Autoroute	Non-uniforme	Emprunt de canaux	Auto/Nu/Ec .. encore !