Fall 2009 Wireless and Mobile Networks

Fall 2009 CSE590 Wireless and Mobile Networks

Location and Hours

Tuesday, Thursday 12:50-2:10pm @ CS2311.

Instructors:

Instructor: Prof. Jie Gao, 1415 Computer Science Building. Email: jgao at cs dot sunysb dot edu. Office hour: Thursday 2:15-4:15pm or by appointment.

Grader: Madhav Reddy, madhav.rbv at gmail.com

Announcements:

Project proposal (1 or 2 pages) is due on Nov 3rd. Please submit your proposal on BLACKBOARD. You MUST specify an objective in your proposal. Your final proposal will need instructor's approval. See below for project suggestions.
Homework 4 is out. Solutions for homework 1 and 2 are posted on blackboard.
Midterm is on Oct 22nd in class from 12:50-2:10 at CS 2311. It is an OPEN BOOK, OPEN NOTES exam. You may bring a calculator. NO computer or Internet is allowed. No collaboration/discussion is allowed. On Oct 20th, we have a review session in which the grader will go through homework problems and you will be given a practice midterm (that was used for an earlier undergraduate course). The difficulty of the real midterm will be harder than the practice midterm and simpler than the homework.
Homework 3 is out. Homework 3 is due on Oct 8th in class.
Homework 2 is due on the 29th. Please submit to the instructor's mailbox by 5pm on 29th (as we do not have lectures on that day).
Homework 1 is due on the 17th.
Room changed to CS2311! Except on 9/17 we meet at Stony Brook Union 237 for all other lectures we will meet at CS2311.
Make up lecture on 9/4/09 Friday 9-10am @ CS2311.
The first class is on Sep 1st. See you there!

Course Description:

This course is a 3-credit graduate course on wireless and mobile networks. Topics include: wireless communication fundamentals: wireless signal transmission, coding, multiplexing. Link, network and transport layer protocols for wireless and mobile networking: medium access control, transmission scheduling, wireless capacity, protocols for wireless multi-hop networks. Cellular networks. Wireless LANs: mobile IP, TCP over wireless networks. Mobile applications. Localization and location management, Network coding. Wireless security.

Prerequisite:

Computer Networks (CSE310) and Operating Systems (CSE306) or equivalent.

Grading and Requirements:

Class attendance: 10%. Attendance is taken at random sessions.
Homework: 30%.
Midterm: 30%.
Final project: 30%. Project topic suggestion: read MobiCom papers from 2000-2009. Idenfify a paper on which you can improve. A 2-page project proposal is due 1 week after midterm. Project report is due Dec 21st. A bi-weekly progress report (1-page long) is required after the proposal till the project due date. Submit your progress report to blackboard by Friday night. A final presentation is scheduled in the last class. No collaboration is allowed on projects.
There is no final exam.
Late policy: each student may submit one homework 1 day late without penalty. Please inform the instructor/grader in advance to use your 1 day buffer. Additional delay is penalized by 20% per day.

Homework grading policy:

Grading criteria:

Correctness and clarity for mathematical questions.
Clarity and thoroughness for design or theory questions.

Tip: Start your assignments early , Don't wait until the deadline.

Homework Regrade Policy:

After you receive your graded homework and the sample solutions, you may believe that we made an error in grading your homework. If so, and if you feel the error is significant enough to merit additional attention, you may submit your graded homework with a written request for reconsideration in the instructors mailbox. You must explain clearly and concisely how you believe that we made a mistake. When a member of the course staff regrades a problem, our goal will be to see if we applied our criteria correctly to the homework paper in question. In fairness to all students, we will not reexamine the systematic grading criteria we applied to the problem set. Please be courteous to the course staff and bear in mind that a few points difference on a few homework solutions should not change your final letter grade in the course.

Textbooks:

I will use papers/handout lecture notes for most of the lectures. Here are some recommended textbooks:

[Sc] Mobile Communications, Jochen Schiller, 2nd edition, Addison Wesley.
[PK] Principles of Wireless Networks, Kaveh Pahlavan, Prashant Krishnamurthy, Prentice Hall.
[TV05] Foundamentals of Wireless Communication, David Tse and Pramod Viswanath, Cambridge University Press, 2005. An electronic version is available here.
Wireless Networking, Anurag Kumar, D. Manjunath, Joy Kuri, Morgan Kaufmann.

Topics of this course include: Introduction to wireless networks (1 lecture), characteristics of wireless transmission/physical layer (3 lectures), medium access control (MAC) (6 lectures), routing and transport layer (4 lectures), location management (3 lectures) and advanced topics.

Syllabus:

	Slides/Notes	Lecture Topics	Required Reading
09/01	Lecture 1	Driving Applications; Challenges: Wireless; Mobility; Portability. Layered Network Architecture. Course overview.
09/03	Lecture 2	Signals, fourier transform, wireless channels.	Chapter 2 of [TV05] and handout (selected pages from chapter 2 of [PK]), fourier transform.
09/04 9-10am @ CS2311	Lecture 3	Modulation	Handout (selected pages from chapter 2 of [Sc]).	Homework 1 out what is dB?
09/15 @ CS2311	Lecture 4	Spread spectrum, Reed Solomon code	Section 3.2, 3.3 of [TV05] (this book has a lot of details, you only need to get the overall idea), lecture notes on DSSS, Reed-Solomon codes,
09/17 @ Stony Brook Union 237	Lecture 5	ISI problem, Viterbi algorithm, MAC introduction	Walsh code, Viterbi algorithm, handout (selected pages from [PK]).	Homework 1 due Homework 2 out
09/18 9-10am @ CS2311	Lecture 6	ALOHA, slotted ALOHA	Analysis of ALOHA and slotted ALOHA
09/22 @ CS2311	Lecture 7	MAC	MAC, handout on selected pages from [PK]
09/24	Lecture 8	Hidden terminal problem, 802.11, mesh network	802.11 paper, RTS/CTS
09/29	No class, following a Monday schedule			Homework 2 due (submit to instructor mailbox by 5pm) Homework 3 out
10/01	Lecture 9	Capacity	Lecture notes by Nitin Vaidya
10/06	Lecture 10	Multi-channel	Capacity of ad hoc networks, [BCD04]
10/08	Lecture 11	Location management, mobile IP	Location management, handout (selected pages from [Sc])	Homework 3 due
10/13	Lecture 12	Routing	Link Reversal Protocol (See below for more on link reversal algorithms), ETX metric, DSDV, Review.	Homework 4 out
10/15	Lecture 13	Geographical routing in ad hoc networks
10/20	Review session	Homework problem review + practice midterm, and solution
10/22	Midterm in class			Homework 4 due
10/27	Lecture 14	DSR, Opportunistic routing
10/29	Lecture 15	Opportunistic routing
11/03	Lecture 16	GPS		Project proposal due
11/05	Lecture 17	Rigidity Theory
11/07	No lecture
11/12	Lecture 19	Location service
11/17	Lecture 20	Location service
11/19	Lecture 21	TCP
11/24	Lecture 22
11/26	No class
12/01	Lecture 23
12/03	Lecture 24
12/08	Project presentation
12/10	Project presentation

Project suggestions:

Programming projects: implement/compare exisitng protocols.
Survey:

Reading List:

MAC:

[BDSZ94] "MACAW: Media Access Protocol for Wireless LANs," V. Bharghavan and A. Demers and S. Shenker and L. Zhang, Proceedings of the ACM SIGCOMM Conference, 1994.
[CWKS97] "IEEE 802.11 Wireless Local Area Networks", B. Crow, I. Widjaja, J. Kim, P. Sakai, IEEE Communications Magazine, Volume: 35 Issue: 9 , Sept. 1997.
[BCD04] "SSCH: Slotted Seeded Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-Hoc Wireless Networks," Victor Bahl, Ranveer Chandra, and John Dunagan, Proc. of ACM Mobicom 2004, Sept.-Oct. 2004.

Capacity:

[GK00] "The Capacity of Wireless Networks," P. Gupta, P.R. Kumar. IEEE Transactions on Information Theory, pp. 388-404, vol. IT-46, no. 2, March 2000.

Ad hoc networks:

Building a Rural Wireless Mesh Network: A do-it-yourself guide to planning and building a Freifunk based mesh network, wiki.
Link Reversal Algorithms:

The original paper: Gafni and Bertsekas, Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology, IEEE Transactions on Communications, Vol Com-29, No.1, Jan, 1981.
The analysis of the convergence time in full/partial link reversal algorithm: Busch, Surapaneni, Tirthapura, Analysis of Link Reversal Routing Algorithms for Mobile Ad Hoc Networks, SPAA, 2003.
Find the minimum set of links to reverse so as to re-establish a DAG: Sukhamay Kundu, A distributed O(|E|) Algorithm for Optimal Link-Reversal, Distributed Computing and Networking, 2009.

Geographical routing:

[Karp00] Karp, B. and Kung, H.T., Greedy Perimeter Stateless Routing for Wireless Networks, in Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), Boston, MA, August, 2000, pp. 243-254. GPSR: one of the first on geographical routing.

Network coding:

[Fragouli06] C. Fragouli, J. Le Boudec, Jorg Widmer, Network coding: an instant primer. A (very) short survey of network coding and applications.
[Katti06] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, J. Crowcroft, XORs in The Air: Practical Wireless Network Coding, Sigcomm’06. Use network coding in wireless networks.
[Katti07] Sachin Katti, Shyamnath Gollakota, Dina Katabi, Embracing Wireless Interference: Analog Network Coding, SIGCOMM 2007. Wireless interference is in fact network coding with the analog signals. The paper uses wireless interference intentionally to improve system throughput.
[Katti08] Sachin Katti, Dina Katabi, Hari Balakrishnan, Muriel Medard, Symbol-level Network Coding for Wireless Mesh Networks, SIGCOMM 2008. The scheme in this paper patches up uncorrupted portions of packets delivered by lossy wireless channels.
[Gollakota08] Shyamnath Gollakota, Dina Katabi, ZigZag Decoding: Combating Hidden Terminals in Wireless Networks, SIGCOMM 2008. Combat hidden terminal problem in wireless networks. When there are collisions.

Localization:

[Bahl00] P. Bahl V. N. Padmanabhan, RADAR: An In-Building RF-Based User Location and Tracking System, IEEE INFOCOM 2000

Other courses and acknowledgements:

Yale: Mobile computing and Wireless Networks.
UIUC: Wireless Networks.