iMPACT - Mobile Computing at ASU

Home

Projects

People

Courses

Contact

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	Min-energy vs. max-lifetime Link-based model vs. node-based model Problems MEBT MLBT MEMT MLMT Broadcast Incremental Power (BIP): an approximation algorithm to MEBT References: BIP: On the construction of energy-efficient broadcast and multicast trees in wireless networks by Wieselthier et al. Definition of approximation ratio: Chapter 35 "Approximation algorithms" in Introduction to Algorithms by Cormen et al., The MIT Press 2001 Energy related problems, link-based and node-based models: Energy-efficient multicast protocols (a book chapter) by Gupta et al.	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	Homework 2: Solution to question 5 Quiz 6 solution discussion Quiz 7 solution discussion Introduction to MLBT Reference: MLBT problem: Maximizing static network lifetime of wireless broadcast adhoc networks by Kang et al.	Lecture notes
10/10/05	Maximum Lifetime Broadcast Tree (MLBT)	Network model Lifetime of link and node Lifetime of multicast tree In terms of lifetime of nodes In terms of lifetime of links EDEN: Equially distributed energy network Results: MST is an optimal solution to MLBT in case of EDEN Reference (repeat): MLBT problem: Maximizing static network lifetime of wireless broadcast adhoc networks by Kang et al.	Lecture notes
10/12/05	Maximum Lifetime Broadcast Tree (MLBT) (con't)	Answer to Quiz 8 A 2-step MLBT algorithm Converage problem Reference to the coverage problem: Worst and best-case coverage in sensor networks by Megerian et al.	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	Project proposal presentation RFID References to RFID: RFID: A key to automating everything by Roy Want Communications of the ACM, September 2005, Vol. 48, No. 9, RFID RFID systems and security and privacy implications by Sarma et al. Security and privacy aspects of low-cost radio frequency identification systems by Weis et al.	Lecture notes
11/07/05	RFID	Smart tags Significance of smart tags: Automatic identification of objects and people Bridging physical and virtual worlds References to RFID: Basics of RFID technology by Harmon (ppt) Security and privacy for RFID systems by Kaliski (ppt) Smart tags: the distributed memory revolution by Peter Hewkin Future automatic identification technologies by Peter Hewkin Bridging physical and virtual worlds with electronic tags by Want et al. People, places, things: web presence for the real world by Kindberg et al.	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: The blocker tag: selective blocking of RFID tags for consumer privacy by Juels et al.	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	Security in WSN Implementation issues Localization Reference: MAX: Human-centric search of the physical world by Yap et al.	Lecture notes
11/23/05	Routing	Time synchronization Reference: Time synchronization for wireless sensor networks by Elson et al. (Slides) Crosslayer scheduling Reference: Cross-layer scheduling for power efficiency in wireless sensor networks by Sichitiu (Slides) Routing and data dissemination Reference: Routing and data dissemination in wireless sensor networks by Sandeep Gupta	Lecture notes

TinyOS References:

About Motes
TinyOS Tutorial by Arvind Easwaran
TinyOS Tutorial from UC Berkeley
Presentation on NesC by Matt Welsh
Application driven research on TinyOS platform by Robert Szewczyk
The Scientist and Engineer's Guide to TinyOS Programming
Lecture on TinyOS (PPT)
Lecture notes on Crossbow Mica Motes (PPT)
TinyOS Web Site
Presentations from Smart Dust Training that took place in Boston from the 15-16 of Jan 2004
Presentations on TinyOS from the tutorial session that took place in Mobisys 2003, San Fransisco
Component & Interface lists
System Architecture Directions for Networked Sensors (PDF) by J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler and K. Pister
Active Message Communication for Tiny Networked Sensors (PDF) by P. Buonadonna, J. Hill, and D. Culler
A Network-Centric Approach to Embedded Software for Tiny Devices (PDF) by R. Szewczyk, A. Woo, P. Buonadonna, J. Hill, and D. Culler

Additional References:

Introduction to approximation ratio: Chapter 35 "Approximation algorithms". Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001). Introduction to Algorithms. The MIT Press
Introduction to weighted graphs, MST algorithms, and NP-completeness: Chapter 7 & 13: Goodrich, M. T., & Tamassia, R. (2001). Algorithm Design -- Foundations, Analysis, and Internet Examples. John Wiley & Sons, Inc.
Energy-efficient multicast/broadcast in WSNs: Gupta, S. K. S., & Wang, B. (2005). Energy-efficient multicast protocols. In Cardei, M., Cardei, I., & Zhu, D.-Z. (Eds.), Resource management in wireless networking. The Netherlands:Kluwer Academic Publishers.
Graph theory basics:
- Algorithmic graph theory
- Diestel, R. (2005) Graph theory. New York: Springer. (A complete electronic edition is available on the author's homepage.)
RFID:
- RFID: A key to automating everything by Roy Want
- Communications of the ACM, September 2005, Vol. 48, No. 9, RFID
- RFID systems and security and privacy implications by Sarma et al.
- Security and privacy aspects of low-cost radio frequency identification systems by Weis et al.