File preview
July 13, 2010 , P. R. Kumar
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
See http://creativecommons.org/licenses/by-nc-nd/3.0/
Foundations of Cyberphysical Systems
P. R. Kumar
with Girish Baliga, Vivek Borkar, Derek Caveney, Scott Graham, Piyush Gupta, Arvind Giridhar, I-Hong Hou, , Kun Huang, Kyoung-Dae Kim, Hemant Kowshik, Craig Robinson
Dept. of Electrical and Computer Engineering,
and Coordinated Science Lab
University of Illinois, Urbana-Champaign
Email: prkumar@illinois.edu Web: http://decision.csl.illinois.edu/~prkumar
NSF CPS Meeting,
Washington DC
August 10, 2010
1/35
July 13, 2010 , P. R. Kumar
Several paths to cyberphysical systems
2/35
July 13, 2010 , P. R. Kumar
One path: From computation to realtime and hybrid systems
Computers for computation (1949)
Real-time computation (1973)
Hybrid systems (1990s)
Cyberphysical systems (Phrase coined around 2006)
“Instigators”: Gill, Kumar, Lee, Midkiff, Mok, Rajkumar, Sastry, Sha, Shin, Stankovic, Sztipanovits, …
3/35
July 13, 2010 , P. R. Kumar
Another path: From communication to sensing to acting
Cellular systems
Wireless networks
Convergence of communication, computation and control
Cyberphysical Systems
Sensor Networks
Networked Embedded Control
4/35
July 13, 2010 , P. R. Kumar
Yet another path
First generation: Analog Control
– Technology: Feedback amplifiers
– Theory: Frequency domain analysis Bode, Evans, Nyquist
•
Foundation of system theory
• • • • • • • • • Linear systems
Nonlinear systems
Estimation
Optimal control
System identification
Adaptive control
Robust control
Discrete event systems
Hybrid systems
•
Bouquet of books
Second generation: Digital Control
– – – – Around 1960
Technology: Digital computers
Theory: State-space design
Real-Time Scheduling
5/35
July 13, 2010 , P. R. Kumar
The third generation of control
Third generation: Networked Control
• Embedded computers
• Wireless and wired networks
• Software
Made possible by the convergence of computing, communication and control
Platform revolution
Just in time for resource-aware system building era of 21st century
– Zero-accident highways, smart grid, tele-operation rooms
6/35
July 13, 2010 , P. R. Kumar
“What’s in a name? That which we call a rose By any other name would smell as sweet” – Shakespeare
7/35
July 13, 2010 , P. R. Kumar
Foundational issues in cyberphysical systems
Information Theory
Sensor Networks
Information Processing
Capacity
Formal Correctness
Methods
Control
Real-time Networking
comm
Time
Middleware
Synchronization
Software
Engineering
Computer Science
8/35
July 13, 2010 , P. R. Kumar
Sensor Networks
Information Processing
From data to information
9/35
July 13, 2010 , P. R. Kumar
Information processing in networks
Environmental monitoring
• n nodes take temperature measurements x1, x2, . , xn
• Determine the Mean temperature: (x1 + x2 + … + xn)/n
Alarm networks
• Determine the Max temperature: Max xi
Sensor networks are not data networks
– Nodes can change/create/discard packets
How should we process information in-network?
10/35
July 13, 2010 , P. R. Kumar
Mean versus Max
Theorem: The Mean can be computed at
⎛ 1 ⎞ rate Θ⎜ ⎟ ⎝ log n ⎠
Theorem: The Max can be computed
⎛ ⎞ 1 at rate Θ ⎜ ⎝ log log n ⎟ ⎠
– Block Coding
• First node announces times of max values: ( • Second node announces times of additional max values: ( 1 • Third node announces of yet more max values: ( 1 1 1 1 1 )
)
)
(Giridhar & K ’03)
11/35
July 13, 2010 , P. R. Kumar
Complexity hierarchy
⎛ 1⎞ Θ⎜ ⎟ ⎝ n⎠
Downloading all data from all nodes
Collocated network: Mean, Mode, Type
⎛ 1 ⎞ Θ⎜ log(n) ⎟ ⎝ ⎠
Multi-hop random network: Mean, Mode, Type
Collocated network: Max
⎛ ⎞ 1 Θ⎜ loglog(n) ⎟ ⎝ ⎠
Multi-hop random network: Max
(Giridhar & K ’03)
12/35
July 13, 2010 , P. R. Kumar
Delivering packets on time
Real-time Networking
comm
13/35
July 13, 2010 , P. R. Kumar
Real-time scheduling: (Liu and Layland `73)
completed
completed
cn
τn
cn
τn
N tasks
– Jobs of Task n arrive with period τn
– Deadline is end of period
– Worst case execution time cn
τn
deadline miss
Rate monotone scheduling: Priority to smallest period task
N
cn 1/N All deadlines met if ∑ ≤ N(2 − 1) n=1 τ n
(
ln 2 = 0.69 as N ∞)
14/35 If any priority policy can meet all deadlines, then this policy can
July 13, 2010 , P. R. Kumar
Formulation of real-time communication
Access Point serving N clients
Slotted
Unreliable channels
τ
delivered
Slot
Packet
1
2
p1
pN
N
p2
AP
p3
4
3
p4
τ
delivered
τ
dropped
Require timely throughput of qn packets per period
Are the requirements {(qn, pn, τ), 1≤n≤N} feasible?
15/35
July 13, 2010 , P. R. Kumar
Characterization of feasibility
qn Load due to Client n is
wn = pnτ
Necessary condition from classical queueing theory
Unavoidable idle time
1
S
Idle
∑w
n=1
N
n
≤1
Forced to be idle
2
S
Idle
AP
But every subset of clients should also be feasible
Theorem: Feasible iff
∑w
n=1
N
n
+ I (1,2,..., N ) ≤ 1
∑w
n∈S
n
+ I(S)
≤ 1, ∀S ⊆ {1,2,..., N}
(Hou, Borkar & K 09)
16/35
July 13, 2010 , P. R. Kumar
Scheduling policies
Delivery debt of Client n
= qn − Actual timely throughput to Client n pn Give higher priority to higher debt
F
1
AP
3
F
S
2
F
F
S
Theorem: This policy is feasibility optimal
(Hou, Borkar & K 09)
17/35
July 13, 2010 , P. R. Kumar
Synchronizing clocks in a network
Time
Synchronization
Computer Science
18/35
July 13, 2010 , P. R. Kumar
Clock synchronization
Knowledge of time is important
Reference Clock 1
Clock 2
d12
d21
Theorem: It is impossible to synchronize clocks
r1 = a2 (s1 + d12 ) + b2
τ2 τ1
s1
r1
s2
r3
s4
τ2
Skew a2
Offset b2
r4
d12
d21
r2
s3
d12
d21
τ1
s2 = a2 (r2 − d21 ) + b2 ⎡ r1 ⎤ ⎡ s1 1 0 1 ⎤ ⎢ s ⎥ ⎢ r 0 −1 1 ⎥ ⎡ a2 ⎤ ⎢ 2⎥ ⎢ 2 ⎥ ⎢ a2 d12 ⎥ ⎥ ⎢ r3 ⎥ = ⎢ s3 1 0 1 ⎥ ⎢ ⎢ ⎥ ⎢ ⎥ ⎢ a2 d21 ⎥ ⎢ s4 ⎥ ⎢ r4 0 −1 1 ⎥ ⎢ b ⎥ ⎢ ... ⎥ ⎢ ... ... ... ...⎥ ⎣ 2 ⎦ ⎣ ⎦ ⎣ ⎦
So assume symmetric delays
Rank 3: Cannot estimate 4 parameters
Noisy observations?
Network?
(Graham & K ‘04) 19/35
July 13, 2010 , P. R. Kumar
Traditional approach
Assume all skews = 1
Std. Dev of Error
= Θ Diameter
(
)
8
ˆ x01
0
1
ˆ x12
2
ˆ x23
3
10
4
6
7
ˆ ˆ ˆ ˆ v3 = x01 + x12 + x23
5
Random multi-hop network with n nodes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
⎛ log n ⎞ = Ω⎜ ⎟ n ⎠ ⎝ (Gupta & K ‘98)
⎛ ⎛ n ⎞ 14 ⎞ Std. Dev of Error
= O ⎜ ⎜ ⎟ ⎜ ⎝ log n ⎟ ⎟ ⎠ ⎠ ⎝
Critical radius for connectivity Error grows polynomially
Can we do better?
20/35
July 13, 2010 , P. R. Kumar
Improving synchronization
Sum of offsets along any loop is zero
Theorem (Karp et al `03)
– Asymptotic error variance is Resistance Distance of network
e ∈ Directed Cycle
∑
xe = 0
1
Loop 1
2
Loop 2
3
4
5
Theorem
–
x = AT v
T ˆ ˆ Minimization problem:
Min x − A v ˆ v 2
–
Error is bounded for large random networks
Error = O(1)
Coordinate descent: Spatial smoothing
ˆ v j,new =
1 Nj
edges (i, j )
ˆ ∑ (v
i,old
ˆ + xij
)
ˆ log α e = 0
Lends support for feasibility of time-based computing
1 5 9 13 17 21 47 29 47 37 2 6 10 14 18 22 26 30 47 38 3 7 11 15 19 47 47 31 35 36
4
8
12
16
20
24
28
32
36
40
Similarly for skew:
e ∈ Directed Cycle
∑
80 70
80 70 60
Closeness -
(in usec)
50 40 30 20 10 0 0 50 100 150 200 250 300 Sample Number
Max Avg Min
Closeness -
60
(in usec)
50 40 30 20 10 0 0 50 100 150 200 250 300 Sample Number
Max Avg Min
Leading algorithm (FTSP, Maroti et al ‘04)
New multi-hop clock synchronization algorithm
(Solis, Borkar and K ‘05)
(Giridhar & K ’06)
21/35
July 13, 2010 , P. R. Kumar
Abstractions and architecture
Middleware
Software
Engineering
22/35
July 13, 2010 , P. R. Kumar
Challenge of abstractions
Internet
Application Layer Presentation Layer Session Layer Transport Layer Network Layer Data Link Layer Physical Layer Application Layer Presentation Layer Session Layer Transport Layer Network Layer Data Link Layer Physical Layer
Serial computation
Hardware
Software
Digital Communication
Source
Coding
Channel
Coding
von Neumann Bridge
(Valiant `90)
What are the abstractions for convergence of control with communication and computing?
Goal is to enable rapid design and deployment
– Critical Resource: Control Designer’s Time
Standardized abstractions
– Minimal reconfiguration and reprogramming
Hopefully
leading to proliferation
23/35
July 13, 2010 , P. R. Kumar
Challenge of architecture
IBM 360
First
commercially successful model
Standard software architecture
360 – All round capability
TCP/IP is de facto standard
Program as data
Interfaces
Ease of customization
Modular design of software
Portability – High level languages
Reusability – Component libraries
Layers of protocols
Breakdown networking into subproblems
Solve sub-problems in different layers
Compose solutions into a working stack
Mechanism: Encapsulation of packets
24/35
July 13, 2010 , P. R. Kumar
Convergence Lab:
The Systems
Vision Sensors
Planning and Scheduling
Automatic Control
Wireless Ad Hoc Network
25/47
(Baliga, Graham, Huang & K ‘02)
25/35
July 13, 2010 , P. R. Kumar
Abstraction layers
Middleware manages the Components
Kalman Filter
Trajecto ry Planner
Deadlock Avoidance
Set Point Generator
Image Process ing
Discrete Event Scheduler
Kalm an filter
Ima Proc ge essin
g
Application Layer
Service 3! Service 2! Clock!
Components
Middleware
TCP
DBF
Modulation
Trajecto ry Planner
System Layer
Transport Layer
Network Layer
PHY/MAC Layer
Set P Gene oint ratio n
Cont r Optim ol Law izatio n
Car
r
e troll con
nt te Eve Discre uler
Sched
Mod el Pr Cont edictive rolle r
(Baliga, Graham & K ‘04)
(Graham, Baliga & K ‘09)
(Kim & K ‘08)
26/35
July 13, 2010 , P. R. Kumar
Collision avoidance
(Schuetz, Robinson & K ’05)
27/35
http://decision.csl.uiuc.edu/~testbed/videos/CollisionAvoidance.mpg
July 13, 2010 , P. R. Kumar
Example of capabilities: Component migration
Communicate pixels?
Or compute
position?
Kalman
filter
Car
controller
Computer 1
Computer 2
Migrate Kalman Filter
(Baliga, Graham & K ‘04)
28/35
Excessive delay
July 13, 2010 , P. R. Kumar
Example of capabilities: Component migration
Communicate pixels?
Or compute
position?
Kalman
filter
Car
controller
Computer 1
Computer 2
Migrate Kalman Filter
Excessive delay
Real-time middleware
(Kim & K ’09)
29/35
July 13, 2010 , P. R. Kumar
Proofs of correctness
Formal Correctness
Methods
30/35
July 13, 2010 , P. R. Kumar
Provably correct behavior
Theorem
– Directed graph model of road network
• Each bin has in-degree 1 or out-degree 1
• System has no occupied cycles initially
– Road width:
W = R(1 − cos β (2 cos α − 1) • Initial condition:
(d, θ ) : d + R(1 − cos θ ) < W • Intersection angles ≤ γ, and road lengths:
= (2γ RR ) (R − R ) L • Multiple cars with appropriate spacing
– Car control model: Kinematic model with turn radii R and R
– Real time renewal tasks: HST scheduling with
C D ≤ 1 ∑
i i
– Then cars can be operated
• Without collisions (Safety) or
• Gridlocks (Liveness)
(Baliga & K ’05)
1 85 84 83 21 20 72 73 2 22 31 53 53 8671 82 3 35 8770 7481 5353 53 4 53 8869 2429 7580 54 5 4553 5342 4153 52 6 4653 5353 5336 7 8 8968 7679 5328 18 9067 9 7778 5353 19 17 10 91 66 65 11 64 6353 6160 92 9353 12 9596 9798 31/35
http://decision.csl.uiuc.edu/~testbed/videos/city_7cars.mpg
July 13, 2010 , P. R. Kumar
Re-convergence: The pedagogical challenge
“…the era of cyberspace and the Internet, with its emphasis on the computer as a communications device and as a vehicle for human interaction connects to a longer history of control systems that generated computers as networked communications devices.” − D. Mindell in “Feedback, Control and Computing before Cybernetics,” 2002
1950 — 2000 and continuing
– – – – – Computation: ENIAC (1946), von Neumann (1944), Turing,..
Sensing and inference: Fisher, Wiener (1949),…
Actuation/Control: Bode, Kalman (1960),…
Communication: Shannon (1948), Nyquist,…
Signal Processing: FFT, Cooley-Tukey (1965),…
2000 — onwards: Age of system building
- Nodes that can communicate, control, compute
- Larger grand re-unification of control, communication and computation
- Pedagogical challenges: Knowledge of all these fields may be important
- Undergraduate education?
- Postgraduate education?
32/35
July 13, 2010 , P. R. Kumar
References - 1
Piyush Gupta and P. R. Kumar, “The Capacity of Wireless Networks,” IEEE Transactions on Infor- mation Theory, vol. IT-46, no. 2, pp. 388-404, March 2000.
Arvind Giridhar and P. R. Kumar, “Computing and Communicating Functions Over Sensor Networks,” IEEE Journal on Selected Areas in Communications, pp. 755–764, vol. 23, no. 4, April 2005.
C. L. Liu, C.L., Layland, J.W.: Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM 20(1) (1973) 46–61
I-Hong Hou, V. Borkar and P. R. Kumar, “A Theory of QoS for Wireless.“ Proceedings of Infocom 2009, April 19-25, 2009, Rio de Janeiro, Brazil.
Scott Graham and P. R. Kumar, “Time in General-Purpose Control Systems: The Control Time Protocol and an Experimental Evaluation,” Proceedings of the 43rd IEEE Conference on Decision and Control, Paradise Island, Bahamas, pp. 4004–4009, December 14-17, 2004
Roberto Solis, Vivek S. Borkar , and P. R. Kumar, “A New Distributed Time Synchronization Protocol for Multihop Wireless Networks.”Proceedings of the 45th IEEE Conference on Decision and Control, pp. 2734–2739, San Diego, Dec. 13–15, 2006.
Piyush Gupta and P. R. Kumar, “Critical Power for Asymptotic Connectivity in Wireless Networks,” in Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming. Edited by W. M. McEneany, G. Yin, and Q. Zhang, Birkhauser, Boston, MA, pp. 547–566, 1998.
J. Elson, R.M. Karp, C.H. Papadimitriou and S. Shenker, “Global Synchronization in Sensornets.” Proceedings of LATIN,
vol. 2976, pp. 609-624, 2004.
33/35
July 13, 2010 , P. R. Kumar
References - 2
Arvind Giridhar and P. R. Kumar, “Distributed Clock Synchronization over Wireless Networks: Algo- rithms and Analysis.” Proceedings of the 45th IEEE Conference on Decision and Control, , pp. 4915– 4920, San Diego, Dec. 13–15, 2006.
Arvind Giridhar and P. R. Kumar, “The Spatial Smoothing Method of Clock Synchronization in Wireless Networks.” Submitted to Theoretical Aspects of Distributed Computing in Sensor Networks. Editors: Sotiris Nikoletseas and Jose D.P. Rolim. Lecture Notes in Computer Science. Springer-Verlag. Submitted November 28, 2009.
Liu, C.L., Layland, J.W.: Scheduling algorithms for multiprogramming in a hard-real-time
environment. Journal of the ACM 20(1) (1973) 46–61
Scott Graham and P. R. Kumar, “The Convergence of Control, Communication, and Computation,” Proceedings of PWC 2003: Personal Wireless Communication, Lecture Notes in Computer Science, vol. 2775/2003, Springer-Verlag, Heidelberg, Germany, pp. 458–475, 2003.
Scott Graham, Girish Baliga, and P. R. Kumar, “Issues in the Convergence of Control with Commu- nication and Computing: Proliferation, Architecture, Design, Services, and Middleware,” Proceedings of the 43rd IEEE Conference on Decision and Control, Paradise Island, Bahamas, pp. 1466–1471, December 14-17, 2004.
Girish Baliga and P. R. Kumar, “A Middleware for Control over Networks,” Proceedings of the 44th IEEE Conference on Decision and Control, pp. 482–487, Seville, Spain, Dec. 12–15, 2005.
Girish Baliga, Scott Graham and P. R. Kumar, “Middleware and Abstractions in the Convergence of Control with Communication and Computation,” Proceedings of the 44th IEEE Conference on Decision and Control, pp. 4245–4250, Seville, Spain, Dec. 12–15, 2005.
Scott Graham, Girish Baliga and P. R. Kumar, “Abstractions, Architecture, Mechanisms, and a Mid- dleware for Networked Control.” IEEE Transactions on Automatic Control, vol. 54, no. 7, pp. 1490– 1503, July 2009.
34/35
July 13, 2010 , P. R. Kumar
References - 3
Kyoung-Dae Kim and P. R. Kumar, “Architecture and Mechanism Design for Real-Time and Fault- Tolerant Etherware for Networked Control.” Proceedings of the 17th World Congress, The International Federation of Automatic Control, pp. 9421–9426, Seoul, Korea, July 6-11, 2008.
Kyoung-Dae Kim and P. R. Kumar, ``Design and experimental verification of real--time mechanisms for middleware for networked control.'’ 2009.
Kyoung-Dae Kim and P. R. Kumar, “The Importance, Design and Implementation of a Middleware for Networked Control Systems.” 2009.
C. L. Robinson, H.-J. Schuetz, G. Baliga and P. R. Kumar, “Architecture and Algorithm for a Labora- tory Vehicle Collision Avoidance System.” 2007 IEEE International Symposium on Intelligent Control (ISIC2007), Singapore, October 1-3, 2007.
Craig Robinson and P. R. Kumar, “Optimizing Controller Location in Networked Control Systems with Packet Drops.” IEEE Journal on Selected Areas in Communications, Special Issue on Control and Communications, pp. 661–671, vol. 26, no. 4, May 2008.
V. Gupta, B. Hassibi and R. M. Murray, "Optimal LQG Control Across Packet-Dropping Links", System and Control Letters, pp. 439-446, Vol 56, No. 6, June 2007.
Hemant Kowshik, Derek Caveney and P. R. Kumar, “Safety and Liveness in Intelligent Intersections.“ In Hybrid Systems: Computation and Control: Proceedings of 11th International Workshop, HSCC 2008, St. Louis, MO, April 22–24, 2008., pp. 301–315, Magnus Egerstedt and Bud Mishra (Eds.): Lecture Notes in Computer Science 4981, Springer–Verlag, Berlin, 2008.
A. Schafer and D. G. Victor, "The future mobility of the world population,” Transportation Resrarch, A34 (3), 171-205, 2000.
Frank Kelly, Challenges of road pricing, Stochastic Networks Conference, June 19-24, 2006, University of Illinois at UrbanaChampaign.
http://www.ifp.illinois.edu/~srikant/StochNetworks2006/schedule_smallfont.htm
35/35
July 13, 2010 , P. R. Kumar
https://netfiles.uiuc.edu/prkumar/www/talks.html
36/35
July 13, 2010 , P. R. Kumar
Thank you
37/35
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
See http://creativecommons.org/licenses/by-nc-nd/3.0/
Foundations of Cyberphysical Systems
P. R. Kumar
with Girish Baliga, Vivek Borkar, Derek Caveney, Scott Graham, Piyush Gupta, Arvind Giridhar, I-Hong Hou, , Kun Huang, Kyoung-Dae Kim, Hemant Kowshik, Craig Robinson
Dept. of Electrical and Computer Engineering,
and Coordinated Science Lab
University of Illinois, Urbana-Champaign
Email: prkumar@illinois.edu Web: http://decision.csl.illinois.edu/~prkumar
NSF CPS Meeting,
Washington DC
August 10, 2010
1/35
July 13, 2010 , P. R. Kumar
Several paths to cyberphysical systems
2/35
July 13, 2010 , P. R. Kumar
One path: From computation to realtime and hybrid systems
Computers for computation (1949)
Real-time computation (1973)
Hybrid systems (1990s)
Cyberphysical systems (Phrase coined around 2006)
“Instigators”: Gill, Kumar, Lee, Midkiff, Mok, Rajkumar, Sastry, Sha, Shin, Stankovic, Sztipanovits, …
3/35
July 13, 2010 , P. R. Kumar
Another path: From communication to sensing to acting
Cellular systems
Wireless networks
Convergence of communication, computation and control
Cyberphysical Systems
Sensor Networks
Networked Embedded Control
4/35
July 13, 2010 , P. R. Kumar
Yet another path
First generation: Analog Control
– Technology: Feedback amplifiers
– Theory: Frequency domain analysis Bode, Evans, Nyquist
•
Foundation of system theory
• • • • • • • • • Linear systems
Nonlinear systems
Estimation
Optimal control
System identification
Adaptive control
Robust control
Discrete event systems
Hybrid systems
•
Bouquet of books
Second generation: Digital Control
– – – – Around 1960
Technology: Digital computers
Theory: State-space design
Real-Time Scheduling
5/35
July 13, 2010 , P. R. Kumar
The third generation of control
Third generation: Networked Control
• Embedded computers
• Wireless and wired networks
• Software
Made possible by the convergence of computing, communication and control
Platform revolution
Just in time for resource-aware system building era of 21st century
– Zero-accident highways, smart grid, tele-operation rooms
6/35
July 13, 2010 , P. R. Kumar
“What’s in a name? That which we call a rose By any other name would smell as sweet” – Shakespeare
7/35
July 13, 2010 , P. R. Kumar
Foundational issues in cyberphysical systems
Information Theory
Sensor Networks
Information Processing
Capacity
Formal Correctness
Methods
Control
Real-time Networking
comm
Time
Middleware
Synchronization
Software
Engineering
Computer Science
8/35
July 13, 2010 , P. R. Kumar
Sensor Networks
Information Processing
From data to information
9/35
July 13, 2010 , P. R. Kumar
Information processing in networks
Environmental monitoring
• n nodes take temperature measurements x1, x2, . , xn
• Determine the Mean temperature: (x1 + x2 + … + xn)/n
Alarm networks
• Determine the Max temperature: Max xi
Sensor networks are not data networks
– Nodes can change/create/discard packets
How should we process information in-network?
10/35
July 13, 2010 , P. R. Kumar
Mean versus Max
Theorem: The Mean can be computed at
⎛ 1 ⎞ rate Θ⎜ ⎟ ⎝ log n ⎠
Theorem: The Max can be computed
⎛ ⎞ 1 at rate Θ ⎜ ⎝ log log n ⎟ ⎠
– Block Coding
• First node announces times of max values: ( • Second node announces times of additional max values: ( 1 • Third node announces of yet more max values: ( 1 1 1 1 1 )
)
)
(Giridhar & K ’03)
11/35
July 13, 2010 , P. R. Kumar
Complexity hierarchy
⎛ 1⎞ Θ⎜ ⎟ ⎝ n⎠
Downloading all data from all nodes
Collocated network: Mean, Mode, Type
⎛ 1 ⎞ Θ⎜ log(n) ⎟ ⎝ ⎠
Multi-hop random network: Mean, Mode, Type
Collocated network: Max
⎛ ⎞ 1 Θ⎜ loglog(n) ⎟ ⎝ ⎠
Multi-hop random network: Max
(Giridhar & K ’03)
12/35
July 13, 2010 , P. R. Kumar
Delivering packets on time
Real-time Networking
comm
13/35
July 13, 2010 , P. R. Kumar
Real-time scheduling: (Liu and Layland `73)
completed
completed
cn
τn
cn
τn
N tasks
– Jobs of Task n arrive with period τn
– Deadline is end of period
– Worst case execution time cn
τn
deadline miss
Rate monotone scheduling: Priority to smallest period task
N
cn 1/N All deadlines met if ∑ ≤ N(2 − 1) n=1 τ n
(
ln 2 = 0.69 as N ∞)
14/35 If any priority policy can meet all deadlines, then this policy can
July 13, 2010 , P. R. Kumar
Formulation of real-time communication
Access Point serving N clients
Slotted
Unreliable channels
τ
delivered
Slot
Packet
1
2
p1
pN
N
p2
AP
p3
4
3
p4
τ
delivered
τ
dropped
Require timely throughput of qn packets per period
Are the requirements {(qn, pn, τ), 1≤n≤N} feasible?
15/35
July 13, 2010 , P. R. Kumar
Characterization of feasibility
qn Load due to Client n is
wn = pnτ
Necessary condition from classical queueing theory
Unavoidable idle time
1
S
Idle
∑w
n=1
N
n
≤1
Forced to be idle
2
S
Idle
AP
But every subset of clients should also be feasible
Theorem: Feasible iff
∑w
n=1
N
n
+ I (1,2,..., N ) ≤ 1
∑w
n∈S
n
+ I(S)
≤ 1, ∀S ⊆ {1,2,..., N}
(Hou, Borkar & K 09)
16/35
July 13, 2010 , P. R. Kumar
Scheduling policies
Delivery debt of Client n
= qn − Actual timely throughput to Client n pn Give higher priority to higher debt
F
1
AP
3
F
S
2
F
F
S
Theorem: This policy is feasibility optimal
(Hou, Borkar & K 09)
17/35
July 13, 2010 , P. R. Kumar
Synchronizing clocks in a network
Time
Synchronization
Computer Science
18/35
July 13, 2010 , P. R. Kumar
Clock synchronization
Knowledge of time is important
Reference Clock 1
Clock 2
d12
d21
Theorem: It is impossible to synchronize clocks
r1 = a2 (s1 + d12 ) + b2
τ2 τ1
s1
r1
s2
r3
s4
τ2
Skew a2
Offset b2
r4
d12
d21
r2
s3
d12
d21
τ1
s2 = a2 (r2 − d21 ) + b2 ⎡ r1 ⎤ ⎡ s1 1 0 1 ⎤ ⎢ s ⎥ ⎢ r 0 −1 1 ⎥ ⎡ a2 ⎤ ⎢ 2⎥ ⎢ 2 ⎥ ⎢ a2 d12 ⎥ ⎥ ⎢ r3 ⎥ = ⎢ s3 1 0 1 ⎥ ⎢ ⎢ ⎥ ⎢ ⎥ ⎢ a2 d21 ⎥ ⎢ s4 ⎥ ⎢ r4 0 −1 1 ⎥ ⎢ b ⎥ ⎢ ... ⎥ ⎢ ... ... ... ...⎥ ⎣ 2 ⎦ ⎣ ⎦ ⎣ ⎦
So assume symmetric delays
Rank 3: Cannot estimate 4 parameters
Noisy observations?
Network?
(Graham & K ‘04) 19/35
July 13, 2010 , P. R. Kumar
Traditional approach
Assume all skews = 1
Std. Dev of Error
= Θ Diameter
(
)
8
ˆ x01
0
1
ˆ x12
2
ˆ x23
3
10
4
6
7
ˆ ˆ ˆ ˆ v3 = x01 + x12 + x23
5
Random multi-hop network with n nodes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
⎛ log n ⎞ = Ω⎜ ⎟ n ⎠ ⎝ (Gupta & K ‘98)
⎛ ⎛ n ⎞ 14 ⎞ Std. Dev of Error
= O ⎜ ⎜ ⎟ ⎜ ⎝ log n ⎟ ⎟ ⎠ ⎠ ⎝
Critical radius for connectivity Error grows polynomially
Can we do better?
20/35
July 13, 2010 , P. R. Kumar
Improving synchronization
Sum of offsets along any loop is zero
Theorem (Karp et al `03)
– Asymptotic error variance is Resistance Distance of network
e ∈ Directed Cycle
∑
xe = 0
1
Loop 1
2
Loop 2
3
4
5
Theorem
–
x = AT v
T ˆ ˆ Minimization problem:
Min x − A v ˆ v 2
–
Error is bounded for large random networks
Error = O(1)
Coordinate descent: Spatial smoothing
ˆ v j,new =
1 Nj
edges (i, j )
ˆ ∑ (v
i,old
ˆ + xij
)
ˆ log α e = 0
Lends support for feasibility of time-based computing
1 5 9 13 17 21 47 29 47 37 2 6 10 14 18 22 26 30 47 38 3 7 11 15 19 47 47 31 35 36
4
8
12
16
20
24
28
32
36
40
Similarly for skew:
e ∈ Directed Cycle
∑
80 70
80 70 60
Closeness -
(in usec)
50 40 30 20 10 0 0 50 100 150 200 250 300 Sample Number
Max Avg Min
Closeness -
60
(in usec)
50 40 30 20 10 0 0 50 100 150 200 250 300 Sample Number
Max Avg Min
Leading algorithm (FTSP, Maroti et al ‘04)
New multi-hop clock synchronization algorithm
(Solis, Borkar and K ‘05)
(Giridhar & K ’06)
21/35
July 13, 2010 , P. R. Kumar
Abstractions and architecture
Middleware
Software
Engineering
22/35
July 13, 2010 , P. R. Kumar
Challenge of abstractions
Internet
Application Layer Presentation Layer Session Layer Transport Layer Network Layer Data Link Layer Physical Layer Application Layer Presentation Layer Session Layer Transport Layer Network Layer Data Link Layer Physical Layer
Serial computation
Hardware
Software
Digital Communication
Source
Coding
Channel
Coding
von Neumann Bridge
(Valiant `90)
What are the abstractions for convergence of control with communication and computing?
Goal is to enable rapid design and deployment
– Critical Resource: Control Designer’s Time
Standardized abstractions
– Minimal reconfiguration and reprogramming
Hopefully
leading to proliferation
23/35
July 13, 2010 , P. R. Kumar
Challenge of architecture
IBM 360
First
commercially successful model
Standard software architecture
360 – All round capability
TCP/IP is de facto standard
Program as data
Interfaces
Ease of customization
Modular design of software
Portability – High level languages
Reusability – Component libraries
Layers of protocols
Breakdown networking into subproblems
Solve sub-problems in different layers
Compose solutions into a working stack
Mechanism: Encapsulation of packets
24/35
July 13, 2010 , P. R. Kumar
Convergence Lab:
The Systems
Vision Sensors
Planning and Scheduling
Automatic Control
Wireless Ad Hoc Network
25/47
(Baliga, Graham, Huang & K ‘02)
25/35
July 13, 2010 , P. R. Kumar
Abstraction layers
Middleware manages the Components
Kalman Filter
Trajecto ry Planner
Deadlock Avoidance
Set Point Generator
Image Process ing
Discrete Event Scheduler
Kalm an filter
Ima Proc ge essin
g
Application Layer
Service 3! Service 2! Clock!
Components
Middleware
TCP
DBF
Modulation
Trajecto ry Planner
System Layer
Transport Layer
Network Layer
PHY/MAC Layer
Set P Gene oint ratio n
Cont r Optim ol Law izatio n
Car
r
e troll con
nt te Eve Discre uler
Sched
Mod el Pr Cont edictive rolle r
(Baliga, Graham & K ‘04)
(Graham, Baliga & K ‘09)
(Kim & K ‘08)
26/35
July 13, 2010 , P. R. Kumar
Collision avoidance
(Schuetz, Robinson & K ’05)
27/35
http://decision.csl.uiuc.edu/~testbed/videos/CollisionAvoidance.mpg
July 13, 2010 , P. R. Kumar
Example of capabilities: Component migration
Communicate pixels?
Or compute
position?
Kalman
filter
Car
controller
Computer 1
Computer 2
Migrate Kalman Filter
(Baliga, Graham & K ‘04)
28/35
Excessive delay
July 13, 2010 , P. R. Kumar
Example of capabilities: Component migration
Communicate pixels?
Or compute
position?
Kalman
filter
Car
controller
Computer 1
Computer 2
Migrate Kalman Filter
Excessive delay
Real-time middleware
(Kim & K ’09)
29/35
July 13, 2010 , P. R. Kumar
Proofs of correctness
Formal Correctness
Methods
30/35
July 13, 2010 , P. R. Kumar
Provably correct behavior
Theorem
– Directed graph model of road network
• Each bin has in-degree 1 or out-degree 1
• System has no occupied cycles initially
– Road width:
W = R(1 − cos β (2 cos α − 1) • Initial condition:
(d, θ ) : d + R(1 − cos θ ) < W • Intersection angles ≤ γ, and road lengths:
= (2γ RR ) (R − R ) L • Multiple cars with appropriate spacing
– Car control model: Kinematic model with turn radii R and R
– Real time renewal tasks: HST scheduling with
C D ≤ 1 ∑
i i
– Then cars can be operated
• Without collisions (Safety) or
• Gridlocks (Liveness)
(Baliga & K ’05)
1 85 84 83 21 20 72 73 2 22 31 53 53 8671 82 3 35 8770 7481 5353 53 4 53 8869 2429 7580 54 5 4553 5342 4153 52 6 4653 5353 5336 7 8 8968 7679 5328 18 9067 9 7778 5353 19 17 10 91 66 65 11 64 6353 6160 92 9353 12 9596 9798 31/35
http://decision.csl.uiuc.edu/~testbed/videos/city_7cars.mpg
July 13, 2010 , P. R. Kumar
Re-convergence: The pedagogical challenge
“…the era of cyberspace and the Internet, with its emphasis on the computer as a communications device and as a vehicle for human interaction connects to a longer history of control systems that generated computers as networked communications devices.” − D. Mindell in “Feedback, Control and Computing before Cybernetics,” 2002
1950 — 2000 and continuing
– – – – – Computation: ENIAC (1946), von Neumann (1944), Turing,..
Sensing and inference: Fisher, Wiener (1949),…
Actuation/Control: Bode, Kalman (1960),…
Communication: Shannon (1948), Nyquist,…
Signal Processing: FFT, Cooley-Tukey (1965),…
2000 — onwards: Age of system building
- Nodes that can communicate, control, compute
- Larger grand re-unification of control, communication and computation
- Pedagogical challenges: Knowledge of all these fields may be important
- Undergraduate education?
- Postgraduate education?
32/35
July 13, 2010 , P. R. Kumar
References - 1
Piyush Gupta and P. R. Kumar, “The Capacity of Wireless Networks,” IEEE Transactions on Infor- mation Theory, vol. IT-46, no. 2, pp. 388-404, March 2000.
Arvind Giridhar and P. R. Kumar, “Computing and Communicating Functions Over Sensor Networks,” IEEE Journal on Selected Areas in Communications, pp. 755–764, vol. 23, no. 4, April 2005.
C. L. Liu, C.L., Layland, J.W.: Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM 20(1) (1973) 46–61
I-Hong Hou, V. Borkar and P. R. Kumar, “A Theory of QoS for Wireless.“ Proceedings of Infocom 2009, April 19-25, 2009, Rio de Janeiro, Brazil.
Scott Graham and P. R. Kumar, “Time in General-Purpose Control Systems: The Control Time Protocol and an Experimental Evaluation,” Proceedings of the 43rd IEEE Conference on Decision and Control, Paradise Island, Bahamas, pp. 4004–4009, December 14-17, 2004
Roberto Solis, Vivek S. Borkar , and P. R. Kumar, “A New Distributed Time Synchronization Protocol for Multihop Wireless Networks.”Proceedings of the 45th IEEE Conference on Decision and Control, pp. 2734–2739, San Diego, Dec. 13–15, 2006.
Piyush Gupta and P. R. Kumar, “Critical Power for Asymptotic Connectivity in Wireless Networks,” in Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming. Edited by W. M. McEneany, G. Yin, and Q. Zhang, Birkhauser, Boston, MA, pp. 547–566, 1998.
J. Elson, R.M. Karp, C.H. Papadimitriou and S. Shenker, “Global Synchronization in Sensornets.” Proceedings of LATIN,
vol. 2976, pp. 609-624, 2004.
33/35
July 13, 2010 , P. R. Kumar
References - 2
Arvind Giridhar and P. R. Kumar, “Distributed Clock Synchronization over Wireless Networks: Algo- rithms and Analysis.” Proceedings of the 45th IEEE Conference on Decision and Control, , pp. 4915– 4920, San Diego, Dec. 13–15, 2006.
Arvind Giridhar and P. R. Kumar, “The Spatial Smoothing Method of Clock Synchronization in Wireless Networks.” Submitted to Theoretical Aspects of Distributed Computing in Sensor Networks. Editors: Sotiris Nikoletseas and Jose D.P. Rolim. Lecture Notes in Computer Science. Springer-Verlag. Submitted November 28, 2009.
Liu, C.L., Layland, J.W.: Scheduling algorithms for multiprogramming in a hard-real-time
environment. Journal of the ACM 20(1) (1973) 46–61
Scott Graham and P. R. Kumar, “The Convergence of Control, Communication, and Computation,” Proceedings of PWC 2003: Personal Wireless Communication, Lecture Notes in Computer Science, vol. 2775/2003, Springer-Verlag, Heidelberg, Germany, pp. 458–475, 2003.
Scott Graham, Girish Baliga, and P. R. Kumar, “Issues in the Convergence of Control with Commu- nication and Computing: Proliferation, Architecture, Design, Services, and Middleware,” Proceedings of the 43rd IEEE Conference on Decision and Control, Paradise Island, Bahamas, pp. 1466–1471, December 14-17, 2004.
Girish Baliga and P. R. Kumar, “A Middleware for Control over Networks,” Proceedings of the 44th IEEE Conference on Decision and Control, pp. 482–487, Seville, Spain, Dec. 12–15, 2005.
Girish Baliga, Scott Graham and P. R. Kumar, “Middleware and Abstractions in the Convergence of Control with Communication and Computation,” Proceedings of the 44th IEEE Conference on Decision and Control, pp. 4245–4250, Seville, Spain, Dec. 12–15, 2005.
Scott Graham, Girish Baliga and P. R. Kumar, “Abstractions, Architecture, Mechanisms, and a Mid- dleware for Networked Control.” IEEE Transactions on Automatic Control, vol. 54, no. 7, pp. 1490– 1503, July 2009.
34/35
July 13, 2010 , P. R. Kumar
References - 3
Kyoung-Dae Kim and P. R. Kumar, “Architecture and Mechanism Design for Real-Time and Fault- Tolerant Etherware for Networked Control.” Proceedings of the 17th World Congress, The International Federation of Automatic Control, pp. 9421–9426, Seoul, Korea, July 6-11, 2008.
Kyoung-Dae Kim and P. R. Kumar, ``Design and experimental verification of real--time mechanisms for middleware for networked control.'’ 2009.
Kyoung-Dae Kim and P. R. Kumar, “The Importance, Design and Implementation of a Middleware for Networked Control Systems.” 2009.
C. L. Robinson, H.-J. Schuetz, G. Baliga and P. R. Kumar, “Architecture and Algorithm for a Labora- tory Vehicle Collision Avoidance System.” 2007 IEEE International Symposium on Intelligent Control (ISIC2007), Singapore, October 1-3, 2007.
Craig Robinson and P. R. Kumar, “Optimizing Controller Location in Networked Control Systems with Packet Drops.” IEEE Journal on Selected Areas in Communications, Special Issue on Control and Communications, pp. 661–671, vol. 26, no. 4, May 2008.
V. Gupta, B. Hassibi and R. M. Murray, "Optimal LQG Control Across Packet-Dropping Links", System and Control Letters, pp. 439-446, Vol 56, No. 6, June 2007.
Hemant Kowshik, Derek Caveney and P. R. Kumar, “Safety and Liveness in Intelligent Intersections.“ In Hybrid Systems: Computation and Control: Proceedings of 11th International Workshop, HSCC 2008, St. Louis, MO, April 22–24, 2008., pp. 301–315, Magnus Egerstedt and Bud Mishra (Eds.): Lecture Notes in Computer Science 4981, Springer–Verlag, Berlin, 2008.
A. Schafer and D. G. Victor, "The future mobility of the world population,” Transportation Resrarch, A34 (3), 171-205, 2000.
Frank Kelly, Challenges of road pricing, Stochastic Networks Conference, June 19-24, 2006, University of Illinois at UrbanaChampaign.
http://www.ifp.illinois.edu/~srikant/StochNetworks2006/schedule_smallfont.htm
35/35
July 13, 2010 , P. R. Kumar
https://netfiles.uiuc.edu/prkumar/www/talks.html
36/35
July 13, 2010 , P. R. Kumar
Thank you
37/35