Algorithms for Radio Networks

Lecture of Christian Schindelhauer

News

• 07.10.2013 web-pages online
• 21.10.2013, 10:15, first lecture
• 16.12.2013: Websystem running under new Domain and new Certificate
• 30.01.2014: Begin of teaching evaluation

Contents

This lecture is directed at master students in embedded systems and computer science. It consists of the following three parts: Introduction to radio networks, localization algorithms, and MIMO techniques.

Radio Networks may be cellular networks, ad hoc networks, hybride networks, or wireless sensor networks. For these types of networks we present and discuss algorithms.

Cellular networks are widely von from mobile telephone networks and wireless local area networks. All communication is redirected over base stations. Direct communications between the participants of the network does not take place. Topics here are OFDM, Smart Antennae, MIMO, Voronoi graphs, Handover problems and the frequency assignment problem.

Ad hoc networks do not use any extra infrastructure. Participants communicate directly and provide the routing necessary to deliver messages over multiple hops. We discuss medium access, and the main routing algorithms. Furthermore we will have a look into mobility of participants resulting in so-called mobile ad hoc networks.

Wireless sensor networks connect devices with sensors and actuators. Such networks use only relatively simple hardware for computation and communication. The key problem is the energy consumptions since such networks have to be sustained for months and years on single cell batteries. We discuss this energy problem and ways to overcome it like data aggregation and energy harvesting. Besides these topics we also present network coding, security in networks, and multiplexing techniques.

Organization

Schedule

• Lecture
  • Monday, 10:15-12:00, room 101- 01-016
  • Friday, 10:15-12:00, room 101-01-016
• Exercises
  • Friday, 10:15-12:00, room 101-01-016

Dates

• Mo 21.10.2013 Lecture Organization
• Fr 25.10.2013 Lecture Fourier-Transformation, Multiplexing
• Mo 28.10.2013 Lecture OFDM
• Fr 01.11.2013 Holiday
• Mo 04.11.2013 Lecture Handover, Frequency Assignment
• Fr 08.11.2013 Exercise Basics
• Mo 11.11.2013 Lecture Medium Access
• Fr 15.11.2013 Lecture Medium Access, Intro WSN, MAC for WSN
• Mo 18.11.2013 Lecture MANET
• Fr 22.11.2013 Exercise MANET
• Mo 25.11.2013 Lecture MANET
• Fr 29.11.2013 Lecture WSN
• Mo 02.12.2013 Lecture WSN
• Fr 06.12.2013 Exercise
• Mo 09.12.2013 Lecture WSN
• Fr 13.12.2013 canceled
• Mo 16.12.2013 Lecture Lifetime, Coverage (online lecture)
• Fr 20.12.2013 Lecture Lifetime, Coverage (online lecture)
• Fr 10.01.2014 Lecture Energy Harvesting
• Mo 13.01.2014 Lecture Geographic Routing
• Fr 17.01.2014 Lecture/Exercise Maximum flow minimum cut
• Mo 20.01.2014 Lecture Network Coding
• Fr 24.01.2014 Lecture Security
• Mo 27.01.2014 Lecture Localization
• Fr 31.01.2014 Lecture/Exercise Localization
• Mo 03.02.2014 Lecture Localization
• Fr 07.02.2014 Lecture MIMO
• Mo 10.02.2014 Lecture MIMO
• Fr 14.02.104 Exercise MIMO

Forum

Please use the forum¹ for general questions about the lecture. Maybe your question and the answer is probably interesting to other students. Please feel free to start new threads and interesting discussion.

Material

Please ask us for a password to access the files. It will be presented in the first lecture. The annotated slides appear also on this page asap.

Slides (all slides², all annotated slides³)

• 00: Organization (version 20.10.2013, lecture 21.10.2013, slides⁴)
• 01-A: Introduction and Basics (version 20.10.2013, lecture 21.10.2013,slides⁵, annotated slides⁶)
• 01-B: Fourier-Transformation (version 20.10.2013, lecture 25.10.2013,slides⁷, annotated slides⁸)
• 01-C: Multiplexing (version 20.10.2013, lecture 25./28.10.2013,slides⁹, annotated slides part 1¹⁰, annotated slides part 2¹¹)
• 02-A: Orthogonal Frequency Division Multiplexing (version 24.10.2013, lecture 28.10.2013 slides¹², annotated slides¹³)
• 02-B: Handover (version 24.10.2013, lecture 04.11.2013slides¹⁴, annotated slides¹⁵)
• 02-C: Frequency-Assignment (version 24.10.2013, lecture 04.11.2013 slides¹⁶, annotated slides¹⁷)
• 03-A: Medium Access, Aloha, CSMA (version 04.11.2013 slides¹⁸, annotated slides¹⁹)
• 03-B: MACA (version 04.11.2013 slides²⁰, annotated slides²¹)
• 03-C: MACAW (version 15.11.2013 slides²²,  annotated slides²³)
• 03-D: Introduction to Wireless Sensor Networks (version 14.11.2013 slides²⁴,  annotated slides²⁵))
• 03-E: MAC for WSN (version 14.11.2013, slides²⁶,  annotated slides part 1²⁷,  annotated slides part 2²⁸)
• 04: Routing, introduction, MANET routing, Flooding, DSR, AODV  (version 26.11.2013, slides²⁹, annotated slides part 1³⁰, annotated slides part 2³¹)
• 05: Routing, Link Reversal, OLSR, ZRP (version 01.12.2013, slides³², annotated slides)³³
• 06: Data aggregation in Wireless Sensor Networks (version 08.12.2013, slides³⁴)
• 07: Wireless Sensor Networks, Coverage, Lifetime and Energy Harvesting (version 09.01.2014, full slides³⁵, slides from the online lecturepart 1 coverage³⁶, part 2 lifetime³⁷, annotated slides³⁸)
• 08: Geographic Routing (version 10.01.2014 slides³⁹, annotated slides⁴⁰)
• 09: Network Coding (version 16.01.2014 slides⁴¹,  annotated slides part 1⁴²,part 2⁴³)
• 10: Security (slides⁴⁴)
• 11: Localization (version 31.01.2014 slides⁴⁵, annotated slides part 1⁴⁶, part 2⁴⁷, part 3⁴⁸, part 4⁴⁹)
• 12: MIMO (version 10.02.2014 slides⁵⁰, annotated slides⁵¹)

Recordings

• 21.10.2013: Organization, Basics of Wireless Communication (1st part⁵², 2nd part⁵³)
• 25.10.2013: Fourier-Transformation, Multiplexing (mp4⁵⁴)
• 28.10.2013: Multiplexing, OFDM (mp4⁵⁵)
• 04.11.2013: Handover, frequency assignment (mp4⁵⁶)
• 11.11.2013: Medium Access (mp4⁵⁷)
• 15.11.2013: Medium Access, Introduction to Wireless Networks (mp4⁵⁸)
• 18.11.2013: Medium Access for Wireless Sensor Networks, Introduction to Routing (mp4⁵⁹)
• 25.11.2013: Routing in the Internet and in MANETs (mp4⁶⁰)
• 29.11.2013: Routing in MANETs (mp4⁶¹)
• 02.12.2013: Data Aggregation(mp4⁶²)
• 09.12.2013: Data Aggregation (mp4⁶³)
• 16.12.2013: Coverage, virtual lecture (recording only)(mp4⁶⁴)
• 20.12.2013: Lifetime, energy harvesting, virtual lecture (recording only)(mp4⁶⁵)
• 09.01.2014: Recap of coverage and lifetime, energy harvesting (mp4⁶⁶)
• 13.01.2014: Geometric Routing (mp4⁶⁷)
• 17.01.2014: Networking as a flow problem (mp4⁶⁸)
• 20.01.2014: Network Coding (mp4⁶⁹)
• 27.01.2014: Localization: Measuring (mp4⁷⁰)
• 31.01.2014: Localization: Dead Reckoning, Triangulation (mp4⁷¹)
• 03.02.2014: Localization: Multilateration (mp4⁷²)
• 07.02.2014: Anchor-free Localization (mp4⁷³), MIMO (mp4⁷⁴)
• 10.02.2014: MIMO (mp4⁷⁵)

Exercises

Submit solutions over our websystem⁷⁶. Deadline for exercise submission is Thursday evening 11:59 pm. Students may volunteer to present a solution one week before the exercise. For this, please contact your tutor. Presented solutions will be a part of the oral exam and it is mandatory to submit for the presentation of the written solution over the web-system.

• Exercise 1 pdf⁷⁷ (08.11.2013)
• Exercise 2 pdf⁷⁸ (22.11.2013)
• Exercise 3 pdf⁷⁹ (30.11.2013)
• Exercise 4 pdf⁸⁰ (14.01.2014)
• Exercise 5 pdf⁸¹ (25.01.2014)
• Exercise 6 pdf⁸² (10.02.2014)

Exam

There will be oral exams at the end of the lecture. Please register for the exam until 31.01.2014 using the online system. The exam dates are 

• 18.02.2014
• 19.02.2014
• 05.03.2014
• 26.03.2014
• 27.03.2014

Literature

• Murthy, Manoj, Ad Hoc Wireless Networks, Prentice Hall 2004
• Ilyas, Mahgoub, Handbook of Senso Networks: Compact and Wired Sensing Systems, CRC Press
• Agrawa, Zeng, Introduction to Wireless and Mobile Systems, Thomson, 2003
• Schiller, Mobile Communications, Addison-Wesley, 2000
• Karl, Willig, Protocols and Architectures for Wireless Sensor Networks, Wiley, 2005
• Zhao, Guibas, Wireless Sensor Networks – An Information Processing Approach, Morgan Kaufmann, 2004
• Yu, Prasanna, Krishnamachari, Information Processing and Routing in Wireless Sensor Networks, 2006
• Wu, Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks
• Boukerche Handbook of Algorithms for Wireless Networking and Mobile Computing, CRC 2005
• Perkins, Ad Hoc Networking, Addison-Wesley, 2000

and current research papers to be announced in the lecture