Faculté informatique et communications IC, Section des systèmes de communication, Institut de systèmes de communication ISC (Laboratoire de communications audiovisuelles LCAV)

Distributed routing algorithms for sensor networks

Barrenetxea, Guillermo ; Vetterli, Martin (Dir.) ; Beferull-Lozano, Baltasar (Dir.)

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

Add to personal list
    Summary
    Recent advances in wireless communications and computing technology are enabling the emergence of low-cost devices that incorporate sensing, processing, and communication functionalities. A large number of these devices are deployed in the field to create a sensor network for both monitoring and control purposes. Sensor networks are currently an active research area mainly due to the potential of their applications. However, the deployment of a working large scale sensor network still requires solutions to a number of technical challenges that stem primarily from the constraints imposed by simple sensor devices: limited power, limited communication bandwidth, and small storage capacity. In view of all these particular constraints, we require a new paradigm for communication, which consists of new algorithms specifically conceived for sensor networks. This thesis concentrates on the routing problem, that is, moving data among different network locations, and on the interactions between routing and coding, that is, how sensors code the observations. We start by designing efficient and computationally simple decentralized algorithms to transmit data from one single source to one single destination. We formalize the corresponding routing problem as a problem of constructing suitably constrained random walks on random graphs and derive distributed algorithms to compute the local parameters of the random walk that induces a uniform load distribution in the network. The main feature of this routing formulation is that it is possible to route messages along all possible routes between the source and the destination node, without performing explicit route discovery/repair computations and without maintaining explicit state information about available routes at the nodes. A natural extension to the single-source/single-destination scenario is to consider multiple sources and/or multiple destinations. Depending on the structure and goal of the network, nodes exhibit different communication patterns. We analyze the problem of routing under three different communication models, namely uniform communication, central data gathering, and border data gathering. For each of these models, we derive capacity limits and propose constructive routing strategies that achieve this capacity. An important constraint of sensor networks is the limited storage capacity available at the nodes. We analyze the problem of routing in networks with small buffers. We develop new approximation models to compute the distribution on the queue size at the nodes which provide a more accurate distribution than the usual Jackson's Theorem. Using these models, we design routing algorithms that minimize buffer overflow losses. Routing in large and unreliable networks, such as sensor networks, becomes prohibitively complex in terms of both computation and communication: due to temporary node failures, the set of available routes between any two nodes changes randomly. We demonstrate that achieving robust communications and maximizing the achievable rate per node are incompatible goals: while robust communications require the use of as many paths as possible between the source and the destination, maximizing the rate per node requires using only a few of the available paths. We propose a family of routing algorithms that explores this trade-off, depending on the degree of reliability of the network. The performance of routing algorithms in sensor networks can be significantly improved by considering the interaction of the source coding mechanism with the transport mechanism. We jointly optimize both the source coding and the routing algorithm in a common scenario encountered in sensor network, namely, real-time data transmission. We demonstrate that the combination of specially designed coding techniques, such as multiple description coding, and multipath routing algorithms, performs significantly better that the usual routing and coding schemes. In summary, this thesis revisits the classic routing problem in the light of distributed schemes for networks with resource-limited nodes.
    Résumé
    Les récents progrès des communications sans fils et des technologies informatiques ont permis l'apparition de dispositifs à bas coûts intégrant les fonctionnalités de captage, de traitement et de communication. Un grand nombre de ces dispositifs sont deployés dans la nature afin de créer un réseau de capteurs à des fins aussi bien de contrôle que de monitorisation. Le fort potentiel d'applications des réseaux de capteurs en font un domaine de recherche très actif. Cependant, la conception d'un réseau de capteurs de grande taille se heurte à un certain nombre de difficultés techniques provenant des contraintes imposées par les capacités réduites des capteurs individuels: basse puissance, capacité de communication réduite et faible capacité de stockage. Afin de surmonter ces difficultés, de nouveaux paradigmes de communication sont nécessaires: il y a un besoin de nouveaux algorithmes spécifiques aux réseaux de capteurs. Cette thèse se concentre sur la question du routage, à savoir le transfert de données entre différentes parties du réseau, et son interaction avec le codage, à savoir, comment les capteurs codent leurs observations. Dans un premier temps nous avons conçu un algorithme décentralisé simple et efficace pour transmettre les données d'une source unique à une destination unique. Dans ce but, on reformule le problème du routage en celui d'imposer les contraintes appropriées à des chemins aléatoires sur des graphes (aléatoires). En suite nous dérivons des algorithmes distribués pour trouver les paramètres locaux des marches aléatoires qui induiront un certain propriété de distribution de la charge dans le réseau. La caractéristique principale de cette formulation est que nous sommes capables de transmettre des messages entre une source et une destination par tous les chemins possibles, en nous affranchissant d'une reconnaissance explicite du chemin au préalable, et sans devoir tenir à jour une information sur l'état des chemins à chaque noeud. Une extension naturelle de ce scenario est de considérer plusieurs sources et/ou destinations. Selon la structure et la fonction du réseau, les noeuds présentent différents motifs de communication. Nous avons traité le problème dans le cadre de trois modèles de communication : la communication uniforme, "central data gathering" et "border data gathering". Dans le cadre de chacun de ces modèles, nous avons étudié les limites de capacités et avons explicité les stratégies de routage qui permettent de les atteindre. Une limitation courante des réseaux de capteurs est leur faible capacité de stockage aux noeuds du réseau. Nous avons donc analysé le problème du routage dans des réseaux avec faible mémoire tampon, ce qui a necessité de nouveaux modèles pour obtenir la distribution de la taille des queues aux noeuds. Nous avons ainsi proposé une alternative au traditionnel théorème de Jackson, qui permet une évaluation plus précise des distributions. Ce faisant, nous avons obtenu des algorithmes qui minimisent les pertes du au débordement de la mémoire tampon. Nous nous sommes également intéresés au problème du routage dans des réseaux défaillants, où chaque noeud est susceptible, temporairement et de façon aléatoire, de tomber en panne. Nous montrons alors que, d'une part robustesse des communications et d'autre part maximisation du traffic par noeud , sont des objectifs contradictoires. La robustesse implique l'utilisation d'un nombre de chemins (entre la source et la destination) aussi grand que possible, tandis que maximiser l'utilisation d'un noeud incite à n'utiliser qu'un nombre restreint de chemins possibles. Nous montrons comment obtenir différents compromis, selon le degré de fiabilité du réseau. Enfin, nous nous sommes également intéresés à l'interaction entre le codage à la source et le mécanisme de transport dans le réseau de capteurs. Nous nous sommes dans un premier temps intéresé à l'utilisation des techniques de codage par descriptions multiples pour la transmission de données en temps réel à travers des réseaux de capteurs : nous avons formulé et résolu analytiquement un problème de réseau qui optimise simultanément le codage à la source et le mécanisme de routage. Nous avons ensuite considéré les aspects pratiques de l'utilisation des techniques de codage par descriptions multiples dans des réseaux de capteurs à grande échelle, où le nombre de chemins disponibles entre une source et une destination est grand.