Transcript sensor data

Routing Techniques in Wireless Sensor
Networks
Professor Choong Seon Hong
Kyung Hee University
[email protected]
Fall 2006
Introduction
 Routing
 Process of delivering a message across one or more
networks via the most appropriate path
 WSNs routing is different from traditional IP routing
 One of the main goals of WSNs is to prolonged the lifetime
of the network
 Maintain connectivity by employing energy management
techniques as energy sources in WSNs are limited and
irreplaceable
 Extensive collaboration between sensor nodes is required to
perform high quality sensing and to behave as fault tolerant
systems
 Sensor network can be categorized as time-driven or eventdriven. So, routing techniques must be adaptive to
applications
Fall 2006
2
Design Issues
 Routing protocols should be designed with the
following principles
 Sensor nodes should be self-organizing. Also the operation
of the sensor networks is unattended, so the organization
and configuration should be performed automatically
 Most application sensor nodes are stationary. However, in
some applications nodes may allowed to change their
location
 Sensor networks are application specific. For example the
challenging problem of low-latency precision tactical
surveillance is different from that required for a periodic
weather-monitoring task
 Data collected by many sensors in WSNs are based on
common phenomena. So, there is high probability that these
data have some redundancy. So efficient routing technique
should perform an in-network processing
Fall 2006
3
Design Issues (Cont’d)
Sensor networks are data-centric. Once an
event of interest is detected, data can be sent
to sink. So, periodic sleep can be exercised to
conserve more energy
Exercising periodic sleep requires appropriate
duty cycle calculation and synchronization
 Data aggregation is useful only when it does
not hinder the collaborative effort of the sensor
nodes
An ideal sensor network has attribute –based
addressing and location awareness
Fall 2006
4
Design Issues (Cont’d)
 As sensor network is highly dense. For a certain
period of time optimal number of sensor will be
responsible of sensing and disseminating data
 Dynamic routing capability based on power
availability, position and reachability
 As sensor networks works under broadcast
mechanism, probabilistic or location aware
flooding technique should be used rather than
simple flooding.
Fall 2006
5
Routing Challenges
 Ad hoc deployment
 Adaptive to topology changes
 Computation capabilities
 Light-weight and simple
 Communication range
 Short range
 Multihop routing
 Fault Tolerance
 Physical damage
 Lack of power
 Scalability
 High density deployment
 Routing should be scalable according to network size,
topology and density
Fall 2006
6
Routing Challenges (Cont’d)
 Hardware constraints
 Small in size
 Extremely low power
 Transmission media
 Contention based protocols (e.g. CSMA) do not suite
 Connectivity
 Nodes are expected to be highly connected
 Control overhead
 Control packet overhead increase linearly with density
 Tread off between energy conservation, route setup cost,
routing performance matrices (e.g. latency, hop count)
 Quality of service
 In some applications, data should be delivered within a
certain period of time from the moment they are sensed
Fall 2006
7
Taxonomy of Current Proposed Routing Protocols
Routing protocols in WSN
Network Structure
Flat
network
routing
Hierarchical
network
routing
Location
based
routing
SPIN,
Directed
Diffusion,
Rumor,
MCFA,
GBR
LEACH,
PEGASIS,
TEEN,
APTEEN,
MECN
GAF,
GEAR,
SPAN
Protocol operation
Negotiation
based
routing
Multipath
based
routing
SPIN
Maximum
Lifetime
Routing
Query
based
routing
Directed
Diffusion
QoS
based
routing
Coherent
based
routing
Sequential
Sequential
Assignment
Assignment
Routing
Routing
(SAR)
Fall 2006
8
Flat Vs Hierarchical Routing
 Hierarchical Routing:
 Reservation based Scheduling
 Collision avoided
 Reduced duty cycle due to
periodic sleeping
 Simple but non-optimal Routing
 Requires local and global
Synchronization
 Overhead of cluster formation
throughout the network
 Lower latency because multiple
hops networks formed by
cluster head always available
 Energy dissipation is uniform
 Energy dissipation can be
controlled
 Fair Channel allocation
 Flat Routing:
 Contention based scheduling
 Collision overhead present
 Variable duty cycle by
controlling sleep time of nodes
 Node on multihop path
aggregates incoming data from
neighbors
 Routing is complex but optimal
 Links formed on the fly without
synchronization
 Routes formed only in regions
with data for transmission
 Latency in waking up
intermediate nodes and setting
up multipath
 Energy dissipation depends on
traffic pattern
 Energy dissipation adapts to
traffic patterns
 Fairness not guaranteed
Fall 2006
9
Why Hierarchical and Data-Centric Routing is Better

In sensor networks, hierarchical control structures contribute
to improved efficiency of resource use by creating contexts for:





Managing the whole network with near optimal number of nodes
for energy conservation
Managing wireless communications among multiple nodes to
reduce channel contention
Forming routing backbones to reduce network diameter
Periodic sleep and awake technique can be exercised to
conserve energy
Data-centric routing can make efficient use of resources in the
following way



To combine data from different sensors to eliminate redundant
transmission
From multiple sources to a destination data-centric approach
allows in-network consolidation of data
Most of the sensor network application data is requested based
on certain attribute, so data-centric routing is suitable for sensor
network
Fall 2006
10
Desired Characteristics of Hierarchical Routing

Constructing clustering algorithm should have the
following properties:





The algorithm must choose the best nodes as
clusterheads and gateways considering energy and
topological position in the network
Number of cluster head should be kept as minimum as
possible without destroying the reliability of the network
operation
Distributed hierarchical control structure (it means cluster
head and gateway must be well distributed in the network)
Cluster setup overhead should be kept as low as possible
The algorithm must execute based on local coordination
and should not depend on global topology information as
localized protocols are rewarded with good performance in
terms of energy consumption and backbone size
Fall 2006
11
Flat and Query Based Routing Protocols
Joanna Kulik, Wendi Rabiner Heinzelman, and Hari Balakrishnan:
SPIN: Sensor Protocol for Information via Negotiation,
Selected Papers from Mobicom'99 Volume 8 , Issue
2/3 (March-May 2002) Pages: 169 – 185
Fall 2006
12
What do we expect in a WSN?
Internet and
Satellite
Sink
D
E
User
C
A
B
Task manager node
Sensor field
Sensor nodes
Problem: Information dissemination
 Can monitor and control the physical environment from remote
locations (sink nodes)
 Improve sensing accuracy by distributed processing
 Can aggregate sensor data to provide multi-dimensional view
 Focus on critical events (e.g. intruder entering)
 Function accurately when individual sensors fail
Fall 2006
13
Challenges !
 Energy-limited nodes
 Sense data
 Transmit data
 Route data
 Computation
 Signal processing Algorithms
 Sophisticated network protocols
 Communication
 Bandwidth-limited
 Energy-intensive
Goal: Minimize energy dissipation
Fall 2006
14
What sparked off SPIN?
 Study of the conventional protocols led to SPIN’s
development –protocol characterized as “classic
flooding”
A
C
B
D
E
F
 Flooding
G
 Send data to all neighbors
Fall 2006
15
Classic Flooding Limitations
 Implosion
(a)
A
B
(a)
(a)
C
D
(a)
 Data overlap
q
r
A
(q,r)
s
B
C
(r,s)
 Resource blindness
Nodes do not modify their activities
based on the energy available to them
Fall 2006
16
Other Data Dissemination Algorithms
 Classic Flooding
A
C
B
A
D
E
C
B
D
 Gossiping
 Forward data to a random neighbor
 Avoids implosion (but no for overlap)
F
G
 Ideal Dissemination
 Shortest-path routes
 Avoids overlap
 Minimum energy
Fall 2006
17
SPIN Family
Sensor Protocol for Information via Negotiation
 Negotiation
Using “meta-data” – only useful information is
sent -> take care of implosion and overlap
 Resource-adaptation
Check the energy level before plunging into data
transmissions
Cut down activity to save energy
Fall 2006
18
Meta-Data
 Exchanging sensor data may be expensive, but
exchanging data about sensor may not be.
 Sensors use meta-data to describe the sensor data
briefly
 If x is the meta-data descriptor for data X
sizeof (x) < sizeof (X)
 If x==y
sensor-data-of (x) = sensor-data-of (y)
 If X==Y
meta-data-of (X) = meta-data-of (Y)
 Meta-data format is application specific
Fall 2006
19
SPIN Messages
 ADV- advertise data
 REQ- request specific data
 DATA- requested data
ADV
A
B
REQ
A
B
DATA
A
B
• ADV and REQ messages contain only
meta-data so they are smaller in size.
Fall 2006
20
SPIN Protocols
 SPIN on Point-to-Point Networks
SPIN-PP (Point-to-Point)
SPIN-EC (Energy Conserving)
 SPIN on Broadcast Networks
SPIN-BC (BroadCast)
SPIN-RL (ReLiable)
Fall 2006
21
SPIN on Point-to-Point Networks
 Linear cost with number of neighbors
 SPIN-PP
3-stage handshake protocol (ADV-REQ-DATA)
Advantages
• Straightforward.
• Scalability (single-hop neighbors).
 SPIN-EC
SPIN-PP + low-energy threshold
Modifies behavior based on current energy
resources
Fall 2006
22
SPIN-PP Demonstration
A
B
Fall 2006
23
SPIN on Broadcast Networks
 One transmission reaches all neighbors
 SPIN-BC
 Same 3-stage handshake protocol as SPIN-PP
 Uses only broadcast communication
• Same transmission cost as unicast
• Coordination among nodes
• Broadcast message suppression
 SPIN-RL
 SPIN-BC + Reliability
 Periodically re-broadcast ADVs and REQs
Fall 2006
24
SPIN-BC Demonstration
E
E
DATA
B suppression
B
Request
ADV
E
Mode
ADVA
A
B
A
C
C
REQ
C ADV
G
D
D
DADV
F
Nodes with data
Nodes without data
Nodes waiting to send REQ
Fall 2006
25
SPIN Evaluation
 Strengths
 Simplicity -> save energy in communication (more efficient
(60%) than classic flooding)
 Latency: converges relatively quickly
 Straightforward: ADV  REQ  DATA
 Scalability: Topological changes are localized (single-hop
neighbors)
 Robust: immune to node failures.
 Reliability: adapted to work in lossy or mobile networks.
 Weaknesses
 Nodes always participating (broadcast media)
 Cannot guarantee the delivery of data (intrusion detection)
Fall 2006
26
SPIN Conclusions
 Successfully use meta-data negotiation
 solves the implosion and overlap problems
 Resource-adaptive enhancements
 take care of resource blindness problem




Reliability enhancements
SPIN outperforms gossiping
SPIN consumes less energy than flooding
SPIN distributes more data per unit energy than
flooding
Fall 2006
27
Flat and Query Based Routing Protocols
D. Braginsky and D. Estrin, "Rumor routing algorithm for sensor
networks," in Proceedings of the First Workshop on Sensor
Networks and Applications (WSNA), Atlanta, GA, October 2002
Fall 2006
28
Rumor Routing
 Designed for query/event ratios between query and
event flooding
 Motivation
 Sometimes a non-optimal route is satisfactory
 Advantages
 Tunable best effort delivery
 Tunable for a range of query/event ratios
 Disadvantages
 Optimal parameters depend heavily on topology (but can be
adaptively tuned)
 Does not guarantee delivery
Fall 2006
29
Basis for Algorithm
 Observation: Two lines in a
bounded rectangle have a
69% chance of intersecting
 Create a set of straight line
gradients from event, then
send query along a random
straight line from source.
Event
Source
Fall 2006
30
Creating Paths
 Nodes having observed an
event send out agents which
leave routing info to the
event as state in nodes
 Agents attempt to travel in a
straight line
 If an agent crosses a path to
another event, it begins to
build the path to both
 Agent also optimizes paths if
they find shorter ones.
Fall 2006
31
Algorithm Basics
 All nodes maintain a neighbor list.
 Nodes also maintain a event table
When it observes an event, the event is added
with distance 0.
 Agents
Packets that carry local event info across the
network.
Aggregate events as they go.
Fall 2006
32
Agent Path
 Agent tries to travel in a “somewhat” straight
path.
Maintains a list of recently seen nodes.
When it arrives at a node, it adds the node’s
neighbors to the list.
For the next tries to find a node not in the recently
seen list.
Avoids loops
important to find a path regardless of “quality”
Fall 2006
33
Following Paths
 A query originates from source, and is
forwarded along until it reaches it’s TTL
 Forwarding Rules:
If a node has not seen the query before, it is sent
to a random neighbor
If a node has a route to the event, forward to
neighbor along the route
Otherwise, forward to random neighbor using
straightening algorithm
Fall 2006
34
Energy Comparison
 Rumor Routing (1000 queries)
 Total energy = Es + Q*(Eq + N*(1000-Qf)/1000)
 Es = avg. energy to set up path
 Eq = avg. energy to route a query
 Qf = successful queries
 Q number of queries are routed
 N = total number of nodes
 Query Flooding
 Total energy = Q*N
 Event Flooding
 Total energy = E*N
Fall 2006
35
Fault Tolerance
 After agents propagated paths to events,
some nodes were disabled.
 Delivery probability degraded linearly up to
20% node failure, then dropped sharply
Fall 2006
36
Some Thoughts
 The straightening algorithm used is essentially
only a random walk … can something better be
done.
 The tuning of parameters for different network
sizes and different node densities is not clear.
Fall 2006
37
Can we analyze
 The inherent concept looks powerful.
 Even though not presented in this way … this algorithm is
just an example of gossip routing.
 There are two types of gossip, gossip of events and gossip
of queries.
 It maybe possible to find the probability of intersection of
these two.
 That might lead to a set of techniques for parameter
estimation, or an optimal setting.
Fall 2006
38
C. Intanagonwiwat, R. Govindan, and D. Estrin, Directed diffusion:
a scalable and robust communication paradigm for sensor
networks, Proceedings of ACM MobiCom '00, Boston, MA,
(2000) 56-67
Fall 2006
39
Directed Diffusion
 Directed Diffusion is a prominent example
of data-centric routing based on
application layer data and purely local
interaction
 A sensing task is disseminated throughout
the network
 This dissemination sets up gradients within
the network
 There may be multiple gradient paths
 The sensor network reinforces one or
small number of these paths
Fall 2006
40
Basic Elements
Interest: Query or interrogation which specifies
what an user wants
Data Messages: Collected or processed
information of a physical phenomenon
Gradient: Direction state in each node that
receives an interest
Reinforcement: Selection of a particular neighbor
for drawing real data
Fall 2006
41
Naming
 Task descriptions are named by a list of
attribute-value pairs:
 Type = Four-legged animal //detect animal location
 Interval = 20 ms //send back events every 20 ms
 Duration = 10 seconds // for next 10 seconds
 Rect = [-100, 100, 200, 400] //from sensors within
rectangle
 Intuitively, the task description specifies an
interest for data matching the attributes. For
this reason, such a task description is called an
interest
Fall 2006
42
Interest Dissemination
C’s Interest cache
C
Interests
Gradients
source
B
sink
Sink disseminates interest for a four-legged animal (~36 bytes).
Initial interval is large.
Type = four-legged animal
Interval = 1s
Rect = [-100,200,200,400]
Timestamp = 01:10:40 Expires at = 01:20:40
Fall 2006
43
Interest Dissemination
C’s Interest cache
C
Interests
Gradients
source
B
sink
Every node contains an interest cache, with separate entries for distinct interests.
Entries do not contain info about sinks and therefore scale well.
Overlapping entries may be aggregated for efficiency.
Fall 2006
44
Interest Dissemination
C’s Interest cache
C
Interests
Gradients
Sink: 1s | B: 1s
source: 1s
source
B
Each interest cache entry contains a list of gradients; events that
match interest entries are propagated back to the sink via these
gradients. Gradient entries contain locally unique neighbor IDs,
data rates, and interval attributes.
sink
In the absence of information about which sensor nodes are likely to be able to
satisfy an interest, interests are broadcasted to all neighbors.
However, a node may suppress a received interest if it recently re-sent a matching request.
Fall 2006
45
C’s Data cache
Data Propagation
EVENT
C’s Interest cache
C
1 eps
Interests
Gradients
Sink: 1s | B: 1s
source: 1s
1 eps
source
1 eps
B
1 eps
1 eps
Initial interests request data at slow rates (e.g. 1 event per second).
sink
A sensor node that is able to furnish a query-result searches its interest cache for a matching entry; if
it finds one, it begins sending data messages (~64 bytes) towards the sink via its gradient list at the
highest specified rate.
Type = four-legged animal // type of animal seen
Instance = elephant //instance of this type
Location = [125,220] // node location
Confidence = 0.85 //confidence in the match
Timestamp = 01:20:40 //even generation time
Fall 2006
46
C’s Data cache
Data Propagation
C’s Interest cache
C
1 eps
EVENT
match
Interests
Gradients
Sink: 1s | B: 1s
source: 1s
1 eps
source
1 eps
B
1 eps
1 eps
Upon receiving a data message, nodes check their interest caches.
If no match is found, the data message is silently dropped.
sink
If a match is found, the node checks its data cache, which keeps track of recently
seen data items. If no data cache entry matches the message, a new entry is made
in the data cache and the message is re-sent to the node’s neighbors.
If a data cache entry matches the data message, the message is silently dropped,
thus, preventing loops.
Fall 2006
47
C’s Data cache
Reinforcement
C’s Interest cache
C
100
1 eps
eps
EVENT
Interests
Gradients
Sink:.01s
S:
1s | B: 1s
source: 1s
1 eps
source
1 eps
B
1 eps
100
eps
1 eps
After the sink starts receiving these low data rate events, it
reinforces one particular neighbor in order to “draw down” higher
quality (higher data rate) events.
sink
It does this explicitly by re-sending the original interest message, but with a smaller
interval value, to the empirically low delay path node.
Nodes update their caches and can then propagate reinforcement messages according to
local policies. For example, the node might choose that neighbor from whom it first
received the latest event matching the interest
Fall 2006
48
Considerations
 Embedding application semantics in
communication logic allows for optimizations
such as loop prevention and downconversion
(for instance, interpolating high rate
messages for a low rate receiver)
 Negative reinforcement is used to prune
superfluous gradients
Fall 2006
49
Negative Reinforcement
 Could use time outs or explicit degrade
messages as negative reinforcement
mechanisms
 Orthogonal to the mechanism, NR controls
can be propagated according to a number of
different rules
E.g.: negatively reinforce that neighbor from which
no new events have been received within a
window of N events or T time units
Fall 2006
50
Network Topology
 This paradigm works with multiple sources (but sinks
may draw redundant data) and multiple sinks hosting
identical interests (in which case the second sink can
immediately draw down high quality via its cache)
Fall 2006
51
Local Repair
 Reinforcement rules can be
applied by intermediate
nodes to repair faulty links:
 Node C can discover better
path by requesting higher
rates from non-faulty
neighbors
 Reinforcement must be
applied carefully to prevent
all downstream nodes from
doing the same, which will
result in discovery of a good
path, but will waste
resources
Fall 2006
52
Design Parameters
Diffusion
Element
Design Choices
Interest
Propagation
Flooding
Constrained or directional flooding
Directional propagation based on previously cached data
Data
Propagation
Reinforcement to single path delivery
Multi-path delivery with selective quality along different
paths
Multi-path delivery with probabilistic forwarding
Data Caching
and Aggregation
For robust data delivery in the face of node failure
For coordinated sensing and data reduction
For directing interests
Reinforcement
Rules for deciding when to reinforce
Rules for how many neighbors to reinforce
Negative reinforcement mechanism and rules
Fall 2006
53
Evaluation: Metrics
 Average Dissipated Energy
 Measures the ratio of total dissipated energy per node in
the network to the number of distinct events seen by
sinks
 Computes average work done by a node as well as the
overall lifetime of sensor nodes
 Average Delay
 Measures the average one-way latency between
transmitting an event and receiving it at a sink
 Event Delivery Ratio
 Ratio of the number of distinct events received to the
number originally sent
Fall 2006
54
Conclusions
 Diffusion is data-centric
 All communication is neighbor-to-neighbor, not endto-end
 No routers—each node can interpret all messages
 No globally unique IDs (but locally unique IDs needed)
 Application-specific semantics embedded in
communication
 Observations
 Congestion?
 Network locality could be used to conserve energy and get
rid of un-necessary transmissions?
Fall 2006
55
Hierarchical Routing Protocols
Heinzelman, W.R.; Chandrakasan, A.; Balakrishnan, H.; LEACH:
Low Energy Adaptive Cluster Hierarchy, System Sciences,
2000. Proceedings of the 33rd Annual Hawaii International
Conference on , 4-7 Jan. 2000 vol.2
Fall 2006
56
LEACH (1)
 In order to spread this energy usage over
multiple nodes, the cluster-head nodes are not
fixed:
Dynamic clusters: (a) cluster-head nodes= C at time t1
(b) cluster-head nodes = C’ at time t1+d.
Fall 2006
57
LEACH (2)







Self-organizing, adaptive clustering protocol that uses
randomization to distribute the energy load evenly among the
sensors in the network.
Nodes organize themselves into local clusters, with one node
acting as the local base station or cluster-head
LEACH includes randomized rotation of the high-energy clusterhead position such that it rotates among the various sensors in
order to not drain the battery of a single sensor
Cluster-header nodes broadcast their status to the other sensors
in the network. Each sensor node determines to which cluster it
wants to belong by choosing the cluster-head that requires the
minimum communication energy
Each cluster-head creates a schedule for the nodes in its cluster
Each non-cluster-head node to be turned off at all times except
during its transmit time
Cluster-head node aggregates the data and then transmits the
compressed data to the base station
Fall 2006
58
LEACH (3)
Normalized total system energy
dissipated versus the percent of
nodes that are cluster-heads
Total system energy dissipated
using direct communication,
MTE routing and LEACH for the
100-node random network
Fall 2006
59
LEACH (4)
System lifetime using direct
transmission, MTE routing,
static clustering, and LEACH
with 0.5 J/node
Sensors that remain alive and
those that are dead after 1200
rounds with 0.5 J/node for LEACH
Fall 2006
60
LEACH (5)
Total system energy dissipated using (a) direct
communication and LEACH and (b) MTE routing and
LEACH for the random network
Fall 2006
61
LEACH Algorithm Details (1)
 The operation of LEACH is broken up into rounds,
where each round begins with a set-up phase,
when the clusters are organized, followed by a
steady-state phase, when data transfers to the
base station occur.
 In order to minimize overhead, the steady-state
phase is long compared to the set-up phase
Fall 2006
62
LEACH Algorithm Details (2)

Advertisement Phase




Initially, when clusters are being created, each node decides whether or not
to become a cluster-head for the current round
This decision is based on the suggested percentage of cluster heads for the
network and the number of times the node has been a cluster-head so far
This decision is made by the node n choosing a random number between 0
and 1.
If the number is less than a threshold T(n). The node becomes a cluster-head
for the current round. The threshold is set as:
P
1-P*(r mod 1/P)
If n ЄG
T(n) =
0
otherwise
where P = the desired percentage of cluster heads, r = the current round, and G is
the set of nodes that have not been cluster-heads in the last 1/P rounds
Fall 2006
63
LEACH Algorithm Details (3)

Advertisement Phase (cont.)
P
1-P*(r mod 1/P)
If n ЄP
T(n) =
0
otherwise
 During round 0 (r=0), each node has a probability P of
becoming a cluster-head.
 Nodes that are cluster-heads in round 0 cannot be clusterheads for the next 1/P rounds
 After 1/P -1 rounds, T =1 for any nodes that have not yet been
cluster-heads, and after 1/P rounds, all nodes are once again
eligible to become cluster-heads.
 Assuming that all nodes begin with the same amount of energy
and being a cluster-head removes approximately the same
amount of energy for each node
 Each non-cluster-head node decides the cluster to which it will
belong for this round. This decision is based on the received
signal strength of the advertisement
Fall 2006
64
LEACH Algorithm Details (4)

Cluster Set-Up Phase



Schedule Creation



After each node has decided to which cluster it belongs, it must
inform the cluster-head node that it will be a member of the cluster
All cluster-head nodes must keep their receivers on
Based on the number of nodes in the cluster, the cluster-head node
creates a TDMA schedule telling each node when it can transmit
This schedule is broadcast back to the nodes in the cluster
Data transmission



Send it during their allocated transmission time to the cluster head
Each non-cluster-head node can be turned off until the node’s
allocated transmission time, thus minimizing energy dissipation in
these nodes
All the data has been received, the cluster head node performs
signal processing functions to compress the data into a single signal
Fall 2006
65
LEACH Algorithm Details (5)

Multiple Clusters



Transmission in one cluster will affect communication in a nearby
cluster
Each cluster communicates using different CDMA codes
Neighboring clusters’ radio signals will be filtered out and not corrupt
the transmission of nodes in the cluster
B
A
C

Hierarchical Clustering


Cluster-head nodes would communicate with “super-cluster-head”
nodes and so no until the top layer of the hierarchy
For large network, this hierarchy could save a tremendous amount of
energy
Fall 2006
66
LEACH Conclusion

LEACH: a clustering-based routing protocol that minimizes
global energy usage by distributing the load to all the nodes at
different points in time

LEACH outperforms static clustering algorithms by requiring
nodes to volunteer to be high-energy cluster-heads and
adapting the corresponding clusters based on the nodes that
nodes choose to be cluster-head at a given time

Distributing the energy among the nodes in the network is
effective in reducing energy dissipation from a global
perspective and enhancing system lifetime
Fall 2006
67
Discussion
 Routing is one of the challenging and flourishing
frontier of WSNs research
 One of the major reason is target localization
 Energy efficiency, still prevailing as the main
optimization issue
 We will study few of the recent protocols and
analysis in the next class
Fall 2006
68
Thanks !
Fall 2006
69