Energy-Efficient Communication Protocol for

Wireless Microsensor Networks

Wendi Rabiner Heinzelman

Anatha Chandrasakan
Hari Balakrishnan

Massachusetts Institute of Technology

Presented by Rick Skowyra

Overview
 Introduction
 Radio Model
 Existing Protocols
– Direct Transmission
– Minimum Transmission Energy
– Static Clustering
 LEACH
 Performance Comparison
 Conclusions
2
Introduction
 LEACH (Low-Energy Adaptive
Clustering Hierarchy) is a routing
protocol for wireless sensor networks in
which:
– The base station (sink) is fixed
– Sensor nodes are homogenous
 LEACH conserves energy through:
– Aggregation
– Adaptive Clustering
3
Radio Model
 Designed around
acceptable Eb/N0
 Eelec = 50nJ/bit
– Energy dissipation
for transmit and
receive
 εamp = 100pJ/bit/m2 ETx (k , d )  ( Eelec * k )  ( amp * k * d 2 )
– Energy dissipation ERx (k )  Eelec * k
for transmit amplifier
 k = Packet size
 d = Distance
4
Existing Routing Protocols
 LEACH is compared against three other
routing protocols:
– Direct-Transmission
• Single-hop
– Minimum-Transmission Energy
• Multi-hop
– Static Clustering
• Multi-hop

5
Direct-Transmission
 Each sensor node
transmits directly to
the sink, regardless
of distance
 Most efficient when
there is a small
coverage area Sensor Status after 180 rounds
and/or high receive with 0.5J/node

cost

6
Minimum Transmission Energy (MTE)
 Traffic is routed
through intermediate
nodes
– Node chosen by transmit
amplifier cost
– Receive cost often
ignored
 Most efficient when the
average transmission Sensor Status after 180 rounds
with 0.5J/node
distance is large and
Eelec is low

7
MTE vs Direct-Transmission
When is Direct-Transmission Better?
Edirect  EMTE when:
Eelec r 2 n

 amp 2
Edirect  k ( Eelec   ampn 2 r 2 )
• High radio operation costs
EMTE  k (( 2n  1) Eelec   ampnr 2 ) favor direct-transmission
• Low transmit amplifier
For MTE, a node at distance nr costs (i.e. distance to the
requires n transmits of distance r, sink) favor direct
and n-1 receives transmission
• Small inter-node
distances favor MTE

8
MTE vs. Direct-Transmission (cont)

• 100-node random network

• 2000 bit packets
• εamp = 100pJ/bit/m2

9
Static Clustering
 Indirect upstream
traffic routing
 Cluster members
transmit to a cluster
head
– TDMA
 Cluster head transmits
to the sink
– Not energy-limited
 Does not apply to
homogenous
environments
10
LEACH
 Adaptive Clustering
– Distributed
 Randomized Rotation
– Biased to balance energy loss
 Heads perform compression
– Also aggregation
 In-cluster TDMA

11
LEACH: Adaptive Clustering
 Periodic independent
self-election
t1
– Probabilistic
 CSMA MAC used to
advertise
 Nodes select
advertisement with
strongest signal
strength t2

 Dynamic TDMA cycles

12
LEACH: Adaptive Clustering

 Number of clusters
determined a priori
– Compression cost of
5nj/bit/2000-bit message
 “Factor of 7 reduction
in energy dissipation”
– Assumes compression is
cheap relative to
transmission
– Overhead costs ignored

13
LEACH: Randomized Rotation
 Cluster heads elected every round
– Recent cluster heads disqualified
– Optimal number not guaranteed
 Residual energy not considered
 Assumes energy uniformity
– Impossible with significant network diameters

 P = Desired cluster head  P

percentage  if n  G
1
 r = Current Round T (n)  1  P * (r mod )
 G = Set of nodes which have not  P
been cluster heads in 1/P 0 otherwise
rounds
14
LEACH: Operation
 Periodic process
 Three phases per round:
– Advertisement
• Election and membership
– Setup
• Schedule creation
– Steady-State
• Data transmission

15
LEACH: Advertisement
 Cluster head self-election
– Status advertised broadcast to nearby
nodes
 Non-cluster heads must listen to the
medium
– Choose membership based on signal
strength
• RSSI
• Eb/N0

16
LEACH: Setup
 Nodes broadcast membership status
– CSMA
 Cluster heads must listen to the
medium
 TDMA schedule created
– Dynamic number of time slices

17
LEACH: Data Transmission
 Nodes sleep until time slice
 Cluster heads must listen to each slice
 Cluster heads aggregate/compress and
transmit once per cycle
 Phase continues until the end of the
round
– Time determined a priori

18
LEACH: Interference Avoidance
 TDMA intra-cluster
 CDMA inter-cluster
– Spreading codes
determined randomly
• Non-overlapping
modulation may be
NP-Complete
– Broadcast during
advertisement phase

19
LEACH: Hierarchical Clustering
 Not currently implemented
 n tiers of clusters of cluster heads
 Efficient when network diameters are
large

20
Performance: Parameters
 MATLAB Simulator
 100-node random
network
 Eelec = 50nj/bit
 εamp = 100pJ/bit/m2
 k = 2000 bits

21
Performance: Network Diameter
 LEACH vs. Direct
Transmission
– 7x-8x energy
reduction
 LEACH vs. MTE
– 4x-8x energy
reduction

22
Performance: Energy and Diameter

LEACH vs. Direct Transmission

MTE vs. Direct Transmission

• LEACH performs in most conditions

• At low diameters and energy costs,
performance gains negligible
•Not always same for costs
•Comparable to MTE for some configurations
LEACH vs. MTE 23
Performance: System Lifetime
 Setup costs ignored
 0.5J of energy/node
 LEACH more than
doubles network
lifetime
 Static clusters fail
as soon as the
cluster head fails
– Can be rapid

24
Performance: System Lifetime
 Experiments
repeated for
different maximum
energy levels
 LEACH gains:
– 8x life expectancy for
first node
– 3x life expectancy for
last node

25
Performance: Coverage
 LEACH
– Energy distributed evenly
– All nodes serve as
cluster heads eventually
– Deaths randomly
distributed
 MTE
– Nodes near the sink die
first
 Direct Transmission
– Nodes on the edge die
first

26
Conclusions
 LEACH is completely distributed
– No centralized control system
 LEACH outperforms:
– Direct-Transmission in most cases
– MTE in many cases
– Static clustering in effectively all cases
 LEACH can reduce communication costs by
up to 8x
 LEACH keeps the first node alive for up to 8x
longer and the last node by up to 3x longer
27
Future Work
 Extend ns to simulate LEACH, MTE, and
Direct Transmission
 Include energy levels in self-election
 Implement hierarchical clustering

28
Areas for Improvement
 LEACH assumes all cluster heads pay the
same energy cost
– Death model incorrect
 Compression may not be as cheap as claimed
– Unclear how much savings are from compression
assumptions and how much from adaptive
clustering
 Optimal number of cluster heads must be
determined in simulation, before
implementation
 Round durations never specified or explained
29
Questions

30