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

Efficient decentralized communications in sensor networks

Cristescu, Razvan ; Vetterli, Martin (Dir.)

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

Add to personal list
    Summary
    This thesis is concerned with problems in decentralized communication in large networks. Namely, we address the problems of joint rate allocation and transmission of data sources measured at nodes, and of controlling the multiple access of sources to a shared medium. In our study, we consider in particular the important case of a sensor network measuring correlated data. In the first part of this thesis, we consider the problem of correlated data gathering by a network with a sink node and a tree communication structure, where the goal is to minimize the total transmission cost of transporting the information collected by the nodes, to the sink node. Two coding strategies are analyzed: a Slepian-Wolf model where optimal coding is complex and transmission optimization is simple, and a joint entropy coding model with explicit communication where coding is simple and transmission optimization is difficult. This problem requires a joint optimization of the rate allocation at the nodes and of the transmission structure. For the Slepian-Wolf setting, we derive a closed form solution and an efficient distributed approximation algorithm with a good performance. We generalize our results to the case of multiple sinks. For the explicit communication case, we prove that building an optimal data gathering tree is NP-complete and we propose various distributed approximation algorithms. We compare asymptotically, for dense networks, the total costs associated with Slepian-Wolf coding and explicit communication, by finding their corresponding scaling laws and analyzing the ratio of their respective costs. We argue that, for large networks and under certain conditions on the correlation structure, "intelligent", but more complex Slepian-Wolf coding provides unbounded gains over the widely used straightforward approach of opportunistic aggregation and compression by explicit communication. In the second part of this thesis, we consider a queuing problem in which the service rate of a queue is a function of a partially observed Markov chain, and in which the arrivals are controlled based on those partial observations so as to keep the system in a desirable mildly unstable regime. The optimal controller for this problem satisfies a separation property: we first compute a probability measure on the state space of the chain, namely the information state, then use this measure as the new state based on which to make control decisions. We give a formal description of the system considered and of its dynamics, we formalize and solve an optimal control problem, and we show numerical simulations to illustrate with concrete examples properties of the optimal control law. We show how the ergodic behavior of our queuing model is characterized by an invariant measure over all possible information states, and we construct that measure. Our results may be applied for designing efficient and stable algorithms for medium access control in multiple accessed systems, in particular for sensor networks.
    Résumé
    Cette thèse est concernée par des problèmes de la communication décentralisée dans des grands réseaux. Nous abordons d'une part le problème d'allocation de débit et de transmission de données mesurés aux noeuds, d'autre part le problème de contrôle d'accès multiple des sources à un milieu partagé. Dans notre étude, nous considérons en particulier le cas important d'un réseau de senseurs mesurant des données corrélées. Dans la première partie de cette thèse, nous considérons le problème de récolte de données corrélées par un réseau ayant un noeud évier et une structure de communication en arbre, où le but est de réduire au minimum le coût de transmission pour transporter l'information rassemblé par les noeuds au noeud évier. Deux stratégies de codage sont analysées: un modèle Slepian-Wolf où le codage optimal est complexe et l'optimisation de transmission est simple, et un modèle de codage avec la communication explicite où le codage est simple et l'optimisation de transmission est difficile. Ce problème exige une optimisation commune de l'allocation de débit aux noeuds et de la structure de transmission. Pour le codage Slepian-Wolf, nous dérivons une solution forme-fermée et un algorithme distribué efficace d'approximation. Nous généralisons nos résultats au cas d'éviers multiples. Pour le codage avec communication explicite, nous montrons qu'établir l'arbre de transmission est NP-complet et nous proposons divers algorithmes distribués d'approximation. Nous comparons asymptotiquement, pour des réseaux denses, les coûts liés au codage Slepian-Wolf et au codage avec communication explicite, en trouvant leurs lois correspondantes et en analysant le rapport du leur coûts respectifs. Pour des grands réseaux et dans certaines conditions sur la structure de corrélation, un codage Slepian-Wolf plus complexe mais "intelligent" fournit des gains illimités au-dessus du l'approche largement répandue de l'agrégation et de la compression par communication explicite. Dans la deuxième partie de cette thèse, nous considérons un problème dans lequel le taux de service d'une file d'attente est une fonction d'une chaîne de Markov partiellement observée, et où les arrivées sont basées sur des observations partielles, afin de maintenir le système dans un régime modérément instable souhaitable. Le contrôleur optimal pour ce problème satisfait une propriété de séparation: nous calculons d'abord une mesure de probabilité sur l'espace d'état de la chaîne, à savoir l'état de l'information, en employant alors cette mesure comme le nouvel état pour prendre des décisions de commande. Nous donnons une description formelle du système considéré et de sa dynamique, nous formalisons et résolvons un problème de commande optimale, et nous montrons avec des simulations numériques les propriétés concrètes de la loi de commande optimale. Nous montrons comment le comportement ergodique de notre modèle est caractérisé par une mesure invariable au-dessus de tous états possibles de l'information, et nous construisons cette mesure. Nos résultats peuvent être appliqués pour concevoir des algorithmes efficaces et stables pour le contrôle d'accès dans les systèmes d'access, en particulier pour les réseaux de senseurs.