Algorithms for Radio Networks
Lecture of Prof. Christian Schindelhauer
News
- 25.10.2011, 16:15, First Lecture
- 17.10.2011: Web-page online
- 16.12.2011 Certificate in websystem changed
Contents
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.
Organisation
Schedule
- Lecture
- Wednesday, 10:15 - 12:00 c.t., Building 101 - 01-016
- Tuesday, 16:15 - 17:00 c.t., Building 101 - 01-016
- Exercises
- Tuesday, 17:00 - 18:00 c.t., Building 101 - 01-016
Forum
Please use the forum1 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.
Slides
- Lecture 00: Organization, pdf2 (25.10.2011)
- Lecture 01-A: Basics of Radio Networks, pdf3 (25.10.2011)
- Lecture 01-B: Fourier-Transformation, pdf4 (26.10.2011)
- Lecture 01-C: Multiplexing, pdf5 (26.10.2011)
- Lecture 02-A: OFDM, pdf6 (2.11.2011)
- Lecture 02-B: Smart Antennas, pdf7 (3.11.2011)
- Lecture 02-C: Voronoi & Delauney, pdf8 (8.11.2011)
- Lecture 03-A: Voronoi Complexity, pdf9 (9.11.2011)
- Lecture 03-B: Handover, pdf10 (15.11.2011)
- Lecture 03-C: Frequency Assignment, pdf11 (15./16.11.2011)
- Lecture 04-A: Aloha, CSMA pdf12 (22.11.2011)
- Lecture 04-B: MACA pdf13 (23.11.2011)
- Lecture 04-C: MACAW pdf14(23.11.2011)
- Lecture 05-A: Flooding and DSR pdf15(29.11.2011)
- Lecture 05-B: Distance-Vector Routing, Link-State-Routing pdf16(30.11.2011)
- Lecture 05-C: AODV pdf17 (06.12.2011)
- Lecture 06-A: Link Reversal pdf18
- Lecture 06-B: OLSR pdf19
- Lecture 06-C: ZRP pdf20
- Lecture 06-D: Geometric Routing pdf21
- Lecture 07-A: Localization pdf22
- Lecture 07-B: Mobility Models pdf23
- Lecture 07-C: Random Mobility Considered Harmful pdf24
- Lecture 08-A: WSN Intro pdf25
- Lecture 08-B: WSN Problems pdf26
- Lecture 08-C: WSN: MAC STEM, Preamble Sampling, S-MAC pdf27
- Lecture 09-A: WSN MAC, T-MAC, B-Mac pdf28
- Lecture 09-B: WSN Data aggregation: Functions, Steiner trees pdf29
- Lecture 09-C: WSN Data aggregation: Approximation of Steiner trees pdf30
- Lecture 10-A: WSN Sensor Coverage pdf31
- Lecture 10-B: WSN Lifetime pdf32
- Lecture 10-C: WSN Power Management for Energy Harvesting pdf33
- Lecture 11-A: Routing as a Flow Problem pdf34
- Lecture 11-B: Network Coding pdf35
- Lecture 11-C: XOr in the Air, COPE pdf36
- Lecture 12-A: Security pdf37
- Lecture 12-B: Cryptography pdf38
- Lecture 12-C: Wireless Security pdf39
will appear here prior to the lecture
Recordings
- Lecture 01 (25.10.2011): 00,01-A Organizsaiton, Basics mp440
- Lecture 02 (26.10.2011): 01-A, 01-B Basics, Fourier mp441
- Lecture 03 (02.11.2011): 01-C, 02-A Multiplexing, OFDM mp442
- Lecture 04 (08.11.2011): 02-B, Smart Antennas mp443
- Lecture 05 (09.11.2011): 02-C, Voronoi Diagrams mp444
- Lecture 06 (15.11.2011): 03-A, Voronoi Diagrams mp445
- Lecture 07 (16.11.2011): 03-B, 03-C, Handover & Frequency Assignemt mp446
- Lecture 08 (22.11.2011): 04-A, MAC, Aloha mp447
- Lecture 09 (23.11.2011): 04-B, 04-C, MACA, MACAW mp448
- Lecture 10 (29.11.2011): 05-A: Flooding DSR mp449
- Lecture 11 (30.11.2011): 05-B: DSR Cache, Distance-Vector mp450
- Lecture 12 (06.12.2011): 05-C AODV mp451
- Lecture 13 (07.12.2011): 06-A, 06-B, 06-C Link-Reversal, OLSR, ZRP mp452
- Lecture 14 (13.12.2011): 06-D Geometric Routing mp453
- Lecture 15 (14.12.2011): 07-A Localization mp454
- Lecture 16 (20.12.2011): 07-B Mobility Models mp455
- Lecture 17 (21.12.2011): 07-C Mobility considered harmful mp456
- Lecture 18 (10.01.2012): 08-A Wireless Sensor Networks, Introduction mp457
- Lecture 19 (11.01.2012): 08-A, 08-B, Wireless Sensor Networks, Introduction, Problems mp458
- Lecture 20 (17.01.2012): 08-C WSN-MAC I mp459
- Lecture 21 (17.01.2012): 09-A, 09-B, WSN-MAC II, Data Aggregation: B-Mac mp460
- Lecture 22 (24.01.2012): 09-B, 10-A, Data Aggregation: Voronoi-Trees, Approximationsmp461
- Lecture 23 (25.01.2012): 10-B, 10-C WSN, Sensor Coverage, Lifetime mp462
- Lecture 24 (31.01.2012): 10-C, 11-A Lifetime Energy Harvesting mp463
- Lecture 25 (01.02.2012): 11-A, 11-B, Energy Harvesting, Routing as a flow Problem mp464
- Lecture 26 (07.02.2012): 11-C Network Coding mp465
- Lecture 27 (08.02.2012): 11-C, 12-A: Network Coding, Security mp466
- Lecture 28 (14.02.2012): 12-A: Security mp467
- Lecture 29 (15.02.2012): 12-B, 12-C: Cryptography, Wireless Security mp468
Exercises
Submit solutions over our websystem69. Deadline for exercise submission is Monday evening 11:59 pm.
- Exercise 1 pdf70 (02.11.2011)
- Exercise 2 pdf71 (09.11.2011)
- Exercise 3 pdf72 (16.11.2011)
- Exercise 4 pdf73 (24.11.2011) (Diagrams: path74, signal strength75, Scilab 76code: handoff_simulator.sce77)
- Exercise 5 pdf78 (01.12.2011)
- Exercise 6 pdf79 (10.12.2011) (updated!)
- Exercise 7 pdf80 (16.12.2011)
- Exercise 8 pdf81 (22.12.2011)
- Exercise 9 pdf82 (13.01.2012)
- Exercise 10 pdf83 (24.01.2012)
- Exercise 11 pdf84 (31.01.2012) (Diagram: Nodes-Free Cells 85)
- Exercise 12 pdf86 (07.02.2012)
- Exercise 13 pdf87 (14.02.2012)
Exam
There will be oral exams at the end of the lecture. Students are allowed to use a selection of their exercise solutions in the exam. To be selected the solution should be submitted to the tutor during the semester within the deadline, also a review has to be done on the solutions of five peers. Furthermore, non relevant or wrong solutions may not be selected.
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
- current research works in this area