Announcements

About the course

Instructor:
Sergio Servetto

Meeting times and place:
Thu 9am-12pm, 380 RH.

Prerequisites:
ECE 562 (Information Theory). MATH 413 is not required, but would help.

Grading:
50% homeworks (6-8), 50% project (either review of 2 papers, or a take-home exam---undecided yet).

Lectures:
Consist of (roughly): 1:45-2 hours by Sergio, 15 minute break, 45'-1 hour of solving homework problems in the blackboard.
Coffee/cookies available during the break.
Eventually we will put here a collection of nice/interesting/tough problems we encounter.

Syllabus:
The goal in this offering of the course is to thoroughly study the proof techniques needed to analyze/understand two problems (actually, two family of problems) of particular relevance in the study of sensor networks: random walks on graphs, and capacity and rate/distortion in multiterminal settings. Why are these problems interesting, specifically in the context of sensors?

• Random walks on graphs. Large scale, massively distributed sensing/computation involves severe constraints in terms of communication and processing resources. Such limitations may stem, for example, from miniature physical size and/or limited energy sources. An example of such devices is given by biological sensors, a few hundred nanometers in size, with energy storage of just a few nanoJoules, and with data storage capabilities of a few hundred bits only. Additionally, the number of nodes in the network can be potentially very large. The devices may often fail (due to reliability issues, due to exhaustion of energy, ...) and the network needs to compensate for removal of non-operational units. An important challenge is such networks is that of providing suitable routing protocols, one of the most primitive networking operations. Previous work has suggested the idea that scalability and fault tolerance in such extreme scenarios could be potentially achieved by means of using randomized algorithms. Therefore, the study of random walks on graphs is relevant to sensor networking in that it provides a set of tools needed to analyze a new family of emerging routing protocols.
  • Z. Haas, J. Halpern, L. Li. Gossip-Based Ad Hoc Routing, Infocom 2002.
  • W. Vogels, R. van Renessee, K. Birman. The Power of Epidemics: Robust Communication for Large-Scale Distributed Systems, Hotnets 2002.
  • S. D. Servetto, G. Barrenechea. Constrained Random Walks on Random Graphs: Routing Algorithms for Large Scale Wireless Sensor Networks, WSNA 2002.

• Capacity and Rate/Distortion in Multiterminal Settings. Network information theory is not a new problem: already in 1960, Shannon introduced what could be considered the first multiterminal problem, that of communicating over the two-way channel. And the field saw a "golden age" in the 70s and early 80s, with the pioneering work of people like Ahlswede, Berger, Cover, Slepian, Wolf, Wyner and Ziv (among others). More recently, a host of new communication systems (the Internet, wireless networks, and now sensor networks) are contributing to a resurge of interest in these old ideas. A good example we are currently involved with is that of communicating over the reachback channel in sensor networks: multiple sensors are deployed on a field, and they collect local measurements of some random process which then need to be encoded and reproduced at a remote location. For one instance of the reachback problem, we were able to present a number of information theoretic bounds on the performance of a distributed transmission array that is formed by a large number of cheap, unreliable sensors, by showing an equivalence between this instance and the classical multiterminal source coding problem. Therefore, the study of classical results from network information theory appears very relevant to sensor networking, in that the classical theory provides a rich framework in which to study these new networking problems---and with any luck, maybe use insights from the new application to advance the theory.
  • J. Barros, S. D. Servetto. On the Capacity of the Reachback Channel in Wireless Sensor Networks, MMSP 2002.
  • J. Barros, S. D. Servetto. Reachback Capacity with Non-Interfering Nodes. Currently under review.
  • J. Barros, S. D. Servetto. An Inner Bound for the Rate/Distortion Region of the Multiterminal Source Coding Problem. Currently under review.

• Course presentation:
  • Overview of material, administrativia.
  Reading assignments (for review):
  Review chapters 2-5,8-10,13 of Cover and Thomas.
  Read chapter 1 of Motwani and Raghavan.

  Random Walks on Graphs (8 weeks, until spring break):

  • Development of the "toolbox":
    • "Warm up" problems: random permutations, simulation of random variables, counting.
    • Use of the union bound and of Markov/Chebyshev inequalities to bound deviations from the mean behavior.
      Two examples: stable marriages and coupon collector.
    • Use of large deviation methods (the Chernoff bound) and martingale methods, for bounding deviations from the mean behavior for sums of random variables.
      Two examples: routing and wiring.
    • Counting methods based on probabilistic tools.
      Three examples: max-sat, oblivious routing, existence of expanders.
  • Analysis of random walks on graphs:
    • Markov chains induced by graphs.
    • Stopping/Hitting times.
    • Cover times.
    • Mixing times.

  Required reading:

  Motwani/Raghavan, Randomized Algorithms (Chapters 3-6).
  Reading supplements from:

  Alon/Spencer, The Probabilistic Method.

  Aldous/Fill, Reversible Markov Chains and Random Walks on Graphs.

  Kelly, Reversibility and Stochastic Networks.

  Network Information Theory (5 weeks, from the break till end of semester):

  • Development of the "toolbox":
    • Fano's inequality, typical sequences, and the AEP.
    • The channel capacity and rate/distortion theorems.
    • Strong and joint typicality.
    • Berger's Markov lemma.
  • Some interesting network problems:
    • The multiple access channel.
    • The broadcast channel.
    • Distributed encoding of correlated sources (variations on a theme).
    • General multiterminal problems.

  Required reading:

  Cover/Thomas, Elements of Information Theory (Chapter 14).
  Reading supplements from:

  Berger, Lecture Notes on Multiterminal Source Coding.

  Cormen/Leiserson/Rivest/Stein, Introduction to Algorithms.