Méthodologies pour la planification de réseaux locaux sans-fil. Katia Runser



Yüklə 503 b.
tarix28.10.2017
ölçüsü503 b.


Méthodologies pour la planification de réseaux locaux sans-fil.

  • Katia Runser

  • Laboratoire CITI - INSA de Lyon

  • Projet ARES – INRIA

  • Directeurs de thèse :

  • Jean-Marie Gorce, MdC., INSA de Lyon

  • Stéphane Ubéda, Pr., INSA de Lyon


Plan

  • Introduction

    • 1.1. Le problème de planification wLAN
  • Prédiction de couverture radio

    • 2.1. Méthode de prédiction Multi-Résolution FDPF adaptative
    • 2.2. Adaptation à la planification wLAN.
  • Stratégies de planification wLAN

    • 3.1. Modélisation du problème
    • 3.2. Heuristiques de planification
  • Conclusions et perspectives



1.1. Le problème wLP (wLAN Planning)

  • Réseaux locaux sans-fil (wLAN) en mode infrastructure.



1.1. Le problème wLP (wLAN Planning)

  • Configuration des AP

  • Le nombre N

  • Pour chaque AP k :

    • La position pk=(x, y, z),
    • La puissance d’émission PkE,
    • Le type d’antenne tk,
    • La direction d’émission k,


1.1. Nos objectifs

  • Proposer une stratégie de planification automatique qui soit :

    • Réaliste,
    • Réalisable en un temps acceptable.
  • Pour cela, il nous faut :

    • Un modèle de prédiction de couverture radio efficace et précis,
    • Une modélisation réaliste du réseau,
    • Une heuristique d’optimisation efficace.


Plan

  • Introduction

    • 1.1. Le problème de planification wLAN
  • Prédiction de couverture radio

    • 2.1. Méthode de prédiction Multi-Résolution FDPF
    • 2.2. Adaptation à la planification wLAN.
  • Stratégies de planification wLAN

    • 3.1. Modélisation du problème
    • 3.2. Heuristiques de planification Conclusions
  • Conclusions et perspectives



2.1. Prédiction de couverture radio

  • Modèles existants :

    • Empiriques (COST 231)
      • Rapides mais peu précis (EQM ~10dB)
    • Déterministes (Lancer de rayon)
      • Compromis précision / temps de calcul
      • Prédictions en 3D natives
    • Discrets (modèles FDTD)
      • Lents mais très précis


2.1. Fourier Domain ParFlow

  • Gorce et Ubéda. [2001, IEEE VTC]

  • Time Domain ParFlow O(N3)

    • modèle discret de résolution dr.
  • Domaine fréquentiel :

    • prédictions de l’état stationnaire à la fréquence
  • Un grand système linéaire à résoudre.

  • Comment ?

    • Inversion directe : Non abordable pour de grands environnements O(N6)
    • Résolution itérative : O(N3)


2.1. Le concept Multi-Resolution



2.1. Le concept Multi-Resolution

  • Un MR-Bloc :

    • Surface : Rectangle de NX . NY pixels
    • Un jeu de flux entrant
    • Un jeu de flux sortant
    • Une matrice de propagation A
  • Si NX = NY = 1 pixel

    • Pixel du modèle ParFlow


2.1. Le concept Multi-Resolution

  • Un MR-bloc :

  • Peut être fusionné à un autre MR-bloc :

    • Où A est calculé à partir de B et C


2.1. Le concept Multi-Resolution

  • Phase de prétraitement

  • Calcul des N

    • A partir des pixels ParFlow
  • Pyramide des MR-blocs :

    • N pour chaque MR-bloc
  • Complexité en O(N3)

  • Indépendant de la position de la source



2.1. Le concept Multi-Resolution

  • Phase de propagation :

  • Si B est une source, on calcule la source A en fusionnant B et C

  • Calcul et sauvegarde des flux internes à A



2.1. Le concept Multi-Resolution

  • Phase de propagation :

  • Agrégation montante des MR-blocs.



2.1. Le concept Multi-Resolution

  • Phase de propagation :

  • Décomposition d’un MR-bloc

  • Calcul des flux entrant sur B et C à partir :

    • des flux internes,
    • de B et C


2.1. Le concept Multi-Resolution

  • Phase de propagation :

  • Agrégation montante des MR-blocs.

  • Décomposition descendante vers les blocs voulus.

  • Complexité en O(N² log2(N))



2.1. Couverture à 2.4 GHz

  • Contrainte : dr <<  → dr ~ 2cm à 2.4 GHz

  • Pour un étage de 92.6 x 23 m, on obtient :

    • Un environnement de 4630 x 1150 pixels
    • 53 min. de prétraitement
    • 18 s. de propagation à 2cm.


Plan

  • Introduction

    • 1.1. Le problème de planification wLAN
  • Prédiction de couverture radio

    • 2.1. Méthode de prédiction Multi-Résolution FDPF
    • 2.2. Adaptation à la planification wLAN.
  • Stratégies de planification wLAN

    • 3.1. Modélisation du problème
    • 3.2. Heuristiques de planification
  • Conclusions et perspectives



2.2. Adaptation au WLAN

  • Pour réduire le temps de calcul :

  • Modification de la résolution dr,

  • Structure ‘adaptative’ de la pyramide MR-FDPF,

  • Calibration du modèle.



2.2. Modification du pas dr

  • Augmentation de dr

      • Complexité ~(1/dr)2
      • Couverture à 2 cm inutile -> Précision voulue P ~ 1 m
      • Puissance moyenne sur 1m² réaliste, on impose
      • P ≥ simdr sim /6 ≤ P / 6
        • i.e. si P ~ 1 m alors dr=10cm
  • La fréquence de simulation fsim

      • Multiple de la fréquence réelle
      • P ≥ sim  fsim ≥ c0/P ; fsim = 480MHz


1.2 MR-FDPF Adaptatif

  • Création des MR-blocs de la pyramide

  • Blocs Homogènes Bh :

    • Les premiers blocs homogènes en matériau obtenus lors de la propagation descendante.
  • Bh sont grands :

    • Calcul rapide des couvertures à cette résolution


2.2. MR-FDPF Adaptatif

  • Heuristique de découpage du plan :

    • Selon la plus grande discontinuité
    • Compromis entre :
      • La taille des blocs homogènes,
      • La durée du prétraitement,
      • La taille de la pyramide en mémoire.


2.2. MR-FDPF Adaptatif

  • Heuristique de découpage du plan :

    • Selon la plus grande discontinuité
    • Compromis entre :
      • La taille des blocs homogènes,
      • La durée du prétraitement,
      • La taille de la pyramide en mémoire.




2.2. Calibration des simulations

  • Réduire les erreurs de prédictions :

    • Calibration rapide,
    • Calibration fine.
  • A partir de :

      • Mesures :
      • Prédictions MR-FDPF :
  • Calibration rapide :

    • Offset de mise à l’échelle :


2.2. Calibration des simulations

  • Calibration fine

    • Relaxer les paramètres de propagation des N matériaux du plan :
      • Indices de propagation n = (n1, .., nN
      • Coefficients d’affaiblissement m
  • Minimisation de l’erreur quadratique moyenne (EQM) :



2.2. Calibration automatique

  • Calibration fine :

    • 1 Evaluation d’EQM : 1 minute,
    • Calcul prétraitement + couverture.
  • DIRECT : Dividing RECTangle

    • Algorithme de recherche directe à motifs. [Jones et al., 1993]
    • Fonctions continues à plusieurs variables.
    • Recherche globale et locale.


2.2. Jeu de mesures

  • Bâtiment :

    • 30 x 80 mètres, 3 matériaux
  • Mesures :

    • 6 APs – IEEE 802.11b, 2.4 GHz
    • 199 points de mesure par AP
    • 300 échantillons par point


2.2. Résultats de calibration

  • Modélisation à 1 et 2 matériaux

    • Recherche exhaustive
    • Facteurs d’atténuation :
      •  = 1.0 pour chaque matériau → murs fins / dr
  • Modélisation à 3 matériaux

    • Calibration automatique (DIRECT)
    • Indices de réfraction :
    • EQM : Q = 5.3 dB


2.2. Validation des simulations

  • Environnements :

    • CITI2:
      • 40 mesures
      • 3 AP
    • Building G:
      • 15 mesures
      • 1 AP


2.2. Bilan

  • Modèle de prédiction adapté à la planification wLAN :

    • Réduction du temps de
      • Prétraitement de 53 minutes à 18 secondes
      • Propagation de 18 secondes à 0.5 seconde
  • Bonne précision avec 5 à 6 dB d’EQM

    • Phase de calibration basée sur des mesures réelles.


Plan

  • Introduction

    • 1.1. Le problème de planification wLAN
  • Prédiction de couverture radio

    • 2.1. Méthode de prédiction Multi-Résolution FDPF adaptative
    • 2.2. Adaptation à la planification wLAN.
  • Stratégies de planification wLAN

    • 3.1. Modélisation du problème
    • 3.2. Heuristiques de planification
  • Conclusions et perspectives



3.1. Modélisation : variables

  • Formulation discrète :

    • M positions candidates des AP
    • Puissance P et direction ψ d’émission discrets
    • Une solution :
  • Choix des positions :

    • Utilisation du découpage adaptatif de la méthode MR-FDPF,
    • Un AP candidat au centre des blocs homogènes.


3.1. Modélisation : variables



3.1. Modélisation : couvertures

  • Cartes de couverture :

    • Liste des blocs homogènes à couvrir
    • { Bl, l  [1..Nc] }
    • Flk : Puissance reçue au bloc Bl de l’AP k
    • FlBS : Puissance du signal le plus fort (‘Best Server’) au bloc Bl


3.1. Modélisation : critères

  • Forme générique des critères définis :

  • Avec :

    • fmesl la fonction de mesure associée au bloc Bl.
    • l = Al / Atot le pourcentage de la surface totale du bloc Bl


3.1. Modélisation : critères

  • Critères d’optimisation :

    • Couverture
      • Couverture homogène
      • Couverture à seuil progressif
    • Interférences
      • Minimise le recouvrement entre cellules
    • Débit
      • Garantit un débit minimal
    • Localisation :
      • améliore les performances d’un service de localisation


3.1. Modélisation : critères

  • Couverture à seuil progressif fslope:

    • Pénalise les blocs mal couverts
      • fmesl : s’applique à FlBS
      • Sm = Seuil à 1Mbps
      • SM = Seuil à 11Mbps / 54 Mbps


3.1. Modélisation : critères

  • Critère d’interférences finterf.

    • Minimiser le recouvrement entre les zones de service
    • Répartition des signaux reçus au bloc Bl [thèse Jedidi 04]:
      • h signaux utiles,
      • les signaux interférents supérieurs au seuil de bruit Sm
    • Pénaliser les blocs où l’interférent le plus fort est plus puissant que le bruit en réception.
  • A utiliser avec un critère de couverture : N optimal.



3.1. Modélisation : critères

  • Critère de débit

    • fmes pénalise un bloc si le débit fournit est inférieur à un débit minimal ds
    • Estimation du trafic d’un AP:
      • Evaluation des performances de la couche MAC 802.11 : modèle de Lu et Valois (2005)
      • Débit réel dul d’un utilisateur de la zone de service à R Mbits/s (R = 1,2,... 11 Mbits/s)
      • Distribution uniforme des utilisateurs.
  • A utiliser avec un critère d’interférences + couverture



Plan

  • Introduction

    • 1.1. Le problème de planification wLAN
  • Prédiction de couverture radio

    • 2.1. Méthode de prédiction Multi-Résolution FDPF
    • 2.2. Adaptation pour la planification wLAN.
  • Stratégies de planification wLAN

    • 3.1. Modélisation du problème : variables et critères
    • 3.2. Heuristiques de planification
  • Résultats et perspectives



3.2. Heuristiques

  • Problème wLP : problème Multicritère.



3.2. Approche mono-objectif

  • Critère agrégé :

  • Choix des coefficients i avant le lancement de la recherche.

  • Ajout d’une contrainte de couverture



3.2. Approche mono-objectif

  • Métaheuristique tabou [Glover, 86]:

    • Recherche locale qui accepte la dégradation de la solution courante Sc
    • Liste tabou : Historique des mouvements -> Evite le bouclage
  • Implantation

    • Taille dynamique de la liste tabou,
    • Pas de critère d’aspiration.


3.2. Approche mono-objectif

  • Exemple d’optimisation :

    • variables :
      • position, nombre d’AP N
      • environnement Foch : 258 candidats


3.2. Approche mono-objectif



3.2. Approche mono-objectif

  • Temps de traitement

    • 258 cartes de couverture
      • # 4 minutes
    • Recherche tabou :
      • 1 itération : 1.5 s
      • 715 itérations en moyenne
      • # 18 minutes


3.2. Approche multicritère

  • Recherche de plusieurs solutions

  • Surface de compromis

  • Dominance au sens de Pareto :

    • x domine y si :
  • Front de Pareto Optimal FPT

  • Front de Pareto Pratique FPP



3.2. Approche multicritère

  • Heuristique tabou multicritère :

    • Front de recherche Fc : K solutions courantes,
    • K recherches tabou en parallèle,
    • 1 liste tabou par solution,
    • Obtention d’un Front de Pareto Pratique


3.2. Approche multicritère



3.2. Approche multicritère



3.2. Approche multicritère

  • Convergence de FPP vers FPT.

    • Critères : fslope et finterf (h=0)
    • Variables : positions
    • 129 positions candidates, N = 3 AP
    • 18 solutions non dominées


3.2. Approche multicritère

  • Optimisation de 3 critères :

    • fslope, finterf (h=2), fdébit (ds = 256k, 200 nœuds),
    • Rmax = 2 et K = 15,
    • Front optimal pratique : 1202 solutions
  • Sélection de q solutions dans le Front de Pareto pratique :

    • Critère de niche :


3.2. Approche multicritère



Plan

  • Introduction

    • 1.1. Le problème de planification wLAN
  • Prédiction de couverture radio

    • 2.1. Méthode de prédiction Multi-Résolution FDPF
    • 2.2. Adaptation à la planification wLAN.
  • Stratégies de planification wLAN

    • 3.1. Modélisation du problème
    • 3.2. Heuristiques de planification
  • Conclusions et perspectives



4. Conclusions

  • Prédiction de couverture radio pour le wLAN :

    • Mise en œuvre du modèle MR-FDPF dédié au problème wLP :
      • Modélisation complète des phénomènes de propagation.
      • Temps de calcul faible (t < 1s).
    • Un processus de calibration automatique a été proposé.
    • Les performances du modèle ont été validées par des mesures.


4. Conclusions

  • Stratégies de planification :

    • Formulation discrète avec prise en compte la géométrie du bâtiment.
    • Modélisation de plusieurs objectifs de planification.
    • Proposition de deux heuristiques de résolution
      • Monocritère tabou : rapide mais délicate à paramétrer.
      • Multicritère tabou : propose un éventail de solutions réalisables mais plus longue.


4. Perspectives

  • Prédiction de couverture radio

    • Validation pour d’autres environnements
    • Amélioration de la calibration automatique
    • Passage au 3D
  • Stratégies de planification

    • Validation expérimentale des critères
    • Modification ‘à la volée’ des i de la recherche monocritère
    • Amélioration du temps de traitement de la recherche multicritères


4. Perspectives

  • Gestion dynamique du réseau :

    • Adaptation des paramètres (puissance, fréquence)
    • Ajout / suppression d’AP
  • Les stratégies multicritères :

    • wLAN
    • Ad hoc / réseaux de capteurs :
      • Plusieurs configurations des nœuds maîtres dans les réseaux de capteurs (maximisation de la durée de vie du réseau).


Publications

  • Conférences Internationales.

  • [1] G. De La Roche, R. Rebeyrotte, K. Runser and J.-M. Gorce, "A new strategy for indoor propagation fast computation with MR-FDPF algorithm." in IEEE IASTED (ARP), Banff, Alberta, Canada, July 2005.

  • [2] J.-M. Gorce and K. Runser, "Assessment of a frequency domain TLM like approach for 2D simulation of Indoor propagation." in IEEE IMACS, Paris, France, July 2005.

  • [3] K. Runser and J.-M. Gorce, "Assessment of a new indoor propagation prediction model based on a multi-resolution algorithm" in Proceedings of the IEEE VTC Spring 2005, Stockholm, Sweden, May 2005.

  • [4] K. Runser, E. Jullo and J.-M. Gorce, "Wireless LAN planning using the multi-resolution FDPF propagation model" in Proceedings of IEE ICAP, Exeter, UK, Vol. I, pp.80-83, April 2003.

  • [5] J.-M. Gorce, E. Jullo and K. Runser, "An adaptative multi-resolution algorithm for 2D simulations of indoor propagation" in Proceedings of IEE ICAP, Exeter, UK, Vol. I, pp.216-219, April 2003. Best paper award on Propagation.

  • Conférences Nationales.

  • [6] G. De La Roche, R. Rebeyrotte, K. Runser and J.-M. Gorce, "Prédiction de couverture radio pour les réseaux locaux sans-fil par une approche 2D multi-résolution." in Actes des 14èmes journées nationales micro-ondes, Mai 2005.

  • [7] K.Runser, P.Buhr, G. De La Roche and J.-M. Gorce, "Validation de la méthode de prédiction de couverture radio MR-FDPF" in Actes des 6e Rencontres Francophones AlgoTel 2004, Batz sur Mer, France, pp. 21-26, Mai 2004.

  • [8]K. Runser, S. Ubeda and J.-M. Gorce, "Optimisation de réseaux locaux sans fils" in 5e congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Avignon, France, pp. 205-251, February 2003.




Dostları ilə paylaş:


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2017
rəhbərliyinə müraciət

    Ana səhifə