WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

Gestion du spectre de fréquence et implémentation des reseaux de telecommunications: cas d'un réseau Wimax

( Télécharger le fichier original )
par Khalil Atoui
USTHB - Ingéniorat en recherche operationnelle 2009
Dans la categorie: Rapports de stage
  

Disponible en mode multipage

Soutenons La Quadrature du Net !

TABLE DES MATIÈRES

Preambule Introduction générale

1 Présentation de l'organisme d'acceuil: Algérie Télécom

1.1 Présentation d'Algérie Télécom

1.2 Missions et objectifs d'Algérie Télécom

1.2.1 Missions

1.2.2 Objectifs

1.3 Organisation d'Algérie Télécom

1.4 Organigramme

2 Le réseau d'accés large bande Wimax

2.1 Définition et présentation du Wimax

2.2 Wimax: Evolution des standards

2.3 Apport de Wimax

2.4 Les principaux équipements du réseau

2.5 Applications des réseaux Wimax

2.5.1 La desserte avec Wimax

2.5.2 La collecte avec Wimax

2.6 Les avantages et les inconvénients du Wimax

2.6.1 Les avantages

2.6.2 Les inconvénients

2.7 Technologie autour du Wimax.

2.7.1 Quelques définitions

2.7.2 Importance du spectre de fréquence:

2.7.3 Nécessite de la gestion du spectre de fréquence:

2.7.4 Les objectifs de la gestion du spectre

2.7.5 Les interférences

2.8 Wimax et ses concurrents

1

2

4

4

5

5
5
5

6

8

8

8

9

10

11

11

11

12

12

12

13

13 16 16 16 16 18

2.9 Conclusion 19

3 Problématique et Modélisation 20

3.1 Introduction 20

3.2 Réseaux hertziens 20

3.3 Concept cellulaire 21

3.4 Problématique 23

3.5 Modélisation du problème 23

3.5.1 Modélisation mathématique 24

3.5.2 Modélisation par la théorie des graphes 25

3.5.3 Complexité du probléme 25

3.6 Conclusion 26

4 Méthodes de résolution 27

4.1 Choix des méthodes de résolution 27

4.1.1 Les methodes exactes 27

4.1.2 Méthode exacte de coloration 28

4.1.3 Méthodes de résolution approchée 30

4.1.4 La méthode Tabou adaptée à la coloration des graphes 30

4.2 Conclusion 35

5 Présentation du logiciel 36

5.1 Introduction 36

5.2 Qu'est-ce que Delphi ? 36

5.3 Présentation du logiciel 37

Conclusion générale 45

Bibliographie 46

Annexe 1 48

Annexe 2 50

Acronymes 54

LISTE DES FIGURES

2.1 LOS & NLOS :(Source:Wimax Forum White Paper, 2004) 10

2.2 La desserte avec Wimax 12

2.3 La collecte avec Wimax 13

LISTE DES TABLEAUX

2.1 Comparaison entre Wimax et quelques technologies 18

Preambule

Notre travail, qui s'inscrit dans la cadre de la préparation d'un mémoire de fin d'étude pour l'obtention du diplôme d'ingénieur en recherche opérationnelle, Faculté de Mathématiques, Université des sciences et technologie Houari Boumédienne, Bab ez Zouar, Alger, consiste globalement, à implémenter un logiciel sur la planification du spectre de fréquence sur les stations de bases en utilisant un minimum de fréquences pour une couverture maximale.

Notre mémoire est articulé sur cinq chapitres :

· Dans le premier chapitre, nous procéderons à la présentation de l'entreprise Algérie Telecom.

· Le second chapitre, sera consacré d'abord à une présentation générale puis nous procéderons à une présentataion détaillée de la technologie du Wimax.

· Dans le troisième chapitre nous traiterons de la problématique ainsi que sa formulation mathématique (modélisation).

· Le quatrième chapitre sera réservé aux méthodes de résolution.

· Enfin, le cinquième chapitre sera consacré à l'implémentation ainsi qu'à la description générale du logiciel informatique utilisé et des résultats obtenus.

Introduction générale

De nos jours la demande de connexions à Internet haut débit se fait croissante; Conjointement les accès de type ADSL se multiplient, mais ces technologies présentent certaines limites relatives aux débits et à la portée, et ne permettent pas la souplesse qu'offre une connexion sans-fil.

En effet, il existe aujourd'hui de nombreuses technologies sans fil standardisées; Chacune présente un équilibre entre différents facteurs (portée, débit, capacité, services, niveau d'interférences,. .etc).

Le Wimax (Worldwide Interoperability for Microwave Access) est une alternative pour des connexions sans-fil à haut débit sur des zones de couverture de plusieurs kilomètres, permettant des usages en situation fixe ou en mobilité. Avec une grande couverture, une grande efficacité spectrale et un débit important, le Wimax représente une vraie alternative des systèmes nécessitant des connections câblées, comme l'ADSL par exemple.

Algérie Telecom a obtenue une licence d'exploitation de la technologie Wimax, cette dernière technologie peut convient à cet opérateur qui souhaite offrir un accès internet haut débit de meilleure qualité de service.

C'est dans ce contexte que s'inscrit l'objectif de notre projet de fin d'études intitulé Gestion du spectre des fréquences et l'implémentation dans les réseaux de télécommunications proposé dans le cadre d'une collaboration entre L'Université des Sciences et de la Technologie Houari Boumediene (USTHB), d'une part et l'opérateur Algérie Télécom d'autre part.

Le spectre radioélectrique est devenu une ressource extrêmement précieuse, en raison de son exploitation massive par des systèmes de communication de toutes sortes.

Il faut donc des méthodes novatrices pour gérer le spectre de manière dynamique afin que cette ressource puisse être disponible pour les nouveaux services à même d'éviter les brouillages de signaux.

Le but de cette etude sera de satisfaire la demande de chaque station de base (BTS) en terme de fréquences tout en minimisant l'ensemble des interférences ainsi que la partie du spectre radio.

Pour cela, et à l'issu de ce travail nous proposons l'implémentation d'un logiciel permettant la gestion du spectre de fréquence sur les stations de bases en utilisant un minimum de fréquences pour une couverture maximale.

CHAPITRE 1

Présentation de l'organisme d'acceuil: Algérie

Télécom

1.1 Présentation d'Algérie Télécom

Algérie Telecom, est une société par actions à capitaux publics opérant sur le marché des réseaux et services de communications électroniques.

Sa naissance a été consacrée par la loi 2000/03 du 5 août 2000, relative à la restructuration du secteur des Postes et Télécommunications, qui sépare notamment les activités Postales de celles des Télécommunications.

Algérie Telecom est donc régie par cette loi qui lui confère le statut d'une entreprise publique économique sous la forme juridique d'une société par actions SPA.

Entrée officiellement en activité à partir du 1er janvier 2003, elle s'engage dans le monde des Technologies de l'Information et de la Communication avec trois objectifs:

· Rentabilité

· Efficacité

· Qualité de service

Algérie Telecom est leader sur le marché Algérien des télécommunications qui connait une forte croissance. Offrant une gamme complète de services de voix et de données aux clients résidentiels et professionnels.

Cette position s'est construite par une politique d'innovation forte adaptée aux attentes des clients et orientée vers les nouveaux usages.

Son ambition est d'avoir un niveau élevé de performance technique, économique, et sociale pour se maintenir durablement leader dans son domaine, dans un environnement devenu concurrentiel.

Son souci consiste, aussi, à préserver et développer sa dimension internationale et participer à la promotion de la société de l'information en Algérie.

1.2 Missions et objectifs d'Algérie Télécom

1.2.1 Missions

L'activité principale d'Algérie Télécom est de :

· Fournir des services de télécommunication permettant le transport et l'échange de la voix de messages écrits, de données numériques et d'informations audiovisuelles.

· Développer, exploiter et gérer les réseaux publics et privés de télécommunications.

· Etablir, exploiter et gérer les interconnexions avec tous les opérateurs des réseaux.

1.2.2 Objectifs

Algérie Telecom est engagée dans le monde des technologies de l'information et de la communication avec les objectifs suivants :

· Accroître l'offre de services téléphoniques et faciliter l'accès aux services de télécommunications au plus grand nombre d'usagers, en particulier en zones rurales.

· Accroître la qualité de services offerts et la gamme de prestations rendues et rendre plus compétitifs les services de télécommunications.

· Développer un réseau national de télécommunication fiable et connecté aux autoroutes de l'information.

1.3 Organisation d'Algérie Télécom

Algérie Télécom est organisée en Divisions, Directions Centrales, et Régionales, a cette structure s'ajoutent trois filiales:

- Mobile (Mobilis)

- Internet (Djaweb)

- Télécommunications Spatiales (RevSat)

Algérie Telecom s'implique dans le développement socio-économique du pays à travers la fourniture des services de télécommunications.

En outre, Algérie Télécom met en oeuvre des moyens importants pour rattacher les localités isolées et les établissements scolaires.

Le Marketing et l'action commerciale pour réhabiliter l'image de marque d'Algérie Telecom et fidéliser sa clientèle, notamment par la mise en place du système informatique « GAIA » qui permet :

· Le client aura un guichet unique au niveau de l'ACTEL, qui saisit la demande du client, ses coordonnées, l'adresse, etc.

· La suppression de l'échange de papier entre les services techniques du CECLI et l'Actel "gestion zéro papier" .

· Permettre aux clients de consulter leurs factures à travers l'Internet.

· Recrutement et formation.

· Partenariat Dans le cadre du partenariat, Algérie Télécom pourra profiter aussi bien du savoir faire que de capitaux. S'agissant de diversification d'activités, la branche des services d'Algérie Télécom, contrairement à celle des infrastructures sera largement ouverte à la concurrence à travers des partenariats susceptibles d'engendrer l'épanouissement de l'investissement pour obtenir des niveaux de rentabilité élevés avec des retours rapides sur investissements.

· Introduction massive des nouvelles technologies.

1.4 Organigramme

L'organigramme d'Algérie Télécom se présente comme suit :

Organigramme d'Algérie Télécom

CHAPITRE 2

Le réseau d'accés large bande Wimax

2.1 Définition et présentation du Wimax

Le Wimax ou Worldwide Interoperability for Microwave Access, est une norme technique développée par le consortium Wimax Forum. Celle ci basée sur le standard de transmission radio 802.16, validé en 2001 par l'organisme international de normalisation IEEE. En effet, le Wimax ressemble au Wifi mais avec des performances nettement supérieures en de nombreux points.

Plusieurs standards relèvent du terme Wimax : les plus avancés concernent les usages en situation fixe (le client ne bouge pas), mais une version mobile (connexion à haut débit en situation de mobilité) est entrain de voir le jour et qui à pour objectif d'étendre Wimax à des machines terminales mobiles, impliquant donc la possibilité de réaliser des connexions xDSL sans fil vers des mobiles.

2.2 Wimax: Evolution des standards

Le tableau ci-aprés montre que la technologie Wimax réunit plusieurs standards, tous à des états d'avancement différents, qui sont autant d'axes de travail du groupe IEEE 802.16.

Les différentes normes 802.165: (source :IEEE Standard for Local and metropolitan area
networks,2004).

Les révisions du standard IEEE 802.16 se déclinent en deux catégories :

Wimax fixe/résidentiel (802.16-2004): destiné à un usage fixe, du domicile à l'antenne relais et opérant dans des bandes de fréquences de 2.5 GHz et 3.5 GHz (avec licence d'exploitation obligatoire) et 5.8 GHz (bande libre). Le débit maximum théorique est de 75 Mbit/s pour une portée de 50 à 70 kilomètres sans obstacles.

Wimax mobile/nomade (802.16 e) : prévoit la possibilité de connecter des clients mobiles au réseau Internet. Le Wimax mobile ouvre ainsi la voie à la téléphonie mobile sur IP ou plus largement à des services mobiles hauts débit. Le débit maximum théorique est de 30 Mbit/s pour une portée de 2 à 4 kilomètres sans obstacles.

La portée, les débits et surtout la nécessité ou non d'être en ligne de vue de l'antenne émettrice, dépendent de la bande de fréquence utilisée. Dans la bande 11-66 GHz, les connexions se font en ligne de vue: LOS (Line Of Sight), alors que sur la partie 2-11 GHz, le NLOS (Non Line Of Sight) est possible notamment grâce à l'utilisation de la modulation OFDM. Ceci ouvre la voie à des terminaux d'intérieur, facilement installables par l'utilisateur final car ne nécessitant pas l'installation d'antennes extérieures par un technicien agréé.

Actuellement les standards Wimax actifs ou en cours de normalisation, sont limités aux fréquences entre 2 et 11 GHz. Selon les pays, les bandes Wimax sont soit libres soit soumises à une licence.

2.3 Apport de Wimax

L'objectif du Wimax est de fournir une connexion Internet à haut débit sur une zone de couverture de plusieurs kilomètres de rayon. Le standard Wimax possède l'avantage de permettre une connexion sans fil entre une station de base et des milliers d'abonnés sans nécessiter de ligne visuelle directe (en anglais Line Of Sight, parfois abrégée LOS) ou NLOS (pour Non Line Of Sight). Dans la réalité le Wimax ne permet de franchir que de petits obstacles tels que des

Figure 2.1: LOS & NLOS :(Source:Wimax Forum White Paper, 2004).

arbres ou une maison mais ne peut en aucun cas traverser les collines ou les immeubles. Le débit réel lors de la présence d'obstacles ne pourra ainsi excéder 20 Mbit/s.

Le déploiement du Wimax permet à des zones isolées, mal desservies par le DSL ou le câble ou souhaitant tirer profit d'une connexion sans fil, de disposer d'un accès Internet large bande. Le développement du Wimax pourrait donc jouer un rôle important dans l'aménagement numérique du territoire.

Le débit et la portée présentent les atouts du Wimax. Il fonctionne à 70 Mbit/s maximum théoriquement dans des conditions extrêmement favorables, 12 Mbits/s pratiquement et peut couvrir des zones de rayon allant jusqu'à 50 Km.

2.4 Les principaux équipements du réseau

Depuis le coeur du réseau et en descendant vers l'utilisateur, on trouve les éléments suivants :

· Une liaison à très haut débit, par exemple par fibre optique ou faisceau hertzien, alimentant l'émetteur Wimax.

· Station de base BTS physiquement, elles sont constituées d'une antenne et d'un matériel radio contenant le dispositif électronique. Placées à une hauteur de 12 à 50 m, les antennes utilisent en général des supports tels que (château d'eau, toit d'immeuble, pylône.. . etc.).

· Entre l'antenne et l'utilisateur, plusieurs kilomètres de transmission sans fil. Le Wimax peut assurer une transmission sans ligne de vue (c'est-à-dire même lorsque des obstacles tels que des arbres se trouvent entre l'émetteur et le récepteur), mais cela, a généralement pour effet de réduire notablement la portée.

· Chez l'abonné, une antenne Wimax assure la liaison entre l'émetteur de la zone et l'équipement connecté (ordinateur ou autre).


· Le débit maximum est de quelques dizaines de Mbits/s, mais il est partagé entre tous les utilisateurs raccordés à une même station. Par ailleurs, le débit dépend de quelques facteurs, tels que la distance entre l'usager et la station, ou la topographie des lieux.

Figure 2.2: Antenne Wimax

2.5 Applications des réseaux Wimax

2.5.1 La desserte avec Wimax

Le but de la desserte est de relier le client final à un réseau donné afin qu'il puisse accéder à Internet.

Pour cela, le client doit posséder un récepteur Wimax (une puce intégrée ou un CPE : Customer Premise Equipement) et se trouver dans le champ d'action d'un émetteur. La transmission entre le client et son hot spot Wimax est dite en "non ligne de vue" (NLOS), c'est-à-dire que le client ne se trouve pas en vue directe avec l'antenne. En effet, les bâtiments ou la végétation que l'on trouve dans les villes "forcent" le signal à être détourné grâce à l'utilisation de la modulation de fréquence OFDM.

2.5.2 La collecte avec Wimax

Dans un réseau, la collecte consiste à relier les points d'accès (hot spots Wifi ou DSLAM) assurant ainsi la connexion avec Internet. On appelle ce mécanisme le backhauling de hots spots. Contrairement à la desserte, la collecte se fait en "ligne de vue" (LOS), grâce à des émetteurs Wimax placés suffisamment haut.

L'avantage du Wimax réside dans sa simplicité de mise en oeuvre. Il ne faudra que deux antennes pour relier deux réseaux distants, là où il aurait fallu des kilomètres de fibre optique en filaire.

Figure 2.2: La desserte avec Wimax

2.6 Les avantages et les inconvénients du Wimax

Les avantges et les inconvénients du wimax peuvent se résumer comme suit :

2.6.1 Les avantages

· La possibilité de réutilisation d'une fréquence dédiée à une BTS pour augmenter la capacité du système, ainsi le système peut supporter des centaines d'utilisateurs.

· L'allocation de fréquences se fait de façon sectorielle quand le nombre d'utilisateurs augmente.

· Cout faible, le Wimax permet un déploiment plus rapide sans nécessité de gros travail de génie civile.

· Permet de conectivités internet sans fil à haut débits sur de longues distances.

· Peut servir plusieurs clients à la fois.

· Un signale malgré les obstacles.

· Perspective de nomadisme.

2.6.2 Les inconvénients

· Pour avoir des distances et des débits optimaux, l'émetteur et le récepteur doivent être en « ligne de vue». Hors « ligne de vue », les débits chutent rapidement.

· Le débit est partagé entre les usagers d'une même antenne centrale.

Figure 2.3: La collecte avec Wimax

· Nécessité de déservir les stations de base Wimax par un reseau de collecte (fibre optique, faisceau hertzien....).

· Nécessité de disposer d'une licence : seuls les détenteurs d'une licence sont à même de déployer des reseaux Wimax; Le nombre de licences délivrées est limité.

· Nécessité de disposer d'un point haut : afin d'assurer la meilleure couverture possible, l'emetteur doit étre placé sur un point haut (pylône, chateau d'eau,etc.).

2.7 Technologie autour du Wimax.

Les technologies hertziennes sont prometteuses pour tous les pays qui cherchent à assurer un accés aux technologies de l'information et de la communication et à mettre en place la societé de l'information; Le spectre de fréquence en est un composant essentiel.

Afin de mieux cerner la problématique, il est necessaire de procéder au préalable à certaines défintions.

2.7.1 Quelques définitions

-Fréquence:

En physique, la fréquence désigne en général la mesure du nombre de fois qu'un phénomène périodique se reproduit par unité de temps; C'est-à-dire le nombre de fois qu'un phénomène temporel régulier se reproduit identique à lui-même par intervalle de temps donné.

L'unité de fréquence étant l'hertz (hz), les fréquences sont exprimées:

· En kilohertz (Khz), jusqu'à 3 000 Khz inclus;

· En mégahertz (Mhz), au-delà de 3 Mhz, jusqu'à 3 000 Mhz inclus;

· En gigahertz (Ghz), au-delà de 3 Ghz jusqu'à 3 000 Ghz inclus.

-Bande de fréquence:

Les bandes de fréquences sont l'ensemble des fréquences comprises dans un intervalle donné :

· Les basses fréquences sont comprises entre 30 et 300 Khz.

· Les hautes fréquences sont comprises entre 3 et 30 Mhz.

-Ondes radioélectriques ou ondes hertziennes:

Ondes électromagnétiques dont la fréquence est inférieure à 3000 Ghz, se propagent dans l'espace sans guide artificiel.

-Spectre de fréquence:

Le spectre de fréquence est la partie du spectre électromagnétique qui achemine les ondes radio; Il est subdivisé en neuf bandes de fréquences, désignées par des nombres entiers consécutifs conformément au tableau ci-aprés.

Tableau 2.2: Les différents types de bande de fréquences.

Les bandes allouées par la ARPT pour le déploiment du réseau Wimax se situent entre: 3.4 à 3.6 Ghz.

Il est à noter que l 'Autorité de Régulation de la Poste et des Télécommunications (ARPT)a été créée dans le cadre de la libéralisation des marchés postal et des télécommunications. Leur ouverture à la concurrence et à la promotion de la participation de l'investissement privé dans ces marchés, ont été consacrés par la loi n°2000-03 du 5 août 2000 fixant les règles générales relatives à la poste et aux télécommunications.

Parmi les missions principales de l'ARPT dans le domaine des fréquences radioélectriques, elle est chargée de planifier, gérer, assigner et contrôler l'utilisation des fréquences dans les bandes qui lui sont attribuées dans le respect du principe de non discrimination;

Il en est de même en ce qui concerne l'Agenge Nationale des fréquences ANF;

C'est un établissement public national à caractère industriel et commercial doté de la personnalité morale et de l'autonomie financière.

L'ANF est régie par les règles administratives dans ces relations avec l'état et par les règles commerciales dans ses relations avec les tiers.

Elle est chargée :

· de mener des études en vue d'une utilisation optimale du spectre des fréquences radioélectriques.

· de la planification, la gestion et le contrôle de l'utilisation des fréquences radioélectriques.

· d'élaborer le règlement national des radiocommunications et de fixer les règles nationales et les procédures relatives à la répartition des bandes de fréquences.

· d'attribuer les bandes de fréquences.

· de préparer les éléments nécessaires à la définition des positions et des actions de l'Algérie
dans les négociations internationales dans le domain des fréquences radioélectriques.

· d'assurer la coordination de l'utilisation des fréquences dans les zones frontalières.

Figure 2.6: Répartition des bandes de fréquences Wimax dans le monde (source: Wimax
Forum White Paper, 2006)

2.7.2 Importance du spectre de fréquence:

La demande de la ressource spectrale a nettement augmenté en Algérie au cours de la dernière
décennie, notamment dans les bandes de fréquences affectées aux communications hertziennes
(liaisons hyperfréquences, téléphonie cellulaire, accès hertzien fixe, accès hertzien sans fil, etc.)

Le spectre des fréquences est l'épine dorsale d'une large gamme d'activités dans des secteurs tels que les télécommunications, la radiodiffusion, les transports, la recherche et le développement.

Avec le developpement de ces technologies et leurs implications dans la croissance économique du pays et leur rareté, leur impotance dans notre vie de tous les jours et de plus en plus grandissante; Il est donc nécessaire de prévoir une gestion rationellle de cette ressource.

2.7.3 Nécessite de la gestion du spectre de fréquence:

La croissance continue de la demande de spectre, aussi bien pour les services existants que pour les nouveaux services radio, exerce des contraintes de plus en plus fortes sur cette ressource notamment en ce qui concerne l'équilibre entre l'offre et la demande ; Cette ressource doit être gérée d'une manière efficace et efficiente afin que l'on puisse en retirer un maximum d'avantages sur les plans économiques et socials. Plus le spectre radioélectrique est encombré, plus il est difficile à gérer, et plus l'outil nécessaire pour bien le gérer doit être performant. Il faut donc des méthodes novatrices pour le gérer de manière dynamique afin qu'elle puisse être disponible pour les nouveaux services. Sa gestion permet également d'éviter les brouillages de signaux (interférences).

2.7.4 Les objectifs de la gestion du spectre

· Garantir une plus grande facilité d'utilisation du spectre.

· Rationaliser l'usage du spectre, même dans un environnement où la fréquence n'est pas encore une ressource rare.

· Garantir la disponibilité des fréquences.

· Répondre au besoin de développement des télécommunications et des radiocommunications nationales.

· Répondre aux besoins de la sécurité et de la défense nationale.

· Contrôler l'utilisation (conformité) du spectre.

La non gestion rationelle du spectre de fréquence entraine automatiquement une mauvaise qualité du signal par la création d'interférences.

2.7.5 Les interférences

On parle d'interférence lorsqu'un point donné de l'espace de couverture reçoit en plus du signal utile (assurant le service) un signal dit interférent de puissance relativement élevée et porté sur une fréquence identique ou adjacente.

Il existe deux grands types d'interférences: celles qui sont dues a la réutilisation d'une même fréquence (interférence Co-canal) et celles qui sont dues à l'utilisation de fréquences adjacentes (interférence canal adjacent).

Interférences Co-canal

Ce sont des interférences induites par des signaux émis sur la même porteuse. Ceci se produit quand un point de la zone de couverture reçoit plusieurs signaux provenant de différents BTS et émis sur la même fréquence.

Interférence Co-canal

Interférences canal-adjacent

Les signaux émis sur des fréquences adjacentes entrainent des interférences non négligeables.

Interférence canal-adjacent

2.8 Wimax et ses concurrents

Les différentes technologies d'accès à la donnée sans fil offrent des débits différents sur des zones de couvertures différentes. Chaque technologie devrait pouvoir trouver sa place, son usage et sa cible. Le Wimax permettra à partir de stations de base Wimax d'aroser des aglomérations dans des zones rurales à faible pénétration voire des pays ou l'infrastructure de communications est souvent moins développée (notamment des pays en voie de développement) n'ayant pas d'accès a l'Internet haut débit. Le Wimax serait alors une alternative au câble classique d'Internet haut débit qui reste un moyen d'accès couteux en termes d'investissement.

Le Wimax pourrait venir en complément du WiFi pour couvrir des zones plus larges, rendant ainsi possible la concentration des hots spots WiFi et donc la création de hot-zones.

L'utilisateur se connecterait toujours en WiFi (identification et facturation) et le Wimax viendrait renforcer la connexion en termes de capacité, de débit, et de couverture.

Technologie

WiFi

Wimax

3G/UMTS

EGE

Débit

11 Mbits/s

75 Mbits/s

384 Kbits/s

115 Kbits/s

Couverture

Local/Immeuble

Petite ville

Agglomération

Agglomération

 

Tableau 2.1: Comparaison entre Wimax et quelques technologies

2.9 Conclusion

Etant une technologie d'accès radio sans fil, le Wimax offre un ensemble d'avantage comme le débit élevé, le faible coût ou encore la large portée par rapport aux autres réseaux sans fil. Toutes ces caractéristiques lui permettent de réaliser un succès pertinent et des demandes en croissance continues depuis son apparition. S'il y a un domaine où le Wimax excelle, c'est surtout dans sa capacité de diffusion sur une zone de territoire très large (portée d'une dizaine de kilomètres en zones rurales). Cette caractéristique répond clairement au besoin des zones trop éloignées qui ne peuvent être raccordées au réseau fixe DSL. Un déploiement massif de cette technologie pourrait révolutionner le haut débit. Grâce à des connexions sans-fil à haut débit sur des zones de couverture très large, le Wimax permet des usages en situation fixe, ou même mobile. De plus, les enjeux économiques de cette technologie sont très importants. En effet, en termes de coût, la mise en place de ce réseau serait bien moins couteuse que le déploiement d'une infrastructure filaire. Effectivement, alors que les technologies DSL doivent intégrer des réamplifacteurs de signaux tous les 5 à 10 Km, une station de base peut relier à un réseau, des clients distants de 40 Km (diamétralement opposés). De plus, le fait que les standards sont normalisés, le coût des équipements devrait chuter assez rapidement.

CHAPITRE 3

Problématique et Modélisation

3.1 Introduction

Depuis les années 80, le probléme d'affectation de fréquences a fait l'objet d'études menées par différents chercheurs dans le but d'une meilleurs gestion. Le spectre de fréquences qui est attribué aux opérateurs de téléphonie est divisé en canaux fréquentiels. L'allocation de fréquences regroupe les mécanismes et procédures mis en oeuvre afin de gérer l'attribution des canaux de fréquences aux demandes de communication. Cette gestion permet de déterminer la qualité du réseau.

L'objet de ce chapitre sera de poser la problématique de l'affectation de fréquences et la traduire en théorie des graphes; Ceci nous permettra d'une part de proposer des solutions à même de résoudre cette problématique et d'autre part, de présenter quelques définitions de base qui nous permettrons de mieux comprendre la problématique posée.

3.2 Réseaux hertziens

L'objectif d'un système de radio hertziens tel que le Wimax est de permettre l'accès au réseau à partir d'un terminal portatif sur une zone géographique plus ou moins vaste. Cet accès est réalisé grâce à une liaison hertzienne. Pour que la qualité des communications soit satisfaisante, la puissance de réception doit être assez élevée, rendant nécessaire la bonne distribution d'un ensemble de stations de base sur le territoire à couvrir. Chaque station de base couvre une partie du territoire appelée cellule.

Utilisation de plusieurs antennes à faible puissance au lieu d'une antenne puissante

Les deux schémas de configuration d'un site:(a) site muni d'une seule antenne
omnidirectionnelle, (b) site muni de trois antennes sectorielles.

Les stations de base composant le réseau sont regroupées en emplacements géographiques appelés sites. Selon le type d'antennes utilisées, un site peut contenir une ou plusieurs BTS. Plus précisément, une seule antenne omnidirectionnelle, ou plusieurs antennes sectorielles. Les schémas ci-dessus représentent les deux configuration possible de site.

Le schéma (a) représente un site muni d'une seule antenne omnidirectionnelle, le schéma(b) montre un site à trois antennes sectorielles. Dans le réseau Wimax, il est usuel de limiter le nombre d'antennes séctorielles sur un site à trois.

3.3 Concept cellulaire

Une cellule représente l'ensemble des points du territoire couvert par une même station (BTS).Chaque station de base peut posséder plusieurs antennes donnant ainsi naissance à plusieurs cellules (appelées secteurs dans ce cas), généralement trois. Des stations de base mono-sectorielles, couvrant la zone à 360°, sont utilisées dans les zones trés peu peuplées et dans les centres villes pour créer des microcellules. Des stations de base bi-sectorielles, donnant naissance à deux cellules de 180° chacune, sont souvent mises en place aux abords des autoroutes.

Les stations de base tri - sectorielles sont les plus répandues et les plus utilisée pour le réseau Wimax; elles génèrent trois cellules de 120°.

Modèle du concept cellulaire

La forme hexagonale à été universellement adoptée comme représentation théorique du design cellulaire [Mac Donald,1979]. En effet l'hexagone désigne la forme géométrique la plus proche du cercle (propagation des ondes radio dans un espace sans obstacles) qui permet un pavage régulier du plan en utilisant le moins de cellules. De plus il garantit une uniformité des distances entre les émetteurs, la régularité des schémas d'antennes et de la propagation des ondes radio en espace libre. La réalité, cependant, s'écarte de cette vue théorique. La non régularité des reliefs géographiques (montagnes, plateaux...) et architecturaux (bâtiments, maisons...) fait que la propagation des ondes ne s'effectue pas de la même façon dans toutes les directions. De ce fait, des prolongements, des rétractions voir même des discontinuités importantes apparaissent dans la couverture des cellules.

Concept cellulaire: (a) couverture théorique, (b) couverture réelle.

Le concept cellulaire constitue le fondement de base des réseaux hertziens. Premièrement, l'utilisation du concept cellulaire permet l'ajustement des ressources radio à la demande en trafic. Cet ajustement est réalisé en densifiant les zones à forte demande en communications.

Le principe de densification se traduit par des zones urbaines à forte concentration de BTS couvrant de petites cellules et des zones rurales à faible concentration de BTS couvrant des cellules de grande taille.

La réutilisation des ressources radio (fréquences) dans les réseaux hertziens constitue le deuxième intérêt du concept cellulaire. En effet l'opérateur est restreint à un nombre limité de fréquences pour couvrir l'ensemble du réseau, ce qui rend nécessaire la réutilisation du spectre radio mainte fois de façon à prévenir les situations d'interférences entre les ondes radio. En conséquence de la réutilisation des fréquences, le réseau est capable d'écouler un nombre de trafic beaucoup plus grand que le nombre de fréquences disponibles.

3.4 Problématique

Aujourd'hui les operateurs radio doivent faire face à un double défit: répondre à une augmentation croissante du trafic tout en maintenant une bonne qualité radio. La difficulté du problème résulte du fait qu'une solution acceptable doit satisfaire des contraintes multiples, la plupart des fois contradictoires.

L'une des contraintes les plus sévères c'est le nombre restreint de fréquences (canaux) disponibles pour l'allocation (le spectre radio étant une ressource très limitée). Cette contrainte impose un degré élevé de réutilisation des fréquences, fait qui augmente la probabilité d'interférence.

Algérie Télécom dispose d'un nombre limité de fréquences pour couvrir la totalité d'un térritoire. Pour celà, la réutilisation des fréquences est par conséquent inévitable pour augmenter la capacité du réseau et répondre à la demande de plus en plus importante. Une disrtibution optimale du spectre de fréquences disponibles sur les stations doit garantir un écoulement maximal du trafic tout en minimisant les interférences. L'écoulement de trafic porté par ces zones est alors conditionné par la qualité de l'affectation des fréquences.

Afin de satisfaire cette demande, il est indispensable d'exploiter cette ressource d'une manière rationnelle et optimale; Il est donc légitime de s'interesser à une modelisation plus fine de la problématique de planification de fréquences. Un tel projet nécessite l'utilisation de méthodes scientifiques basées sur des téchniques de recherche operationnelle.

Notre zone d'étude concernera la Wilaya d'Alger avec 8 kmcomme taille de la cellule.

3.5 Modélisation du problème

Comme mentionné dans le chapitre precédent, les gestionnaires sont souvent confrontés à de multiples problèmes et leur résolution s'avère souvent une tâche difficile. Ces problèmes se présentent sous forme de données, de contraintes dont on doit en tenir compte.

Pour arriver à résoudre un problème donné, nous devons commencer par interpréter tous ses paramètres et les transformer sous des formes qu'on peut gérer. La première étape dans

la résolution d'un problème consiste en sa projection dans un espace permettant ainsi diverses manipulations sur le problème projeté. Ce dernier s'appelle le modèle associé au problème.

La modélisation est donc une traduction des paramètres du problème dans un langage accessible par la méthode de résolution utilisée, ou bien c'est une façon de décrire le problème sous une forme qui introduit sa réalisation.

Enfin, la modélisation d'un problème doit pouvoir donner une interprétation aux solutions concrètes répondant aux besoins du problème réellement posé.

Les différentes étapes de la modélisation.

3.5.1 Modélisation mathématique

Les données du problème

N : nombre de stations.

NF: nombre de fréquences disponibles.

C [j]: nombre de cellules à considérer.

R[j]: pour chaque station i, nous connaissons le nombre de fréquence requis.

Contrainte:

- Respecter la contrainte d'interférence Co - canal,

ie: éviter d'assigner la même fréquence à deux cellules voisines.

Objectifs :

Trouver un bon plan de fréquence qui doit minimiser l'ensemble des interférences ainsi que la partie du spectre radio.

3.5.2 Modélisation par la théorie des graphes

Le probléme d'affectation de fréquences est un probléme de la classe du coloriage de graphe (Graph Coloring Problem).

Soit un graphe G = (X, E) defini par:

X: L'ensemble des sommets du graphe représentent les transmetteurs (TRX).

E: L'ensemble des arêtes du graphe représentent les risques d'interférences,

Il existe une arête [xi, xj] de E ssi xi est voisin avec x (voir figure ci-dessous).

Pour résoudre le probléme d'affectation de fréquences, on utilise la coloration des sommets qui consiste à affecter à tous les sommets du graphe une couleur (fréquence) de façon que chaque paire de sommets soit de couleurs differentes; En d'autre termes, s'il existe une arête [xi, xj] de E alors on a c(i) =6 c(j).

Le nombre minimum de couleurs nécessaires pour colorier ce graphe en respectant cette contrainte, est appelé le nombre chromatique XG.

L'application de la théorie des graphes va nous permettre de trouver le nombre minimal de fréquences allouées aux stations de bases et qui minimise l'intégralité des interférences.

Allocation des fréquences dans les réseaux cellulaires

3.5.3 Complexité du probléme

Le probléme de la détermination du nombre chromatique XG est difficile. Plus précisément, déterminer si un graphe donné à une k-coloration pour un k > 2 fixé est NP-complet .

Notre graphe doit être colorié avec au moins 3 couleurs (la taille de la clique max est égale à w(G) = 3), donc, il est NP-dure.

Afin de déterminer le nombre chromatique d'un graphe, un algorithme exact peut être appliqué si la taille du graphe n'est pas trop grande. Sinon, on se contente d'estimer le nombre chromatique, en utilisant par exemple un algorithme heuristique telque la Recherche Tabou qui ne donnera qu'une borne supérieure mais qui est bien plus rapide qu'un algorithme exact.

3.6 Conclusion

Dans ce chapitre nous avons mis en exergue les difficultés de la gestion des fréquences, posé la problématique avec les principaux objectifs assignés à notre étude et par la même nous avons procédé à sa modélisation.

Dans le chapitre suivant nous traiterons des méthodes de résolutions de cette problématique.

CHAPITRE 4

Méthodes de résolution

4.1 Choix des méthodes de résolution

L'optimisation combinatoire occupe une place trés importante en Recherche Operationnelle, en mathématiques discrètes et en informatique. Son importance se justifie d'une part par la grande difficulté des problémes d'optimisation et d'autre part par de nombreuses application pratiques pouvant être formulées sous la forme d'un probléme d'optimisation combinatoire. Bien que les problèmes d'optimisation combinatoire soient souvent faciles à définir, ils sont généralement difficiles à résoudre. En effet, la plupart de ces problèmes appartiennent à la classe des problémes NP-difficiles et ne possédent donc pas à ce jour de solution algorithmique efficace valable pour toutes les données.

Pour la résolution des problèmes, en recherche opérationnelle, le choix de la méthode de résolution constitue une étape cruciale. Il existe deux grandes familles de méthodes de résolution. D'un coté, les méthodes exactes (complétes) qui garantissent la complétude de la résolution, de l'autre les méthodes approchées heuristiques métaheuristiques (incomplétes) qui perdent en complétude pour gagner en efficacité.

La principale différence entre ces deux familles réside dans le fait que la qualité des résultats donnés par les heuristiques n'est pas garantie par la théorie. Les méthodes exactes soutenues par la théorie, aboutissent aux solutions optimales du problème. En pratique, les méthodes exactes sont sensiblement liées à la taille du problème et leur utilisation est sanctionnée par des temps d'exécution souvent inacceptables. Tandis que les heuristiques et métaheuristiques montrent qu'elles peuvent aboutir à des résultats très satisfaisants en des temps beaucoup plus raisonnables.

4.1.1 Les methodes exactes

On peut définir une méthode exacte comme une méthode qui garantit l'obtention de la solution optimale pour un problème d'optimisation. L'utilisation de ces méthodes s'avèrent particulièrement intéressante, mais elles sont souvent limitées au cas des problèmes de petite taille.

4.1.2 Méthode exacte de coloration

Le seul moyen connu pour déterminer le nombre chromatique d'un graphe G est de faire une énumération (implicite) de toutes les colorations de G. On commence en général par considérer une borne supèrieure q de XG.

Une méthode standard d'une telle énumération consiste à considérer un ordre de sommets V1, ,Vn. Soit q la plus petite valeure pour laquelle il existe une q - coloration lors du processus d'énumération.

Comme nous savons que le nombre chromatique XG est inferieur ou égale a N (nombre max de couleur), nous posons initialement q est égale a N, puis nous colorons successivement les sommets V1, ,V n avec la plus petite couleure possible. Si une couleur inferieure à q est affectée à chaque sommet, alors une coloration en q1 < q couleurs à été obtenue.

Nous posons q = q1, et nous effectuons marche arrière jusqu'au sommet Vj tel que Vj+1 soit le premier sommet coloré avec la couleur q1. Nous tentons d'attribuer à Vj la plus petite couleur possible, supérieure à la couleur courante et inferieure à q. Si une telle couleur est trouvée, alors nous procédons comme auparavant en colorant itérativement les sommets Vj+1 à Vn.

Si à une certaine étape, la plus petite couleur pour un certain sommet V, est égale a q, alors nous effectuons une marche arrière jusqu'au sommet Vp_1 et nous poursuivons le processus comme précédemment.

L'algorithme se termine lorsque nous devons faire marche arrière à partir du sommet V1.

[// {On a: w(G) XG max dG , pour notre cas, la taille de la clique max est égale à trois d'ou: w(G) = 3,et le deg max du graphe est égale à: 6, donc on en déduit que: 3 XG 6.//}.

Cette méthode peut se résumé comme suit :

Etapel:

L'étape une est basée sur l'algorithme séquentiel suivant:

· Poser q égale au nombre maximum de couleur N.

· Pour chaque sommet d'un graphe G, déterminer les degrés, puis classer les sommets dans l'ordre décroissant de leurs degrés.

· Parcourir la liste des sommets du graphe (i := 1 a n) , en attribuant à chaque sommet xi la plus petite couleur possible, c'est-à-dire la plus petite couleur qui n'est pas utilisée par x adjacent à xi, pour tout j <i.

· Si la couleur q n'a pas été utilisée, nous avons obtenu une coloration en q1 <q couleurs, et remplaçons q par q1(q := q1).

Etape 2:

· Faire marche arrière (en décolorant les sommets) jusqu'au sommet xr tel que xr+1 ait été le premier sommet à avoir la couleur q.

· Nous recolorons xr avec la plus petite couleur possible qui soit plus grande que sa couleur courante.

· Recolorier à nouveau les sommets xr, . . . , x avec l'algorithme séquentiel.

· Si à un moment donné la couleur q doit être affectée à un sommet x5 (ce que nous voulons éviter, puisque nous voudrions utiliser moins de q couleurs), nous remontons dans l'algorithme séquentiel jusqu'au sommet x5_1 et faisons comme précédemment (c'est-à- dire recolorer x5_1 avec la plus petite couleur possible qui soit plus grande que sa couleur courante et continuer).

· L'algorithme se termine lorsque l'on est remonté jusqu'à x1, et XG est égal à la valeur courante de q.

Exemple illustratif

Figure 4.1 :Exemple illustratif

Sommets

1

2

3

4

5

6

7

8

9

10

11

12

13

Sommets triés

6

7

8

2

3

11

12

1

4

5

9

10

13

Couleurs attribuées

C1

 

C1

C3

C4

C3

C4

 
 

C3

C3

 
 

Couleurs optimisées

C1

 

C3

C3

C1

C3

C1

 
 

C3

C1

 
 
 

D'ou le nombre chromatique est X(G) := 3. Avec : C1:= Couluer grise.

:= Couluer rouge.

C3:= Couluer bleu.

4.1.3 Méthodes de résolution approchée

Bien que de nombreux problèmes de la vie pratique puissent être modélisés sous la formes d'une recherche du nombre chromatique dans un graphe, ce dernier n'a souvent aucune des structures idéales pour lesquelles on peut appliquer des algorithmes polynomiaux. Toutes fois, lorsque la taille du problème est assez petite, il est possible d'utiliser des methodes exactes qui permettent d'obtenir une solution optimale en des temps raisonnables. Pour des graphes de trés grande taille, on doit par contre faire appel à des heuristiques.

Depuis la formulation du problème de la détermination du nombre chromatique dans un graphe, de nombreaux chercheurs ont continuellement proposé de nouvelles heuristiques de coloration. Nous pouvons classer l'ensemble de ces methodes en différentes catégories.

Beaucoup d'heuristiques de coloration de graphes ont été développées parallement à une études théorique: la recherche d'algorithmes exactes pour certaines classes des graphes a parfois fourni des algorithmes performant pour des graphes quelconques. L'algorithme exacte de coloration décrit en haut est ainsi non seulement, connu pour son comportement polynomial et exact, mais il est en plus, considéré comme une heuristique offrant un bon compromis entre la qualité de solution et le temps de calcul.

Nous nous intéressons également à une deuxième catégorie d'heuristiques. Des chercheurs ont developpé des méthodes génerales qui permettent de résoudre de nombreux problémes d'optimisation combinatoire, moyennant quelques définitions propres à chaque probléme. C'est le cas des méthodes génitiques, du récuit simulé ou de la technique Tabou, dont nous allons traiter l'adaptation de la recherche tabou au probléme de la coloration de graphes.

4.1.4 La méthode Tabou adaptée à la coloration des graphes

La technique Tabou est une méthode générale d'optimisation combinatoire qui a été introduite par Glover dans un cadre particulier et développée plus tard dans un contexte plus générale. Indépendament, Hansen a developpé la méthode de SAMD (del'anglais Steepest Ascent Mildest Descent) qui se base sur des idées similaires. La technique Tabou s'est déja montrée trés performante pour un nombre considérable de probléme d'optimisation combinatoire.

En ce qui concerne notre cas, nous donnerons tout d'abord une description générale de la méthode Tabou, puis nous présenterons l'adaptation de cette technique au probléme de la coloration baptisé TABUCOL par M Dominique de Werra (Werra,1993).

La technique Tabou

Le probléme d'optimisation combinatoire qui nous intéresse est le suivant : étant un ensemble X de solutions admissibles et une fonction f définie sur X, il s'agit de déterminer une solution s* 2 X minimisant f sur X.

Definissons un voisinage N(s) pour toute solution s 2 X; Nous utiliserons une technique qui consiste à se déplacer de solution s en solution voisine s' 2 N(s) ,tout en essayant de minimiser la fonction f.

De nombreuses heuristiques ont été développées dans ce même contexte; la plus connue étant certainement la méthode de descante: tant qu'il existe une solution s'voisine de la solution courante s et telle que f(s') < f(s). ,on se déplace de s vers s' qui devient ainsi la nouvelle solution courante. Cette méthode de descente s'arrête donc au premier minimum local rencontré. Le principal inconvénient de cette technique provient alors du fait que la valeur de cet optimum local peut être largement supérieur à celle d'un optimum globale.

Pour cette raison, de nombreuse heuristiques ont été étudiées afin d'éviter le piége que représentent ces minima locaux. Ainsi, par exemple, la methode du R~ecuit Simul~e est conçue de telle maniére qu'il est relativement aisé de sortir d'un optimum locale tant que la température (un paramétre) est assez élevée. Cette température dimine lentement au cours de l'algorithme et lorsqu'elle atteint une valeur assez basse. On se trouve finalement bloqué dans un optimum qu'on espére globale mais qui sera probablement bien meilleur que le premier optimum local rencontré.

Une telle méthode présente un certain nombre d'inconvéniants dont le plus important découle de la manipulation délicate du paramètre qu'est la température : Il est non seulement difficile de donner une valeur initiale à cette température, mais de plus sa décroissance doit être réglée de maniére à donner assez de temps à l'algorithme pour atteindre un optimum globale sans lui en faire perdre trop à des températures élevées car on risque alors de visiter un trop grand nombre de solutions largement moins bonnes que cet optimum global.

Une toute autre méthode générale d'optimisation combinatoire a été proposée par Glover: il s'agit de la technique Tabou que nous noterons TS (de l'anglais Tabu Search). L'une des idées principales constituant cette méthode consiste à choisir à chaque déplacement la meilleure solution voisine s' de la solution courante s.

Tant que l'on ne se trouve pas dans un optimum local, TS se comporte donc comme la méthode de descente et améliore à chaque étape la valeur de la fonction objectif. Lorsque l'on atteint pa r contre un optimum, TS choisit le moins mauvais des voisins, c'est-a-dire celui qui donne un accroissement aussi faible que possible à la fonction objectif.

L'inconvénient que présenterait une méthode basée sur cet unique principe serait que si un minimum local s se trouve au fond d'une vallée profonde, il serait impossible de ressortir de celle-ci en une seule itération, et un déplacement de la solution s vers une solution s' 2 N'(s) avec f(s') > f(s) pourrait provoquer, à l'itération suivante, le déplacement inverse puisque s 2 N(s') et f(s') <f(s); on risquerait donc de cycler autour de ce minimum local.

C'est pour cette raison que TS s'appuie sur un deuxiéme principe qui consiste à garder en mémoire les dernières solutions visitées et à interdire un retour vers celles-ci pour un nombre fixé d'itérations. Le but étant de donner assez de temps à l'algorithme pour lui permettre de sortir de toute vallée contenant un minimum local. En d'autres termes, TS conserve à chaque étape une liste T de solutions "taboues", vers lesquelles il est interdit de se déplacer momentanément.

'

Lors du choix de la meilleure solution sE N(s), il est possible que l'on ait à départager plusieurs candidats donnant certes, une même valeur à la fonction objectif, mais ne nous dirigeons pas tous vers un optimum global. Il est ainsi parfois souhaitable de pouvoir retrourner

vers une solution visitée s, malgré le fait qu'elle fasse parite de la liste T des solutions taboues, ceci afin d'explorer une nouvelle région voisine de s.

Pour cette raison , TS fait intervenir un nouvel ingrédient appelé fonction d'aspiration et définie sur toutes les valeurs de la fonction objectif: lorsqu'une solution s' voisine de la solution s fait parite de T et satisfait de plus notre aspiration {c'est-à-dire f(s') A(f(s))} ,on lève le

'

statut tabou de cette solution set elle devient donc candidate lors de la sélection du meilleur voisin de s.

Il nous faut encore définir une condition d'arrêt. On se donne en général un nombre maximum d'itérations entre deux améliorations de la meilleure solution s* rencontrée.

Dans certains cas, il est possible de déterminer une borne inférieure f* de la fonction objectif et on peut alors stopper la recherche lorsqu'on a atteint une solution s de valeur f(s) proche de f*.

L'algorithme Tabou peut être décrit par l'algorithme suivant :

Organigramme de la méthode de recherche tabou

Tabou adaptée à la coloration de graphe

Nous allons adapter TS à la déremination d'une k - col oration dans un graphe G pour un nombre de couleurs k fixé. L'algorithme ainsi obtenu sera l'ingrédient principal de la méta- heuristique suivante :

k := borne superieure du nombre chromatique XG d'un graphe G; tant que TABUCOL est capable de déterminer une (k -- 1)--coloration dans G faire

k := k -- 1;

On peut représenter une coloration d'un graphe comme une partition de ses sommets en ensembles stables. l'objectif de TABUCOL consiste donc à construire une partition des sommets d'un graphe G = (V, E) en un ensemble k fixé d'ensembles indépendants. Nous avons défini l'espace X des solutions comme étant l'ensemble des partition (V1 , ...., Vn) de V en k sous ensembles non forcément stables.

La fonction objectif f comptabilise le nombre d'arêtes ayant leurs deux extrémités dans une même partie Vi. En d'autres termes f = Eki= 11E(Vi)1 .et cherchons à la minimiser.

Ainsi f(s = (V 1, ....., Vn)) = 0 ssi S est une k -- coloration de G. Nous pouvons donc fixé f = 0 et arrêter la recherche si l'on visite une solution s telle que f (s) = 0.

Une soloution s' = (V,1 , ..., V,n) est considérée comme voisine d'une solution s = (V1, ....., Vn) si on peut l'obtenir à partir de s en ne déplaçant qu'un seul sommet x d'un sous ensemble Vi à un sous ensemble Vj .Ainsi :

Vi, = Vi / {x} ; Vi, = Vi U {x} ; Vr, = Vr pour tout r = 1......k r =6 i, j;

Il serait peu réaliste de considérer une liste T de solutions taboues. En effet, elle demanderait trop de place en mémoire et nous perdrions trop de temps à tester si une solution de V# fait parite de T. Nous avons donc décidé de ne mémoriser qu'une information moins complète. Lorsqu'un sommet x se déplace d'un ensemble Vi à un ensemble Vj, le couple (x, i) devient tabou, ce qui signifie que le sommet x n'est pas autorisé à revenir dans l'ensemble Vi pour un nombre 1T1 d'itérations. La taille 1T1 = 7 s'est expérimentalement avérée satisfaisante.

Il est parfois souhaitable de lever un tel statut tabou, surtout lorsque le retour de x dans Vi donne une solution s n'ayant encore jamais été visitée et de petite valeur f(s). Nous avons définit la fonction d'aspiration comme étant égale à la valeur f (s*) de la meilleure solution s* rencontrée. Considérons donc une solution s, de V* obtenue à partir de la solution courante s en déplaçant un sommet x dans une partie Vi, et suposons que (x, i) E T; si f (s,) < f (s*), Nous levons le statut tabou de s' qui devient ainsi candidat pour le choix de la meilleure solution dans V*.

Le principal critère d'arrêt de la méthode Tabou est la découverte d'une solution s avec f (s) = 0, c'est-à-dire d'une k -- coloration. On peut alors diminuer la valeur de k d'une unité et appliquer à nouveau la méthode Tabou, afin de tenter d'obtenir une meilleure borne supérieure sur le nombre chromatique. Mais ce critère d'arrêt ne permet pas d'assurer que l'algorithme s'arrête; en particulier si k < XG, il n'est pas suffisant. Il faut donc introduire un ou plusieurs autres critères d'arrêt pour interrompre la recherche. Les plus fréquents sont :

· un nombre fixé d'itérations à été effectué.

· il n'y a plus eu d'amélioration de s* depuis un nombre fixé d'itérations.

· le temps de calcul a atteint une limite fixée.

Nous obtenons ainsi la méthode Tabou pour le problème de la k - coloration décrit ci- dessous. Notons qu'afin d'accélerer un peu l'aglorithme, la génération de M peut

être interrompue dés que S avec f(s') < f(s) a été trouvé.

Algorithme Tabou; begin

choisir une solution initiales ;

S*:=S;T=ø;

while aucun critère d'arrêt n'est satisfait do

générer M avec M solutions S = (X1, ..., X,) E N(s)

telles que x E= X pour toute paire (x, i) dans T

ou f(s) <f(s*) ;

- dés qu'un S avec f(s') <f(s) est trouvé

- arrêter la génération

S := meilleure solution dans M;

mettre 'a jour T ;

if f(s) < f(s*) then S* := S ;

end while;

end algorithme:

4.2 Conclusion

Dans ce chapitre, deux méthodes de résolutions ont été présentées; l'une dite exacte et l'autre appellé méthode Tabou. Ces deux méthodes seront utilisées pour résoudre notre problématique. A l'issue nous pourrons déterminer les avantages et les inconvéniants de chacune d'elles.

CHAPITRE 5

Présentation du logiciel

5.1 Introduction

Lors de la réalisation de cette étude, nous avons été amenés à concevoir un logiciel dans le but d'appliquer les méthodes de résolution au problème posé. En effet il serait déraisonnable d'essayer de trouver une solution au problème sans l'aide d'une machine, étant donné la complexité du problème et la méthode utilisée.

Avant de procéder à la présentation du logiciel, une description de l'environnement de programmation utilisé s'avère nécessaire; Nous notons aussi que nous avons utilisé l'outil de programmation Delphi7.

5.2 Qu'est-ce que Delphi?

Delphi est un langage de programmation inspiré de Pascal, fondé sur les notions d'événements et d'objets. Il permet de créer simplement de belles interfaces graphiques tout en disposant d'un puissant langage de programmation.

Delphi fournit tous les outils qui sont nécessaires pour développer, tester déboguer et déployer des applications incluant une importante bibliothèque de composants réutilisables, un ensemble d'outils de conception, des modèles d'application et de fiches, ainsi que des experts de programmation. Ces outils simplifient le prototype et réduisent la durée de développement.

L'un des principaux objectifs de son utilisation est de permettre la construction d'un logiciel ayant le maximum de qualité : la fiabilité, la convivialité et surtout l'efficacité, et ceci explique notre choix pour Delphi version 7.0 pour créer notre application.

Cette rapidité et cette simplicité de développement sont dues à une conception visuelle de l'application. Delphi propose un ensemble très complet de composants visuels prêts à l'emploi incluant la quasi-totalité des composants Windows (boutons, boîtes de dialogue, menus, barres d'outils. . . ) ainsi que des experts permettant de créer facilement divers types d'applications et de librairies.

5.3 Présentation du logiciel

Ce logiciel, qui a été concu par nous, en utilisant le langage Delphi, se présente comme suit :

Un interface dans lequel on trouve respectivement :

- La commande "Sommet (cellule) ".

- La commande" Adjacence sommet (cellule) ". - La commande "traitement ".

- Et enfin, la commande "Quiter ".

La commande "Sommet (cellule)", nous permet d'introduire tout les sommets du graphe comme indiqué ci-aprés.

Pour introduire un sommet (cellule), il faut au préalable appuyer sur la commande "ajouter" puis, ecrire le libellé du sommet. Aprés, soit on valide soit on annule.

Nous avons également la possibilité de proceder à des suppréssions ou modifications. Pour conclure, nous utilisons la commande "fermer".

En ce qui concerne, la commande "sommets adjacent", elle nous permet, pour chaque sommet d'introduire ses sommets adjacents, en appuyant sur la touche "initialiser"; Par cet action, nous allons avoir tous les sommets du graphe saisis qui apparaissent sur la fenêtre du dessous: nous sélectionnons ainsi, les sommets adjacents correspondants en éliminant ceux qui ne le sont pas.

En fermant cette fenêtre par la touche "fermer", nous retournons à la page principale.

La commande "Traitement" permet d'avoir un tableau dans lequel seront indiqués les sommets du graphes ordonnés par ordre décroissant, leur degrés correspondant ainsi que les colorations.

En appuyant sur la touche "color sommet (affectation de fréquence)", on obtient la coloration associée au sommet du graphe qui s'affiche dans la partie resultat.

Le nombre maximum de couleurs utilisées, est indiqué en bas de la fenêtre.

La commande "Recoloriage sommet" permet de recolorer à nouveau les sommets avec un nombre de couleurs optimisées. Le nombre chromatique du graphe s'affiche en bas de la fenêtre.

La commande "Méthode Tabou" permet de résoudre le problème par la deuxième approche. En appuyant sur cette commande, on aura la fenêtre ci-dessus.

En introduisant de nouveau, le nombre de sommets, le nombre d'arets, la borne superieure de couleur et le nombre maximum d'itérations et on appuyant sur la touche "ouvrir graphe", on aura la liste des sommets adjacents.

La commande "K-coloriage" permet de lancer l'algorithme et affiche le déroulement des opérations jusqu'a aboutir à la solutions optimale.

Conclusion générale

Pour une gestion rationnelle du spectre de fréquence par des méthodes propre à la recherche opérationnelle, nous avons étudié procédé à son étude en utilisant deux approches :une méthode exacte et la méthode Tabou.

Après avoir optimisé les paramètres de chaque méthode de recherche, nous avons testé les deux méthodes selon les mêmes contraintes à notre modèle de réseau pour la recherche d'un plan de gestion de fréquence.

Un logiciel adapté a ces méthodes, a été conçu à cet effet.

Les résultats obtenus ont été très satisfaisants notamment celles obtenues par la méthode dite Méta Heuristiques.

Si actuellement, Algérie Télécom arrive uniquement à utilisé 6 fréquences, la méthode proposée et testée peut allé jusqu'à 3 fréquences.

A l'issue de ce travail, avec cette expérience acquise en contact des techniciens d'Algérie Télécom, nous pensons que celui-ci sera d'un apport certain pour l'amélioration de la gestion du spectre de fréquence en Algérie.

Notre veux est que ce travail puisse être améliorer afin qu'il soit concrétisé par les services concernés.

Bibliographie

A. Caminada" Résolution du problème de l'affectation des fréquences par programmation par contraintes" Rapport technique, CNET, Belfort, 1995.

A. Akrout "Problèmes d'Affectation de Fréquences: Méthodes Basées sur le Recuit Simulé Rapport technique, CNET, Paris; 1994

C. Berge, Graphes, Gauthier-Villars, Paris ; 1983.

D. de Werra et Y. Gay, Chromatic scheduling and frequency assignment, Discrete Applied Mathematics; 1994.

D. de Werra et A. Hertz, Consecutive colorings of graphs, Zeischrift fur Operations Research 32, 1988, 1-8.

D. de Werra et D. Kobler, Coloration et ordonnencement chromatique, ORWP 00/04, Ecole Polytechnique Fédérale de Lausanne; 2000.

De Werra D., Hertz A. -Tabu Search Techniques: A tutorial and an application to neural networks - OR Spektrum, 1989, pp. 131-141.

D. Brélaz "New Methods to Color Vertices of Graph" Communications of ACM, N°22,1979, pp 251-256.

F. Glover et M. Laguna, Tabu Search. Kluwer Academic Publ; 1997.

J. Hao, R. Dorne, P. Galinier "Tabu Search for Frequency Assignment in Mobile Radio Networks" Journal of heuristics, N° 4, 1998, pp 47-62.

Intel Technical White Paper, « Understanding Wimaw and 3G for Portable/Mobile Broadband Wireless », 2004.

IEEE Std 802.16-2004, "IEEE Standard for Local and metropolitan area networks Part 16: Air Interface for Fixed Broadband Wireless Access Systems", 2004.

M.G. Garey et D.S. Johnson, The complexity of near-optimal graph coloring. J. ACM 23,1976, 43-49.

N. Dubois et D. de Werra, EPCOT : An Efficient Procedure for Coloring Optimally with Tabu Search. Comput. Math. Appl. 25,1993, 35-45.

N. Alon et M. Tarsi, Colorings and orientations of graphs. Combinatorica 12 (1992) 125-

134.

P. Hansen, A. Hertz et J. Kuplinsky, Bounded Vertex Colorings of Graphs. Discrete Math. 111,1993, 305-312.

R. Borndorfer, A. Eisenblatter, M. Grotschel, A. Martin "Frequency Assignment in Cellular Phone Networks" ZIB-Repport 97-35,1997.

R. Dorne, J. Hao "Tabu Search for Graph Coloring, T-coloring and Set T-coloring" Metaheuristics: advances and trends in local search paradigms for optimization, 1998, (Chapitre 6, Kluwer academic publishers, pp 77-92.)

R. Dorne "Etude des Méthodes Heuristiques pour la Coloration, la T-Coloration et l'Affectation de Fréquences" Thèse de doctorat, Université de Montpellier II, 1998.

Hertz A., de Werra D. -Using Tabu Search Techniques for Graph Coloring - Computing 39, 1987, pp. 345-351.

Joham Dréo, Alain Pétrowski, Patrick Siarry, Eric Taillard, « Métaheuristiques pour l'optimisation difficile », Edition EYROLLES, France, Juillet 2003.

Hakim Mabed, « Modèles et techniques d'optimisation dynamique pour les réseaux radiomobiles » : Thèse de doctorat, Ecole doctorale d'Angers, 2003.

Hakim Mabed, « Optimisation dynamique: Application au fréquençage », Séminaire du laboratoire systeme et transpore (SeT), 2004.

V. H. Mac Donald "Advanced Mobile Phone Service: The cellular Concept" The Bell System Technical Journal, 1979, pp 15-41.

Wimax Forum White Paper, "Wimax End-to-End Network Systems Architecture", 2006.

Wimax Forum White Paper: "Wimax's technology for LOS and NLOS environments",

2004.

Wimax Forum White Paper, "Wimax End-to-End Network Systems Architecture", 2006.

Annexe 1

Solution donnée par l'Algorithme exacte de coloration

N° de la cellule

Antenne principale

Fréquence attribuée

Cellule 1

A

La 2~eme fréquence

Cellule 2

C

La 3~eme fréquence

Cellule 3

C

La 1~erefréquence

Cellule 4

P

La 2~eme fréquence

Cellule 5

A

La 3~eme fréquence

Cellule 6

A

La 1~erefréquence

Cellule 7

D

La 2~eme fréquence

Cellule 8

G

La 3~eme fréquence

Cellule 9

P

La 3~eme fréquence

Cellule 10

Q

La 1~erefréquence

Cellule 11

R

La 2~eme fréquence

Cellule 12

B

La 1~erefréquence

Cellule 13

E

La 2~eme fréquence

Cellule 14

D

La 3~eme fréquence

Cellule 15

G

La 1~eme fréquence

Cellule 16

K

La 2~erefréquence

Cellule 17

M

La 3~eme fréquence

Cellule 18

M

La 1~erefréquence

Cellule 19

Q

La 2~eme fréquence

Cellule 20

Q

La 3~eme fréquence

Cellule 21

R

La 1~eme fréquence

Cellule 22

B

La 2~eme fréquence

Cellule 23

F

La 3~eme fréquence

Cellule 24

E

La 1~erefréquence

Cellule 25

H

La 2~eme fréquence

Cellule 26

H

La 3~eme fréquence

Cellule 27

K

La 1~erefréquence

Cellule 28

N

La 2~eme fréquence

Cellule 29

N

La 3~eme fréquence

N° de la cellule

Antenne principale

Fréquence attribuée

Cellule 30

F

La 1~eme fréquence

Cellule 31

F

La 2~eme fréquence

Cellule 32

I

La 3~erefréquence

Cellule 33

I

La 1~erefréquence

Cellule 34

L

La 2~eme fréquence

Cellule 35

O

La 3~eme fréquence

Cellule 36

O

La 1~erefréquence

Cellule 37

J

La 3~eme fréquence

Cellule 38

J

La 1~erefréquence

Cellule 39

I

La 2~eme fréquence

Cellule 40

L

La 3~erefréquence

Cellule 41

L

La 1~erefréquence

Annexe 2

Rappel sur la théorie des graphes

Introduction

La théorie des graphes est utilisée dans un grand nombre de disciplines (mathématiques, physique, économie, etc.). Les recherches en théorie des graphes sont essentiellement menées par des informaticiens, du fait de l'importance des aspects algorithmiques (recherche de solutions). Il s'agit essentiellement de modéliser des problèmes :

· on exprime un problème donné en termes de graphes;

· il devient alors un problème de « théorie des graphes » que l'on sait le plus souvent résoudre car il rentre dans une catégorie de problèmes connus.

Les solutions de problèmes de graphes peuvent être :

· faciles et efficaces (car le temps nécessaire pour les traiter par informatique est raisonnable car il dépend polynomialement du nombre de sommets du graphe) ;

· difficiles (car le temps de traitement est exponentiel) ; dans ce cas on utilisera une heuristique, c'est-à-dire un processus de recherche d'une solution - pas forcément la meilleure.

Qu'est-ce qu'un graphe?

Définition 1

On appelle graphe G = (X; A) la donn ee d'un ensemble X dont les el ements sont appelés sommets et d'une partie de A symétrique((x; y) E A (y; x) E A) dont les éléments sont appelés arêtes.

En présence d'une arête a = (x; y) qui peut être notée simplement xy, on dit que x et y sont les extrémités de a, que a est incidente en x et en y, et que y est un successeur ou voisin de x (et vice versa).

On dit qu'un graphe est sans boucle si A ne contient pas d'arête de la forme (x; x), c'esta-dire joignant un sommet a lui-même.

Le nombre de sommets est appelé ordre du graphe.

Un graphe ne possédant pas de boucle ni d'arêtes parallèles (deux arêtes distinctes joignant la même paire de sommets) est appelé graphe simple ou 1-graphe. En revanche un p-graphe ou graphe généralisé est un graphe pour lequel il n'existe jamais plus de p arêtes de la forme (x;x).

Graphiquement, les sommets peuvent être représentés par des points et l'arête a = (x; y) par un trait reliant x à y. On notera que la disposition des points et la longueur ou la forme (rectiligne ou incurvée) des traits n'a aucune importance. Seule l'incidence des différentes arêtes et sommets compte.

Définition 2

On appelle graphe orienté ou digraphe G = (X; A) la donnée d'un ensemble X dont les éléments
sont appelés sommets et d'une partie A de X x X dont les éléments sont appelés arcs ou arêtes.

En présence d'un arc a = (x; y) qui peut être noté simplement xy, on dit que x est l'origine (ou extrémité initiale) et y l'extrémité (terminale) de a, que a est sortant en x et incident en y, et que y est un successeur de x tandis que x est un prédécesseur de y. On dit aussi que x et y sont adjacents.

Définition 3

Un graphe non orienté n'est qu'un graphe orienté symétrique ; si un arc relie le sommet a au sommet b, un autre arc relie le sommet b au sommet a : on ne trace alors qu'un trait entre a et b que l'on appelle une « arête ».

Degré d'un graphe

On appelle degré sortant ou demi-degré extérieur d'un sommet x le nombre d'arcs de la forme a = (x; y) avec y =6 x, c'est- a-dire le nombre d'éléments de ['(x)\ {x} ( ['(x) l'ensemble des successeurs d'un sommet x E X).

On note d5(x)ce degré.

On appelle degré entrant ou demi-degré intérieur d'un sommet x le nombre d'arcs de la forme a = (y; x) avec y =6 x, c'est- a-dire le nombre d'éléments de ['~1(x)\ {x} (['~1(x) l'ensemble des prédécesseurs d'un sommet x E X).

On note de(x) ce degré.

On appelle degré de x (ou valence) la somme du degré entrant et du degré sortant.

Un sommet de degré entrant non nul et de degré sortant nul est appelé puits, tandis qu'un sommet de degré entrant nul et de degré sortant non nul est appelé source.

Un sommet n'ayant pas d'arcs incidents est appelé sommet isolé ; ces sommets ont un degré nul. Deux arcs adjacents sont dits "en série" si leur sommet commun est de degré egal à deux. Dans la définition d'un graphe, l'ensemble des arcs A peut être vide; dans ce cas, on a affaire à un graphe nul. Tous les sommets d'un graphe nul sont donc des sommets isolés. En revanche, l'ensemble des sommets X ne peut être vide sinon le graphe correspondant n'existe pas. Cela signifie donc qu'un graphe comporte au moins un sommet.

Matrice d'adjacence

Considérons un graphe G = (X; A) comportant n sommets. La matrice d'adjacence de G est égale à la matrice U = (uij) de dimension n x n telle que

~ 1 si (i; j) E A (c'est-a-dire (i; j) est une arête)

uij = 0 sinon

Une telle matrice, ne contenant que des "0" et des "1" est appel ee, de manière générale, une matrice booléenne.

Un graphe orienté quelconque à une matrice d'adjacence quelconque, alors qu'un graphe non orienté possède une matrice d'adjacence symétrique. L'absence de boucle se traduit par une diagonale nulle.

La matrice d'adjacence poss ede quelques propri et es qui peuvent être exploitées. Considérons un graphe G et sa matrice d'adjacence associée U :

· la somme des eléments de la i~eme ligne de U est égale au degré sortant d5(xi) du sommet xi de G.

· la somme des eléments de la j~eme colonne de U est égale au degré entrant de(xj) du sommet xj de G.

· U est symétrique si, et seulement si, le graphe G est symétrique.

Définition d'un stable:

Un sous ensemble de sommetsI C X d'un graphe G = (X, A) est un stable s'il ne comprend que des sommets non adjacents deux à deux:

ViE I,Vj E I - (i,j) E= A.

Coloriage des sommets d'un graphe

Définitions

La coloration des sommets d'un graphe consiste à affecter à tous les sommets de ce graphe une couleur de telle sorte que deux sommets adjacents ne portent pas la même couleur. Une coloration avec k couleurs est donc une partition de l'ensemble des sommets en k parties stables. Le nombre chromatique, noté x(G); du graphe G est le plus petit entier k pour lequel il existe une partition de X en k sous-ensembles stables.

Encadrement du nombre chromatique

Majoration x (G) < A (X) + 1, où A (X) est le plus grand degré de ses sommets.

Minoration Le nombre chromatique d'un graphe est supérieur ou égal à celui de chacun de

ses sous graphes.

Le nombre chromatique du graphe sera supérieur ou égal à l'ordre de sa plus grande clique

x(G) ~ w(G).

Acronymes

ADSL: Asymetric Digital Subscriber Line.

BS : Base Station.

BTS: Base Transceiver Station. CPE: Customer Premise Equipement.

DSL: Digital Subscriber Line.

EDGE: Enhanced Data Rates for GSM Evolution.

FAP: Frequency Assignement Problem.

IEEE: Institute of Electrical and Electronics Engineer.

IP: Internet Protocol.

LOS: Line Of Sight.

NLOS: Non Line Of Sight.

OFDM: Orthogonal Frequency Division Multiplexing.

OFDMA: Orthogonal Frequency Division Multiple Access. QoS: Qualiy of Service.

UMTS: Universal Mobile Telecomunication System.

WiFi: Wirless Fidelity.

Wimax: Worldwide Interoperability for Microwave Acces.

Soutenons La Quadrature du Net !





Soutenons La Quadrature du Net !