Algorithms for Wireless Networks



Time and place :     Tuesdays 14:00 - 16:00, Takustraße 9 SR 049
                              Thursdays 16:00 - 18:00, Takustraße 9 SR 053.
Winter Semester 2011 - 2012.


Important annuncements:
  1. Introductory class is on Tuesday, October 18. See you there!
  2. No class on 3/11, 8/11, 10/11
  3. Project ideas will given in class on 1/11
  4. Grading distribution updated. See below.
  5. Problem set 1 is out. Due 13/12.
  6. NO CLASS on 3/1 and 5/1.
  7. Problem Set 2 is out. Due on 2/2 before class.
  8. Final chance of student presentations on 31/1: topics already given in class
  9. Send your presentation slides after your presentation


Instructor
: Dr. Rik Sarkar

Email :

Description: Our surroundings are becoming more interconnected. The fastest development in interconnectedness is from the spread of wireless devices. This makes communication possible everywhere: irrespective of location, motion and other properties of devices. A Wireless Network is a general model for such interconnected systems.

Each wireless device contains information that is potentially useful to others. The challenge is to efficiently search and deliver the important information to the relevant parties. This becomes harder as the networks grow in number of devices and is deployed over larger areas. 

The ideas applied to handle such large networks come from many different areas of computer science. The concepts covered in the course are directly useful in theoretical computer science, databases, signal and image processing, information theory, geometry and topology and many other subjects.


Grading Scheme: Project: 60%,  Problem sets 20% and paper presentation 20%.

Part of the grading will be based on a project. This may be:

  1. A theoretical (algorithmic) project that develops a new algorithm or protocol, or analyzes an existing one. OR
  2. An implementation project that studies existing algorithms or protocols through implementation or simulation. 
Project ideas will be given in class. Students are also welcome to think of their own project ideas and discuss with the instructor.

Schedule:

Lecture date
Topic
References
Comments
18/10
Introduction Slides


20/10
Location Based Routing Slides
ROU(1,3,6)

25/10
Landmark Based Routing Slides
ROU(7,8,9)

27/10
Some basic facts and methods
in wireless communication Slides


1/11
Data Centric Routing Slides
DRT(1,2,3,4)

3/11
No class


8/11
No class


10/11
No class


15/11
Student presentations
ROU(10,11,12)

17/11
Multi Dimensional Data and Queries Slides
MRQ(2,3)

22/11
TinyDB, Data Aggregation and Medians Slides
AGR(1,2)

24/11
ODI Synopsis, Probabilistic Counting and Multipath Aggregation Slides
AGR(3,4)

29/11
HW1 is out
Boundary Detection Slides
BDD(1,2,3)

1/12
Coding and Storage Sldies
COD(1)

6/12
Student presentations
LOC(1,2,4)

8/12
Network Coding Slides
COD(2,3)

13/12
Network Coding Slides
COD(4)

15/12
HW1 Solutions in class


3/1
No Class


5/1
No Class

10/1
Student Presentations


12/1
Gossip : The Push Sum protocol Slides
GOS(1)

17/1
Managing Mobility Slides
MOB(1,2)

19/1
HW2 is out
Mobility, Tracking and Aggregate Queries Slides
MOB(3,4)

24/1
Diffusion rates, heat equation and laplacian Slides


26/1
Analysis of Gossip and Diffusion


31/1
Student Presentations (final)


2/2
HW2 due. Solutions in class


7/2
Project Presentations:
1. Thomas Holst, Lu Chunxian, Irena Kpogbezan
2. Simon Putzke & Jakob Pfender



9/2
Project Presentations:
1. Manuel Gellfart,  Jörg Meier, Holger Schmeisky
2. Pedro Jesus and Oscar Barrachina.
3. Andreas Wierz, Lukas Maischak




Reading materials by topic:

Localization (LOC)
  1. A. Savvides, C.-C. Han, and M. B. Strivastava. Dynamic fine-grained localization in ad-hoc networks of sensors. MobiCom 01.
  2. Yi Shang, Wheeler Ruml, Ying Zhang, Markus P.J. Fromherz. Localization from Mere Connectivity, MobiHoc 03. 
  3. N. B. Priyantha, H. Balakrishnan, E. Demaine, S. Teller. Mobile-Assisted Localization in Wireless Sensor Networks, Infocom 05.
  4. D. Moore, J. Leonard, D. Rus, S. Teller. Robust distributed network localization with noisy range measurements, Proc. ACM SenSys 2004.

Routing (ROU)
  1. P. Bose, P. Morin, I. Stojmenovic and J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks 2001.
  2. Karp, B. and Kung, H.T. Greedy Perimeter Stateless Routing for Wireless Networks, MobiCom 2000 
  3. F. Kuhn, R. Wattenhofer, Y. Zhang, A. Zollinger. Geometric Ad-hoc routing: of theory and practice, in PODC'03.
  4. Kim, Y.-J., Govindan, R., Karp, B., and Shenker, S. On the Pitfalls of Geographic Face Routing, The third International workshop on foundations of mobile computing (DIAL-M-POMC), 2005.
  5. Hannes Frey, Ivan Stojmenovic, On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks, Mobicom’06.
  6. Ananth Rao, Christos Papadimitriou, Scott Shenker, and Ion Stoica, Geographical routing without location information, MobiCom 2003.
  7. Rodrigo Fonseca, Sylvia Ratnasamy, Jerry Zhao, Cheng Tien Ee and David Culler, Scott Shenker, Ion Stoica, Beacon Vector Routing: Scalable Point-to-Point Routing in Wireless Sensornets, NSDI'05. 
  8. Qing Fang, Jie Gao, Leonidas Guibas, Vin de Silva, Li Zhang, GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks, INFOCOM 2005.
  9. An Nguyen, Nikola Milosavljevic, Qing Fang, Jie Gao, Leonidas Guibas, Landmark selection and Greedy Landmark-descent Routing for Sensor Networks, INFOCOM’07
  10. M. Caesar, M. Castro, E. B. Nightingale, G. O'Shea, A. Rowstron, Virtual Ring Routing: Network Routing Inspired by DHTs, Sigcomm’06
  11. Yun Mao, Feng Wang, Lili Qiu, Simon S. Lam, Jonathan M. Smith, S4: Small State and Small Stretch Routing Protocol for Large Wireless Sensor Networks, NSDI’07.
  12. James Newsome, Dawn Song, GEM: Graph EMbedding for Routing and Data-Centric Storage in Sensor Networks Without Geographic Information, Proc. Sensys'03

Data Centric Routing (DRT)
  1. Chalermek Intanagonwiwat, Ramesh Govindan and Deborah Estrin, Directed diffusion: A scalable and robust communication paradigm for sensor networks, MobiCom '00
  2. Sylvia Ratnasamy,  Li Yin,  Fang Yu,  Deborah Estrin,  Ramesh Govindan,  Brad Karp,  Scott Shenker, GHT: A Geographic Hash Table for Data-Centric Storage, In First ACM International Workshop on Wireless Sensor Networks and Applications (WSNA) 2002
  3. David Braginsky, Deborah Estrin, Rumor routing algorithm for sensor networks, 1st ACM workshop on Wireless Sensor Networks, 2002
  4. Rik Sarkar, Xianjin Zhu, Jie Gao, Double Rulings for Information Brokerage in Sensor Networks, MobiCom '06

Multi Dimensional Data and Range Query (MRQ)
  1. Deepak Ganesan, Deborah Estrin and John Heidemann, DIMENSIONS: why do we need a new data handling architecture for sensor networks. ACM SIGCOMM workshop on hot topics in networks, 2002.
  2. X. Li, Y. J. Kim, R. Govindan, W. Hong, Multi-dimensional Range Queries in Sensor Networks, Proc. ACM SenSys 2003.
  3. J. Gao, L. Guibas, J. Hershberger, L. Zhang, Fractional Cascaded Information in a Sensor Network, IPSN'04. 
Data Aggregation (AGR)
  1. Samuel R. Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong. TAG: a Tiny Aggregation Service for Ad-Hoc Sensor Networks, OSDI 2002.
  2. Nisheeth Shrivastava, Chiranjeeb Buragohain, Divy Agrawal, Subhash Suri. Medians and Beyond: New Aggregation Techniques for Sensor Networks, SenSys '04.
  3. Suman Nath, Phillip B. Gibbons, Zachary Anderson, and Srinivasan Seshan. Synopsis Diffusion for Robust Aggregation in Sensor Networks. SenSys'04.
  4. Jeffrey Considine, Feifei Li, George Kollios and John Byers. Approximate Aggregation Techniques for Sensor Databases, ICDE 2004.

Boundary Detection (BDD)
  1. Stefan Funke, Christian Klein. Hole Detection or: "How much Geometry hides in Connectivity?", SoCG 2006.
  2. A. Kröller, S. P. Fekete, D. Pfisterer, S. Fischer, Deterministic boundary recognition and topology extraction for large sensor networks, SODA06. Video Link
  3. Yue Wang, Jie Gao, Joseph S.B. Mitchell. Boundary Recognition in Sensor Networks by Topological Methods, Mobicom06.
Coding in Storage and Communication (COD)
  1. A. G. Dimakis, V. Prabhakaran and K. Ramchandran, Ubiquitous Access to Distributed Data in Large-Scale Sensor Networks through Decentralized Erasure Codes, IPSN'05.
  2. Rudolf Ahlswede , Ning Cai , Shuo-yen Robert Li , Raymond W. Yeung. Network Information Flow, IEEE Transactions on Information Flow, 2000.
  3. C. Fragouli, J. Le Boudec, Jorg Widmer, Network coding: an instant primer.
  4. Abhinav Kamra, Vishal Misra, Jon Feldman, Dan Rubenstein, Growth Codes: Maximizing Sensor Network Data Persistence, SIGCOMM06.

Mobile Nodes (MOB)
  1. Baruch Awerbuch, David Peleg. Concurrent online tracking of mobile users, SIGCOMM'91.
  2. Jinyang Li, John Jannotti, Douglas S. J. De Couto, David R. Karger and Robert Morris. A scalable location service for geographic ad hoc routing, MobiCom'00.
  3. I. Abraham, D. Dolev, D. Malkhi. LLS : a Locality Aware Location Service for Mobile Ad Hoc Networks, DIALM-POMC 2004.
  4. Rik Sarkar, Jie Gao. Differential Forms for Target Tracking and Aggregate Queries in Distributed Networks, MOBICOM '10.

Gossip (GOS)
  1. David Kempe, Alin Dobra, Johannes Gehrke. Gossip-Based Computation of Aggregate Information. FOCS 2003.



Links:
  1. How to read a paper.

Similar and related courses at other Universities: