Méthodologies pour la planification de réseaux locaux sans-fil. Katia Runser
tarix 28.10.2017 ölçüsü 503 b. #18878
Méthodologies pour la planification de réseaux locaux sans-fil. Katia Runser Projet ARES – INRIA Directeurs de thèse : Jean-Marie Gorce, MdC., INSA de Lyon Stéphane Ubéda, Pr., INSA de Lyon Plan Introduction 2.1. Méthode de prédiction Multi-Résolution FDPF adaptative 2.2. Adaptation à la planification wLAN. Stratégies de planification wLAN 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) 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 Un MR-Bloc : Surface : Rectangle de NX . NY pixels Un jeu de flux entrant 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 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 : 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 dr ≤ sim /6 ≤ P / 6La fréquence de simulation f sim Multiple de la fréquence réelle P ≥ sim f sim ≥ c0/P ; f sim = 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 = (n 1, .., 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. 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 Favorise l’allocation des canaux, 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 258 cartes de couverture 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 : 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 : 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ş:
