Tutorial: Wireless Sensor Networks

.
 General Overview

 Introduction to Wireless Sensor Networks

 Data Dissemination and Routing Protocols
 Data Gathering
 Medium Access Control Protocols
 Locationing and Coverage
 Testbeds/Applications
 Security in Wireless Sensor Networks
 Summary & Discussion

2
 Motivation
 GOAL: Deeply Networked Systems or Pervasive
Networking
 98% of all processors are not in traditional desktop
computer systems, but in house-hold appliances,
vehicles, and machines on factory floors
 Add reliable wireless communications and sensing
functions to the billions of physically embedded
computing devices to support ubiquitous networked
computing
 Distributed Wireless Sensor Networks is a collection
of embedded sensor devices with networking
capabilities
3
Introduction to WSN

4
 Background , contd.
 Sensors
 Enabled by recent
advances in MEMS
Battery CPU
technology
 Integrated Wireless
Transceiver
Wireless
Transceiver  Limited in
Energy
Memory
Computation
Storage
Transmission range
Sensing Hardware
Bandwidth

5
Background, contd.

6
Sensor Nodes, contd.

7
 Sensors (contd.)
 The overall architecture of a sensor
node consists of:
 The sensor node processing
subsystem running on sensor
node main CPU
 The sensor subsystem and
 The communication subsystem
 The processor and radio board
includes:
 TI MSP430 microcontroller with
10kB RAM
 16-bit RISC with 48K Program
Flash
Crossbow Mote
 IEEE 802.15.4 compliant radio
at 250 Mbps TPR2400CA-TelosB
 1MB external data flash
 Runs TinyOS 1.1.10 or higher
 Two AA batteries or USB
 1.8 mA (active); 5.1uA (sleep)

8
Overall Architecture of a sensor node
Application Layer Sensor

Communication
SubSystem Sensor Node CPU

Network Layer

Slow Serial Link

MAC Layer
Physical Layer Radio Board

Forward Packet Path

Wireless Channel

9
 Wireless Sensor Networks (WSN)
 Distributed collection of networked sensors

10
 Networked vs. individual sensors
 Extended range of sensing:
 Cover a wider area of operation

 Redundancy:
 Multiple nodes close to each other increase fault
tolerance
 Improved accuracy:
 Sensor nodes collaborate and combine their data
to increase the accuracy of sensed data
 Extended functionality:
 Sensor nodes can not only perform sensing
functionality, but also provide forwarding service.
11
 Applications of sensor networks
 Physical security for military operations
 Indoor/Outdoor Environmental monitoring
 Seismic and structural monitoring
 Industrial automation
 Bio-medical applications
 Health and Wellness Monitoring
 Inventory Location Awareness
 Future consumer applications, including smart
homes.

12
 Applications, contd.
cooperative
processing

cooperative
SENSING signalling

THREAT

ALERT

ALERT THREAT
MULTI-HOP
COMMUNICATION
Beam Formation

COMMAND LEVEL

13
Applications, contd.

14
 Characteristics and challenges
 Deeply distributed architecture: localized coordination to
reach entire system goals, no infrastructure with no central
control support
 Autonomous operation: self-organization, self-configuration,
adaptation, exception-free
 TCP/IP is open, widely implemented, supports multiple
physical network, relatively efficient and light weight, but
requires manual intervention to configure and to use.
 Energy conservation: physical, MAC, link, route, application
 Scalability: scale with node density, number and kinds of
networks
 Data centric network: address free route, named data,
reinforcement-based adaptation, in-network data aggregation

15
 Challenges, contd.
 Challenges
 Limited battery power
 Limited storage and computation
 Lower bandwidth and high error rates
 Scalability to 1000s of nodes
 Network Protocol Design Goals
 Operate in self-configured mode (no infrastructure
network support)
 Limit memory footprint of protocols
 Limit computation needs of protocols -> simple,
yet efficient protocols
 Conserve battery power in all ways possible

16
 WSN vs. MANET
 Wireless sensor networks may be considered a
subset of Mobile Ad-hoc NETworks (MANET).
 WSN nodes have less power, computation and
communication compared to MANET nodes.
 MANETs have high degree of mobility, while sensor
networks are mostly stationary.
 Freq. node failures in WSN -> topology changes

 Routing protocols tend to be complex in MANET, but

need to be simple in sensor networks.
 Low-power operation is even more critical in WSN.
 MANET is address centric, WSN is data centric.

17
 Why not port Ad Hoc Protocols?
 Ad Hoc networks require significant amount of
routing data storage and computation
 Sensor nodes are limited in memory and CPU

 Topology changes due to node mobility are

infrequent as in most applications sensor nodes are
stationary
 Topology changes when nodes die in the network
due to energy dissipation
 Scalability with several hundred to a few thousand
nodes not well established
 GOAL: Simple, scalable, energy-efficient protocols

18
 Focus: Radio Transceiver Usage
 The wireless radio transceiver is typically in three modes:
 Transmit – Maximum power consumption

 Receive

 Idle

 Turned off – Least power consumption

 Sensor node exists in three modes: Active, standby, and

battery dead
 Turnaround time: Time to change from one mode to another
(esp. important is time from sleep to wakeup and vice-versa)
 Protocol design attempts to place node in these different
modes depending upon several factors
 Sample power consumption from 2 sensor nodes shown next

19
 Rockwell Node (SA-1100 proc)
MCU Mode Sensor Mode Radio Mode Power(mW)
Active On Tx(36.3mW) 1080.5
Tx(13.8mW) 942.6
Tx(0.30mW) 773.9
Active On Rx 751.6
Active On Idle 727.5
Active On Sleep 416.3
Active On Removed 383.3
Active Removed Removed 360.0
Sleep On Removed 64.0
20
 UCLA Medusa node (ATMEL CPU)
MCU Mode Sensor Radio(mW) Data rate Power(mW)
Active On Tx(0.74,OOK) 2.4Kbps 24.58
Tx(0.74,OOK) 19.2Kbps 25.37
Tx(0.10,OOK) 2.4Kbps 19.24
Tx(0.74,OOK) 19.2Kbps 20.05
Tx(0.74,ASK) 19.2Kbps 27.46
Tx(0.10,ASK) 2.4Kbps 21.26
Active On Rx - 22.20
Active On Idle - 22.06
Active On Off - 9.72
Idle On Off - 5.92
Sleep Off Off - 0.02
21
 Energy conservation
• Low power circuit(CMOS, ASIC) design
Physical layer • Optimum hardware/software function division
• Energy effective waveform/code design
• Adaptive RF power control

MAC sub-layer • Energy effective MAC protocol

• Collision free, reduce retransmission and transceiver on-times
• Intermittent, synchronized operation
• Rendezvous protocols
Link layer • FEC versus ARQ schemes; Link packet length adapt.

Network layer • Multi-hop route determination

• Energy aware route algorithm
• Route cache, directed diffusion
Application layer • Video applications: compression and frame-dropping
• In-network data aggregation and fusion

See Jones, Sivalingam, Agrawal, and Chen survey article in ACM WINET, July 2001;
See Lindsey, Sivalingam, and Raghavendra book chapter in Wiley Handbook of Mobile Computing,
Ivan Stojmenovic, Editor, 2002.

22
Network Architectures

23
 Network Architectures
Layered Clustered
Architecture Architecture
Base
Base Statio
Statio n
n

Layer 1

Layer 2

Layer 3

Larger Nodes denote Cluster Heads

24
 Clustered network architecture
 Sensor nodes autonomously form a group called clusters.
 The clustering process is applied recursively to form a hierarchy of clusters.

Tier 2
Tier 1

Tier 1

Tier 0
Tier 0

25
 Cluster architecture (contd.)
 Example - LEACH protocol
 It uses two-tier hierarchy
Base Station clustering architecture.
 It uses distributed
(( )) algorithm to organize the
Cluster-head
sensor nodes into
(( )) clusters.
(( ) ) (( ))
Cluster-head  The cluster-head nodes
(( ) ) Cluster create TDMA schedules.
(( ) )
Cluster-head
(( ))  Nodes transmit data
(( ) ) (( ) ) during their assigned
Cluster slots.
(( )) Cluster  The energy efficiency of
Sensor the LEACH is mainly due
to data fusion.
26
 Layered Network Architecture
 A few hundred sensor nodes
(half/full duplex)
 A single powerful base-station
 Network nodes are organized
into concentric Layers
 Layer: Set of nodes that have
the same hop-count to the
base-station
 Additional Mobile Nodes
traversing the network
 Wireless Multi-Hop
Infrastructure Network
Architecture (MINA)
A 10 node sensor network depicting cluster of node 3;
there are 2 mobile nodes

27
 MINA, contd.

 Set of wireless sensor nodes create an

infrastructure – provide sensing and data
forwarding functionality
 Mobile soldiers with hand-held units access the
sensors for data and also to communicate with a
remote BS
 BS is data gathering, processing entity and
communication link to larger network
 Shorter-range, low-power transmissions preferred
for covert operations and to conserve power

28
Data Dissemination Architectures
and Protocols

29
 Data Dissemination
 In ad hoc networks, traffic is peer-to-peer
 Multi-hop routing is used to communicate data
 In WSN, other traffic models are possible:
 Data Collection Model
 Data Diffusion Model
 Data Collection Model: Source sends data to a collection
entity (e.g. gateway): periodically or on-demand
 Data Diffusion Model:
 Source: A sensor node that generates data, based on its
sensing mechanisms’ observations
 Event: Something that needs to be reported, e.g. in target
detection; some abnormal activity
 Sink: A node, randomly located in the field, that is
interested in events and seeks such information

30
 Data Diffusion: Concept
Sink 1

Sources

Sink 2

32
 Diffusion: Basics
 Data-centric vs. address centric architecture
 Individual network address is not critical; Data is important
and is accessed as needed
 User can pose a specific task, that could be executed by
sensor nodes
 Concept of Named Data: (Attribute, Value) Pair
 Sink node requests data by sending “interests” for data
 Interests are propagated through the network, setting up
gradients in the network, designed to “draw” data
 Data matching the interest is then transmitted towards the
sink, over multiple paths (obtained by the gradients
 The sink can then reinforce some of these paths to optimize

33
 Diffusion Basics, contd.
 Design Issues:
 How does a sink express its interest in one or
more events?
 How do sensor nodes keep track of existing
interests from multiple sinks?
 When an event occurs, how does data get
propagated from source(s) to sink(s)?
 Can in-network data processing (e.g. data fusion),
data aggregation and data caching help improve
performance?
 [Intanagonwiwat et. al.; ACM MobiCom 2000]

34
 Diffusion Basics, contd
 Example Task
{Type = Animal; Interval = 20ms; Time = 10s;
Region = [-100, 100, 200, 400] }
 The above task instructs a sensor node in the
specified region to track for animals; If animal is
tracked/detected, then send observations every 20
ms for 10s
 The above task is sent via interest messages and all
sensor nodes register this task.
 When a node detects an event, it then constructs a
Data Event message

35
 Diffusion: Basics, contd
 Data Event Example:
{Type = Animal; Instance = Tiger;
Location = [101, 201]; Intensity = 0.4;
Confidence = 0.8; Timestamp = 2:51:00}
Interests and Gradients:
 For each active task that a sink is interested in:
 Sink broadcasts interest to its neighbors
Initially, to explore, it could set large interval (e.g 1s)
 Sinkrefreshes each interest, using timestamps
 Each sensor node maintains an interest cache
 Interest aggregation is possible
36
 Diffusion: Interests
 When a node receives an interest, it:
 Checks cache to see if an entry is present.

 If no entry, creates an entry with a single gradient

to neighbor who sent this interest
 Gradient specifies the direction and data rate.

 Resend interest to a subset of its neighbors

 This is essentially flooding-based approach

 Other probabilistic, location-based and other

intelligent forwarding approaches possible
 Similar to multicast tree formation, at sink instead of
at source
37
 Diffusion: Interest Propagation
Sink 1

Sources

Sink 2

38
 Diffusion: Data Propagation
 When a sensor node detects a target, it:
 Searches interest cache for matching entry

 If found, computes highest requested event rate

among its gradients
 Instructs sensor sub-system to generate data at
this rate
 Sends data to neighbors on its gradient list

 Intermediate nodes maintain a data cache

 Caches recently received events

 Forwards event data to neighbors on its gradient

list, at original rate or reduced rate (intelligently)
39
 Diffusion: Reinforcement
 When sink gets an event notification, it:
 Picks a suitable set of neighbor(s) (best link, low
delay, etc.) and sends a refresh interest message,
with higher notification rate (e.g. every 10 ms
instead of every 1s)
This will prune some of its neighbors (since interests in
a node’s cache will expire)
 Each selected neighbor forwards this new interest
to a subset of its neighbors; selecting a smaller
set of paths
 Negative reinforcement also necessary to de-select
weaker paths if a better path found.
40
Part III: Data Gathering
Algorithms

41
 Problem Definition
 Objective: Transmit sensed data from each sensor node to a base station
 One round = BS collecting data from all nodes

 Goal is to maximize the number of rounds of communication before nodes

die and network is inoperable
 Minimize energy AND reduce delay
 Conflicting requirements

Sensor Nodes

Base station

42
 Energy*Delay metric
 Why energy * delay metric?
 Find optimal balance to gather data quickly but in
an energy efficient manner
 Energy = Energy consumed per round

 Delay = Delay per round (I.e. for all nodes to send

packet to BS)
 Why is this metric important?
 Time critical applications

43
 Direct Transmission
 Direct Transmission
 All nodes transmit to the base station (BS)
 Very expensive since BS may be located very far
away and nodes need more energy to transmit
over longer distances
Farther the distance, greater the propagation losses,
and hence higher the transmission power
 All nodes must take turns transmitting to the BS
so delay is high (N units for a N-node network)
 Better scheme is to have fewer nodes transmit
this far distance to lower energy costs and more
simultaneous transmissions to lower delay

44
 LEACH
 Low Energy Adaptive Clustering Hierarchy
 Two-level hierarchy
Base
Station

Larger Nodes denote Cluster Heads

45
 Scheme #1: PEGASIS
 Goalsof PEGASIS (Power-Efficient GAthering for
Sensor Information Systems)
 Minimize distance nodes must transmit

 Minimize number of leaders that transmit to BS

 Minimize broadcasting overhead

 Minimize number or messages leader needs to

receive
 Distribute work more equally among all nodes

46
 PEGASIS
 Greedy Chain Algorithm
 Start with node furthest away from BS

 Add to chain closest neighbor to this node that

has not been visited
 Repeat until all nodes have been added to chain

 Constructed before 1st round of communication

and then reconstructed when nodes di
 Data fusion at each node (except end nodes)
 Only one message is passed at every node

 Delay calculation: N units for an N-node network

 Sequential transmission is assumed

47
 PEGASIS

End

Start

48
 Scheme #2: Binary Scheme
 Chain-based as described in PEGASIS
 At each level node only transmits to another node
 All nodes receiving at any level rise to the next level
 Delay: O(log2 N)

Step 4: c3  BS
Step 3: c3 c7
Step 2: c1 c3 c5 c7
Step 1: c0c1 c2c3 c4c5 c6c7

50
 Scheme # 3:Chain-based 3 level
 For non-CDMA sensor nodes, binary scheme is not
logical
 Construct chain as described in PEGASIS
 Divide chain into 10 groups (for the 100-node)
 To space out simultaneous transmissions to
minimize interference
 In each group, nodes will transmit one at a time
 Finally, one node out of each group at each level will
contain all the data and will rise to the next level until
finally the leader will transmit to the BS
 Total delay = 15 units (9+4+1+1) for 100-nodes

51
 Chain-based 3 level scheme
 ThirdLevel
 Two nodes rise to top and non-leader transmits to
leader
 Leader transmits to BS

c18  BS
c18c68
c8 c18c28c38c48 c58 c68 c78 c88c98
c0c1c2…c7c8c9 c10c11…c18c19 …c90 c91…c98 c99

52
MAC Protocols for WSN

53
 MAC Protocols
 What is fundamentally different for MAC Protocol
design in WSN?
 Low-power operation is even more critical
 Reduced coordination and synchronization is
beneficial
 Resilience to frequent node failures
 Suitably blend with the network architecture
Probably application dependent
 Scalability to support large number of nodes
Thousands of nodes likely
Limited bandwidth availability
Would the 802.11 family of protocols work?

54
 TDM-Based MAC
 Considered for Clustered architecture
 Nodes are organized into clusters

 Each cluster has a clusterhead, that

communicates directly with gateway or BS node
 TDMA MAC
 The cluster head knows its members’ IDs

 Creates a simple TDM schedule, allocating time

slots to members
 Broadcasts schedule to members

 Schedule may be periodically updated

 Rotating cluster heads possible

55
 TDM-Based MAC, contd.
 Advantages:
 Simple to coordinate within cluster
 No collisions
 Can be more energy-efficient: members wake up
only when they have to send/receive data
 Disadvantages:
 Adjoining clusters need to coordinate to operate
in different channels (or frequencies)
 TDM is not very scalable to large number of
nodes: high delays possible
 Nodes need to be synchronized within each
cluster
56
 S-MAC [Ye et. Al. 2002]
 Sensor-MAC Protocol proposed in 2002
 Assumptions
 Network consists of several small nodes,
deployed in an ad hoc manner
 Nodes dedicated to a single or few collaborative
applications: Per-node fairness is not critical
 In-network processing assumed: e.g. data fusion,
data aggregation, collab signal processing
 Long idle periods and occasional burst of data:
higher latency may be tolerated

57
S-MAC details, contd.
 Periodic Listen and Sleep
Mode of operation
 Each node sleeps for a
while; wakes up and
then communicates with
its neighbors, as
necessary.
 Periodic synch among
neighbors to reduce drift
 Pair-wise or group-wise
node synch
 Nodes exchange
schedule by broadcast
 MAC is still needed to
avoid collisions
58
Localization (Location Discovery)
Algorithms

59
 Location Information
 Itis essential, in some applications, for each node to
know its location
 Sensed data coupled with loc. data and sent

 We need a cheap, low-power, low-weight, low form-

factor, and reasonably accurate mechanism
 Global Positioning Sys (GPS) is not always feasible
 GPS cannot work indoors, in dense foliage, etc.

 GPS power consumption is very high

 Size of GPS receiver and antenna will increase

node form factor

60
 Indoor Localization
 Use a fixed infrastructure
 Beacon nodes are strategically placed
 Nodes receive beacon signals and measure:
 Signal Strength
 Signal Pattern
 Time of arrival; Time difference of arrival
 Angle of arrival
 Nodes use measurements from multiple beacons
and use different multi-lateration techniques to
estimate locations
 Accuracy of estimate depends on correlation
between measured entity and distance
61
 Indoor Localization
 Examples of Indoor Loc. Systems
 RADAR (MSR), Cricket (MIT), BAT (AT&T), etc.

 Some approaches require a priori signal

measurement and characterization and database
creation
 Node obtains distance estimate by using
database
 Not always practical to have database loaded in
the individual node; only some nodes (e.g.
gateway) might carry it.

62
 Sensor Net. Localization
 No fixed infrastructure available
 Prior measurements are not always possible
 Basic idea:
 Have a few sensor nodes who have known
location information
 These nodes sent periodic beacon signals

 Other nodes use beacon measurements and

triangulation, multi-lateration, etc. to estimate
distance
 Following mechanisms presented in Savvides et. al.
in ACM MobiCom 2001
63
 Sensor Net. Localization, contd.
 Receiver Signal Strength Indicator (RSSI) was used to
determine correlation to distance
 Suitable for RF signals only

 Very sensitive to obstacles, multi-path fading, environment

factors (rain, etc.)
 Was not found to have good experimental correlation

 RF signal had good range, few 10metres

 RF and Ultrasound signals

 The beacon node transmits an RF and an ultrasound
signal to receiver
 The time difference of arrival between 2 signals is used to
measure distance
 Range of up to 3 m, with 2cm accuracy

64
 Localization algorithms
 Based on the time diff. of arrival
 Atomic Multi-lateration:
 If a node receives 3 becaons, it can determine its
location (similar to GPS)
 Iterative ML:
 Some nodes not in direct range of beacons
 Once an unknown node estimates its location, will
send out a beacon
 Multi-hop approach; Errors propagated
 Collaborative ML:
 When 2+ nodes cannot receive 3 beacons (but
can receive say 2), they collaborate
65
 Multi-lateration examples
Beacon Nodes

Unknown Nodes

Beacon Nodes

Unknown Nodes

66
Exposure; Coverage and
Deployment

67
 Coverage Problems
 Coverage: is a measure of the Quality of service of
a sensor network
 How well can the network observe (or cover) a given
event?
 For example, intruder detection; animal or fire
detection
 Coverage depends upon:
 Range and sensitivity of sensing nodes

 Location and density of sensing nodes in given

region

68
 Coverage, contd.
 Worst-Case Coverage: Areas of breach (lowest
coverage)
 Can be used to determine if additional sensors
needed
 Best-Case Coverage: Areas of best coverage
 Can be used by a friendly user to navigate in
those areas

69
 Coverage, contd.
 Given: A field A with sensors S, where for each sensor $s_i
\in S$, its location (x_i, y_i) is known (How? Based on the
Localization Techniques described earlier). Areas I and F are
initial and final locations of an agent traversing the field.
 Problem: Identify P_B, the maximal breach path in S,
starting in I and ending in F
 P_B is defined as the locus of points p in the region,
where p is in P_B if the distance from p to the closest
sensor is maximized.
 I and F are arbitrarily specified inputs.

 Solution: Determine the Voronoi diagram corresponding to

the sensor graph. The path P_B will be composed of line
segments that belong to the Voronoi diagram.

70
 Voronoi diagrams
 In 2D, the Voronoi diagram
of a set of points partitions
the plane into a set of
convex polygons such that:
 All points inside a
polygon are closest to
only one site.
 The polygons have
edges equidistant from
nearby points.
 Related is Delaunay
Triangulation
 Connect points in V-
Diag. whose polygons
share a common edge.

71
 Worst-Case Coverage: Alg.
1. Generate the bounded Voronoi diagram
a. Let U and L denote vertex set and links of diag.

2. Create a graph with vertices from set U and links

from L
a. Weight of link in graph = minimum distance from
all sensors in S
3. Do a breadth-first search to determine a path from I
to F in the graph, such that the path has maximum
edge cost
4. Multiple such breach paths are possible.

72
 Best-Case Coverage
 Problem: Identify P_S, the path with maximum
support in S, starting at I and ending in F.
 Solution: Use Delaunay triangulation
 The best path will be one connecting some of the
sensor nodes
 Similar approach to Max. Breach Path
 Use Delaunay instead of Voronoi

 The edge cost in the graph G, will be the length of

the Delaunay triangle line segment.

73
 Examples

 Fig. on left shows the bounded Voronoi diagram and the

maximal breach path
 Fig. on right shows the Delaunay Triangulation and the
maximal support path
 Question: Once these are determined, how to use these?

74
 Exposure Problems
 Exposure is related to the coverage
 Exposure may be defined as the expected ability of
observing a target in the sensor field
 Formally defined as the integral of the sensing
function (depends on distance from sensors) on a
path from P_s to P_d
 Sensing function depends on nature of sensors
 Sensor model:

S ( s, p ) 
[d ( s, p)]k
 , k are constants; and d ( s, p) is distance of point p from
sending node s

75
 Exposure at a point
 All-SensorField Intensity at Point p in field with n
sensors denoted by {s1 , s2 ,..., sn }
n
I A ( F , p)   S ( si , p)
i 1

 Closest-Sensor Field Intensity at Point p:

S min  sm  S | d ( sm , p)  d ( si , p)si  S
I C ( F , p)  S ( S min , p)

76
 Exposure along a path
 Suppose object O is traveling from point p(t1) to
p(t2) along path p(t).
 Exposure for object O during interval t1 to t2 along
p(t) is defined as:
t2
dp(t )
E[ p(t ), t1 , t 2 ]   I ( A or C ) ( F , p(t )) dt
t1
dt
dp(t )
is the element of arc length
dt
If p(t)  (x(t), y(t)) then
2
 dx(t )    dy (t )  
2
dp (t )
       
dt  dt    dt  
77
 Exposure: Properties
 Consider only 1 sensor at location (0,0). Let
1
S [ s (0,0), p ( x, y )]  1
d ( s, p) 
x2  y2

 Determine the path from a=(1,0) to point b=(X,Y)

with minimum exposure
 Determine x(t), y(t) such that x(0) = 1; y(0) = 0;
x(1) = X; y(1) = Y and the exposure function is
minimized.
 Lemma 1: If b=(0,1), then the minimum exposure
path is  cos  t , sin  t  and E  
 
 2 2  2

78
 Exposure: Properties
 Lemma 2: Given a sensor s and two points a and b, such
d(s,a)=d(s,b), then the minimum exposure path between a
and b is that part of the circle centered as s and passing
through a and b.
 Theorem: Let the sensor be located at (0,0) in a unit field.
The minimum exposure path from (1,-1) to (-1,1) is as below:

S=(0,0)

79
 Exposure: Properties
 Let s be a sensor in a polygonal field with vertices
v1,…,vn.
 For the inscribed circle of the polygon, let edge
v_i,v_{i+1} be tangent at point u_i
 The minimum exposure path from vertex v_i to
vertex v_j consists of:
 Line segment from v_i to u_i
 Part of inscribed circle from u_i to u_j
 Line segment from u_j to v_j
 (OR) in the opposite direction (from v_i to u_j etc)
 Problem of MEP between 2 points in same corner or
between 2 points inside the inscribed circle is open
80
 Generic Exposure Problem
 Given a network with randomly placed sensor
nodes, how to determine minimum exp. Path
 Solution:
 Tessellate the network into a set of equidistant
grid points (with varying degree of precision)
 For each edge in the grid network, assign an
edge equal to the exposure along the edge
(integrated from the sensor function)
 Using Dijkstra’s algorithm, determine the shortest
path from a source (based on edge weights)
 This is the min. exposure path

81
 Security in Sensor Networks
 What is different ?
 Unfriendly, unattended environments
 Severe resource constraints render most of the
cryptographic mechanisms impossible
 PKI is infeasible for sensor networks and have to
rely on symmetric key cryptography
 Security has never been more important!
 Applications in battlefield management,
emergency response systems and so on
 Key management is the most critical issue
 Focus of majority of the research
 Following is review of some key research in the area

83
 SPINS-Perrig et al, Berkeley
 Complete suite of security protocols for sensor
networks
 SNEP (Secure Network Encryption Protocol)
 Data Confidentiality

 Authentication

 Integrity

 Freshness

 μTESLA
 Lightweight version of TESLA for authenticated
broadcast

84
 SPINS: Applications
 Authenticated Routing
 Base station can be authenticated using μTESLA

 For each time interval, the first packet heard is

chosen as parent, which is authenticated later
 Prevents spurious routing

 Node-to-Node Key Agreement

 A sends B a request with a nonce

 B asks BS for a session key using SNEP

 BS distributes shared session keys securely to A

and B using SNEP with strong freshness

85
 Key Management Scheme for DSN
 Eschenauer et al, UMD (CCS 2002)
 Based on probabilistic key sharing
 Each node is equipped before deployment with a
key-ring chosen randomly from a common key pool
 Each key has an identifier associated with it
 Shared secret key is established between two nodes
by one of the two ways:
 Broadcasting the key identifiers and comparing
them to find a common key if one exists
 Sending a challenge encrypted in a key; a valid
response is a successful decryption of the
challenge establishing a shared key

86
 Key Mgmt Contd
 There may not be a shared key between a pair of
nodes
 In such a case a path to one node from the other
is established through the secure links already in
place
 A direct secure link is then established

 If a node is compromised, its entire key-ring is

revoked from the network
 In general for a required probability of 0.5, 75 keys
need to be in the key ring chosen from a pool of
10,000 keys.

87
 Random Key Predistribution Schemes
 Chan, Perrig et al, CMU, 2003
 Proposes three random key predistribution schemes
 q-Composite random key predistribution
 Multi-path key reinforcement
 Random pair-wise scheme
 q-Composite random key predistribution
 Builds on the work of Eschenauer and Gligor (referred to
as basic scheme)
 Basic idea is to share q keys between nodes rather than
just one key
 Final key is the hash of all q keys
 An attacker now needs to capture more nodes in order to
eavesdrop on any link with given probability

88
 q-Composite Predistribution Contd.
 However choosing size |S| of common key pool is
tricky
 Too large May not find q common keys
between every pair of node
 Too small Attacker can get a large sample of
S by capturing just a few nodes
 Choose largest |S| such that Pconnect ≥ P
 Pconnect is the probability of two nodes sharing
sufficient keys to form a secure link (derived
mathematically)
 P is the desired probability that two nodes form a
secure link

89
 q-Composite Predistribution Contd.
 q-Composite scheme thus makes small scale
attacks less appealing for an attacker
 Attacker can only gain a little additional
information by capturing a few nodes
 e.g. amount of additional communication
compromised when 50 nodes are captured is only
4.74% as compared to 9.52% for basic scheme
 However makes network more vulnerable if large
number of nodes are captured

90
 Multi-path Key Reinforcement
 Need to update the key once a secure link has been
formed between two nodes
 To prevent attacker from obtaining and using the
old key by capturing other nodes
 Node A sends j random values over multiple disjoint
secure paths to node B
 The new key is computed from all the j values
 Attacker has to eavesdrop on j paths in order to
construct the key
 The neighbors on those paths are called reinforcing
neighbors

91
 Multi-path Key Reinforcement Contd
 Significantnetwork overheads (~10X)
 The method is not as effective when used with q-
Composite
 Both the methods essentially do the same thing
 But their weakness compound each other
 Small key pool and high network overheads

 Works well in conjunction with the basic scheme

 Reduces the eavesdropping probability 146 times!

92
 Random pair-wise Key Scheme
 Targeted at Node-to-Node authentication without
any help from the base station
 Each node need only save a random set of n*p keys
instead of all n-1 keys
 p is the smallest probability that any two nodes
have a shared key such that all nodes have
shared keys with some high probability
 Nodes are predeployed with m random pair-wise
keys for m other nodes
 Node broadcasts its identifier once deployed
 Mutual key agreement with the neighbors takes
place by cryptographic handshake

93
 Random pair-wise Key Scheme Contd
 Multi-hop range extension is simple with having
neighbors rebroadcast the identifiers further
 Must be used to a limited number of hops to
prevent DoS attack by an adversary
 Distributed node revocation is possible by having
nodes broadcast public votes against a misbehaving
node
 Mechanism for detecting misbehavior assumed at
each node
 If A receives more than a threshold number of votes
are against B, it cuts off all communication with B
 Many practical issues arise!

94
 Random pair-wise Key Scheme Contd
 Node replication can be resisted by limiting the max
degree of each node
 Degree counting is modeled in a similar way as
vote counting for node revocation
 Complete resilience against node capture
 A compromised node does not provide any further
information
 Large network size supported
 n = m/p where m is the key-ring size of a node
and p is the smallest probability that any two
nodes have a shared key such that all nodes
have shared keys with some high probability

95
Testbeds and Applications

96
 Habitat Monitoring
 Traditional human monitoring methods for habitats
are invasive and cause negative impact
 Often, repeated visits necessary to collect data

 Ideal will be to establish a group of wireless sensor

networks that sense and wirelessly transmit data
 Better for environment; Cheaper, Safer, etc.

 Great Duck Island (GDI) Project by College of

Atlantic; Intel and UC Berkeley
 Monitor usage patterns of nesting burrows

 Changes in burrow conditions during breeding

season
97
 GDI Project
 Establishes multiple clusters of sensor networks
 Each cluster or “patch” has a gateway node
 Data from clusters forwarded over a wireless LAN
(802.11b) connection to a basestation (part of the
island’s field station)
 The base station provides necessary connectivity to
Internet
 Sensors sense light, temp, pressure, infra-red,
relative humidity in the burrows
 Sensor data is archived & queried in real-time
 Users with mobile devices and remote clients
access data

98
 GDI Project, contd.
 The sensor nodes are Berkeley Motes (40 Kbps radio, 4 MHz
ATMEL chips, 512KB storage)
 Motes encased in transparent acryclic enclosure
 As of July 2002, 32 motes (nine in underground burrows)
 Data collection and evaluation in progress

99