ST: Algorithmics of Wireless Ad Hoc Networks - CS 6/76995 
Spring 2008

MW  12:30 PM - 1:45 PM
MSB   276

Instructor Office Hours Email  Telephone

Dr. Feodor Dragan   Room 254 MSB  MW  1:45 - 2:15 PM, T 2:00 - 4:00 PM  and by appointment  dragan at cs dot kent dot edu (330) 672-9058

• Outline
  This course is graduate and research oriented. It addresses algorithmic aspects of mobile and wireless networks from a computer science standpoint. That is, the majority of topics are approached from a discrete structure, algorithmic, and protocol point of view. We will consider different algorithmic issues of  packet radio networks, mobile cellular systems, sensor networks,  wireless local area networks, and personal communication systems. We will get familiar with single hop and multi hop radio networks, topological design, routing, broadcasting and clustering in ad hoc mobile systems, searching and querying, location management techniques, power optimization issues, and quality of service.
• Prerequisites
  Data Structures -CS 33001,  Design & Analysis of Algorithms - CS 4/56101
• Text: No special Text-Book.
• Some material will be taken from

                   Handbook of Wireless Networks and Mobile Computing

      Ivan Stojmenovic, Ed., 2002, Wiley-Interscience,
      ISBN 0-471-41902-8,

• We will work on a number of recently published papers.
• Topics will include: This is a graduate level research oriented course. We will cover the following topics (the topics and order listed are tentative and subject to change).
• Short introduction to Wireless and Ad Hoc Networking
• Perspective on Mobile Ad Hoc Networks
• Underlying topologies for routing
          - Unit Disk Graphs,
          - Relative neighborhood graph,
          - Gabriel graph,
          - Yao graph,
          - Yao & Sink graph,
          - local Delaunay graph,
          - restricted Delaunay graph,
          - topologies based on connected dominating sets,
          - topologies based on mobile k-centers (routing backbones),
          - triangular systems (cellular networks),
          - etc.
• Topology features (sparseness, spanner, stretch factor, delay, guarantee delivery, bounded degree, planar, efficient localized construction)
• Maintaining the routing topology (planar backbone, connectors, cluster-heads, gateways, etc.)
• Routing strategies
          - Flooding,
          - Distance-Vector routing
          - Greedy routing
          - Compass routing, randomized compass routing
          - Face routing, adaptive face routing
          - Position based routing
          - O(1)-memory routing
          - Right-hand routing
          - Geometric forwarding
          - Greedy Perimeter Stateless Routing
          - Geometric Ad-Hoc Routing
          - Trajectory routing
          - Hierarchical and mobile clustering based routing
          - Dominating set based routing
          - Bandwidth-Efficient Link-State Routing
          - Link Reversal Routing
          - The Dynamic Source Routing
          - Labeling routing schemes
          - Power efficient routing
• Additional algorithmic problems (e.g., Minimum Forwarding Set Problem in Mobile Network Routing, Cell-Distance Computation for Location Updates in Cellular Networks, etc.)
• The Effects of Beaconing on the Battery Life of Ad Hoc Mobile  Computers
• Course Requirements

research project	25%
programming assignment	20%
class presentations	20%
participation	10%
quiz	15%

Participation: physical presence 5%, in class discussion 5%
Class presentation: average mark by other students
Quiz: questions from student presentations and suggestions 8% and prof lectures 7%
Research Project: literature review on presentation topic, thoughts on future research directions, report due will be announced

---

F. F. Dragan
dragan at cs dot kent dot edu
Spring 2008