Chapter #4.ppt

wsn chapter

1. Chapter #4
Routing Protocols for WSN

2. 2
Outline
Introduction
Flat Routing Protocols
Directed Diffusion
SPIN(Sensor Protocol for Information via Negotiation. )
Hierarchical Routing Protocols
LEACH(Low-energy adaptive clustering hierarchy)
PEGASIS(Power Efficient Gathering in Sensor Information Systems )
TEEN(Threshold-sensitive energy efficient sensor network (TEEN))
Discussion

3. 3
Introduction to WSNs
A sensor network is a computer network of
many, spacially distributed devices using
sensors to monitor conditions at different
locations.
Involve three areas: sensing, communications,
and computation.

4. 4
Introduction to WSNs
Sensor nodes scattered in a sensor field
Each nodes has the capabilities to collect data and route data
back to the sink (Base Station).
Protocols and algorithms with self-organization capabilities.

5. 5
Introduction - WSNs Topology
Issues related to topology maintenance and change in three phases:
Pre-deployment and deployment phase:

Sensor nodes can be either thrown in mass or placed one by one
in the sensor field.
Post-deployment phase:

Topology changes are due to change nodes' position,
reachability, available energy, malfunctioning, and task details.
Re-deployment of additional nodes phase:

Additional sensor nodes can be redeployed at any time to replace
malfunctioning nodes or due to changes in task dynamics.

6. Routing Protocols in WSN
Routing techniques are required for sending data between
sensor nodes and the base stations for communication.
Since sensor nodes have limited power, memory, and
processing capacity, routing in WSN focuses on:
Minimizing energy consumption
Avoiding redundant data
Ensuring reliable communication
Extending network lifetime
6

7. 7
Types of Routing Protocol for WSN
Single-hop Networks
The network consists of n nodes, and
packets are transmitted from sources to
destinations directly.
Multi-hop Networks
The final destination of a packet might not
be reached directly and the other nodes can
be used to route the packet to the final
destination.

8. 8

9. 9
Flat Routing Protocols
Flat Networks
Every incoming packet is sent out on every
outgoing line except the one it arrived on.
Vast numbers of duplicate packets are
generated.
Routing Protocols Used in Flat Networks:
Directed Diffusion, SPIN.

10. 10
The Directed Diffusion
Protocol
Directed Diffusion consists of several
elements:
Interests
Data messages
Gradients
Reinforcements

11. 11
Directed Diffusion - Interest
Propagation
The sink periodically
broadcasts an interest
message to each of its
neighbors.
Every node maintains
an interest cache.
It defines what type of data is required
for example:
“Report temperature readings above 40°C from Region X every 10
seconds.”

12. 12
Directed Diffusion - Gradient Establishment
That every pair of
neighboring nodes
establishes a gradient
toward each other.
This technique can enable
fast recovery from failed
paths or reinforcement of
empirically better paths.

13. 13
Directed Diffusion - Data Propagation
A sensor node that detects a target, it computes
the highest requested event rate among all its
outgoing gradients.
To resend a received data message, a node needs
to examine the matching interest entry's gradient
list.

14. 14
Directed Diffusion - Reinforcement
The node might choose
that neighbor from
whom it first received the
latest event matching the
interest to reinforce.
It is very reactive to
changes in path quality.

15. 15
The SPIN Protocol
Sensor Protocols for Information via Negotiation.
SPIN uses negotiation and resources adaption to address
the deficiencies of flooding.
Negotiation reduces overlap and implosion.
Meta-data is transmitted instead of row data.
SPIN has three types of messages : ADV, REQ and
DATA.
The simple version of SPIN is shown in figure.

16. 16
SPIN
Sensor Protocol for Information via
Negotiation
1 .ADV (Advertisement)
Node A advertises new data to B using
metadata — not the actual data.
Purpose: Inform neighbors about available
data.
2
️. REQ (Request)
Node B checks and, if interested, sends a
REQ to A for the data.
Purpose: Request needed data.
3
️. DATA (Transmission)
Node A sends the actual DATA to B.
Purpose: Deliver the real sensed data.
4
️. B Forwards ADV
Node B advertises the received data to its
neighbors.
Purpose: Continue efficient data
dissemination.

17. 17
SPIN - Flooding deficiencies
Implosion & Overlap
Implosion Problem
Occurs when a node receives duplicate copies of the same data from
multiple neighbors.
Overlap Problem
Occurs when two nodes sense the same event because their sensing
regions overlap, and both send similar data to the sink.
(a)
(a)
(a)
A
B C
D
(a)
(r, s)(q, r)
A B
C
q s
r
Implosion Problem Overlap Problem

18. 18
SPIN-1 - three types of messages
ADV
When a SPIN node has data to share, it can advertise an
ADV message containing meta-data.
REQ
A SPIN node sends an REQ message when it wishes to
receive some actual data.
DATA
DATA messages contain actual sensor data with a meta-
data header.

19. 19
ADVREQ
The SPIN-1 Protocol
Steps
B A
C
D
E
F
DATA
ADV
ADV
ADV
ADVREQ
REQ
DATA
DATA

20. 20
The SPIN-2 Protocol
When energy is plentiful, SPIN-2 nodes
communicate using the same 3-stage protocol as
SPIN-1 nodes.
When a SPIN-2 node observes that its energy is
approaching a low-energy threshold, it adapts by
reducing its participation in the protocol.

21. 21
Hierarchical Routing Protocols
Hierarchical Networks
The main aim of hierarchical routing is to efficiently
maintain the energy consumption of sensor nodes.
Performing data aggregation and fusion in order to
decrease the number of transmitted messages to the
sink.
Routing Protocols: LEACH, PEGASIS, TEEN.

22. 22
The LEACH Protocol
Low-Energy Adaptive Clustering
Hierarchy.
Distributed cluster formation technique
that enables self-organization of large
numbers of nodes.

23. 23
LEACH - Cluster
Algorithms for adapting clusters and rotating cluster
head positions to evenly distribute the energy load
among all the nodes.
The nodes organize themselves into local clusters, with
one node acting as the cluster head.
The cluster head performs signal processing functions
on the data, and transmits data to the remote BS.

24. 24
LEACH - Set-up phase
Cluster Head
Each cluster head node broadcasts an advertisement
message (ADV) let all the other nodes that they have
chosen this role for the current round.
Non-Cluster Head
They transmits a join-request message (Join-REQ)
back to the chosen cluster head.

25. 25
LEACH - Set-up phase
The cluster head node sets up a TDMA schedule
and transmits this schedule to the nodes in the
cluster.
Ensures that there are no collisions among data
messages.
Allows the radio components to be turned off at
all times except during their transmit time.

26. 26
LEACH - Steady-state phase
Broken into frames, where nodes send
their data to the cluster head at most once
per frame during their allocated
transmission slot.
Once the cluster head receives all the
data, it performs data aggregation.

27. 27
LEACH - Time line
Time line showing LEACH operation
NCH
1
NCH
2… … …NCH
m-1
NCH
m
Slot for NCH
2
Frame
ADVJoin-REQSCH
Set-up phase

28. 28
The PEGASIS Protocol
Power-Efficient GAthering in Sensor
Information Systems.
The key idea in PEGASIS is to form a
chain among the sensor nodes so that
each node will receive from and
transmit to a close neighbor.

29. 29
PEGASIS - Chain
The nodes will be organized to form a
chain, which can either be accomplished
by the sensor nodes themselves using a
greedy algorithm starting from some node.
When a node dies, the chain is
reconstructed in the same manner to
bypass the dead node.

30. 30
PEGASIS - Leader
The main idea in PEGASIS is for each node to
receive from and transmit to close neighbors and
take turns being the leader for transmission to the
BS.
Nodes take turns transmitting to the BS, and we
will use node number i mod N (N represents the
number of nodes) to transmit to the BS in round i.

31. 31
PEGASIS - Token
Token passing approach
N0 N1 N2 N3 N4
BS
Token
Data

32. 32
The TEEN Protocol
Threshold sensitive Energy Efficient sensor Network
protocol.
Proactive Protocols (LEACH)
The nodes in this network periodically switch on their sensors
and transmitters, sense the environment and transmit the data of
interest.
Reactive Protocols (TEEN)
The nodes react immediately to sudden and drastic changes in
the value of a sensed attribute.

33. 33
TEEN - Functioning
At every cluster change time, the cluster-head
broadcasts to its members
Hard Threshold (HT)
This is a threshold value for the sensed attribute.
It is the absolute value of the attribute beyond which, the
node sensing this value must switch on its transmitter and
report to its cluster head.
Soft Threshold (ST)
This is a small change in the value of the sensed attribute
which triggers the node to switch on its transmitter and
transmit.

34. 34
TEEN - Hard Threshold
The first time a parameter from the
attribute set reaches its hard threshold
value, the node switches on its transmitter
and sends the sensed data.
The sensed value is stored in an internal
variable in the node, called the sensed
value (SV).

35. 35
TEEN - Soft Threshold
The nodes will next transmit data in the
current cluster period, only when both the
following conditions are true:
The current value of the sensed attribute is
greater than the hard threshold.
The current value of the sensed attribute
differs from SV by an amount equal to or
greater than the soft threshold.

36. 36
TEEN - Drawback
If the thresholds are not reached, the user
will not get any data from the network at all
and will not come to know even if all the
nodes die.
This scheme practical implementation
would have to ensure that there are no
collisions in the cluster.

37. 37
References
I.F. Akyildiz, W. Su*, Y. Sankarasubramaniam, and E. Cayirci,
"Wireless sensor networks: a survey".
K. Akkaya, M. Younis,
"A Survey on Routing Protocols for Wireless Sensor Networks".
J.N. Al-Karaki, A.E. Kamal,
"Routing Techniques in Wireless Sensor Networks".
C. Intanagonwiwat, R. Govindan, and D. Estrin,
"Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks".
W. Heinzelman, J. Kulik, and H. Balakrishnan,
"Adaptive Protocols for Information Dissemination in Wireless Sensor Networks".
W. Heinzelman, A. Chandrakasan, and H. Balakrishnan,
"An Application-Specific Protocol Architecture for Wireless Microsensor Networks".
S. Lindsey and C. Raghavendra,
"PEGASIS: Power-Efficient Gathering in Sensor Information Systems".
A. Manjeshwar and D. Agrawal,
"TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks".