UNIVERSITÉ DE MONTRÉAL

OPTIMISATION DU PLACEMENT ET DE L’ASSIGNATION DE

FRÉQUENCES D’ANTENNES DANS UN RÉSEAU DE
TÉLÉCOMMUNICATIONS

ALEXANDRE MARTY
DÉPARTEMENT DE MATHÉMATIQUES ET GÉNIE INDUSTRIEL
ÉCOLE POLYTECHNIQUE DE MONTRÉAL

MÉMOIRE PRÉSENTÉ EN VUE DE L’OBTENTION DU DIPLÔME DE

MAÎTRISE ÈS SCIENCES APPLIQUÉES
(MATHÉMATIQUES ET GÉNIE INDUSTRIEL)
NOVEMBRE 2011

c Alexandre Marty, 2011.

 UNIVERSITÉ DE MONTRÉAL

ÉCOLE POLYTECHNIQUE DE MONTRÉAL

Ce mémoire intitulé :

OPTIMISATION DU PLACEMENT ET DE L’ASSIGNATION DE

FRÉQUENCES D’ANTENNES DANS UN RÉSEAU DE
TÉLÉCOMMUNICATIONS

présenté par : MARTY Alexandre

en vue de l’obtention du diplôme de : Maîtrise ès sciences appliquées
a été dûment accepté par le jury constitué de :

M. LE DIGABEL Sébastien, Ph.D., président

M. AUDET Charles, Ph.D., membre et directeur de recherche
M. HERTZ Alain, Doct. ès Sc., membre et codirecteur de recherche
Mme SANSÒ Brunilde, Ph.D., membre
 iii

Résumé

Les nombreux services de communication mobile disponibles aujourd’hui reposent

sur des réseaux d’infrastructures exploités par des opérateurs de télécommunications.
Pour rester compétitifs, ils doivent s’adapter à la demande du marché et faire face
à la croissance permanente du nombre d’utilisateurs ainsi qu’à l’augmentation de
leurs exigences en termes de services et de couverture géographique. Il leur faut pour
cela constamment améliorer leurs réseaux en mettant à niveau leurs installations
existantes et en en ajoutant de nouvelles. Le déploiement et l’entretien d’un réseau de
télécommunications étant très onéreux, la minimisation du coût lié aux infrastructures
est un enjeu très important pour les opérateurs.
Or les réseaux de télécommunications sont aujourd’hui devenus des systèmes très
complexes, composés d’éléments variés et dépendant de très nombreux paramètres qui
doivent être pris en compte lors de leur conception. La difficulté de conception d’un
réseau est donc très élevée et il serait intéressant pour les opérateurs de pouvoir se
munir d’outils d’optimisation conçus pour les aider dans cette tâche. Le présent travail
se propose de poser les bases d’une nouvelle méthode d’optimisation d’un réseau de
télécommunications, dans le but de permettre le développement futur de tels outils
d’aide à la décision pour la conception de réseaux de télécommunications.
Les constituants de base d’un réseau de télécommunications sont les antennes ou
stations de base, qui doivent être placées judicieusement sur le territoire à couvrir
pour fournir un service à tous les usagers. La difficulté de placement des antennes
provient du fait que des antennes émettant aux mêmes fréquences interfèrent entre
elles, donnant aux zones de couverture de chacune des formes irrégulières et sensibles
aux variations de position et de fréquence. La méthode développée ici s’attache à op-
timiser la localisation des antennes conjointement avec leur assignation de fréquence.
La démarche utilisée se décompose en deux étapes principales. Il est d’abord né-
cessaire de développer un modèle de réseau de télécommunications adapté à l’opti-
misation que l’on souhaite en faire et de l’implémenter sous forme de programme
informatique afin d’effectuer des simulations. Le modèle doit être suffisamment précis
pour donner des résultats concordant avec la réalité mais sans être trop complexe pour
que les simulations puissent s’exécuter en un temps court. Un algorithme d’optimi-
 iv

sation est ensuite développé, utilisant une méthode de recherche directe, l’algorithme
Mads, et une métaheuristique, la recherche tabou, et traitant la simulation de réseau
comme une boîte noire à optimiser.
La méthode est testée avec différentes instances et les résultats sont présentés et
analysés. Les résultats obtenus sont encourageants, en particulier avec l’instance cor-
respondant à un territoire réel. La méthode semble donc pouvoir être utilisée comme
point de départ pour le développement d’outils d’optimisation de réseaux de télécom-
munications.
 v

Abstract

All the mobile communication services available today rely on networks operated
by telecommunications companies. To remain competitive, they have to conform to
the market and cope with the ever growing number of users and the increase in their
demands in terms of services and geographic coverage. They need to constantly im-
prove their networks by upgrading their facilities and adding new ones. Expanding
and maintaining a telecommunications network is very expensive, therefore minimiz-
ing the costs related to networks is a very important issue for operators.
And yet, telecommunications networks have now become very complex systems,
made up of various elements and depending on a large number of parameters which
have to be considered when designing a network. Thus it is a difficult task and it
would be very interesting for operators to have optimization tools to help them. The
present work intends to lay the foundations for a new telecommunications network
optimization method, in order to enable the future development of tools to help in
the process of designing a network.
The components at the root of a telecommunications network are antennas or base
stations, which have to be placed wisely on the target territory in order to supply
all users with mobile service. Placing antennas is difficult because antennas emitting
at the same frequencies interfere, and the shape of their coverage zones can then be
irregular and sensitive to variations of localization and frequencies. The goal of the
method developed here is to optimize the localization of the antennas together with
their frequency allocation.
The approach used in this work breaks down into two stages. First, a telecommu-
nications network model suitable to the optimization is developed and implemented
as a computer program in order to perform simulations. The model needs to be
accurate enough to give realistic results, but not to complex so as to allow quick
simulations. An optimization algorithm is then developed, which uses a direct search
method, the Mads algorithm, and a metaheuristic, the tabu search, and handles the
network simulation as a black-box.
The method is tested on various instances and results are presented and analysed.
The results are encouraging, especially with the instance corresponding to an actual
 vi

territory. Therefore the method seems a promising first step in the development of
telecommunications networks optimization tools.
 vii

Table des matières

RÉSUMÉ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v

TABLE DES MATIÈRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii

LISTE DES TABLEAUX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii

LISTE DES FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii

LISTE DES ALGORITHMES . . . . . . . . . . . . . . . . . . . . . . . . . . . xv

LISTE DES ANNEXES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi

LISTE DES SIGLES ET ABRÉVIATIONS . . . . . . . . . . . . . . . . . . . xvii

CHAPITRE 1 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . 1

CHAPITRE 2 LES RÉSEAUX DE TÉLÉCOMMUNICATIONS . . . . . . . 5

2.1 Généralités sur les canaux de communication . . . . . . . . . . . . . . 5
2.1.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2 Spectre de fréquence d’un signal . . . . . . . . . . . . . . . . . 5
2.1.3 Bande passante d’un canal . . . . . . . . . . . . . . . . . . . . 6
2.1.4 Adaptation au canal . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Débit de données et bande passante . . . . . . . . . . . . . . . . . . . 8
2.2.1 Capacité d’un canal de communications . . . . . . . . . . . . . 9
2.2.2 Ondes radioélectriques . . . . . . . . . . . . . . . . . . . . . . 10
2.2.3 Division du spectre radiofréquence . . . . . . . . . . . . . . . 10
2.2.4 Réglementation . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Propagation des ondes . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.1 Modèle de propagation dans le vide . . . . . . . . . . . . . . . 13
2.3.2 Propagation en présence d’obstacles . . . . . . . . . . . . . . . 14
2.3.3 Modèle retenu . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
 viii

2.4 Rapport signal-bruit et zone de couverture . . . . . . . . . . . . . . . 17

2.4.1 Rapport signal-bruit . . . . . . . . . . . . . . . . . . . . . . . 17
2.4.2 Critère de qualité du signal . . . . . . . . . . . . . . . . . . . 18
2.4.3 Zone de couverture . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.4 Détermination du rapport signal-bruit . . . . . . . . . . . . . 19
2.5 Assignation de fréquences . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.1 Multiplexage et division en canaux . . . . . . . . . . . . . . . 21
2.5.2 Groupes de canaux . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5.3 Zones de couverture . . . . . . . . . . . . . . . . . . . . . . . 23
2.6 Méthodes d’optimisation actuelles . . . . . . . . . . . . . . . . . . . . 24
2.6.1 Optimisation du placement . . . . . . . . . . . . . . . . . . . 24
2.6.2 Optimisation de l’assignation de fréquences . . . . . . . . . . . 26
2.6.3 Optimisation simultanée du placement et de l’assignation de
fréquences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

CHAPITRE 3 MODÉLISATION ET SIMULATION . . . . . . . . . . . . . 29

3.1 Entrées et sorties de la boîte noire . . . . . . . . . . . . . . . . . . . . 29
3.2 Modèle physique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.2 Modèle de propagation des ondes . . . . . . . . . . . . . . . . 30
3.2.3 Puissance de canal et interférences . . . . . . . . . . . . . . . 33
3.2.4 Rapport signal-bruit . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.5 Zone de couverture . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.6 Zone de couverture effective . . . . . . . . . . . . . . . . . . . 35
3.2.7 Nombre d’usagers . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.8 Sorties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.1 Discrétisation du plan . . . . . . . . . . . . . . . . . . . . . . 37
3.3.2 Puissance reçue des antennes . . . . . . . . . . . . . . . . . . 38
3.3.3 Étapes de la simulation . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Approximation par diagramme de Voronoï . . . . . . . . . . . . . . . 40
3.4.1 Diagramme de Voronoï . . . . . . . . . . . . . . . . . . . . . . 40
3.4.2 Intérêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4.3 Calcul d’un diagramme de Voronoï . . . . . . . . . . . . . . . 42
 ix

CHAPITRE 4 RECHERCHE DIRECTE . . . . . . . . . . . . . . . . . . . . 43

4.1 L’optimisation par recherche directe . . . . . . . . . . . . . . . . . . . 43
4.1.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.1.2 Un problème d’optimisation . . . . . . . . . . . . . . . . . . . 44
4.1.3 Concept de boîte noire . . . . . . . . . . . . . . . . . . . . . . 45
4.1.4 Propriétés des problèmes de boîte noire . . . . . . . . . . . . . 46
4.2 La recherche par motifs . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.1 Bref historique de la recherche directe . . . . . . . . . . . . . . 47
4.2.2 Notions importantes en recherche par motifs . . . . . . . . . . 48
4.2.3 Les algorithmes de recherche par motifs . . . . . . . . . . . . . 50
4.3 L’algorithme Mads . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3.1 Définitions et notations . . . . . . . . . . . . . . . . . . . . . . 53
4.3.2 Construction des ensembles . . . . . . . . . . . . . . . . . . . 54
4.3.3 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3.4 Mise à jour des paramètres . . . . . . . . . . . . . . . . . . . . 56
4.3.5 Gestion des contraintes . . . . . . . . . . . . . . . . . . . . . . 56
4.3.6 Ordre d’évaluation . . . . . . . . . . . . . . . . . . . . . . . . 57
4.4 Analyse de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.4.1 Notions d’analyse non lisse . . . . . . . . . . . . . . . . . . . . 58
4.4.2 Résultats de convergence . . . . . . . . . . . . . . . . . . . . . 59
4.5 Nomad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

CHAPITRE 5 OPTIMISATION D’UN RÉSEAU . . . . . . . . . . . . . . . 62

5.1 Définition de la simulation et notations . . . . . . . . . . . . . . . . . 62
5.1.1 Entrées de la boîte noire . . . . . . . . . . . . . . . . . . . . . 62
5.1.2 Sorties de la boîte noire . . . . . . . . . . . . . . . . . . . . . 63
5.2 Plan général de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . 64
5.3 Mise en place du problème . . . . . . . . . . . . . . . . . . . . . . . . 66
5.3.1 Couverture géographique et nombre total d’usagers . . . . . . 66
5.3.2 Équilibrage de la charge . . . . . . . . . . . . . . . . . . . . . 67
5.3.3 Séparation des problèmes . . . . . . . . . . . . . . . . . . . . . 67
5.4 Construction de la solution initiale . . . . . . . . . . . . . . . . . . . 68
5.4.1 Centre géométrique et centre de masse . . . . . . . . . . . . . 68
5.4.2 Moments centraux et découpage . . . . . . . . . . . . . . . . . 69
 x

5.4.3 Placement récursif des antennes . . . . . . . . . . . . . . . . . 70

5.4.4 Amélioration du placement initial . . . . . . . . . . . . . . . . 71
5.4.5 Assignation initiale de canaux . . . . . . . . . . . . . . . . . . 72
5.5 Recherche tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.5.1 Métaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.5.2 La recherche tabou . . . . . . . . . . . . . . . . . . . . . . . . 73
5.5.3 Recherche tabou avec mouvements . . . . . . . . . . . . . . . 74
5.6 Optimisation de l’assignation de canaux . . . . . . . . . . . . . . . . 75
5.6.1 Caractéristiques des recherches tabou . . . . . . . . . . . . . . 75
5.6.2 Fonctions objectifs . . . . . . . . . . . . . . . . . . . . . . . . 79
5.7 Optimisation de la localisation des antennes . . . . . . . . . . . . . . 81
5.7.1 Fonction objectif . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.7.2 Contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.7.3 Paramètres algorithmiques . . . . . . . . . . . . . . . . . . . . 82
5.8 Optimisation du problème complet . . . . . . . . . . . . . . . . . . . 83
5.8.1 Couplage des recherches . . . . . . . . . . . . . . . . . . . . . 83
5.8.2 Critères d’arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . 83

CHAPITRE 6 RÉSULTATS . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.1 Présentation des instances . . . . . . . . . . . . . . . . . . . . . . . . 86
6.1.1 Cartes de terrain . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.1.2 Cartes de densité . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.2 Déroulement de l’optimisation . . . . . . . . . . . . . . . . . . . . . . 92
6.3 Profils d’évolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.3.1 Recherche Voronoï initiale . . . . . . . . . . . . . . . . . . . . 100
6.3.2 Nombre d’antennes et nombre d’usagers non servis . . . . . . 101
6.3.3 Analyse des tendances générales d’évolution . . . . . . . . . . 103
6.3.4 Comportement individuel des recherches . . . . . . . . . . . . 112
6.3.5 Phase de terminaison . . . . . . . . . . . . . . . . . . . . . . . 114
6.4 Résultats finaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.4.1 Influence des nombre de canaux et d’antennes . . . . . . . . . 115
6.4.2 Influence du terrain et de la densité . . . . . . . . . . . . . . . 116
6.4.3 Comportement avec les instances réelles . . . . . . . . . . . . 118
 xi

CHAPITRE 7 CONCLUSION . . . . . . . . . . . . . . . . . . . . . . . . . . 119

7.1 Synthèse des travaux . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
7.2 Limitations de la solution proposée . . . . . . . . . . . . . . . . . . . 120
7.3 Améliorations futures . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

RÉFÉRENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

ANNEXES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
 xii

Liste des tableaux

Tableau 1.1 Évolution des technologies de téléphonie mobile . . . . . . . . 3

Tableau 2.1 Division du spectre radiofréquence et exemples d’utilisation . . 12
Tableau 2.2 Caractéristiques des principales technologie de téléphonie 2G . 21
Tableau 6.1 Résultats pour l’instance de terrain Square U,V . . . . . . . . . 101
Tableau 6.2 Résultats pour l’instance de terrain M tl V . . . . . . . . . . . . 102
Tableau 6.3 Résultats finaux agrégés par nombre de canaux et d’antennes. 116
Tableau 6.4 Résultats finaux agrégés par type de terrain. . . . . . . . . . . 117
Tableau 6.5 Résultats finaux agrégés par type de densité. . . . . . . . . . . 117
Tableau A.1 Résultats pour l’instance de terrain Square U . . . . . . . . . . 132
Tableau A.2 Résultats pour l’instance de terrain Square C . . . . . . . . . . 133
Tableau A.3 Résultats pour l’instance de terrain Square E . . . . . . . . . . 134
Tableau A.4 Résultats pour l’instance de terrain Square B . . . . . . . . . . 135
Tableau A.5 Résultats pour l’instance de terrain Circle U . . . . . . . . . . . 136
Tableau A.6 Résultats pour l’instance de terrain Circle C . . . . . . . . . . . 137
Tableau A.7 Résultats pour l’instance de terrain Circle E . . . . . . . . . . . 138
Tableau A.8 Résultats pour l’instance de terrain Circle B . . . . . . . . . . . 139
Tableau A.9 Résultats pour l’instance de terrain Banana U . . . . . . . . . . 140
Tableau A.10 Résultats pour l’instance de terrain Banana C . . . . . . . . . . 141
Tableau A.11 Résultats pour l’instance de terrain Banana E . . . . . . . . . . 142
Tableau A.12 Résultats pour l’instance de terrain Banana B . . . . . . . . . . 143
Tableau A.13 Résultats pour l’instance de terrain M tl. . . . . . . . . . . . . 144
 xiii

Liste des figures

Figure 1.1 Évolution du nombre d’abonnés à un service de téléphonie mobile 2

Figure 1.2 Couverture du territoire canadien par l’opérateur Koodo Mobile
en 2010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Figure 2.1 Bande de fréquences occupée par un signal. . . . . . . . . . . 6
Figure 2.2 Exemple d’un flux de données numériques représenté par diffé-
rents codages. . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Figure 2.3 Occupation spectrale d’un signal en bande de base et bande
passante de l’air . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Figure 2.4 Effet de l’utilisation des décibels sur une courbe de rapport
signal-bruit typique. . . . . . . . . . . . . . . . . . . . . . . . 18
Figure 3.1 Entrées et sorties de la boîte noire. . . . . . . . . . . . . . . . 29
Figure 3.2 Puissance reçue d’une antenne isotrope dans le vide . . . . . . 32
Figure 3.3 Puissance reçue d’une antenne isotrope dans le vide en décibels 32
Figure 3.4 Exemple de diagramme de Voronoï. . . . . . . . . . . . . . . . 41
Figure 4.1 Le concept de boîte noire . . . . . . . . . . . . . . . . . . . . . 45
Figure 5.1 Entrées et sorties de la boîte noire . . . . . . . . . . . . . . . . 64
Figure 6.1 Les différentes cartes de terrain utilisées. . . . . . . . . . . . . 87
Figure 6.2 Cartes de densité pour terrain carré. . . . . . . . . . . . . . . 89
Figure 6.3 Cartes de densité pour terrain circulaire. . . . . . . . . . . . . 90
Figure 6.4 Cartes de densité pour terrain en forme de banane. . . . . . . 91
Figure 6.5 M tl : Carte de densité pour l’île de Montréal. . . . . . . . . . 91
Figure 6.6 Cartes de service à différentes étapes de la recherche pour l’ins-
U
tance Square10,20 . . . . . . . . . . . . . . . . . . . . . . . . . . 93
Figure 6.7 Cartes de service à différentes étapes de la recherche pour l’ins-
C
tance Circle10,20 . . . . . . . . . . . . . . . . . . . . . . . . . . 94
Figure 6.8 Cartes de service à différentes étapes de la recherche pour l’ins-
E
tance Banana10,20 . . . . . . . . . . . . . . . . . . . . . . . . . 95
Figure 6.9 Cartes de service à différentes étapes de la recherche pour l’ins-
tance M tl10,20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
U
Figure 6.10 Profil d’évolution de l’instance Square10,20 . . . . . . . . . . . . 98
 xiv

C
Figure 6.11 Profil d’évolution de l’instance Circle10,20 . . . . . . . . . . . . 98
E
Figure 6.12 Profil d’évolution de l’instance Banana10,20 . . . . . . . . . . . 99
Figure 6.13 Profil d’évolution de l’instance M tl10,20 . . . . . . . . . . . . . . 99
Figure 6.14 Deux profils d’évolution avec des longueurs relatives de re-
cherche Voronoï initiale différentes. . . . . . . . . . . . . . . . 105
Figure 6.13 Effet de l’augmentation du nombre d’antennes sur l’instance
C
Circle10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
Figure 6.14 Deux instances avec couverture totale. . . . . . . . . . . . . . 109
Figure 6.15 Deux instances ne permettant pas d’obtenir une couverture totale.111
C
Figure 6.16 Exemple de l’instance Banana15,60 , pour laquelle la couverture
complète n’est obtenue qu’après un temps long. . . . . . . . . 112
 xv

Liste des Algorithmes

1 Mise à jour des puissances de canal. . . . . . . . . . . . . . . . . . . . 39

2 Mise à jour de la matrice des zones de couverture. . . . . . . . . . . . 40

3 Algorithme CS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4 Algorithme Gps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5 Algorithme Mads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

6 Plan général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
7 Fonction récursive de placement des antennes. . . . . . . . . . . . . . . 71
8 Recherche tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
9 Recherche tabou avec utilisation de mouvements. . . . . . . . . . . . . 76
10 Plan de l’algorithme général. . . . . . . . . . . . . . . . . . . . . . . . 84
 xvi

Liste des annexes

Annexe A Tableaux de résultats . . . . . . . . . . . . . . . . . . . . . . . . . 131

 xvii

Liste des sigles et abréviations

CS Coordinate Search
Gps Generalized Pattern Search
Mads Mesh Adaptive Direct Search
VNS Variable Neighborhood Search
SMS Short Message Service
MMS Multimedia Messaging Service
WAP Wireless Application Protocol
IP Internet Protocol
UIT Union Internationale des Télécommunications
GSM Global System for Mobile Communications
UMTS Universal Mobile Telecommunications System
SIR Signal to Interference Ratio
FDMA Frequency Division Multiple Access
TDMA Time Division Multiple Access
CDMA Code Division Multiple Access
 1

Chapitre 1

Introduction

Les communications mobiles font aujourd’hui partie intégrante de nos sociétés,

quelle que soit la zone du monde où l’on se trouve. Depuis l’apparition des premiers
réseaux de téléphonie mobile dans les années 1980, le nombre d’applications différentes
des réseaux sans fil ainsi que leur nombre d’usagers et leurs exigences n’ont cessé de
croître, et à un rythme toujours plus rapide. Les opérateurs de téléphonie mobile
ont dû s’adapter à l’évolution soutenue du marché, en investissant sans cesse dans
de nouvelles installations et de nouvelles technologies afin de proposer des services
toujours plus complets à des consommateurs de plus en plus exigeants.
Pour répondre aux attentes croissantes des usagers, les opérateurs mobiles doivent
répondre à trois enjeux principaux des réseaux de télécommunications : l’augmenta-
tion du nombre d’utilisateurs, l’amélioration des services et la couverture géogra-
phique des réseaux.

Nombre d’utilisateurs
Le nombre d’utilisateurs des réseaux de téléphonie mobile dans le monde connait
une croissance très rapide depuis de nombreuses années et s’élève en 2010 à plus de
5 milliards d’abonnés ([BBC(2010)]). Cette donnée est illustrée par la figure 1.1 qui
présente l’évolution du nombre d’abonnés à un opérateur de téléphonie mobile dans
le monde, au Canada et en Chine, pays où le nombre d’utilisateurs est aujourd’hui le
plus élevé et le plus rapidement croissant.
 2

(a) Monde

(b) Canada

(c) Chine

Figure 1.1 Évolution du nombre d’abonnés à un service de téléphonie mobile (source :

Index Mundi).
 3

Amélioration des services

Les premiers réseaux de téléphonie mobile n’offraient à leurs usagers que la pos-
sibilité de passer des appels téléphoniques. Mais l’évolution des technologies et des
habitudes de consommation a permis aux réseaux de téléphonie mobile d’offrir de
plus en plus de fonctionnalités : envoi de SMS, de MMS, navigation sur Internet (en-
core très limitée) grâce au WAP. Aujourd’hui, les réseaux 3G permettent un accès à
Internet à haute vitesse, autorisant l’envoi et la réception de courriels, la navigation
sur l’Internet complet, le visionnage de vidéos ou encore le téléchargement d’applica-
tions. Toutes ces nouvelles possibilités demandent des débits de données importants.
L’évolution des débits de données disponibles dans les réseaux de télécommunications
est illustrée par le tableau 1.1 avec quelques unes des technologies principales ayant
marqué le domaine des télécommunications.

Tableau 1.1 Évolution des technologies de téléphonie mobile (sources : [Lee(2006)],

Wikipedia).

Année d’in- Débit de données

Technologie Génération
troduction maximal théorique
AMPS 1 1984 10 kb/s
GSM 2 1991 33 kb/s
GPRS 2.5 2001 114 kb/s
UMTS 3 2001 56 Mb/s (2011)
LTE-Advanced 4 Futur 1 Gb/s

Couverture géographique
La couverture géographique est également un des objectifs importants dont doivent
tenir compte les opérateurs téléphoniques lorsqu’ils conçoivent leurs réseaux. Si en
zone urbaine il est clair que l’ensemble du territoire doit être couvert par le réseau, il
n’en va pas de même à l’échelle d’une région ou d’un pays, où les densités de population
sont variables et ne justifient pas une couverture complète du territoire. Les opérateurs
doivent faire le choix de fournir un service à certaines zones géographiques et non à
d’autres en évaluant l’importance de couvrir certains territoires par rapport à leurs
contraintes économiques. La figure 1.2 illustre la couverture du territoire du Canada
réalisée par l’opérateur Koodo Mobile.
Cet enjeu possède une importance particulière à l’heure actuelle, en raison du
 4

développement rapide de la téléphonie mobile dans les pays émergents et en voie de

développement, où les territoires sont souvent très étendus et les populations concen-
trées dans les zones urbaines. Il est primordial dans ces nouveaux marchés de parvenir
à arbitrer correctement entre l’objectif de couverture et des coûts des installations éle-
vés.

Figure 1.2 Couverture du territoire canadien par l’opérateur Koodo Mobile en 2010
(source : Koodo Mobile). Les zones couvertes sont les zones foncées.

Le marché de la téléphonie mobile représente un enjeu économique et social très

important, obligeant les différents acteurs à développer leurs réseaux et à sans cesse
les mettre à niveau au rythme de l’évolution des technologies. L’installation et la
mise à niveau permanente d’un réseau de télécommunications engendre des dépenses
considérables pour les opérateurs de téléphonie mobile, qui doivent pourtant toujours
répondre aux demandes croissantes du marché. C’est pourquoi il est intéressant de
posséder des outils permettant d’optimiser la conception des réseaux de télécommuni-
cations, afin de réduire au maximum les coûts des infrastructures, tout en répondant
le mieux possible aux contraintes du marché. C’est dans ce cadre que s’inscrit le
présent travail, en tentant d’ouvrir la voie à de nouvelles méthodes d’optimisation
d’un réseau de télécommunications s’appuyant sur la modélisation et la simulation
des réseaux, et sur un algorithme d’optimisation utilisant des techniques de recherche
directe et des métaheuristiques.
 5

Chapitre 2

Les réseaux de télécommunications

Un réseau de télécommunications est un système complexe dont l’étude et la modé-

lisation nécessitent la maîtrise de nombreuses notions dans plusieurs domaines scien-
tifiques. Afin de pouvoir modéliser puis optimiser un réseau de télécommunications,
il faut d’abord en étudier tous les aspects différents et la façon dont ils s’organisent.
Le présent chapitre est une introduction aux concepts fondamentaux des réseaux
de télécommunications nécessaires à la compréhension de leur fonctionnement et à la
modélisation.

2.1 Généralités sur les canaux de communication

2.1.1 Définition
En télécommunications ou dans les réseaux informatiques, un canal de commu-
nication est un médium de transmission d’information, permettant l’acheminement
d’un message d’une ou plusieurs sources à un ou plusieurs destinataires. Cette trans-
mission d’information peut se faire au travers d’un support physique, comme un câble,
ou d’un support logique, comme un canal radio.
En communications sans fil, le support de communication est constitué par des
ondes radioélectriques transmises entre émetteurs et récepteurs. Il s’agit d’un canal
analogique présentant de nombreuses spécificités par rapport aux autres canaux phy-
siques.

2.1.2 Spectre de fréquence d’un signal

Quel que soit le type de support utilisé pour la transmission de données, le signal
se propageant dans le médium de transmission est de nature analogique. Il s’agit
de signaux électriques dans un câble et d’ondes électromagnétiques dans l’air. Pour
comprendre comment l’information est transportée, il faut posséder certaines notions
 6

d’analyse et de traitement du signal. Nous résumons ici les notions présentées dans
[Gaillard et Lengellé(2006)] ou [Bellanger(2006)].
Considérons un signal s se propageant dans un canal. On peut effectuer une analyse
spectrale de ce signal en calculant la transformée de Fourier de s, ou la série de
Fourier de s dans le cas particulier d’un signal périodique. On obtient alors le spectre
de fréquences de s, qui indique la puissance transportée par le signal pour chaque
fréquence.
Pour un signal réel (par opposition à un signal aléatoire), la quasi-totalité de
l’énergie contenue dans le signal est comprise dans une bande de fréquence limitée,
en dehors de laquelle la puissance du signal est très faible. On définit ainsi un seuil de
puissance en-dessous duquel on considère que la puissance du signal est nulle, ce qui
permet d’identifier clairement la bande de fréquences occupée par le signal comme
illustré par la figure 2.1.

Figure 2.1 Bande de fréquences occupée par un signal.

2.1.3 Bande passante d’un canal

Il est très important de connaître les caractéristiques fréquentielles du canal sur
lequel on veut transmettre de l’information. En effet, un canal ne peut transporter des
signaux que dans une certaine bande de fréquences, appelée bande passante du canal.
Les signaux ayant une fréquence à l’extérieur de cette bande seront très rapidement
 7

atténués sur de très courtes distances, de sorte que l’on dit que le canal est opaque à
ces fréquences. Au contraire, les fréquences situées dans la bande passante du canal
se propageront beaucoup mieux. La bande passante d’un canal dépend bien sûr de
la nature du support, mais également de la longueur de transmission nécessaire pour
l’utilisation envisagée.

2.1.4 Adaptation au canal

Les informations transmises au sein d’un réseau de télécommunications peuvent
provenir de différentes sources et correspondre à diverses applications : voix humaine
pour une conversation téléphonique, paquets IP pour la navigation sur internet, flux
vidéo... Quelle que soit la source initiale de l’information, cette dernière est d’abord
convertie en un flux de données numériques. Ce sont pourtant des signaux de nature
analogique qui sont transmis au sein du réseau, et il faut donc transformer les données
numériques à transmettre en un signal pouvant transiter dans le réseau.

Signal en bande de base

Le flux de données numériques à transmettre peut être transporté par un courant

électrique dont l’amplitude varie dans le temps. Notons sI ce signal à transmettre.
Il a typiquement l’allure d’une fonction en créneaux, et l’information à transmettre
peut être encodée de différentes façons, comme illustré par la figure 2.2.
Ce signal, appelé signal en bande de base, contient toute l’information que l’on
veut envoyer. Cependant, il ne peut pas être transmis en l’état. En effet, une analyse
spectrale de ce type de signal montre que l’essentiel de l’énergie qu’il transporte
est située dans une bande de fréquences faibles. Or, la plupart du temps, la bande
passante du support de transmission est située dans des fréquences beaucoup plus
élevées (voir figure 2.3). Le signal en bande de base se propage donc très mal dans le
support, et est rapidement atténué sur de très courtes distances.

Modulation du signal

Il est nécessaire de changer la fréquence du signal à transmettre pour qu’il se

situe dans la bande passante du support. Pour cela, on réalise la modulation d’une
onde porteuse par le signal en bande de base. Une onde porteuse sP est une onde
sinusoïdale, d’amplitude aP , et de fréquence fP située dans la bande passante du
 8

Figure 2.2 Exemple d’un flux de données numériques représenté par différents codages.

support, de la forme : sP (t) = aP cos(2πfP t). Cette onde porteuse est modulée par
le signal à transmettre pour obtenir un nouveau signal, dont le spectre est centré
autour de fP et possédant un certain étalement spectral. Le signal est alors composé
de fréquences comprises dans la bande passante du support et peut maintenant être
transmis.

2.2 Débit de données et bande passante

Le débit de données d’un canal de communications est un élément très important,
puisqu’il détermine la quantité d’informations que ce canal pourra véhiculer. Chaque
usager d’un réseau de télécommunications requiert un certain débit de données pour
les différents services qu’il utilise. Si le débit de données que peuvent transporter les
signaux électromagnétiques était illimité, la conception d’un réseau de télécommu-
nications serait chose facile. Malheureusement, nous allons voir qu’au contraire, la
bande passante est une ressource rare et coûteuse, et que les débits de données pou-
vant être transmis par les ondes électromagnétiques sont limités, d’où la difficulté de
concevoir les réseaux de télécommunications.
 9

Figure 2.3 Occupation spectrale d’un signal en bande de base et bande passante de
l’air

2.2.1 Capacité d’un canal de communications

Les signaux électromagnétiques transmis dans un réseau de télécommunications
sont, d’après la section précédente, des signaux modulés, qui possèdent un certain
étalement spectral. Le médium de transmission utilisé, l’air, possède quant à lui une
certaine bande passante ∆f , qui est l’intervalle des fréquences pouvant être transmises
par ce canal de transmission.
Une formule de la théorie de l’information de Shannon ( [Shannon(1948)]) donne
un lien entre la largeur de bande du canal de transmission et la quantité d’informations
que celui-ci peut transporter :

PS
 
CI = ∆f log2 1 + (2.1)
PN
où : CI : capacité du canal en bits/s ;
∆f : largeur de bande du canal (ici l’air) ;
PS : puissance du signal reçu de l’émetteur ;
PN : puissance du bruit perturbant la réception.

On voit d’après cette formule que la largeur de bande du canal ∆f joue un rôle
prépondérant dans la capacité du canal, puisque cette capacité dépend linéairement
de ∆f .
 10

Un autre facteur important est la qualité de réception du signal, qui apparaît

dans le logarithme. C’est le rapport entre la puissance utile reçue d’une antenne et le
bruit, qui est la somme des contributions de tous les signaux à la même fréquence que
celui de l’antenne et qui perturbent les transmissions. Cet aspect sera discuté dans la
section suivante.
Il découle de cette formule que si l’on peut augmenter la largeur de bande de
façon arbitraire, on peut alors transmettre la quantité de données que l’on veut, et
donc fournir du service à autant d’utilisateurs que l’on souhaite. Mais en pratique la
largeur de bande disponible est limitée, et est même faible par rapport à l’utilisation
que l’on aimerait en faire.

2.2.2 Ondes radioélectriques

Les ondes radioélectriques (ou simplement ondes radio, ou encore ondes hert-
ziennes) sont, d’après la définition de l’Union Internationale des Télécommunications
(UIT), les « ondes électromagnétiques dont la fréquence est par convention inférieure
à 3000 GHz, se propageant dans l’espace sans guide artificiel ». L’ensemble de ces
fréquences constitue le spectre radiofréquence.
La limite de 3000 GHz correspond à la frontière des ondes infrarouges, de fréquence
plus élevée, et que l’on ne sait utiliser aujourd’hui qu’avec des supports optiques. On
ne peut donc pas utiliser d’ondes électromagnétiques de fréquences supérieures à 3000
GHz pour les radiocommunications, d’où cette définition des ondes radio.

2.2.3 Division du spectre radiofréquence

Bien que l’ensemble du spectre radiofréquence puisse être utilisé pour transmettre
des ondes radio, toutes les fréquences ne peuvent pas être utilisées pour les télécom-
munications. En effet, de nombreux phénomènes naturels influent sur la propagation
des ondes radio, et de façon différente selon la fréquence considérée.
Par exemple, les fréquences plus élevées sont plus rapidement atténuées, et ne
permettent pas de transporter de l’information sur de très grandes distances. En
revanche, elles permettent d’utiliser des bandes de fréquences plus importantes et de
transmettre de plus grandes quantités de données. Il faut donc trouver un compromis
entre ces deux aspects. De plus, les équipements nécessaires pour l’utilisation d’ondes
de fréquences élevées sont plus coûteux.
 11

D’autre part, il faut aussi prendre en compte les phénomènes naturels tels la
réflexion sur l’atmosphère ou la sensibilité aux intempéries. Des utilisations telles que
la radio AM, qui émet dans des bandes de fréquences de l’ordre de 100 kHz à 10000
kHz, tirent parti de la réflexion sur l’ionosphère des ondes de ces fréquences pour
augmenter leur portée d’émission. Les radio AM peuvent ainsi être reçues jusqu’à
1000 km de leur point d’émission. Cependant, cela est possible car les signaux de la
radio AM transportent une faible quantité de données par rapport à la largeur de
bande utilisée par les signaux, ce qui rend les transmissions plus robustes. Une telle
approche n’est pas envisageable dans le cas des télécommunications.
Enfin, il faut également considérer les perturbations occasionnées par les obstacles
tels que les bâtiments, les reliefs de terrain ou les arbres. Certaines applications uti-
lisent une transmission en « ligne de vue », où il n’y a pas d’obstacle entre l’émetteur
et le récepteur. Pour les télécommunications, on aimerait au contraire que les si-
gnaux puissent se propager malgré la présence d’obstacles, et il faut donc choisir des
fréquences qui le permettent.
Le choix de la bande de fréquence utilisée pour chaque type de transmission ne
doit pas être laissé au hasard. On divise conventionnellement le spectre radiofréquence
en bandes d’une décade, portant chacune un nom et correspondant à des utilisations
différentes, dont des exemples sont donnés dans le tableau 2.1.

2.2.4 Réglementation
Le domaine des radiocommunications est un domaine très réglementé. C’est l’UIT
qui établit et fait respecter le règlement des radiocommunications dans le monde. Il
concerne les ondes de fréquences comprises entre 9 kHz et 3000 GHz, les fréquences
inférieures à 9 kHz n’étant pas réglementées car elles ne sont pas utilisables pour les
radiocommunications.
La nécessité d’une réglementation des radiocommunications est indiscutable tant
le nombre d’utilisations diverses est élevé, ce qui fait du spectre radiofréquence une
ressource rare et convoitée, qu’il faut partager entre un grand nombre d’acteurs. Sans
une stratégie d’attribution efficace, l’utilisation incontrôlée du spectre radiofréquence
provoquerait des brouillages entre différentes applications qui utiliseraient les mêmes
bandes de fréquence, ce qui rendrait les communications radio impossibles.
L’UIT réserve donc des bandes de fréquences pour chaque type d’application uti-
 12

Tableau 2.1 Division du spectre radiofréquence et exemples d’utilisation, tiré de [Wi-

kipedia(2011b)].

Désignation interna-
Fréquence Exemples d’utilisation
tionale
ELF (extremely low 3 Hz à
Détection de phénomènes naturels
frequency) 30 Hz
SLF (super low fre- 30 Hz à
Communication avec les sous-marins
quency) 300 Hz
ULF (ultra low fre- 300 Hz à
Détection de phénomènes naturels
quency) 3 000 Hz
VLF (very low fre- 3 kHz à Communication avec les sous-marins, im-
quency) 30 kHz plants médicaux, recherches scientifiques...
30 kHz à Radionavigation, radiodiffusion GO, radio-
LF (low frequency)
300 kHz identification
MF (medium fre- 300 kHz à Radio AM, service maritime, appareil de re-
quency) 3 MHz cherche de victimes d’avalanche
Organisations diverses, militaire, radiodif-
3 MHz à
HF (high frequency) fusion, maritime, aéronautique, radioama-
30 MHz
teur, météo, radio de catastrophe...
Radio FM, aéronautique, maritime, radio-
VHF (very high fre- 30 MHz à
amateur, pompiers, réseaux privés, taxis,
quency) 300 MHz
militaire, météo...
UHF (ultra high fre- 300 MHz à Réseaux privés, militaire, GSM, GPS, Wi-
quency) 3 GHz Fi, Télévision
SHF (super high fre- 3 GHz à
Réseaux privés, micro-onde
quency) 30 GHz
EHF (extremely high 30 GHz à Réseaux privés, radars anticollision pour
frequency) 300 GHz automobiles, liaisons vidéo transportables
300 GHz à
Terahertz Applications scientifiques
3 000 GHz

lisant des ondes radio. On peut voir dans le tableau 2.1 quelques exemples de bandes
de fréquences réservées et les utilisations correspondantes. Toutes les technologies de
télécommunications utilisées aujourd’hui (en tête desquelles les technologies GSM,
 13

3G et Wi-Fi) se partagent des fréquences dans la bande UHF.

2.3 Propagation des ondes

Dans un réseau de télécommunications, les informations sont échangées par le
biais d’ondes radio émises et captées par les différents appareils qui composent le
réseau. Les stations de base et terminaux émettent des ondes qui se propagent dans
l’air et dont la puissance décroît à mesure que l’on s’éloigne de l’émetteur ou que ces
ondes rencontrent des obstacles. Pour pouvoir déterminer la région couverte par un
émetteur, il nous faut connaître la puissance des signaux que l’on reçoit lorsqu’on se
déplace.
La première étape de la modélisation d’un réseau de télécommunications consiste
en la modélisation de la propagation des ondes radio. De nombreux facteurs in-
fluencent cette propagation, et les modèles développés peuvent devenir très complexes
si l’on essaye de prendre en compte plusieurs phénomènes différents. Dans cette sec-
tion sera d’abord présenté le modèle le plus simple, celui de la propagation des ondes
dans le vide, puis quelques modèles décrivant l’influence des phénomènes les plus
importants seront évoqués.

2.3.1 Modèle de propagation dans le vide

Le modèle le plus simple pour la propagation des ondes est le modèle de propa-
gation dans le vide. Il se fonde sur les hypothèses principales suivantes :
– Le milieu dans lequel se propagent les ondes est le vide. En pratique, le fait
qu’on se situe dans l’air et non dans le vide a une influence négligeable, et cette
hypothèse n’est donc pas trop restrictive de ce point de vue. En revanche on ne
tient tient pas compte de la présence d’obstacles.
– L’émetteur est isotrope, c’est-à-dire qu’il rayonne la même puissance dans toutes
les directions de l’espace. On ne considère pas le cas où on utilise des émetteurs
directionnels.
Sous ces hypothèses, la puissance reçue d’un émetteur à une distance d de celui-
ci est donnée par l’équation de Friis ([Friis(1946)]). Elle est aussi appelée équation
des télécommunications, en raison de son aspect fondamental, et est présentée dans
[Rappaport(2002a)], [Granatstein(2008)] et [Lee(2006)] sous la forme suivante :
 14

!2
λ
Pr = Pe Ge Gr , (2.2)
4πd
où : Pr : puissance du signal capté par le récepteur ;
Pe : puissance de l’émetteur ;
Gr : gain de l’antenne du récepteur ;
Ge : gain de l’antenne de l’émetteur ;
λ : longueur d’onde du signal ;
d : distance entre l’émetteur et le récepteur.

En télécommunications on préfère en général travailler avec des fréquences plutôt

que des longueurs d’onde. L’équation peut être réécrite en fonction de la fréquence f ,
en vertu de la relation f = λc , où c est la vitesse de la lumière :
!2
c
Pr = Pe Ge Gr . (2.3)
4πdf
Cette équation permet de réaliser deux observations importantes :
– La puissance reçue a une dépendance à la fréquence des signaux en f −2 . Cela dé-
montre le fait que des signaux de fréquence élevée se propagent sur des distances
plus courtes que des signaux de fréquence plus faible ;
– La puissance reçue décroît très rapidement avec la distance à laquelle on se
trouve de l’émetteur, comme le montre le facteur d−2 dans l’équation.

2.3.2 Propagation en présence d’obstacles

La propagation des ondes est fortement perturbée par la présence d’obstacles.
Deux types d’approches sont couramment utilisés pour modéliser la propagation des
ondes lorsque les obstacles sont pris en compte : une approche théorique ou une
approche empirique.

Modèles théoriques

Pour étudier l’effet des obstacles sur la propagation des ondes, une première ap-
proche consiste à déterminer les différents chemins que peuvent emprunter les ondes
émises par une antenne pour arriver jusqu’au récepteur. Dans le modèle de propaga-
tion dans le vide, le récepteur ne reçoit les transmissions de l’émetteur qu’en ligne
 15

directe. En réalité, les ondes radio subissent deux types de déviations par les obs-
tacles : elles peuvent être réfléchies ou diffractées. Il y a alors en général plusieurs
chemins que peuvent emprunter les ondes pour aller de l’émetteur au récepteur. Cela
crée des interférences qui dégradent la réception.

Les différents modèles utilisant une approche analytique considèrent un type d’obs-
tacle et développent une formule donnant la puissance reçue de l’émetteur en fonction
de la géométrie et des caractéristiques des obstacles rencontrés. Par exemple, le mo-
dèle de réflexion sur le sol, présenté dans [Rappaport(2002b)], considère que les ondes
atteignent le récepteur en empruntant deux chemins différents : un chemin en ligne
directe, et un obtenu par réflexion sur le sol.
D’autres modèles comme ceux de Walfisch-Bertoni ou Ikegami, décrits dans [Gra-
natstein(2008)], rendent compte de la diffraction subie par les ondes sur les toits des
bâtiments lorsque l’antenne est située au-dessus des toits et le récepteur plus bas dans
une rue.

L’utilisation de tels modèles peut être intéressante pour effectuer des simulations
si l’on ne recherche pas une trop grande précision et si les environnements restent
simples. C’est le cas en général pour les réseaux de téléphonie mobile. En revanche, si
l’on souhaite réaliser des simulations sur de petites échelles dans des environnements
complexes, comme c’est le cas pour les réseaux Wi-Fi à l’intérieur de bâtiments, on
préférera effectuer des simulations par lancer de rayons. Cette technique consiste à
simuler l’émission d’un grand nombre de rayons depuis la source, se propageant en
ligne droite, et à suivre le chemin de chacun d’eux. On peut ainsi obtenir des résultats
très précis, mais au prix d’un temps de calcul très long.

Modèles empiriques

L’approche empirique peut être illustrée par le modèle de Delisle-Egli, présenté

dans [Granatstein(2008)], qui est un modèle de propagation en milieu urbain. Il se
base sur un grand nombre de mesures effectuées dans des villes des États-Unis, qui ont
permis d’établir la formule suivante pour l’atténuation de la puissance d’un signal :

4 2
4.27 × 10−17 d2 f
 si hm < 10 m
hb hm
Lempirique = (2.4)
4.27 × 10−17 d4 f 2
si hm > 10 m

h2b h2m
 16

où : Lempirique : atténuation de la puissance reçue ;

d : distance entre l’émetteur et le récepteur ;
f : fréquence du signal ;
hb : hauteur de l’antenne de la station de base ;
hm : hauteur de l’antenne du récepteur.

Ce modèle est valable en milieu urbain. Pour modéliser la propagation des ondes
dans des milieux de densités variées, une autre méthode consiste à utiliser, pour
l’atténuation L de la puissance du signal, une formule du type :

L = Kdα f 2 avec α ∈ [2, 4] (2.5)

où K est une constante et α est un paramètre dépendant de la densité du milieu,

variant de 2 pour les milieux vides de bâtiments comme les zones rurales, à 4 pour
les milieux les plus denses comme les zones urbaines.
Ce type de modèle permet d’obtenir de bons résultats si l’on s’intéresse à des
simulations de réseaux sur de grandes distances, où les phénomènes à petite échelle
ont une influence limitée. C’est en général le cas pour les réseaux de téléphonie mobile
par exemple.

2.3.3 Modèle retenu

Même s’il est important de connaître les différents facteurs qui influencent la
propagation des ondes et la façon dont on peut les modéliser, l’utilisation de modèles
élaborés mène à des calculs complexes et coûteux, et à une difficulté d’implémentation
accrue. Pour ces raisons, c’est le modèle de propagation des ondes dans le vide, avec
la formule de Friis, qui est retenu.
On fait également l’hypothèse que toutes les ondes électromagnétiques participant
aux différents phénomènes physiques impliqués dans les communications sont générées
par les antennes faisant partie du réseau. On néglige donc toutes les sources d’ondes
extérieures (rayons cosmiques, rayonnements naturels, autres utilisations des ondes
radio. . .).
Le présent travail de maîtrise doit être vu comme une première expérimentation
d’une nouvelle méthode de simulation et d’optimisation, et ne prétend donc pas te-
nir compte de tous les facteurs de modélisation. L’extension de notre approche à
 17

des modèles plus élaborés est donc laissée aux travaux ultérieurs qui souhaiteraient
l’utiliser.

2.4 Rapport signal-bruit et zone de couverture

La section précédente a décrit le calcul de la puissance reçue d’une antenne en
un point donné de l’espace. Mais cette donnée n’est pas suffisante pour déterminer la
zone de couverture de cette antenne. En effet, il n’existe pas de critère absolu sur la
seule puissance reçue d’une antenne pour établir si la qualité du signal est suffisante ou
non. On ne peut pas considérer une antenne de façon isolée, et il faut donc examiner
les sources d’interférences.

2.4.1 Rapport signal-bruit

Les interférences gênant la réception du signal d’un émetteur sont tous les autres
signaux de même fréquence que celui que l’on veut capter. Ces signaux se superposent
aux émissions de la source considérée et dégradent donc la qualité du signal reçu.
Dans notre modèle, on fait l’hypothèse que les ondes électromagnétiques provenant de
l’extérieur du réseau sont négligeables. Les seules ondes que l’on considère sont celles
générées à l’intérieur du réseau, par les antennes y appartenant. Les interférences
perturbant les émissions de l’une des antennes sont donc les signaux émis par les
autres antennes du réseau travaillant à la même fréquence.
Le rapport signal-bruit, souvent noté SIR (pour Signal to Interference Ratio), est
défini comme le rapport entre la puissance reçue d’une source PS et la puissance des
interférences perturbant la réception PI :

PS
SIR = , (2.6)
PI

ou encore en décibels :
PS
 
SIRdB = 10 log . (2.7)
PI
Dans le cadre de notre modèle, PS sera la puissance reçue d’une antenne, et PI la
somme des puissances reçues des autres antennes émettant à la même fréquence.

Il est souvent très pratique d’utiliser le décibel comme unité pour les grandeurs
 18

que l’on considère. On utilisera alors l’indice dB pour indiquer les fonctions exprimées
en décibels, par exemple Pd B pour la puissance reçue d’une antenne.
Pour rappel, la conversion en décibels s’effectue en prenant le logarithme de la
grandeur considérée, multiplié par 10, par exemple :

P
 
PdB = 10 log10 . (2.8)
1W

1400 40
SIR(x) 10*log10(SIR(x))
1200 30

Rapport signal-bruit (dB)

20
Rapport signal-bruit

1000
10
800
0
600
-10
400
-20
200 -30

0 -40
-20 -15 -10 -5 0 5 10 15 20 -20 -15 -10 -5 0 5 10 15 20
Distance a l’antenne (m) Distance a l’antenne (m)

(a) Rapport signal-bruit (b) Rapport signal-bruit en décibels

Figure 2.4 Effet de l’utilisation des décibels sur une courbe de rapport signal-bruit
typique.

La figure 2.4 illustre la conversion d’un rapport signal-bruit en décibels. L’intérêt

de cette conversion est évident : l’utilisation des décibels permet de mieux visualiser
l’évolution de grandeurs ayant de grandes variations. On voit par exemple sur la figure
2.4 que le rapport signal-bruit est très élevé lorsqu’on est très proche d’un émetteur,
et rapidement faible autour, sans que ses variations soient distinguables. Pourtant,
ce sont elles qui sont significatives pour nous. L’utilisation des décibels permet de les
faire apparaître.

2.4.2 Critère de qualité du signal

Pour déterminer si la transmission est de qualité suffisante pour effectuer une
communication, il n’est pas possible de ne se référer qu’à la puissance reçue PS . En
effet, il est toujours possible d’amplifier un signal électromagnétique. On pourrait
donc théoriquement capter le signal d’une antenne à une distance arbitrairement
grande de celle-ci, et il suffirait de l’amplifier pour pouvoir communiquer. En l’absence
 19

d’interférences, la zone de couverture d’une antenne est donc théoriquement infinie.

Mais lorsque l’on considère que des ondes électromagnétiques interfèrent avec les
signaux provenant de notre antenne, il n’en est plus ainsi. Pour que la communication
puisse avoir lieu, il faut que les signaux envoyés par l’antenne puissent être discernés
au milieu des ondes électromagnétiques que l’on capte. Il faut que la puissance reçue
de l’antenne soit suffisamment grande par rapport au bruit pour que l’on puisse filtrer
le signal et récupérer la partie qui nous intéresse.
Le rapport signal-bruit est un parfait indicateur : la communication est possible
si et seulement si la puissance PS reçue de l’émetteur est suffisamment grande par
rapport à la puissance des interférences PI , donc lorsque le rapport signal-bruit est
suffisamment élevé. On peut définir un seuil SIR ∗ pour la qualité du signal. On
pourra alors dire que le signal reçu d’une antenne est de qualité suffisante lorsque
∗
SIRdB ≥ SIRdB .
Ce seuil est généralement de l’ordre de 10 dB ([Rappaport(2002a)]), ce qui signifie
que le signal est suffisamment bon lorsque la puissance reçue d’une antenne est au
moins 10 fois supérieure à la puissance des interférences.

2.4.3 Zone de couverture

La zone de couverture d’une antenne est l’ensemble des points du plan où la qualité
du signal reçu de cette antenne est suffisante pour pouvoir effectuer une communica-
tion. Elle est définie à partir du rapport signal-bruit, de la façon suivante :
n o
∗
Z = (x, y) ∈ R2 : SIRdB (x, y) ≥ SIRdB . (2.9)

2.4.4 Détermination du rapport signal-bruit

Pour déterminer si un point du plan fait partie de la zone de couverture d’une
antenne, il faut calculer le rapport signal-bruit de l’antenne en ce point, et donc la
puissance reçue ainsi que la puissance des interférences. Ce sont ces deux grandeurs
qui sont les plus difficiles à déterminer.

Puissance de la source PS

Pour déterminer la puissance reçue d’une antenne, on vient de voir différentes

façons de modéliser la propagation des ondes électromagnétiques. La difficulté du
 20

calcul de la puissance reçue dépend de la complexité du modèle choisi. Le modèle de

propagation retenu dans ce travail est celui de la propagation des ondes dans le vide,
qui nous permet de calculer la puissance reçue de façon assez simple.

Puissance des interférences PI

Les interférences perturbant la réception des signaux d’une antenne peuvent pro-
venir de différentes origines. Il y a trois types d’interférences importantes :
– les interférences extérieures au réseau : il s’agit principalement des interférences
d’origine naturelle, comme le bruit provenant du soleil ou des rayons cosmiques.
En première approximation, on peut les considérer constantes dans le temps et
l’espace. Elles apportent donc une constante additive supplémentaire dans les
interférences PI . Cela est équivalent, lorsque l’on travaille en décibels, à intégrer
∗
ce terme dans le seuil SIRdB que l’on fixe alors à une valeur plus élevée. C’est
pourquoi ces interférences ne sont pas intégrées dans le modèle.
– les interférences de canal : il s’agit des ondes émises par les autres antennes
travaillant sur le même canal. La division du spectre en canaux est présentée
de façon détaillée à la section suivante. Pour effectuer le calcul, il suffit de faire
la somme des puissances reçues de toutes les antennes émettant à la même
fréquence.
– les interférences inter-canaux : ce sont les interférences se produisant entre les
signaux d’antennes émettant sur des canaux différents. Elles sont causées par
les imperfections des filtres utilisés par les équipements. Certaines fréquences
proches de celle du canal utilisé peuvent ainsi être mal filtrées et causer des
interférences. En pratique, on fait en sorte que les antennes placées à proximité
les unes des autres utilisent des canaux de fréquences assez éloignées. On divise
pour cela le spectre de fréquences disponibles en un grand nombre de canaux
de largeur plus petite. La contribution de ces interférences à la puissance totale
PI est alors faible en première approximation, et on néglige donc ce type d’in-
terférences dans le modèle. Il faudrait bien sûr en tenir compte dans un modèle
plus précis.
 21

2.5 Assignation de fréquences

La qualité de réception d’un signal est déterminée par la valeur du rapport signal-
bruit, et est intimement liée au niveau des interférences subies par chaque récepteur.
Il est donc primordial de minimiser les interférences au sein du réseau. Pour cela, il
convient de bien effectuer la répartition des canaux entre les antennes.

2.5.1 Multiplexage et division en canaux

Comme on l’a vu à la section 2.2.3, la bande de fréquence allouée aux télécommu-
nications est limitée. Par exemple, les bandes de fréquences allouées aux principales
technologies de téléphonie mobile de deuxième génération (2G) sont données dans
le tableau 2.2. Pour permettre à un grand nombre d’utilisateurs d’utiliser simulta-
nément le spectre de fréquences partagé, on utilise des techniques de multiplexage,
notamment en fréquence et en temps, comme indiqué par [Rappaport(2002a)].

Tableau 2.2 Caractéristiques des principales technologie de téléphonie 2G ([Rappa-

port(2002a)]).

Technologie
Caractéristiques GSM cdmaOne NADC
(Europe) (Etats-Unis) (Japon)
Fréquences émission 890-915 MHz 824-849 MHz 800-1500 MHz
Fréquences réception 935-960 MHz 869-894 MHz 800-1500 MHz
Séparation des
200 kHz 1.25 MHz 30 kHz
porteuses
Créneaux temporels
8 64 3
par canal

Multiplexage fréquentiel (FDMA)

Le multiplexage FDMA (Frequency Division Multiple Access) consiste à diviser

le spectre de fréquences disponible en N canaux de largeur plus faible. Chaque canal
peut alors transporter une certaine quantité d’informations, et donc véhiculer les
données d’un certain nombre d’utilisateurs.
 22

Multiplexage temporel (TDMA)

Le multiplexage temporel TDMA (Time Division Multiple Access) divise le temps

en créneaux temporels qui se succèdent, durant lesquels un seul utilisateur peur rece-
voir ou émettre. On divise ainsi le temps en C créneaux de durée T , alloués chacun
à un utilisateur différent.

Dans les technologies de télécommunications, ces deux types de multiplexage sont

en général utilisés conjointement. Ainsi, le spectre de fréquences est divisé en N
canaux, et chacun d’eux est à son tour divisé en créneaux temporels, ce qui permet de
transporter les données de plusieurs utilisateurs sur chaque canal. Les caractéristiques
des multiplexages fréquentiel et temporel des principales technologies 2G sont données
dans le tableau 2.2.
Par exemple, pour la technologie GSM, le spectre de fréquences disponibles est
d’abord divisé en deux bandes de largeur égale : la bande 890-915 MHz pour les
émissions depuis les antennes de base, et la bande 935-960 MHz pour les réceptions.
Chacune de ces bandes de 25 MHz est divisée en 125 canaux de 200 kHz. On a
donc 250 canaux unidirectionnels, ou 125 canaux bidirectionnels. Enfin, chaque canal
est divisé en 8 créneaux temporels, et peut donc véhiculer les conversations de 8
utilisateurs différents. Il y a au total un maximum de 1000 canaux logiques disponibles
pour transporter une conversation. En pratique, ce nombre est inférieur en raison de
l’utilisation de certains canaux comme canaux de contrôle.

2.5.2 Groupes de canaux

Le spectre de fréquences disponible pour les communications mobiles est divisé
en N canaux de largeur égale. Chacun de ces canaux peut transporter les données
d’un certain nombre d’utilisateurs. On assigne à chaque antenne non pas un seul mais
plusieurs canaux, et on divise alors les N canaux disponibles en p groupes de canaux.
Habituellement, on fait en sorte que tous les groupes de canaux possèdent le même
nombre de canaux Np .
Le choix du nombre p de groupes de canaux n’est pas laissé au hasard. En effet,
il a une grande influence à la fois sur la couverture géographique du réseau et sur le
nombre d’utilisateurs qui peuvent être servis, comme on va le voir dans les sections
suivantes.
 23

Par abus de langage et pour simplifier, on omet souvent de faire la distinction

entre canal et groupe de canaux lorsque le contexte rend la distinction inutile. Par
exemple, on parlera en général du canal assigné à une antenne, alors qu’il s’agit en
fait du groupe de canaux.

2.5.3 Zones de couverture

Dans la section précédente a été définie la zone de couverture d’une antenne à
partir du rapport signal-bruit. Ce dernier est défini comme le rapport de la puissance
PS reçue de l’antenne considérée sur la puissance totale des interférences PI . Dans
le modèle choisi pour ce travail, on ne considère qu’un seul type d’interférences : les
interférences de canal, qui ont lieu entre antennes travaillant sur le même canal.
Considérons donc, dans un réseau de télécommunications, une antenne A, produi-
sant une puissance P (x, y) au point (x, y) ∈ R2 , et émettant sur le canal c. Les seules
sources d’interférences perturbant la réception sont les autres antennes émettant éga-
lement sur le canal c, que nous noterons A1 , A2 , . . . , Ak .
Avec le modèle de propagation des ondes dans le vide, la puissance reçue d’une
antenne à une distance d de celle-ci est de la forme : P = dK2 . Si on considère que
toutes les antennes sont identiques, le facteur K est le même pour toutes les antennes
du réseau. La puissance totale des interférences subies de la part des antennes Ai au
point (x, y) est :
k
X K
PI (x, y) = 2
, (2.10)
i=1 di

où di est la distance de l’antenne Ai au point (x, y).

Le rapport signal-bruit pour notre antenne s’écrit :
1
P (x, y) d2
SIR(x, y) = = Pk 1
. (2.11)
PI (x, y) i=1 d2i

Selon cette formule, le rapport signal-bruit dépend principalement de deux fac-

teurs :
– le nombre k d’antennes qui interfèrent avec A : plus le nombre d’antennes dans
le canal c est élevé, plus il y a de termes qui s’additionnent dans le calcul des
interférences et plus la réception est mauvaise. On a donc intérêt à avoir le plus
faible nombre possible d’antennes par canal.
 24

– les distances di : plus les antennes Ai sont proches de l’antenne A, et plus les
interférences subies en un point (x, y) situé dans le voisinage de A sont élevées.
On a donc intérêt à maximiser la distance entre les antennes utilisant le même
canal.
En conséquence, on voit apparaître deux voies possibles pour maximiser les zones
de couverture des antennes :
– optimiser l’assignation de canaux : il s’agit de choisir adéquatement le canal à
assigner à chaque antenne, afin de maximiser la distance entre antennes appar-
tenant au même canal ;
– augmenter le nombre de groupes de canaux : cela permettrait d’avoir un faible
nombre d’antennes utilisant un même canal. Malheureusement, réduire le nombre
de canaux disponibles pour une antenne conduit à une réduction du nombre
d’utilisateurs pouvant être servis par une antenne, et donc à augmenter le
nombre d’antennes nécessaires pour servir tous les usagers.

2.6 Méthodes d’optimisation actuelles

L’optimisation d’un réseau de télécommunications est un sujet qui a déjà donné
lieu à plusieurs travaux. Mais les recherches effectuées jusqu’à présent se focalisent
presque toujours sur l’optimisation d’un seul aspect des réseaux. En particulier, les
problèmes du placement des antennes et de l’assignation de leurs fréquences sont deux
problèmes qui sont traités séparément. Pour chacun d’entre eux, différentes méthodes
ont été testées, chacune étant plutôt adaptée à des conditions particulières.

2.6.1 Optimisation du placement

Les réseaux de télécommunications

Lors de l’optimisation du placement des stations de base d’un réseau de télécom-

munications, on cherche en général à maximiser un objectif de couverture géogra-
phique, de capacité totale ou de débit moyen par utilisateur. On veut en outre mini-
miser le nombre de stations de base afin de réduire les coûts du réseau. On cherche
pour cela la localisation optimale des stations de base sur un territoire donné.
Les premiers travaux sur l’optimisation du placement des stations de base, tels
[Sherali et al.(1996)] ou [Tutschku(1998)], utilisent une modélisation simple des ré-
 25

seaux, ne tenant pas compte des interférences entre émetteurs. La zone couverte
par un émetteur est simplement la zone où la puissance reçue est supérieure à un
seuil. Des modèles plus fidèles apparaissent ensuite, qui tiennent compte des interfé-
rences engendrées par plusieurs stations émettant sur la même fréquence et utilisent
un critère de seuil sur le rapport signal-bruit pour définir les zones de couverture,
comme [Amaldi et al.(2003)] ou [Yang et al.(2007)]. Enfin, les travaux plus récents
tendent à considérer des modèles plus élaborés, comme [Abdel Khalek et al.(2011)]
qui traite différemment les canaux montant et descendant entre stations de base et
mobiles, prenant en compte la dissymétrie des échanges.
Une fois une modélisation choisie, l’optimisation consiste à trouver un placement
optimal des émetteurs sur un territoire. Dans la plupart des travaux, ce sont des ap-
prochez basées sur des métaheuristiques qui sont utilisées. Ainsi, [Amaldi et al.(2003)]
utilise une recherche tabou pour optimiser le placement, alors que [Cerri et al.(2002)]
choisit plutôt un algorithme génétique. [Yang et al.(2007)] compare quant à lui l’ef-
ficacité de trois algorithmes différents : un algorithme génétique, le recuit simulé, et
un algorithme hybride de recuit simulé évolutionniste. Les métaheuristiques sont un
type d’algorithme très populaire pour le problème de l’optimisation du placement des
stations de base, toujours à l’heure actuelle, car ils permettent d’atteindre assez ra-
pidement des solutions de bonne qualité malgré des problèmes de grande taille, longs
à simuler et présentant des fonctions non lisses.
Des méthodes de recherche directe, également bien adaptées à ce type de pro-
blème d’optimisation, ont aussi été employées. L’idée d’utiliser ce type d’algorithme
remonte à [Wright(1998)], qui ne propose pas d’exemple d’application mais suggère
l’utilisation de l’algorithme de Nelder-Mead ([Nelder et Mead(1965)]) et décrit son
fonctionnement. Parmi les travaux récents qui utilisent des méthodes de recherche di-
recte, on peut citer [Abdel Khalek et al.(2011)] qui sépare le problème de placement
en deux sous-problèmes, l’un continu et l’autre entier, et l’optimise avec un algorithme
de recherche par motifs.

Les réseau d’accès en intérieur

Une autre direction de recherche est utilisée pour le cas des réseaux d’accès en
intérieur, comme les réseaux WiFi par exemple. Pour optimiser le placement des
stations de base dans ce type de réseau, une modélisation par lancer de rayons est le
plus souvent utilisée. Ce type de simulation permet de tenir compte de la géométrie
 26

des espaces intérieurs, ce qui est nécessaire pour le placement d’antennes à l’intérieur
de bâtiments. Des systèmes tels que WISE ([Fortune et al.(1995)]) ou POPULAR
([Frühwirth et Brisset(1998)]) utilisent ce type de simulation. Le placement est ensuite
optimisé grâce à l’algorithme de recherche directe de Nelder-Mead pour le premier
exemple, et par programmation par contraintes pour le second.
Il s’agit dans ces exemples de maximiser la taille de la zone de couverture du réseau,
celle-ci étant définie par une puissance de réception minimale. Des environnements
de résolution de problèmes plus récents intègrent des simulations plus précises qui
utilisent un critère sur le rapport signal-bruit. Par exemple, l’environnement S4W
de [Mishra et al.(2007)] permet de choisir entre deux types de simulations différentes,
soit par lancer de rayons, soit par estimation de puissance comme ce qui est réalisé
pour les réseaux de télécommunications. Le module d’optimisation utilise l’algorithme
de recherche directe DIRECT de [Jones et al.(1993)] pour optimiser le placement des
émetteurs.
D’autres voies de modélisation et d’optimisation sont également explorées, comme
par [Vilovic et al.(2007)] qui s’appuie sur un modèle de réseau de neurones et effectue
une optimisation par essaims particulaires.

2.6.2 Optimisation de l’assignation de fréquences

Dans cette deuxième phase de conception d’un réseau de télécommunications, il
s’agit d’assigner à chaque station de base un ou plusieurs canaux parmi ceux dispo-
nibles. L’objectif est ici toujours de minimiser la somme des interférences subies au sein
du réseau, qu’il s’agisse des interférences de canal ou des interférences inter-canaux.
Il s’agit donc d’un problème combinatoire, et c’est pourquoi les métaheuristiques
occupent une place privilégiée dans la littérature concernant ce sujet.
Le problème de l’optimisation de l’assignation de canaux dans un réseau est tou-
jours un défi important aujourd’hui. Les travaux traitant de ce problème n’effectuent
pas de simulation d’un réseau de télécommunications pour évaluer la qualité de leurs
solutions, ce qui serait trop lourd. Ce n’est d’ailleurs pas nécessaire, le placement des
antennes étant connu. Des fonctions relativement simples à évaluer sont développées
dans les différents travaux.
Le schéma de distribution des fréquences le plus simple est un schéma fixe, dans
lequel les fréquences sont attribuées a priori aux émetteurs et ne changent jamais.
 27

Une répartition orthogonale est utilisée, ce qui signifie que des stations de base rap-
prochées recevront des fréquences suffisamment éloignées pour diminuer les interfé-
rences inter-canaux, simplifiant l’optimisation mais réduisant l’efficacité spectrale du
réseau. De très nombreux travaux existent exploitant cette répartition et un grand
nombre d’algorithmes différents on été testés. Par exemple [Ruiz et al.(1999)] réalise
l’optimisation grâce à un algorithme de recuit simulé, alors que [Reilly(2009)] utilise
l’algorithme SIMBA, variation de l’optimisation par essaims particulaires.
Une meilleure utilisation du spectre radio peut être obtenue en n’utilisant pas un
schéma d’assignation fixe mais en modifiant l’assignation de fréquences dynamique-
ment en fonction de l’évolution de la répartition de la demande. Le défi principal
de ce type de planification est qu’une optimisation doit s’effectuer en un temps très
court pour que le réseau s’adapte en temps réel. [Lopez-Perez et al.(2009)] développe
un modèle de planification dynamique, et [Lopez-Perez et al.(2008)] présente deux
méthodes d’optimisation pour ce problème, avec un recuit simulé et une recherche
tabou.
Une autre approche, plus expérimentale, est utilisée par [Luna et al.(2007)] : les
solutions sont évaluées en utilisant des données précises d’interférences provenant d’un
réseau GSM réel. Deux algorithmes d’optimisation sont comparés : une optimisation
par colonie de fournis et un algorithme génétique, le premier donnant des résultats
bien meilleurs. [Luna et al.(2008)] poursuit dans la même voie en ajoutant de nouvelles
instances de test et en comparant un plus grand nombre d’algorithmes.

2.6.3 Optimisation simultanée du placement et de l’assigna-

tion de fréquences
Bien que les deux problèmes précédents soient déjà difficiles à traiter séparément, il
est intéressant d’essayer de les considérer conjointement. En effet, ces deux problèmes
ne sont pas séparables, et il est donc naturel que de meilleures solutions puissent
être obtenues par une méthode globale. Cependant les travaux tentant d’explorer
cette voie sont presque inexistants. Le seul article intéressant à signaler est [Weicker
et al.(2003)], qui présente un algorithme évolutionniste ayant pour objectif d’optimiser
simultanément le placement des stations de base, l’assignation des fréquences ainsi
que leur niveau de puissance. Le modèle de réseau utilisé est toutefois très simplifié :
la zone de couverture de chaque station est représentée par un cercle dont le rayon
 28

dépend de son réglage de puissance. Le niveau d’interférences est ensuite calculé en

comptant le nombre de canaux qui interfèrent entre stations adjacentes. On est donc
loin de simulations réalistes d’un réseau de télécommunications.
 29

Chapitre 3

Modélisation et simulation

Le chapitre précédent a posé les bases de la conception d’un réseau de télécom-

munications. Le problème que nous voulons traiter est celui de l’optimisation de la
localisation et de l’assignation de canaux des antennes dans un tel réseau. Pour pou-
voir effectuer cette optimisation, il faut d’abord construire un modèle de réseau, ce
qui sera présenté dans la première partie de ce chapitre. Le modèle doit ensuite être
implémenté, sous forme de boîte noire, pour pouvoir être simulé.

3.1 Entrées et sorties de la boîte noire

Étant donné que l’on veut optimiser le placement des antennes conjointement avec
l’assignation des fréquences du réseau, les entrées de la boîte noire seront les positions
des antennes et les canaux qui y sont assignés. Pour ce qui est des sorties, la capacité
du réseau et sa couverture doivent être maximisées en même temps. On utilisera donc
pour l’optimisation des sorties reflétant ces deux grandeurs. La figure 3.1 illustre cette
situation.

Positions des antennes -

Capacité
-
du réseau
Boîte noire
- -
Assignation des canaux Couverture du réseau

Figure 3.1 Entrées et sorties de la boîte noire.

 30

3.2 Modèle physique

Le modèle développé doit être suffisamment élaboré pour ne pas être trop éloigné
de la réalité, sans contraindre au développement d’un module de simulation trop
complexe. Cette section présente le modèle construit et les différentes étapes de calcul
permettant d’effectuer la simulation.

3.2.1 Notations
Soit un réseau de communications composé de p stations de base A1 , A2 , . . . , Ap .
Les canaux sont au nombre de q et sont notés C1 , C2 , . . . , Cq .
Les entrées de la boîte noire sont les coordonnées {(x1 , y1 ), (x2 , y2 ), . . . , (xp , yp )} de
chaque antenne, et les canaux assignés à chacune (c1 , c2 , . . . , cp ) ∈ {C1 , C2 , . . . , Cq }n .
La puissance reçue d’une antenne Ai au point (x, y) ∈ R2 sera notée Pi (x, y). De
même, PjC (x, y) sera la puissance du canal Cj au point (x, y) ∈ R2 , soit la somme des
puissances de toutes les antennes émettant sur ce canal.

3.2.2 Modèle de propagation des ondes

La modélisation de la propagation des ondes électromagnétiques est un élément
critique dans la conception de la boîte noire. En effet, c’est du choix de la finesse
de modélisation de ce phénomène que dépendent à la fois la précision et le temps de
calcul de la simulation. Et une grande latitude est laissée dans ce choix, selon que l’on
utilise le modèle le plus simple, celui de la propagation des ondes dans le vide, ou que
l’on souhaite considérer un maximum de phénomènes physiques liés aux obstacles
sur le terrain, comme les réflexions ou la diffraction. Il est également possible de
considérer des émetteurs anisotropes, c’est-à-dire dont la puissance d’émission n’est
pas identique dans toutes les directions de l’espace.
La modélisation retenue pour la réalisation de la boîte noire est la plus simple
qui puisse être utilisée. On se place sur un territoire plan, sans relief. Le modèle de
propagation utilisé est celui de la propagation des ondes dans le vide. Les antennes
sont toutes identiques : ce sont des émetteurs isotropes ayant tous les mêmes caracté-
ristiques physiques et la même puissance. La puissance reçue de la part d’une antenne
en un point de l’espace ne dépend donc que de la distance d à l’émetteur, et elle est
 31

proportionnelle à l’inverse du carré de cette distance :

K
Pi (x, y) = , i ∈ J1; pK, (x, y) ∈ R2 (3.1)
d2
q
où d = (x − xi )2 + (y − yi )2 est la distance de l’antenne au point (x, y).
Il faut cependant adapter cette formule, puisqu’elle indique que lorsqu’on se rap-
proche de l’antenne, la puissance reçue tend vers l’infini, ce qui est évidemment incor-
rect. Cette formule n’est en réalité valable que dans le champ lointain de l’antenne,
où les phénomènes de diffraction sont négligeables et ne subsiste que le rayonnement.
Comme l’indique [Rappaport(2002a)], la limite entre le champ proche et le champ
lointain se situe à la distance de Fraunhofer dF :

2D2
dF = (3.2)
λ
où D est la plus grande dimension physique de l’antenne, dépendant de sa géométrie
et typiquement de l’ordre du mètre, et λ est la longueur d’onde du rayonnement
électromagnétique émis par l’antenne.
La formule (3.1) peut dès lors être modifiée pour tenir compte de cette limite, en
introduisant une saturation dans la zone d < dF :

 K2

si d < dF
Pi (x, y) =  dF i ∈ J1; pK, (x, y) ∈ R2 . (3.3)
 K2 si d ≥ dF
d

Ou encore en décibels :
  
10 log K2

si d < dF
d
Pi,dB (x, y) =  F i ∈ J1; pK, (x, y) ∈ R2 . (3.4)
10 log K2

si d ≥ dF
d

Une illustration de ces formules est donnée par les figures 3.2 et 3.3.
Afin d’éviter les problèmes liés à la non validité du modèle dans le champ proche,
on fera en sorte lors de l’optimisation que deux antennes ne puissent pas se situer
dans le champ proche l’une de l’autre, c’est-à-dire que l’on empêchera qu’elles soient
à une distance trop proche.
Ce modèle pourrait être affiné, si nécessaire, en utilisant une des modélisations
présentées dans le chapitre précédent. Par exemple, on pourrait prendre en compte
les milieux urbains et la densité des obstacles que doivent traverser les ondes. Une
 32

P(x,y)
0.4
0.35 0.4
0.3 0.35
0.25 0.3
0.25
0.2 0.2
0.15 0.15
0.1 0.1
0.05 0.05
0 0

40
102030
-40 -30 -20
-10 -100
-20
0 10 20 30
40 -40-30

Figure 3.2 Puissance reçue d’une antenne isotrope dans le vide

0 10*log10(P(x,y))

-5 0
-10 -5
-10
-15
-15
-20 -20
-25 -25

203040
10
-40 -30 -20
-10 -100
-20
0 10 20 30
40 -40-30

Figure 3.3 Puissance reçue d’une antenne isotrope dans le vide en décibels
 33

pratique courante dans les simulations consiste à utiliser un exposant différent pour
la distance à l’antenne selon la densité du milieu :

 Kα

si d < dF
dF
Pi (x, y) = (3.5)
 Kα

si d ≥ dF
d

avec α ∈ [2; 4], α = 2 pour les zones dégagées jusqu’à α = 4 pour les zones urbaines
denses.
Attention cependant à l’apparente simplicité de ce modèle de propagation. La
simulation est tout aussi simple que le modèle de propagation dans le vide si l’en-
semble du territoire est d’un seul type et donc si la valeur de α est fixe sur tout le
terrain. Mais dès que la densité est variable et que les rayons émis par une station de
base doivent traverser des zones avec des valeurs de α variées, la difficulté de simula-
tion augmente considérablement et il devient nécessaire d’utiliser des simulations par
lancer de rayons.

3.2.3 Puissance de canal et interférences

L’étape suivante consiste à calculer les interférences qui perturbent les transmis-
sions de chaque antenne. Pour une antenne Ai , il s’agit de l’ensemble des contributions
des sources émettant à la même fréquence autres que Ai .
Dans notre modèle, on néglige toutes les sources naturelles d’ondes électroma-
gnétiques, et toutes les émissions sont produites par les antennes du réseau. De plus,
seules les interférences de canal sont prises en compte, et les interférences inter-canaux
sont négligées.
Dans ce cadre, les interférences perturbant les transmissions d’une antenne Ai sont
constituées par la somme des puissances émises par toutes les antennes émettant sur
le même canal que Ai autres que Ai .
On définit d’abord, pour chaque canal Cj , la puissance de canal PjC , qui est la
puissance totale reçue de toutes les antennes émettant sur ce canal :

PjC (x, y) =
X
Pi (x, y). (3.6)
{i∈J1;pK: Ai ∈Cj }

Les interférences Ii subies par l’antenne Ai peuvent alors s’écrire comme la diffé-
 34

rence entre la puissance du canal ci et la puissance de Ai :

Ii (x, y) = PcCi (x, y) − Pi (x, y). (3.7)

3.2.4 Rapport signal-bruit

Comme indiqué précédemment, il n’existe pas de critère sur la seule puissance
d’une antenne pour déterminer si l’on capte correctement son signal. Pour savoir si le
signal reçu d’une antenne en un point de l’espace est de qualité suffisante pour pouvoir
être utilisé, il faut comparer sa puissance à celle des interférences qui le brouillent. On
peut alors définir un critère de bonne réception basé sur le ratio des deux grandeurs.
Comme indiqué dans le chapitre précédent, le rapport signal-bruit de l’antenne
Ai est défini comme le rapport de la puissance de l’antenne Pi sur la puissance des
interférences Ii :
Pi (x, y)
SIRi (x, y) = . (3.8)
Ii (x, y)
Le critère de qualité de signal pour l’antenne Ai au point (x, y) s’écrit, en décibels :

∗
SIRdB,i (x, y) ≥ SIRdB . (3.9)

∗
La valeur du seuil SIRdB est à déterminer en fonction des caractéristiques du
réseau et de l’équipement utilisé. Elle est typiquement de l’ordre de 10 dB, ce qui
signifie que l’on reçoit correctement le signal de Ai si sa puissance est environ 10 fois
supérieure à celle des interférences.

3.2.5 Zone de couverture

La zone de couverture Zi d’une antenne Ai est définie dans le chapitre précédent.
Il s’agit de la zone géographique dans laquelle la qualité du signal reçu est considérée
comme suffisante :

n o
∗
Zi = (x, y) ∈ R2 : SIRdB,i (x, y) ≥ SIRdB , i ∈ J1; pK. (3.10)

La zone de couverture du réseau ZR est la région du plan où l’on capte correcte-

ment le signal d’au moins une antenne appartenant au réseau :
 35

p
[
Z= Zi . (3.11)
i=1

3.2.6 Zone de couverture effective

La zone de couverture effective Zie est l’ensemble des points du plan où le service
sera assuré aux clients par l’antenne Ai . Elle est incluse dans la zone de couverture
Zi de l’antenne, puisqu’il faut d’abord que la qualité du signal reçu par le client soit
suffisante. Mais elle peut être plus petite que Zi . En effet, il est possible que les zones
de couverture de deux antennes se recoupent. C’est généralement le cas par exemple
pour deux antennes proches émettant sur des canaux différents. Un client situé dans
l’intersection des deux zones captera alors les signaux des deux antennes de façon
satisfaisante. Cependant, il ne sera connecté qu’à une seule des deux antennes. Celle
qu’il choisira sera celle dont il reçoit le signal avec la meilleure qualité.
La zone de couverture effective Zie est donc l’ensemble des points de Zi où la
qualité du signal reçu de Ai est supérieure à celle des autres antennes :

Zie = {(x, y) ∈ Zi : ∀j ∈ J1; pK, SIRdB,i (x, y) ≥ SIRdB,j (x, y)} . (3.12)

3.2.7 Nombre d’usagers

Contrairement aux zones de couverture des antennes, les zones de couverture
effective ne se recoupent pas. Elles correspondent exactement aux zones qui seront
desservies par chaque antenne. Cela permet de déterminer, pour un ensemble de
clients répartis sur le territoire à couvrir, par quelle antenne sera servi chacun d’eux.
On utilise des cartes de densité de population sur les territoires traités. Ces cartes
donnent la densité de population en chaque point du plan, qui peut être représentée
par une fonction de densité D(x, y) indiquant le nombre de clients au mètre carré en
chaque point (x, y).
Il est alors facile de calculer le nombre de clients à servir par chaque antenne :
ZZ
Ni = D(x, y) dx dy. (3.13)
(x,y)∈Zie

Le nombre total d’usagers à servir par l’ensemble du réseau est alors simplement
 36

obtenu en faisant la somme du nombre d’usagers pour toutes les antennes :

p
X
N = Ni (3.14)
i=1

3.2.8 Sorties
Une fois les calculs précédents effectués, on dispose d’assez d’informations pour
calculer toutes les grandeurs pertinentes qui apportent des connaissances sur le réseau.

Couverture géographique totale du réseau

La couverture géographique totale est l’aire de la zone desservie par le réseau.

C’est l’aire de la zone Z définie à l’équation (3.11) :
ZZ
A= dx dy. (3.15)
(x,y)∈ZR

On pourra également définir, pour la simulation et l’optimisation, un domaine

T ⊂ R2 qui sera le territoire sur lequel on veut optimiser le réseau. Il s’agira du
domaine réalisable pour le placement des antennes, qui ne pourront donc pas se
trouver à l’extérieur. De plus, tous les utilisateurs à servir seront également situés
dans cette région T , et donc ∀(x, y) 6∈ T, D(x, y) = 0. La couverture géographique
devient alors : ZZ
A= dx dy. (3.16)
(x,y)∈T ∩ZR

Nombre total d’usagers servis

Le nombre total d’usagers servis par le réseau est la somme du nombre d’usagers
servis par chaque antenne. On peut aussi l’obtenir à partir de la zone de couverture
totale du réseau : p ZZ
X
N = Ni = D(x, y) dx dy. (3.17)
i=1 (x,y)∈ZR

Variance du nombre d’usagers par antenne

Un des objectifs principaux de l’optimisation sera de minimiser le nombre d’usa-

gers servis par chaque antenne. Cela revient à équilibrer le nombre d’utilisateurs
servis entre toutes les antennes. Il est donc intéressant de considérer la variance du
 37

1 Pp
nombre d’usagers par antenne, qu’il faudra alors minimiser. Notons N̄ = p i=1 Ni
la moyenne du nombre d’usagers par antenne. La variance est alors :
p
1X
V= (Ni − N̄ )2 . (3.18)
p i=1

Charge maximale des antennes

La charge maximale des antennes est le nombre d’utilisateurs servis par l’antenne
la plus chargée :
Nmax = max Ni . (3.19)
i∈J1,pK

Cette sortie peut aussi servir à l’équilibrage du nombre d’usagers par antenne,
au même titre que la variance. Cependant, elle apporte moins d’informations que
la variance, puisqu’elle ne considère la charge que d’une seule antenne, alors que
la variance apporte une information tenant compte de toutes les antennes, ce qui
est préférable pour l’optimisation. L’intérêt de la charge maximale est alors plutôt
d’apporter une information plus claire et compréhensible.

3.3 Implémentation
Le modèle de propagation des ondes dans le vide et les calculs qui viennent d’être
présentés ont été implémentés sous forme de programme informatique en C++ pour
l’exécution de simulations. L’ensemble des calculs présentés dans la section précédente
doit être effectué au sein d’une boîte noire. Il convient de les implémenter de façon
réfléchie afin d’optimiser le temps de calcul.

3.3.1 Discrétisation du plan

Tous les aspects de la simulation nécessitent d’effectuer des calculs sur des régions
du plan. Le plan a donc été discrétisé sous forme matricielle pour pouvoir réaliser
les calculs en chaque point du terrain. La simulation est réalisée sur une région T
du plan. On construit un treillis régulier sur ce domaine, avec une taille de maille δ
constante. Le terrain peut alors être représenté par une matrice de taille n1 × n2 , de
sorte qu’il soit contenu dans un rectangle de taille δ n1 × δ n2 . Tous les calculs au sein
de la boîte noire sont ensuite effectués sur des matrices de cette taille, exceptée la
 38

puissance de réception des antennes. Chaque élément (u, v) d’une matrice correspond
à la valeur prise par une grandeur physique au point (x, y) = (δ u, δ v).

3.3.2 Puissance reçue des antennes

Étant donné que le modèle de propagation des ondes utilisé est celui de la propa-
gation dans le vide, la puissance reçue d’une antenne ne dépend que de la distance
d à laquelle on s’en trouve, et non de la localisation de l’antenne. On peut donc ef-
fectuer le calcul de la puissance des antennes une seule fois, et le réutiliser à chaque
évaluation, ce qui apporte un gain de temps de calcul très important.
P
Pour ce faire, on utilise pour chaque antenne Ai une matrice MA,i de taille (2n1 −
1) × (2n2 − 1). L’antenne est placée au point (n1 , n2 ) dans la matrice. Le remplissage
de la matrice est réalisé avec l’équation (3.3). L’intérêt d’utiliser une matrice de taille
plus grande que le terrain est que cela permet de retrouver la puissance reçue en un
point en effectuant le minimum de calculs. Ainsi, si une antenne A a pour coordonnées
(xA , yA ) = (δ uA , δ vA ), la puissance reçue au point (x, y) = (δ u, δ v) se trouve dans
la matrice MAP à l’élément (n1 − uA + u, n2 − vA + v). On retrouve ainsi la puissance
recherchée très rapidement.
Enfin, on considère dans notre modèle que toutes les antennes sont identiques,
c’est-à-dire que le facteur K apparaissant dans le numérateur de l’équation (3.3) est
le même pour toutes. En conséquence, une seule matrice MAP suffit.

3.3.3 Étapes de la simulation

Afin de rendre la simulation la plus rapide possible, il est important de ne pas
effectuer de calculs inutiles ou redondants. Cette section décrit la suite de calculs
réalisés au sein de la boîte noire lors d’une évaluation et précise leur complexité.

Mise à jour des puissances de canal

Lorsque de nouvelles valeurs sont appliquées en entrée de la boîte noire, il convient

d’abord de déterminer quels canaux seront modifiés. Si une antenne est déplacée par
rapport à la simulation précédente, ce sont toutes les antennes du canal qui sont
affectées. De même, si une antenne se voit assigner un nouveau canal, il faudra mettre
à jour la puissance du canal que l’antenne vient de quitter ainsi que la puissance de
celui qu’elle vient de rejoindre. Un déplacement d’antenne cause donc la mise à jour
 39

de la puissance d’un seul canal, alors que l’échange des canaux entre deux antennes
nécessite la mise à jour de deux canaux.
P
Chaque canal Cj possède une matrice MC,j , de taille n1 ×n2 , contenant la puissance
totale du canal en chaque point du treillis. Pour chaque canal à mettre à jour, il
faut recalculer la puissance de canal sur l’ensemble du terrain, comme décrit par
l’algorithme 1.

Algorithme 1: Mise à jour des puissances de canal.

pour chaque canal Cj à mettre à jour faire
P
pour chaque élément (u, v) de MC,j faire
s=0
pour chaque antenne Ai appartenant au canal Cj faire
s = s + MAP (n1 − uAi + u, n2 − vAi + v)
fin
P
MC,j (u, v) = s
fin
fin

Ainsi, en notant NC le nombre de canaux à mettre à jour, comme chaque canal

possède exactement pq antennes, la complexité de cette étape du calcul est de l’ordre
de O(NC pq n1 n2 ).
P
On peut remarquer que le calcul de chaque élément (u, v) de MC,j est indépendant.
P
Il est donc possible d’effectuer le calcul de tranches de la matrice MC,j de façon indé-
pendante. Cela permet de paralléliser le calcul en utilisant plusieurs fils d’exécution.
La bibliothèque Boost ([Boost(2011)]) a été utilisée pour réaliser cette parallélisation.

Mise à jour des zones de couverture

Le calcul préalable des puissances de canal permet ensuite de faire le calcul des
rapports signal-bruit plus rapidement. On met maintenant à jour la matrice MZ qui
indique, en chaque point du treillis, si ce point est couvert par le réseau et si oui, par
quelle antenne. Le calcul est décrit dans l’algorithme 2.
À la fin de ce calcul, chaque élément de MZ indique, pour chaque point du treillis,
s’il est desservi par une antenne, auquel cas MZ (u, v) est le numéro de l’antenne en
question. Si au contraire le point n’est couvert par aucune antenne, on a MZ (u, v) =
−1. La matrice MZ contient donc les zones de couverture effective de chaque antenne,
 40

Algorithme 2: Mise à jour de la matrice des zones de couverture.

pour chaque point (u, v) du treillis géographique faire
SIRm = −∞
pm = −1
pour chaque antenne Ai faire
Soit Cj le canal de l’antenne Ai
P
P = MA,i (n1 − uA + u, n2 − vA + v)
P
SIR = M P (u,v)−P
C,j

si SIR ≥ SIR ∗ et SIR > SIRm alors

SIRm = SIR
pm = i
fin
fin
MZ (u, v) = pm
fin

ce qui permet de calculer toutes les sorties de la boîte noire.

La complexité de cette partie du calcul est de l’ordre de O(p n1 n2 ). D’autre part,
on constate qu’ici également, les éléments de la matrice MZ peuvent être calculés de
façon indépendante, et le calcul a aussi été parallélisé.

3.4 Approximation par diagramme de Voronoï

Le modèle et l’implémentation présentés ci-dessus permettent d’effectuer des si-
mulations assez rapidement, mais il est intéressant d’envisager des méthodes d’ap-
proximation pour accélérer encore les calculs. Une méthode utilisant les diagrammes
de Voronoï est ici présentée.

3.4.1 Diagramme de Voronoï

Comme défini sur [Wikipedia(2011a)], un diagramme de Voronoï dans un espace
métrique de dimension n, relativement à un ensemble S d’objets, est une décompo-
sition de l’espace en régions telles que tous les points d’une région sont plus proches
d’un des objets de S que de n’importe quel autre. Le plus souvent, les objets de S
sont simplement des points dans l’espace. Et dans notre cas, on se limite à un espace
à deux dimensions, puisqu’on travaille dans le plan.
 41

Considérons un ensemble S de n points du plan muni de la distance euclidienne d.

Les points p de S sont appelés les germes du diagramme. Le diagramme de Voronoï
associé à S est l’unique découpage du plan en n régions V orS (p) telles que tout point
de V orS (p) est plus proche du point p que de tout autre point de S :
n o
∀p ∈ S, V orS (p) = x ∈ R2 : ∀q ∈ S\{p}, d(x, p) ≤ d(x, q) . (3.20)

3.4.2 Intérêt
L’idée d’utiliser les diagrammes de Voronoï vient de l’observation des cartes des
zones de couverture obtenues lors de simulations avec le modèle complet. On constate
en effet rapidement que, de façon tout à fait visuelle, elles ressemblent à des dia-
grammes de Voronoï où les germes seraient aux mêmes coordonnées que les antennes,
comme illustré par l’exemple de la figure 3.4. Les diagrammes de Voronoï pourraient
donc permettre d’obtenir une approximation dez zones de couverture des antennes.

Figure 3.4 Exemple de diagramme de Voronoï.

L’intérêt d’utiliser les diagrammes de Voronoï pour effectuer des approximations

de la simulation est double. D’une part, il est plus rapide de calculer les zones de
couverture des antennes avec un diagramme de Voronoï qu’avec le modèle de réseau,
 42

comme précisé dans la section suivante. D’autre part, le calcul du diagramme de

Voronoï est indépendant de l’assignation de canaux utilisée pour les antennes, et ne
prend en compte que leur localisation. Ces diagrammes peuvent donc être utilisés
pour essayer de trouver une bonne localisation initiale des antennes, où le nombre
d’utilisateurs contenus dans les régions de Voronoï de chaque antenne serait équilibré.

3.4.3 Calcul d’un diagramme de Voronoï

Depuis leur introduction en 1908, les diagrammes de Voronoï ont été très largement
étudiés, notamment en dimension 2. Ainsi, [Fortune(1987)] présente un algorithme de
calcul de diagramme de Voronoï ayant une complexité de l’ordre de O(p log(p)), p
étant le nombre de germes. Le problème de cet algorithme est qu’il ne permet de
calculer un diagramme de Voronoï que de façon analytique, en donnant les équations
des droites formant les limites des régions de Voronoï. Or pour la simulation, il est
nécessaire de connaître, pour chaque point du treillis, l’antenne qui en est la plus
proche. Calculer le diagramme de Voronoï discret à partir du diagramme analytique
n’est pas judicieux d’un point de vue algorithmique.
Dans ces conditions, il n’y a pas d’autre choix que de déterminer, pour chaque
point du treillis, la distance à chaque antenne, et d’identifier ainsi la plus proche. L’al-
gorithme ainsi obtenu a une complexité en O(p n1 n2 ), à comparer avec la complexité
de la simulation du modèle complet, en O((1 + NqC ) p n1 n2 ). Une légère diminution du
temps de calcul est obtenue. De plus, il existe des méthodes utilisant les capacités des
cartes graphiques des ordinateurs récents pour calculer un diagramme de Voronoï dis-
cret très rapidement, comme présenté par exemple par [Majdandzic et al.(2008)]. Ils
permettent une réduction du temps de calcul très importante. Ce type d’algorithme
n’a pas été implémenté dans le cadre de ce travail, mais pourrait l’être assez facile-
ment, rendant le calcul de l’approximation de la simulation beaucoup plus rapide.
 43

Chapitre 4

Recherche directe

L’optimisation d’un système est bien souvent une tâche difficile et coûteuse en
termes de temps de calcul, en particulier lorsque les problèmes sont complexes ou de
grande taille. De nombreuses méthodes d’optimisation existent qui ciblent des classes
de problèmes particulières et parviennent à en résoudre de grandes instances en un
temps raisonnable. Mais ces méthodes reposent sur la connaissance du modèle ma-
thématique décrivant le problème et nécessitent que ce dernier possède une forme ou
des caractéristiques particulières. Par exemple, la programmation linéaire ne permet
de traiter que des problèmes dont la fonction objectif ainsi que les contraintes sont li-
néaires. La plupart des méthodes d’optimisation non linéaire nécessitent quant à elles
que toutes les fonctions apparaissant dans le problème possèdent un certain degré de
régularité.
Pourtant, il existe un grand nombre de problèmes ne possédant pas ces propriétés,
ou pour lesquels on ne peut ou ne souhaite pas obtenir toutes ces informations. Dans
ce cas, on ne peut pas utiliser toutes les techniques développées dans ce cadre. C’est
ce type de problèmes que l’optimisation par recherche directe se propose de traiter.

4.1 L’optimisation par recherche directe

4.1.1 Motivations
Les techniques d’optimisation reposant sur une structure particulière de problème
sont séduisantes, car elles permettent de résoudre des problèmes de grande taille en
un temps raisonnable. Mais bien souvent en ingénierie, elles ne sont pas adaptées aux
problèmes concrets rencontrés. Beaucoup de facteurs peuvent jouer en défaveur de
ces approches.
En premier lieu, elles nécessitent toujours des hypothèses de régularité sur les
fonctions entrant en jeu dans le problème : linéarité, convexité, différentiabilité, ou
 44

simplement continuité pour les moins contraignantes. Il arrive pourtant souvent dans
les problèmes réels que l’on rencontre des fonctions ne présentant pas ces caractéris-
tiques. En particulier, lors de la modélisation de phénomènes physiques complexes, on
peut facilement avoir à composer avec des fonctions très irrégulières, qui ne sont déri-
vables qu’en peu d’endroits et présentant de nombreuses discontinuités. Un exemple
d’un tel problème est donné par [Audet et al.(2008a)]. D’autre part, même si on a
affaire à des fonctions dont les dérivées peuvent théoriquement être évaluées, il peut
arriver qu’en pratique leur approximation soit beaucoup trop coûteuse pour qu’on
puisse les exploiter.
Deuxièmement, il arrive fréquemment dans l’industrie que l’on n’ait pas accès
au fonctionnement interne du système que l’on souhaite optimiser. Cela arrive par
exemple lorsque le code informatique qui effectue les calculs est trop complexe, ou
inaccessible pour des raisons de confidentialité ou de propriété intellectuelle.
Face à toutes ces difficultés, on n’a pas d’autre choix que de se contenter de tester
la réponse du système à différents paramètres d’entrée, et d’effectuer l’optimisation à
partir de cette seule information. C’est pourquoi on nomme les algorithmes fonction-
nant sur ce modèle des algorithmes de recherche directe, des algorithmes d’optimisa-
tion de boîte noire, ou encore des méthodes sans dérivées. Une bonne introduction à
ce sujet peut être trouvée dans le livre [Conn et al.(2009)].

4.1.2 Un problème d’optimisation

On se place dans Rn et on considère donc un problème à n variables réelles. Soit
X une partie de Rn , dont le rôle sera discuté plus loin. On définit :
– une fonction f : X → R ∪ {∞}, appelée fonction objectif du problème ;
– m fonctions cj : X → R ∪ {∞}, j ∈ J1, mK, servant à définir les contraintes.

Tout problème d’optimisation mono-objectif peut s’écrire sous la forme suivante :

min f (x) (4.1)

x∈Ω

où Ω = {x ∈ X : cj (x) ≤ 0, ∀j ∈ J1, mK} est le domaine réalisable.

 45

A cette écriture on préfère souvent la suivante en optimisation :

min f (x)
x∈X
(4.2)
s.c. cj (x) ≤ 0 j ∈ J1, mK.

4.1.3 Concept de boîte noire

Une boîte noire conceptualise un système dont on ne connaît pas le fonctionnement
interne, encapsulé dans un objet avec lequel on ne peut interagir qu’en essayant
différents paramètres d’entrée et en analysant les réponses. Pour le problème général
décrit ci-dessus, on peut agir sur le paramètre d’entrée x, et recueillir les valeurs de
la fonction objectif f et des fonctions contraintes cj en ce point, comme décrit par la
figure 4.1.

-
f (x)
x ∈ Rn Fonction objectif
- Boîte noire
Point d’essai cj (x)
-
Fonctions contraintes

Figure 4.1 Le concept de boîte noire

On ne connaît pas a priori le domaine réalisable Ω, qui est défini à partir de

X et des fonctions contraintes cj . Il est important de distinguer plusieurs types de
contraintes, car il existe des mécanismes différents pour les traiter. On identifie ainsi
trois types de contraintes ([Audet et al.(2010)]) :
– les contraintes non relaxables : elles définissent X, et ne peuvent être violées
par aucun point d’essai. En tout point n’appartenant pas à X, la valeur de la
fonction objectif est fixée à +∞.
– les contraintes relaxables : ce sont les contraintes cj (x) ≤ 0. Un point d’essai
violant ces contraintes est non réalisable, mais l’évaluation de la boîte noire peut
avoir lieu et apporte une information supplémentaire. En effet, les fonctions cj
sont sensées être conçues de telle sorte que la valeur de cj (x) en un point non
réalisable apporte une mesure de la violation de la contrainte.
– les contraintes cachées : ces contraintes ne peuvent être définies à l’avance, et
peuvent entraîner l’existence de points non réalisables qui ne violent pas les
 46

autres contraintes. De tels points peuvent être produits par exemple lorsque
l’évaluation de la boîte noire échoue pour une raison quelconque, comme dans
[Audet et al.(2008a)] où l’évaluation échoue 43 % du temps.

4.1.4 Propriétés des problèmes de boîte noire

Le concept de boîte noire permet d’encapsuler le problème à optimiser et de faire
abstraction de ses propriétés. Les algorithmes de recherche directe sont donc capables
de s’accommoder d’une très grande variété de problèmes aux propriétés diverses :
– aucune hypothèse de régularité n’est nécessaire pour les fonctions du problème f
et les cj : elles peuvent être non convexes, non différentiables, non continues. Les
propriétés de convergence des algorithmes sont toutefois plus ou moins fortes
selon le niveau de régularité des fonctions ;
– aucune hypothèse n’est non plus requise pour le domaine X, qui peut être non
convexe ou même non connexe ;
– l’évaluation de la boîte noire peut échouer même si l’on se trouve dans le do-
maine réalisable Ω ;
– une évaluation de la boîte noire peut prendre un temps très long, comme par
exemple lorsqu’il s’agit d’une simulation de mécanique des fluides comme dans
[Marsden et al.(2007)], où une seule simulation peut durer plusieurs semaines.
Une boîte noire est, comme on peut le voir, un objet mathématique très pratique
d’un point de vue conceptuel, mais qui peut avoir un comportement très irrégulier et
inattendu. Un tel objet peut donc se révéler très difficile à manipuler.

4.2 La recherche par motifs

L’intérêt des algorithmes de recherche directe, comparativement aux algorithmes
d’optimisation classiques, est qu’ils ne nécessitent pas de calcul de dérivées, mais se
contentent d’évaluations numériques de fonctions. Les exemples de problèmes avec des
dérivées inexistantes ou trop laborieuses à évaluer sont légion. Différentes approches
de résolution de tels problèmes ont rapidement vu le jour, mais elles ont toutes en
commun la même idée de base. En partant d’une solution initiale, les algorithmes
de recherche directe évoluent itérativement en évaluant un certain nombre de points
d’essai proches du point actuel et en se déplaçant vers celui offrant la plus grande
 47

amélioration de l’objectif.

4.2.1 Bref historique de la recherche directe

Parmi les premières tentatives de résolution par recherche directe, on peut citer
[Box(1957)] qui utilise une approche similaire à celle des algorithmes génétiques, mise
en pratique dans un contexte industriel. Par la suite, la période 1960-1971 fut l’« âge
d’or » de la recherche directe, comme le relate [Lewis et al.(2000)]. Durant cette
période, trois grands types d’algorithmes de recherche directe furent développés. Ces
trois catégories sont, d’après [Lewis et al.(2000)] :
– la recherche par simplexe, introduite par [Spendley et al.(1962)] et améliorée
ensuite par [Nelder et Mead(1965)] ;
– la recherche avec directions de recherche dynamiques, dont la première mé-
thode fut celle de [Rosenbrock(1960)]. Un autre exemple est l’algorithme de [Po-
well(1964)], qui assure la convergence vers l’optimum en un nombre fini d’ité-
rations pour les fonctions quadratiques ;
– la recherche par motifs, dont le tout premier algorithme fut présenté par
[Hooke et Jeeves(1961)]. Il s’agit également de la première utilisation de l’ex-
pression « recherche directe ».

Les algorithmes modernes exploitent également d’autres techniques de recherche.

En particulier, les algorithmes comme Dfo ([Conn et al.(1998)]) tentent de créer un
modèle polynomial par échantillonnage de la fonction objectif et l’affinent progressive-
ment. La régularité du modèle polynomial permet d’utiliser des techniques exploitant
les dérivées pour l’optimiser rapidement. Plus récemment, [Conn et Le Digabel(2011)]
combinent les avantages de Dfo et de Mads (Mesh Adaptive Direct Search). On peut
également citer l’algorithme DiRect, présenté dans [Jones et al.(1993)], avec une ana-
lyse de convergence dans [Finkel et Kelley(2004b)] et une extension dans [Finkel et
Kelley(2004a)]. Il divise récursivement et de façon déterministe l’espace de recherche
en hyper-rectangles de plus en plus petits, et échantillonne la fonction objectif en un
point de ces zones.
On retrouve sinon les mêmes catégories que celles présentées ci-dessus. Bien que de
sérieux problèmes de convergence dans le cas général ont été identifiés pour les algo-
rithmes de simplexe dans [McKinnon(1998)], de nombreuses variantes, adaptées à des
problèmes spécifiques, ont été développées, comme [Price et al.(2002)] ou [Nazareth
 48

et Tseng(2002)]. Des propriétés de convergence en faible dimension ont également été

identifiées dans [Lagarias et al.(1998)].
Un exemple récent d’algorithme de recherche par motifs est Gps, décrit dans
[Torczon(1997)]. Finalement, l’algorithme Mads, développé par [Audet et Dennis,
Jr.(2006)], est une généralisation de Gps (Generalized Pattern Search), utilisant un
jeu de directions dynamique évoluant à chaque itération.
Les algorithmes de recherche directe ont longtemps souffert de l’absence de preuves
de convergence suffisamment générales. De nombreux travaux ont tenté de combler
cette lacune au fil du temps, avec de nouveaux algorithmes et des analyses de conver-
gence de plus en plus poussées, comme par exemple [Conn et al.(1997)] ou [Torc-
zon(1997)]. Mais ce n’est que récemment, grâce notamment à l’analyse non lisse
de [Clarke(1983)], que des analyses de convergence robustes et complètes ont pu
voir le jour. D’abord [Audet et Dennis, Jr.(2003)] réalise une analyse de convergence
de Gps, puis [Audet et Dennis, Jr.(2006)] présente l’algorithme Mads et prouve sa
convergence vers un point stationnaire au sens de l’analyse de [Clarke(1983)], grâce
à sa capacité à générer ultimement une infinité de directions de recherche différentes
qui couvrent toutes les directions de l’espace de recherche.

4.2.2 Notions importantes en recherche par motifs

La plupart des algorithmes de recherche directe fonctionnent sur le même principe :
– à partir d’une solution courante, l’algorithme génère un ensemble de directions
de recherche à partir d’une base positive de l’espace de recherche ;
– à partir de ces directions de recherche, des points d’essai sont créés sur un treillis,
permettant de contrôler la distance du point courant aux points d’essai ;
– la boîte noire est alors évaluée en chacun de ces points d’essai. Si une meilleure
solution que la solution courante est trouvée, l’algorithme s’y déplace. Sinon,
on reste au point actuel et on réduit la taille du treillis.
Cette étape de recherche est appelée étape de sonde. Elle est répétée de façon
itérative jusqu’à arriver au critère d’arrêt. On peut y ajouter une étape de recherche,
qui permet à l’algorithme d’essayer de chercher un optimum global.
 49

Base positive

La notion de base positive est analogue à celle de base de Rn : c’est une fa-
mille génératrice positive minimale de Rn , c’est-à-dire qu’elle engendre Rn par des
combinaisons linéaires positives de ses vecteurs, et qu’aucune sous-famille n’a cette
propriété. Elles ont été étudiées dans [Davis(1954)] et [Audet(2011)]. Une caractéris-
tique intéressante d’une telle famille, primordiale pour l’analyse de convergence, est
qu’il existe au moins un vecteur compris dans tout demi-espace ouvert de Rn .

Treillis

Un treillis est une discétisation régulière de Rn , sur laquelle on construit les points
d’essai pour les évaluer. Il est défini par trois paramètres : sa taille ∆ ∈ R+ , qui définit
la distance entre deux points adjacents du treillis, sa position, imposée par la position
du point courant x ∈ Rn , qui doit se trouver sur le treillis, ainsi qu’un ensemble de
directions D ∈ Rn×p . Il est également très important dans l’analyse de convergence
des algorithmes de recherche par motifs.
Lors de la recherche, sa taille est mise à jour à chaque itération. Lorsque l’évalua-
tion des points générés lors de l’étape de sonde conduit à un succès, donc à une amé-
lioration de la solution, la taille du treillis est conservée ou augmentée. Au contraire,
s’il s’agit d’un échec, la taille du treillis est réduite.

Étape de sonde

L’étape de sonde est aussi appelée sonde locale, car elle consiste en une étape de
recherche locale autour du point courant. C’est lors de cette étape que les directions
de recherche, qui forment une base positive, sont générées, ainsi que les points d’essai
qui sont attachés au treillis. La boîte noire est ensuite évaluée en ces points d’essai.
Si un point avec une meilleure valeur de la fonction objectif est trouvé, l’étape est un
succès, dans le cas contraire c’est un échec. La taille du treillis est alors mise à jour
et l’itération suivante peut avoir lieu.
Ce processus se poursuit jusqu’à atteindre le critère d’arrêt, qui peut être une taille
minimale du treillis, un nombre d’itérations de l’algorithme, un nombre d’évaluations
de la boîte noire ou encore une durée maximale d’exécution.
 50

Étape de recherche

A l’étape de sonde peut s’ajouter une étape de recherche, aussi appelée recherche
globale. Une recherche composée uniquement de la sonde locale se retrouve attirée dans
un optimum local. Si l’on veut effectuer une recherche plus large, on peut élaborer
une stratégie de recherche globale qui sera exécutée lors de la phase de recherche.
A chaque itération un certain nombre de points supplémentaires seront également
évalués. Ces points, qui devront toujours être attachés au treillis, sont générés par
une stratégie définie par l’utilisateur, qui devrait tirer profit de sa connaissance du
problème pour identifier des points intéressants à explorer.
En pratique, cette étape se révèle très importante. Même si l’étape de sonde per-
met de se déplacer vers un minimum local avec des preuves de convergence, l’étape
de recherche permet de diversifier la recherche et entraîne généralement une nette
amélioration des solutions par rapport à la seule sonde locale.

4.2.3 Les algorithmes de recherche par motifs

Les notions définies ci-dessus sont au cœur de toutes les méthodes de recherche
par motifs. Le premier algorithme de recherche par motifs à avoir été formalisé est
l’algorithme Coordinate Search (Cs), qui utilise les vecteurs de la base canonique
de Rn comme directions de recherche. Une évolution de Cs est l’algorithme Gps
(Generalized Pattern Search), présenté par [Torczon(1997)], qui utilise des directions
de recherche plus évoluées. Enfin, la dernière évolution de cette classe d’algorithmes
est Mads (Mesh Adaptive Direct Search), introduit dans [Audet et Dennis, Jr.(2006)],
dont la méthode de génération des directions de recherche est encore plus élaborée,
et permet une analyse de convergence poussée. Ce dernier algorithme sera présenté
en détails dans la section suivante.

Coordinate Search (Cs)

L’algorithme Cs, en tant que premier véritable algorithme de recherche directe,

n’utilise pas encore explicitement les notions de base positive, de treillis, d’étapes de
sonde ou de recherche. Seule une phase de sonde locale est en fait présente. A partir
d’un point courant xk , l’algorithme évalue simplement la fonction objectif f en les 2n
points de l’ensemble Pk = {xk ± ∆k ei : i ∈ J1, nK}. Les directions de recherche sont
donc ±ei , les vecteurs de la base canonique de Rn et leurs opposés. Le paramètre ∆k
 51

est en fait la taille du treillis, qui est divisée par 2 en cas d’échec de l’étape de sonde,
et gardée constante en cas de succès. L’algorithme 3 détaille le fonctionnement de Cs.

Algorithme 3: Algorithme CS
Initialisation :
Compteur d’itérations : k = 0
Point initial : x0
Taille de pas initiale : ∆0 > 0
Sonde locale :
tant que le critère d’arrêt n’est pas atteint faire
Pk = {xk ± ∆k ei : i ∈ J1, nK}
si ∃ y ∈ Pk , f (y) < f (xk ) alors
xk+1 = y
∆k+1 = ∆k
sinon
xk+1 = xk
∆k+1 = ∆2k
fin
k =k+1
fin

Generalized Pattern Search (Gps)

Du fait de l’utilisation d’un faible nombre de directions de recherche, l’algorithme

CS n’est pas toujours très efficace en pratique. L’algorithme Gps a été développé
par [Torczon(1997)] et [Lewis et Torczon(1999)] pour améliorer ce comportement. Ses
principales améliorations par rapport à CS sont : l’ajout d’une étape de recherche
globale optionnelle, l’utilisation de directions de recherche plus variées, et une gestion
plus évoluée de la taille du treillis.
A chaque itération, les directions de recherche Dk de Gps sont formées des p
vecteurs d’un ensemble générateur positif D, avec p ≥ n + 1. Afin d’assurer les
propriétés de convergence de Gps, la construction de l’ensemble D obéit à des règles
strictes qui seront détaillées dans la section suivante avec la description de Mads. La
remarque importante à effectuer ici est qu’on dispose maintenant d’un ensemble de
directions de recherche bien plus variées que les simples vecteurs de la base canonique
de Rn . Cependant, les directions de recherche restent en nombre fini.
La taille du treillis, quant à elle, n’est plus limitée à seulement se réduire ou rester
 52

constante. Son mécanisme de mise à jour lui permet de se réduire en cas d’échec
de l’étape de sonde et à grandir en cas de succès. Cette caractéristique ne modifie
aucunement l’analyse mathématique par rapport à CS, mais permet généralement
une convergence plus rapide en pratique.
L’algorithme Gps tel que décrit ici est succinctement détaillé dans l’algorithme 4.

Algorithme 4: Algorithme Gps

1. Initialisation :
Compteur d’itérations : k = 0
Point initial : x0
Taille de treillis initiale : ∆0 > 0
2. Étape de recherche (optionnelle) :
Évaluer l’objectif f en un nombre fini de points d’essai fournis par l’uti-
lisateur, situés sur le treillis.
3. Étape de sonde (si l’étape de recherche a échoué) :
Évaluer f en les points de Pk = {xk + ∆k d : d ∈ Dk }, avec Dk ⊂ D.
4. Mise à jour des paramètres :
si un point d’essai y tel que f (y) < f (xk ) est trouvé alors
Poser xk+1 = y
Mettre à jour la taille du treillis ∆k+1 ≥ ∆k
sinon
Poser xk+1 = xk
Mettre à jour la taille du treillis ∆k+1 < ∆k
fin
5. Critère d’arrêt :
Si le critère d’arrêt n’est pas rencontré, poser k = k + 1 et retourner à
l’étape de recherche.

4.3 L’algorithme Mads

L’algorithme Mads est la dernière évolution des algorithmes de recherche par
motifs sur treillis, développée par [Audet et Dennis, Jr.(2006)]. Il est une généralisation
de l’algorithme Gps, et possède une analyse de convergence détaillée.
 53

4.3.1 Définitions et notations

La principale amélioration apportée par Mads par rapport à Gps est de pouvoir
générer des directions de recherche encore plus variées, grâce à l’introduction d’un
paramètre de taille de sonde et à une nouvelle façon de choisir ces directions. En
fait, l’algorithme peut générer ultimement une infinité de directions de recherche qui
balayent toutes les directions possibles.

Ensemble générateur positif D

Il est nécessaire de définir un ensemble de directions D qui seront utilisées tout au

long de l’algorithme pour construire les directions de recherche. L’ensemble D défini
par Mads est identique à celui utilisé dans Gps. Soit Z ⊂ Zn un ensemble générateur
positif entier de Rn , contenant p ≥ n + 1 éléments. Soit également une matrice
G ∈ Rn×n inversible. Posons, pour j ∈ J1, pK, dj = Gzj , et définissons l’ensemble
D = {d1 , d2 , . . . , dp }. Avec cette construction, D est un ensemble générateur positif
de Rn . Il peut être pratique de considérer les ensembles Z et D comme des matrices
de taille n × p, et on peut alors écrire D = GZ.
La propriété fondamentale qui découle de cette construction de D est que tous les
points du treillis généré à partir des vecteurs de D sont à une distance finie les uns
des autres. Sans cette propriété, rien n’assure que le treillis généré ne puisse avoir de
points infiniment proches. Ce résultat joue un rôle majeur à la fois dans les analyses
de convergence de Gps et Mads et dans le comportement des algorithmes.

Notations

Pour présenter l’algorithme Mads, il est nécessaire d’introduire un certain nombre

de notations. La plupart des paramètres de l’algorithme évoluent au fil des itérations.
Le compteur d’itérations sera noté k, et les notations dépendant de l’itération courante
seront indicées par k. On définit alors :
– Mk : le treillis ;
– xk : le centre de sonde ;
– ∆mk : le paramètre de taille du treillis ;
p
– ∆k : le paramètre de taille de sonde ;
– Dk : l’ensemble des directions de sonde ;
– Pk : le voisinage de sonde ;
 54

– Sk : l’ensemble de recherche.

4.3.2 Construction des ensembles

À chaque itération de l’algorithme, le treillis Mk , l’ensemble de recherche Sk et le
voisinage de sonde Pk doivent être mis à jour.

Treillis

De façon générale, le treillis centré en x ∈ Rn de taille ∆ ≥ 0 est défini par :

M (x, ∆) = {x + ∆Dy : y ∈ Np } ⊂ Rn . (4.3)

Soit Vk l’ensemble des points de Rn où l’objectif f a été évalué au début de

l’itération k. Le treillis courant à l’itération k est l’ensemble suivant :
n o
|D|
M (x, ∆m m
[
Mk = k ) = x + ∆k Dz : x ∈ Vk , z ∈ N . (4.4)
x∈Vk

Ensemble de recherche

L’ensemble de recherche Sk est un ensemble fini de points fournis par l’utilisateur

qui seront évalués avant l’étape de sonde. Les seules règles auxquelles doit obéir l’étape
de recherche sont que les points générés doivent se trouver sur le treillis courant Mk ,
et que l’évaluation de Sk doit se faire en un temps fini.

Voisinage de sonde

À l’itération k, le voisinage de sonde est défini par :

Pk = {xk } ∪ {xk + ∆m
k d : d ∈ Dk } ⊂ Mk , (4.5)

où Dk est tel que pour tout d ∈ Dk :

– d est une combinaison linéaire entière positive non nulle de vecteurs de D :
n o
Dk ⊂ Du : u ∈ N|D| \ {0} ; (4.6)
 55

– la distance du centre de sonde xk à un point d’essai xk + ∆m

k d est majorée par
une valeur dépendant du paramètre de taille de sonde ∆pk :

p 0 0
∆m
k kdk ≤ ∆k max {kd k : d ∈ D} . (4.7)

4.3.3 Algorithme
Le fonctionnement de Mads sans contraintes est détaillé dans l’algorithme 5. Le
traitement des contraintes est expliqué dans les sections suivantes.

Algorithme 5: Algorithme Mads

1. Initialisation :
Compteur d’itérations : k = 0
Point initial : x0 ∈ X
Taille de treillis initiale : ∆m
0
Taille de sonde initiale : ∆p0

2. Étape de recherche (optionnelle) :

Générer l’ensemble des points de recherche Sk avec la stratégie définie
par l’utilisateur.
Évaluer l’objectif f sur l’ensemble Sk .

3. Étape de sonde (si l’étape de recherche a échoué) :

Générer les directions de recherche Dk puis le voisinage de sonde Pk .
Évaluer l’objectif f sur l’ensemble Pk .
4. Mise à jour des paramètres :
si un point d’essai y tel que f (y) < f (xk ) est trouvé alors
Poser xk+1 = y
Mettre à jour ∆mk+1 ≥ ∆k
m

Mettre à jour la taille de sonde ∆pk+1

sinon
Poser xk+1 = xk
Mettre à jour ∆mk+1 < ∆k
m

Mettre à jour la taille de sonde ∆pk+1

fin

5. Critère d’arrêt :
Si le critère d’arrêt n’est pas rencontré, poser k = k + 1 et retourner à
l’étape de recherche.
 56

4.3.4 Mise à jour des paramètres

À chaque itération, les paramètres de taille du treillis et de la sonde doivent être
mis à jour. La taille du treillis est mise à jour selon la formule :

∆m
k+1 = τ
wk m
∆k (4.8)

où τ > 1 est une constante rationnelle et wk est un entier. La valeur de wk dépend

de l’issue des évaluations :
– si l’itération conduit à un succès, on choisit wk ≥ 0, de sorte que la taille du
treillis est maintenue constante ou agrandie ;
– si on a un échec, on prend wk ≤ −1, et la taille du treillis est réduite.

Le paramètre de taille de sonde doit quant à lui obéir à la relation ∆pk ≥ ∆m

k , et
doit satisfaire la propriété suivante :

p
Pour tout K ⊂ N de cardinal infini : lim ∆m
k = 0 ⇔ lim ∆k = 0. (4.9)
k∈K k∈K

p p
Une stratégie de mise à jour typique consiste à poser ∆m m
k+1 = 2∆k et ∆k+1 = 4∆k
1 m p 1 p
en cas de succès de l’itération, et ∆m
k+1 = 4 ∆k et ∆k+1 = 2 ∆k en cas d’échec.

4.3.5 Gestion des contraintes

Comme mentionné précédemment, il existe trois types de contraintes dans un
problème d’optimisation de boîte noire : les contraintes relaxables, non relaxables et
cachées. Deux mécanismes principaux existent pour traiter ces contraintes : la barrière
extrême et la barrière progressive.

La barrière extrême

La première version de Mads, présentée dans [Audet et Dennis, Jr.(2006)], ne

possédait que la barrière extrême comme mécanisme de gestion des contraintes. Elle
ne nécessite pas de modifier l’algorithme présenté ci-dessus. Elle consiste à remplacer
la fonction objectif f par une fonction fΩ définie comme suit :

f (x)

si x ∈ Ω,
fΩ (x) =  (4.10)
+∞ sinon.
 57

La barrière progressive

La barrière progressive, définie par [Audet et Dennis, Jr.(2009)], distingue les con-
traintes non relaxables, définies par le domaine X, des contraintes relaxables définies
par les fonctions cj . Elle définit une fonction de violation de contraintes h de la façon
suivante : 
 m (max(cj (x), 0))2 si x ∈ X,
 P
j=1
h(x) = (4.11)
+∞

sinon.

La fonction de violation de contraintes prend la valeur h(x) = 0 si et seulement

x ∈ Ω. D’autre part, si le point x n’est pas réalisable mais ne viole que les contraintes
relaxables, on a 0 < h(x) < +∞. On obtient ainsi une mesure de la violation des
contraintes. Lors de la progression de l’algorithme, un paramètre hmaxk ≥ 0 est utilisé
définissant le seuil d’acceptation ou de rejet d’un point d’essai. Ainsi, tout point x tel
que h(x) > hmax
k sera rejeté. Le seuil hmax
k est progressivement abaissé au cours de la
recherche pour forcer une violation des contraintes de moins en moins importante.

4.3.6 Ordre d’évaluation

Les solutions du voisinage de sonde Pk sont évaluées lors de l’étape de sonde.
L’ordre d’évaluation des solutions peut avoir une influence importante sur l’efficacité
de l’algorithme. Il est donc intéressant de chercher une stratégie d’évaluation efficace
plutôt que d’évaluer les solutions dans un ordre quelconque. La stratégie la plus
souvent utilisée est la stratégie opportuniste, qui consiste à évaluer en premier lieu
lors d’une itération les directions qui ont donné lieu à un succès le plus récemment
lors des itérations précédentes, et à arrêter l’évaluation des solutions du voisinage de
sonde dès qu’un succès est obtenu.

4.4 Analyse de convergence

L’algorithme Mads est un des premiers algorithmes de recherche par motifs à
bénéficier d’une analyse de convergence complète pour l’optimisation non lisse sous
contraintes. Pour pouvoir présenter les résultats de convergence de l’algorithme, il
faut d’abord introduire des définitions de calcul non lisse.
 58

4.4.1 Notions d’analyse non lisse

Dans le cadre de l’établissement de conditions d’équilibre pour des fonctions non
lisses, l’étude des dérivées d’une fonction régulière est remplacée par l’étude de la
dérivée directionnelle généralisée de Clarke dans les directions contenues dans le cône
hypertangent en un point. La dérivée directionnelle généralisée s’applique aux fonc-
tions Lipschitz, définies comme suit :

Définition 1. Soient I un sous-ensemble non vide de Rn et un réel λ > 0. La fonction

f : I → R est dite λ-lipschitzienne ou λ-Lipschitz si :

∀(x, y) ∈ I 2 , |f (x) − f (y)| ≤ λ kx − yk .

Une fonction f est dite lipschitzienne ou Lipschitz s’il existe λ > 0 tel que f est
λ-lipschitzienne.

La dérivée directionnelle généralisée est alors introduite par [Clarke(1983)] de la

façon suivante :

Définition 2. Soient une fonction f localement Lipschitz autour d’un point x ∈ Rn ,

un vecteur v ∈ Rn et un réel positif t ∈ R+ . La dérivée directionnelle généralisée de
f en x dans la direction v est notée f ◦ (x; v) et est définie ainsi :

f (y + tv) − f (y)
f ◦ (x; v) = lim supy→x .
t

Notons B (x) = {y ∈ Rn : ||y − x|| ≤ } la boule fermée de rayon  centrée en x.

Introduisons enfin le cône hypertangent, défini par [Rockafellar(1980)] :

Définition 3. Un vecteur v ∈ Rn est dit hypertangent à l’ensemble Ω ⊂ Rn au point

x ∈ Ω s’il existe un réel  > 0 tel que :

y + tw ∈ Ω pour tout y ∈ Ω ∩ B (x), w ∈ B (v) et t ∈ ]0, [ .

L’ensemble des vecteurs hypertangents à Ω en x est appelé le cône hypertangent à Ω

en x et se note TΩH (x).

C’est une généralisation du cône tangent, obtenu par des combinaisons linéaires
des gradients des contraintes, lorsque celles-ci sont différentiables.
 59

4.4.2 Résultats de convergence

Les preuves des résultats de l’analyse de convergence énoncées dans cette section
ont été développées par [Audet et Dennis, Jr.(2006)]. Elles reposent sur l’hypothèse
suivante :

Hypothèse 1. La suite d’itérés produite par Mads appartient à un sous-ensemble

borné de Rn .

Introduisons d’abord les définitions de sous-suite raffinante et de direction raffi-

nante, propres à l’algorithme Mads :

Définition 4. Une sous-suite de centres de sonde {xk }k∈K , pour un sous-ensemble

d’indices K ⊂ N, convergente vers x̂, est une sous-suite raffinante si limk∈K ∆m
k = 0.

Définition 5. Si la limite limk∈L kddkk k existe pour un sous-ensemble d’indices L ⊆ K

avec des directions de sonde dk ∈ Dk , et si xk + ∆m k dk ∈ Ω pour une infinité d’indices
k ∈ L, alors cette limite est une direction raffinante pour x̂.

On peut alors énoncer le théorème de convergence de Mads :

Théorème 1. Soit f une fonction Lipschitz autour de la limite x̂ ∈ Ω d’une sous-

suite raffinante, et supposons que TΩH (x̂) 6= ∅. Si l’ensemble des directions raffinantes
pour x̂ est dense dans TΩH (x̂), alors x̂ est un point Clarke-stationnaire de f sur Ω,
c’est-à-dire que f ◦ (x̂; v) ≥ 0 pour tout v ∈ TΩH (x̂).

Ce résultat est une généralisation au cas des fonctions simplement Lipschitz des
conditions KKT (Karush-Kuhn-Tucker) pour une fonction strictement différentiable.
On peut en effet obtenir ce second résultat comme un corollaire du premier :

Corollaire 1. Soit f une fonction strictement différentiable autour de la limite x̂ ∈ Ω

d’une sous-suite raffinante, et supposons que TΩH (x̂) 6= ∅. Si l’ensemble des direc-
tions raffinantes pour x̂ est dense dans TΩH (x̂), alors x̂ est un point Clarke-KKT-
stationnaire pour f sur Ω.

Il est à noter que les résultats énoncés ici nécessitent que l’algorithme génère un
ensemble de directions raffinantes denses dans TΩH (x̂). Il existe différentes stratégies
de génération des directions de sonde permettant de satisfaire cette condition. Parmi
celles-ci on peut citer la stratégie OrthoMads, une instance de l’algorithme Mads
présentée dans [Abramson et al.(2009b)].
 60

4.5 Nomad
Nomad est un logiciel développé en C++ implémentant l’algorithme Mads. Le
projet Nomad a été initié par [Abramson et al.(2003)] et développé par [Le Diga-
bel(2011)]. Il permet le développement rapide d’applications d’optimisation de boîte
noire, grâce à l’existence d’un mode console pour les problèmes les plus simples. Pour
les problèmes plus complexes, le mode librairie permet le paramétrage complet de
l’algorithme Mads et l’utilisation de nombreuses fonctionnalités avancées, présentées
ici.

Variables de catégorie

L’algorithme Mads classique ne fonctionne qu’avec des variables prenant leurs

valeurs dans un ensemble ordonné, et tire parti de la relation d’ordre qui existe dans
cet ensemble. Les variables de catégorie, dont l’utilisation avec Mads est introduite
par [Audet et Dennis, Jr.(2001)], sont quant à elles des variables prenant des valeurs
discrètes dans un ensemble non ordonné. L’analyse de convergence de Mads a été
étendue à ce type de variables par [Abramson et al.(2009a)], et la gestion de ces
variables est implémentée dans Nomad.

Variables périodiques

Les variables périodiques sont également supportées par Nomad. Elles bénéficient
d’une analyse de convergence dans [Audet et Le Digabel(2011)]. Le gain d’efficacité
qu’elles apportent dans le déroulement de l’algorithme est incontestable lorsqu’il s’agit
par exemple de traiter des variables représentant des angles.

Optimisation biobjectif

Au lieu de se contenter d’une fonction objectif f unique, l’optimisation biobjectif

cherche à optimiser un problème comportant deux fonctions objectif f1 et f2 . Au
sein de Nomad, elle est réalisée grâce à l’algorithme BiMads, présenté dans [Audet
et al.(2008d)] et qui construit une approximation du front Pareto du problème en
lançant de multiples instances de Mads mono-objectif.
 61

Recherche globale à voisinage variable

Nomad implémente une stratégie de recherche globale dont l’utilisateur peut choi-
sir de se servir pour l’étape de recherche de Mads. Elle permet de diversifier les
zones de recherche et de traiter les problèmes possédant de multiples optima locaux.
Il s’agit d’un algorithme de type VNS, dont le couplage avec Mads est proposé et
décrit dans [Audet et al.(2008b)].

Groupes de variables

L’utilisation de groupes de variables permet de définir des ensembles de variables

intéressantes à traiter conjointement. Par exemple, dans un problème de localisation, il
peut être intéressant de grouper les 2 ou 3 variables représentant la position d’un objet
dans l’espace à 2 ou 3 dimensions. L’utilisation des groupes de variables a été explorée
en profondeur par [Garnier(2010)] grâce à l’application au problème de localisation
de balises permettant d’estimer le couvert nival dans un bassin hydrologique.

Parallélisme

Nomad implémente différentes extensions de Mads permettant l’évaluation en

parallèle de plusieurs solutions, notamment grâce à l’algorithme Psd-Mads présenté
dans [Audet et al.(2008c)]. Ces extensions, implémentées avec la bibliothèque Mpi,
permettent de réduire les temps d’exécution de façon importante et de traiter de plus
gros problèmes. D’autres exemples d’algorithmes parallèles pour Mads sont décrits
dans [Le Digabel et al.(2010)].
 62

Chapitre 5

Optimisation d’un réseau

La boîte noire conçue dans le chapitre 3 permet d’effectuer des simulations de

couverture d’un réseau d’accès sans fil. C’est grâce à ces simulations qu’est effectuée
l’optimisation du placement des antennes du réseau ainsi que de leur assignation de
fréquence.

5.1 Définition de la simulation et notations

Comme précédemment, on considère un réseau d’accès constitué de p antennes
A1 , A2 , . . . , Ap et de q canaux C1 , C2 , . . . , Cq .

5.1.1 Entrées de la boîte noire

Les variables d’entrée de la boîte noire appartiennent à deux catégories : les va-
riables de position des antennes, et les variables de canaux.

Variables de position

Le problème traité dans ce travail est à deux dimensions d’espace, et les antennes
sont placées sur une surface plane. En revanche, le territoire considéré peut être
de forme quelconque. La position des antennes est repérée par leurs coordonnées
Xi = (xi , yi ), i ∈ J1, pK. La région du plan correspondant au territoire autorisé pour
le placement des antennes sera notée T .
Les variables de position sont au nombre de 2p, et sont des variables continues.
Cependant, même si la boîte noire accepte des variables réelles en entrée pour les
positions des antennes, les calculs sont réalisés sur un terrain discrétisé.
 63

Variables d’assignation de canaux

Chaque antenne émet et reçoit sur un canal (ou un groupe de canaux) donné.
Chaque groupe de canaux Cj , j ∈ J1, qK correspond à des fréquences d’onde por-
teuses différentes. On considère dans le modèle que les interférences entre canaux
sont négligeables, et on n’en tient donc pas compte. En revanche les antennes possé-
dant le même canal interfèrent entre elles, puisqu’elles émettent et reçoivent sur les
mêmes fréquences.
On notera ci le canal de l’antenne Ai . On pourra considérer indifféremment que
ci ∈ {1, 2, . . . , q} ou que ci ∈ {C1 , C2 , . . . , Cq }, selon la notation la plus commode.
D’autre part, il est utile de définir A(Cj ) comme l’ensemble des antennes utilisant
le canal Cj :
A(Cj ) = {Ai : ci = Cj , i ∈ J1, pK} . (5.1)

Ces variables d’assignation de canaux ci , au nombre de p, sont de nature combi-

natoire, et peuvent prendre q valeurs différentes. Il faut les traiter avec une méthode
adaptée aux variables entières.

5.1.2 Sorties de la boîte noire

En réponse à une entrée donnée, la boîte noire simule le réseau de télécommu-
nications et calcule un plan de couverture du terrain par les différentes antennes,
comme décrit dans le chapitre 3. Ce plan permet alors de déterminer toutes les sor-
ties importantes dont on a besoin. Les informations pertinentes que l’on peut obtenir
sont :
– la couverture géographique totale du réseau A ;
– le nombre total d’usagers servis N ;
– la variance du nombre d’usagers par antenne V ;
– la charge maximale des antennes Nmax .
Cette situation est illustrée par la figure 5.1.

Appartenance au territoire T

Une autre information utile dans le cadre de l’optimisation et qui n’a pas encore été
mentionnée est la mesure de la violation de la contrainte d’appartenance des antennes
au territoire T . Soit d(Xi , T ) la distance du point Xi , représentant la localisation de
 64

(X1 , X2 , . . . , Xp ) - Couverture A
-
Positions des antennes - Nombre d’usagers N
Boîte noire
(c1 , c2 , . . . , cp ) - Variance V
-
Assignation des canaux - Charge maximale Nmax

Figure 5.1 Entrées et sorties de la boîte noire

l’antenne Ai , au territoire T . C’est la distance du point Xi au point de T le plus

proche de Xi . La mesure de la violation de la contrainte d’appartenance à T peut
être exprimée de la manière suivante :
p
d(Xi , T )2 .
X
dT,2 = (5.2)
i=1

5.2 Plan général de l’algorithme

L’algorithme développé ici se déroule en plusieurs étapes. Dans un premier temps,
une solution initiale est construite. Puis cette solution est améliorée de façon itérative
au sein d’une boucle.
Le plan général de l’algorithme utilisé est décrit dans l’algorithme 6.

Algorithme 6: Plan général

Initialisation :
Construire une solution initiale
Recherche :
Optimiser l’assignation de canaux (recherche tabou)
Optimiser le placement des antennes (algorithme Mads)
Bouclage :
Si un critère d’arrêt n’est pas atteint, recommencer l’étape de recherche

Au sein de la boucle d’optimisation, deux méthodes sont utilisées. En effet, les

variables d’entrée que l’on manipule sont de natures différentes : les variables de
position sont considérées comme continues, alors que les variables d’assignation de
canaux sont combinatoires. Il n’est donc pas forcément judicieux d’utiliser la même
méthode d’optimisation pour traiter ces deux groupes de variables.
 65

Variables continues

Les variables continues, qui sont les variables de position, seront traitées avec
l’algorithme Mads, présenté dans le chapitre 4.

Variables combinatoires

Les variables d’assignation de canaux ne peuvent pas être traitées de la même façon
que les variables continues. La principale difficulté, en dehors du fait qu’il s’agisse de
variables discrètes, est qu’il n’existe pas de relation d’ordre entre les différentes valeurs
prises par ces variables.
Il s’agit de variables de catégorie et l’algorithme Mads avec extension aux va-
riables de catégorie pourrait être utilisé. Dans ce cas, le problème traité serait alors
un problème d’optimisation de boîte noire à 3p variables, dont p seraient des variables
de catégorie. Ce problème serait très lourd et coûteux, et n’exploiterait aucunement
le fait que les variables combinatoires ont un rôle particulier.
Pour traiter ces variables, une métaheuristique sera utilisée. Ce type d’algorithme
est destiné au traitement des problèmes combinatoires. Plus précisément, l’algorithme
choisi est une recherche tabou, qui sera décrite plus loin.

Critère d’arrêt

Différents critères d’arrêt peuvent être utilisés. Le plus évident serait sans doute
d’utiliser un critère de qualité de la solution, qui permettrait de continuer l’optimisa-
tion jusqu’à ce que la solution obtenue soit jugée de qualité suffisante. Cependant, il
peut être difficile de définir précisément un objectif de qualité. En effet, avant d’effec-
tuer l’optimisation, on ne peut pas vraiment savoir quelle serait la solution optimale,
et donc à quelle distance on s’en trouve tout au long de la recherche.
Un autre critère simple à utiliser est une borne supérieure sur le nombre d’itéra-
tions de chaque type de recherche. C’est par exemple le type de borne qui sera utilisé
pour la recherche tabou.
Pour la recherche directe avec Mads, une particularité intéressante de l’algorithme
est l’utilisation d’un treillis. Étant donné que le terrain est discrétisé, il est inutile
d’essayer de placer les antennes avec une précision plus importante que la taille du
pas de discrétisation. On peut donc arrêter la recherche lorsque la taille du treillis
 66

interne de Mads passe en-dessous de la taille du pas de discrétisation, car on sait que
l’algorithme ne pourra alors plus améliorer la solution.

5.3 Mise en place du problème

Les informations que l’on peut obtenir en sortie de la boîte noire sont nombreuses
et de natures différentes. Il est donc important de comprendre le rôle de chacune et
de bien définir les objectifs à atteindre pour pouvoir bien exploiter les informations
disponibles.

5.3.1 Couverture géographique et nombre total d’usagers

Le premier objectif que l’on veut atteindre lors de l’optimisation d’un réseau de
télécommunications est la maximisation de sa couverture. Mais déjà une première
question se pose : parle-t-on de la couverture géographique, ou de la couverture en
termes de population servie ? En fait, c’est au concepteur du réseau de déterminer
quel aspect sera le plus important pour lui, et son choix sera guidé par le type de
zone géographique à couvrir.
Dans le cas d’une zone urbaine, la population à servir est généralement répartie
sur une grande partie du territoire, et il serait inadmissible d’avoir des régions non
desservies au milieu d’une ville ou dans ses environs proches. Il est préférable dans
ce cas d’essayer de couvrir l’ensemble du territoire, et toute la population sera alors
également couverte.
Dans le cas d’une zone rurale, ou d’un territoire très étendu comme une province
ou un pays, la population ne recouvre plus qu’une petite partie de la région considérée.
Couvrir l’ensemble du territoire serait alors trop coûteux et inutile. On préfèrera donc
dans ce cas maximiser le nombre d’usagers servis. Ainsi, seules les zones nécessitant
réellement une couverture du réseau seront desservies.

Le présent travail ne se concentre que sur des zones de type urbain, où la popu-
lation à servir recouvre l’ensemble du territoire. La distinction entre les objectifs de
couverture géographique A et de la population N reste importante dans le cas où il
n’est pas possible d’arriver à une couverture totale. En effet, la densité de population
D, a priori inhomogène, intervient dans le calcul de N , alors que pour A, tous les
points du territoire ont la même importance.
 67

Cependant, si le réseau parvient à réaliser une couverture complète, les objectifs

de couverture géographique et de la population sont équivalents, et dans ce cas l’un
ou l’autre de ces deux points de vue peut être utilisé indifféremment.
Il a été fait le choix ici de privilégier une approche qui tienne compte de la non-
homogénéité de la répartition de la population. On choisit donc de maximiser le
nombre total d’usagers servis N .

5.3.2 Équilibrage de la charge

L’objectif de maximisation de la couverture est insuffisant pour réaliser l’opti-
misation. Deux situations peuvent se présenter. Premièrement, s’il n’est pas pos-
sible de réaliser une couverture complète, l’objectif de maximisation de la couverture
conduit l’optimisation à éloigner les antennes d’un même canal les une des autres, afin
d’agrandir la zone de couverture de chacune et de couvrir un maximum d’usagers.
Cela mène généralement à des solutions aberrantes où quelques antennes seulement
servent des utilisateurs et les autres, rejetées aux limites du territoire, sont presque
inutiles. Deuxièmement, si une couverture totale peut être atteinte, il existe alors un
grand nombre de solutions équivalentes qui maximisent la couverture mais qui ne
peuvent pas être distinguées.
D’autre part, il a été montré dans le chapitre 2 qu’une antenne ne peut servir
qu’un nombre limité d’usagers. Plus une antenne est chargée, plus la qualité de la
communication d’un nouvel usager voulant se connecter via cette antenne sera dégra-
dée. Il est donc important de garder le nombre d’usagers à servir par chaque antenne
aussi bas que possible.
L’introduction d’un objectif d’équilibrage de la charge des antennes est donc néces-
saire. Le rôle de cet objectif est de minimiser la charge supportée par chaque antenne
en essayant de répartir la charge totale entre toutes les antennes. La variance du
nombre d’utilisateurs par antenne V est un bon indicateur du déséquilibre de charge
entre les antennes et sera donc utilisé pour l’optimisation.

5.3.3 Séparation des problèmes

Dans notre algorithme d’optimisation, les deux aspects de l’optimisation que sont
le placement des antennes et l’assignation de canaux sont traités séparément. Les
deux problèmes ne sont pourtant pas séparables, et il pourrait être tentant de les
 68

traiter ensemble avec une méthode d’optimisation bi-objectif. La méthode utilisée ici
est cependant une méthode d’optimisation mono-objectif, pour deux raisons princi-
pales. Premièrement, l’optimisation bi-objectif est très longue et coûteuse en temps
de calcul, beaucoup plus que l’optimisation mono-objectif. Deuxièmement, elle n’est
pas nécessaire ici, car on ne veut pas calculer un front de Pareto complet, mais obtenir
seulement une solution qui réalise un compromis entre les deux aspects.

5.4 Construction de la solution initiale

Lors de la construction de la solution initiale, on cherche avant tout à trouver un
placement des antennes de qualité correcte. La méthode développée ici se déroule en
deux parties. La première est inspirée de techniques de reconnaissance d’images et de
formes, utilisées notamment en robotique pour localiser, identifier et positionner des
objets filmés par une caméra. La seconde utilise l’algorithme Mads avec l’approxi-
mation de la simulation par diagrammes de Voronoï.

5.4.1 Centre géométrique et centre de masse

Le centre géométrique d’une région du plan est, de façon intuitive, la « moyenne »
de tous les points de la région.
Soit R une région du plan. Son aire A est définie de la façon suivante :
ZZ
A= dx dy. (5.3)
R

Les coordonnées de son centre (xc , yc ) sont alors données par :

RR
x dx dy
R
xc = , (5.4)
RR A
y dx dy
yc = R . (5.5)
A

Le centre géométrique de R est l’unique point du plan qui minimise la somme des
distances à tous les autres points de R. On a donc l’intuition que ce point serait le
plus adapté pour placer une antenne si l’on voulait couvrir la région R. Cependant, on
voudrait aussi traiter des problèmes avec une densité de population non uniforme sur
le terrain considéré. Le centre géométrique n’est alors plus forcément un bon choix
 69

pour placer une antenne, et il faut trouver un placement initial tenant compte de
cette densité.
Introduisons alors la notion de centre de masse, par analogie avec la physique, où
il est aussi appelé centre de gravité. Soit D(x, y) une fonction de densité sur la région
R. Dans l’analogie mécanique, il s’agirait d’une densité de masse. La masse totale m
de la région R est alors : ZZ
m= D(x, y) dx dy. (5.6)
R

Les coordonnées (xm , ym ) du centre de gravité sont données par les équations
suivantes :
RR
x D(x, y) dx dy
R
xm = , (5.7)
RR m
y D(x, y) dx dy
ym = R . (5.8)
m

Si D représente la densité de population sur la région R, m est alors la popula-

tion totale à l’intérieur de cette région et le centre de masse est le barycentre de la
population.

5.4.2 Moments centraux et découpage

Le centre de masse, tel que défini ci-dessus, semble être un bon choix pour le
placement initial d’une antenne sur une région du plan. Cependant, cette information
est insuffisante si on veut placer un plus grand nombre d’antennes. Idéalement, il
faudrait trouver un placement qui équilibre la charge de toutes les antennes, c’est-à-
dire qu’elles servent toutes le même nombre d’utilisateurs. Pour essayer d’approcher
une telle configuration, on tente de découper le territoire en n régions contenant
chacune le même nombre d’usagers.
Afin de réaliser un bon découpage, il faut analyser la structure du territoire et
obtenir des informations sur la répartition de la population. Pour cela, la méthode
des moments centraux est utilisées. Le moment central d’ordre (α + β), où α et β
sont deux entiers positifs, est défini par :
ZZ
µαβ = (x − xm )α (y − ym )β D(x, y) dx dy (5.9)
R

où (xm , ym ) sont les coordonnées du centre de masse de R.

 70

On définit ensuite le moment central normalisé d’ordre (α + β) comme :

µαβ
ηαβ = (5.10)
(µ00 )γ

avec
α+β
γ= + 1. (5.11)
2
Les seuls moments qui sont utiles ici sont les moments η11 , η20 et η02 . Le moment η11
quantifie l’éloignement de la population par rapport au centre de masse. Les moments
η02 et η20 renseignent quant à eux sur la direction dans laquelle la population est le
plus étalée. C’est cette information qui est importante : si η02 > η20 , la population
est plus étalée le long de l’axe des x, alors que si η02 < η20 , elle est plus étalée selon
l’axe des y.
Grâce à cette information, on peut réaliser le découpage de la région R en deux
régions R1 et R2 en sachant s’il est plus judicieux de l’effectuer selon l’axe des x ou
des y. Ainsi, si η02 > η20 , R sera coupé en deux par une droite verticale, placée de telle
sorte que les deux parties résultantes contiennent la même population. Si au contraire
η02 < η20 , c’est par une droite horizontale que R sera coupé.

On pourrait également calculer l’angle de l’axe principal de la région R, au regard

de la densité de population D(x, y), avec la formule suivante :

1
θ= atan2(2µ11 , µ20 − µ02 ) (5.12)
2

Cet angle donne la direction de l’axe dans lequel la population est la plus étalée.
Couper R selon une droite perpendiculaire à l’axe principal permettrait d’obtenir une
meilleure répartition.

5.4.3 Placement récursif des antennes

La méthode qui vient d’être décrite permet de trouver un bon découpage du
terrain. Le placement initial des antennes peut alors être effectué de façon récursive
grâce à l’algorithme 7.
 71

Algorithme 7: Fonction récursive de placement des antennes.

Données :
Nombre d’antennes à placer : p
Territoire à découper : R
Densité de population : D(x, y)
Fonction récursive : PlacerAntennes(p, R, D)
Calculer les coordonnées (xm , ym ) du centre de masse de R
si p = 1 alors
Retourner (xm , ym )
sinon
Soit d la droite de découpe
Calculer les moments µ11 , µ20 et µ02
si η02 > η20 alors
Orienter d verticalement
sinon
Orienter d horizontalement
fin
Calculer la position de d pour couper R en régions de même poids
Couper R en deux régions R1 letmR2 selon d
positions1 = PlacerAntennes( p2 , R1 , D)
j k
positions2 = PlacerAntennes( p2 , R2 , D)
Retourner (positions1 , positions2 )
fin

5.4.4 Amélioration du placement initial

Le placement initial obtenu à l’issue de la première phase est utilisé comme point
de départ pour la seconde phase. Dans cette deuxième partie, la boîte noire est utilisée
pour réaliser des simulations à l’aide de la méthode des diagrammes de Voronoï décrite
dans le chapitre 3. On ne se préoccupe ici pas encore de l’assignation de canaux, et
seule la localisation des antennes est optimisée.
La boîte noire en mode Voronoï permet de calculer le nombre d’usagers Ni servis
par chaque antenne en assimilant leurs zones de couverture à leurs régions de Voronoï.
La variance V des charges des antennes est une approximation de sa valeur réelle,
telle qu’elle serait calculée avec le modèle complet. On n’a pas ici à tenir compte de
l’objectif de couverture, puisque le diagramme de Voronoï couvre tout le territoire. On
peut donc se concentrer sur l’objectif d’équilibrage des charges, en utilisant seulement
V comme sortie.
 72

L’algorithme Mads est utilisé pour réaliser cette deuxième phase de construction
de la solution initiale, avec les paramètres suivants :
– entrées de la boîte noire : les localisations des antennes (X1 , X2 , . . . , Xp ) ;
– fonction objectif : la variance des charges des antennes V ;
– contrainte : la mesure de la violation de la contrainte d’appartenance au terri-
toire dT,2 ;
– critère d’arrêt : arrêter lorsque la taille du treillis atteint la taille de discrétisa-
tion du territoire.
Avec des territoires de formes réalistes, il est rare que la localisation des antennes
viole la contrainte d’appartenance au territoire. Ce problème d’optimisation est donc
principalement le problème non contraint de minimisation de la variance V.

5.4.5 Assignation initiale de canaux

Pour ce qui est de l’assignation de fréquence, il n’est pas évident de trouver une
heuristique permettant de donner facilement un bon résultat. En outre, il n’est pas
nécessaire de démarrer avec une bonne assignation de canaux car la première étape
de la recherche subséquente permet d’améliorer très rapidement le choix des canaux.
Une simple numérotation séquentielle des canaux suffit alors : ci = i mod q.

5.5 Recherche tabou

L’assignation des canaux dans le réseau est un problème combinatoire. Son trai-
tement est réalisé grâce à une recherche tabou. Le fonctionnement de ce type de
recherche est décrit dans cette section.

5.5.1 Métaheuristiques
Une métaheuristique est un algorithme d’optimisation destiné à résoudre des pro-
blèmes difficiles, en général de façon non optimale. Les métaheuristiques sont parti-
culièrement adaptées aux problèmes combinatoires, pour lesquels on ne connait pas
de méthode efficace de résolution optimale.
Il existe de nombreux types de métaheuristiques, possédant chacune des caracté-
ristiques différentes et étant adaptées à différents types de problèmes. Dans ce travail,
c’est une recherche tabou qui a été choisie, car il s’agit d’une métaheuristique assez
 73

simple à mettre en place et présentant généralement de bonnes performances sur les

problèmes de coloration de graphes, auxquels le problème d’assignation de canaux
peut se ramener.

5.5.2 La recherche tabou

La recherche tabou est une métaheuristique itérative, introduite par [Glover(1989)].
Elle a été depuis très largement utilisée pour traiter de nombreux problèmes d’op-
timisation combinatoire, et reste populaire aujourd’hui en raison de sa puissance et
de sa facilité de mise en œuvre, comme en témoignent des applications récentes dé-
crites dans [Galinier et al.(2011)], [St-Hilaire et Liu(2011)] ou [Rajalakshmi et Hima
Bindu(2011)].
La recherche tabou consiste, en partant de la solution actuelle, à explorer un en-
semble de solutions proches, que l’on nomme voisinage, et à se déplacer vers l’élément
du voisinage possédant la meilleure valeur de la solution objectif. Ce processus est en-
suite répété jusqu’à atteindre le critère d’arrêt souhaité. Sous cette forme, l’algorithme
ressemble de très près à une classique méthode de descente, mais permet en réalité
de s’échapper des minima locaux et d’explorer efficacement l’espace de recherche.
Si la solution actuelle est un minimum local, les solutions voisines ont une va-
leur de la fonction objectif supérieure. À la différence des algorithmes de descente,
la recherche tabou se déplace alors vers une solution de moins bonne qualité. Une
difficulté apparaît immédiatement : si l’algorithme s’échappe d’un minimum local en
dégradant la solution, il y a de fortes chances que la position qu’il vient de quitter soit
dans le nouveau voisinage, et qu’il y retourne à l’itération suivante. C’est pourquoi il
est nécessaire de mettre en place un mécanisme de mémoire, appelé liste tabou. Cette
liste contient l’ensemble des positions qui ont été explorées, et l’algorithme interdit
d’y revenir tant qu’elles sont dans la liste. Ce mécanisme permet de ne pas retomber
dans les minima locaux et de franchir les zones de valeurs de la fonction objectif plus
élevées, pour ensuite espérer retomber vers un minimum plus bas.

Pour écrire l’algorithme de façon mathématique, introduisons les notations sui-

vantes :
– f : fonction objectif ;
– s : solution actuelle ;
– s∗ : meilleure solution trouvée jusqu’à présent ;
 74

– N (s) : voisinage de la solution s ;

– L : liste tabou.
Une recherche tabou typique est décrite par l’algorithme 8. Une autre façon de gérer la
structure de voisinage et les déplacements dans l’espace de recherche est l’utilisation
de mouvements. La section suivante décrit une version modifiée de la recherche tabou
avec l’utilisation de mouvements.

Algorithme 8: Recherche tabou

Initialisation :
s = s∗ = s0
L=∅
Recherche :
tant que critère d’arrêt non atteint faire
eval = ∞
pour s0 ∈ N (s) faire
si f (s0 ) < eval et s0 6∈ L alors
ŝ = s0
eval = f (s0 )
fin
fin
s = ŝ
L = L ∪ {s}
si f (s) < f (s∗ ) alors s∗ = s
fin

5.5.3 Recherche tabou avec mouvements

Il n’est pas toujours judicieux de garder des solutions complètes dans la liste tabou,
même lorsque le problème n’est pas très grand. En effet, cela peut conduire à stocker
de grandes quantités de données, et à alourdir le travail de recherche dans la liste.
C’est pourquoi il est souvent préférable de ne stocker que la suite de mouvements qui
a conduit à l’état actuel.
Lorsque l’on travaille avec les mouvements, le voisinage de la solution actuelle,
auparavant noté N (s), ne contient plus des solutions complètes mais des mouvements,
et il sera alors noté Nm (s). Pour évaluer les solutions voisines de s définies par la
structure de voisinage, chaque mouvement m ∈ Nm (s) est appliqué à s et la solution
 75

résultante est évaluée. La solution obtenue par application d’un mouvement m à une
solution s sera notée m|s.
La liste tabou, elle aussi, contient maintenant des mouvements et non des solutions
complètes. Elle sera notée Lm pour éviter des confusions. Il faut bien voir les consé-
quences de considérer des mouvements plutôt que des solutions. Il n’est plus possible
de garder dans la liste tabou tous les mouvements effectués précédemment, sinon il
arriverait un moment où plus aucun mouvement ne serait possible et l’algorithme
serait bloqué. D’autre part, un mouvement qui vient d’être effectué doit être interdit
pour ne pas retourner immédiatement à la position précédente, mais il est tout à fait
possible qu’il soit intéressant de l’effectuer à nouveau plus tard dans la recherche, une
fois que l’on se sera éloigné du minimum local auquel on voulait échapper. Il faut
donc limiter la taille de la liste tabou, en n’y gardant les mouvements que pendant
un certain nombre d’itérations.
La nouvelle version de l’algorithme avec l’utilisation de mouvements est décrite
par l’algorithme 9.

5.6 Optimisation de l’assignation de canaux

L’optimisation de l’assignation de canaux est réalisée en deux étapes distinctes.
Ces deux étapes sont deux recherches tabou effectuées l’une à la suite de l’autre. Au
cours de la première, la couverture du réseau est maximisée, alors qu’au cours de la
seconde, l’équilibrage des charges des antennes est optimisé. Ces deux instanciations
de la recherche tabou sont strictement identiques et partagent donc les mêmes ca-
ractéristiques, à l’exception des fonctions objectif utilisées dans chacune. Toutes les
caractéristiques des recherches sont décrites dans cette section.

5.6.1 Caractéristiques des recherches tabou

Les deux recherches tabou utilisées pour l’optimisation de l’assignation de canaux
sont des instanciations particulières de l’algorithme de la recherche tabou décrit ci-
dessus. Il suffit de redéfinir tous les paramètres de l’algorithme pour caractériser
complètement la recherche. Les paramètres à redéfinir sont :
– le type de recherche : classique en utilisant des solutions complètes, ou en uti-
lisant des mouvements ;
 76

Algorithme 9: Recherche tabou avec utilisation de mouvements.

Initialisation :
s = s∗ = s0
Lm = ∅
Recherche :
tant que critère d’arrêt non atteint faire
eval = ∞
pour m ∈ Nm (s) faire
si f (m|s) < eval et m 6∈ Lm alors
ŝ = m|s
eval = f (m|s)
fin
fin
s = ŝ
Lm = Lm ∪ {s}
si f (s) < f (s∗ ) alors s∗ = s

pour m ∈ Lm faire
si m doit être retiré de Lm alors
Lm = Lm \{m}
fin
fin
fin

– la forme des solutions s ;

– le domaine de recherche ;
– la fonction objectif f ;
– la nature des mouvements m le cas échéant ;
– la structure de voisinage N (s) ou Nm (s) ;
– la longueur de la liste tabou ;
– le critère d’arrêt.
Cette section décrit les paramètres communs aux deux recherches, c’est-à-dire tous
sauf la fonction objectif, qui sera discutée à la section suivante.

Type de recherche

La recherche utilisée ici est une recherche tabou avec mouvements, plutôt qu’une
recherche avec solutions complètes.
 77

Forme des solutions

Les solutions sont représentées par un vecteur de taille p, sous la forme s =

(c1 , c2 , . . . , cp ), où chaque ci est, comme défini précédemment, le canal de l’antenne
Ai , et représente un canal parmi {C1 , C2 , . . . , Cq }.

Nature des mouvements

Les mouvements utilisés sont des échanges (swaps en Anglais), c’est-à-dire qu’un
mouvement peut être représenté par un couple (i, j), signifiant qu’il faut échanger les
canaux des antennes Ai et Aj . Considérant une solution s = (c1 , c2 , . . . , cp ), l’applica-
tion du mouvement m = (i, j) donne la solution :

m|s = (c1 , c2 , . . . , ci−1 , cj , ci+1 , . . . , cj−1 , ci , cj+1 , . . . , cp ) (si i < j).

Domaine de recherche

Le réseau est constitué de p antennes et q groupes de canaux. Les antennes pour-

raient être réparties, a priori, de façon quelconque entre les canaux, qui pourraient
ainsi avoir des nombres d’antennes différents. Certains groupes d’antennes pourraient
alors jouer un rôle différent des autres, permettant de mettre en œuvre des techniques
avancées de conception de réseaux. Cependant, le choix de techniques spécifiques est
un sujet complexe qui dépend de décisions de conception qui sortent du cadre de
l’optimisation.
On ne fait dans ce travail aucun choix de conception particulier. Tous les canaux
sont équivalents, et chacun d’eux se voit attribuer le même nombre d’antennes. Le
nombre d’antennes p est ainsi contraint à être un multiple du nombre de canaux q,
et le nombre d’antennes dans chaque canal est pq .
Il conviendra dans la recherche tabou d’assurer que toutes les solutions manipulées
soient bien de cette forme. On remarquera que l’algorithme séquentiel utilisé pour
générer une attribution de canaux initiale produit bien une solution valide.

Structure de voisinage

Étant donné que les échanges ne modifient pas le nombre d’antennes par canal
et mènent toujours à une solution valide, ils sont tous autorisés. Cependant, il n’est
pas nécessaire de tous les évaluer. Par exemple, il est inutile d’échanger les canaux
 78

de deux antennes si elles possèdent le même canal. De même, pour tout (i, j) dans
J1, pK2 , les mouvements (i, j) et (j, i) sont entièrement équivalents, puisqu’ils mènent à
la même solution. Il conviendra donc d’éviter d’inclure plusieurs mouvements menant
à la même solution.
Le voisinage d’une solution s = (c1 , c2 , . . . , cp ) peut être défini de la façon suivante :
n o
Nm (s) = (i, j) ∈ J1, pK2 : i < j, ci 6= cj . (5.13)

La détermination du nombre de mouvements contenus dans un voisinage Nm (s)

n’est pas triviale. Ce nombre peut être plus facilement évalué en réécrivant l’ensemble
de la façon suivante :

n o q n o
2
(i, j) ∈ J1, pK2 : i < j, ci = cj = k .
[
Nm (s) = (i, j) ∈ J1, pK : i < j \ (5.14)
k=1

Comme l’union d’ensembles est incluse dans l’ensemble de gauche, et que tous les
ensembles de l’union sont disjoints, on a :

n o p n o
2
(i, j) ∈ J1, pK2 : i < j, ci = cj = k
X
|Nm (s)| = (i, j) ∈ J1, pK : i < j − .
k=1
(5.15)
p(p−1)
D’une part, |{(i, j) ∈ J1, pK2 : i < j}| = (p − 1) + (p − 2) + · · · + 1 = D’autre 2
.
part, chaque canal Ck possède |A(Ck )| antennes. Le nombre de couples (i, j) que l’on
peut construire avec les entiers de 1 à |A(Ck )|, tels que i < j, est égal à :

|A(Ck )|(|A(Ck )| − 1)
(|A(Ck )| − 1) + (|A(Ck )| − 2) + · · · + 1 = .
2

On obtient donc :
q
p(p − 1) X |A(Ck )|(|A(Ck )| − 1)
|Nm (s)| = − . (5.16)
2 k=1 2

Lorsque n est un multiple de p, ce qui correspond au cas étudié, tous les canaux
ont le même nombre d’antennes |A(Ck )| = np . Le nombre de mouvements dans le
voisinage est alors : !
n2 1
|Nm (s)| = 1− . (5.17)
2 p
 79

La taille du voisinage peut devenir très importante pour les problèmes de grande
taille. Dans ce cas, l’évaluation complète du voisinage à chaque itération est trop
longue en temps de calcul. Le voisinage n’est donc pas entièrement généré, et seule une
partie de tous les mouvements possibles est évaluée. Il a été choisi de ne générer que
20 % du voisinage complet, car il a été observé sur plusieurs essais que cette proportion
permet de réduire le temps de calcul de façon importante tout en conservant de bons
résultats.

Longueur de la liste tabou

La longueur de la liste tabou désigne ici le nombre d’itérations pendant lequel

un mouvement restera tabou. Il existe deux stratégies principales pour le choix de la
longueur : la stratégie statique, où l’on fixe la longueur de la liste tabou au début de
la recherche, et la stratégie dynamique, où la longueur de la liste tabou est modifiée
au cours de la recherche.
Ici, une stratégie statique a été choisie, et la longueur de la liste tabou a été fixée à
10 itérations. Quelques essais ont permis de voir, empiriquement, que cette longueur
permettait d’obtenir de bons résultats.

Critère d’arrêt

Le critère d’arrêt utilisé est une limite sur le nombre d’itérations sans amélioration.
Un paramètre k est fixé au début de la recherche, qui se poursuit tant que k itérations
successives sans amélioration de la valeur de l’objectif n’ont pas été réalisées. De cette
façon, la recherche parvient à sortir des minima locaux dont il est facile de s’échapper,
mais lorsqu’elle rencontre un minimum difficile à améliorer, ce mécanisme évite d’y
passer trop de temps en stoppant la recherche en cours et en passant à l’étape suivante
de l’optimisation.
Quelques tests ont permis de déterminer de façon empirique qu’une valeur de
k = 15 permettait d’obtenir des résultats satisfaisants.

5.6.2 Fonctions objectifs

Les deux recherches tabou permettant de réaliser l’optimisation de l’assignation
de canaux diffèrent seulement par leur fonction objectif, qui est adaptée dans chaque
 80

cas à l’aspect qui doit être amélioré : la couverture du réseau, ou l’équilibrage de la

charge.

Couverture du réseau

Dans la première recherche tabou, on s’intéresse à la maximisation de la couverture

de la population, ou, de façon équivalente, à la minimisation de la population non
desservie par le réseau. Soit NT la population totale dans le territoire T . La population
non couverte est définie ainsi :

Nnc (s) = NT − N (s), (5.18)

où N est la population totale servie par le réseau, comme défini précédemment.

Équilibrage de la charge

Lors de la deuxième recherche tabou, l’équilibrage de la charge des antennes doit

être amélioré, tout en essayant de ne pas dégrader la couverture de la population.
Pour cela, une approche avec pénalité est utilisée. Le critère choisi pour mesurer
l’équilibrage de la charge est la variance de la charge des antennes V. Afin de calculer
la pénalité, les valeurs de la couverture N̂nc et de la variance V̂ obtenues à l’issue de
∼
la recherche précédente sont stockées. La fonction objectif avec pénalité V est définie
de la façon suivante :

Nnc (s) 2
 
∼  V(s)

+ si N̂nc > 0,
V̂ N̂nc
V(s) =  (5.19)
V(s)

V̂
+ (Nnc (s))2 si N̂nc = 0.

Les deux cas distingués dans cette fonction objectif correspondent aux situations
suivantes :
– N̂nc > 0 : la recherche précédente n’est par parvenue à atteindre une couverture
totale. Cette deuxième recherche est susceptible d’améliorer à la fois l’équili-
brage de la charge et la couverture ;
– N̂nc = 0 : une couverture totale est atteinte. Il n’est plus nécessaire d’améliorer
la couverture, puisqu’elle est maximale, mais il faut empêcher qu’elle soit trop
dégradée.
 81

Le cas V̂ = 0 correspondrait à un équilibrage optimal de la charge dans le ré-

seau. La solution correspondante serait optimale, et il n’y aurait aucun moyen de
l’améliorer. C’est pourquoi ce cas n’est pas considéré dans le calcul.

5.7 Optimisation de la localisation des antennes

L’optimisation de la localisation des antennes est réalisée au moyen de l’algorithme
de recherche directe Mads, décrit dans le chapitre 4. Il s’occupe des 2p variables de po-
sition des antennes (x1 , y1 ), (x2 , y2 ), . . . , (xp , yp ). La fonction objectif, les contraintes,
ainsi que les paramètres algorithmiques utilisés dans cette optimisation sont décrits
dans cette section.

5.7.1 Fonction objectif

La fonction objectif utilisée pour l’optimisation de la localisation des antennes est
la variance de la charge des antennes V. La couverture du réseau est quant à elle
intégrée dans les contraintes, et une distinction est donc faite entre le rôle des deux
objectifs de l’optimisation.

5.7.2 Contraintes
Les contraintes définies pour cette partie de l’optimisation sont au nombre de
trois, gérées avec les mécanismes de la barrière extrême ou progressive :
– la contrainte de non-superposition des antennes, gérée par la barrière extrême,
interdit à deux antennes de se trouver plus proches l’une de l’autre que la
discrétisation du territoire ;
– la contrainte d’appartenance au territoire dT,2 , gérée par la barrière progressive,
mesure la violation de la contrainte d’appartenance au territoire. Sa gestion par
la barrière progressive peut permettre à la recherche de faire sortir temporaire-
ment des antennes du terrain pour aller vers de meilleures régions de l’espace
de recherche ;
– la population non couverte Nnc , gérée par la barrière progressive. Grâce à l’utili-
sation de la barrière progressive avec cette contrainte, l’algorithme Mads essaye
de minimiser la population non couverte si elle est non nulle. Si toute la popu-
lation est desservie, l’objectif n’est plus violé et la recherche se concentre sur
 82

l’amélioration de la variance V. Il est intéressant de traiter Nnc comme une

contrainte dans la mesure où on cherche principalement à trouver des solutions
réalisant une couverture totale.

5.7.3 Paramètres algorithmiques

Recherche globale

L’algorithme Mads est utilisé ici sans stratégie de recherche globale, sauf la re-
cherche spéculative, activée par défaut, qui consiste à explorer plus loin dans la di-
rection d’un succès. Toutefois, les recherches tabou utilisées pour l’optimisation de
l’assignation de canaux constituent un mécanisme de diversification qui peut être vu
comme faisant office d’étape de recherche pour Mads.

Groupes de variables

Aucune stratégie de groupement de variables n’est mise en place dans cette re-
cherche. Il pourrait être intéressant d’essayer de former des groupes de variables,
d’autant plus que la structure du problème peut suggérer des stratégies intéressantes.
D’une part, la position de chaque antenne est représentée par deux variables de
position xi et yi , qui pourraient être groupées ensemble. D’autre part, les groupes
d’antennes appartenant à un même canal peuvent aussi constituer une stratégie de
groupement intéressante. Il faudrait en revanche bien gérer l’évolution des groupes
au cours de la recherche afin de conserver les propriétés de convergence de Mads,
comme expliqué dans [Garnier(2010)].

Taille de treillis

Comme indiqué au chapitre précédent, la taille minimale du treillis employé par

Mads peut être définie par l’utilisateur de l’algorithme. Ici, il est inutile que la re-
cherche se poursuive lorsque la taille du treillis devient inférieure à la taille de discré-
tisation du terrain. La taille minimale du treillis est donc réglée sur cette valeur.
 83

5.8 Optimisation du problème complet

Les deux recherches qui viennent d’être présentées se concentrent chacune sur l’un
des deux aspects du problème : l’assignation de canaux pour optimiser la couverture
ou l’équilibrage, et la localisation des antennes. Pour optimiser le problème complet,
qui consiste à optimiser ces trois sous-problèmes conjointement, il convient de coupler
les différentes recherches.

5.8.1 Couplage des recherches

La plus importante partie de l’optimisation débute dès que la phase de construc-
tion de la solution initiale est terminée. Durant cette phase, le contrôle alterne rapi-
dement entre les trois types de recherche. Cela permet d’évoluer rapidement vers une
bonne région de l’espace de recherche en ne négligeant pas un groupe de variables par
rapport à l’autre.
Cette phase d’alternance se termine lorsqu’aucune amélioration n’est obtenue pen-
dant plusieurs itérations lors de l’optimisation de l’assignation de canaux pour la cou-
verture de la population, qui ne peut alors plus être améliorée. La dernière phase, qui
est la phase de terminaison, se focalise uniquement sur la localisation des antennes.
Le couplage des recherches est illustré par l’algorithme 10.

5.8.2 Critères d’arrêt

Sous-étapes de recherche

Pendant la phase de recherche, l’optimisation alterne rapidement entre la localisa-

tion des antennes et l’assignation de canaux pour la couverture ou pour l’équilibrage.
Chacune de ces sous-étapes s’exécute pendant un temps court.
L’étape d’optimisation de l’assignation de canaux pour la couverture de population
est stoppée lorsque la recherche tabou effectue N1 = 15 itérations sans améliorer
la solution. Il en est de même pour l’optimisation de l’assignation de canaux pour
l’équilibrage de la charge des antennes. Elle se termine après N2 = 15 itérations
sans amélioration. Quant à l’étape d’optimisation de la localisation des antennes, elle
s’arrête après N3 = 30 itérations de l’algorithme Mads.
Ces valeurs ont été choisies après quelques essais, qui ont montré qu’elles per-
mettent une alternance assez rapide, et ont mené à des résultats satisfaisants sur les
 84

Algorithme 10: Plan de l’algorithme général.

Initialisation :
Construire la solution initiale
Fixer N1 , N2 et N3

Recherche :
Optimiser l’assignation pour la couverture pendant N1 itérations
si l’assignation de canaux n’apporte aucune amélioration pour la
deuxième fois consécutive alors
Aller à la phase de terminaison
sinon
Recommencer l’étape de recherche
fin
Optimiser l’assignation pour l’équilibrage pendant N2 itérations
Optimiser la localisation des antennes pendant N3 itérations
Terminaison :
Optimiser la localisation des antennes jusqu’à rencontrer le critère d’arrêt

instances de test. Ces critères d’arrêt pourraient sans doute être améliorés, notamment
grâce à l’utilisation de critères dynamiques plutôt que statiques.

Phase de recherche

Lorsqu’aucune amélioration n’est obtenue après deux exécutions successives de

l’optimisation de l’assignation de canaux pour la couverture, l’assignation de canaux
est de très bonne qualité considérant la localisation des antennes courante. Il est alors
difficile de continuer à l’améliorer, c’est pourquoi on peut arrêter la phase de recherche
et passer à la phase de terminaison.

Phase de terminaison

Cette dernière phase de l’optimisation s’occupe exclusivement de l’optimisation de

la localisation des antennes. Après la phase de recherche, les antennes sont générale-
ment assez proches de leur position finale, et cette dernière étape permet d’améliorer
leur localisation le plus possible.
Un critère d’arrêt possible pour cette optimisation est la taille de treillis de Mads.
Comme expliqué précédemment, il est possible d’indiquer à l’algorithme Mads de
s’arrêter lorsque la taille de son treillis atteint la taille de discrétisation du territoire.
 85

La solution alors obtenue est normalement un minimum local. Cependant, avec ce

critère, cette dernière phase de recherche peut être très longue, alors que les amélio-
rations obtenues en fin de recherche sont faibles.
Il peut être plus judicieux de choisir un critère d’arrêt qui permette à la recherche
de se terminer plus tôt. On obtient ainsi une solution de légèrement moins bonne
qualité, mais au bénéfice d’un temps d’exécution nettement plus court. Ce choix ne
doit être fait que si le temps d’exécution de l’optimisation est un critère important.
 86

Chapitre 6

Résultats

Le cadre d’optimisation d’un réseau de télécommunications mis en place dans les

chapitres précédents est composé d’une boîte noire permettant de faire des simula-
tions d’un réseau, présentée au chapitre 3, et d’un algorithme d’optimisation mêlant
recherche directe et métaheuristiques, développé au chapitre 5. La pertinence de cette
approche reste à être évaluée et c’est ce qui est fait dans le présent chapitre avec la
présentation des résultats numériques obtenus.

6.1 Présentation des instances

Plusieurs instances de test ont été utilisées pour réaliser des essais et obtenir les
résultats numériques. Les données d’entrée nécessaires pour réaliser l’optimisation
sont d’une part une carte de terrain représentant un terrain T ⊂ R2 , et d’autre part
une carte de densité donnant la densité de population D(x, y) ∈ R+ sur l’ensemble
du terrain. Pour chacun de ces deux types de cartes, différentes configurations ont été
utilisées, le but étant d’évaluer l’influence de différents paramètres sur les résultats.
Toutes les cartes utilisées ont une taille de discrétisation du terrain de 100 mètres.
Chaque pixel des images représentant les cartes, qui sont présentées ci-dessous, re-
présente donc un élément de terrain carré de 100 mètres de côté.

6.1.1 Cartes de terrain

Quatre types de terrains ont été testées :
– un terrain carré Square (figure 6.1a), terrain le plus simple possible, mais pré-
sentant des effets de bords à cause de la présence de coins ;
– un terrain circulaire Circle (figure 6.1b), permettant de tester l’influence de la
symétrie circulaire ;
– un terrain en forme de banane Banana (figure 6.1c), présentant une non-
convexité prononcée ;
 87

– l’île de Montréal M tl (figure 6.1d), possédant une forme assez régulière ainsi
que des non-convexités.
Sur les cartes, une valeur de pixel de 1 (pixels clairs) signifie qu’il fait partie du
terrain T , alors qu’une valeur de 0 (pixels noirs) signifie qu’il en est exclu.

(a) Terrain carré. (b) Terrain circulaire.

(c) Terrain en forme de banane. (d) Terrain de Montréal.

Figure 6.1 Les différentes cartes de terrain utilisées.

6.1.2 Cartes de densité

Le modèle de réseau et l’algorithme d’optimisation sont conçus dans le but de
pouvoir prendre en compte des densités de populations quelconques sur le terrain
considéré. Quatre types différents de cartes de densité ont été utilisés pour chacun
des terrains, carré, circulaire et en banane :
– une densité uniforme U ;
– une densité C avec une seule zone centrale de concentration de la population ;
 88

– une densité E avec une seule zone de concentration de la population, excentrée ;

– une densité B avec deux zones de concentration de la population.
Ces cartes de densité sont représentées pour les terrains carré, circulaire et en
banane par les figures 6.2, 6.3 et 6.4 respectivement. Pour ce qui est du terrain de l’île
de Montréal, la carte de densité utilisée est basée sur la densité de population réelle
de la ville, représentée figure 6.5.
Les valeurs des pixels sur ces cartes sont comprises entre 0 et 1, la valeur 1 indi-
quant une densité maximale alors que la valeur 0 indique une absence de population.
En réalité, aucun point du terrain ne possède une densité de 0, afin de forcer l’algo-
rithme d’optimisation à essayer de couvrir l’ensemble du territoire. Le seuil minimum
est fixé à une valeur de 0.05.
Pour désigner les différentes instances de terrains et densités, on les notera avec
le nom du terrain, suivi du type de carte de densité en exposant. Les notations des
instances sont indiquées en regard de chaque figure.
 89

(a) Square U : Densité uniforme. (b) Square C : Une zone de concentration centrale.

(c) Square E : Une zone de concentration excentrée. (d) Square B : Deux zones de concentration.

Figure 6.2 Cartes de densité pour terrain carré.

 90

(a) Circle U : Densité uniforme. (b) Circle C : Une zone de concentration centrale.

(c) Circle E : Une zone de concentration excentrée. (d) Circle B : Deux zones de concentration.

Figure 6.3 Cartes de densité pour terrain circulaire.

 91

(a) Banana U : Densité uniforme. (b) Banana C : Une zone de concentration centrale.

(c) Banana E : Une zone de concentration excentrée. (d) Banana B : Deux zones de concentration.

Figure 6.4 Cartes de densité pour terrain en forme de banane.

Figure 6.5 M tl : Carte de densité pour l’île de Montréal.

 92

6.2 Déroulement de l’optimisation

L’algorithme d’optimisation d’un réseau de télécommunications se compose de
plusieurs étapes, chacune ayant un rôle particulier. La génération des cartes des zones
de service des antennes permet de suivre visuellement l’évolution du réseau au cours
de l’optimisation et donne facilement une bonne indication de la qualité de la solution
courante. Les figures 6.6, 6.7, 6.8 et 6.9 sont une illustration, pour différentes instances
de terrain, de l’état du réseau au début des grandes étapes de l’optimisation, pour un
réseau composé de 20 antennes et 10 canaux.
Pour ce qui est de l’identification des instances, on les notera avec le nom du
terrain et le type de densité en exposant, comme précédemment, suivi du nombre de
canaux puis du nombre d’antennes en indice.
 93

(a) Solution initiale. (b) Après la recherche Voronoï initiale.

(c) Après la première recherche tabu. (d) Après la première recherche Mads.

(e) En cours de recherche. (f) Solution finale.

Figure 6.6 Cartes de service à différentes étapes de la recherche pour l’instance

U
Square10,20 .
 94

(a) Solution initiale. (b) Après la recherche Voronoï initiale.

(c) Après la première recherche tabu. (d) Après la première recherche Mads.

(e) En cours de recherche. (f) Solution finale.

Figure 6.7 Cartes de service à différentes étapes de la recherche pour l’instance

C
Circle10,20 .
 95

(a) Solution initiale. (b) Après la recherche Voronoï initiale.

(c) Après la première recherche tabu. (d) Après la première recherche Mads.

(e) En cours de recherche. (f) Solution finale.

Figure 6.8 Cartes de service à différentes étapes de la recherche pour l’instance

E
Banana10,20 .
 96

(a) Solution initiale. (b) Après la recherche Voronoï initiale.

(c) Après la première recherche tabu. (d) Après la première recherche Mads.

(e) En cours de recherche. (f) Solution finale.

Figure 6.9 Cartes de service à différentes étapes de la recherche pour l’instance

M tl10,20 .
 97

Ces cartes de service permettent d’avoir une vision intuitive du déroulement de

la recherche, et de se faire visuellement une idée sur le rôle de chacune des étapes
de l’algorithme. On voit en particulier que les localisations initiales des antennes,
obtenues par une heuristique, sont en général éloignées de celles de la solution finale.
Toutefois la recherche Voronoï initiale permet de rapprocher sensiblement les antennes
d’une bonne localisation. On voit bien par ailleurs l’influence très importante de la
première recherche tabou qui, sans déplacer les antennes, apporte rapidement une très
importante amélioration de la couverture du réseau. La première recherche Mads
pour l’optimisation de la localisation apporte elle aussi une forte amélioration du
réseau en peu d’itérations.
Finalement, pour les instances illustrées ici, le reste de l’optimisation permet d’ap-
procher petit à petit la solution finale à partir d’une configuration qui en est déjà assez
proche. Ce n’est pas forcément le cas pour les instances de grande taille qui, comme
on le verra, nécessitent plus d’itérations pour atteindre une configuration de bonne
qualité.

6.3 Profils d’évolution

Les cartes de service présentées ci-dessus permettent une vision intuitive du dérou-
lement de la recherche. Une vision plus quantitative peut être donnée par les profils
d’évolution des fonctions au cours de la recherche. Ces graphiques présentent l’évolu-
tion de la variance du nombre d’usagers V et du nombre d’usagers non servis Nnc en
fonction du nombre d’évaluations de boîte noire effectuées par l’optimisation.
Les profils d’évolution pour les mêmes instances que précédemment, comportant
20 antennes et 10 canaux, sont donnés par les figures 6.10, 6.11, 6.12 et 6.13. Sur
ces graphiques, la zone grisée correspond à la recherche Voronoï initiale, les rayures
obliques ascendantes à la recherche tabou pour l’optimisation de la couverture et
les rayures descendantes à la recherche tabou pour l’optimisation de la variance du
nombre d’usagers. Enfin, les zones sur fond blanc correspondent aux recherches avec
l’algorithme Mads.
 98

U
Figure 6.10 Profil d’évolution de l’instance Square10,20 .

C
Figure 6.11 Profil d’évolution de l’instance Circle10,20 .
 99

E
Figure 6.12 Profil d’évolution de l’instance Banana10,20 .

Figure 6.13 Profil d’évolution de l’instance M tl10,20 .

 100

6.3.1 Recherche Voronoï initiale

Les profils d’évolution permettent de voir le nombre d’évaluations consommées
par la phase de la recherche Voronoï initiale, ainsi que les valeurs initiale et finale des
fonctions considérées. Les figures ci-dessus présentent des phases de recherche Voronoï
plutôt longues et qui nécessitent un grand nombre d’évaluations de boîte noire. La
longueur de cette phase de recherche initiale peut être très variable d’une instance à
l’autre, quel que soit le terrain et la dimension du réseau. Ce fait est illustré par la
B B
figure 6.14 qui montre les profils d’évolution des instances Square10,50 et Banana10,20
ayant des phases de recherche Voronoï initiales de longueurs très différentes par rap-
port à la durée totale de la recherche.
Quoi qu’il en soit, cette recherche initiale consomme généralement un nombre
assez important d’évaluations. Cela est dû au fait que le critère d’arrêt choisi pour
l’algorithme Mads est l’obtention de la taille minimale du treillis de recherche, qui
est un critère exigeant. On n’a peut-être pas besoin d’atteindre une telle précision
pour une recherche initiale. Ce choix a été fait comme choix par défaut, et aucun
essai n’a été fait pour améliorer l’efficacité de la recherche Voronoï initiale. Il s’agirait
donc d’une piste d’amélioration de l’algorithme.
D’autre part, on peut constater sur certains profils que les valeurs des fonctions
à la suite de la recherche Voronoï sont plus élevées que celles de la solution initiale.
On pourrait donc se dire que cette recherche dégrade la solution. En réalité ce n’est
pas forcément le cas. La dégradation des valeurs des fonctions est due au fait que
la recherche Voronoï déplace les antennes vers de nouvelles positions alors que l’as-
signation de canaux est toujours l’assignation initiale, qui n’a pas été optimisée. La
situation est très vite rétablie par la première recherche tabou qui améliore de façon
drastique l’assignation de canaux.
Pour tenter d’évaluer la pertinence et l’efficacité de la recherche Voronoï initiale,
deux séries de tests ont été réalisées avec les instances Square U et M tl, où l’optimisa-
tion a été à nouveau réalisée, mais cette fois-ci sans effectuer la recherche Voronoï. Les
résultats sont présentés dans les tableaux 6.1 et 6.2 et sont à comparer aux résultats
de l’optimisation avec recherche Voronoï donnés dans les tableaux A.1 et A.13 situés
en annexe. Ces données semblent indiquer que la recherche complète avec Voronoï
permet d’obtenir de meilleures solutions finales, en particulier en ce qui concerne le
nombre d’usagers non couverts. La variance du nombre d’usagers par antenne s’en
trouve légèrement affectée, mais reste sensiblement identique. En revanche, le nombre
 101

Tableau 6.1 Résultats pour l’instance de terrain Square U,V .

Terrain p n V % × 102 %
Nnc Évaluations Temps (s)
8 64 0.45 4264 39
12 2.1 19 10188 110
4
16 0.25 33 15039 162
20 0.28 43 38064 483
14 0.0013 0 6180 239
21 2.2 1.7 22592 240
7
28 0.046 13 48667 388
35 0.091 19 138254 1332
20 0.0027 0 10237 425
Square U,V 30 0.031 0 44293 349
10
40 0.84 0.41 132378 1447
50 0.17 5.2 238936 2777
30 0.0018 0 23294 180
45 0.00072 0 52460 505
15
60 0.0011 0 70654 768
75 0.06 0.02 368696 5325
40 0.0015 0 26059 234
60 0.00054 0 86840 999
20
80 0.00054 0 154288 2098
100 0.0006 0 283748 4606

d’évaluations de boîte noire nécessaires à l’optimisation est beaucoup plus important

avec la recherche Voronoï activée et il est légitime de se demander si la légère améliora-
tion de la solution justifie une si grande augmentation du temps de calcul. Il faudrait
toutefois vérifier s’il n’est pas possible de remédier à cet inconvénient en instaurant
un meilleur critère d’arrêt.

6.3.2 Nombre d’antennes et nombre d’usagers non servis

Parmi toutes les instances utilisées, toutes ne permettent pas d’atteindre une
couverture totale du réseau. En fait, pour un nombre de canaux donné, il est de
plus en plus difficile d’obtenir une couverture complète lorsque le nombre d’antennes
augmente. Cette situation est illustrée par la figure 6.13, qui montre l’exemple de
 102

Tableau 6.2 Résultats pour l’instance de terrain M tl V .

Terrain p n V % × 102 %
Nnc Évaluations Temps (s)
8 24 0 4183 110
12 15 10 7927 123
4
16 15 14 25534 380
20 4.5 28 43453 697
14 0.49 0 7600 331
21 5.2 0.0057 31182 405
7
28 1.4 3.9 65750 480
35 0.35 13 105843 839
20 0.058 0 13774 598
M tl V 30 1.4 0.011 30319 232
10
40 1.1 0.17 106776 880
50 0.5 1.4 267865 3438
30 0.006 0 18390 187
45 0.0032 0 45309 581
15
60 0.042 0 225778 3556
75 0.28 0 510816 9269
40 0.0043 0 42395 487
60 0.0033 0 65511 954
20
80 0.054 0 299633 5633
100 0.17 0 1421581 30582

l’instance Circle C avec 10 canaux et 2, 3, 4 et 5 antennes par canal.

 103

C C
Les instances Circle10,20 et Circle10,30 , avec 2 et 3 antennes par canal, permettent
C C
d’atteindre une couverture totale, alors que les instances Circle10,40 et Circle10,50 , avec
4 et 5 antennes par canal, ne le permettent pas. Le fait qu’il soit plus difficile de couvrir
la totalité du territoire lorsque le nombre d’antennes augmente peut sembler contre-
intuitif. En réalité, lorsqu’on ajoute des antennes, les interférences entre antennes
d’un même canal augmentent rapidement, réduisant la zone de couverture de chaque
antenne. C’est ce phénomène d’augmentation des interférences qui est prépondérant
lors de l’ajout d’antennes.
Pour un nombre de canaux donné, il existe donc un nombre maximal d’antennes
par canal permettant d’obtenir une couverture complète. Ce comportement est bien
connu dans le domaine des télécommunications. Pour pouvoir augmenter le nombre
d’antennes du réseau, il faut alors également ajouter des canaux. Ce résultat est par
exemple décrit dans [Rappaport(2002a)].

En ce qui concerne l’évolution du nombre d’usagers non servis pendant l’opti-

misation, on peut voir qu’elle est constituée de deux phases. Ce nombre chute très
rapidement en début de recherche. On part en effet d’une assignation de canaux non
optimisée, obtenue de façon séquentielle, et qui peut donc être arbitrairement éloignée
d’une bonne assignation. Il est donc naturel que les premières étapes de la recherche
améliorent fortement la valeur de cette fonction. Les premières recherches tabou sont
particulièrement efficaces pour cette tâche, car elles permettent de se déplacer rapi-
dement vers une bonne assignation de canaux.
En revanche, pour les instances où l’on ne peut pas obtenir de couverture complète,
on observe un ralentissement de l’amélioration avec les recherches tabou. On parvient
même généralement à un stade où les recherches tabou n’apportent plus aucune mo-
dification. L’assignation de canaux est alors probablement optimale vis-à-vis de la
localisation des antennes, et on ne peut plus améliorer la couverture de cette façon.
Par contre, les recherches Mads pour l’optimisation de la localisation parviennent
toujours à améliorer la solution petit à petit jusqu’à l’arrêt de la recherche.

6.3.3 Analyse des tendances générales d’évolution

L’évolution de la variance du nombre d’usagers par antenne est fortement liée
à la possibilité ou non de couvrir l’ensemble des usagers. Premièrement, pour les
instances qui permettent une couverture complète comme celles de la figure 6.14,
 104

le nombre d’usagers non servis a peu d’influence. En effet, il chute très rapidement
dès le début de l’optimisation, atteignant une valeur nulle. La recherche se concentre
alors sur la seule optimisation de la variance, et on observe alors sa décroissance,
rapide dans la figure 6.14a, plus lente dans la figure 6.14b. Cette différence de vitesse
s’explique par la différence de difficulté à atteindre une couverture complète entre les
instances considérées.
Pour les instances comportant peu d’antennes par canal, lors de l’optimisation
de la localisation avec l’algorithme Mads, les antennes possèdent une grande liberté
de mouvement et peuvent être facilement déplacées sans pour autant dégrader la
couverture, ce qui permet aux recherches d’emprunter de meilleures directions. On
observe alors une décroissance très rapide de la variance, d’allure exponentielle, et
l’optimisation pourrait dans ce cas être arrêtée assez vite selon la qualité de la solution
recherchée.
Au contraire, pour les instances ayant un grand nombre d’antennes par canal, il est
plus difficile d’atteindre une couverture complète. Une fois qu’on l’a obtenue, de petits
changements de position des antennes peuvent la dégrader considérablement. Les
recherches subséquentes sont donc plus contraintes et progressent moins rapidement,
d’où l’observation d’une décroissance plus lente, d’allure plutôt linéaire, ne permettant
pas d’arrêter l’optimisation trop tôt.
 105

B
(a) Square10,50 .

B
(b) Banana10,20 .

Figure 6.14 Deux profils d’évolution avec des longueurs relatives de recherche Voronoï
initiale différentes.
 106

C
(a) Circle10,20 : deux antennes par canal.
 107

C
(b) Circle10,30 : trois antennes par canal.

C
(c) Circle10,40 : quatre antennes par canal.
 108

C
(d) Circle10,50 : cinq antennes par canal.

C
Figure 6.13 Effet de l’augmentation du nombre d’antennes sur l’instance Circle10 .
 109

U
(a) Circle15,30 .

U
(b) Circle15,60 .

Figure 6.14 Deux instances avec couverture totale.

 110

Deuxièmement, on trouve à l’opposé les instances ne permettant pas d’obtenir

une couverture complète, qui possèdent un grand nombre d’antennes par canal. La
figure 6.15 illustre de telles instances. On voit dans ce cas que les deux objectifs de
couverture complète et d’équilibrage des charges sont antagonistes. Ainsi, le nombre
d’usagers non couverts diminue peu à peu durant l’optimisation, alors que la variance
du nombre d’utilisateurs ne fait qu’augmenter. Ce comportement est dû au fait qu’il
a été fait le choix d’optimiser en priorité le nombre d’usagers non servis pour obtenir
une couverture complète, ce qui se fait au détriment de la variance.
 111

(a) M tl7,35 .

E
(b) Banana7,35 .

Figure 6.15 Deux instances ne permettant pas d’obtenir une couverture totale.
 112

Finalement, entre ces deux cas se trouvent un grand nombre d’instances pour
lesquelles une couverture totale est obtenue, mais seulement après un certain nombre
d’itérations. Un exemple d’une telle instance est donné par la figure 6.16. Deux phases
apparaissent dans l’optimisation. Dans un premier temps, la couverture du réseau est
optimisée, et la variance se dégrade rapidement, jusqu’à ce que la recherche atteigne
une couverture complète. Dans un second temps, l’optimisation peut se concentrer
sur l’optimisation de la variance du nombre d’usagers, qui est alors progressivement
améliorée.

C
Figure 6.16 Exemple de l’instance Banana15,60 , pour laquelle la couverture complète
n’est obtenue qu’après un temps long.

6.3.4 Comportement individuel des recherches

L’analyse qui vient d’être faite ne décrit que l’évolution générale des fonctions au
cours de la recherche, sans s’attarder sur le comportement particulier des différentes
recherches. Elles ont en effet chacune un impact différent, qui dépend ici aussi de
l’état dans lequel se trouve l’optimisation vis-à-vis de la couverture du réseau.
 113

La recherche tabou pour la minimisation du nombre d’usagers non servis est in-
diquée sur les profils d’évolution par les rayures obliques montantes. Son rôle n’est
intéressant que lorsqu’une solution réalisant une couverture complète n’a pas encore
été trouvée, car dans le cas contraire on ne peut pas améliorer la fonction objectif et
la recherche n’est tout simplement pas exécutée. On peut s’appuyer sur la figure 6.15
pour faire des observations. On voit que dans les premiers temps de l’optimisation,
les recherches tabou pour l’amélioration de la couverture font chuter très rapidement
le nombre d’usagers non servis, tout en dégradant la variance du nombre d’usagers
par antenne. C’est bien le comportement attendu, puisque l’assignation de canaux
initiale n’est pas du tout optimisée. Mais plus on avance dans l’optimisation, et plus
les recherches tabou suivantes ont un effet faible, voire nul. On pouvait également
s’y attendre, car il arrive un point de l’optimisation où l’assignation de fréquences
est presque optimale par rapport à la localisation des antennes. Il est donc difficile
d’améliorer la couverture de cette façon, et c’est pourquoi les dernières recherches ta-
bou sont courtes, car elles apportent une petite amélioration puis s’arrêtent au bout
de 15 itérations sans succès.
Il semble donc que beaucoup de temps soit perdu dans les dernières étapes de
l’optimisation pour certaines instances comme celles de la figure 6.15, en raison d’une
trop rapide alternance entre les recherches tabou et Mads. Il pourrait donc être
intéressant d’essayer de détecter que l’on se trouve dans cette phase et d’allonger la
durée des recherches Mads pour l’optimisation de la localisation entre deux étapes
de recherche tabou.
Ensuite, la recherche tabou pour l’optimisation de l’équilibrage du nombre d’usa-
gers par antenne, qui est indiquée par les rayures obliques descendantes, a un compor-
tement très différent de la précédente. Comme on peut le voir sur la figure 6.16, elle
s’attache surtout à améliorer la variance du nombre d’usagers par antenne, sans trop
dégrader la couverture. Cela correspond tout à fait à la fonction objectif utilisée par
cette recherche, qui valorise l’amélioration de l’équilibrage et pénalise fortement la
dégradation de la couverture. Cela permet de compenser en partie la dégradation de
la variance induite par le premier type de recherche tabou lors de la recherche d’une
couverture complète, mais aussi d’essayer d’améliorer la variance si la couverture est
déjà complète. Comme précédemment, on constate que cette recherche peut avoir un
effet très bénéfique en début d’optimisation, mais qu’elle peine à améliorer la solu-
tion dans les étapes plus avancées. La voie d’amélioration à privilégier est la même :
 114

il faudrait gérer dynamiquement la durée des recherches Mads entre les recherches
tabou.
Enfin, les recherches Mads pour l’optimisation de la localisation des antennes
permettent d’améliorer la solution tout au long de l’optimisation. Comme pour les
recherches tabou, les recherches Mads entraînent une très rapide amélioration de la
solution en début de recherche, puis la vitesse d’amélioration se réduit peu à peu.
On constate également que lorsque la couverture n’est pas complète, la recherche
optimise en priorité la couverture au détriment de la variance. Cela est dû au fait que
la couverture est gérée au sein de l’algorithme comme une contrainte avec barrière
progressive, ce qui revient à résoudre un problème non contraint où la couverture
compterait comme une pénalité dont la valeur est le carré du nombre d’utilisateurs
non servis. Le poids de cette pénalité est alors plus important que celui de la variance.

6.3.5 Phase de terminaison

La phase de terminaison consiste en une dernière recherche Mads pour l’amélio-
ration de l’équilibrage du nombre d’usagers. Dans les essais effectués, le critère d’arrêt
utilisé pour cette recherche est l’obtention de la teille de treillis minimale. L’existence
de cette phase de terminaison peut bien être visualisée sur la figure 6.14, où elle se
traduit par une large zone finale sur fond blanc. Sur d’autres instances, comme celles
de la figure 6.15, cette zone n’apparaît pas. Cela est dû au fait que les profils d’évo-
lution ont ici été tracés jusqu’au dernier point représentant une amélioration de la
solution. Il se peut qu’en réalité l’optimisation se soit poursuivie plus longtemps, mais
tous les points situés à droite du dernier point représenté ne réalisent pas d’améliora-
tion de la solution. Il serait aisé de définir un critère d’arrêt permettant d’arrêter la
recherche plus rapidement lors de la phase de terminaison. En effet, il est possible de
s’apercevoir assez rapidement si la recherche stagne, auquel cas il suffit de l’arrêter
au bout d’un certain nombre d’itérations sans amélioration.

6.4 Résultats finaux

Les profils d’évolution présentés dans la section précédente permettent d’observer
la progression de l’algorithme d’optimisation et d’analyser son comportement au cours
de la recherche. Il est essentiel d’analyser également les résultats finaux obtenus à la
 115

suite des optimisations effectuées avec les différentes instances.

Comme on l’a vu, chaque instance peut être identifiée par le type de terrain
(Square, Circle, Banana ou M tl), le type de densité (U , C, E ou B), le nombre
de canaux p et le nombre d’antennes n. Les chiffres intéressants que l’on peut ob-
server sont la variance du nombre d’usagers par antenne V, le nombre d’usagers non
servis Nnc , le nombre d’évaluations de boîte noire effectuées, ainsi que, à titre indica-
tif, la durée de l’optimisation. En réalité, il est surtout intéressant de considérer les
grandeurs V % et Nnc% , exprimées en pourcentage de la population totale de chaque
territoire, ce qui permet de comparer les résultats pour toutes les instances. L’en-
semble des résultats pour toutes les instances testées sont présentées à l’annexe A,
avec des précisions sur les machines utilisées pour aider à comprendre les temps de
calcul réels observés.

6.4.1 Influence des nombre de canaux et d’antennes

Les résultats finaux sont présentés dans le tableau 6.3 sous forme agrégée. Il in-
dique les moyennes des résultats finaux pour chaque nombre de canaux et d’antennes,
en agrégeant les données des différents terrains. On peut ainsi facilement observer
l’influence des nombre de canaux et d’antennes sur chacun des aspects des solutions
finales.
Tout d’abord, on remarque immédiatement que, comme prévu, le nombre d’usa-
gers non servis Nnc% est le plus faible lorsque le nombre d’antennes par canal est faible.
Pour les instances ne comportant que 4 canaux, on ne parvient pratiquement jamais
à obtenir une couverture complète et ce nombre de canaux est donc insuffisant. En
revanche pour les nombres de canaux plus élevés, il est possible d’ajouter un plus
grand nombre d’antennes tout en gardant une couverture complète.
Une deuxième observation immédiate qui peut être réalisée est que le nombre
d’évaluations de boîte noire requises, et donc le temps de calcul, sont croissants avec
le nombre d’antennes pour un nombre de canaux donné, ce qui est naturel puisque cela
entraîne une augmentation du nombre de variables. En revanche, on peut également
constater que pour un nombre d’antennes donné, le nombre d’évaluations nécessaires
diminue avec l’augmentation du nombre de canaux. Cela peut être expliqué par le fait
que cette augmentation du nombre de canaux augmente la robustesse des solutions
courantes au cours de la recherche, qui peuvent alors être davantage perturbées ce
 116

Tableau 6.3 Résultats finaux agrégés par nombre de canaux et d’antennes.

p n V % × 102 Nnc% Évaluations Temps (s)

8 628.14 0.30 5605.25 97.31
12 468.28 11.56 11636.94 232.50
4
16 148.97 25.44 25603.81 473.31
20 31.70 39.50 56496.63 975.69
14 42.10 0 11518.44 537.56
21 99.63 0.51 36930.00 920.06
7
28 66.65 6.02 85451.81 727.38
35 26.00 14.14 149120.94 1431.75
20 3.50 0 21026.06 852.38
30 23.49 0 59013.13 475.75
10
40 22.19 0.48 153124.88 1492.31
50 28.11 3.28 314344.56 3659.75
30 0.49 0 36383.13 291.13
45 2.04 0 112710.88 1189.13
15
60 3.95 0 260898.31 3312.56
75 3.65 0.07 608441.94 9089.63
40 0.05 0 57483.50 556.88
60 0.29 0 179039.81 2223.56
20
80 0.59 0 455167.69 6733.56
100 0.70 0 919709.75 14354.63

qui permet à l’optimisation d’avoir accès à de meilleures directions de recherche.

Enfin, pour ce qui est de la variance du nombre d’usagers par antenne, il n’est
pas nécessairement évident de déceler une tendance dans son évolution lorsque le
nombre d’antennes augmente pour un nombre de canaux fixé. En revanche, on voit
nettement que l’augmentation du nombre de canaux permet une grande amélioration
de l’équilibrage du nombre d’usagers par antenne. Un plus grand nombre de canaux
permet en effet une plus grande liberté dans le choix de la localisation des antennes,
puisqu’elles interfèrent moins entre elles, ce qui entraîne un meilleur équilibrage.

6.4.2 Influence du terrain et de la densité

Le tableau 6.4 présente les résultats agrégés par type de carte de terrain. Les
données présentées sont donc la moyenne, pour chaque terrain, de toutes les instances
 117

utilisant cette carte de terrain. On remarque que les cartes de terrain a priori les plus
régulières donnent en fait les moins bons résultats, alors que les meilleurs chiffres
sont obtenus pour les instances les plus irrégulières, aussi bien en termes de qualité
de la solution qu’en termes de temps d’exécution. Ce résultat peut sembler étonnant
à première vue, mais peut s’expliquer par le fait que les instances les plus régulières
présentent en réalité des effets de conditions aux limites importants. Par exemple, le
terrain Square, de forme carrée, possède quatre coins qui sont difficiles à couvrir, car
il faut placer des antennes assez près des limites du terrain tout en veillant à ne pas
perdre toute leur zone de couverture en dehors du terrain.

Tableau 6.4 Résultats finaux agrégés par type de terrain.

Terrain V % × 102 Nnc% Évaluations Temps (s)

Square 9.24 6.76 207626.88 3011.95
Circle 8.38 7.06 214231.98 3157.48
Banana 6.63 3.26 149318.44 2050.79
M tl 7.76 3.18 140764.20 1705.15

Pour ce qui est du type de carte de densité, les résultats agrégés sont présentés
dans le tableau 6.5. On constate cette fois-ci que les instance les plus faciles à traiter en
termes de temps de calcul sont celles présentant une densité de population uniforme,
ou en tous cas assez bien répartie, comme c’est le cas pour les densités U , B et
celle du terrain de Montréal. Au contraire, plus la répartition de la population est
déséquilibrée et dissymétrique et plus le temps de calcul augmente. Les valeurs des
fonctions objectif suivent également cette tendance, les moins bon scores étant réalisés
avec les densités C et E, qui sont les plus déséquilibrées.

Tableau 6.5 Résultats finaux agrégés par type de densité.

Densité V % × 102 Nnc% Évaluations Temps (s)

U 1.98 5.44 114844.32 1662.37
C 10.88 7.24 197340.57 2702.08
E 14.58 5.29 257378.40 3685.33
B 4.89 4.81 192006.43 2910.50
M tl 7.76 3.18 140764.20 1705.15
 118

6.4.3 Comportement avec les instances réelles

L’analyse des résultats finaux présentés ci-dessus permet de voir que l’optimisation
avec une instance réelle, ici l’île de Montréal, possède un très bon comportement. Il
s’agit en effet du type de terrain sur lequel l’optimisation est la plus rapide. De même
en comparaison avec les différents types de densités, l’optimisation avec la carte de
densité réelle de Montréal est à peine moins rapide à réaliser qu’avec une densité
uniforme. De plus, pour ce qui est des fonctions objectifs, c’est cette instance qui
parvient à obtenir les meilleurs taux de couverture, et elle est également parmi les
meilleures en ce qui concerne la variance du nombre d’usagers.
On voit donc que l’optimisation d’une instance réelle permet ici d’obtenir de
meilleurs résultats qu’avec des instances de test théoriques, qui sembleraient pour-
tant plus faciles à traiter à première vue. Ce constat est très intéressant, puisqu’en
pratique on s’intéressera surtout à optimiser des réseaux sur des territoires réels et
l’algorithme développé dans ce travail semble bien adapté à ce type de problème.
 119

Chapitre 7

Conclusion

La téléphonie mobile et les réseaux sans fil représentent aujourd’hui un enjeu éco-
nomique considérable. Ils constituent également un défi technique important, tant la
croissance de la demande est forte et les solutions technologiques développées sont
complexes. Le travail réalisé ici avait pour objectif initial d’évaluer la possibilité d’uti-
liser de nouvelles techniques d’optimisation pour l’amélioration de réseaux mobiles.
C’est ce qui a été réalisé tout au long de ce travail de maîtrise, qui se veut donc une ou-
verture vers le développement de nouvelles méthodes de conception et d’optimisation
de réseaux de téléphonie mobile.

7.1 Synthèse des travaux

L’objectif premier de ce travail de recherche était de déterminer s’il était possible
d’utiliser une méthode de recherche directe pour l’optimisation de la localisation des
antennes au sein d’un réseau de téléphonie mobile. Pour cela il a fallu développer un
modèle de réseau qui soit adapté à l’optimisation qui en serait faite. Initialement, nos
connaissances en ce qui a trait aux réseaux de communications sans fil étaient très
limitées. La première étape du travail a donc consisté à se documenter abondamment
sur le sujet, afin d’acquérir une bonne compréhension des phénomènes physiques
mis en jeu et des solutions techniques utilisées dans l’industrie. Un modèle simple
de réseau a ensuite été développé, sur la base du modèle de propagation des ondes
électromagnétiques dans le vide.
Le modèle ainsi réalisé a ensuite été implémenté sous forme de programme infor-
matique en C++ afin de pouvoir réaliser des simulations et, à l’aide de nombreux
tests, d’essayer d’acquérir une compréhension profonde du comportement du modèle
face à la modification des différents paramètres du réseau. Cette étape a été cruciale
dans le déroulement du projet, puisque c’est grâce à ces essais et tâtonnements que
l’étendue de l’optimisation a été fixée. En particulier, il a alors été fait le choix de s’in-
 120

téresser à l’optimisation simultanée de la localisation des antennes et de l’assignation

de fréquences, ces deux aspects étant très liés et difficilement dissociables.
Une fois obtenu ce premier élément essentiel du projet et la possibilité de réali-
ser des simulations, il a été possible de s’attacher au développement d’une méthode
d’optimisation pour ce problème. L’objectif initial étant d’utiliser l’algorithme Mads
pour l’optimisation de la localisation des antennes, il a été décidé de conserver ce
choix qui semblait parfaitement convenir à ce rôle. Pour ce qui est de l’assignation
de fréquences, qui est un problème combinatoire, il a été rapidement décidé d’utiliser
une métaheuristique, et la recherche tabou s’est naturellement présentée comme un
très bon choix d’algorithme. Ces décisions préliminaires réalisées, il a ensuite fallu
effectuer l’implémentation de ces algorithmes. Il a ensuite été possible d’ajuster les
paramètres de chacune des étapes du processus et d’améliorer leurs interactions. Il
n’a bien sûr pas été possible de tester en détail l’influence de tous les paramètres en
raison de leur grand nombre et de la durée limitée du projet, et leurs valeurs ont
généralement été fixées de façon empirique à la suite de plusieurs essais.
Finalement, l’ensemble du système développé jusqu’ici a été utilisé pour réaliser
de nombreuses batteries de tests sur des instances de problèmes variées. Les don-
nées obtenues à la suite de ces tests ont fait l’objet d’une analyse poussée, qui a
permis de conclure que la méthode développée permet d’obtenir des résultats satis-
faisants, en particulier lorsqu’utilisée avec des instances réelles, et qu’elle constitue
par conséquent une piste sérieuse pour le développement de techniques de conception
et d’optimisation de réseaux de télécommunications.

7.2 Limitations de la solution proposée

La solution proposée ici pour l’optimisation d’un réseau de télécommunications
est le fruit d’un travail exploratoire visant l’évaluation de la pertinence de l’approche
utilisée. Son champ d’application se limite donc pour l’instant à des problèmes expéri-
mentaux, et elle ne peut pas être utilisée en l’état pour la conception de réseaux réels
à l’échelle industrielle. Leur optimisation nécessiterait en effet un modèle de réseau
bien plus élaboré et complexe que le modèle élémentaire utilisé ici.
D’autre part, l’algorithme d’optimisation ne présente pas du tout des performances
optimales. De très nombreux paramètres différents définissent son comportement, et
ceux-ci ont été fixés de façon empirique à des valeurs qui semblaient convenables. Il est
 121

clair que de gros progrès pourraient être apportés par l’optimisation des paramètres
algorithmiques, aussi bien en termes de qualité des résultats que de performances et
temps de résolution.

7.3 Améliorations futures

Il existe de très nombreuses voies d’amélioration possibles pour la solution réa-
lisée au cours de ce projet de maîtrise. Celles-ci rejoignent les limitations identifiées
ci-dessus, et suivent donc deux axes principaux : l’élaboration d’un modèle et d’une
simulation plus réaliste, et l’amélioration de l’algorithme d’optimisation. Il est aussi
nécessaire de réaliser une comparaison avec d’autres méthodes afin de justifier l’ap-
proche proposée.
Le modèle de réseau conçu dans ce travail est un modèle très simple ne pouvant
pas être appliqué au traitement de cas réels. De nombreux ajouts peuvent être faits
au modèle qui permettraient d’affiner la simulation, selon les objectifs que l’on veut se
donner. Une des améliorations les plus simples à réaliser serait l’ajout du traitement de
terrains en relief, qui permettrait ainsi de tenir compte de l’altitude. Pour ce qui est du
modèle de propagation des ondes, il serait possible d’utiliser un modèle plus élaboré,
comme ceux présentés dans le chapitre 3, ce qui serait sans doute l’amélioration
ayant le plus gros impact sur la qualité de la modélisation. Enfin, un élément ayant
également une grande influence sur la finesse de la simulation serait la prise en compte
de types d’interférences supplémentaires, comme les interférences inter-canaux. Les
possibilités de développement du modèle sont innombrables, et on peut donc affiner le
modèle jusqu’au niveau souhaité. Cependant, sa complexification entraîne aussi une
rapide augmentation du temps de la simulation.
Le deuxième axe d’amélioration de la solution se situe du côté de l’algorithme d’op-
timisation. Comme indiqué précédemment, il est lui-même constitué d’algorithmes
évolués possédant chacun de nombreux paramètres, et interagissant entre eux à plu-
sieurs niveaux. Pour obtenir des valeurs optimales de tous les paramètres, il faudrait
faire de nombreux tests et déterminer la meilleure stratégie à utiliser pour chacun
d’eux, ce qui serait très laborieux. Toutefois, il est possible d’identifier certains para-
mètres principaux dont l’influence semble prépondérante. Le changement qui appor-
terait sans doute la meilleure amélioration est le choix de meilleurs critères d’arrêt
pour les différentes recherches qui composent l’algorithme. L’utilisation de critères
 122

d’arrêt dynamiques plutôt que statiques, bien calibrés, permettrait à la recherche

d’évoluer plus rapidement vers l’optimum et de perdre moins de temps à réaliser des
itérations inutiles. D’autres paramètres algorithmiques comme l’utilisation de groupes
de variables et l’ajout d’une étape de recherche globale avec l’algorithme Mads pour-
raient également améliorer les performances de l’algorithme et la qualité des solutions
produites.
La solution proposée est encore loin d’être adaptée à la résolution de problèmes
réels, mais les pistes d’amélioration sont très nombreuses et ouvrent un vaste ho-
rizon de possibilités qui permettront peut-être à terme de parvenir à une méthode
d’optimisation utilisable en pratique dans l’industrie.
 123

Références

[Abdel Khalek et al.(2011)] ABDEL KHALEK, A., AL-KANJ, L., DAWY, Z. et

TURKIYYAH, G. (2011). Optimization Models and Algorithms for Joint
Uplink/Downlink UMTS Radio Network Planning With SIR-Based Power
Control. Vehicular Technology, IEEE Transactions on, 60, 1612–1625.
[Abramson et al.(2009a)] ABRAMSON, M. A., AUDET, C., CHRISSIS, J. W. et
WALSTON, J. G. (2009a). Mesh Adaptive Direct Search Algorithms for Mixed
Variable Optimization. Optimization Letters, 3, 35–47.
[Abramson et al.(2003)] ABRAMSON, M. A., AUDET, C., COUTURE, G., DEN-
NIS, JR., J. E. et LE DIGABEL, S. (2003). The NOMAD project. Software
available at http ://[Link]/nomad.
[Abramson et al.(2009b)] ABRAMSON, M. A., AUDET, C., DENNIS, JR., J. E. et
LE DIGABEL, S. (2009b). OrthoMADS : A Deterministic MADS Instance with
Orthogonal Directions. SIAM Journal on Optimization, 20, 948–966.
[Amaldi et al.(2003)] AMALDI, E., CAPONE, A. et MALUCELLI, F. (2003). Plan-
ning UMTS base station location : optimization models with power control and
algorithms. Wireless Communications, IEEE Transactions on, 2, 939–952.
[Audet(2011)] AUDET, C. (2011). A short proof on the cardinality of maximal po-
sitive bases. Optimization Letters, 5, 191–194.
[Audet et al.(2008a)] AUDET, C., BÉCHARD, V. et CHAOUKI, J. (2008a). Spent
potliner treatment process optimization using a MADS algorithm. Optimization
and Engineering, 9, 143–160.
[Audet et al.(2008b)] AUDET, C., BÉCHARD, V. et LE DIGABEL, S. (2008b).
Nonsmooth optimization through Mesh Adaptive Direct Search and Variable
Neighborhood Search. Journal of Global Optimization, 41, 299–318.
[Audet et Dennis, Jr.(2001)] AUDET, C. et DENNIS, JR., J. E. (2001). Pattern
Search Algorithms for Mixed Variable Programming. SIAM Journal on Optimi-
zation, 11, 573–594.
[Audet et Dennis, Jr.(2003)] AUDET, C. et DENNIS, JR., J. E. (2003). Analysis of
Generalized Pattern Searches. SIAM Journal on Optimization, 13, 889–903.
 124

[Audet et Dennis, Jr.(2006)] AUDET, C. et DENNIS, JR., J. E. (2006). Mesh Adap-

tive Direct Search Algorithms for Constrained Optimization. SIAM Journal on
Optimization, 17, 188–217.
[Audet et Dennis, Jr.(2009)] AUDET, C. et DENNIS, JR., J. E. (2009). A Progres-
sive Barrier for Derivative-Free Nonlinear Programming. SIAM Journal on Op-
timization, 20, 445–472.
[Audet et al.(2008c)] AUDET, C., DENNIS, JR., J. E. et LE DIGABEL, S. (2008c).
Parallel Space Decomposition of the Mesh Adaptive Direct Search Algorithm.
SIAM Journal on Optimization, 19, 1150–1170.
[Audet et al.(2010)] AUDET, C., DENNIS, JR., J. E. et LE DIGABEL, S. (2010).
Globalization strategies for Mesh Adaptive Direct Search. Computational Opti-
mization and Applications, 46, 193–215.
[Audet et Le Digabel(2011)] AUDET, C. et LE DIGABEL, S. (2011). The mesh
adaptive direct search algorithm for periodic variables. Rapport technique G-
2009-23, Les Cahiers du GERAD. À paraître dans Pacific Journal of Optimiza-
tion.
[Audet et al.(2008d)] AUDET, C., SAVARD, G. et ZGHAL, W. (2008d). Multiob-
jective Optimization Through a Series of Single-Objective Formulations. SIAM
Journal on Optimization, 19, 188–210.
[BBC(2010)] BBC (2010). Over 5 billion mobile phone connections worldwide, BBC,
http ://[Link]/news/10569081.
[Bellanger(2006)] BELLANGER, M. (2006). Traitement numérique du signal - Théo-
rie et pratique (8e édition). Dunod.
[Boost(2011)] BOOST (2011). Boost C++ Librairies, http ://[Link].
[Box(1957)] BOX, G. E. P. (1957). Evolutionary Operation : A Method for Increasing
Industrial Productivity. Applied Statistics, 6, 81–101.
[Cerri et al.(2002)] CERRI, G., DE LEO, R., RUSSO, P. et MICHELI, D. (2002).
Optimized Planning for Base Station Location. EMC Europe 2002. International
Symposium on Electromagnetic Compatibility. Milan, Italy, vol. vol.1, 463 – 6.
[Clarke(1983)] CLARKE, F. H. (1983). Optimization and Nonsmooth Analysis. Wi-
ley, New York.
 125

[Conn et Le Digabel(2011)] CONN, A. R. et LE DIGABEL, S. (2011). Use of Qua-

dratic Models with Mesh Adaptive Direct Search for Constrained Black Box Op-
timization. Rapport technique G-2011-11, Les cahiers du GERAD. À paraître
dans Optimization Methods and Software.
[Conn et al.(1997)] CONN, A. R., SCHEINBERG, K. et TOINT, P. (1997). On the
Convergence of Derivative-Free Methods for Unconstrained Optimization. M. D.
Buhmann et A. Iserles, éditeurs, Approximation Theory and Optimization : Tri-
butes to M.J.D. Powell, Cambridge University Press, Cambridge, United King-
dom. 83–108.
[Conn et al.(1998)] CONN, A. R., SCHEINBERG, K. et TOINT, P. (1998). A
Derivative Free Optimization Algorithm in Practice. Proceedings the of 7th
AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Op-
timization. St. Louis, Missouri.
[Conn et al.(2009)] CONN, A. R., SCHEINBERG, K. et VICENTE, L. N. (2009).
Introduction to Derivative-Free Optimization. MPS/SIAM Book Series on Opti-
mization. SIAM, Philadelphia.
[Davis(1954)] DAVIS, C. (1954). Theory of Positive Linear Dependence. American
Journal of Mathematics, 76, 733–746.
[Finkel et Kelley(2004a)] FINKEL, D. E. et KELLEY, C. T. (2004a). An Adaptive
Restart Implementation of DIRECT.
[Finkel et Kelley(2004b)] FINKEL, D. E. et KELLEY, C. T. (2004b). Convergence
Analysis of the DIRECT Algorithm. Rapport technique CRSC-TR04-28, Center
for Research in Scientific Computation.
[Fortune(1987)] FORTUNE, S. (1987). A Sweepline Algorithm for Voronoi Diagrams.
Algorithmica, 2, 153–174.
[Fortune et al.(1995)] FORTUNE, S. J., GAY, D. M., KERNIGHAN, B. W., LAN-
DRON, O., VALENZUELA, R. A. et WRIGHT, M. H. (1995). WISE design of
indoor wireless systems : practical computation and optimization. Computatio-
nal, 2, 58–68.
[Friis(1946)] FRIIS, H. T. (1946). A note on a simple transmission formula. Proc
IRE, 34, 254–256.
 126

[Frühwirth et Brisset(1998)] FRÜHWIRTH, T. et BRISSET, P. (1998). Optimal Pla-

cement of Base Stations in Wireless Indoor Telecommunication. Principles and
Practice of Constraint Programming—CP98, Springer. 476–480.
[Gaillard et Lengellé(2006)] GAILLARD, P. et LENGELLÉ, R. (2006). Analyse et
traitement du signal. Ellipses.
[Galinier et al.(2011)] GALINIER, P., HERTZ, A., PAROZ, S. et PESANT, G.
(2011). Using local search to speed up filtering algorithms for some NP-hard
constraints. Annals of Operations Research, 184, 121–135.
[Garnier(2010)] GARNIER, V. (2010). La gestion des groupes de variables en re-
cherche directe. Mémoire de maîtrise, École Polytechnique de Montréal.
[Glover(1989)] GLOVER, F. (1989). Tabu Search - Part I. INFORMS Journal on
Computing, 1, 190–206.
[Granatstein(2008)] GRANATSTEIN, V. L. (2008). Physical principles of wireless
communications. Auerbach Publications.
[Hooke et Jeeves(1961)] HOOKE, R. et JEEVES, T. A. (1961). Direct Search So-
lution of Numerical and Statistical Problems. Journal of the Association for
Computing Machinery, 8, 212–229.
[Jones et al.(1993)] JONES, D. R., PERTTUNEN, C. D. et STUCKMAN, B. E.
(1993). Lipschitzian optimization without the Lipschitz constant. Journal of
Optimization Theory and Application, 79, 157–181.
[Lagarias et al.(1998)] LAGARIAS, J. C., REEDS, J. A., WRIGHT, M. H. et
WRIGHT, P. E. (1998). Convergence Properties of the Nelder-Mead Simplex
Method in Low Dimensions. SIAM Journal on Optimization, 9, 112–147.
[Le Digabel(2011)] LE DIGABEL, S. (2011). Algorithm 909 : NOMAD : Nonlinear
Optimization with the MADS Algorithm. ACM Transactions on Mathematical
Software, 37, 44 :1—-44 :15.
[Le Digabel et al.(2010)] LE DIGABEL, S., ABRAMSON, M. A., AUDET, C. et
DENNIS, JR., J. E. (2010). Parallel Versions of the MADS Algorithm for Black-
Box Optimization. Optimization days. GERAD, Montreal.
[Lee(2006)] LEE, W. C. Y. (2006). Wireless and cellular telecommunications.
McGraw-Hill, troisième édition.
 127

[Lewis et Torczon(1999)] LEWIS, R. M. et TORCZON, V. (1999). Pattern Search

Algorithms for Bound Constrained Minimization. SIAM Journal on Optimiza-
tion, 9, 1082–1099.
[Lewis et al.(2000)] LEWIS, R. M., TORCZON, V. et TROSSET, M. W. (2000).
Direct Search Methods : Then and Now. Journal of Computational and Applied
Mathematics, 124, 191–207.
[Lopez-Perez et al.(2008)] LOPEZ-PEREZ, D., JUTTNER, A. et ZHANG, J. (2008).
Optimisation Methods for Dynamic Frequency Planning in OFDMA Networks.
Telecommunications Network Strategy and Planning Symposium, 2008. Networks
2008. The 13th International. 1–28.
[Lopez-Perez et al.(2009)] LOPEZ-PEREZ, D., JUTTNER, A. et ZHANG, J. (2009).
Dynamic Frequency Planning Versus Frequency Reuse Schemes in OFDMA Net-
works. VTC Spring 2009 IEEE 69th Vehicular Technology Conference, 1–5.
[Luna et al.(2007)] LUNA, F., BLUM, C., ALBA, E. et NEBRO, A. J. (2007). ACO
vs EAs for solving a real-world frequency assignment problem in GSM networks.
Proceedings of the 9th annual conference on Genetic and evolutionary computa-
tion. ACM, New York, NY, USA, GECCO ’07, 94–101.
[Luna et al.(2008)] LUNA, F., ESTÉBANEZ, C., LEÓN, C., CHAVES-GONZÁLEZ,
J. M., ALBA, E., ALER, R., SEGURA, C., VEGA-RODRíGUEZ, M. A., NE-
BRO, A. J., VALLS, J. M., MIRANDA, G. et GÓMEZ-PULIDO, J. A. (2008).
Metaheuristics for solving a real-world frequency assignment problem in GSM
networks. Proceedings of the 10th annual conference on Genetic and evolutionary
computation. ACM, New York, NY, USA, GECCO ’08, 1579–1586.
[Majdandzic et al.(2008)] MAJDANDZIC, I., TREFFTZ, C. et WOLFFE, G. (2008).
Computation of Voronoi diagrams using a graphics processing unit. 2008 IEEE
International Conference on ElectroInformation Technology, 437–441.
[Marsden et al.(2007)] MARSDEN, A. L., WANG, M., DENNIS, JR., J. E. et MOIN,
P. (2007). Trailing-edge noise reduction using derivative-free optimization and
large-eddy simulation. Journal of Fluid Mechanics, 572, 13–36.
[McKinnon(1998)] MCKINNON, K. I. M. (1998). Convergence of the Nelder-Mead
Simplex Method to a Nonstationary Point. SIAM Journal on Optimization, 9,
148–158.
 128

[Mishra et al.(2007)] MISHRA, D., SHAFFER, C. A., RAMAKRISHNAN, N., WAT-

SON, L. T., BAE, K. K., HE, J., VERSTAK, A. A. et TRANTER, W. H. (2007).
S4W : a problem-solving environment for wireless system design. Softw. Pract.
Exper., 37, 1539–1558.
[Nazareth et Tseng(2002)] NAZARETH, L. et TSENG, P. (2002). Gilding the Lily :
A Variant of the Nelder-Mead Algorithm Based on Golden-Section Search. Com-
putational Optimization and Applications, 22, 133–144.
[Nelder et Mead(1965)] NELDER, J. A. et MEAD, R. (1965). A Simplex Method for
Function Minimization. The Computer Journal, 7, 308–313.
[Powell(1964)] POWELL, M. J. D. (1964). An efficient method for finding the mi-
nimum of a function of several variables without calculating derivatives. The
Computer Journal, 7, 155–162.
[Price et al.(2002)] PRICE, C. J., COOPE, I. D. et BYATT, D. (2002). A Convergent
Variant of the Nelder-Mead Algorithm. Journal of Optimization Theory and
Applications, 113, 5–19.
[Rajalakshmi et Hima Bindu(2011)] RAJALAKSHMI, K. et HIMA BINDU, M.
(2011). An Overview of Solution Approaches for Assignment Problem in Wi-
reless Telecommunication Network. V. V. Das, G. Thomas et F. Lumban Gaol,
éditeurs, Information Technology and Mobile Communication, Springer Berlin
Heidelberg, vol. 147 de Communications in Computer and Information Science.
407–410.
[Rappaport(2002a)] RAPPAPORT, T. S. (2002a). Wireless Communications : prin-
ciples and practice. Prentice Hall, seconde édition.
[Rappaport(2002b)] RAPPAPORT, T. S. (2002b). Wireless Communications : prin-
ciples and practice, Prentice Hall, chapitre 1. Seconde édition.
[Reilly(2009)] REILLY, G. B. O. (2009). Frequency Assignment Optimization using
the Swarm Intelligence Multi-agent based Algorithm (SIMBA). J. A. Cordeiro et
J. Filipe, éditeurs, ICEIS 2009 - Proceedings of the 11th International Conference
on Enterprise Information Systems, Volume AIDSS, Milan, Italy, May 6-10,
2009. 25–32.
[Rockafellar(1980)] ROCKAFELLAR, R. T. (1980). Generalized directional deriva-
tives and subgradients of nonconvex functions. Canad. J. Math., 32, 257–280.
 129

[Rosenbrock(1960)] ROSENBROCK, H. H. (1960). An Automatic Method for Fin-

ding the Greatest or Least Value of a Function. The Computer Journal, 3,
175–184.
[Ruiz et al.(1999)] RUIZ, S., COLET, X. et ESTEVEZ, J. J. (1999). Frequency plan-
ning optimisation in real mobile networks. Vehicular Technology Conference,
1999. VTC 1999 - Fall. IEEE VTS 50th. vol. 4, 2082–2086 vol.4.
[Shannon(1948)] SHANNON, C. E. (1948). A Mathematical Theory of Communica-
tion. Bell System Technical Journal, 27, 379–423.
[Sherali et al.(1996)] SHERALI, H. D., PENDYALA, C. M. et RAPPAPORT, T. S.
(1996). Optimal location of transmitters for micro-cellular radio communication
system design. IEEE Journal on Selected Areas in Communications, 14, 662–673.
[Spendley et al.(1962)] SPENDLEY, W., HEXT, G. R. et HIMSWORTH, F. R.
(1962). Sequential Application of Simplex Designs in Optimisation and Evo-
lutionary Operation. Technometrics, 4, 441–461.
[St-Hilaire et Liu(2011)] ST-HILAIRE, M. et LIU, S. (2011). Comparison of different
meta-heuristics to solve the global planning problem of UMTS networks. Comput.
Netw., 55, 2705–2716.
[Torczon(1997)] TORCZON, V. (1997). On the Convergence of Pattern Search Al-
gorithms. SIAM Journal on Optimization, 7, 1–25.
[Tutschku(1998)] TUTSCHKU, K. (1998). Demand-based radio network planning of
cellular mobile communication systems. INFOCOM 98 Seventeenth Annual Joint
Conference of the IEEE Computer and Communications Societies Proceedings
IEEE, 3, 1054–1061 vol.3.
[Vilovic et al.(2007)] VILOVIC, I., BURUM, N. et SIPUS, Z. (2007). Design of an
Indoor Wireless Network with Neural Prediction Model. Antennas and Propa-
gation 2007 EuCAP 2007 The Second European Conference on. 1–5.
[Weicker et al.(2003)] WEICKER, N., SZABO, G., WEICKER, K. et WIDMAYER,
P. (2003). Evolutionary multiobjective optimization for base station transmitter
placement with frequency assignment. Evolutionary Computation, IEEE Tran-
sactions on, 7, 189–203.
[Wikipedia(2011a)] WIKIPEDIA (2011a). Diagramme de Voronoï, Wikipédia,
http ://[Link]/wiki/Diagramme_de_Voronoi.
 130

[Wikipedia(2011b)] WIKIPEDIA (2011b). Spectre électromagnétique, Wikipédia,

http ://[Link]/wiki/Spectre_electromagnetique.
[Wright(1998)] WRIGHT, M. H. (1998). Optimization methods for base station pla-
cement in wireless applications. Proceedings of the 48th IEEE Vehicular Tech-
nology Conference, 1, 387–391.
[Yang et al.(2007)] YANG, J., AYDIN, M. E., ZHANG, J. et MAPLE, C. (2007).
UMTS base station location planning : A mathematical model and heuristic
optimisation algorithms. IET Communications, 1, 1007–1014.
 131

Annexe A

Tableaux de résultats

Les tableaux ci-dessous présentent l’ensemble des résultats finaux pour toutes les
cartes de terrain et de densité et tous les nombres de canaux et d’antennes. Pour
chaque instance, les données présentées sont les valeurs des deux fonctions objectif
principales en pourcentage de la population totale, la variance du nombre d’utilisa-
teurs par antenne V % et le nombre d’usagers non servis Nnc% , le nombre d’évaluations
de boîte noire réalisées, ainsi que le temps d’exécution de l’optimisation.

Note sur le nombre d’évaluations de boîte noire : les nombres d’évaluations de

boîte noire indiqués dans ces résultats sont les nombres d’évaluations totaux, obte-
nus en allant jusqu’au bout de l’étape de terminaison de l’algorithme d’optimisation,
c’est-à-dire jusqu’à l’obtention d’une taille de treillis minimale lors de la dernière re-
cherche Mads pour l’optimisation de la localisation des antennes. Comme indiqué au
chapitre 6, cette dernière étape consomme généralement un grand nombre d’évalua-
tions, et pourrait le plus souvent être arrêtée bien avant d’atteindre ce critère d’arrêt
en conservant une bonne qualité de la solution.

Note sur les temps d’exécution : les tests ont été réalisés sur deux ordinateurs
possédant les mêmes caractéristiques : un processeur Intel i7 à 6 cœurs cadencés à
3.3 GHz avec 12 GB de mémoire, tournant sous OpenSUSE 10.4. Bien que les deux
ordinateurs possédaient des configurations identiques, on a pu constater une certaine
différence entre les temps d’exécution moyens sur les deux machines. Sur la première
machine, la plus rapide, ont été effectués les tests pour toutes les instances de terrain
avec les densités U et C, alors que les densités E et B, ainsi que le terrain M tl, ont
été testés sur la deuxième machine, un peu plus lente. Ceci explique la différence
moyenne de temps d’exécution qui peut être observée entre les instances.
 132

Tableau A.1 Résultats pour l’instance de terrain Square U .

Terrain p n V % × 102 %
Nnc Évaluations Temps (s)
8 64 0.45 4272 37
12 2.3 19 7184 89
4
16 0.15 32 12703 134
20 0.26 41 50347 647
14 0.0013 0 6681 218
21 3.3 0.27 30833 380
7
28 0.13 11 74114 589
35 0.16 18 163870 1599
20 0.0018 0 17858 530
Square U 30 0.099 0 69147 527
10
40 0.92 0.44 147192 1473
50 0.35 4.8 266844 3197
30 0.0017 0 26334 209
45 0.00098 0 77450 784
15
60 0.0018 0 155050 1847
75 0.098 0 435761 6652
40 0.0012 0 55736 705
60 0.00068 0 99200 1299
20
80 0.00062 0 359884 5827
100 0.00064 0 559524 10388
 133

Tableau A.2 Résultats pour l’instance de terrain Square C .

Terrain p n V % × 102 %
Nnc Évaluations Temps (s)
8 1.2e+02 0.27 5254 49
12 35 24 12748 215
4
16 5 44 27622 403
20 2.2 53 46257 898
14 4.4 0 9334 296
21 17 0.49 39919 527
7
28 2.2 15 67380 572
35 1.1 26 149555 1432
20 0.52 0 24318 765
Square C 30 4.7 0 63131 582
10
40 2.2 0.68 181053 1911
50 0.42 7.9 314360 3993
30 0.015 0 31516 334
45 0.12 0 116329 1350
15
60 0.34 0.0084 314744 4372
75 0.52 0.011 719546 12466
40 0.0011 0 55958 563
60 0.0016 0 140666 1943
20
80 0.027 0 483780 6564
100 0.069 0 992199 13040
 134

Tableau A.3 Résultats pour l’instance de terrain Square E .

Terrain p n V % × 102 %
Nnc Évaluations Temps (s)
8 1.5e+02 0.034 5416 57
12 1.1e+02 9.7 11401 188
4
16 13 34 24157 407
20 9.4 42 42109 691
14 17 0 18253 620
21 17 1.5 51996 724
7
28 6.5 10 94988 821
35 3.3 19 196075 1934
20 0.44 0 21567 685
Square E 30 7.8 0 74561 706
10
40 5.9 1 176872 1887
50 2.2 4.7 371763 4452
30 0.25 0 39233 345
45 0.64 0 177353 1981
15
60 1 0 444819 5945
75 0.57 0.36 809432 12893
40 0.0073 0 64851 720
60 0.049 0 359420 4893
20
80 0.2 0 988855 16491
100 0.21 0 1664465 25681
 135

Tableau A.4 Résultats pour l’instance de terrain Square B .

Terrain p n V % × 102 %
Nnc Évaluations Temps (s)
8 73 0.28 5562 57
12 13 18 10192 155
4
16 12 29 29670 430
20 2.7 41 47973 846
14 4.5 0 12768 341
21 9.4 1.5 34909 528
7
28 3.7 7.6 74263 617
35 0.81 17 154560 1455
20 0.059 0 21457 644
Square B 30 2.1 0 60680 512
10
40 2.3 0.95 180575 1823
50 1.2 4.4 402621 4809
30 0.0019 0 37607 318
45 0.28 0 147824 1594
15
60 0.78 0 355461 4715
75 0.33 0.14 917237 14550
40 0.0024 0 66174 693
60 0.008 0 225369 2967
20
80 0.066 0 581080 9612
100 0.082 0 1190929 22763
 136

Tableau A.5 Résultats pour l’instance de terrain Circle U .

Terrain p n V % × 102 %
Nnc Évaluations Temps (s)
8 29 0.064 7274 82
12 0.85 23 8182 127
4
16 1.3 35 16959 338
20 0.056 43 47169 806
14 0.06 0 11651 445
21 1.4 1.1 37291 533
7
28 0.084 12 93016 741
35 0.034 21 159445 1443
20 0.0015 0 14318 728
Circle U 30 0.011 0 62801 486
10
40 0.22 0.85 149967 1427
50 0.022 6.3 311926 3686
30 0.0027 0 30784 242
45 0.00089 0 79794 830
15
60 0.0062 0 176148 2112
75 0.038 0.026 556088 9003
40 0.0011 0 53675 532
60 0.00081 0 95294 1300
20
80 0.00052 0 264631 4480
100 0.0012 0 402030 8108
 137

Tableau A.6 Résultats pour l’instance de terrain Circle C .

Terrain p n V % × 102 %
Nnc Évaluations Temps (s)
8 99 0.76 7292 96
12 38 23 12906 399
4
16 3.2 49 22991 685
20 1.5 56 61190 1327
14 6.3 0 12282 463
21 8.7 1.6 39656 950
7
28 2.1 18 76248 641
35 0.48 31 167095 1559
20 0.15 0 30016 1207
Circle C 30 2.6 0 64250 584
10
40 1.2 1.2 200621 2086
50 0.28 10 317559 3953
30 0.0084 0 40562 325
45 0.031 0 127694 1593
15
60 0.4 0.0061 281920 3911
75 0.34 0.11 629111 10449
40 0.0025 0 63161 858
60 0.0014 0 170326 2440
20
80 0.025 0 596931 8055
100 0.079 0.0046 921258 12606
 138

Tableau A.7 Résultats pour l’instance de terrain Circle E .

Terrain p n V % × 102 %
Nnc Évaluations Temps (s)
8 1.2e+02 1.5 7885 104
12 95 10 12924 257
4
16 42 23 38072 624
20 6.3 45 66880 1490
14 20 0 14832 491
21 21 1 48393 755
7
28 8.3 9.4 110098 934
35 2.5 21 146127 1295
20 3.4 0 36966 1797
Circle E 30 9.7 0 64865 578
10
40 5.9 1.1 213550 2315
50 2.7 4.7 406760 4910
30 0.42 0 66063 571
45 1.4 0 202090 2204
15
60 2.1 0.011 401840 5820
75 1.2 0.066 898047 14251
40 0.037 0 83059 829
60 0.23 0 431491 5621
20
80 0.38 0 881846 14648
100 0.34 0 1751993 27008
 139

Tableau A.8 Résultats pour l’instance de terrain Circle B .

Terrain p n V % × 102 %
Nnc Évaluations Temps (s)
8 51 1.5 3839 42
12 18 17 11436 196
4
16 14 28 19623 457
20 7.1 40 55483 984
14 3.4 0 13098 532
21 17 0.58 38582 715
7
28 4.9 7.1 79692 628
35 1.9 16 146145 1403
20 0.89 0 25029 1054
Circle B 30 4.2 0 64942 506
10
40 3.3 0.99 173064 1659
50 1.5 4.1 406465 4879
30 0.025 0 53429 450
45 0.48 0 155311 1713
15
60 0.88 0 304814 4000
75 0.86 0.078 788180 12353
40 0.0032 0 72347 737
60 0.13 0 345374 4590
20
80 0.17 0 648747 10519
100 0.18 0 1427665 27043
 140

Tableau A.9 Résultats pour l’instance de terrain Banana U .

Terrain p n V % × 102 %
Nnc Évaluations Temps (s)
8 0.021 0 4986 122
12 8.1 5.4 12549 236
4
16 2 16 18350 284
20 0.6 30 52135 821
14 0.0021 0 9460 402
21 0.6 0 24714 986
7
28 0.92 0.8 47797 384
35 0.62 4.9 97115 887
20 0.0035 0 11498 468
Banana U 30 0.0016 0 27472 216
10
40 0.046 0 83706 815
50 0.91 0.051 254433 2939
30 0.0026 0 27095 210
45 0.0011 0 66806 680
15
60 0.0027 0 114686 1460
75 0.002 0 222992 3378
40 0.0062 0 54053 546
60 0.0015 0 117509 1564
20
80 0.00085 0 159743 2798
100 0.00092 0 285133 5966
 141

Tableau A.10 Résultats pour l’instance de terrain Banana C .

Terrain p n V % × 102 %
Nnc Évaluations Temps (s)
8 63 0 7693 157
12 1.1e+02 4.1 12591 267
4
16 81 10 33566 645
20 3.9 40 74298 1387
14 1.9 0 13010 537
21 19 0.0066 48010 860
7
28 6.5 2.2 111913 896
35 2.5 11 159140 1679
20 0.01 0 22096 1110
Banana C 30 1.2 0 69451 599
10
40 2.4 0.47 192967 2124
50 0.5 4.3 306197 3976
30 0.0028 0 27790 241
45 0.12 0 127431 1430
15
60 0.22 0 279559 4268
75 0.36 0.0022 588389 8678
40 0.0029 0 68034 540
60 0.022 0 183543 1748
20
80 0.031 0 476698 5669
100 0.014 0 1399320 18852
 142

Tableau A.11 Résultats pour l’instance de terrain Banana E .

Terrain p n V % × 102 %
Nnc Évaluations Temps (s)
8 68 0 6294 152
12 23 10 15727 236
4
16 17 21 27227 465
20 1.4 44 65183 1137
14 9 0 11904 443
21 13 0 33934 1423
7
28 28 0.84 79240 658
35 20 1.5 142464 1438
20 0.04 0 22921 1072
Banana E 30 1.7 0 82985 686
10
40 3.2 0.014 126027 1362
50 1.3 0.76 358349 4542
30 0.014 0 42112 352
45 0.17 0 135937 1438
15
60 0.22 0 258306 3435
75 0.27 0.36 847102 13471
40 0.0054 0 46000 342
60 0.0074 0 184261 1801
20
80 0.033 0 516637 5910
100 0.044 0 918727 12134
 143

Tableau A.12 Résultats pour l’instance de terrain Banana B .

Terrain p n V % × 102 %
Nnc Évaluations Temps (s)
8 0.006 0 3537 70
12 20 2.1 10275 183
4
16 3.7 18 14529 217
20 2.9 29 43622 717
14 0.0042 0 7486 269
21 2.8 0 25151 912
7
28 3.3 0.32 67176 541
35 2.2 3.8 110116 996
20 0.004 0 11629 446
Banana B 30 0.03 0 43733 346
10
40 0.72 0 109932 1055
50 1.6 0.085 229120 2628
30 0.0036 0 27093 217
45 0.0016 0 73039 781
15
60 0.0022 0 183074 2356
75 0.056 0 430502 6198
40 0.0029 0 46020 477
60 0.0013 0 95452 1371
20
80 0.001 0 195743 3212
100 0.00099 0 402981 7749
 144

Tableau A.13 Résultats pour l’instance de terrain M tl.

Terrain p n V % × 102 %
Nnc Évaluations Temps (s)
8 42 0 5095 133
12 69 4.9 12019 293
4
16 11 17 31048 621
20 3.1 32 62825 965
14 0.2 0 10884 886
21 7.3 0.011 34373 1357
7
28 10 0.51 97826 904
35 1.5 9 148557 1447
20 0.021 0 19186 783
M tl 30 0.86 0 49048 321
10
40 1.8 0 128618 985
50 8 0.096 270779 2648
30 0.0078 0 33128 211
45 0.0035 0 79079 662
15
60 0.092 0 225988 2190
75 0.3 0 473171 5273
40 0.0034 0 47667 342
60 0.0025 0 104183 1010
20
80 0.0025 0 282027 3488
100 0.023 0 699783 9584