Transcript Kein Folientitel

CPSC 689: Discrete Algorithms
for Mobile and Wireless Systems
Spring 2009
Prof. Jennifer Welch
Overview
 Mobile wireless systems are moving into your
neighborhood! Robots, vehicular networks, sensor
networks, etc.
 How can we ensure they are correct and properly
evaluate their performance? What are inherent
limitations on solvability of problems in this domain?
 We will study algorithms for such systems
emphasizing those with well-defined correctness and
performance properties:
 MAC layer, localization, time synchronization, topology
control, routing, location services, middleware, applications
Discrete Algs for Mobile Wireless Sys
2
Course Goals
 Understand nature of wireless ad hoc network setting
 what can be assumed about correctness, reliability, and
performance?
 what are appropriate complexity measures?
 Identify important, well-defined problems that can be
solved with distributed algorithms
 communication, synchronization, localization, etc.
 Learn about existing algorithms for these problems
 identify where more algorithmic work is needed
 Identify inherent limitations (lower bounds, impossibility
results)
 Identify useful abstraction layers for programming wireless
networks
Discrete Algs for Mobile Wireless Sys
3
Motivation
 Mobile ad hoc network: collection of computing
devices (nodes) that communicate via wireless
broadcasts
 Nodes may have sensors and/or actuators
 Nodes move spontaneously or under
advice/control from software
 No available infrastructure
 Possible uses: rescue workers, robots exploring
a new location, aircraft over ocean
Discrete Algs for Mobile Wireless Sys
4
Motivation
 Programming such networks is hard!
 Mobility, nodes leaving and joining, failing
and recovering
 Need good distributed algorithms for
problems from basic communication to high
level applications
 reliable communication, establishing and
maintaining structures, providing layers of
abstraction, managing data and resources,
controlling and coordinating physical entities
Discrete Algs for Mobile Wireless Sys
5
Approach
 We will take a theoretical, mathematical
viewpoint:





define clean computational models
define abstract problems
describe algorithms clearly
analyze complexity of algorithms
identify inherent limitations
 Try to develop a theory that "fits" practical
assumptions
Discrete Algs for Mobile Wireless Sys
6
Challenge
 Practical algorithms often provide few hard-andfast guarantees
 hard to get them, since network is so poorly behaved
 Theoretical algorithms usually can give good
guarantees
 but sometimes based on questionable assumptions
 Can we find algorithms that work in practice and
still satisfy some provable guarantees?
Discrete Algs for Mobile Wireless Sys
7
Schedule
 Part I: Basics




physical layer
MAC layer
time synchronization
localization
 Part II: Communication
 global broadcast
 routing
 location services
Discrete Algs for Mobile Wireless Sys
8
Schedule
 Part III: Building and Maintaining Network
Structures





topology control
clustering
unit disk graphs and related models
wakeup problem
maximal independent sets, coloring, etc.
Discrete Algs for Mobile Wireless Sys
9
Schedule
 Part IV: Middleware
 local infrastructure
 token circulation, leader election, resource allocation,
group communication
 compulsory protocols
 virtual node layers
 Applications
 data aggregation
 implementing atomic memory
 robot and vehicle motion coordination
Discrete Algs for Mobile Wireless Sys
10
How the Class Will Work
 Source material consists of:
 papers in the research literature (available
through the course web page)
 drafts of two books (paper copies will be made
available)
 For each class, we will read 1 or 2
papers/book chapters and discuss them
Discrete Algs for Mobile Wireless Sys
11
Course Requirements
 Do the assigned reading before each class:
 turn in a 1-page summary of each paper at the
beginning of class
 may have a few questions to answer also
 Attend each class and participate in the
discussion
 Term project: go into more depth with
supplementary reading or tackle an original
research problem
 written report
 oral presentation
Discrete Algs for Mobile Wireless Sys
12