15-10-2016, 02:44 PM
[attachment=73116]
Abstract
Data gathering is a common but critical operation
in many applications of wireless sensor networks. Innovative
techniques that improve energy efficiency to
prolong the network lifetime are highly required. Clustering
is an effective topology control approach in wireless
sensor networks, which can increase network scalability
and lifetime. In this paper, we propose a novel
clustering schema EECS for wireless sensor networks,
which better suits the periodical data gathering applications.
Our approach elects cluster heads with
more residual energy through local radio communication
while achieving well cluster head distribution; further
more, it introduces a novel method to balance the
load among the cluster heads. Simulation results show
that EECS outperforms LEACH significantly with prolonging
the network lifetime over 35%.
1 Introduction
Continued advances of MEMS and wireless communication
technologies have enabled the deployment
of large scale wireless sensor networks (WSNs) [1].
The potential applications of WSNs are highly varied,
such as environmental monitoring, target tracking and
military [2]. Sensors in such a network are equipped
with sensing, data processing and radio transmission
units while the power is highly limited. Due to the
sensors’ limited power, innovative techniques that improve
energy efficiency to prolong the network lifetime
are highly required.
Data gathering is a common but critical operation
in many applications of WSNs, where data aggregation
and hierarchical mechanism are commonly used
techniques. Data aggregation can eliminate the data
redundancy and reduce the communication load [3].
Hierarchical (clustering) mechanisms are especially effective
in increasing network scalability and reducing
data latency, which have been extensively exploited.
LEACH [4] which is the first clustering protocol, proposes
a two-phase mechanism based on single-hop
communication. The plain node transmits the data to the corresponding cluster head and the cluster head
transmits the aggregated data to the base station
(BS). HEED [5] selects cluster heads through O(1)
time iteration according to some metric and adopts
the multi-hop communication to further reduce the
energy consumption. PEGASIS [6] improves the performance
of LEACH and prolongs the network lifetime
greatly with a chain topology. But the delay is significant
although the energy is saved. There are some
other related work [7–9] which efficiently use energy
through clustering.
In this paper, we propose and evaluate an energy
efficient clustering scheme (EECS) for periodical data
gathering applications in WSNs. In the cluster head
election phase, a constant number of candidate nodes
are elected and compete for cluster heads according
to the node residual energy. The competition process
is localized and without iteration, thus it has much
lower message overhead. The method also produces
a near uniform distribution of cluster heads. Further
in the cluster formation phase, a novel approach is
introduced to balance the load among cluster heads.
EECS is fully distributed and more energy efficient
and the simulation results show that it prolongs the
network lifetime as much as 135% of LEACH.
The remainder of this paper is organized as follows.
Section 2 outlines the data gathering issues in WSNs.
Section 3 exhibits the details of EECS and Section 4
analyzes the properties of EECS. Section 5 evaluates
the performance of EECS. Finally, Section 6 gives the
conclusion and future work.
2 Problem Outline
Data gathering is a typical application in WSNs.
Sensors periodical sense the environment and transmit
the data to the base station (BS), and the BS analyzes
the data to draw some conclusions about the activity
in the area. We make a few assumptions about the
network model and introduce the radio model before
the problem statements.
Network Model
To simplify the network model, we adopt a few
reasonable assumptions as follows: 1)N sensors are
uniformly dispersed within a square field A; 2)All
sensors and BS are stationary after deployment;
3) The communication is based on the single-hop;
4)Communication is symmetric and a sensor can compute
the approximate distance based on the received
signal strength if the transmission power is given;
5)All sensors are location-unaware; 6)All sensors are
of equal significance.
We use a simplified model shown in [4] for the radio
hardware energy dissipation as follows. We refer
readers to [4] for more details. To transmit an l-bit
data to a distance d, the radio expands:
ETx
(l, d) = (
l × Eelec + l × ²f sd
2
, d < dcrossover
l × Eelec + l × ²mpd
4
, d ≥ dcrossover
(1)
The first item presents the energy consumption of
radio dissipation, while the second presents the energy
consumption for amplifying radio. Depending
on the transmission distance both the free space ²f s
and the multi-path fading ²mp channel models are
used [11]. When receiving this data, the radio expends:
ERx
(l) = l×Eelec. Additionally, the operation
of data aggregation consumes the energy as EDA.
2.2 Problem Statement
Once a sensor node runs out its energy, we consider
the network is dead because some area cannot
be monitored any more. Periodical data gathering applications
in large scale sensor networks appeal the design
of scalable, energy efficient clustering algorithms.
Thus our primal goals in EECS are as follows: 1) fully
distributed manner. Sensors interact with each other
through localized communication; 2) low control overhead.
It is desirable to reduce control overhead to
extend the time of data gathering; 3) load balanced
clustering mechanism. Balance the load among the
sensors, especially among the cluster heads. In the
next section, we will describe the EECS algorithm in
details.
3 EECS Details
EECS is a LEACH-like clustering scheme, where
the network is partitioned into a set of clusters with
one cluster head in each cluster. Communication between
cluster head and BS is direct (single-hop). For
easy reference, we summarize the notations in Table
1.
In the network deployment phase, the BS broadcasts
a “hello” message to all the nodes at a certain
Cluster head election
In this phase, several cluster heads are elected.
Nodes become CANDIDATE nodes with a probability
T and then broadcast the COMPETE HEAD MSGs within
radio range Rcompete to advertise their wills. Each
CANDIDATE node checks whether there is a CANDIDATE
node with more residual energy within the radius
Rcompete. Once the CANDIDATE node finds a more powerful
CANDIDATE node, it will give up the competition
without receiving subsequential COMPETE HEAD MSGs.
Otherwise, it will be elected as HEAD in the end.
3.2 Cluster formation
In this phase, each HEAD node broadcasts the
HEAD AD MSG across the network, while the PLAIN
nodes receive all the HEAD AD MSGs and decide which
cluster to join. Most of existed metric for PLAIN nodes
to make decisions is the distance metric. For example
in [4] or [7], the PLAIN nodes choose the cluster
head that require minimum communication according
to the received signal strength. However, pursuing ef-
ficient energy consumption of the PLAIN nodes only
may lead HEAD nodes exhausted quickly during the
data transmission phase.
Abstract
Data gathering is a common but critical operation
in many applications of wireless sensor networks. Innovative
techniques that improve energy efficiency to
prolong the network lifetime are highly required. Clustering
is an effective topology control approach in wireless
sensor networks, which can increase network scalability
and lifetime. In this paper, we propose a novel
clustering schema EECS for wireless sensor networks,
which better suits the periodical data gathering applications.
Our approach elects cluster heads with
more residual energy through local radio communication
while achieving well cluster head distribution; further
more, it introduces a novel method to balance the
load among the cluster heads. Simulation results show
that EECS outperforms LEACH significantly with prolonging
the network lifetime over 35%.
1 Introduction
Continued advances of MEMS and wireless communication
technologies have enabled the deployment
of large scale wireless sensor networks (WSNs) [1].
The potential applications of WSNs are highly varied,
such as environmental monitoring, target tracking and
military [2]. Sensors in such a network are equipped
with sensing, data processing and radio transmission
units while the power is highly limited. Due to the
sensors’ limited power, innovative techniques that improve
energy efficiency to prolong the network lifetime
are highly required.
Data gathering is a common but critical operation
in many applications of WSNs, where data aggregation
and hierarchical mechanism are commonly used
techniques. Data aggregation can eliminate the data
redundancy and reduce the communication load [3].
Hierarchical (clustering) mechanisms are especially effective
in increasing network scalability and reducing
data latency, which have been extensively exploited.
LEACH [4] which is the first clustering protocol, proposes
a two-phase mechanism based on single-hop
communication. The plain node transmits the data to the corresponding cluster head and the cluster head
transmits the aggregated data to the base station
(BS). HEED [5] selects cluster heads through O(1)
time iteration according to some metric and adopts
the multi-hop communication to further reduce the
energy consumption. PEGASIS [6] improves the performance
of LEACH and prolongs the network lifetime
greatly with a chain topology. But the delay is significant
although the energy is saved. There are some
other related work [7–9] which efficiently use energy
through clustering.
In this paper, we propose and evaluate an energy
efficient clustering scheme (EECS) for periodical data
gathering applications in WSNs. In the cluster head
election phase, a constant number of candidate nodes
are elected and compete for cluster heads according
to the node residual energy. The competition process
is localized and without iteration, thus it has much
lower message overhead. The method also produces
a near uniform distribution of cluster heads. Further
in the cluster formation phase, a novel approach is
introduced to balance the load among cluster heads.
EECS is fully distributed and more energy efficient
and the simulation results show that it prolongs the
network lifetime as much as 135% of LEACH.
The remainder of this paper is organized as follows.
Section 2 outlines the data gathering issues in WSNs.
Section 3 exhibits the details of EECS and Section 4
analyzes the properties of EECS. Section 5 evaluates
the performance of EECS. Finally, Section 6 gives the
conclusion and future work.
2 Problem Outline
Data gathering is a typical application in WSNs.
Sensors periodical sense the environment and transmit
the data to the base station (BS), and the BS analyzes
the data to draw some conclusions about the activity
in the area. We make a few assumptions about the
network model and introduce the radio model before
the problem statements.
Network Model
To simplify the network model, we adopt a few
reasonable assumptions as follows: 1)N sensors are
uniformly dispersed within a square field A; 2)All
sensors and BS are stationary after deployment;
3) The communication is based on the single-hop;
4)Communication is symmetric and a sensor can compute
the approximate distance based on the received
signal strength if the transmission power is given;
5)All sensors are location-unaware; 6)All sensors are
of equal significance.
We use a simplified model shown in [4] for the radio
hardware energy dissipation as follows. We refer
readers to [4] for more details. To transmit an l-bit
data to a distance d, the radio expands:
ETx
(l, d) = (
l × Eelec + l × ²f sd
2
, d < dcrossover
l × Eelec + l × ²mpd
4
, d ≥ dcrossover
(1)
The first item presents the energy consumption of
radio dissipation, while the second presents the energy
consumption for amplifying radio. Depending
on the transmission distance both the free space ²f s
and the multi-path fading ²mp channel models are
used [11]. When receiving this data, the radio expends:
ERx
(l) = l×Eelec. Additionally, the operation
of data aggregation consumes the energy as EDA.
2.2 Problem Statement
Once a sensor node runs out its energy, we consider
the network is dead because some area cannot
be monitored any more. Periodical data gathering applications
in large scale sensor networks appeal the design
of scalable, energy efficient clustering algorithms.
Thus our primal goals in EECS are as follows: 1) fully
distributed manner. Sensors interact with each other
through localized communication; 2) low control overhead.
It is desirable to reduce control overhead to
extend the time of data gathering; 3) load balanced
clustering mechanism. Balance the load among the
sensors, especially among the cluster heads. In the
next section, we will describe the EECS algorithm in
details.
3 EECS Details
EECS is a LEACH-like clustering scheme, where
the network is partitioned into a set of clusters with
one cluster head in each cluster. Communication between
cluster head and BS is direct (single-hop). For
easy reference, we summarize the notations in Table
1.
In the network deployment phase, the BS broadcasts
a “hello” message to all the nodes at a certain
Cluster head election
In this phase, several cluster heads are elected.
Nodes become CANDIDATE nodes with a probability
T and then broadcast the COMPETE HEAD MSGs within
radio range Rcompete to advertise their wills. Each
CANDIDATE node checks whether there is a CANDIDATE
node with more residual energy within the radius
Rcompete. Once the CANDIDATE node finds a more powerful
CANDIDATE node, it will give up the competition
without receiving subsequential COMPETE HEAD MSGs.
Otherwise, it will be elected as HEAD in the end.
3.2 Cluster formation
In this phase, each HEAD node broadcasts the
HEAD AD MSG across the network, while the PLAIN
nodes receive all the HEAD AD MSGs and decide which
cluster to join. Most of existed metric for PLAIN nodes
to make decisions is the distance metric. For example
in [4] or [7], the PLAIN nodes choose the cluster
head that require minimum communication according
to the received signal strength. However, pursuing ef-
ficient energy consumption of the PLAIN nodes only
may lead HEAD nodes exhausted quickly during the
data transmission phase.