Transcript ProgrammingAbstracti.. - University of Virginia, Department of

Programming Abstractions
in
Wireless Sensor Networks
Professor Jack Stankovic
Department of Computer Science
University of Virginia
Importance
• Raise the level of abstraction
• Move out of the domain of HW and
embedded systems programmer
• Amplify the applications addressed –
programmed by domain experts
• More reliable
• One of the most important areas of
research to make WSN widely used
Context
System Development
Environment
Analysis/Tools
Use of System
SQL/Queries
Actual Programming
Programming Models
• Environmental (domain specific, tracking,
monitoring, …)
– EnviroSuite
• Data/Database Centric - Queries
– SQL, TinyBD, Cougar
– Statistical and range queries
• Middleware APIs and Services
– Group Management, Token machine language
(Regiment), Milan (QoS based), Agilla
– Support for other models
•
•
•
•
Components
Database
Event
Agent
Programming Models
• Components
– nesC
• Virtual Machines
– Mate
• Functional Macro-programming
– Regiment (regions, streams)
• (Mobile) Scripts
– SensorWare
• Extend TCL interpreter with support for commands such as
query, send, wait, replicate, …
• Provides execution environment for Scripts
• Events
– Publish/subscribe
– DSWare, SNEDL, Impala
Programming Models
•
•
•
•
Model Driven
Swarm computing
Java
Linux
Program What?
•
•
•
•
Low level protocols (MAC, routing, …)
Middleware services
Application
Use of system
– Queries
Blurs
Sensor/Actuator/Communication
Resource management, team formation,
networking, aggregation, …
Heterogeneous
Homogeneous
Severe constraints
power, memory, bandwidth, cpu, cost, ...
Reliability
• Make an unreliable platform reliable!!
• HW (motes) are/will be very reliable
• Environment/wireless communication
will not be reliable
Abstractions
• Program as a whole – not individual
nodes
• Hide details (which ones, expose what)
–
–
–
–
–
–
–
–
–
Single node decisions
Asynchrony
Race conditions
False alarms
Retries
Physical details (e.g., location, sensor characteristics, …)
Faults
Scale
Storage locations
Other Questions
• How to disseminate programs
– Flooding, viral programs, gossip protocols
• Efficient on small, embedded, real-time
devices
• Long-lived systems
– Disseminate again
– Disseminate pieces of executable
Environmental Paradigm
• Current Paradigms
–
–
–
–
Single node abstractions
Explicit interactions between nodes
Read sensor data; fuse data; move data
Set actuators
• Environmental Paradigm
– Reflect the physical world directly
– Virtual world of entities (fire, people, vehicles,
pesticide, velocity, location, areas, …)
EnviroSuite
• Way to think
– Events – measurable environmental activities
– Events mapped to programming objects
– Computation is attached to these objects
• Report location, compute velocity, …
• Library provides protocols for sensor data
processing, object maintenance, inter-object
coordination, aggregation mechanisms, etc.
EnviroSuite
person
event
Base Station
vehicle
event
mapping
object type: VEHICLE
object ID: vehicle01
object type: PERSON
object ID: person01
attribute: location
attribute: location
method:
report location to the
base station every 5
seconds
method:
turn on a nearby microphone if current location
is less than 1 mile away
from the base station
EnviroSuite
event-object VEHICLE {
object_creation_condition =
ferrous object && background sound
object_resolution = 6; // minimal distance between
// two events
object_function = report.Location;
object_function = report.Speed;
}
This statement is supported by drivers in a library:
ferrous object && background sound
Level of Knowledge
Required
• Ferrous object
– Which signal processing module?
– What parameter specifications need to be
made?
– We are programming in an application that
interacts with the environment – how
divorced from that fact can the
programmer be?
Routing Protocol - SPEED
USES VELOCITY
Expose Velocity
D
E2E Distance
j
Actual Speed
i
Speed to
destination
(Set Point )
FS
E2E Delay is bound by E2E Distance/Speed SetPoint
Radio Irregularity
Do Not
Expose
DOI = 0.05
DOI = 0.2
DOI = Degree of Irregularity
Data/Database Centric
• Query Processing Architectures (SQL-based)
– Process the queries
– Route the queries
– Retrieve information efficiently (in time and with
low energy costs)
• Storage Architectures
– How/where to store collected data from sensors
– In-network storage
• At local node
• Data centric – name the data and hash to a location
• Multi-resolution (hierarchies)
Example of Query
• Retrieve, every 30 seconds, the rainfall
level if it is greater than 50 mm
SELECT R.Sensor.getRainfallLevel()
FROM RFSensors R
WHERE R.Sensor.getRainfallLevel() > 50
AND $every(30);
Many other extensions to query capability
including statistical and range based queries
Content Dissemination Caching
Receivers
(Refresh Rate,
Accuracy)
Data replicas
(Placement?)
Information source
(Aperiodic updates)
Goal: Find the optimal
communication path to
send sensory data from
a monitored source to
multiple (mobile) sinks
such that energy usage
is minimized.
Middleware APIs
• Group Management
–
–
–
–
–
Create
Terminate
Merge
Join/Leave
Assign function
• Track target
• Classify target
• Map temperature region
– Consensus
Group Management
IR Camera
Group Management
IR Camera
Examples: Tracking and
Map Regions
Base Station
Group Management - API
– Create_Group(name,function,criterion,atleast,acc
uracy) - implicit and explicit
– Destroy_Group(name)
– Join()
– Leave()
– Merge()
– Move_COG()
– Expand() -- to gain sensing confidence
– Shrink()
-- to save power
– Commit(grp_ID) - to synchronize group reconfigurations
Other Services
•
•
•
•
•
•
Naming
Directory
Location
Monitor
Configure
…
Question
• How general/specific should a
middleware service be?
Function of severity of
resource constraints
Severe
Careful interoperability
Exactly what is needed
and no more!
Excess
Capacity
More general services
Useable by many
Functional MacroProgramming (Regiment)
•
•
•
•
Apply function to data from a stream
Aggregate samples from a stream
Filter stream
Define/Disseminate Events from a area
(region)
Streams
Abstract
Regions
Area
Base
Station
Regiment (cont.)
•
•
•
•
•
Set frequency
Fidelity
Contour finding
Combine regions
Anchors (leaders for a region)
• Functional Language
Regiment
• Abstractions
– Streams, Spaces, Events, Anchors (leader
for a region), When (time)
– Regions – group of nodes with some
relationship to each other
• Like the function for a group in previous
middleware slides
• Ex. – all nodes within k radio hops of node N
• Ex. – all nodes whose proximity sensor records
a hit
Token Machine Language
(TML)
• Kind of middleware to support Regiment
PL
• Regiment
– Compiler transforms a macro-program
written in functional style into an efficient
nodal program based on a token machine
– Token machine is an intermediate language
(target) for Regiment
TML
Token from
Network
NODE
Generate
Tokens
Token Handlers –
Atomic Tasks
Name of Token
Handler
Data
Components - nesC
• Underlying execution model (TinyOS)
– Tasks and Events
– Split phase operation
• Modules
– Component Specification – Interfaces
– Component Implementation
• Configurations
– Wiring Diagrams
Tasks and Events
• Tasks
– Deferred computation
– Non-preemptable by other tasks
– Scheduled FCFS from task queue
• Events
– Execution of an interrupt handler
– Runs to completion
– Can preempt tasks and can be preempted
by other events
Application Example
sensing application
application
Routing Layer
routing
Messaging Layer
messaging
packet
byte
bit
Radio Packet
UART Packet
Radio byte
UART byte
RFM
photo
clocks
ADC
Temp
SW
i2c
HW
Components - nesC
• The nesC model:
– Interfaces:
• uses
• provides
Application
Component
D
Component
A
– Components:
• modules
• configurations
• Application:=
graph of
components
EnviroTrack on top of configuration
nesC
Component
C
Component
B
Component
F
Component
E
configuration
Interfaces
• Examples of interfaces:
interface StdControl {
command result_t init ();
command result_t start ();
command result_t stop ();
}
StdControl.nc
interface SendMsg {
command result_t send (uint16_t addr,
uint8_t len,
TOS_MsgPtr p);
event result_t sendDone ();
}
SendMsg.nc
interface Timer {
command result_t start (char type,
uint32_t interval);
command result_t stop ();
event result_t fired ();
}
Timer.nc
interface ReceiveMsg {
event TOS_MsgPtr receive (TOS_MsgPtr m);
}
ReceiveMsg.nc
Modules
• Implements a component’s specification with C code:
module MyCompM {
provides interface X;
provides interface Y;
uses interface Z;
}
implementation {
…// C code
}
MyCompM.nc
Modules
• Posting Tasks:
module BlinkM {…
}
implementation {…
task void processing () {
if(state) call Leds.redOn();
else call Leds.redOff();
}
}
event result_t Timer.fired () {
state = !state;
post processing();
return SUCCESS;
}…
BlinkM.nc
Configuration Example
• Blink application
• Wiring Example
BlinkC
Main
configuration BlinkC {
}
implementation {
components Main, BlinkM, ClockC, LedsC;
}
Main.StdControl->BlinkM.StdControl;
BlinkM.Clock->ClockC;
BlinkM.Leds->LedsC;
BlinkM
BlinkC.nc
ClockC
LedsC
Future?
• Different component models?
• nesC components are “low level” with a
fair amount of syntax
• Envirosuite, Mate, etc. do build on top
of nesC
Mate – Virtual Machine
24 Instruction Programs
Code capsules
Mate VM
(interprets)
TinyOS
Each instruction
executes as task
(slow)
Code Capsules
• One capsule = 24 instructions
• Fits into single TOS packet
– Energy efficient
• Atomic reception
• Code Capsule
– Type and version information
– Types: send, receive, timer, subroutine
• Larger programs – use several capsules
Value
• Re-programmability
– Re-task a network
• Parameter adjustment
• Self-replication
– One of the special instructions on the VM
is forward (which supports a viral-like
infection of the entire network)
• Incremental addition of new nodes
Propagation Example
Node Enters the Network
Instruction Set


One byte per instruction
Three classes: basic, s-type, x-type
basic: arithmatic, halting, LED operation
•s-type: messaging system
•x-type: pushc, blez
•
 8 instructions reserved for users to define

Instruction polymorphism
•
Example: add(data, message, sensing)
User Defined
Instructions
24 Instruction Programs
1
3
Code capsules
3
- Sound alarm
1 - Write to flash
Mate VM
(interprets)
TinyOS
Instructions
Understood by
Mate
User defined
1 2 3 4
Mate Architecture

2
3
gets/sets
PC
Operand
Stack
Return
Stack
Receive
•
1
Events
Send
0
Code
Clock timer
•Message reception
•Message send
Subroutines
Clock

Stack based architecture
 Operand stack
 Return address stack
Three events/execution
contexts:
Code Example(1)
• Display Counter to LED
gets
pushc 1
add
copy
sets
pushc 7
and
putled
halt
#
#
#
#
#
#
#
#
#
Push heap variable on stack
Push 1 on stack
Pop twice, add, push result
Copy top of stack
Pop, set heap
Push 0x0007 onto stack
Take bottom 3 bits of value
Pop, set LEDs to bit pattern
Code Example(2)
• Sense and Send
pushc 1
sense
pushm
clear
add
send
halt
#
#
#
#
#
#
#
Light is sensor 1
Push light reading on stack
Push message buffer on stack
Clear message buffer
Append reading to buffer
Send message using built-in
ad-hoc routing system
TinyOS Sense and Send
event result_t Timer.fired() {
if (state == IDLE && call Photo.sense()) {state = SENSE;}
return SUCCESS;
}
event result_t Photo.dataReady(uint16_t data) {
if (state == SENSE) {
packet->reading = data;
if (call SendMsg.send(packet, sizeof(DataBuf)) {
state = SENDING;
} else {state = IDLE;}
}
return SUCCESS;
}
event result_t SendMsg.sendDone(TOS_MsgPtr msg) {
if (state == SENDING) {state = IDLE;}
return SUCCESS;
}
Component Breakdown
• 7286 bytes code, 603 bytes RAM
Questions
• What should a programmer see?
–
–
–
–
–
–
–
New language
New middleware
Services
Components
Abstracts models
All the above
None of the above
Questions
• What would have made your life easier
in doing the programming assignments?
• What makes it easier to get the system
to work?
– Debugging tools
• Initially (in programming environment)
• On real platform
Ideas
• Move code to node – executes on
middleware, VM, interpreter
• Domain specific (good or bad?)
• Regions/Streams
• Expose/Hide?
– Performance
– Physical systems
• Disseminate
Summary
• Very active area
– It must be
• Solutions can have large impact
– Applications programmers rather than
system experts
• Standard?
– Analogy to real-time computing and
programming languages?
• WSN-Java?
Final Question
• Will there be GP WSNs (and how might
that affect the programming
abstractions)?