Information Processing in Sensor Networks Feng Zhao PARC formerly Xerox PARC www parc com zhao Stanford EE392S Winter 2004 Feb 3 2004 Acknowledgement PARC CoSense team Patrick Cheung Maurice Chu Leo Guibas Qingfeng Huang Jie Liu Julia Liu Jim Reich Student Interns Jaewon Shin Qing Fang Judy Liebman Elaine Cheong Soham Mazumdar Dragan Petrovic External collaborations Diffusion Deborah Estrin John Heidemann Fabio Silva UCLA USC ISI DOA Estimation Kung Yao UCLA TinyGALS Berkeley Funded in part by the DARPA SensIT Program under contract F30602 00 C 0175 PARC Smart Matter Research Smart Matter Research since 1994 Sensor networks IDSQ CADR Location services Collaborative processing Modular reconfiguration Embedded software design Constraint based control Scalable Information architecture Adaptive optimization Group management TinyGALS PIECES Distributed attention MEMS signal processing Applications Energy harvesting Large area sensor actuator arrays MEMS devices Actuator networks Smart Networked Sensors Of 9 6 billion uP to be shipped in 2005 98 will be embedded processors Intel plans to put a radio on every uP Riding on Moore s law smart sensors get More powerful Easy to use Inexpensive simple Crossbow MICA mote HP iPAQ w 802 11 Sensoria WINSNG 2 0 CPU 300 MIPS 1 1 GFLOP FPU 32MB Flash 32MB RAM Sensors external CPU 240 MIPS 32MB Flash 64MB RAM Both integrated and offboard sensors 4 MIPS CPU integer only 8KB Flash 512B RAM Sensors on board stack Super cheap tiny Smart Dust in progress CPU Memory TBD LESS Sensors integrated Ubiquitous Sensing will Change the Way People Live Work and Play Sensor nets Networked transportation Healthcare Internet Ubiquitous appliances TCP IP Core Smart Factories Networks of tiny sensors will track everything from weather to inventory BusinessWeek Aug 18 2003 Challenges Hardware challenges Limited capabilities Processing storage comm Limited resources Power bandwidth Small programs on tiny devices Sample Sensor Hardware Berkeley motes CPU 8 bit 4 MHz Atmel processor No floating point arithmetic support Radio 916 MHz RFM 10Kbps Distance 30 100ft Adjustable strength for RF transmission reception Photodiode and hood Antenna 916MHz Temperature sensor Microphone Five other sensor inputs Storage 8 KB instruction flash 512 bytes data RAM 512 bytes EEPROM on processor OS TinyOS event driven 3 5KB code space Sensors 10 bit ADC mux d over 7 analog input channels Sensing light sound temperature acceleration magnetic field pressure humidity RF signal strength Hardware 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 LED s 4 mA 0 0 Photo Diode 200 A 0 0 Temperature 200 A 0 0 Rene motes data Jason Hill Communication computation ratio Rene motes Comm 7mA 3V 10e3 8 16 8 J per 8bit Comp 5mA 3V 4e6 3 8 nJ per instruction Ratio 4 400 instruction hop Sensoria nodes Comm 100mW 56e3 32 58 J per 32bit Comp 750mW 1 1e9 0 7nJ per instruction Ratio 82 000 instruction hop Panasonic CR2354 560 mAh This means Lithium Battery runs for 35 hours at peak load and years at minimum load a three orders of magnitude difference Challenges Hardware challenges Limited capabilities Processing storage comm Limited resources Power bandwidth Networking challenges Limited support Peer to peer mesh topology Dynamic mobile unreliable connectivity No universal routing protocols No central name and registry services Both router and application host Limited infrastructure support An application of wireless sensor network fire monitoring Challenges Hardware challenges Limited capabilities Processing storage comm Limited resources Power bandwidth Networking challenges Limited support Peer to peer mesh topology Dynamic mobile unreliable connectivity No universal routing protocols No central name and registry services Both router and application host Application challenges Dynamic collaboration among nodes Global property from local execution Massively distributed multitasking Competing events tasks Real time missions Collaborative processing monitoring multiple events Rethinking the network infrastructure In wireless ad hoc networks networking is intimately coupled with sensing interaction and control needs and hence application semantics Break down traditional barriers of OSI model Consider both communication cost and application requirements to plan routes and task sensrors Application OSI OSI Model Model P S T N D P Data centric and ad hoc Address nodes based on geography and capability not by name Group management vital to scalability Limit data propagation to sensors relevant to measurement at hand Applications Query interface data management Information fusion Collaboration group management Storage time location services OS OS OS Networking processor processor processor sensors sensors sensors Next generation EmSoft As untethered sensors actuators embedded processors become ubiquitous we need new ways to program and organize them A central problem define and manage collaborative sensor groups dynamically based on their relevance to the current task and available network resources Where is the data and how to move it to where it will be needed Source Sink For example use directed diffusion routing Estrin et al Publish and subscribe Interest from user data attribute from source gradient Finding shortest paths in graph But we must also consider the content of data Moving Center of Aggregation Protocol A leader node blue square carries belief state Choose sensor in the neighborhood with good information Hand off current belief to chosen sensor new leader and update Target moving in straight line Tracking using particle filter Close up of target particles show velocity vectors Sequential Bayesian Estimation Prior info p x t z t Apply dynamics p x t 1 x t Become prior for next iteration Prediction p x t 1 z t Task sensor and get measurement Posterior Combine prediction Posterior p x t 1 z t 1 with likelihood Likelihood p z t 1 x t 1 Information Directed Sensor Querying IDSQ Idea maximize the predicted information that a sensor s measurement will bring given the current estimated distribution Information is measured using mutual information p u v I U V E p u v log p u p v IDSQ criteria k IDSQ arg max k N I X t 1 Z t 1 Z t z t where N is the set of candidate sensors i e topological neighbors This is equivalent to choosing the sensor which will give the greatest change to the current belief Sensor2 Posterior from S1 Small improvement Sensor 1 Posterior from S2