ST: Algorithmics of Wireless Ad Hoc Networks - CS
6/76995
Spring 2014
Tuesday 5:30 PM - 8:15
PM
HDN - 107
Instructor
Office Hours
Email
Telephone
|
Dr. Feodor
Dragan
Room 254 MSB
T 3:00 - 5:00 PM, W 2:00 - 3:45 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 other personal communication systems. We will get familiar
with single hop and multi hop wireless 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 23001, 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 2014