snBENCH A Development and Run-Time Platform for Rapid Deployment

snBENCH A Development and Run-Time Platform for Rapid Deployment of Sensor Network Applications Michael Ocean Azer Bestavros & Assaf Kfoury & Adam Bradley Computer Science Department Boston University BOSS January 27th 2006 http://www.cs.bu.edu/groups/wing

Imagine a networked world of . . sensors, actuators, processors and storage, which is part of a shared physical infrastructure Not hard to imagine! January 27, 2006 BOSS: snBench Overview 2

Evolving Sensor Networks Traditional Sensor Networks : Highly constrained computation, communication, power, etc. Shared single common goal Singularly tasked entities Program the nodes Our domain: Heterogeneous/Hybrid networks Not all devices/networks are uniformly constrained Shared, transient entities Multiple, potentially conflicting goals January 27, 2006 Program the network BOSS: snBench Overview 3

Sensorium Infrastructure Sensorium: A common space equipped with video sensors (VS) for ubiquitous recognition and tracking of activities therein January 27, 2006 BOSS: snBench Overview 4

Sensoria: A Paradigm Shift The proliferation of networked, embedded, and mobile digital video sensors requires a paradigm shift in many areas of CS to address: The unique spatio-temporal aspects of sensory (video) data acquisition, processing, representation, communication, storage, real-time indexing/retrieval, data mining The challenges of programming, QoS management and coordinated resource arbitration of sensory networks, which are both embedded and mobile The other extreme in sensor networks research! January 27, 2006 BOSS: snBench Overview 5

Sensoria: Example Deployments Assistive Environments e.g. for home/hospice/elder care/ Safety Monitoring e.g. in factories/daycare/hospitals/garages/subway Intelligent Spaces e.g. for classrooms/meeting rooms/theaters/farms Secure Facilities and Homeland Security Uses e.g. at airports/embassies/prisons/ People Flow/Activity Studies January 27, 2006 e.g. at retail stores/museums/ BOSS: snBench Overview 6

snBench: SN Workbench The Sensorium is the computer Design/implement the programming and run-time infrastructure necessary for developers to specify and deploy truly distributed applications over a heterogeneous network of Sensing Elements (SEs) and of Computing Elements (CEs) What sensors could I use and what functionality do I get from them? January 27, 2006 BOSS: snBench Overview 7

snBench: Goals “Write Once, Run Wherever” Don’t program nodes Program the network! Start with building blocks Glue together with high-level language January 27, 2006 Conditionals, loops, functions Pretend the network isn’t there Sensors Stock algorithms (edge detect, face count, FFT) Location agnostic “Single System Image” BOSS: snBench Overview 8

snBench: Programming Cycle Program Compile SNAFU program is compiled to produce a plan of execution expressed in STEP Map and Link Program specified by gluing together building blocks using SNAFU language STEP plans are decomposed in smaller dispatch-able STEPs which are linked Load and Execute January 27, 2006 STEP plans are dispatched (i.e., loaded) onto a common runtime/execution environments (SXEs) BOSS: snBench Overview 9

SNAFU: SNet Apps as FUnctions! Functional specification language e.g., identify the face seen through camera 1 identify(facefind(snapshot(cam1)) ) January 27, 2006 BOSS: snBench Overview 10

SNAFU: SNet Apps as FUnctions! Use “annotative” functions for constraints e.g., what streams can be “exposed” public(facecount(snapshot(private(cam1)))) ) e.g., minimum acceptable resolution facecount(resn(800x600x24b,snapshot(cam1)) ) January 27, 2006 BOSS: snBench Overview 11

SNAFU: SNet Apps as FUnctions Functional specification language e.g., variable assignment works as in functional languages let x grabframe(cam1) in cond(facefind(x), identify(facecount(x)), “no faces found”) January 27, 2006 BOSS: snBench Overview 12

Persistence and Iteration SNAFU does not allow recursion Events in time, persistent computation achieved through the “trigger” construct email(“[email protected]”, trigger( (motion(snapshot(cam2)) && (2am NOW 4am)), snapshot(cam2))) Two general types of triggers: January 27, 2006 Transient – i.e., will expire naturally Persistent – i.e, will run “forever” BOSS: snBench Overview 13

Transient: “wait until” Trigger “Wait until p becomes true to evaluate a” trigger(p,a) do {} until (p) ; return (a) ; P True Trigger P False Time Once fired, evaluation of trigger is complete trigger(greater(roomtemp,”80c”),hvac heatoff) January 27, 2006 BOSS: snBench Overview 14

Persistent (1): Level Trigger “On Every” “As long as p is true re-evaluate a” Trigger level trigger(p,a) while(true) if (p) return (a); P True P False Time Level triggers are persistent queries that return a stream of evaluations of “a” while “p” is true January 27, 2006 BOSS: snBench Overview 15

Persistent (2): Edge Trigger “On Every First” “When p becomes true re-evaluate a” edge trigger(p,a) Trigger while(true) if (p) {return(a); while(p) {}}; P True P False Time Edge triggers are persistent queries that return a stream of evaluations of “a” every time “p” transitions from false to true January 27, 2006 BOSS: snBench Overview 16

Extension: Annotating triggers Level triggers could be made periodic This is an example of scheduling annotations period(100ms, level trigger(motion(cam1),snapshot(cam1)) ) Persistent triggers could have explicit longevity expires(10min, level trigger(motion(cam1),snapshot(cam1)) ) January 27, 2006 BOSS: snBench Overview 17

Triggers: Accessing results Three trigger “read” semantics: Trigger P True Fresh Non-blocking read - Last result is returned Blocking read - Wait for next result Fresh read - Wait for a “from scratch” result Blocking Non-blocking persistent triggers values change over time P False Time January 27, 2006 Read BOSS: snBench Overview 18

STEP: Sensorium Typed Exec Plan SNAFU -compiled-into- STEP “Instruction Set Architecture” level trigger Directed Acyclic Graph not level trigger( not(equals(0,LTE)), cond(isnil(LTE), 5, subtract(LTE,1) ) ) January 27, 2006 equals 0 BOSS: snBench Overview LTE cond isnil 5 subtract LTE LTE 1 20

STEP: Sensorium Typed Exec Plan Notes: “Evaluation” percolates up from leaf nodes toward roots. Value Nodes are always leaves. Expression nodes evaluate once then disable themselves. Trigger nodes re-enable children for re-evaluation. LTE reads a trigger January 27, 2006 level trigger not equals 0 BOSS: snBench Overview LTE cond isnil 5 subtract LTE LTE 1 21

STEP: Sensorium Typed Exec Plan STEP is the execution plan: an XML representation of this DAG “Let” nodes do not exist, they are directives to point multiple edges to the same node. Recursion is not allowed Cycles are prohibited LTE is like a “cyclesafe” cycle. January 27, 2006 level trigger not equals 0 BOSS: snBench Overview LTE cond isnil 5 subtract LTE LTE 1 22

STEP: XML Representation Serialized STEP graph represented in XML level trigger( not(equals(0,LTE)), cond(isnil(LTE),5,subtract(LTE,1)) ) stepgraph id "prog count" level trigger id "TriggerHead" exp id "not" opcode "sxe.core.not" exp id "equals" opcode "sxe.core.equals" value id "0" snobject type "snbench/integer" 0 /snobject /value last trigger eval id "lte" target "TriggerHead"/ /exp /exp exp id "cond" opcode "sxe.core.cond" exp id "isnil" opcode "sxe.core.isnil" last trigger eval id "lte1" target "TriggerHead"/ /exp value id "start value" snobject type "snbench/integer" 5 /snobject /value exp id "subtract" opcode "sxe.core.math.subtract" last trigger eval id "lte2" target "TriggerHead"/ value id "1" snobject type "snbench/integer" 1 /snobject /value /exp /exp /level trigger /stepgraph January 27, 2006 BOSS: snBench Overview 23

SnBench: Runtime components SXE: Sensorium eXecution Environment SSD: Sensorium Service Dispatcher SXE SXE SXE SXE SSD, SXE SXE SXE SXE, Compiler January 27, 2006 BOSS: snBench Overview 24

SSD: STEP Decomposition Given the state of the resources in the SN, split the STEP into smaller STEPs to be deployed onto available resources Insert into the sub-STEPs additional nodes (e.g., network sockets) that allow the sub STEPs to compute the larger STEP Find a partitioning that minimizes new computation January 27, 2006 i.e., maximize the reuse of already deployed STEP nodes [Mapping and linking] BOSS: snBench Overview 25

Map, Link, and Dispatch email SXE “[email protected]” edge trigger && 2AM clock SXE motion 4AM snapshot SXE cam2 January 27, 2006 BOSS: snBench Overview 26

STEP: Linked Representation A “linked” STEP graph includes bindings to physical resources, includes additional nodes (sockets) to reconnect flow of computation despite partitioning across physical resources January 27, 2006 BOSS: snBench Overview 27

Intrinsic Research: Scheduling Map & Link Challenges How did we arrive at this partitioning? How did we arrive at these assignments? email “[email protected]” edge trigger SXE && 2AM clock SXE motion 4AM snapshot cam2 January 27, 2006 BOSS: snBench Overview SXE 28

Scheduling: Processing Capacity Sensorium Resource Manager Keeps track of CPU loading conditions S01 45% S02 98% S03 33% SXE V01 10% SSD/ SRM SXE SXE SXE January 27, 2006 BOSS: snBench Overview 29

Scheduling: Network Capacity Sensorium Resource Manager Keeps track of current network conditions 8Mb/s 95% S01-S02 95% 8mb S01-S03 40% 100mb SXE S03-v01 20% 100mb S02-v01 75% 512kb 100Mb/s 40% SSD/ SRM SXE SXE January 27, 2006 BOSS: snBench Overview 512kb/s 75% 100Mb/s 20% SXE 30

Scheduling: Node Capabilities Sensorium Resource Manager Keeps track of STEP activity, known sensors motion email delta S01 [empty] facefind S02 [empty] bodytrack S03 SXE email V01 SSD/ SRM SXE snapshot delta motion oflow delta [empty] January 27, 2006 BOSS: snBench Overview SXE SXE 31

SSD:Partitioning and Reuse Scheduling amounts to a constrained graph embedding problem Difficult (NP-hard) Problem Approximations and heuristics Different programs may share STEP sub-graphs January 27, 2006 Such situations are obvious candidates for “reuse” BOSS: snBench Overview 32

Intrinsic Research: Scheduling Different programs may share STEP sub-graphs Examples: email(“[email protected]”, trigger((motion(snapshot(cam2)) && (2am NOW 4am)), snapshot(cam2))) trigger( facerecognizer( trigger((motion(snapshot(cam2)) && (2am NOW 4am)), snapshot(cam2)), facelibrary(“Azer Bestavros”)), email(“[email protected]”, “He’s working late again.”)) January 27, 2006 BOSS: snBench Overview 33

STEP Scheduling: CSE Common Subexpression/Subgraph Elimination email email(“[email protected]”, “[email protected]” trigger trigger((motion(snapshot(cam2)) && (2am NOW 4am)), snapshot(cam2))) && trigger motion facerecognizer 2AM clock 4AM email snapshot cam2 trigger facelibrary “[email protected]” “He’s working late again” && “Azer Bestavros” trigger( facerecognizer( trigger((motion(snapshot(cam2)) motion && (2am NOW 4am)), snapshot(cam2)), facelibrary(“Azer2am Bestavros”)), snapshot clock 4am email(“[email protected]”, “He’s working late again.”)) cam2 January 27, 2006 BOSS: snBench Overview 34

STEP Scheduling: CSE Common Subexpression/Subgraph Elimination email bg ra ph email(“[email protected]”, “[email protected]” trigger trigger((motion(snapshot(cam2)) && (2am NOW 4am)), snapshot(cam2))) Su && 2AM clock on motion 4AM m snapshot cam2 facerecognizer Co m trigger trigger facelibrary email “[email protected]” “He’s working late again” && “Azer Bestavros” trigger( facerecognizer( trigger((motion(snapshot(cam2)) motion && (2am NOW 4am)), snapshot(cam2)), facelibrary(“Azer2am Bestavros”)), snapshot clock 4am email(“[email protected]”, “He’s working late again.”)) cam2 January 27, 2006 BOSS: snBench Overview 35

STEP Scheduling: CSE Common Subexpression/Subgraph Elimination email “[email protected]” trigger email(“[email protected]”, trigger((motion(snapshot(cam2)) && (2am NOW 4am)), snapshot(cam2))) logical and trigger 2AM clock lights are on 4AM facerecognizer snapshot cam2 trigger facelibrary email “[email protected]” “He’s working late again” logical and “Azer Bestavros” trigger( facerecognizer( trigger((motion(snapshot(cam2)) && (2am NOW 4am)), lights are on snapshot(cam2)), facelibrary(“Azer2AM Bestavros”)), snapshot clock 4AM email(“[email protected]”, “He’s working late again.”)) cam2 January 27, 2006 BOSS: snBench Overview 36

Intrinsic Research: Compilation Program Optimization let x snapshot(cam2) in email(“[email protected]”, block(edge trigger(motion(x) && (2am NOW 4am), x))) let x snapshot(cam2) in trigger( edge trigger(motion(x) && (2am NOW 4am), true), email(“[email protected]”, x)) What to optimize? January 27, 2006 STEP Node count? Trigger count? BOSS: snBench Overview 37

SnBench: Runtime components SXE: Sensorium eXecution Environment SSD: Sensorium Service Dispatcher SXE SXE SXE SXE SSD, SXE SXE SXE SXE, Compiler January 27, 2006 BOSS: snBench Overview 38

Sensor eXecution Environment What does it do? Provides an abstraction to the sensing and computing capabilities of an SN participant STEP -- action Communication via HTTP Receives STEP programs via HTTP post Give results via HTTP server (XML, open standards based representations) Communicates current state/load to SSD/SRM via HTTP post Sensor interaction/abstraction January 27, 2006 Video:Java Media Framework Temperature: UDP BOSS: snBench Overview 39

Sensor eXecution Environment What does it do? Java 1.5 based classes for web server, web client, XML parser, STEP interpreter, XSLT (markup XML results) and the core functionalities core suite of “basic sensing and computing functionalities” For each exp node, there is an implementation of the so-called “opcode” in sxe.core Limitations January 27, 2006 Client must be able to run a Java run-time to participate, right? BOSS: snBench Overview 40

SXEs What if we can’t run SXE on a node? STEP: as a virtual ISA Embedded C dialects? Java ME? Alternate linking protocols Serial (base station) SN wireless protocols (e.g. 802.15.4) January 27, 2006 BOSS: snBench Overview 41

Intrinsic Research: Expressive PL Better Programming Languages Alternate Execution Environments SNAFU SnQL SnLOG SnC STEP Native C January 27, 2006 J2ME JXTA BOSS: snBench Overview SXE 42

snBench: Status Skeleton of snBench is done Basic SNAFU-STEP compiler Basic SSD Basic SXE for Basic STEP dispatcher Basic SRM Mid-powered computing nodes Sensor integration for Video sensing Berkeley Motes (temperature) DEMO January 27, 2006 BOSS: snBench Overview 43