ASPLOS 2000

A System Architecture for Networked Sensors: 

A System Architecture for Networked Sensors Jason Hill, Robert Szewczyk, Alec Woo, Seth Hollar, David Culler, Kris Pister http://tinyos.millennium.berkeley.edu U.C. Berkeley 11/13/2000

Computing in a cubic millimeter:: 

Computing in a cubic millimeter: Advances in low power wireless communication technology and micro-electromechanical sensors (MEMS) transducers make this possible How do you combine sensing, communication and computation into a complete architecture What are the requirements of the software? How do you evaluate a given design?

Ad hoc sensing: 

Ad hoc sensing Autonomous nodes self assembling into a network of sensors Sensor information propagated to central collection point Intermediate nodes assist distant nodes to reach the base station Connectivity and error rates used to infer distance Base Station

Organization: 

Organization The Vision Hardware of today Software Requirements TinyOS system architecture System evaluation

Today’s Hardware: 

Today’s Hardware Assembled from off-the-shelf components 4Mhz, 8bit MCU (ATMEL) 512 bytes RAM, 8K ROM 900Mhz Radio (RF Monolithics) 10-100 ft. range Temperature Sensor andamp; Light Sensor LED outputs Serial Port 1.5' x 1.5'

No dedicated I/O controllers: 

No dedicated I/O controllers Bit by bit interaction with Radio Software must process bit every 100µs No buffering missed deadline  lost data Must time share on granularity of 2x sampling rate

Key Software Requirements: 

Key Software Requirements Capable of fine grained concurrency Small physical size Efficient Resource Utilization Highly Modular

TinyOS system architecture: 

TinyOS system architecture

State Machine Programming Model: 

State Machine Programming Model System composed of state machines Command and event handlers transition a module from one state to another Quick, low overhead, non-blocking state transitions Many independent modules allowed to efficiently share a single execution context

Simple State Machine Logic: 

Simple State Machine Logic bit_cnt++ bit_cnt==8 Send Byte Event bit_cnt = 0 Done No Yes Bit_Arrival_Event_Handler State: {bit_cnt} Don’t you have to do computational work eventually? 'Tasks' used to perform computational work Start

TinyOS component model: 

TinyOS component model Component has: Frame (storage) Tasks (computation) Command and Event Interface Constrained Storage Model allows compile time memory allocation Provides efficient modularity Explicit Interfaces help with robustness Messaging Component Internal State Internal Tasks Commands Events

TinyOS – The Software: 

TinyOS – The Software Scheduler and graph of components constrained two-level scheduling model: tasks + events Provides a component based model abstracting hardware specifics from application programmer Capable of maintaining fine grained concurrency Can interchange system components to get application specific functionality

Composition into a Complete Application: 

Composition into a Complete Application RFM Radio byte Radio Packet i2c Temp photo Messaging Layer clocks bit byte packet Routing Layer sensing application application HW SW ADC messaging routing

The Application: 

The Application The single node application is just another state machine A network of devices is just another collection of state machines Message_Handler(incoming_message){ if(sender_is_better_parent()){ my_parent = sender(); }else if(I_am_parent_of_sender(){ forward_message(my_parent, incoming_message); } } Clock_Event_Handler(){ check_expire(my_parent); if(my_parent != null){ send_data(my_parent); } }

Analysis: 

Analysis Let’s take apart Space, Power and Time

Space Breakdown…: 

Space Breakdown… Code size for ad hoc networking application Scheduler: 144 Bytes code Totals: 3430 Bytes code 226 Bytes data

Power Breakdown… : 

Power Breakdown… But what does this mean? Lithium Battery runs for 35 hours at peak load and years at minimum load! That’s three orders of magnitude difference! A one byte transmission uses the same energy as approx 11000 cycles of computation.

Time Breakdown…: 

Time Breakdown… 50 cycle thread overhead (6 byte copies) 10 cycle event overhead (1.25 byte copes)

How well did we meet the requirements?: 

How well did we meet the requirements? Capable of fine grained concurrency Small physical size Efficient Resource Utilization Highly Modular

Conclusions: 

Conclusions People are working on shrinking sensors and communication, we need to focus on what brings them together TinyOS is a highly modular software environment tailored to the requirements of Network Sensors, stressing efficiency, modularity and concurrency We now have a whole new set of tradeoffs need to investigate

Hardware Kits: 

Hardware Kits Two Board Sandwich Main CPU board with Radio Communication Secondary Sensor Board Allows for expansion and customization Current sensors include: Acceleration, Magnetic Field, Temperature, Pressure, Humidity, Light, and RF Signal Strength Can control RF transmission strength andamp; Sense Reception Strength

How to get more information:: 

How to get more information: http://tinyos.millennium.berkeley.edu

Real time operating systems: 

Real time operating systems QNX context switch = 2400 cycles on x86 pOSEK context switch andgt; 40 µs Creem -andgt; no preemption

TOS Component: 

TOS Component Messaging Component AM_SUB_INIT AM_SUB_POWER AM_SUB_TX_PACKET AM_TX_PACKET _DONE AM_RX_PACKET _DONE Internal State AM_INIT AM_POWER AM_SEND_MSG AM_MSG_REC AM_MSG_SEND_DONE Internal Tasks Commands Events //AM.comp// TOS_MODULE AM; ACCEPTS{ char AM_SEND_MSG(char addr, char type, char* data); void AM_POWER(char mode); char AM_INIT(); }; SIGNALS{ char AM_MSG_REC(char type, char* data); char AM_MSG_SEND_DONE(char success); }; HANDLES{ char AM_TX_PACKET_DONE(char success); char AM_RX_PACKET_DONE(char* packet); }; USES{ char AM_SUB_TX_PACKET(char* data); void AM_SUB_POWER(char mode); char AM_SUB_INIT(); };

Assembling Components: 

Assembling Components Assemble overall system structurally using either textual tools or structural VHDL Allows for compile time resolution of event handlers Eliminates need for registration mechanisms and dynamic dispatch Automatically allows events to be handled by multiple components. (Power, Init,…) Significantly more flexibility than library based component models Less runtime overhead than OOP Allows for more aggressive in-lining

Ad hoc networking: 

Ad hoc networking Each node needs to determine it’s parent and its depth in the tree Each node broadcasts out andlt;identity, depth, dataandgt; when parent is known At start, Base Station knows it is at depth 0 It send out andlt;Base ID, 0, **andgt; Individuals listen for minimum depth parent 0 Base

Easy Migration of the Hardware Software Boundary: 

Easy Migration of the Hardware Software Boundary TinyOS component models hardware abstractions in software Component model allows migration of software components into hardware Example: Bit level radio processing component could be implemented as specialized FIFO with complex pattern matching Could reduce CPU utilization while sending by more than 50%

Sample tradeoffs: 

Sample tradeoffs

Hardware Kits: 

Hardware Kits Two Board Sandwich Main CPU board with Radio Communication Secondary Sensor Board Allows for expansion and customization Current sensors include: Acceleration, Magnetic Field, Temperature, Pressure, Humidity, Light, and RF Signal Strength Can control RF transmission strength andamp; Sense Reception Strength

TOS Component: 

TOS Component Messaging Component Internal State Internal Tasks Commands Events

Energy: 

Energy It turns out energy is your most valuable resource Traditional notions of resources – memory, CPU, I/O become expenses, not resources All components must support low power modes

How well did we meet the requirements?: 

How well did we meet the requirements? Small physical size Complete applications in 3.5 Kbytes Useful applications developed for 4Mhz, 8-bit CPU Efficiency Demonstrated by our ability to use a single controller to manage multiple RAW I/O sources State Machine programming model allows efficient use of CPU and memory Support multiple simultaneous flows of data though single node 50 cycle thread overhead, 10 cycle event overhead Modular Component model allows efficient composition of task specific applications Model allows multiple applications to run side-by-side

What does it take to do this with…: 

What does it take to do this with… 4 MHz embedded microcontroller 512 bytes of RAM 8K of ROM Radio with 'bit-by-bit' interface Milliamps of power

Emerging Themes: 

Emerging Themes Growth rates… data andgt; storage andgt; CPU andgt; communication andgt; batteries Graph of ^

Future Goals:: 

Future Goals: Short Term Deploy sensor net for week long trials Target Civil Engineering’s and The Center For the Built Environment’s needs for a real world deployment. Determine algorithms for aggregation and analysis of data inside the network. Support applications where data is 'picked up' by roaming data collection nodes. Long Term Deploy networks of 1000s of nodes Year long, unattended deployments

What is performance: 

What is performance Physical Size? Power consumption? Overhead? Data Throughput? Total network battery life? Measurement accuracy? Data Latency? Reconfigurability?

Dynamics of Events and Threads: 

Dynamics of Events and Threads Message Send Transition

Cut from energy slide.: 

Cut from energy slide. How do you allocate your power? Communication, computation, sensing or actuating What new tricks can you play to conserve it Duty cycle Lower accuracy Data compression, aggregation, filtering

State machine example: 

State machine example n++