Berkeley NOW

Berkeley NOW

Operating System Design for Tiny Networked Sensors David Culler Computer Science Division U.C. Berkeley Emerging Microscopic Devices CMOS stuff is not just Moores law Micro Electical Mechanical Systems (MEMS) rich array of sensors are becoming cheap and tiny Low-power Wireless Communication I Q Imagine, all sorts of chips that are connected to the physical world and to cyberspace! 4/2001 PLL TinyOS with Pister baseband filters mixer

LNA 2 What can you do with them? Embed many distributed devices to monitor and interact with physical world Network these devices so that they can coordinate to perform higher-level tasks. => Requires robust distributed systems of hundreds or thousands of devices. Disaster Management Habitat Monitoring Circulatory Net 4/2001 TinyOS 3 Characteristics of Network Sensors Small physical size and low power consumption

Concurrency-intensive operation multiple flows, not wait-command-respond Limited Physical Parallelism and Controller Hierarchy actuators primitive direct-to-device interface Asynchronous and synchronous devices sensors Diversity in Design and Usage application specific, not general purpose huge device variation => efficient modularity => migration across HW/SW boundary storage network Robust Operation numerous, unattended, critical => narrow interfaces 4/2001 TinyOS 4

Outline Motivation for exploring a Tiny OS Tiny wireless sensor experimental platform Basics of TinyOS with Demo Dig deeper into execution model Emerging layers of abstraction Directions for exploration Wrap-up 4/2001 TinyOS 5 Isun Motherboard: Processor Core Atmel AVR Clock speed: 4 MHz Memory 8 Kbytes of program memory (flash) 512 bytes of data RAM 512 bytes of EEPROM on chip (write: 4 ms/byte) 32 8 bit registers

IO capabilities 32 general purpose IO lines Some lines also serve more specialized purposes, e.g. UART 10-bit 8-channel ADC Connector interface means that the IO lines serve a more specific purposes Interrupts No interrupt queuing 4/2001 TinyOS 6 Radio Circuit RFM Monolithics TR1000 916 MHz radio On/off keying at 10 kbps (max. 19.2 kbps) Capable of 115 kbps using amplitude shift keying Capable of turning on in 30 us Low-power listening by switching on and off on a sub-bit granularity Processor interface

RFM CNTRL 0 and 1 switch between transmit, receive, and sleep Raw, unbuffered access to transmit (RFM TX) and receive (RFM RX) Requires DC balanced signal an equal number of 1s and 0s in the signal Sampling on reception and modulating on transmission done is software Too much noise in received signal to use UART for sampling too little flexibility offered by UART Imposes real time constraints on the system Power usage Transmit current: 7 mA Receive current: 4.5 mA 4/2001 Sleep: 5 uA TinyOS 7 Expansion Connector Documented hardware interface Swap components on either side of the connector while preserving investment in sensors or main boards Sensor interfaces

4 lines dedicated to switching components on and off 7 analog voltage sensing lines 2 I2C busses SPI UART lines Debugging aids All radio-related signals: RX, TX, base band, control signals, signal strength Programming interfaces SPI and reset signals for the main processor and the coprocessor Ground, Vcc for both analog and digital circuits 12 lines reserved for future use 4/2001 TinyOS 8 Sensor Boards Basic Sensor Proto Photo resistor PW1 and ADC1 Thermistor PW2 and ADC2 Prototyping area Vibration Sensor

Photo resistor: PW1 and ADC1 Thermistor: PW4, ADC6 2 axis accelerometer: ADC2 and 3, PW2 Digital temperature: I2C Bus 1 2 axis magnetometer 4/2001 Convert magnetic fields into a differential output Field range -2 to +2 gauss Sensitivity 3.2mV/V/gauss Resolution: 27gauss at 10Hz Bandwidth: 5MHz TinyOS 9 Isun Networked Sensor 1 x 1.5 motherboard

ATMEL 4Mhz, 8bit MCU, 512 bytes RAM, 8K pgm flash 900Mhz Radio (RF Monolithics) 10-100 ft. range ATMEL network pgming assist Radio Signal strength control and sensing I2C EPROM (logging) Base-station ready stackable expansion connector all ports, i2c, pwr, clock Several sensor boards basic protoboard tiny weather station (temp,light,hum,press) vibrations (acc, temp, ...) accelerometers magnetometers 4/2001 TinyOS

10 Basic Power Breakdown Active Idle Sleep CPU 5 mA 2 mA 5 A Radio 7 mA (TX) 4.5 mA (RX) 5 A EE-Prom 3 mA

0 0 LEDs 4 mA 0 0 Photo Diode 200 A 0 0 Temperature 200 A 0 0 Panasonic CR2354

560 mAh But what does this mean? Lithium Battery runs for 35 hours at peak load and years at minimum load! three orders of magnitude difference! A one byte transmission uses the same energy as approx 11000 cycles of computation. Idleness is not enough, sleep! 4/2001 TinyOS 11 A Operating System for Tiny Devices? Traditional approaches command processing loop (wait request, act, respond) monolithic event processing bring full thread/socket posix regime to platform Alternative 4/2001 provide framework for concurrency and modularity

never poll, never block interleaving flows, events, energy management allow appropriate abstractions to emerge TinyOS 12 TOS Approach Stylized programming model with extensive static information Program = graph of TOS components TOS component = command/event interface + behavior Rich expression of concurrency Events propagate across many components Tasks provide internal concurrency Regimented storage management Current implementation is very simple Broad range of alternative execution mechanisms 4/2001 TinyOS 13 Tiny OS Concepts

Messaging Component frame per component, shared stack, no heap Very lean multithreading Efficient Layering TinyOS internal thread Internal State TX_pack et_done (success RX_pack )et_done (buffer) Constrained Storage Model 4/2001 msg_rec(type, data) msg_sen d_done) Commands,

Event Handlers Frame (storage) Tasks (concurrency) init Power(mode) TX_packet(buf) init Component: Events send_msg (addr, type, data) constrained two-level scheduling model: threads + events Commands power(mode) Scheduler + Graph of

Components 14 application Application = Component Graph Route map router sensor appln packet Radio Packet byte Radio byte bit Active Messages RFM 4/2001 Serial Packet

UART Temp photo SW HW ADC clocks TinyOS Example: ad hoc, multi-hop routing of photo sensor readings 15 Storage Breakdown (C Code) 4000 Multihop Router 3500 AM light AM Temp

3000 AM 3450 B code 226 B data Packet 2500 Radio Byte RFM 2000 Photo Temp UART Packet 1500 UART i2c 1000 Init TinyOS Scheduler

500 C Runtime 0 4/2001 TinyOS 16 Empirical Breakdown of Effort Components AM Packet Radio handler Radio decode thread RFM Radio Reception Idle Total Packet reception Percent CPU work breakdown Utilization 0.05% 1.12%

26.87% 5.48% 66.48% 100.00% 0.20% 0.51% 12.16% 2.48% 30.08% 54.75% 100.00% Energy (nj/Bit) 0.33 7.58 182.38 37.2 451.17 1350 2028.66 can take apart time, power, space, 50 cycle thread overhead, 10 cycle event overhead 4/2001 TinyOS 17

TOS Execution Model commands request action ack/nack at every boundary call cmd or post task message-event driven events notify occurrence Tasks provide logical concurrency preempted by events Migration of HW/SW boundary 4/2001 packet event-driven packet-pump Radio Packet crc event-driven byte-pump byte HW intrpt at lowest level may signal events

call cmds post tasks active message Radio byte encode/decode event-driven bit-pump bit data processing application comp TinyOS RFM 18 Dynamics of Events and Threads bit event filtered at byte layer

bit event => end of byte => end of packet => end of msg send thread posted to start send next message radio takes clock events to detect recv 4/2001 TinyOS 19 Event-Driven Sensor Data char TOS_EVENT(SENS_OUTPUT_CLOCK_EVENT)(){ return TOS_CALL_COMMAND(SENS_GET_DATA)(); } char TOS_EVENT(SENS_DATA_READY)(int data){ TOS_CALL_COMMAND(SENS_OUTPUT_OUTPUT)((data >> 2) &0x7); return 1; }

clock event handler initiates data collection sensor signals data ready event data event handler calls output command common pattern 4/2001 TinyOS 20 Component Composition include modules{ MAIN; SENS_OUTPUT; INT_TO_LEDS; CLOCK; PHOTO; }; MAIN SENS_OUTPUT CLOCK hardware.h PHOTO


char PHOTO_INIT(void); char PHOTO_GET_DATA(void); char PHOTO_PWR(char mode); }; SIGNALS{ char PHOTO_DATA_READY(int data); }; USES{ char SUB_ADC_INIT(void); char SUB_ADC_GET_DATA(char port); }; HANDLES{ char PHOTO_ADC_DONE(int data); }; 4/2001 TinyOS system/PHOTO.desc 22 Active Messages Sending Declare buffer storage in a frame

Request Transmission Naming a handler Handle Completion signal TOS_FRAME_BEGIN(INT_TO_RFM_frame) { Receiving Declare a handler Firing a handler automatic upon arrival of corresponding message behaves like any other event char pending; TOS_Msg msg; Buffer management strict ownership exchange tx: done event => reuse rx: must rtn a buffer built-in wrapper 4/2001 } TOS_FRAME_END(INT_TO_RFM_frame);

TinyOS 23 Send Message char TOS_COMMAND(INT_TO_RFM_OUTPUT)(int val){ int_to_led_msg* message = (int_to_led_msg*)VAR(msg).data; if (!VAR(pending)) { message->val = val; if (TOS_COMMAND(INT_TO_RFM_SUB_SEND_MSG)(TOS_MSG_BCAST, AM_MSG(INT_READING), &VAR(msg))) { VAR(pending) = 1; return 1; access appln msg buffer } } cast to defined format return 0; application specific ready check } build msg request transmission

destination identifier get handler identifier msg buffer mark busy 4/2001 TinyOS 24 Completion Event char TOS_EVENT(INT_TO_RFM_SUB_MSG_SEND_DONE)(TOS_MsgPtr sentBuffer){ if (VAR(pending) && sentBuffer == &VAR(data)) { VAR(pending) = 0; TOS_SIGNAL_EVENT(INT_TO_RFM_COMPLETE)(1); return 1; } return 0; } Underlying message layer notifies all sending components of completion event may need to resume activity after others completion provides reference to sent buffer to identify action Here event propagated as output done 4/2001 TinyOS

25 Handling Active Messages Fired (via dispatch) on arrival Gains ownership to buffer passed in msg accessed as MUST return ownership to a buffer If lifetime(buffer) < lifetime(handler), return incoming otherwise, return free buffer no free buffer => must punt operation and return incoming TOS_MsgPtr TOS_MSG_EVENT(INT_READING) (TOS_MsgPtr val){ ... return val; } 4/2001 TinyOS 26 TinyOS Execution Contexts events Tasks commands

Interrupts Hardware 4/2001 TinyOS 27 Typical application use of tasks event driven data acquisition schedule task to do computational portion char TOS_EVENT(MAGS_DATA_EVENT)(int data){ struct adc_packet* pack = (struct adc_packet*)(VAR(msg).data); printf("data_event\n"); VAR(reading) = data; TOS_POST_TASK(FILTER_DATA); ... 4/2001 TinyOS mags.c 28 Filter Magnetometer Data Task

TOS_TASK(FILTER_DATA){ int tmp; VAR(first) = VAR(first) - (VAR(first) >> 5); VAR(first) += VAR(reading); VAR(second) = VAR(second) - (VAR(second) >> 5); VAR(second) += VAR(first) >> 5; VAR(diff) = VAR(diff)-(VAR(diff) >> 5); tmp = VAR(first) - VAR(second); if(tmp < 0) tmp = -tmp; VAR(diff) += tmp; if((VAR(diff) >> 5) > 85){ TOS_CALL_COMMAND(MAGS_LEDg_on)(); VAR(led_on) = 255; } } 128 Hz sampling rate simple FIR filter dynamic software tuning for centering the magnetometer signal (1208 bytes) digital control of analog, not DSP ADC (196 bytes) 4/2001 TinyOS 29 Tasks in low-level operation

transmit packet send command schedules task to calculate CRC task initiated byte-level datapump events keep the pump flowing receive packet receive event schedules task to check CRC task signals packet ready if OK byte-level tx/rx task scheduled to encode/decode each complete byte must take less time that byte data transfer i2c component i2c bus has long suspensive operations tasks used to create split-phase interface events can procede during bus transactions 4/2001 TinyOS 30 Digging into Communications Stack Building up from the RFM bit level Messaging Packet Level Byte Level RFM Bit Level

Bit level abstracts away radio specifics Byte level radio component collects individual bits into bytes Packet Level constructs packets from bytes Messaging layer interprets packets as messages Data pump paradigm used to connect layers 4/2001 TinyOS 31 RFM RFM.comp Bit level interface to the RFM radio Abstracts away bit level timing, RFM specific control logic (TX vs. RX modes) Signals RX and TX bit events RFM_SET_BIT_RATE accepts 3 sampling rates 0 = 50us (2 x bit rate) 1 = 75us (1.5 x bit rate) 2 = 100us (1x bit rate) TOS_MODULE RFM; ACCEPTS{ char RFM_INIT(void); char RFM_TX_MODE(void); char RFM_TX_BIT(char data);

char RFM_RX_MODE(void); char RFM_PWR(char mode); char RFM_SET_BIT_RATE(char level); }; SIGNALS{ char RFM_TX_BIT_EVENT(void); char RFM_RX_BIT_EVENT(char data); }; 2x Bit rate used for detecting start symbol, bit rate 1.5 x used to transition to middle of bit transmission, 1x bit rate used to read and write data 4/2001 TinyOS 32 Data Pump Paradigm High level components initiate transfer (COMMANDS) Lower level components signal when more data can be handled (EVENTS) Collection of bit events aggregated into single byte event Collection of byte events collected into single packet event Packet Level

Byte Level RFM Bit Level 4/2001 TinyOS 33 Radio Byte Level RADIO_BYTE.comp, TOS_MODULE RADIO_BYTE; FOUR_B_RADIO_BYTE.comp, SEC_DED_RADIO_BYTE.comp, ACCEPTS{ char RADIO_BYTE_INIT(void); SEC_DED_RADIO_BYTE_SIGNAL char RADIO_BYTE_TX_BYTES(char data); .comp char RADIO_BYTE_PWR(char mode); }; All have similar interfaces SIGNALS{ char RADIO_BYTE_RX_BYTE_READY(char Transfer individual bits to the data, char error); radio char RADIO_BYTE_TX_BYTE_READY(char Fires off TX_READY event when success); char RADIO_BYTE_TX_DONE(void);

it can accept another byte }; 4/2001 TinyOS 34 General Radio Byte Operation Pipelines transmission transmits single byte while encoding next byte Trades 1 byte of buffering for additional latency Separates high level latencies from low level latency requirements Encoding Task must complete before byte transmission completes Decode must complete before next byte arrives Encode Task Bit transmission Byte 1 start Byte 2 Byte 1 RFM Bits 4/2001

TinyOS Byte 3 Byte 2 Byte 4 Byte 3 35 Radio Byte FSM with Tasks (Sending) 0 tx_bytes/POST_TASK tx_bit &c16 / tx_byte_rdy,tx_done 1 2 tx_bit &~c16 tx_bit &c16 / tx_byte_rdy tx_bytes/POST_TASK tx_bit &~c16

4 3 tx_bit &~c16 State Table 0 = idle 1 = waiting to send out first byte 2 = sending out byte, no next byte 3 = sending out byte, waiting to encode next byte 4 = sending out byte, done encoding next byte 4/2001 TinyOS Encode Task Executed tx_bit called tx_bytes accepted tx_byte_rdy signaled 36 tx_done signaled Task Scheduling currently simple fifo scheduler Bounded number of pending tasks When idle, shuts down node except clock Uses non-blocking task queue data structure 4/2001

TinyOS 37 DARPA-esq demo UAV drops nodes along road, carries one hot-water pipe insulation for package Nodes self configure into linear network Calibrate magnetometers Each detects passing vehicle Share filtered sensor data with 5 neighbors Each calculates estimated direction & velocity Share results As plane passes by, joins network upload as much of missing dataset as possible from each node when in range 7.5 KB of code!

4/2001 TinyOS 38 Working Across Levels Encoding Low power listening Fair and efficient network access Proximity detection Security Tiny virtual machines 4/2001 TinyOS 39 Packet Encoding / Layers Radio requires rough DC balance No more than three ones between zeros

Manchester encoding Radio byte components 4b/6b Bit error rate significant and increases with distance Radio packet components CRC, 3-redundant or SECDED with DC-balanced coding careful choice of generator matrix 8-bits => 17-bits, no CRC 4/2001 TinyOS 40 Low-Power Listening Costs about as much to listen as to xmit, even when nothing is received Only way to save power is to turn radio off when there is nothing to hear. Can turn radio on/of in about 1 bit 30 ms on every 300 ms Can detect transmission at cost of ~2 bit times Small sub-msg recv sampling Xmit:

sleep preamble b message Recv: Optimal Preamble = (2/3 Sxb)1/2 Application-level synchronization rendezvous to determine when to sample Jason Hill 4/2001 TinyOS 41 Networking issues in TinyOS context Two Problems arbitration of access to contended radio channel even under low duty cycle, due to correlated behavior self-organized dynamic multihop routing Two approaches build it into the lower communication layers expose to the application to solve

4/2001 TinyOS 42 Media Access Control Hardware: single channel RF radio Nodes contend for the same wireless channel Traffic is highly correlated Periodic nature of sensor networks applications detection of common events Collision detection mechanism is not available Channel capacity ~25 packet/s High amount of traffic due to High node density High transmission rate of each node 4/2001 TinyOS 43 Options Application attempts to schedule communication to avoid contention limit rate stagger initiation time

Communication stack provides adaptation and feedback 4/2001 TinyOS 44 Factors Application cannot tell if communication was successful without additional msgs Radio component is listening (efficiently) by default natural to introduce CSMA within that component Place MAC at RADIO_BYTE level in between application layer and RFM radio component not just backoff and retry, because listening costs If channel is very busy, backpressure to application to slow transmission rate revealed subtle jitter bug Busy Transmission Request 4/2001

TinyOS Listen for Random Period (16 bit LFB SR) Idle Transmit 45 CSMA Evaluation Channel Utilization and % Throughput per Mote at 4 packet/s Duty Cycle % Channel Utilization ~70% 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

1 2 3 4 5 6 Number of Motes 4/2001 TinyOS 7 8 9 10 Throughput per node is fair 46

Multihop Bandwidth Management Should self-organize into fair, dynamic multihop net Hidden nodes between each pair of levels CSMA is not enough P[msg-to-base] drops with each hop Investment in packet increases with distance need to optimize for low-power fairness! RTS/CTS costly (power & BW) Local rate control to approx. fairness Priority to forwarding, adjust own data rate Additive increase, multiplicative decrease Listen for retransmission as ack Simulation: of packets get through 4 levels out 4/2001 TinyOS 47 Example: Multihop Adaptive Transmission Control Max rate: 4 samples/sec - rate = 4p Channel BW ~20 p/s 1

8 - cannot expect more than 1/3 thru parent Monitor number of children (n) 1 5 1 4 1 6 (n) ~ 1/n 1 7 p = p + (n) on success (echo) B p = p * node 14 15 16 17

18 4/2001 = mean 0.36 0.56 0.55 0.55 0.39 p/s (COV) (64%) (14%) (11%) (12%) (11%) without rate control, success drops ~ per hop TinyOS 48 Proximity / Location detection Signal strength sensing Circuit works, falls off cleanly in good environment Incredibly sensitive to obstructions!

Error rates a useful proximity metric Bit errors vs. packet errors signal strength + Kalman filter provides good position detection 4/2001 TinyOS 49 Digital Pot Signal Strength 4/2001 Proc TinyOS inc dir 50k sel TX RFM

50 Near Signal Strength at low-power 4/2001 TinyOS 51 Thoughts on robust Algorithms Active Dynamic Route Determination When hear a new route beacon, record parent, retransmit from SELF, ignore additional messages for epoch Radio cell structure very unpredictable Builds and maintains good breadth-first forest Each node maintains O(1) state Fundamental operation is pruning retransmission Monotonic variables Message signature caches Takes energy to retain structure

4/2001 TinyOS 52 Authentication / Security RC-5 shared key crypto in 1.7 kb Energy costs of a secure channel Modified Tesla freshness encryption computation freshness transmission protocol for transmission 0% 0% 7% encryption MAC confidential & computation computation 0% authenticated base 2% MAC

broadcast transmission 20% Easy to compromise a node, but hard to get data many transmission 71% 4/2001 TinyOS 53 Application-Specific Virtual Machine Small byte-code interpreter component Code, static data, stack Accepts clock-event capsules Other events too Hides split-phase operations below interpreter HW + collection of components defines space of applications Allows very efficient coding within this space Capsules define specific query / logic

4/2001 TinyOS 54 Larger Challenges Programming support for systems of generalized state machines highly-concurrent, event-driven programming language, debugging, verification, composition Programming the unstructured aggregate SPMD, Data Parallel, Query Processing, Tuples Resilient Aggregators MAX vs 90 % Understanding how an extreme system is behaving and what is its envelope adversarial simulation Self-configuring, self-correcting systems 4/2001 TinyOS 55 Expanding the Computing Spectrum

Planetary Services Open Internet Services Internet Services Servers Workstations Personal Computers PDAs / HPCs/ smartphones Microscopic sensor networks 4/2001 TinyOS 56 Common issues at the Extremes Concurrency intensive data streams and real-time events, not command-response Communications-centric Limited resources (relative to load) Huge variation in load population usage & physical stimuli robustness Hands-off (no UI) Dynamic configuration, discovery Self-organized and reactive control Similar execution model

event driven, components Complimentary roles tiny semi-autonomous devices empowered by infrastructure infrastructure services connected to the real world Huge space of open problems... 4/2001 TinyOS 57

Recently Viewed Presentations

  • PHY132 Introduction to Physics II

    PHY132 Introduction to Physics II

    PHY132 Introduction to Physics IIClass 9 - Outline: ... which has units of C/m, is the amount of charge . per meter. of length. The linear charge density of an object of length . L. ... An electron is launched...
  • Title I Part D Annual Caseload Count 2019

    Title I Part D Annual Caseload Count 2019

    Introduction: When the grant year begins in July, funds are within the Title IA allocation for neglected, and for a separate grant for districts with detention centers (Part D, Subpart 2 funds).
  • Insolvency &amp; bankruptcy code, 2016 - Professional ...

    Insolvency & bankruptcy code, 2016 - Professional ...

    KEY FACETS. IBC-2016 was enacted to bring-in an umbrella law that shall encompass and accommodate the various fragmented and compartmentalized laws relating with corporate restructuring, insolvency and liquidation.. The intent was to: ensure easy and timely resolution/ recovery of bad...
  • Presentación de PowerPoint

    Presentación de PowerPoint

    Disclaimer. In addition to figures prepared in accordance with IFRS, PRISA presents non-GAAP financial performance measures, e.g., EBITDA, EBITDA margin, adjusted EBITDA, adjusted EBITDA margin, adjusted EBIT, adjusted net profit, free cash flow, gross debt and net debt, among others.
  • Biodiversity Loss and Species Extinction

    Biodiversity Loss and Species Extinction

    Overharvesting causes biodiversity loss. Vulnerable species: K-selected . Large, few in number, long-lived, and have few young. The Siberian tiger is hunted without rules and regulations. Powerful economic incentives increase poaching. Many other species are affected . Whales, sharks, gorillas....
  • Proportion difference and confidence interval based on ...

    Proportion difference and confidence interval based on ...

    Proportion difference and confidence interval based on CMH test in stratified RCT with an example in pooled analysis of HIV trials . Jacob Gong
  • Vaki Riverwatcher - Greathouse

    Vaki Riverwatcher - Greathouse

    Fish counting device. Developed for aquaculture in late 1980's. Photographs, video, silhouettes ... Sub-terminal mouth distinct. 3. Blunt or rounded head. Absence of photograph, all we got. Images. O. mykiss. ... Vaki Riverwatcher - Greathouse
  • PowerPoint - Models of the Atom - A Historical Perspective

    PowerPoint - Models of the Atom - A Historical Perspective

    a Historical Perspective Early Greek Theories 400 B.C. - Democritus thought matter could not be divided indefinitely. John Dalton 1800 -Dalton proposed a modern atomic model based on experimentation not on pure reason. Adding Electrons to the Model Dalton's "Billiard...