Faculté informatique et communications IC, Section des systèmes de communication, Institut de systèmes de communication ISC (Laboratoire pour les communications informatiques et leurs applications 3 LCA3)

Asymptotic properties of wireless multi-hop networks

Dousse, Olivier ; Thiran, Patrick (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2005 ; no 3310.

Ajouter à la liste personnelle
    Summary
    In this dissertation, we consider wireless multi-hop networks, where the nodes are randomly placed. We are particularly interested in their asymptotic properties when the number of nodes tends to infinity. We use percolation theory as our main tool of analysis. As a first model, we assume that nodes have a fixed connectivity range, and can establish wireless links to all nodes within this range, but no other (Boolean model). We compute for one-dimensional networks the probability that two nodes are connected, given the distance between them. We show that this probability tends exponentially to zero when the distance increases, proving that pure multi-hopping does not work in large networks. In two dimensions however, an unbounded cluster of connected nodes forms if the node density is above a critical threshold (super-critical phase). This is known as the percolation phenomenon. This cluster contains a positive fraction of the nodes that depends on the node density, and remains constant as the network size increases. Furthermore, the fraction of connected nodes tends rapidly to one when the node density is above the threshold. We compare this partial connectivity to full connectivity, and show that the requirement for full connectivity leads to vanishing throughput when the network size increases. In contrast, partial connectivity is perfectly scalable, at the cost of a tiny fraction of the nodes being disconnected. We consider two other connectivity models. The first one is a signal-to-interference- plus-noise-ratio based connectivity graph (STIRG). In this model, we assume deterministic attenuation of the signals as a function of distance. We prove that percolation occurs in this model in a similar way as in the previous model, and study in detail the domain of parameters where it occurs. We show in particular that the assumptions on the attenuation function dramatically impact the results: the commonly used power-law attenuation leads to particular symmetry properties. However, physics imposes that the received signal cannot be stronger than the emitted signal, implying a bounded attenuation function. We observe that percolation is harder to achieve in most cases with such an attenuation function. The second model is an information theoretic view on connectivity, where two arbitrary nodes are considered connected if it is possible to transmit data from one to the other at a given rate. We show that in this model the same partial connectivity can be achieved in a scalable way as in the Boolean model. This result is however a pure connectivity result in the sense that there is no competition and interferences between data flows. We also look at the other extreme, the Gupta and Kumar scenario, where all nodes want to transmit data simultaneously. We show first that under point-to-point communication and bounded attenuation function the total transport capacity of a fixed area network is bounded from above by a constant, whatever the number of nodes may be. However, if the network area increases linearly with the number of nodes (constant density), or if we assume power-law attenuation function, a throughput per node of order 1/√n can be achieved. This latter result improves the existing results about random networks by a factor (log n)1/2. In the last part of this dissertation, we address two problems related to latency. The first one is an intruder detection scenario, where a static sensor network has to detect an intruder that moves with constant speed along a straight line. We compute an upper bound to the time needed to detect the intruder, under the assumption that detection by disconnected sensors does not count. In the second scenario, sensors switch off their radio device for random periods, in order to save energy. This affects the delivery of alert messages, since they may have to wait for relays to turn on their radio to move further. We show that asymptotically, alert messages propagate with constant, deterministic speed in such networks.
    Résumé
    Ce travail de thèse a pour but d'étudier les réseaux sans fil, dans lesquels les noeuds agissent comme relais pour les autres noeuds (réseaux à relais multiples). Nous nous intéressons en particulier à leur comportement asymptotique lorsque le nombre noeuds tend vers l'infini. Nous utilisons principalement la théorie de la percolation pour parvenir à cette fin. Comme premier modèle, nous faisons l'hypothèse que les noeuds sont capable d'établir une communication radio avec tous leurs voisins situés dans un certain périmètre autour d'eux, mais pas plus loin (modèle Booléen). Pour les réseaux unidimensionnels, nous calculons la probabilité que deux noeuds peuvent communiquer (avec l'aide d'autres noeuds agissant comme relais), en fonction de la distance qui les sépare. Nous montrons que cette probabilité tend exponentiellement vers zéro lorsque la distance augmente. Ainsi, aucune communication à longe distance n'est possible dans les réseaux unidimensionnels. Dans les réseaux bidimensionnels, si la densité de noeuds est suffisante (phase sur-critique), une clique géante de noeuds connectés se forme (phénomène de percolation). Cette clique contient une fraction non-nulle des noeuds, laquelle ne dépend que de la densité de noeuds et de leur protée. De plus, cette fraction tend rapidement vers 1 lorsque la densité augmente. Nous comparons cette connectivité partielle à la connectivité complète du réseau, et montrons que cette dernière est très coûteuse en termes de performance du réseau. Par contre, la connectivité partielle ne demande pas d'adaptation des paramètres du réseau pour être maintenue lorsque celui-ci s'agrandit. Dans ce travail, nous étudions deux autres modèles de connectivité, plus sophistiqués. Dans le premier, on considère que deux noeuds peuvent établir une communication sans fil si le rapport signal-sur-interférence-plus-bruit est supérieur à un seuil prescrit. Pour calculer ce rapport, nous faisons l'hypothèse que les signaux s'affaiblissent selon une fonction déterministe de la distance parcourue (fonction d'atténuation). Nous montrons que dans ce modèle, le même phénomène de percolation a lieu, et nous décrivons les conditions sous lesquelles il se réalise. Notamment, nous montrons que les hypothèses faites sur la fonction d'atténuation ont un impact important sur la résultats. En particulier, l'hypothèse usuelle qui consiste à prendre l'atténuation égale à une puissance négative de la distance confère au modèle des propriétés de symétrie particulières, mais malheureusement irréalistes, vu que la fonction d'atténuation doit être bornée pour des raisons physiques évidentes. Le second modèle consiste à déclarer deux noeuds connectés s'il est possible de transmettre de l'information de l'un à l'autre avec un certain débit prescrit, avec l'aide de tous les autres noeuds. Nous montrons que dans ce modèle, il est aussi possible de garder une fraction arbitraire de noeuds connectés entre eux, sans changer le débit prescrit, lorsque la taille et le nombre de noeuds du réseau augmente. Les résultats ci-dessus sont des résultat de connectivité pure, vu que nous ne regardons qu'une paire de noeuds à la fois, et qu'il n'y a donc pas d'interférence entre plusieurs flots de données. Dans une seconde étape, nous étudions le modèle initialement proposé par Gupta et Kumar, dans lequel chaque noeud veut transmettre des données vers une destination de son choix. Nous montrons que si le réseau occupe une surface bornée, et que la fonction d'atténuation est aussi bornée, le débit de donnée alloué à chaque noeud doit décroître de façon inversement proportionnelle au nombre de noeuds dans le réseau. Par contre, si la densité de noeuds est constante, et que la surface augmente linéairement avec le nombre de noeuds n, alors un débit égal et de l'ordre de 1/√n est réalisable pour chaque noeud. Ce résultat améliore la borne inférieur connue jusqu'ici d'un facteur (log n)1/2. La dernière partie de ce travail est consacrée à deux études portant sur le temps de latence de réseau de capteurs. Dans la première étude, le réseau doit détecter un intrus qui se déplace en ligne droite et à vitesse constante. Nous calculons une borne supérieure à la distribution du temps requis pour détecter l'intrus, sous l'hypothèse que l'intrus n'est détecté que quand il entre en contact avec la fraction de noeuds connectés du réseau. Dans la seconde étude, nous nous intéressons à un réseau de capteurs qui, pour économiser leur batterie, éteignent leur radio pour des périodes aléatoires, indépendamment les uns des autres. Dans ce réseau, un noeud émet un message d'alerte à tous les autres noeuds. Comme certains noeuds ont éteint leur radio, le message se propage jusqu'à ce qu'il ne puisse atteindre d'autres noeuds actifs; ensuite, il doit attendre qu'un nouveau noeud devienne actif pour continuer. Nous prouvons que dans un tel scénario, le rapport entre la distance parcourue par le message et le temps écoulé tend asymptotiquement vers une constante déterministe.