CSE 592: Advanced Topics in Ad Hoc and Sensor Networks

Fall, 2008
Tuesday-Thursday, 3:50-5:10pm
Chemistry 124

Office Hours

Announcements

• The paper that discussed the dynamic programming for the k-median problem in undirected trees. In short, the mistake I made in class is assuming that T_u has no caches. In fact, we pick u as the leftmost *highest* cache node (i.e., the first encountered in depth-first search) and then, reduce the problem of finding t caches in T_v into the problems of (i) finding i caches in T_u, and (ii) (t-i) caches in R_{v,u}, under the _pretext_ that there are no caches on the path u to v. When solving for R_{v,u}, we do NOT need to impose the condition that the path (v,u) is cache free (the reason for this is tricky).
• The presentation of 12/2 will be on 11/25 instead.
• HW 4 available. Last presentation (complexity in SINR) Slides.
• HW 1 solutions. HW 2 solutions. HW 3 solutions.

Topics, Slides, References, and Presentation Suggestions

• Overview and Routing in Ad Hoc Wireless Networks.
  Slides;
  References.
  Nancy Lynch's (MIT) course notes.
• Location-Based Routing, Location Based Services.
  Slides;
  References;
• Topology Control
  Notes.
  References.
• MAC, TDMA Scheduling.
  Slides. JRCAS Slides (will be updated).
  References.
• Caching in Ad Hoc/Sensor Networks Notes. References.
• Sensor Network Databases (SQL in sensor networks, Data streams)
• Other Topics/Applications (Localization, RFIDs, Target Tracking, etc.)

Tentative Presentation Schedule

• 23rd September: Distributed Construction of Planar Spanner and Routing for Ad Hoc Networks, Li et al. Presentation
• 25th September: Fatima Zarinni, "A Scalable Location Service for Geographic Ad Hoc Routing", Li et al, MobiCom 2000.
• 7th October: Minnu Tom, "Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications", Stoica et al., SIGCOMM 2001.
• 28th October: Nidhi Pai, "Distributed construction of connected dominating set", P. Wan, K. Alzoubi, O. Frieder.
• 30th: October: Madhavi Wagle, "Barrier Coverage with Sensor Networks", Kumar et al., MobiCom 2005.
• 11th November: Karthikeyan A Srinaivasan, "SSCH: Slotted Seeded Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-Hoc Wireless Networks", P Bahl et al, Mobicom 2004.
• 13th November: Giordano Fusco, "Complexity in Geometric SIMR", Goussevskaia et al., MobiHoc 2007.
• 18th November: Aneeta Bhattacharyya, J. Monks, V. Bhargavan, and W-W. Hwu, "Power Controlled Multiple Access Protocol for Wireless Packet Networks," IEEE Infocom, 2001.
• 15th Novemeber: Bhuvan Mital, "Benefit-based data caching in networks", Tang et al., ICNP 2005.
• 4th December: Xiaoxiao Hou. "Synopsis Diffusion for Robust Aggregation in Sensor Networks", Nath et al., Sensys 2004.
• 9th December: Kristov Widak. "Starvation mitigation through multi-channel coordination in CSMA multi-hop wireless networks", Mobihoc 2006.

Homeworks

Course Description

The course will cover the area of wireless ad hoc networks, sensor networks, and sensor network databases. Tentatively, we will focus on routing algorithms, topology control, caching, data management and querying, and applications. The course will have an algorithmic and possibly, database flavor. The course will be based mostly on current literature, supplemented by occasional textbook readings related to background materials. But there will be no primary textbook. Evaluation will be based on a few short homework assignments, class presentations, and possibly a course project (done in groups of 1-2 students). Most likely, there will be no exams. Prerequisites: Undergrad networks and algorithms, or consent of instructor. | Credits: 3.

Course Grading

• Assignments: 60% (some may be like take-home examinations)
• Presentation: 25%
• Attendance in Student Presentations: 15%.