Transcript Brooks_Workshop_10_99 - Electrical and Computer

Workshop - RSN Update
Richard R. Brooks
Head
Distributed Intelligent Systems Dept.
Applied Research Laboratory
Pennsylvania State University
P.O. Box 30
State College, PA 16804-0030
email: [email protected]
Tel. (814) 863-5698
Fax (814) 863-1396
Dept. (814) 863-5735
October 7, 1999
Reactive Sensor Network
1
Research Problems
• Phase 1: How to best implement communications and computation
mobility for ad hoc wireless sensor networks.
• Phase 2: Methods, algorithms, and software for: distributed dynamic
calibration of redundant sensors, and ad hoc routing for sensor data to
conserve bandwidth.
• Phase 3: Local behaviors for globally desirable behavior of the system
in response to random, chaotic, non-linear network disruptions.
• Phase 4: Find the limits of a global system’s ability to adapt using
purely local actions.
October 7, 1999
Reactive Sensor Network
2
Phase I: RSN Mobile code approach
Will support:
Will not consider:
• Security beyond trusted code model
• Code migration
• Debugging support
• “Write once run anywhere”
• Interfaces between modules
These topics are orthogonal.
October 7, 1999
• Compiled languages
• Interpreted languages
• Hardware dependencies
• Internet and wireless nodes
• Adaptation to system state
• Virtual memory model
• Explicit programming
• Data pipelines
• On the fly compression/decompression
• On the fly compilation
• Resource recovery
Reactive Sensor Network
3
ARL/MCN
service on NT
ARL/MCN
Service on
WINS/NG
Code
Repository
ARL/MCR
ARL/MCN
service on NT
Data
description
Gateway
HW
description
DB
engine
ARL/MCN
Service on
WINS/NG
ARL/MCN
Service on
WINS/NG
Scenario 1: User Request
ARL/MCN
Service on
WINS/NG
GUI
October 7, 1999
Reactive Sensor Network
4
ARL/MCN
service on NT
ARL/MCN
Service on
WINS/NG
Code
Repository
ARL/MCR
ARL/MCN
service on NT
Data
description
Gateway
HW
description
DB
engine
ARL/MCN
Service on
WINS/NG
ARL/MCN
Service on
WINS/NG
Scenario 2: Virtual Memory
ARL/MCN
Service on
WINS/NG
GUI
October 7, 1999
Reactive Sensor Network
5
REAP -Remote Execution and Action Protocol
• Request and control of remote code execution
• Transaction based with multiple concurrent requests in a transaction
• A single transaction may involve multiple nodes
• Multiple concurrent transactions supported
• Transaction synchronization supported
• Push and Pull data access
• Data pipelines supported
• API provided for use by others in Sensor IT community
• URLs identify data and code
• Allows data gathering and scattering
• Designed to minimize power consumption by ACK & NAK packets
October 7, 1999
Reactive Sensor Network
6
Version 1.0 Delivery in January 2000
January delivery will support:
• Windows NT / Windows CE
• IP connections
• Well-defined C++ API for use by other research groups
• Registration of code, hardware, and data types
• Programs registered can be in any language (with caveats)
• .DLL and .EXE
• Garbage collection
• Explicit execution
• Data pipelines
Updates during phase II / III will provide more complete support:
• WINS NG API
• On-the-fly compilation / build
• On-the-fly compression / decompression
• Dependency graphs
• Scheduling and adaptation support
October 7, 1999
Reactive Sensor Network
7
Phase II: Sensor Collaboration
1) Use of redundant readings increase
accuracy / dependability
• Set of redundant sensor data
• Weight by variance from estimate
• Dynamic calibration
• Distributed approach
• Asynchronous algorithm
October 7, 1999
2) Use of redundant data consumes
bandwidth
• Queries for limited area
• Design “reverse-multicast” tree
• Combine only local information
• Conserve resources
3) Both are extremes of a continuum
• Implement and test both
• Quantify costs/ benefits
• Physical tests on WINS NG
• Simulations test scalability
• Merge into a common approach
• Allow graceful degradation
Reactive Sensor Network
8
Network model for simulation
• Regular grid
• regular tessellation
• Stochastic grid
• position variance within grid
• Single neighborhood (1 gateway)
• Number of nodes
• Node density
• NG node variables
0.7
0.6
0.5
Ps– Sensor position
rs – Sensor position range
rc – Sensor communication
range
 – Variance of sensor position
in stochastic grid
• simulated by stochastic variables
• sensor range
• communications range
• battery lifetime
0.4
• Data types

0.3
rc
0.2
rs
0.1
0
Ps
October 7, 1999
• different method for each type
• binary
• code book / enumeration
• continuous value
• vectors of continuous
• 1-D (time series)
• 2-D (image)
• 3-D (sequence of images)
• Queries
• entire grid until failure
• position at random
Reactive Sensor Network • following target through grid
9
Phase III: Task / Data routing
• IP resources have fewer power constraints
• Route to nearest gateway
• Similar to mobile ad-hoc routing
• Queries tied to physical location
• Queries not tied to machine identity
• Routing tables unnecessary, expensive
• Power & congestion information unstable
• Routing to conserve energy (trade-off)
• Routing to minimize delay (trade-off)
• Decision made at each hop
• Decision based on immediate neighborhood
• “Water flowing downstream”
• Example initial conditions
October 7, 1999
Reactive Sensor Network
10
Model evolution of network resources over time
using empirical estimates of resource consumption
to route data and allocate tasks to nodes
October 7, 1999
Reactive Sensor Network
11
Conclusion
• Phase I underway
–
–
–
–
–
–
Draft C++ API
Remote Execution and Action Protocol
Windows CE / NT Service
v. 1.0 delivery 01/2000
API available for use by other programs
Requests accepted, as well as .DLLs and .EXEs for testing
• Initial planning for phase II
–
–
–
–
Experimental designs for physical tests and simulations
Coding for dynamic calibration
Conception of network topology
Resource conservation concepts
• Phase III will build on I & II
– Survey of ad hoc routing methods
– Sensor IT specific routing constraints established
– Network modeling methodology
October 7, 1999
Reactive Sensor Network
12