Lecture 11

WSNs: Sensor Management

Reading:
Wireless Sensor Networks, in Ad Hoc Wireless Networks: Architectures
and Protocols, Chapter 12, section 12.7.
Sensor Management by M. Perillo and W. Heinzelman. In Wireless
Sensor Networks, Kluwer Academic Publishers, 2004.
2
Sensor Management
What is sensor management and why is it needed?
Sensors often deployed with added redundancy
Fault tolerance
Time-varying application requirements
Time-varying environmental phenomena
Extend network lifetime
Sensor management goal
Select sensor roles to provide application-specific QoS
Sensors
Routers
Turn other sensors off to save energy
Rotate active sensor sets
3
Example Quality Metrics
Coverage
Determines how well network can observe event
Depends on range and location of sensors
Worst-case coverage: areas where coverage is poorest
Can be used to determine where to deploy additional
sensors
Maximal breach path through field
Path intruder can take such that path is maximum
distance from all sensors
Best-case coverage: areas where coverage is best
Maximum support/exposure path
Best-case coverage path
Path that is minimum distance at all points to sensors
4
Example Quality Metrics
Coverage (cont.)
K-coverage
Entire area must be within sensing range of at least K
sensors
Exposure
Ability of sensor network to observe target in field
Based on
Sensing model for particular point in sensing range
Sensor locations
5
Sensor Management (cont.)
Different application types require different sensor
management protocols
Differing QoS requirements
Differing time-varying behavior
Possible to find optimal schedules for sensor roles
Computationally intensive
Requires global knowledge
Not robust to changes in network state/application state
Distributed techniques
Topology control select active routers
Sensor mode selection select active sensors
6
Topology Control
Goal
Ensure enough nodes activated to provide connected network so all
sensors can route data to sink(s)
Reduce energy consumption by allowing non-selected nodes to sleep
Rotate active routers to balance energy
Ensure robustness so one/few sensor losses does not disconnect
network
Example protocols
GAF
Span
ASCENT
STEM
7
Geographic Adaptive Fidelity
(GAF)
Idea: neighboring nodes
equivalent from routing
perspective
Overlay virtual grid on
network
Each node assigned a cell in
grid
Only one node per cell
assigned to be active
Grid size chosen so that any
node in network can reach
node in neighboring grid:
_
5
tx range


8
GAF (cont.)
Different states
Discovery
Active state
Sleep state
Nodes periodically enter discovery state to determine if
they should become active
GAF extends network lifetime proportionally to node
density
9
Span
Goal: create connected backbone of router nodes
Nodes assign themselves coordinators.
Selected set of coordinators chosen so capacity of backbone network
approaches potential capacity of complete network
Nodes rotate coordinator position
Balance energy
Ensure network remains connected and high capacity
Becoming a coordinator
Minimum distance between two of nodes neighbors exceeds three
hops
Backoff delays before coordinator announcement
Node with higher energy and more connectivity more likely to
become coordinators
10
Adaptive Self-Configuring sEnsor
Networks Topologies (ASCENT)
Goal: select active routers to retain connected network while
other nodes sleep
Becoming active based on
Connectivity
Observed data loss rates
Provides ability to trade energy consumption for communication
reliability
States
Test state: route, probe channel, learn loss rates
Active: remain active permanently
Passive: gathers same information as in Test state but does not
route data
Sleep state: turn off radio
Must periodically re-enter passive state from sleep state
11
ASCENT (cont.)
12
Sparse Topology and Energy
Management (STEM)
Previous approaches proactively create connected backbone
Sensor networks may not continuously need active routers
Only require routers when sensors send data
May be infrequent for some sensor network applications
STEM goal: reactively turn on routers only when data to send
Paging channel used to awaken downstream neighbors
STEM-T: use a tone as wake-up message
STEM-B: use a beacon as wake-up message
STEM can be combined with proactive topology control protocols
Only have active routers listen to paging channel
13
Sensor Mode Selection
Goal
Select sensing modes to ensure data provides application-specified
QoS
Reduce energy consumption by allowing non-selected nodes to sleep
Mode selection
Determine which sensors to activate/deactivate
Determine sensing features
Sensing frequency
Data resolution
Influence what traffic generated on network
Greatly reduces energy dissipation
May be necessary to avoid network congestion
14
Sensing Mode Selection (cont.)
Sensing mode selection application-specific
Different application have different QoS requirements
Examples
Coverage-preserving applications: require K-coverage of
some area
Tracking applications: require minimum tracking accuracy
Detection applications: require maximum missed detection
probability and/or false alarm probability
Coverage-preserving applications
Intruder detection
Biological/chemical agent detection
Environmental monitoring
15
Probing Environment and
Adaptive Sleeping (PEAS)
Goal: provide consistent environmental coverage and
robustness to node failures
Nodes send probe messages to neighbors
Neighbors reply after backoff
If no replies node becomes active
If replies node sleeps
Probing range chosen to meet transmission and sensing
coverage
Probing rate adaptive
Tradeoff between energy savings and robustness
Long delay in recovering from node failures if probing
rate long
16
Node Self-Scheduling Scheme
(NSSS)
Goal: select active sensors to
cover full sensing area
Node measures sectors/central
angles covered by neighboring
sensors
If coverage is full 360, node
sleeps
Some redundancy not
accounted for by this model
Backoff and double checks used
to ensure simultaneous
deactivation of nodes does not
leave areas uncovered
17
Gur Game Model
Goal: nodes set sending state so sink receives predetermined number of
packets
Nodes operate as single chain finite state machines
After each round, sink sends information r that tells nodes how to move
in their FSMs
Network settles at desired resolution
Robust to sensor failures or new sensors
18
Reference Time-based Scheduling
Scheme
Goal: maintain coverage at every grid point while minimizing
number of sensors
Nodes broadcast random reference time in [0,T)
T is round length
Broadcast to all sensors in 2x sensing range
For each grid location of a sensor
Sensor sorts reference times of all sensors that can monitor point
Sensor schedules itself to be active halfway between its reference
time and the reference time of sensor immediately preceding it in list
Same for sensor immediately after it in list
Sensor remains active for union of scheduled slots calculated for
each grid point in sensing range
19
Reference Time-based Scheduling
Scheme
20
Coverage Configuration Protocol
(CCP)
Goal: maintain K-coverage of area
Nodes find intersection points between
borders of neighbors sensing radii and
edges of area
Node eligible for deactivation if these
intersection points all K-covered
Ex: S4 deciding whether to activate, K=1
Knows that S1-S3 active
Intersection points 1-5
S1 covers points 1 and 3, S2 covers
points 2 and 4, S3 covers point 5
S4 can deactivate
In second case, point 6 not covered so
S4 must remain active
21
Integration of TC and SM
Why might it be beneficial to integrate topology control
and sensor management?
Selecting sensors selecting routers
Higher performance via integration of role selection
May have more sensors activated as routers than needed if
do not take into account traffic patterns
22
Connected Sensor Cover
Joint sensing mode selection and topology control
Goal: find minimum set of sensors and routers to
efficiently process query over given region
Sensors added in greedy fashion
Sensors calculate added coverage and required routers if
they would be added to set
Set with most coverage and least additional routers
needed added to set
Continues until entire region covered
23
Application-based Routing
Cost
Sensors whose data are important to the application
should not be used as routers
Sensors must determine
application value
E.g., Redundant sensors
less important
How to determine a good
application cost?
Zzz..
Zzz..
Zzz..
Zzz..
Zzz..
Zzz..
Zzz..
Zzz..
24
Application Cost
Each subregion characterized by unique sensor set
Application cost:
app
total
1
Cost (S ) max ( , ) C(S )
E ( , )
i i
x y
x y
=
25
Example Routes
0 5 10 15 20 25 30 35 40 45 50
0
5
10
15
20
25
30
35
40
45
50
Fewest Hops Path
Smallest App. Cost Path
26
Distributed Activation with Pre-
determined Routes (DAPR)
Integrates coverage preservation with route discovery
Pre-calculate shortest cost routes
Activate sensors incrementally until environment is fully
covered
Round
N-1
Route
Disc
Role Discovery
Opt In Opt Out
Normal
Operation
Round
N+1
Round N
27
DAPR Protocol
Base station sends Round Start message
Sensors forward messages, adding routing costs as
Propagate these messages incorporating delays
proportional to cost
r j app t i app j i link
E S C E S C S S C * ) ( * ) ( ) , ( + =
Round
N-1
Route
Disc
Role Discovery
Opt In Opt Out
Normal
Operation
Round
N+1
Round N
28
DAPR Protocol
During Opt In phase, nodes set backoffs proportional to
cumulative path cost
During Opt Out phase, nodes backoff in reverse order and
deactivate if possible
Beacons sent over distance of 2 x sensing range
Round
N-1
Route
Disc
Role Discovery
Opt In Opt Out
Normal
Operation
Round
N+1
Round N
29
DAPR Protocol
1
4
2
3
30
Simulation Scenario
0
2
4
6
8
10
12
L
i
f
e
t
i
m
e

(
h
o
u
r
s
)
Constant Cost
Energy Cost
Application Cost
200 nodes
Most placed in densely
covered regions
Few placed in sparsely
covered region
Application cost: 56%
improvement over energy cost
31
Choosing Protocols
Based on
Application requirements
MAC protocol why?
Bandwidth resources
Availability of network services
Localization
Synchronization
Radio characteristics
Trade-offs
Energy vs. robustness
Localization vs. guaranteed coverage
Delay vs. energy
32
Discussion