Transcript N - Lane Department of Computer Science and Electrical Engineering

Scalable and reliable
wireless sensor network systems
Vinod Kulathumani
Dept. of Computer Science and Electrical Engineering
West Virginia University
CS/EE 796 Graduate seminar series
Embedded systems

Found in variety of devices





Aircraft, radar systems, nuclear and chemical plants
Vehicles, TVs, camcorders, elevators
> 90% of CPUs used for embedded devices
Part of a larger system
Application known apriori

Little flexibility in programming
Networked embedded systems


What if embedded processors were connected ?
Not wired but wireless
Enter Wireless Sensor Networks
- Really a network of embedded systems
Enabling technology

Micro-sensors (MEMS, Materials, Circuits)





acceleration, vibration, gyroscope, tilt, motion
magnetic, heat, pressure, temp, light, moisture, humidity, barometric
chemical (CO, CO2, radon), biological, micro-radar
actuators (mirrors, motors, smart surfaces, micro-robots)
Communication

short range, low bit-rate, CMOS radios
The Vision for WSNs



Combine wireless networks with sensing / actuation
 Ubiquitous computing
Fine-grained monitoring and control of environment
Network and interact with billions of embedded computers
Reasons
 Wireless communication - no need for infrastructure setup
 Drop and play
 Nodes are built using off-the-shelf cheap components
 Feasible to deploy nodes densely
log (people per computer)
A new class of computing
Number Crunching
Data Storage
Mainframe
Minicomputer
productivity
interactive
Workstation
PC
Laptop
PDA
year
Slide courtesy: Murat Demirbas
streaming
information
to/from physical
world
Application areas
Science: oceanography, seismology
Engineering: industrial automation, structural monitoring
Daily life: health care, disaster recovery
Emerging applications
 Combination of sensors with mobile devices


Social networking
Participatory urban sensing
 Assisted living – health monitoring
 Vehicular networks with variety of sensors
 Control systems using sensor networks
Trends
 Increasing in scale
Intel Developer Forum
Intel Hillsboro Fab
 Increasing in complexity
ExScal
Middle America Subduction Experiment
Outline of talk

Research challenges / goals

Summary of contributions





Details of a specific contribution


Centralized classification / tracking [SRDS’05, Computer Comm’03]
Distributed vibration control [MSNDC’05]
Sensor network service for object tracking [EWSN’07, IPSN’06]
Distance sensitive snapshot service [OPODIS’07]
Sensor network service for object tracking
Future research interests
My research focus
Interests

Distributed systems / networking



Fault-tolerance
Self-healing systems
Scalability
Sensor networks pose plenty of problems in these areas !
Research challenge
Industrial, medical, military
Observation
based
/ control based
Rising in scale,
complexity
Application
Static
/ mobilecrucial
Performance
Scales: < 100 to 10000
How to design scalable, reliable WSN
applications
Middleware
services
Network abstraction layer
despite unreliable networks ?
Network design
Resource constrained nodes
Network
Unreliable
Low bandwidth, fading, interference
Harsh, malicious environments
Classification and tracking (monitoring)

Scenario –– asset
asset protection
protection
 Scenario

 Dense
Dense
Densedeployment;
deployment;
deployment;Resource
Resource
Resourceand
and
andbandwidth
bandwidth
bandwidthconstrained
constrained
constrained

Goal:
classify
and
observe
tracks
of
objects

 Goal:
Goal:
Goal:classify
classify
classifyand
and
andobserve
observe
observetracks
tracks
tracksofof
ofobjects
objects
objects
 Requirement : low latency (<2 s), high accuracy (> 99%)
 Application design
 Application
Application design
design



 Reliable estimation of influence fields [SRDS ‘05]

 Reliable
Reliable estimation
estimation of
of influence
influence fields
fields [SRDS
[SRDS ‘05]
‘05]
Aggregator
 Influence field (IF) – region over which an object can be detected
Network
design
 Network
IF estimated
usingfor
binary
detections
Network
design

services
separation
 Network
Classification
– Estimating
of IF

abstractions
for IF size
separation
services
for uniformity
 
Tracking
– Estimating
shape
of IFinsensitivity
Distance
insensitivity,
contention
Network
parameters
(density)
 Network abstractions for IF shape
 Routing
uniformity
Deployment
and
testing

parameters
(density)
 Network
Line in the
sand [Computer
Communications’ 03]
Soldier and vehicle influence
 ExScal (RTSS’05)
fields wrt magnetometer
Distributed vibration control

 Scenario


 Control vibrations during payload launch

 Sensors / actuators distributed across surface
 Low computational resource, fault-prone
 Experimental
study on Boeing fairing simulator [MSNDC’05]
Application
design




 Faults
– potentially
Use
on-offimpact
control
scheme severe
 Hard to detect in real time
Model plant as linear system; vibration modes assumed
Requirement – mission critical stability
Model unreliability as Byzantine behavior of actuators
Worst input to plant at all times

Network design

Determine actuator placement for plant to be stable despite
Byzantine actuators [MSNDC’ 05]
Distributed tracking – optimal interception

 Scenario
Scenario






WSN
WSNlaid
laidto
toprotect
protectasset
asset
WSN
laid
to
protect
asset
Evader’s
Pursuersgoal:
queryminimize
sensor network
network
distancefor
for
to mobile
mobile
asset evader
evader locations
locations
Pursuers
query
sensor
Pursuer’s goal: intercept evaders at maximum distance
Pursuers query sensor network for mobile evader locations
 Application design
 Model
Model as
as zero-sum
zero-sum game
game

 Formulation
Formulation of
of optimal
optimal pursuit
pursuit control
control strategies
strategies [IPSN’06]
[IPSN’06]

 Presence of delay
 Under
discrete sampling rate
Network
design
 Network design


Nash
for successful
 Trail
Trail ––equilibrium
distance conditions
sensitive network
network
servicepursuit

aa distance
sensitive
service
information
nearer
objects
required
at faster rate
 
O(d)
find time, of
cost
for object
distance
d away
information
of nearer
objects
with
lower delay
 
O(d*log(d))
update
time,
costMe
forrequired
distance
d moved
Deployed
and tested
in
Catch
If You Can
 Demonstrated
Fault-tolerant, at
energy-efficient,
family
of tunable
protocols

Richmond Field
Station,
Berkeley,
August 05
Distance sensitive snapshots in WSN

Scenario



Application design



Distributed object tracking using WSN
Goal: Pursuers should eventually catch all evaders
Perfect information not necessary
State of evaders distance sensitive in error, latency and rate
 eventual catch
Network design


Network service for distance sensitive snapshots [OPODIS 07]
Exploit alternate forms of compression to gain efficiency



State of nearby nodes is fresher
State of nearby nodes more precise
State of nearby nodes refreshed more often
Systems built

ExScal (Extreme Scaling Experiment)




Goal: classify between person, soldier, SUV and ATV and track
Deployment area: 1,260m x 288m
1000+ sensor nodes, 200+ Stargates
Technology transferred to Northrup Grumman


10,000 node experiment using ExScal software
Roles



Classification / tracking subsystem
Integrating communication chain
Yield studies [ICNP’05]

Identify and study impact of faults
ExScal field
Other systems built

Kansei




Mobile network PeopleNET



WSN testbed at Ohio State
432 TelosB, 150 Stargates, 150 XSM, 100
i-mote2
Software services for data injection, data
collection
Cellphones integrated with psi-mote
Buddy messaging, elevator status
Vehicle classification


Los Alamos National Labs [2007]
Seismic + Acoustic sensors
Trail: network service for tracking
Motivating scenario
 Mobile Objects tracked by network of static sensors over a
large area
 Network runs a tracking service
 Application (residing on mobile objects) issues query of the
form “Find object X” to the tracking service
Motivation for Trail


Queries answered by one (or more) central nodes not scalable

Depletes energy

Increases latency
One way to make queries local


Publish object state everywhere
But upon every move, global update needed

Global update for every object move not scalable

We need to publish object information systematically
Informal problem statement
Requirement 1: Find distance sensitivity
Network tracking service returns query results in time and work
proportional to distance from object
Requirement 2: Update distance sensitivity
When an object moves, tracking protocol updates the track in time
and work proportional to distance moved
Trail tracking structure

Trail protocol based on geometric ideas



Model



Properties proved on continuous 2-d plane
Then implemented on discrete plane
2-d real bounded plane, C denotes center of this plane
Cost measured in Euclidean distance
One track maintained for each object


Let P be object being tracked located at point p
Tracking data structure for P denoted as trailP


Pointers that lead to current location of P
All tracks rooted at C
Trail intuition
 If trailP restricted to be a straight line, each move will involve update
from C
p’
C
p
 Instead, trailP marked with vertices on-the-fly




Vertices serve as anchor points for update
Distance between vertices increases exponentially moving towards C
Anchor updated depending on distance moved
After sufficiently large distance, update from C
Examples of trailP
C
C
C
N3
N3
N3
N2
N2
p c2
c3
c1
p
N3
N2
N2
N1
N1
C
N1
c2
c3
c1
p
c1
p
c1c2
C
N3
N3
N2
N2
N1
N1
c2
c3
C
c3
c2 pc1 c3
N1
c2 p c1 c3
Cost for update and find
N3
Theorem
Cost of updating trailP over a move of
distance d is O(d*log(d))
worst case structure: log spiral
N2
N1
p’
c1
c2 p
c3
Algorithm for find
 Draw successive circles of radii 20, 21, 22 .. 2(log dist(C,q))
 Until trailP is intersected
 Or reach C
C
 Follow trailP to reach current location of P
Theorem
N3
Cost of finding P from object Q at point q is
O(d) where d is dist(p,q)
Cost includes
reaching trailP, following trailP, returning to q
m
N2
q
N1
p
c2
c3
Fault-tolerance and adaptivity of Trail

Fault-tolerance

Nodes may fail after creating trail or old trails may not be deleted

Self-stabilizing actions using heartbeats along trail structure
 Tolerating failures during update and find


As size of holes increases, update and find cost proportionally increase


Route around failures using a method such as left hand rule in GPSR
Trail supports graceful degradation
Adaptivity (Trail yields family of protocols)


Can be tuned based on update and query frequency
When query frequency higher, publish structure increases and find
increasingly straight

Extreme case – find is a straight line to C and publish in circles
Performance evaluation

Experimental evaluation (Kansei testbed at OSU)

Used to demonstrate PE tracking application for NEST DARPA project

Intruder tracks collected from Richmond Field Station [140m X 60m]

Tracks injected into Kansei testbed nodes to emulate motion of
evaders


15 X 7 node network, 3 ft spacing

3 pursuer 3 evader scenario
Study effect of interference on scaling in



Objects [2 - 10]
Query frequency [0.25 – 1 Hz]
Simulations [JProwler]
Garcia Robots as Pursuers

8100 nodes (90 by 90)

Up to 50 objects (uniformly separated and collocated)
Summary of Trail features

Trail – a distance sensitive network service




Assumes no hierarchical partitioning of network
O(d) find time, cost for object distance d away
O(d*log(d)) update time, cost for distance d moved
Fault-tolerant


Self-stabilizing, graceful degradation
When many objects come close together, network interference can
cause delay


Synchronized push version?
Distance sensitive snapshot service
Distance sensitive snapshot service
A brief overview
Informal problem statement
Given
 N nodes, with bounded memory, in f dimensions
 each can sense m-bit information at any time
 each can communicate at W bits per second
Deliver a global snapshot
 at each node (can be relaxed to a subset)
 that uniformly has distance sensitive latency (and distance sensitive
resolution, and distance sensitive rate)




State of nearby nodes is fresher
State of nearby nodes more precise
State of nearby nodes refreshed more often
periodically, as fast as possible (can be relaxed to lower rate)
Illustration
Illustration
Results
Maximum staleness in state of a node i received by a
snapshot at node j is O(log(n) * m * d) where d = dist(i, j)
Resolution of state of a node i in a snapshot received at node
j is Ω(1 / d2) where d = dist(i, j)
Communication cost to deliver a snapshot of one sample
from each node to all nodes is on average O(N * log(n) * m)
Conclusions

Research focus

Reliable network services for WSN applications

Applications for classification, tracking, distributed control

Network services tested in actual field deployments

Key role in integrating complete WSN systems


ExScal, Line in the Sand, Kansei, Catch Me If You Can

Facility monitoring at Los Alamos National Labs
Provided deep insight into real problems in wireless and sensor
networks
Future research interests
WSNs combined with mobility, actuation
Mobile heterogeneous wireless networks


Convergence of mobile devices with sensors

Urban surveillance, online health monitoring, disaster relief, mobile
gaming, vehicular networks

Realization of ubiquitous systems
Research questions

Low power self – localization of mobile units



Scenarios: low cost indoor tracking, security, identity management
Reliable, secure information management

Protect against eavesdropping, jamming

Provide reliable content delivery
Architecture

Composing applications across heterogeneous networks [MODUS 2008]

Convergence / inter-operability with Internet, cellular networks
Wireless sensor networks for control


WSNs suited for control applications

Wireless feature: industrial control and process control applications

Large scale feature: control of distributed parameter systems, power grids
Challenges / research questions


Performance

How to guarantee reliability / low latency and meet wire-line standards?

How to secure the network against jamming?
Architecture


Underlying network independent of control system / application ?
Theory

Joint stabilization of control application and network layer
Cross cutting research
Information processing
Database systems
Data Mining
Network protocols
Network architecture
•Reliable
•Secure
Computer vision
(urban surveillance)
Control systems
Wireless communication
technology
MEMS / sensor
fabrication
Thank you
Contact Information
Vinod Kulathumani
[email protected]
http://www.csee.wvu.edu/~vkkulathumani