Hide Notes 

Slide 1: Wireless Sensor Networks Lecture 8 – CS252 2/14/02 CS252/Hill Lec 8.1
Slide 2: Sensor Networks: The Vision • Push connectivity out of the PC and into the real world • Billions of sensors and actuators EVERYWHERE!!! • Zero configuration • Build everything out of CMOS so that each device costs pennies • Enable wild new sensing paradigms 2/14/02 CS252/Hill Lec 8.2
Slide 3: Why Now? Combination of: • Breakthroughs in MEMS technology • Development of low power radio technologies • Advances in low-power embedded microcontrollers 2/14/02 CS252/Hill Lec 8.3
Slide 4: Real World Apps… 2/14/02 CS252/Hill Lec 8.4
Slide 5: Vehicle Tracking 2/14/02 CS252/Hill Lec 8.5
Slide 6: Cory Energy Monitoring/Mgmt System • • • • 2/14/02 50 nodes on 4th floor 5 level ad hoc net 30 sec sampling 250K samples to database over 6 weeks CS252/Hill Lec 8.6
Slide 7: Structural performance due to multidirectional ground motions (Glaser & CalTech) Mote Layout 1 3 6`    1 5 4 1 8 1   1 5 29   1 Mote infrastructure Comparison of Results Wiring for traditional structural instrumentation + truckload of equipment 2/14/02 CS252/Hill Lec 8.7
Slide 8: Node Localization “Best Fit” Regression • Reducing Noise • Reducing Error • Results Noise 60 Error Regression Calibration Localization RSSI Noise 50 50 cm cm 20 cm 40 cm 60 cm Distance 80 cm 2/13/2002 100 cm 4 Kamin Whitehouse. Nest Retreat 2/14/02 CS252/Hill Lec 8.8
Slide 9: Sensor Network Algorithms • Directed Diffusion – Data centric routing (Estrin, UCLA) • Sensor Network Query Processing (Madden, UCB) • Distributed Data Aggregation • Localization in sensor networks (UCLA, UW, USC, UCB) • Multi-object tracking/Pursuer Evader (UCB, NEST) • Security 2/14/02 CS252/Hill Lec 8.9
Slide 10: Recipe For Architectural Research 1. Take known workload 2. Analyze performance on current systems 3. Form hypothesis on ways of improving “performance” 4. Build new system based on hypothesis 5. Re-analyze same workload on new system 6. Publish results 2/14/02 CS252/Hill Lec 8.10
Slide 11: Our Approach…. 1. Hypothesize about requirements based on potential applications 2. Explore design space based on these requirements 3. Develop hardware platform for experimentation 4. Build test applications on top of hardware platform 5. Evaluate performance characteristics of applications 6. GOTO step 1 (hopefully you’ll come up with a better set of requirements) 2/14/02 CS252/Hill Lec 8.11
Slide 12: Sensor Node Requirements • • • • • • Low Power, Low Power, Low Power… Support Multi-hop Wireless Communication Self Configuring Small Physical Size Can Reprogram over Network Meets Research Goals – – – – Operating system exploration Enables exploration of algorithm space Instrumentation Network architecture exploration 2/14/02 CS252/Hill Lec 8.12
Slide 13: First Decision: The central controller • What will control the device? • Modern Microcontroller Sidebar – What’s inside a microcontroller today? – What peripheral equipment do you need to support one? – How do you program one? 2/14/02 CS252/Hill Lec 8.13
Slide 14: Major Axes of Microcontroller Diversity • Flash based vs. SRAM based • • • • • • • Internal vs. External Memory Memory Size Digital Only vs. On-chip ADC Operating Voltage Range Operating Current, Power States and wake-up times Physical Size Support Circuitry Required – External Clocks, Voltage References, RAM – SPI, USART, I2C, One-wire – Combination of FLASH and CMOS logic is difficult • Peripheral Support 2/14/02 • Cycle Counters • Capture and Analog Compare • Tool Chain CS252/Hill Lec 8.14
Slide 15: 2/14/02 CS252/Hill Lec 8.15
Slide 16: 2/14/02 CS252/Hill Lec 8.16
Slide 17: Second Decision: Radio Technologies • Major RF Devices – Cordless Phones Digital/Analog » Single Channel – Cellular Phones » Multi-channel, Base station controlled – 802.11 » “wireless Ethernet” – Bluetooth » Emerging, low-power frequency hopping CS252/Hill Lec 8.17 2/14/02
Slide 18: What is in your cell phone? • Texas Instrument’s TCS2500 Chipset ARM9, 120Mhz + DSP >> 270.833 kbps CS252/Hill Lec 8.18 2/14/02
Slide 19: RFM TR1000 Radio 916.5 Mhz fixed carrier frequency No bit timing provided by radio 5 mA RX, 10 mA TX Receive signal digitized based on analog thresholds Able to operate in OOK (10 kb/s) or ASK (115 kb/s) mode • 10 Kbps design using programmed I/O • Design SPI-based circuit to drive radio at full speed • • • • • • Improved Digitally controlled TX strength DS1804 • Receive signal strength detector – 1 ft to 300 ft transmission range, 100 steps – full speed on TI MSP, 50 kb/s on ATMEGA 2/14/02 CS252/Hill Lec 8.19
Slide 20: TR 1000 internals 2/14/02 CS252/Hill Lec 8.20
Slide 21: Why not use federation of CPUs? • Divide App, RF, Storage and Sensing • Reproduce PC I/O hierarchy • Dedicated communications processor could greatly reduce protocol stack overhead and complexity • Providing physical parallelism would create a partition between applications and communication protocols • Isolating applications from protocols can prove costly Flexibility is Key to success Apps CPU Storage CPU Storage RF CPU Radio CS252/Hill Lec 8.21 Sensing CPU Sensors 2/14/02
Slide 22: Can you do this with a single CPU? 2/14/02 CS252/Hill Lec 8.22
Slide 23: The RENE architecture • Atmel AT90LS8535 – – – – 4 Mhz 8-bit CPU 8KB Instruction Memory 512B RAM 5mA active, 3mA idle, <5uA powered down 51-Pin I/O Expansion Connector 8 Programming Digital I/O 8 Analog I/O Lines AT90LS8535 Microcontroller • 32 KB EEPROM Transmission Power Control TR 1000 Radio Transceiver SPI Bus Coprocessor • RFM TR1000 radio • Network programmable • 51-pin expansion connector • GCC based tool/programming chain 1.5”x1” form factor 2/14/02 CS252/Hill Lec 8.23 – 1-4 uj/bit r/w 32 KB External EEPROM – Programmed I/O – 10 kb/s – OOK
Slide 24: What is the software environment? • Do I run JINI? Java? • What about a real time OS? • IP? Sockets? Threads? • Why not? 2/14/02 CS252/Hill Lec 8.24
Slide 25: TinyOS • OS/Runtime model designed to manage the high levels of concurrency required • Gives up IP, sockets, threads • Uses state-machine based programming concepts to allow for fine grained concurrency • Provides the primitive of low-level message delivery and dispatching as building block for all distributed algorithms 2/14/02 CS252/Hill Lec 8.25
Slide 26: Key Software Requirements • Capable of fine grained concurrency • Small physical size • Efficient Resource Utilization • Highly Modular • Self Configuring 2/14/02 CS252/Hill Lec 8.26
Slide 27: State Machine Programming Model • System composed of state machines • Command and event handlers transition modules from one state to another – Quick, low overhead, non-blocking state transitions • Many independent modules allowed to efficiently share a single execution context CS252/Hill Lec 8.27 2/14/02
Slide 28: Tiny OS Concepts • Scheduler + Graph of Components – constrained two-level scheduling model: threads + events init Power(mode) TX_packet(buf) – – – – Commands, Event Handlers Frame (storage) Tasks (concurrency) init • Component: Messaging Component internal thread Internal State • Constrained Storage Model – frame per component, shared stack, no heap • Very lean multithreading • Efficient Layering 2/14/02 TX_pack et_done (success RX_pack ) et_done (buffer) CS252/Hill Lec 8.28 msg_rec(type, data) msg_sen d_done) Commands power(mode) send_msg (addr, type, data) Events
Slide 29: Application = Graph of Components application Route map router sensor appln Active Messages packet Radio Packet Serial Packet Temp photo SW HW byte Radio byte UART ADC Example: ad hoc, multi-hop routing of photo sensor readings 3450 B code 226 B data bit RFM clocks Graph of cooperating state machines on shared stack 2/14/02 CS252/Hill Lec 8.29
Slide 30: System Analysis • After building apps, system is highly memory constrained • Communication bandwidth is limited by CPU overhead at key times. Communication has bursty phases. • Where did the Energy/Time go? – 50% of CPU used when searching for packets – With 1 packet per second, >90% of energy goes to RX! 2/14/02 CS252/Hill Lec 8.30
Slide 31: Architectural Challenges • Imbalance between memory, I/O and CPU – Increase memory (Program and Data) by selecting different CPU • Time/energy spent waiting for reception – Solution: Low-power listening software protocols • Peak CPU usage during transmission – Solution: Hardware based communication accelerator 2/14/02 CS252/Hill Lec 8.31
Slide 32: The MICA architecture • Atmel ATMEGA103 – – – – – – – – 4 Mhz 8-bit CPU 128KB Instruction Memory 4KB RAM 5.5mA active, 1.6mA idle, <1uA powered down SPI interface 1-4 uj/bit r/w 51-Pin I/O Expansion Connector 8 Programming Digital I/O 8 Analog I/O Lines DS2401 Unique ID Atmega103 Microcontroller • • 4 Mbit flash (AT45DB041B) RFM TR1000 radio Transmission Power Control Hardware Accelerators SPI Bus Coprocessor • • • Network programmable 51-pin expansion connector – 50 kb/s – ASK Communication focused hardware acceleration TR 1000 Radio Transceiver 4Mbit External Flash Power Regulation MAX1678 (3V) GCC based tool/programming chain Analog compare + interrupts 2xAA form factor 2/14/02 Cost-effective power source CS252/Hill Lec 8.32
Slide 33: Wireless Communication Phases Transmit command provides data and starts MAC protocol. Transmission Data to be Transmitted Encode processing Start Symbol Transmission Encoded data to be Transmitted MAC Delay Bit Modulations Transmitting encoded bits Radio Samples Start Symbol Search Receiving individual bits Synchronization Reception Start Symbol Detection Encoded data received Data Received 2/14/02 … … … … … … … Decode processing CS252/Hill Lec 8.33
Slide 34: Radio Interface • Highly CPU intensive • CPU limited, not RF limited in low power systems • Example implementations – RENE node: » 19,200 bps RF capability » 10,000 bps implementation, 4Mhz Atmel AVR – Chipcon application note example: » 9,600 bps RF capability » Example implementation 1,200bps with 8x over sampling on 16 Mhz Microchip PICmicro (chipcon application note AN008) 2/14/02 CS252/Hill Lec 8.34
Slide 35: Node Communication Architecture Options Classic Protocol Direct Device Control Protocol Processor RF Transceiver Processor Application Controller Application Controller Narrow, refined Chip-to-Chip Interface Hybrid Accelerator RF Transceiver Application Controller Memory I/O BUS Raw RF Interface Serialization Accelerator Timing Accelerator Hardware Accelerators RF Transceiver 2/14/02 CS252/Hill Lec 8.35
Slide 36: Accelerator Approach • Standard Interrupt based I/O perform start symbol detection • Timing accelerator employed to capture precise transmission timing – Edge capture performed to +/- 1/4 us Hybrid Accelerator Application Controller Memory I/O BUS Serialization Accelerator Timing Accelerator Hardware Accelerators • Timing information fed into data serializer – Exact bit timing performed without using data path – CPU handles data byte-by-byte RF Transceiver 2/14/02 CS252/Hill Lec 8.36
Slide 37: Results from accelerator approach • Bit Clocking Accelerator – 50 Kbps transmission rate » 5x over Rene implementation – >8x reduction in peak CPU overhead • Timing Accelerator – Edge captured to +/- ¼ us » Rene implementation = +/- 50 us – CPU data path not involved 2/14/02 CS252/Hill Lec 8.37
Slide 38: Power Optimization Challenge Scenario: • 1000 node multi-hop network • Deployed network should be “dormant” until RF wake-up signal is heard • After sleeping for hours, network must wake-up with-in 20 seconds Goal: • Minimize Power consumption 2/14/02 CS252/Hill Lec 8.38
Slide 39: What are the important characteristics? • Transmit Power? • Receive Power consumption of the radio? • Clock Skew? • Radio turn-on time? 2/14/02 CS252/Hill Lec 8.39
Slide 40: Solutions • Minimize the time to check for “wake-up” message • “check” time must be greater than length of wake-up message • If data packets are used for wake up signal, then “check” time must exceed packet transmission time • Instead use long wake-up tone 2/14/02 CS252/Hill Lec 8.40
Slide 41: Tone-based wake-up protocol • Each node turns on radio for 200us and checks for RF noise • If present, then node continues to listen to confirm the tone • If not, node goes back to sleep for 4 seconds • Resulting duty cycle? .0002/4 = . 005 %. • 200us due to wake-up time of the radio 2/14/02 CS252/Hill Lec 8.41
Slide 42: • Tos_sim ++ Project Ideas – RF usage modeling – Cycle-accurate simulation – Nono-joule-accurate simulation • Tiny application specific VM – – – – Source program lang Intermediate representation Mobile code story Communication model • Analysis of CPU Multithreading/Radical core architectures • Federated Architecture Alternative 2/14/02 CS252/Hill Lec 8.42
Slide 43: Project Ideas (2) • Closed loop system analysis • Channel characterization, Error Correction • Stable, energy efficient, multi-hop communication implementation • Scalable Reliable Multicast Analog • Sensor network specific CPU design • “Passive Vigilance” Circuits • Power Harvesting • Correct Architectural Balance (Memory:I/O:CPU) • Self-diagnosis/watchdog architecture • Cryptographic Support • Alternate Scheduling Models – Perhaps periodic realtime • Explore query processing/content based routing • Design and build your own X 2/14/02 CS252/Hill Lec 8.43 – Simulation of closed loop systems – Impact of design decisions on latency
Slide 44: Microcontroller Alternatives • Atmega 163 – same pin out as RENE – 2x memory – Can self-reprogram • ARM Thumb Not enough memory – lower power consumption, lower voltage – greater performance – poor integration  slow radio Peripheral support missing • TI MSP340 – Superior performance – 1/10 power consumption – Better integration No GCC, tool chain missing 2/14/02 CS252/Hill Lec 8.44