Kestrel PI Presentation

Information about Kestrel PI Presentation

Published on October 30, 2007

Author: Mentor

Source: authorstream.com

Content

CONSONA Constraint Networks for the Synthesis of 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: [email protected] & [email protected] 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

Related presentations


Other presentations created by Mentor

Johari Window
30. 10. 2007
0 views

Johari Window

ConsolServiceCorp
28. 04. 2008
0 views

ConsolServiceCorp

astwood
22. 04. 2008
0 views

astwood

Eco24 16
17. 04. 2008
0 views

Eco24 16

wipo smes uln 07 www 89155
16. 04. 2008
0 views

wipo smes uln 07 www 89155

taiex ghymers rijen2006 ppt
14. 04. 2008
0 views

taiex ghymers rijen2006 ppt

e future
13. 04. 2008
0 views

e future

sapir 12 2007
10. 04. 2008
0 views

sapir 12 2007

cbm47 441
09. 04. 2008
0 views

cbm47 441

Ocean
07. 04. 2008
0 views

Ocean

Closing Plenary PERUGIA
30. 03. 2008
0 views

Closing Plenary PERUGIA

The Ming and Qing Dynasties
25. 03. 2008
0 views

The Ming and Qing Dynasties

fables and morals
14. 09. 2007
0 views

fables and morals

Temperate Woodland
14. 09. 2007
0 views

Temperate Woodland

OB IDDRI 200104
12. 10. 2007
0 views

OB IDDRI 200104

NacTem2007XuUszkoreit
15. 10. 2007
0 views

NacTem2007XuUszkoreit

Leduff course 1
16. 10. 2007
0 views

Leduff course 1

WIM
16. 10. 2007
0 views

WIM

Shakespeare Presentation
19. 10. 2007
0 views

Shakespeare Presentation

Puska
07. 09. 2007
0 views

Puska

Mystery Animal
14. 09. 2007
0 views

Mystery Animal

CREATION to EVOLUTION
14. 09. 2007
0 views

CREATION to EVOLUTION

nw pall care bad news
29. 09. 2007
0 views

nw pall care bad news

SUPPLY LCS MDS
22. 10. 2007
0 views

SUPPLY LCS MDS

PRESENTACION GTI Malaga
24. 10. 2007
0 views

PRESENTACION GTI Malaga

ethics health disparities
29. 10. 2007
0 views

ethics health disparities

halt
23. 10. 2007
0 views

halt

BTL Fuels
16. 11. 2007
0 views

BTL Fuels

2005 CeladrinLecture
17. 11. 2007
0 views

2005 CeladrinLecture

newsletters
05. 10. 2007
0 views

newsletters

Moscow Presentation
23. 11. 2007
0 views

Moscow Presentation

6 338 Progress Presentation
28. 12. 2007
0 views

6 338 Progress Presentation

6 01 T P Analog Systems
03. 01. 2008
0 views

6 01 T P Analog Systems

Prepare Yourself
04. 10. 2007
0 views

Prepare Yourself

idruspresentation
07. 01. 2008
0 views

idruspresentation

8p
24. 10. 2007
0 views

8p

stewart
08. 10. 2007
0 views

stewart

lizhitang
11. 10. 2007
0 views

lizhitang

Inter scholastic Sports
09. 07. 2007
0 views

Inter scholastic Sports

High School Athletics
09. 07. 2007
0 views

High School Athletics

4479
09. 07. 2007
0 views

4479

42 sp101
09. 07. 2007
0 views

42 sp101

2005 Flag Football Clinic
09. 07. 2007
0 views

2005 Flag Football Clinic

lec TC strain gauge
16. 02. 2008
0 views

lec TC strain gauge

SNAP Propulsion
07. 11. 2007
0 views

SNAP Propulsion

Legend Powerpoint
28. 02. 2008
0 views

Legend Powerpoint

lect10
14. 09. 2007
0 views

lect10

bec
15. 10. 2007
0 views

bec

APS NW Poster
12. 03. 2008
0 views

APS NW Poster

UofWfAC06
10. 03. 2008
0 views

UofWfAC06

DrFlock
09. 07. 2007
0 views

DrFlock

health sports
09. 07. 2007
0 views

health sports

ASTR 2006 Presentation Template
29. 10. 2007
0 views

ASTR 2006 Presentation Template

4 DSM Design Guide
02. 01. 2008
0 views

4 DSM Design Guide

LiuhtoBaltic04
26. 10. 2007
0 views

LiuhtoBaltic04

STKU5 Larson
19. 06. 2007
0 views

STKU5 Larson

standard email
19. 06. 2007
0 views

standard email

Software Versions
19. 06. 2007
0 views

Software Versions

SDT Tech Briefing06 01 07
19. 06. 2007
0 views

SDT Tech Briefing06 01 07

SDT Tech Briefing
19. 06. 2007
0 views

SDT Tech Briefing

refresh cycle07
19. 06. 2007
0 views

refresh cycle07

Q2 FY07 Slides
19. 06. 2007
0 views

Q2 FY07 Slides

Q1 FY07 Slides
19. 06. 2007
0 views

Q1 FY07 Slides

psj 0 6 yukai e
19. 06. 2007
0 views

psj 0 6 yukai e

psj 06 schoenfeld e
19. 06. 2007
0 views

psj 06 schoenfeld e

PRI050 WH06
19. 06. 2007
0 views

PRI050 WH06

portal
19. 06. 2007
0 views

portal

usc csci 530 f06 l13
19. 06. 2007
0 views

usc csci 530 f06 l13

BOSC Markel
14. 09. 2007
0 views

BOSC Markel

PresentationBA avril06
23. 10. 2007
0 views

PresentationBA avril06

volvo 09
29. 02. 2008
0 views

volvo 09

qz qc mrt ridership
26. 03. 2008
0 views

qz qc mrt ridership

3a 3 Hellsten
14. 09. 2007
0 views

3a 3 Hellsten

1 IARU DoAST Presentation
09. 07. 2007
0 views

1 IARU DoAST Presentation

sicily03
19. 06. 2007
0 views

sicily03

norway
14. 12. 2007
0 views

norway

1999KC os tri
09. 07. 2007
0 views

1999KC os tri

Virgo Sigrav2004 SF
15. 11. 2007
0 views

Virgo Sigrav2004 SF

RICyT Innocom
25. 10. 2007
0 views

RICyT Innocom

Telekomunikacja Polska 1
14. 09. 2007
0 views

Telekomunikacja Polska 1

sas06 das
19. 06. 2007
0 views

sas06 das

parallel session 1
07. 09. 2007
0 views

parallel session 1

Ch10rev 06
19. 02. 2008
0 views

Ch10rev 06

DemoStudents2005
03. 10. 2007
0 views

DemoStudents2005

interiorscapeplants2
07. 12. 2007
0 views

interiorscapeplants2

PRS328 Schechter
19. 06. 2007
0 views

PRS328 Schechter

ASEAN China
10. 10. 2007
0 views

ASEAN China

tpa 6040a4 overview
19. 06. 2007
0 views

tpa 6040a4 overview

2006 AHM Dissemination Update
17. 10. 2007
0 views

2006 AHM Dissemination Update

Bhat
21. 11. 2007
0 views

Bhat

Aho ealta2006
07. 09. 2007
0 views

Aho ealta2006

Fairness
14. 09. 2007
0 views

Fairness

Ch22
15. 11. 2007
0 views

Ch22

Ready Boost
19. 06. 2007
0 views

Ready Boost

05 asphalt institute
26. 02. 2008
0 views

05 asphalt institute

LightGina
20. 03. 2008
0 views

LightGina

Working Water Conaway
28. 12. 2007
0 views

Working Water Conaway

HERDING101Presentati on
19. 11. 2007
0 views

HERDING101Presentati on

currentshow
02. 11. 2007
0 views

currentshow

flowes class4
11. 12. 2007
0 views

flowes class4