Consona Constraint Networks for the Synthesis of Networked Applications Refinement of a Sense-Fuse-Disseminate Paradigm for Scalable Sensor Networks

Consona Constraint Networks for the Synthesis of Networked Applications

• Refinement of a Sense-Fuse-Disseminate Paradigm for Scalable Sensor Networks

Administrative

• Project Title: CONSONA - Constraint Networks for the Synthesis of Networked Applications

• PM: Vijay Raghavan

• PI: Lambert Meertens & Cordell Green

• PI phone # :[phone]

• PI email:[e-mail] & [e-mail]

• Institution:Kestrel Institute

• Contract #:F30602-01-2-0123

• AO number: L545

• Award start date: 05 Jun 2001

• Award end date: 04 Jun 2003

• Agent name & organization: Juan Carbonell, AFRL/Rome

Subcontractors and Collaborators

• Subcontractors: none

• Collaborators: Berkeley OEP & minitask Boeing minitask

CONSONA Refinement of a Sense-Fuse-Disseminate Paradigm for Scalable Sensor Networks

Overview of Project

• Software focus

• use the motes as given
• would like to be able to use other types of hardware

• Develop model-based methods and tools that

• integrate design and code generation
•  design-time performance trade-offs
• in a goal-oriented way
•  goal-oriented run-time performance trade-offs
• of NEST applications and services
•  low composition overhead

Overview of Technical Approach

• Both services and applications are modeled as sets of soft constraints, to be maintained at run-time

• High-level code is produced by repeated instantiation of constraint-maintenance schemas

• Constraint-maintenance schemas are represented as triples (C, M, S), meaning that
• constraint C can be maintained by
• running code M,
• provided that ancillary constraints S are maintained

• High-level code is optimized to generate efficient low-level code

Overview of Demonstration

• Constraint-based specification of tracking application

• Schema-based refinement into high-level code

• assumes coordinate system

• Synthesis of low-level code

• reality check: simplified algorithm

• Code in action

Application

• Track a moving target

• solution must be scalable & robust

• For simplicity, use photocell

• target carries a standardized light source
• target-mote distance estimated from photocell reading
• could use any sensor that provides a reliable distance estimate
• RF, acoustic found to be unreliable

Specification

• Top level specification:

• maintain an estimate of the target’s position

• Mote-level specification:

• each mote maintains an estimate (est) of the target’s position
• Constraint: FieldConsistent(est)
• the estimates must agree with each other
• Constraint: SensorConsistent(photocell, est)
• the estimates must agree with the sensors
• scalable specification/requirement — local coupling

Refinement: Field Consistent

• i:mote· FieldConsistent(x)  j:neighbors(i)· EdgeConsistent(i.x, j.x)

• neighbors(i, j)  EdgeConsistent(i.x, j.x)  diffuse(x)

• code diffuse(x) { on tick do broadcast(x); on receive(x) do smooth(x, x) }

• scalable, local interaction

Refinement: Sensor Consistent

• SensorConsistent(S, x)  sense(S, x)

• code sense(S, x) { on tick do fuse(S, x) }

Refinement: Estimates

• Target Estimate = 2D rotated Gaussian

• represented as quintuple
• p(x, y) = Kּexp(-Q(x-xc, y-yc)/2)
• where Q(a,b) = uּa2 + vּaּb + wּb2
• K = 1/sqrt(uּw-v2)

Refinement: Smoothing

• Smoothing is weighted product

• smooth(e, f) = e(1-) ּf
• cheap to compute using logs under transformed coordinates
• 5 floating point additions

• 2D rotated Gaussians are closed under product

Refinement: Fuse

• To fuse a photocell reading into a position estimate

• deduce a distance estimate (ring) from the photocell reading
• interpolation over calibration table
• approximate the product of the original estimate and reading’s estimate
• not closed: use 2D rotated Gaussian that is a maximum likelihood estimator
• same means and first moments (approx.)

High-Level Code

• High-level code represented as e-Specs

• “practical category theory for motes”
• state machines with strong semantics defining each state and transition
• hope: common abstraction for Berkeley & Boeing OEPS

• Well-suited to representing single-mote modules/algorithms

• composition & refinement
• optimization at code level

• Low-level C code is automatically synthesized

Simplified Algorithm: Trilateralization

• Need simplified algorithm for today’s demo

• still getting acquainted with TOS/C

• Motes periodically broadcast distance estimates

• Motes periodically estimate new target position using (approximate) trilateralization

• and smooth with old target estimate

Demonstration

• Live

• e-Specs
• code synthesis
• tracking

Evaluation Criteria: Qualitative

• Field Consistent & Sensor Consistent

• are useful, intuitive constraints for specifying applications in scalable sensor networks

• Incremental constraint maintenance / optimization

• through perpetual smoothing & fusion is a useful coding paradigm for scalable sensor networks

Evaluation Criteria: Quantitative

• Accuracy of estimates

• most easily measured with static targets
• value: ~6 inches
• outliers more extreme

• Communication requirements

• number of messages per mote per second
• value: 2

Demonstration Issues

• TOS software is poorly documented

• circuit diagrams are of little value to software engineers (=me)

• Communication range is low when sensor boards are added

• For large scale experiments:

• field programmable motes would be nice
• faithful sensor simulators would be nice