Model Fitting with Traces. Computation of Fractal Dimension

Get Complete Project Material File(s) Now! »

Les Modeles d’ Hyperfractales

Dans tout environnement urbain, il existe une hierarchie des rues basee sur leur import-ance dans le schema d’urbanisation (boulevards, rues, ruelles). Le niveau qu’une rue occupe dans le plan d’urbanisation vient en consequence de la densit de tra c qu’il sup-porte. Une observation interessante et intuitive est que la longueur cumulee d’un type de rue diminue quand l’importance de la rue augmente. Par exemple, la longueur cumulee des boulevards est inferieure a la longueur cumulee des rues, qui, a son tour, est inferieure a la longueur cumulee des allees. Il est donc naturel que la densit moyenne du tra c par longueur cumulee de chaque type de rue suive une loi d’echelle de puissance. Dans ce qui suit, nous analyserons un cas particulier, lorsque la loi de puissance provient d’une distri-bution fractale. Les villes sont organiquement organisees en structures auto-similaires et representent de bons candidats a ^etre modelises en utilisant la geometrie fractale.
Pour construire une fractale, Mandelbrot commence avec un objet geometrique appel initiateur. A cela il applique un motif qui se repete a toutes les echelles en l’appelant le generateur. La fractale est obtenue en appliquant le generateur a l’initiateur, en derivant un objet geometrique qui peut ^etre consider comme compose de plusieurs initiateurs au niveau suivant de la hierarchie ou de l’echelle inferieure. L’application du generateur a la nouvelle echelle entra^ne une elaboration plus poussee de la geometrie de l’objet a une echelle encore plus ne, et le processus se poursuit donc inde niment vers la limite. En pratique, l’iteration s’arr^ete a un niveau au-dessous duquel d’autres copies mises a l’echelle de l’objet original ne sont plus pertinentes aux ns de la modelisation. En substance, cependant, la vraie fractale n’existe que dans la limite, et donc ce que l’on voit a chaque iteration est simplement une approximation de fractale.
Nous proposons d’utiliser notre modele appel hyperfractale, un modele axe sur l’auto-similarite de la topologie. Le modele hyperfractale permet d’echapper aux extr^emes de la regularit ou du hasard.
Le modele propose n’est pas une fractale mais une hyperfractale, en ce sens que la dimen-sion est superieure a la dimension de l’espace euclidien. De facon informelle, le modele hyperfractale est un modele de processus ponctuel de Poisson qui supporte une mesure avec des proprietes de mise a l’echelle di erentes d’un ensemble fractale pur. Initialement, la carte est supposee ^etre le carre unite. Le support de la population est une grille de rues similaire a une grille de Manhattan mais avec une resolution in nie. Un exemple est illustre par la Figure 2a. Dans la premiere etape, les lignes formant le niveau 0 sont dessinees en noir epais. Dans la deuxieme etape, chacune des quatre zones obtenues est a nouveau consideree comme une carte independante avec une mise a l’echelle speci que et les lignes formant le niveau 1 sont dessinees en noir plus n. Le processus se poursuit de la m^eme maniere dans la troisieme etape, ou chacune des 16 zones est de nouveau divisee par 16 lignes tracees en traits noirs tres ns.
La carte contient n noeuds mobiles. Le processus d’assignation des points aux lignes est e ectu recursivement, de la m^eme maniere que le processus d’obtention du Cantor Dust [4]. Les deux lignes de niveau 0 forment une croix centrale qui divise la carte en exactement 4 quadrants. On note par p la probabilite que le n ud mobile soit situe sur la croix centrale selon une distribution uniforme et q = 1 p la probabilite complementaire. Avec une probabilite q=4, le mobile est situe dans l’un des quatre quadrants. La procedure d’assignation se poursuit recursivement dans chaque quadrant et s’arr^ete lorsque le n ud mobile est a ect a une croix de niveau m 0. Un croisement de niveau m est constitue de deux segments de lignes de niveau m qui se croisent et chaque segment de la croix est consider comme un segment de niveau m. Deux segments appartenant a la m^eme ligne sont necessairement de m^eme niveau.
Une rue de niveau H consiste en l’union de segments consecutifs de niveau H dans la m^eme ligne. La longueur d’une rue correspond a la longueur du c^ote de la carte. La Figure 2b montre la population obtenue dans le processus d’assignation des rues apres 4 iterations. Comme on peut facilement le constater, la densit de la population diminue quand le niveau de la rue augmente.
En prenant la densit de l’unite pour la carte initiale, la densit des n uds mobiles dans un quadrant est de q=4. Soit _H la densit des noeuds mobiles a ectes sur une rue de niveau H. Il satisfait:
La mesure, dans le sens de Lebesgue, qui represente la densit reelle des n uds mobiles dans la carte a de fortes proprietes d’echelle. La plus importante est que la carte dans son ensemble est reproduite a l’identique dans chacun des quatre quadrants, mais avec un poids de q=4 au lieu de 1. La mesure a donc une structure qui rappelle la structure d’un ensemble fractale, tel comme la carte du Cantor [4]. Une di erence cruciale reside dans le fait que la dimension fractale ici, d_F , est en fait plus grande que 2, la dimension euclidienne. En e et, considerer la carte dans seulement la moitie de sa longueur consiste a considerer la m^eme carte mais avec un poids reduit d’un facteur q=4. On obtient:
Cette propriet ne peut s’expliquer que via le concept de mesure. Notez que lorsque p ! 0, d_F ! 2 et que la mesure tend vers la mesure uniforme dans le carre de l’unite . En d’autres termes, une hyperfractale avec une valeur asymptotique de d_F = 2 est un processus ponctuel de Poisson uniforme.
Des analyses typiques de la geometrie aleatoire ont et faites pour le modele d’hyperfractale pour les noeuds. En quelques mots, les auteurs ont :
initie le developpement de la methodologie de la geometrie stochastique et des outils pour manipuler le modele hyperfractale a n de faciliter d’autres etudes sur les com-munications entre dispositifs a grande echelle initie la derivation d’outils pour le calcul ulterieur de metriques d’inter^et et facilite le chemin pour une etude plus approfondie du modele : la notion de point typique, Campbel-Mecke, le principe de Mass-Transport, la transformee de Laplace.
Le modele de propagation canyon implique que le signal emis par un n ud mobile ne se propage que dans la rue ou il se trouve. Si le reseau est statique, compte tenu du processus de construction donne, la probabilite qu’un n ud mobile soit place dans une intersection passe a zero lorsque la largeur de la rue passe a zero et les n uds positionnes sur deux rues di erentes ne peuvent jamais communiquer. Notez que lorsqu’une rue a une largeur positive, la largeur de l’intersection est negligeable par rapport a la longueur de la rue et le reseau sera toujours partitionne.

Le Modele Hyperfractale pour les Relais

Il n’est pas surprenant que les emplacements des infrastructures de communication en milieu urbain presentent egalement un comportement auto-similaire. Nous appliquons donc un autre processus hyperfractale pour selectionner les intersections ou un relais de communications est installe.
La procedure d’attribution des relais aux intersections est illustree de maniere intuitive dans la Figure 3.
Notons une probabilite xe et q⁰ = 1 la probabilite complementaire. Une etape de selection d’un intersection necessite deux processus: le processus dans le quadrant et le processus dans le segment. La selection commence par le processus dans le quadrant avec la probabilite ², la selection est le croisement central des deux rues du niveau 0. Avec la probabilite (1 =2), le relais est place dans l’un des les quatre segments de rue du niveau 0 commencant a ce point : Nord, Sud, Ouest ou Est, et le processus se poursuit sur le segment avec le processus en cours. Sinon, avec la probabilite (1 =2)², le relais est place dans l’un des quatre quadrants delimites par la croix centrale et le processus in-quadrant continue recursivement.
La selection est e ectuee M fois. A chaque cycle, la probabilite qu’une intersection entre deux rues de niveaux respectifs H et V soit selectionnee est p(H; V ) = ^{2 1 H+V} .
Si un croisement est selectionn plusieurs fois, un seul relais est installe dans le croisement respectif. Le nombre de passages M est une variable de Poisson de la moyenne . Par consequence, une intersection de niveau (H; V ) a la probabilite exp( p(H; V )) de ne pas avoir de relais et les evenements relatifs a chaque intersection sont independants.
Une exigence obligatoire lors de la fourniture d’un nouveau modele pour les reseaux sans l est le developpement d’une procedure qui permet la transformation des donnees dans le modele avec des parametres de modele speci ques. Des procedures de traitement ponc-tuelles typiques de l’ajustement des donnees ont et developpees dans la communaute de recherche sur la base des di erentes methodes. Par exemple, dans R, un langage couram-ment utilise par la communaute de la geometrie stochastique, les fonctions permettent d’ajuster les points a plusieurs types de processus : Poisson, Strauss, Softcore, etc. Mal-heureusement, les procedures existantes d’ajustement des donnees ne peuvent pas ^etre utilisees pour le modele hyperfractale car l’interaction entre les points est di erente et ne peut pas ^etre reconnue par le logiciel existant.
Pour valider notre modele et prouver son utilite et sa facilite d’utilisation, nous avons developp une procedure de transformation des cartes de ux de tra c en hyperfractales, plus precisement le calcul de la dimension fractale des cartes de ux de tra c. On peut utiliser une telle procedure pour calculer une dimension fractale d’une ville / region, puis calculer des metriques d’inter^et. Un exemple de ces metriques est l’heure de di usion.
Soulignons que dans la de nition du modele hyperfractale, nous n’avons pas fait d’hypotheses ou de conditions sur les proprietes de geometrie telles que la forme. Le modele n’a besoin que de densit et de longueur. Par exemple, une hyperfractale n’a pas besoin que les rues principales / de premier niveau soient en croix ou qu’il existe exactement deux rues de niveau 1 qui ont la longueur exacte. Ce qui est necessaire est la mise a l’echelle entre la longueur des di erents niveaux du support. En tenant compte de ces observations (qui viennent naturellement du processus de construction), nous elaborons maintenant une procedure de calcul de la dimension fractale d’une carte de densit de tra c.
La procedure peut ^etre adaptee en ajoutant trois criteres pour augmenter la precision de l’ajustement : a savoir, densit -longueur, densit d’intersection spatiale et intersection d’intervalle de temps.
Ensuite, nous considerons une seule rue comme un alignement de segments consecutifs dont les densites, du segment le moins dense au segment le plus dense, ne varient pas plus que d’un facteur A > 1. Nous appelons la densit de la rue la densit moyenne de son segment. Dans un modele de ville hyperfractale pure, nous avons A = 1. Ceci est assez similaire au concept standard de quanti cation.
L’etape suivante consiste a classer les rues par ordre decroissant de densit et a calculer le vecteur des sommes cumulees des segments de rues ordonnes par leur densit decroissante.
Nous etablissons ensuite la densit des rues triees par rapport a la longueur cumulee des rues triees. En parallele, nous tracons la fonction de repartition de densit avec une valeur de depart de d_F et en utilisant la mesure de la longueur cumulee et par ajustement de courbe, determinons la meilleure approximation pour d_F .
En n, pour illustrer comment le modele hyperfractale peut ^etre utilise pour representer la distribution des vehicules dans les rues, nous presentons ici quelques resultats d’ajustement des donnees.

Etude de la Vitesse de Propagation de l’Information dans un Reseau Urbain Tolerant aux Retards

La premiere application est la vitesse de propagation de l’information d’une di usion dans un reseau urbain tolerant aux retards qui est deconnect a tout moment, c’est-a-dire ou les chemins multipistes de bout en bout n’existent pas (necessitant un modele d’acheminement di ere). Nous prouvons des limites sur le temps de di usion moyen dans une con guration hyperfractale et montrons que la performance est due en partie a un phenomene auto-similaire interessant, que nous denotons comme teleportation de l’information, qui resulte de la topologie et permet une acceleration de la temps de di u-sion.
On a developp des borne inferieurs et superieurs pour le temps de broadcast d’un pacquet d’information dans un reseaux vehiculaire represent une hyperfractale.
Dans ce travail, nous utilisons le processus d’hyperfractale pour les noeuds comme modele pour les emplacements des vehicules dans le reseau. Nous n’utilisons pas ici le processus pour les relais, fait qui conduira a la generation du reseau tolerant aux delais. Etant donne l’absence des relais, la propagation des paquets a travers les intersections, m^eme a l’aide de la mobilite, necessitera l’existence de tampons pouvant contenir le paquet plus longtemps.
Les mobiles se deplacent sur les lignes qui supportent la carte hyperfractale. Lorsqu’un n ud atteint une limite, il retourne a la carte du m^eme point, suite a une mobilite de billard. Au depart, dans un souci de simplicite, la vitesse des mobiles est consideree comme constante et identique, v, quel que soit le niveau et la densit des n uds sur les lignes.
Ici encore, nous utiliserons l’e et canyon comme phenomene de propagation caracteristique en milieu urbain. Le protocole de di usion consider est single-hop broadcast, ce qui signi-e que chaque vehicule transporte l’information pendant son voyage et cette information est transmise aux autres vehicules dans son voisinage immediat (voisins les plus proches du n ud infecte) lors du prochain cycle de di usion.
Apres les derivations des bornes superieures et inferieures sur le temps moyen de di usion, on arrive au resultat uni ant suivant.
En etudiant la propagation epidemique de l’information dans les hyperfractales, nous avons decouvert le phenomene de teleportation de l’information.
Dans un processus de point de Poisson uniforme bidimensionnel, le paquet d’information se repand uniformement comme un disque complet qui se developpe a un debit constant, ce qui co ncide avec la vitesse de propagation de l’information. Fait interessant, dans une hyperfractale, le phenomene est completement di erent, en raison de l’e et canyon et de la repartition de la population speci que au nouveau modele, comme illustre en Figure 6.
Deux contagions de n uds infectes sur les lignes de niveau 0 sont mises en evidence. Ces zones ne sont pas connectees a la zone infectee principale sur la ligne d’ou elles proviennent, la ligne de niveau H = 0. Les n uds de ces zones sont infectes en recevant le paquet de n uds circulant sur des lignes perpendiculaires. Cela genere plusieurs zones de contagion. Sur cette ligne, le paquet est di use a partir de toutes les sources de contamination apparues et la di usion est acceleree. C’est un phenomene qui caracterise de maniere unique la di usion dans les con gurations hyperfractales.
Le phenomene de teleportation permet une acceleration du temps de di usion. Notez que l’acceleration elle-m^eme est un phenomene auto-similaire et prend place recursivement: la propagation au niveau H_i est acceleree par la teleportation provenant des lignes H_i+1, H_i+2, H_i+3 et ainsi de suite. Dans un hyperfractal avec teleportation, le temps de di usion evolue comme: O(n¹ ).
Toutes ces analyses ont et validees par des simulations e ectuees dans un simulateur auto-developp dans MatLab mais aussi en QualNet.

Le Routage de Bout en Bout dans un Reseau Hyperfractale avec Relais

La deuxieme application est le routage de bout en bout dans un reseau hyperfractale avec relais representant les unites de bord de route dans les communications V2I (vehicule a infrastructure).
Les modeles hyperfractaux pour les n uds et les relais conviennent parfaitement a l’analyse des performances cles des reseaux ad hoc en milieu urbain. Dans ce qui suit, nous montrer-ons comment, en modelisant un reseau de vehicules avec des unites c^ote route en utilisant des hyperfractales, des calculs peuvent ^etre e ectues a n d’observer le compromis entre l’energie de bout en bout et le retard. Cela plaide egalement pour l’utilite de nos modeles.
Dans l’etude des reseaux ad hoc et des sous-categories de reseaux de vehicules ad hoc, la topologie appara^t frequemment comme un facteur determinant dans le calcul de l’energie ou du delai de bout en bout. Par consequent, il est tout a fait naturel d’utiliser les modeles hyperfractaux pour l’analyse de telles mesures.
La strategie de routage consideree est la strategie de routage du plus proche voisin. Le saut suivant est toujours le prochain voisin dans une rue, c’est-a-dire qu’il n’existe aucun autre n ud entre l’emetteur et le recepteur.
Nous de nissons le delai de transmission de bout en bout comme le nombre total de sauts que le paquet prend sur son chemin vers la destination.
La transmission se fait en mode semi-duplex, un n ud n’est pas autorise a emettre et a recevoir pendant le m^eme intervalle de temps. Le signal recu est a ect par le bruit de bruit gaussien blanc additif (AWGN) N et la perte de chemin avec exposant > 2. Nous faisons l’hypothese simpli ee que tous les n uds d’une rue transmettent la m^eme puissance nominale P_m qui ne depend que du nombre de n uds de la rue.
L’energie cumulee de chemin presente un inter^et puisque nous souhaitons optimiser la quantite d’energie depensee dans la communication de bout en bout, et respectivement l’energie maximale du chemin lorsque nous voulons trouver le chemin dont l’energie max-imale ne depasse pas un seuil donne en fonction de la durabilite energetique des n uds ou du protocole. Par exemple, il est probable qu’aucun n ud ne puisse supporter une puissance nominale de P_max qui est l’energie necessaire pour transmettre dans une plage correspondant a la longueur totale d’une rue. Dans ce cas, il est necessaire de trouver un chemin qui utilise des rues avec su samment de population pour reduire la puissance nominale du n ud.
Nous montrons les limites theoriques pour le compte de bonds de communication de bout en bout sous deux contraintes d’energie di erentes : soit l’energie totale accumulee, soit l’energie maximale par n ud. Nous avons en outre calcule une limite inferieure sur la capacite de debit du reseau avec des contraintes sur l’energie du chemin.
Les resultats sont obtenus en observant le comportement du routage dans un chemin direct, un chemin devi avec trois segments, soit un chemin devi avec cinq segments (Figure 7).
Regardons la Figure 8 pour comprendre les compromis entre l’energie cumulee de bout en bout et le nombre de sauts pour un couple emetteur-recepteur. La paire a et selectionnee au hasard parmi les simulations e ectuees sur une carte hyperfractale avec n = 800 noeuds, coe cient de perte = 4, dimension fractale des n uds d_f = 4; 33 et dimension fractale des relais d_r = 3. Le trace montre l’energie cumulee minimale pour la transmission de bout en bout pour un nombre xe et autorise de sauts, k, dans les marqueurs de cercle rouges. Notez que l’energie ne diminue pas de maniere monotone, car forcer a prendre un chemin plus long peut ne pas permettre de prendre le meilleur chemin. Cependant, en considerant l’energie minimale cumulee de tous les chemins jusqu’a un certain nombre de sauts, (les marqueurs d’etoiles noires dans la Figure 8), l’energie diminue et montre clairement le comportement attendu. En d’autres termes, l’energie cumulee minimale di-minue e ectivement lorsque le nombre de sauts est autorise a cro^tre (et la communication de bout en bout est autorisee a choisir des chemins plus longs, mais moins co^uteux).

Goulot d’Etranglement

Une autre analyse a et e ectuee pour observer le goulot d’etranglement dans les strategies de routage considerees.
Notez que, desormais, nous utilisons le terme n ud pour designer a la fois les mobiles et les n uds et les relais.
La charge (x) d’un n ud x est le nombre de chemins routes via le n ud respectif. Nous ne fournissons pas analytiquement une technique de routage telle que la charge soit equilibree. Au lieu de cela, nous calculons ici la charge des n uds de transmission sous la contrainte du routage des co^uts de chemin minimum (soit la technique de routage vers le plus proche voisin, soit un delai minimum).
Bien que la strategie de routage ne soit pas optimale en ce qui concerne l’equilibrage de la charge, nous la choisissons comme technique de routage de reference a n de mieux comprendre la charge obtenue lors de la minimisation des co^uts. De plus, une technique de routage a delai minimal est interessante car elle maximise le debit du reseau.

Table of contents :

Les Hyperfractales pour la Modelisation des Reseaux sans Fil x
0.1 Les Modèles d’ Hyperfractales
0.1.1 Un Modèle de Propagation qui Génére la Nécessité d’Elargir le Modèle Topologique. L’Effet Canyon
0.1.2 Le Modèle Hyperfractale pour les Relais
0.2 Des Applications pour les Réseaux sans Fil
0.2.1 Procédure de Validation avec des Données
0.2.2 Etude de la Vitesse de Propagation de l’Information dans un Réseau Urbain Tolérant aux Retards
0.2.3 Le Routage de Bout en Bout dans un Reseau Hyperfractale avec Relais
0.2.4 Goulot d’Etranglement
1 Introduction and Motivation 
1.1 Technological Context
1.2 Motivation
1.3 Contributions and Structure of the Thesis
1.4 Publications
2 Classic Stochastic Geometry 
2.1 Notions of Classic Stochastic Geometry
2.1.1 Model fundamentals
2.1.2 Poisson Point Process
2.1.3 Poisson Line Process
2.1.4 Voronoi Tessellations
2.2 State of the Art of Stochastic Modeling of the Wireless Networks Topologies
2.3 Mobility Estimation in Cellular Networks by Means of Stochastic Geometry
2.3.1 Mobility State Estimation
2.3.2 System Model
2.3.3 Stochastic Geometry and User History based Mobility Estimation: STRAIGHT
2.3.4 Stretch Parameter Computation
2.3.5 Performance Evaluation
2.3.6 Lessons Learned
3 Self-Similar Geometry. The Hyperfractal Model 
3.1 Self-similar Geometry. Fractals
3.1.1 Fractal Dimension
3.1.2 The Sierpinski Triangle
3.2 Self-Similarity of Human Society Geometry. Self-Similarity of Wireless Networks
3.3 Poisson-Shots on Fractal Maps as Precursors of the Hyperfractal Model
3.3.1 Defnition of Poisson-shots on Fractal Maps
3.3.2 Towards the Hyperfractal
3.4 The Hyperfractal Model
3.4.1 Propagation Model as Feature of the Topological Model. Urban Canyon Model
3.4.2 The Support
3.4.3 The Hyperfractal Model for Mobile Users
3.4.4 Hyperfractal Model for Relays
3.5 Stochastic Geometry of the Hyperfractal Model
3.5.1 Typical Points of , rand
3.5.2 Fundamental Properties of the Typical Points
3.5.3 An Alternative Method for Computing the Number of Relays in the Map
3.6 Concluding Remarks
4 Model Fitting with Traces. Computation of Fractal Dimension 
4.1 Theoretical Foundation
4.1.1 Density-to-Length Criteria and the Computation of the Fractal Dimension
4.1.2 The Spatial Intersection Density Criterion
4.1.3 The Time Interval Intersection Criterion
4.2 Data Fitting Examples
4.3 Concluding Remarks
5 Application to Ad-Hoc Networks. End-to-End Energy versus Delay 
5.1 Introduction and Motivation
5.2 System Model
5.2.1 Preliminary Study on Connectivity with no Energy Constraints
5.3 Main Results
5.3.1 Path Cumulated Energy
5.3.2 Path Maximum Energy
5.3.3 Remarks on the Network Throughput Capacity
5.3.4 Simulations
5.4 Short Study on Load and Bottleneck
5.4.1 System Model
5.4.2 Main Results
5.5 Simulations
5.6 Concluding Remarks
6 Application to Ad-Hoc networks. Delay-Tolerant Networks 
6.1 Introduction and Motivation
6.2 System Model
6.2.1 Canyon Efect
6.2.2 Broadcast Algorithm
6.3 Main Results
6.3.1 Upper Bound
6.3.2 Lower Bound
6.3.3 Asymptotic to Poisson Uniform
6.3.4 Extension with Limited Radio Range
6.3.5 Information Teleportation
6.4 Simulations in a System Level Simulator
6.4.1 QualNet Network Simulator Configuration
6.4.2 Urban Vehicular Environment Modeling and Scenario Description
6.4.3 Validation of Upper and Lower Bounds: Constant Speed
6.4.4 Validation of Bounds Under Speed Variation
6.5 Simulations in a Self-Developped Discrete Time Event-Based Simulator
6.5.1 Information Spread Under Hyperfractal Model and Teleportation Phenomenon
6.5.2 Validation of Upper and Lower Bounds on the Average Broadcast Time in the Entire Network
6.5.3 Validation of Bounds on Average Broadcast Time Under Speed Variation
6.6 Concluding Remarks
7 Conclusion and Future Work
7.1 Conclusion
7.2 Future Work
7.2.1 Generalization of the Model for Nodes
7.2.2 Generalization to Poisson Points on Poisson Lines
7.2.3 Generalization to Poisson Voronoi Tessellations
7.2.4 In-Depth Percolation for a Finite Window

GET THE COMPLETE PROJECT