Reachback communication in wireless sensor networks [Elektronische Ressource] / João Barros

Sujets

• Informatik

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2004
• Nombre de lectures: 21
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Lehrstuhl fur¨ Nachrichtentechnik
Reachback Communication
in Wireless Sensor Networks
Joao˜ Barros
Vollstandiger¨ Abdruck der von der Fakultat¨ fur¨ Elektrotechnik und Informationstechnik
der Technischen Universitat¨ Munchen¨ zur Erlangung des akademischen Grades eines
Doktor–Ingenieurs
genehmigten Dissertation.
Vorsitzender: Univ.–Prof. Dr.–Ing. G. Farber¨
Prufer¨ der Dissertation:
1. Univ.–Prof. Dr.–Ing. J. Hagenauer
2. Univ Dr.–Ing. Dr. rer. nat. H. Boche,
Technische Universitat¨ Berlin
Die Dissertation wurde am 21.09.2004 bei der Technischen Universitat¨ Munchen¨ eingereicht
und durch die Fakultat¨ fur¨ Elektrotechnik und Informationstechnik am 04.11.2004 angenom-
men.Abstract
This dissertation is concerned with a communications scenario in which a large number of sen-
sor nodes, deployed on a field, take local measurements of some physical process and cooperate
to send back the collected data to a far receiver. The first part considers the problem of com-
municating multiple correlated sources over independent channels and with partial cooperation
among encoders, and provides a set of coding theorems that give a complete characterization of
the conditions on the sources and the channels under which reliable communication is possible.
A key insight from these results is that for a large class of networks separate source and channel
coding provides an optimal system architecture. The second part presents new contributions for
the long-standing multiterminal source coding problem. Finally, the third part assumes that the
sensor nodes use very simple encoders and focuses on the design of practical decoding algo-
rithms under given complexity constraints.
Zusammenfassung
Diese Arbeit betrachtet einige Aspekte der Kommunikation zwischen verteilten Sensorknoten,
die gemessene Werte versenden, und einem entfernten Empfanger¨ , der die Daten weiterverar-
¨beitet. Zuerst werden die theoretischen Grenzen fur¨ die kooperative Ubertragung von korre-
lierten Quellen uber¨ statistisch unabhangige¨ Kanale¨ bestimmt. Dies erfolgt durch eine Reihe
von Codierungstheoremen, die hinreichende und notwendige Bedingungen fur¨ nahezu fehler-
freie Kommunikation angeben. Eine wichtige Erkenntnis dieser Arbeit ist, dass fur¨ viele nicht
triviale Netzwerke getrennte Quellen- und Kanalcodierung eine optimale Systemarchitektur an-
bietet. Als zweiter Schritt wird eine Verzerrung der Daten mitberucksichtigt,¨ was zu einem
lange offenen Problem der Rate-Distortion Theorie fuhrt.¨ Auch hierfur¨ werden neue Ergeb-
nisse prasentiert.¨ Der letzte Teil der Arbeit beschaftigt¨ sich mit dem Entwurf von praktischen
Decodierungsalgorithmen unter Einschrankung¨ der algorithmischen Komplexitat.¨Acknowledgements
Throughout the years of research that lead to this dissertation, I was very fortunate to be able to
count on the advice, the encouragement and the friendship of a great number of people.
I would like to begin by thanking Prof. Joachim Hagenauer for his trust in granting me
an assistentship at the Lehrstuhl fur¨ Nachrichtentechnik (LNT) and the freedom to follow any
research path that I set for myself. His professional conduct as a dedicated faculty member
and well-respected engineer made me appreciate the importance of, among other aptitudes,
thinking in international terms, cultivating a broad scope of interests and being able to explain
complex matters with simple examples. It was also thanks to Prof. Hagenauer’s trust and
support that I could present my research at international conferences, learn how to manage an
international graduate program, and supervise students in their diploma and master theses. Not
many professors encourage their doctoral students to spend part of their PhD in another lab —
I am deeply grateful for being given this opportunity.
The core of the present thesis would not have been possible without the thoughtful guidance,
the constant encouragement and the contagious scientific enthusiasm of Prof. Sergio Servetto.
In the course of two research stays at Cornell University – kindly supported by Prof. Hagenauer
and co-sponsored by the Fulbright Commission in June-September 2002, and again February-
March 2003 – and through countless online and offline discussions in the past three years,
Sergio has taught me how to find good scientific problems, how to gather the expertise needed
to accomplish vital research tasks, and, most importantly, how to lose my natural fear of the
complex mathematics that are necessary to solve challenging theoretical problems. By doing
so, Sergio has deeply influenced the way I think about scientific research and helped shape and
solidify the knowledge base upon which I can build my career as a scientist. Words cannot
express my gratitude towards Sergio – his true and honest friendship remains one of the most
important gifts from this endeavor.
Prof. Holger Boche has kindly accepted to lend his technical and mathematical expertise as
a member of the doctoral committee that must evaluate this thesis. Knowing his many solicita-
tions, I am very grateful for his interest, time and dedication.
The work on multiterminal source coding presented in the fourth chapter was much im-
proved following the insightful comments of Prof. Toby Berger, with whom I spent a few very
educative afternoons at Cornell, and Prof. Raymond Yeung, who visited our lab early this year.
Prof. Pedro Guedes de Oliveira at the University of Porto was the first person to encourage
me to pursue graduate studies in Germany, and has constantly supported my efforts with helpful
advice and recommendation letters, as have Prof. Kristian Kroschel (Karlsruhe), Prof. DanCostello (Notre-Dame) and Prof. John B. Anderson (Lund).
I have also profited very much from personal relationships with some of my colleagues at
LNT. Michael Tuchler¨ deserves my fondest gratitude for his close friendship and enthusiastic
collaboration. It was a great pleasure for me to work with him and our two diploma students,
Christoph Hausl and Seong Per Lee, on factor graphs and scalable decoding, yielding the results
presented in the fifth chapter of this thesis. Special thanks are also due to my dedicated friend
Zaher Dawy for many discussions and for proof-reading the first complete draft of this thesis.
I also deeply enjoyed the close collaborations with Andrew Schaefer, Ioannis Oikonomidis and
Nicolas Dutsch.¨ Our sysadmins Johannes Zangl, Gunther¨ Liebl, Stephan Baro¨ and Markus
Kaindl guaranteed an outstanding computer network support at all times. Thanks are also due
to Gunther¨ Soeder, Klaus Eichin, Dieter Heidner and Doris Dorn for friendly administrative
support. Finally, I am much indebted to Silke Jauck, Nicole Rossmann and Pavol Hanus, whose
care and dedication ensured the success of our international graduate program and allowed me
to find time for my research during critical phases of this work.
Beyond the technical skills that are necessary to accomplish any worthy goal, our efforts are
never complete without reaching towards that inner source of inspiration and personal strength
from which all creative work flows. In the past four years, I have had the great privilige of
learning how to seek this path under the guidance of a true master and a wonderful friend: Ulli
Dissmann, the endlessly inspired and inspiring director of the Munchner¨ Sommertheater. I am
deeply grateful to Ulli for her enlightened and invaluable teachings on — among many others
themes — free play, self awareness, powerful speaking, thoughtful leadership, human nature,
and life itself. I hope that my future path is true to these teachings, and that one day I might
give my students at least part of what Ulli has taught me.
Since my son, Daniel, was born, I have come to realize what a overwhelming mission it is
to raise a child and to take responsibility for a family environment that is nurturing in every
possible way. My mother and my father suceeded in finding the necessary balance between
setting important rules and encouraging my sister Luisa, my brother Ze and I to search for our
own path. One of their best decisions was to send us to the German school in Porto, which
broadened our horizons right from early childhood. Words cannot express my gratitude to my
parents for all that they have given me.
This work is dedicated, with love and affection, to Ana, who helps me spread my wings anew
and always holds me when I fall.
Munchen,¨ August 2004
Joao˜ BarrosTo my wife,
AnaContents
1 Introduction 1
2 Fundamentals of Information Theory 7
2.1 The Point-to-Point Communications Problem . . . . . . . . . . . . . . . . . . 7
2.1.1 Communications Model . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Mathematical Tools of Information Theory . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Types and Typical Sequences . . . . . . . . . . . . . . . . . . . . . . 10
2.2.2 Random Coding and Random Binning . . . . . . . . . . . . . . . . . . 13
2.2.3 The Markov Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.4 Useful Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Shannon’s Coding Theorems . . . . . . . . . . . . . . . . . .