Dimensionnement robuste des réseaux optiques sans fil avec des pannes partielles de liens

This thesis summaries the work we have done in optimization of wireless optical networks. More specifically, the main goal of this work is to propose appropriate network dimensioning algorithms for managing the demand and ensuring traffic satisfaction in a network under partial link failures (i.e. when some links and/or nodes are operational with reduced capacity) caused mostly by weather conditions. The primary criterion in deciding the efficiency of the proposed algorithms for the network is the dimensioning cost of the network while keeping the traffic satisfaction at high reasonable levels. The main application area we have in mind are the networks that apply Free Space Optics (FSO) - a well established broadband wireless optical transmission technology where the communication links are provided by means of a laser beam sent from the transmitter to the receiver placed in the line of sight. FSO networks exhibit several important advantages but the biggest disadvantage is vulnerability of the FSO links to weather conditions, causing substantial loss of the transmission power over optical channel. This makes the problem of network dimensioning important, and, as a matter of fact, di cult. Therefore, a proper approach to FSO network dimensioning should take such losses into account so that the level of carried traffic is satisfactory under all observed weather conditions. In this thesis, we firstly describe such an approach. In the first part of the thesis, we introduce a relevant dimensioning problem and present a robust optimization algorithm for such enhanced dimensioning. To construct our approach we start with building a reference failure set which uses a set of weather data records for a given time period against which the network must be protected. Next, a mathematical model formulation of the robust network dimensioning problem uses the above failure set. Yet, such obtained reference set will most likely contain an excessive number of states and at the same time will not contain all the states that will appear in the reality. Hence, we propose to approximate the reference failure set with a special kind of virtual failure set called K-set parameterized by an integer value K, where K is less than or equal to the number of all links in the network. For a given K, the K-set contains all states corresponding to all combinations of K, or less, simultaneously affected links. Sometimes, there are situations where the weather is extremely bad and what we propose is to build a hybrid network model composed of FSO and fiber links. The second part of this thesis is devoted to the improvement of the so-called uncertainty sets (or uncertainty polytopes). In the first part we have introduced the idea of link Ksets. Now we extend this by considering simultaneous degradations of K nodes (meaning degradation of all adjacent links). Finally, inspired by the hitting set problem a new idea was to find a large number of subsets of two or three affected links and to use all possible combinations (composed of 2 or at most 3 of this subsets) to build a new virtual failure set that covers as much as possible the reference failure set that we got from the study of real weather data records. Next, this new failure set will serve as input for our cut-generation xxi algorithm so that we can dimension the network at a minimum cost and for a satisfactory demand realization. A substantial part of the work is devoted to present numerical study for different network instances that illustrates the effectiveness of the proposed approach. A dedicated space is given to the construction of a realistic network instance called Paris Metropolitan Area Network (PMAN).Cette thèse résume le travail que j’ai effectué dans le domaine de l'optimisation des réseaux optiques sans fil. Plus spécifiquement, l'objectif principal de ce travail est de proposer des algorithmes efficaces de dimensionnement de réseau pour assurer la satisfaction du trafic dans un réseau qui subit des pannes partielles de liens (par exemple lorsque certains liens et/ou nœuds sont opérationnels avec une capacité réduite) causés principalement par les conditions météorologiques. Le critère principal pour déterminer l'efficacité des algorithmes proposés est le coût de dimensionnement du réseau tout en maintenant la satisfaction du trafic à des niveaux élevés. Les domaines d'application principale que nous avons à l'esprit sont les réseaux qui utilisent le Free Space Optics (FSO) - une technologie de transmission optique sans fil à large bande où les liens de communication sont assurés au moyen d'un faisceau laser envoyé de l'émetteur au récepteur placé en ligne droite. Les réseaux FSO présentent plusieurs avantages (comme le coût peu élevé, la facilite d'installation, la grande capacité de transmission, etc.), mais le plus grand inconvénient est la vulnérabilité des liens FSO face aux conditions météorologiques, causant une perte substantielle de la puissance de transmission sur le canal optique. Cela rend le problème de dimensionnement du réseau important et difficile. Par conséquent, une approche appropriée du dimensionnement du réseau FSO devrait tenir compte de ces pertes afin que le niveau du trafic transporté soit satisfaisant dans toutes les conditions météorologiques observées. Dans cette thèse, nous avons étudié et développé une telle approche. Dans la première partie de la thèse, nous introduisons un premier problème de dimensionnement, qui a pour objectif d’être le plus général possible et inclue les contraintes les plus importantes. Nous présentons ensuite un algorithme d'optimisation robuste pour ce problème de dimensionnement. Pour construire notre approche, nous commençons par définir un ensemble de défaillances des liens, dit de référence, qui utilise les données météorologiques d’une période donnée pour laquelle le réseau doit être protégé. Ensuite, nous formulons mathématiquement le problème de dimensionnement robuste de réseau qui utilise l'ensemble des pannes de liens ci-dessus. Pourtant, cet ensemble des pannes de référence obtenu contiendra, dans la plupart des cas, un nombre excessif d'états et en même temps ne contiendra pas tous les états qui apparaîtront potentiellement dans le futur. Par conséquent, nous proposons d'approximer cet ensemble par un type spécial d'ensemble de défaillances des liens virtuel (dite ensemble d’incertitude), appelé K-set et paramétré par une valeur entière K, où K est inférieur ou égal au nombre de tous les liens du réseau. Pour un K donné, le K-set contient tous les états du réseau correspondant à toutes les combinaisons de K, ou moins, des liens affectés simultanément. Dans certains cas, il y a des situations où la météo est extrêmement mauvaise et pour lequel nous proposons de construire un modèle de réseau hybride composé de liens FSO et de liens de fibre optique terrestre. La deuxième partie de cette thèse est consacrée à l'amélioration de l’approximation de l’ensemble des pannes de référence via des ensembles de d'incertitude (ou poly-topes d'incertitude). Dans la première partie, nous avons présenté l'idée de K-sets des liens. Maintenant, nous étendons cela en considérant les dégradations simultanées de K nœuds (ce qui signifie la dégradation de tous les liens adjacents)