Kestrel PI Presentation

CONSONAConstraint Networks for the Synthesisof Networked Applications: 

CONSONA Constraint Networks for the Synthesis of Networked Applications Lambert Meertens Cordell Green Kestrel Institute Lambert Meertens Asuman Sünbül Stephen Fitzpatrick Matthias Anlauff http://consona.kestrel.edu/ NEST PI Meeting San Francisco, CA, July 15–16, 2003

Administrative: 

Administrative Project Title: CONSONA - Constraint Networks for the Synthesis of Networked Applications PM: Vijay Raghavan PI: Lambert Meertens & Cordell Green PI Phone #: 650-493-6871 PI Email: meertens@kestrel.edu & green@kestrel.edu Institution: Kestrel Institute Contract #: F30602-01-C-0123 AO number: L545 Award start date: 05 Jun 2001 Award end date: 04 Jun 2004 Agent name & organization: Roger Dziegiel, Jr, AFRL/Rome

Subcontractors and Collaborators: 

Subcontractors and Collaborators Subcontractors none Collaborators none

Consona  Constraint Networks for the Synthesis of Networked Applications: 

Consona Constraint Networks for the Synthesis of Networked Applications Lambert Meertens / Cordell Green Kestrel Institute

Project Objective: 

Project Objective The Consona project aims at developing truly scalable fine-grain fusion of physical and information processes in large ensembles of networked nodes In particular we’re interested in cases where the networked system can be viewed as a discrete approximation of computation on a continuous field Large-scale fine-grain systems have many potentially serious bottlenecks, and the design process must allow exploring trade-offs

Overview of Technical Approach: 

Overview of Technical Approach Services and applications are modeled as 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 provided that ancillary constraints S are maintained, executing code M maintains constraint C High-level code is optimized to generate efficient low-level code

Continuous Soft Constraints: 

Continuous Soft Constraints General Approach System of soft constraints on a set x of real ‘unknowns’: y  0, where y  f(x) for some smooth vector-valued function f Exact equality y = 0 is typically unattainable Instead, try to minimize yTy (‘Least Squares’): scalar yTy = 0 precisely when y = 0 exactly Under (e.g.) solution uniqueness, solution of system yTyx = 0, where yx is the matrix of partial derivatives of y with respect to the variables in x, guarantees minimality of yTy Solve this system

Continuous Soft Constraints ctd.: 

Continuous Soft Constraints ctd. Overcoming Computational Complexity For large numbers of motes the number of unknowns may be large and direct solution unfeasible Instead, partition the problem so that each mote is ‘the responsible agent’ for only a few unknowns (not: constraints) Each agent tries to minimize yTy for ‘its’ unknowns and disseminates the results, using disseminated estimates for the values of the other unknowns Repeat as needed

Localization as Constraints (1): 

Local Map Formation Unknowns: xi and yi for i ranging over the participating motes Assume measured distances Di j are known Constraints: di j – Di j  0, where di j is the Euclidean distance between (xi ,yi) and (xj ,yj) Transforming the Constraints Constraints: Constraints: This is a linear ‘soft’ equation in xi and yi ! Localization as Constraints (1)

Localization as Constraints (2): 

Solving the Constraints For locating mote i, we have one soft constraint for all (unordered) pairs of nodes to which it has a known distance estimate These are not all independent, but enough to determine the location of a 3-connected mote, unless the other motes are all collinear Now solve as before: the final system has just two linear equations in two unknowns A ‘starter’ is needed: first construct a map for a triangle with known side lengths Localization as Constraints (2)

Localization as Constraints (3): 

Reconciling Local Maps of Different Motes High-level variant of Sense-Fuse-Disseminate paradigm Constraint: for some isometric transformation T, for motes i that appear on both maps Two-step process: first solve for (unknown parameters of) T; next average T(xi ,yi) and Localization as Constraints (3)

Imposing One Color / System / …: 

Imposing One Color / System / … Each mote i has a random number 0  ri < 1 Mote broadcasts its ‘color’ with ri to neighbors Neighbor j adopts ‘color’ and ri if ri < rj

Strengths of Localization Method: 

Strengths of Localization Method Expected strengths, have to be borne out by experiments with real motes Does not require anchor motes — but can use them if available Can be used in anytime mode IF ranging can be squeezed in as ongoing background activity Lowered sensitivity to ‘noise’, especially in combination with simple outlier detection and rejection Modest memory use

Weaknesses of Localization Method: 

Weaknesses of Localization Method Depends on heavy-duty ranging (but only required in initialization phase for stationary motes) Patching together of local maps gives ‘flabby’ global map, even if soft constraint di j – Di j  0 is satisfied quite well — alas unavoidable for all methods constructing a map from perturbed local distance data If long-range ranging is possible, problem can be circumvented by multi-level approach: use map from higher level as scaffolding for next level

Development Status: 

Development Status Works in simulated environment for large numbers of nodes Coded in nesC, compiles, runs, and sometimes produces promising results but needs further work — some “Can’t Happen’s” do About 1200 LOC for actual algorithms, plus say 2000 LOC for inter-mote communication (data collection and dissemination) Can this use Neighborhood service? Needs to be looked into

300 Motes, No Noise: 

300 Motes, No Noise

200 Motes With Noise: 

200 Motes With Noise

Kestrel’s Simulator Extensions: 

Based on Berkeley’s Nido Simulation of microphone and sounder (not used in experiments, physical model for sensitivity, delays etc. not validated) Simulation of the VU Acoustic Ranging component (used for Kestrel’s work on localization, validated for MICA2 by similar results for TestAcousticRanging as on hardware motes) Simulation of magnetometer (used for simulation of ‘MagTrackingDemo’ application) Kestrel’s Simulator Extensions

Microphone/Sounder Simulation: 

Microphone/Sounder Simulation Kestrel has extended the graphical interface to the Nido simulator (TinyViz) that it visualizes and animates microphone and sounder events. It communicates with the SMSIM extension to the TinyOS simulator using the plug-in mechanism provided by the TinyViz framework. The microphone/sounder plug-in provides the following functionality: Assignment of mote locations Animation of microphone and sounder events

Microphone/Sounder Simulation ctd.: 

Microphone/Sounder Simulation ctd. Quick start documentation/installation guide available at consona.kestrel.edu Implementation is explained by a walk-through scenario for a given mote emitting a sound at a given time Documentation describes how tone detection events are created in the neighboring motes

Simulation of VU Acoustic Ranging: 

Simulation of VU Acoustic Ranging The VU Ranging component is used to determine distances between motes by using the difference between time-of-flight for a radio signal and a sound signal The motes emit once every minute a radio signal and a chirping sound at the same time, so that receiving motes can estimate the distance to the sender from the time elapsed between the times of arrival of the two signals We do not simulate the actual algorithm; instead, the simulated component provides the same interface and similar behavior to its ‘users’

Simulation of MagTrackingDemo: 

Simulation of MagTrackingDemo Extension of Nido for simulating the MagTrackingDemo application Magnetometer sensor simulation analyzed real sensor values developed a model of a magnetometer implemented a replacement component for the magnetometer in platforms/pc Documentation and implementation guide at consona.kestrel.edu

Toolset: Modeler / Generator: 

Toolset: Modeler / Generator Modeler for Constraint Decomposition various minor improvements not used for present work on Localization: requires advanced symbolic algebra capabilities Consona Code Generator work on adapting code generation from TOS C to nesC not yet in implementation phase — priority given to work on Localization

Project Schedule and Milestones: 

Project Schedule and Milestones Modeling using constraints: achieved Toolset: preliminary design – done, informal Prototype modeling toolset: done Sensor extensions to mote simulator: acoustic, magnetic Localization service: designed and implemented Spring 2004: Handling of non-Gaussian noise in localization service June 2004: Integrated modeler & generator Year One Year Two Year Three Design of modeler Jun ’01 Jun ’02 Jun ’03 Jun ’04 Model of example NEST application Demo on Boeing OEP Localization Service Localization with non-Gaussian noise Prototype generator Prototype modeler Integrated modeler & generator

Goals and Success Criteria: 

Goals and Success Criteria Localization service scalability: rate of increase in computational, storage and communication costs with number of motes accuracy: error in position estimates as a function of error in distance estimates Code generation compactness of abstract code vs. compactness of nesC code

Project Plans: 

Project Plans Investigate how localization service can be adapted to non-Gaussian noise in distance estimates e.g., extend outlier rejection methods e.g., use multi-hypothesis techniques for initial map construction by individual motes (before inter-mote reconcilliation) Adapt code generator to nesC Integrate modeler with generator

Technology Transition/Transfer: 

Technology Transition/Transfer Technology transition activities identified: currently none