|
Cyber-Physical
Systems |
Location |
Time |
Physical Context |
Distribution |
|
Application Examples |
(for
Assisted Living) |
|||
|
Services |
||||
|
Development Challenges |
-
Conquering
Interactive Complexity: Troubleshooting,
Debugging, and Avoidance by Design |
|||
|
Programming Paradigms |
||||
Reading List
Research on
cyber-physical systems is driven by the nature of their interaction with the
physical world. Such systems are part physical and hence have new attributes
that play a major role in system design, development, and execution. These
attributes include physical location (of system components), real time, physical energy consumption, external context,
and distribution (including the need for composition of global properties from multiple
interacting components). Research in cyber-physical systems usually addresses
the effects of one or more of these attributes on system design tools,
protocols, middleware, operating systems, languages, computing abstractions,
simulators, debugging tools, and analytic foundations. This course will
follow recent literature on research surrounding the stated attributes.
Observe that there
is a large spectrum of cyber-physical applications from the very low end, such
as sensor networks, to the very high-end, such as the total shipboard computing
environment designed to run battleships. The emphasis of research typically
depends on the application class under consideration.
In low-end systems, featuring a multitude of small components, distribution challenges and consequently location-related challenges are dominant. In high-end systems, featuring a smaller number of larger and
more expensive components, real-time predictability and reliable composition challenges are dominant. Finally, energy challenges have been addressed in a very
broad spectrum of applications from the very low end to the high-end.
Part I: Background (Sensor
Networks and CPS Visions)
Background for 1/16-1/18 (optional reading):
"Embedded,
Everywhere: A Research Agenda for Networked Systems of Embedded Computers,"
Committee
on Networked Systems of Embedded Computers,
Edward A. Lee (UC Berkeley), "Cyber-Physical Systems
- Are Computing Foundations Adequate?" presented at the NSF Workshop on Cyber-Physical Systems,
October 16, 2006. (Also see Extended
Technical Report)
Part II: Applications
Below we explore examples of cyber-physical applications that motivate emphasis on physical location (the spatial attribute), real time, physical energy consumption, external context, and distribution respectively.
Applications and the
Spatial Attribute:
Tracking and Monitoring Applications
Maxim A. Batalin, Mohammad
Rahimi, Yan Yu, Duo Liu, Aman Kansal, Gaurav S. Sukhatme, William J. Kaiser,
Mark Hansen, Gregory J. Pottie, Mani Srivastava, and Deborah Estrin, "Call and
Response: Experiments in Sampling the Environment," ACM Sensys
2004.
Ting Liu, Christopher M. Sadler,
Pei Zhang, and Margaret Martonosi, "Implementing Software on
Resource-constrained Mobile Sensors: Experiences with Impala and ZebraNet,"
ACM Mobisys 2004.
J. Liu, M. Chu, J. E. Reich,
"Multitarget
Tracking in Distributed Sensor Networks," IEEE Signal
Processing Magazine, Volume 24, Issue 3, May 2007.
Nisheeth Shrivastava, Raghuraman
Mudumbai, Upamanyu Madhow, Subhash Suri, "Target
Tracking with Binary Proximity Sensors: Fundamental Limits, Minimal
Descriptions, and Algorithms," ACM Sensys
2006.
Branislav Kusy, Akos Ledeczi,
Xenofon Koutsoukos, "Tracking
Mobile Nodes Using RF Doppler Shifts," ACM Sensys 2007.
Optional reading on
tracking/monitoring applications:
Javed Aslam, Zack Butler,
Ning Xu, Sumit Rangwala, Krishna
Kant Chintalapudi, Deepak Ganesan, Alan Broad, Ramesh Govindan, Deborah Estrin,
"A Wireless Sensor-Network for Structural Monitoring," ACM Sensys
2004.
Gyula Simon, Miklos Maroti, Akos
Ledeczi, Gyorgy Balogh, Branislav Kusy, Andras Nadas, Gabor Pap, Janos Sallai,
Ken Frampton, "Sensor Network-based Countersniper System," ACM Sensys
2004.
L. Gu, D. Jia, P. Vicaire, T.
Yan, L. Luo, A. Tirumala, Q. Cao, J. A. Stankovic, T. Abdelzaher, and B. Krogh,
"Lightweight Detection and Classification for Wireless Sensor Networks in
Realistic Environments," ACM Sensys 2005.
Leo Selavo, Anthony Wood, Qiuhua
Cao, Tamim Sookoor, Hengchang Liu, Aravind Srinivasan, Yafeng Wu, Woochul Kang,
John Stankovic, Don Young, John Porter, "Luster: Wireless Sensor Network
for Environmental Research," ACM Sensys
2007.
Jude Allred, Ahmad Bilal Hasan,
Saroah Panichsakul, William Pisano, Peter Gray, Jyh Huang, Richard Han, Dale
Lawrence, Kamran Mohseni, "SensorFlock: An Airborne Wireless Sensor
Network of Micro-Air Vehicles," ACM Sensys
2007.
Applications and the Time
Attribute:
Shipboard computing and radar scheduling
TSCE Background (Optional entertaining reading): TSCE is the US
Navy’s futuristic vision of computerized future super-ships. Check out a video
clip on the Zumwalt Class Destroyer; the first battleship
launching TSCE software. Read a Feb, 2007 press release by Raytheon (the contractor who
built the ship) about TSCE launch. A technology review article about the design
of this system is available here.
Next, see assigned reading.
Yuanfang
Zhang, Chenyang Lu, and Christopher Gill, Patrick Lardieri and Gautam Thaker,
"Middleware Support
for Aperiodic Tasks in Distributed Real-Time Systems," RTAS
2007
Tarek Abdelzaher, Gautam Thaker, Patrick Lardieri,
"A
Feasible Region for Meeting Aperiodic End-to-end Deadlines in Resource
Pipelines," IEEE ICDCS,
Praveen
Jayachandran and Tarek Abdelzaher, "A Delay Composition Theorem for Real-Time Pipelines,"
Euromicro Conference on Real-Time Systems,
C.-G. Lee, P.-S. Kang, C.-S. Shih, M. Caccamo, L. Sha,
"Schedulability
Envelope for Real-Time Radar Dwell Scheduling and its Application to Multi-Ship
Multi-Radar Systems," Proceedings of International RADAR
Conference (RADAR '04),
Sathish Gopalakrishnan, Marco Caccamo, Chi-Sheng
Shih, Chang-Gun Lee, and Lui Sha, "Finite-horizon scheduling of radar dwells with online
template construction," Journal
of Real-Time Systems, Volume 33, No. 3, July, 2006. (No summary requested
for papers co-authored by UIUC faculty)
Optional reading on distributed
real-time applications:
Vinny Cahill, Aline Senart, Doug Schmidt, Stefan
Weber, Anthony Harrington, Barbara Hughes, "The Managed
Motorway: Real-time Vehicle Scheduling - A Research Agenda," HotMobile 2008.
Applications and the
Physical Context Attribute:
Personal and home activity monitoring (e.g., for assisted
living)
Background: The healthcare system in the
E.
Munguia Tapia, S. S. Intille, and K. Larson, "Activity recognition
in the home setting using simple and ubiquitous sensors," in Proceedings
of PERVASIVE 2004, vol. LNCS 3001, A. Ferscha and F. Mattern, Eds. Berlin
Heidelberg: Springer-Verlag, 2004, pp. 158-175.
B. Logan, J. Healey, Matthai Philipose, E. Munguia
Tapia, and S. Intille, "A long-term evaluation
of sensing modalities for activity recognition," in Proceedings of the
International Conference on Ubiquitious Computing, vol. LNCS 4717.
Applications and
Distributed Behavior:
Participatory sensing of global phenomena
Readings for 2/13: A vision: Mobiscopes and the
World Wide Sensor Web
Note:
No summaries required for the papers below. Instead see assignment on front
page.
Tarek Abdelzaher, Yaw Anokwa, Peter Boda, Jeff
Burke, Deborah Estrin, Leonidas Guibas, Aman Kansal, Samuel Madden, Jim Reich.
"Mobiscopes
for Human Spaces." In Pervasive Computing, 2007.
Suman Nath, Jie Liu, and Feng Zhao, "SensorMap for Wide-Area
Sensor Webs." IEEE
Computer Magazine, 40(7), pp. 90-93, July, 2007.
Readings for 2/15: Examples. (Note:
No summaries are required). Lecture Slides.
Bret Hull, Vladimir
Bychkovsky, Kevin Chen, Michel Goraczko, Allen Miu, Eugene Shih, Yang Zhang,
Hari Balakrishnan, and Samuel Madden, "CarTel:
A Distributed Mobile Sensor Computing System," in Proc. ACM SenSys, 2006. Check out the CarTel
portal.
Shane B. Eisenman, Emiliano Miluzzo, Nicholas D.
Lane, Ronald A. Peterson, Gahng-Seop Ahn, Andrew T. Campbell, "The BikeNet Mobile
Sensing System for Cyclist Experience Mapping", Proc. of Fifth ACM Conference on Embedded Networked
Sensor Systems (SenSys 2007), Sydney, Australia, Nov. 6-9, 2007.
Check out the BikeNet portal bikeView.
Part III: Services
Below we explore
examples of service that enable cyber-physical applications. Such services
support application discovery, awareness, or exploitation of physical location (the
spatial attribute), real time constraints, physical energy consumption,
external context, and distribution respectively.
Services
and the Location Attribute:
Localization Services in Sensor Networks:
Ziguo
Zhong and Tian He, "MSP: Multi-sequence Positioning of Wireless Sensor Nodes,"
Proc.
of Fifth ACM Conference on Embedded Networked Sensor Systems (SenSys 2007),
R.
Stoleru, P. Vicaire, T. He, J. A. Stankovic "StarDust: A Flexible Architecture for Passive
Localization in Wireless Sensor Networks," In Proceedings of ACM Conference on Embedded
Networked Sensor Systems (SenSys 2006),
Services
and the Time Attribute:
Real-time Scheduling:
Liu, C.L., Layland, J.W., "Scheduling Algorithms
for Multiprogramming in a Hard Real-Time Environment," Journal of the ACM, Vol. 20 No. 1, pp.
40-61, 1973
Lui Sha, Tarek Abdelzaher, Karl-Eric Arzen,
Anton Cervin, Theodore Baker, Alan Burns, Giorgio Buttazzo, Marco Caccamo, John
Lehoczky, Aloysius K. Mok, "Real Time Scheduling Theory: A Historical Perspective,"
Journal of Real-time Systems,
December 2004. (Warning: Long paper. Will cover over two classes)
Services
and Physical Context:
Joint control of time, quality and energy:
Readings for 3/5: The control server - joint scheduling
and control quality optimization. Lecture Slides.
Writing
assignment (Group): Write one paragraphs on each of the following: (i) how
scheduling and control quality are coupled, (ii) how
Dan Henriksson, Anton Cervin, Johan Akesson,
Karl-Erik Arzen "Feedback
Scheduling of Model Predictive Controllers," In Proc. 8th IEEE Real-Time and Embedded Technology
and Applications Symposium, San
Jose, CA, September 2002.
Anton Cervin, Johan Eker, "Control-Scheduling
Codesign of Real-Time Systems: The Control Server Approach," Journal of Embedded Computing, Vol. 1,
No. 2, pp. 209--224, 2005.
Group
assignment (instead of summaries): Mathematically formulate, to the best of
your ability, the statement of a "cyber-physical" energy cost
optimization problem in web-server farms where energy is consumed on both
cooling and computation, indicating using appropriate equations (i) the
objective function of the optimization, (ii) time and resource constraints, and
(iii) any physical relations between variables involved in the optimization
problem. Specify the "control knobs" whose settings the optimizer
computes to minimize total energy. Please do not exceed one page.
Tibor Horvath, Tarek Abdelzaher, Kevin Skadron,
and Xue Liu, "Dynamic
Voltage Scaling in Multi-tier Web Servers with End-to-end Delay Control,''
IEEE Transactions on Computers, Vol. 56, No. 4, pp. 444-458, April 2007
Bash, C.B.; Patel, C.D.; Sharma, R.K., "Dynamic thermal
management of air cooled data centers," In Proc. 10th Thermal and
Thermo-mechanical Phenomena in Electronics Systems, May 2006
Performance Management:
Additional background on 3/26 (Optional): A control
theory approach to software performance management. Lecture
Slides.
Tarek F. Abdelzaher, John A. Stankovic, Chenyang
Lu, Ronghua Zhang, and Ying Lu, "Feedback Performance Control in Software Services,''
IEEE Control Systems Magazine, Vol
23, No. 3, June 2003.
Tarek Abdelzaher, Yixin Diao, Joseph L.
Hellerstein, Chenyang Lu, and Xiaoyun Zhu, "Introduction to Control Theory and its Application to
Computing Systems," SIGMETRICS
Tutorial, Annapolis, MD, June 2008.
Additional background on 3/28 (Optional): An optimization
approach to software performance management. Lecture Slides.
Chen Lee, John Lehoczky, Raj Rajkumar and Dan
Siewiorek "On Quality of Service Optimization with Discrete QoS
Options," in Proceedings of the IEEE
Real-time Technology and Applications Symposium, June 1999.
Troubleshooting,
Debugging, and Avoidance by Design:
Conquering Interactive
Complexity
Additional background on 4/2 (Optional): Debugging interactive
complexity. Lecture Slides.
What is normal accident theory? This very interesting
book by Charles Perrow explains why some catastrophic accidents are
inevitable (and hence "normal") by system design despite taking
significant safety precautions, employing redundancy, and following safety
protocols correctly:
Charles Perrow, "Normal Accidents: Living with High-risk Technologies,"
2nd edition, Princeton
University Press, 1999.
K. Marais, N. Dulac
and N. Leveson, "Beyond normal accidents and high reliability organizations: the need
for an alternative approach to safety in complex systems," MIT
ESD Symposium, March 2004.
Additional background on 4/4, 4/9 (Optional): Designing for simplicity. Lecture
Slides (Sha).
Lui Sha, "Using simplicity to control complexity," IEEE Software, Volume 18, Issue
4, July-Aug. 2001.
Tanya Crenshaw, Elsa Gunter, C. L. Robinson, Lui
Sha and P. R. Kumar, "The Simplex Reference Model: Limiting Fault-Propagation due to
Unreliable Components in Cyber-Physical System Architectures," IEEE Real-time Systems Symposium,
Additional background on 4/11 (Optional): Operating Systems and
Middleware. Slides-1
(David Culler on TinyOS). Slides-2 (Ed Lee on Embedded Systems). Slides-3 (Ed Lee on Platforms and
Abstractions).
Programming Paradigms –
Student Presentations:
The following are early examples. You are encouraged to follow up on each
threads to discover later publications on the subject.
1. NesC:
David Gay, Phil Levis,
Rob von Behren, Matt Welsh, Eric Brewer, and David Culler, “The nesC Language:
A Holistic Approach to Networked Embedded Systems,” PLDI 2003.
2. Virtual Machines:
Philip Levis and David
Culler, “Mate: A Tiny Virtual Machine for Sensor Networks,” Asplos 2003.
3. Environmentally Immersive:
Tarek Abdelzaher et
al., "EnviroTrack: Towards an Environmental Computing Paradigm for
Distributed Sensor Networks," IEEE International Conference on Distributed
Computing Systems,
4. Node-based paradigms:
R. Gummadi, O. Gnawali,
and R. Govindan “Macro-programming Wireless Sensor Networks using Kairos,”
DCoSS 2005.
5. Query-Based Paradigms
Samuel Madden, Michael
J. Franklin, and Joseph M. Hellerstein, and Wei Hong, “TAG: a Tiny AGgregation
Service for Ad-Hoc Sensor Networks,” SigOps 2002.
S. R. Madden, M.J.
Franklin, J.M. Hellerstein, W. Hong, “TinyDB: An Acquisitional Query Processing
System for Sensor Networks,” ACM Transactions on Database Systems, vol.30,
no.1, March 2005.
6. Event-Based Paradigms
Elaine Cheong, Judy
Liebman, Jie Liu, and Feng Zhao, “TinyGALS: A Programming Model for
Event-Driven Embedded Systems,” SAC 2003.
7. Group Based Paradigms
Matt Welsh and Geoff
Mainland, “Programming Sensor Networks Using Abstract Regions,” NSDI 2004.
Kamin Whitehouse, Cory
Sharp, Eric Brewer, and David Culler, “Hood: A Neighborhood Abstraction for
Sensor Networks,” Mobisys 2004.
8. State-Centric
Jie Liu, Maurice Chu,
Juan Liu, James Reich, and Feng Zhao, “State-Centric Programming for
Sensor-Actuator Network Systems,” Pervasive Computing, 2003.
9. Bio-inspired Paradigms
Harold Abelson, Don
Allen, Daniel Coore, Chris Hanson, George Homsy, Thomas F. Knight, Radhika
Nagpal, Erik Rauch, Gerald Jay Sussman, and Ron Weiss, “Amorphous Computing,”
Communications of the ACM, Volume 43 Issue 5, May 2000.