CSE 494/598: Wireless Sensor Networks (Fall 2005)

Lecture M, W 3:15 P.M. - 4:30 P.M. BYAC 260
Graduate Line No 54001
Undergraduate Line No 24875
Instructor Sandeep Gupta
Office BY522
Email Sandeep.Gupta@asu.edu
Office Hours M 4:40 P.M. - 6:00 P.M., W 10:00 A.M. - 11:30 A.M.
TAs Valliappan.Annamalai@asu.edu, Guofeng.Deng@asu.edu
TA Office BY517
TA Office Hours Monday, Wednesday: 4:30 P.M. - 6:00 P.M.
Thursday: 1:00 P.M. - 3:00 P.M.


Course Description

Emergence of wireless sensors has paved the way for new applications especially in disciplines such as bioengineering, human computer interaction (HCI), mechanical and aerospace etc. In HCI, ubiquitous computing is an emerging field that focuses mainly on making the environment cater to the needs of a user with minimal disturbance to the user. One such example is inventory monitoring (Intel). In a warehouse each item in the inventory might check itself to see if it is in the proper shelf, if has gone past the expiration date etc. and then it might take corrective actions like notifying an inventory manager. Another example is a smart living space (Microsoft:Easy Living) where sensors are used for controlling the electrical appliances, based on user movement in an office room, providing access to computing resources based on user location etc. In bioengineering field, in-vivo and in-vitro sensors are used in remote health monitoring during disaster situations (iMPACT:Ayushman, Harvard: CodeBlue). They provide health data regarding a person to the doctors in a triage situation, based on the data the doctors can respond to patients who need immediate attention. Data from a set of sensors is more useful than data from a single sensor. Therefore, sensors deployed in the environment will form a Wireless Sensor Network (WSN) and provide sensed data.

In this course we will provide an introduction to Wireless Sensor Networks (WSN) and cover leading edge topics in WSNs. The goal of this course is to give an overview of fundamental problems in the area of WSNs. We will discuss the existing solutions for some of these problems. Data aggregation, information dissemination, security issues, power management, localization are some of the topics that will be covered in this course. We will also discuss issues that are specific to biosensors (both in-vivo and in-vitro). In this course, students will be assigned projects (Ubiquitous Computing related applications) that will involve implementation on Mica2 motes, from crossbow, and other mobile wireless sensors using a light weight event driven operating system called tinyos. Most of the materials covered will be from recent research work in wireless sensor networks. It will also involve a final project/technical paper that students can choose based on their field of interest. There will different grading scales for undergraduate and for students from other majors.

Why you should take this course?
  • Hands-on experience in programming sensor networks.
  • Access to sensor equipment that can be used to explore and work on sensor applications that interest you.
Note:
  • CSE background is not a prerequisite.
  • Good introductory course for students who are interested in working in the iMPACT lab

Grading Criteria:
Performance of CSE graduate students should be more than undergraduate students to achieve better grades.
ASU's Academic Integrity Policy


Overall score


Assignment Points Date Assigned Due Date
Quizzes 10
    Quiz 1
    Quiz 2
    Quiz 3
    Quiz 4
    Quiz 5
    Quiz 6
    Quiz 7
    Quiz 8
Homework (3 - 5) 15
    Homework1 08/31/05 09/07/05
    Homework2 09/15/05 09/28/05
    Homework3 10/17/05 10/24/05
Programming Assignment (2 - 4) 15
    Programming Assignment I 10/03/05 10/17/05
    Programming Assignment II 10/31/05 11/16/05
Project
Projects should be evaluated using at least two of the following:
  • Simulations
  • Analysis
  • Implementation.
25
Probable List of Projects
      Proposal(5)
      Midterm report(5)
      Presentation(5)
      Final report(10)
Midterm exam 15 10/26/05 (In class)
Final exam 20 Tue. 12/13/05 (10:00 A.M. - 11:50 A.M.)
Performance in assignments, projects and exams
Excellent     A+
Above average     A-/A
Average     B/B+

Other related course(s):


Reference Textbook

  • Fundamentals of Mobile and Pervasive Computing by Sandeep Gupta, Frank Adelstein, Golden Richard, Loren Schweibert. McGraw Hill Publication


Topics Covered
  • Sensor Networking: Model, Challenges, and Technologies
  • Resource-Efficient routing
  • Neighbor Discovery
  • Energy saving techniques
  • Self organization
  • Medium access control: different types of MAC protocols
  • Sensor networks design choices based on constraints set forth by applications
  • Tangible user interfaces (TUI)
  • Usefulness of sensors in pervasive/ubiquitous computing applications
  • Sensor networks in healthcare
  • Advanced topics: time synchronization, localization, distributed scheduling and data-centric routing
  • Security issues in sensor networks


Lecture Date Topic Synopsis Lecture Material
08/22/05 Introduction About course material Grading Student Interest
08/24/05 Context-awareness
  • Introduction to context
    • Need for context
    • Relationship between sensors and context
  • Introduction to sensors
  • Need for wireless sensors?
    • Advantages and disadvantages of wireless sensors
  • Why network sensors?
Lecture notes
08/29/05 WSN: Distributed System
  • Advantage of In-Situ processing
  • Distributed Computational Theory
  • Introduction to Distributed Algorithms
    • Broadcast (Dissemination)
    • Convergecast (Data Collection)
    • Spanning Tree Construction
  • Exercise: Develop a spanning tree construction algorithm
Lecture notes
08/31/05 Distributed computing
  • Introduction to distributed computing
    • Models of distributed computing
      • Shared memory/message passing
      • Asynchronous/synchronous (message passing)
    • Complexity
      • Message complexity
      • Time complexity
  • Distributed algorithm for constructing spanning trees
Lecture notes
09/07/05 Constructing spanning trees
  • Flooding based protocol for tree construction
    • Protocol description
      • Message types
      • Local data structure
      • Events and actions
    • Correctness proof
    • Complexity
      • Message complexity
      • Time complexity
Lecture notes
09/12/05 Modeling the benefits of data aggregation routing
  • What are AC & DC?
    • Address Centric Model (AC)
    • Data Centric Model (DC)
  • Different types of data aggregation
  • Comparative analysis between AC & DC
    • Assumptions
    • Notations
    • Performance metric
    • Source node placement model
      • Random Source (RS) placement model
      • Event-Radius (ER) placement model
    • Upper bound performance
    • Lower bound performance
  • Reference: Detailed descriptions of AC & DC can be found in Section 2 "Routing models" of Modelling data-centric routing in wireless sensor networks by Krishnamachari et al.
Lecture notes
09/14/05 Suboptimal tree construction methods
  • Center at Nearest Source (CNS)
  • Shortest Path Tree (SPT)
  • Greedy Incremental Tree (GIT)
  • Minimum-weight Spanning Tree (MST)
  • Reference: Detailed discriptions of suboptimal schemes CNS, SPT and GIT can be found in Section 3 "Data aggregation" of Modelling data-centric routing in wireless sensor networks by Krishnamachari et al.
Lecture notes
09/19/05 MST Construction Algorithms
  • Properties of MST
  • Kruskal's algorithm
  • Prim's algorithm
  • Centralized Baruvka's algorithm
    • Time Complexity
  • Distributed Baruvka's algorithm
    • Implementation Issues
  • References: Detailed descriptions of algorithms covered in the class can be found in Section 7.3 "Minimum spanning trees" in Algorithm Design -- Foundations, Analysis, and Internet Examples by M.T. Goodrich and R. Tamassia. Here is the link to some sample chapters of the book.
Lecture notes
09/21/05 Multicast tree construction techniques
  • Distributed implementation of Baruvka's algorithm
    • Identify component
    • Selection of minimum cross-edge of a component
  • Multicast tree construction algorithms for Internet
    • Reverse Path Forwarding (RPF)
    • Core-Based Tree (CBT)
  • An approximation algorithm for steiner tree
Lecture notes
09/26/05 Energy-efficient multicast/broadcast in WSNs
  • Euclidean geometry
  • Euclidean MST problem
    • MST in Gα (α is the path-loss constant)
    • A naive algorithm for constructing Euclidean MST
    • Approximation ratio of Euclidean MST is at least 6 for the minimum-energy broadcast tree problem
  • Energy-efficiency versus lifetime
  • References: Detailed description of Gα can be found in Section 2 "Preliminaries" of Minimum-energy broadcasting in static ad hoc wireless networks by Wan et al. The proof of the lower bound of Euclidean MST's approximation ratio can be found in Section 4 "Lower bounds on approximation ratio" of the same reference.
Lecture notes
09/28/05 Energy-efficient multicast/broadcast in WSNs Lecture notes
10/03/05 Programming assignment 1 and homework 2 solution
  • Programming assignment 1
  • Homework 2 solution
Lecture notes TOSSIM Presentation (PPT) Introduction to TinyOS (DOC)
10/05/05 Homework and Quiz Discussion Lecture notes
10/10/05 Maximum Lifetime Broadcast Tree (MLBT) Lecture notes
10/12/05 Maximum Lifetime Broadcast Tree (MLBT) (con't) Lecture notes
10/17/05 Discussion on programming assignment 1
Lecture notes
10/19/05 Coverage problem
  • Solution to programming assignment 1
  • Converage problem
    • Worst-case coverage
      • Breach
      • Maximum Breach Path
      • Voronoi Diagram
    • Best-case coverage
      • Support
      • Maximum Support Path
      • Delaunay Triangulation
  • Reference to the coverage problem: Worst and best-case coverage in sensor networks by Megerian et al.
Lecture notes
10/24/05 Midterm exam review
  • Miderm exam review
  • Solution to homework 3
Lecture notes
10/26/05 Midterm exam
10/31/05 RFID
  • Miderm solution
  • Programming assignment 2
  • RFID
11/02/05 RFID Lecture notes
11/07/05 RFID Lecture notes
11/09/05 RFID
  • Anti collision techniques
    • Problem
    • Solution
      • Probabilistic (randomization)
      • Deterministic protocol-Tree walking
  • Privacy preserving solutions for RFIDs
    • "Kill tag"
    • Faraday cage
    • Active jamming approach
    • Crypto based "smart" solutions
    • Blocker tag approach
  • References to RFID:
Lecture notes
11/16/05 Security
  • Network security basics
    • Confidentiality
      • Cryptography
        • symmetric key
        • public-key
    • Authentication
    • Message integrity
      • Digital signatures
      • Message digests
      • Hash function algorithms
    • Key distribution and certification
      • Key distribution center (KDC)
    • Access and availability
    • Reference: Chapter 7 Network security in Computer networking: a top down approach featuring the Internet (2nd edition) by Kurouse et al.
  • Security in WSNs
    • Goal
    • Approaches
      • Network wide shared key
      • Pair-wise key using PKI
      • Preconfigured pair-wise shared key
      • Bootstrapping keys using a trusted base-station
      • Random key predistribution
    • Reference: Security in wireless sensor networks by Perrig et al.
Lecture notes
11/21/05 Security Lecture notes
11/23/05 Routing Lecture notes
TinyOS References:
Additional References:








Home | Projects | People | Publications | Courses | Resources | Contact