Line-of-sight networks were introduced by Frieze et al. to model wireless communications in an urban setting. Their model is based on a two-dimensional grid of points in the shape of a torus. Two grid points are said to be mutually visible if they lie in the same row or column of the torus and if the distance between them is within a certain predetermined range. Distance is measured using the L1 norm. A random graph is obtained by placing a node at each grid point independently with the same placement probability and connecting all mutually visible pairs of nodes. Among the results proven by Frieze et al. is a threshold for the connectivity of the graph.In this thesis we extend the model of Frieze et al. to higher dimensions and the general Lp norm. Specifically we consider an underlying d-dimensional grid in the shape of a torus and we define two points to be mutually visible if they differ in at most k coordinates, and the distance between them is within a certain range. We then prove corresponding asymptotically tight connectivity thresholds for this generalized model. / Les réseaux de lignes de visée ont été introduits par Frieze et al. pour modéliser les communications sans fil en milieu urbain. Leur modèle est basé sur une grille bidimensionnelle de points en forme de tore. Deux points de la grille sont dits mutuellement visibles si ils sont situés sur la même ligne ou la même colonne du tore et si la distance entre eux est dans un certain intervalle prédéterminé. La distance est mesurée en utilisant le norme L1. Un graphe aléatoire est obtenu en plaçant un noeud à chaque point de la grille indépendamment avec la même probabilité de placement et en reliant toutes les paires de noeuds qui sont mutuellement visible. En particulier, Frieze et. al déterminent le seuil de connectivité du graphe.Dans cette thèse, nous généralisons le modèle de Frieze et al. à dimensions supérieures. Plus précisément, nous considérons comme un réseau sous-jacent une grille à d dimensions et nous disons que deux points sont mutuellement visibles si ils ont un maximum de k coordonnées différentes, et si la distance entre eux est dans un certain intervalle. Ensuite, nous prouvons un seuil pour la connectivité de ce modèle généralisé.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.97260 |
| Date | January 2011 |
| Creators | Farczadi, Linda |
| Contributors | Luc P Devroye (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.002 seconds