Life Time Sensitive Weighted Clustering on Wireless Sensor
Networks
Elnaz Alizadeh Jarchlo
1
and Cüneyt F. Bazlamaçcı
2
1
Department of Information Systems, Informatics Institute, Middle East Technical University, 06800, Ankara, Turkey
2
Department of Electrical and Electronics Engineering, Middle East Technical University, 06800, Ankara, Turkey
Keywords: Wireless Sensor Networks, Network Lifetime, Clustering.
Abstract: The present paper considers weighted clustering algorithms for mobile ad hoc networks (MANET) and
wireless sensor networks (WSN). First, we summarize the similarities and differences between the two
types of networks as then examine the existing weighted clustering algorithms proposed so far. We
specifically examine the objective functions and performances of the algorithm in terms of various
parameters. In addition, we proposed a new algorithm called as the Life Time Sensitive Weighted
Clustering Algorithm (LTS-WCA), which aims to adapt the already existing weighted clustering algorithm
(WCA) proposed for MANET to WSN and modify and enhance it. WCA was proposed in the literature for
forming cluster-heads in mobile ad hoc networks but we have demonstrated that it can also be effective
when used in a wireless sensor network domain.
1 INTRODUCTION
Sensor networks include a large number of sensors,
which are able to sense the environment and process
data in order to transfer gathered information to the
sink(s). Wireless sensor nodes started to play critical
roles in our lives. Many researchers have attempted
to utilize the existing theoretical studies in order to
apply them on practical applications in various areas
such as medicine (e.g. health monitoring (Li, et.al.
2009)), environment (e.g. disaster monitoring),
military (e.g. target surveillance and battlefield
mapping (Dechene, et.al. 2008)) and agriculture
(Burrell, et.al., 2004), etc.
Clustering a network leads to a creating a
hierarchical one by partitioning the existing flat
network into several groups of nodes, where each
group has a leader node called ‘cluster-head’ and the
remaining local nodes, which are connected to their
associated cluster-heads, are called ‘cluster
members’. The cluster-heads then are usually
connected in the shape of a backbone of the
corresponding network. One of the main issues in a
clustering algorithm is the process of categorizing
the nodes into disjoint groups and choosing the most
appropriate nodes as cluster-heads for having an
efficient network. There are different types of
clustering algorithms running on mobile ad hoc
networks (MANET) and wireless sensor networks
(WSN).
The present work aims at modifying and
enhancing the weighted clustering algorithm
(WCA), which was frequently cited for the purpose
of forming cluster-heads in mobile ad hoc networks.
The main argument for choosing it as the subject of
this study is its potential effectiveness when used in
a wireless sensor network domain.
The paper concentrates on the issue of energy
efficiency in clustering in WSN and especially on
increasing the network life time by considering
several critical parameters in this new algorithm
called as the Life-Time Sensitive Weighted
Clustering Algorithm (LTS-WCA).
Section 2 describes MANET and WSN and
briefly overviews the existing weighted clustering
approaches proposed for them. Section 3 presents
our new method, called as Life-Time Sensitive
Clustering Algorithm (LTS-WCA) while
emphasizing the differences between this proposal
and its original version called as Weighted
Clustering Algorithm (WCA). Section 4 includes our
implementation of the algorithm, the simulation
study carried out on LTS-WCA using ns2 simulator,
and evaluation results. Finally, section 5 concludes
the paper.
41
Alizadeh Jarchlo E. and Bazlamaçcı C..
Life Time Sensitive Weighted Clustering on Wireless Sensor Networks.
DOI: 10.5220/0004730700410051
In Proceedings of the 3rd International Conference on Sensor Networks (SENSORNETS-2014), pages 41-51
ISBN: 978-989-758-001-7
Copyright
c
2014 SCITEPRESS (Science and Technology Publications, Lda.)
2 MANET VS WSN
Mobile ad hoc networks and wireless sensor
networks have both similarities and differences. The
main similarities between MANET and WSN are
described as follows (Jindal, et.al., 2011), (MANET
vs WSN):
• Both are distributed and self-organized networks
without any central infrastructure.
• Both use wireless links for communication
purposes.
• Communication and routing among nodes may be
in multi hop fashion.
The main differences between MANET and
WSN can be listed as follows (MANET vs WSN):
• MANET users are generally appliances designed
for human beings (e.g. laptop, computers, PDAs,
mobile radio terminals, etc.) but WSNs focus
mostly on interactions with the environment
(monitoring and sensing the environment or maybe
tracking objects and/or activities in the sensing
environment).
• MANET network density is smaller in comparison
with WSN and the number of WSN sensor nodes
is higher in comparison with MANET.
• The number of active users in the deployment area
specifies the network size in MANET, however the
extension of the observed area, characteristics of
the nodes and the required redundancy level define
the number of nodes in WSN.
• Data traffic in MANET is higher than WSN
because of using services like web, mail, video,
etc.
• Sensor nodes in MANET are powerful
computation devices however in WSN they are
cheap tiny nodes.
• Energy concerns in MANET are of secondary
importance in comparison to WSN. Stored energy
in tiny sensor nodes in WSN is very restricted and
the quick loss of energy is considered as a main
problem in WSN.
The purposes of running clustering algorithms
on these two types of networks are slightly different.
Wireless sensor networks mostly concentrate on
how to sense the environment and send the gathered
data to sink(s) aiming to increase the network life
time and energy efficiency but in mobile ad hoc
networks the main goal is to distribute the generated
traffic among nodes by routing it in a multi hop
fashion.
Weighted Clustering Algorithm (WCA) is one of
the clustering algorithms, which was originally and
initially applied on mobile ad hoc networks. It
considers several different parameters in order to
select a cluster-head (CH) while running the
algorithm. We believe it to be more beneficial
compared to other clustering algorithms that take
one or two parameters into account at most. The
main objectives of applying WCA on MANET are
choosing an optimal number of CHs, decreasing
latency as much as possible and decreasing the
number of re-affiliations. Since there exists many
similarities between MANET and WSN, the
application of WCA is conjectured to be helpful and
beneficial for WSN also, however it surely needs
modifications in order to adapt it to wireless sensor
network environments.
2.1 Weighted Clustering Algorithms
for MANET
There is a vast amount research work carried out on
the weighted clustering algorithms. Each of these
studies has its own specific objective employing
various parameters. This section reviews the existing
weighted clustering approaches very briefly.
2.1.1 On-demand Weighted Clustering
Algorithm for Ad Hoc Networks
(WCA)
On-demand weighted Clustering algorithm (WCA)
is the original weighted clustering algorithm cited by
many other studies in the field (Chatterjee, et.al.,
2000). WCA is an on-demand algorithm, which aims
at optimizing the operation of the medium access
control protocol and decreasing the cost of both
communications and computations. In this
algorithm, cluster heads use ‘dual power’ mode in
order to transfer a message among clusters in a
higher transmission range. WCA procedure is as
follows:
1- Each node finds its neighbors and the node
degree
d
v
= |N[v]|=
∑
dist
v, v
T
∈,
.
where N[v] denotes the set of neighbors of node v,
dist(u,v) denotes the distance between nodes u and
v, and T
x
denotes the transmission range of a node.
2- Each node calculates its degree difference
∆
v
=|d
v
-δ|
where d
v
defines the number of node degree and δ
is a predefined ideal number of nodes placed
within a cluster.
3- Each node calculates the sum of the distances to
all its neighbors
D
v
=
∑
dist
v, v
∈
SENSORNETS2014-InternationalConferenceonSensorNetworks
42
4- Each node defines the running average of its
speed until current time T
M
v
=
∑
x
x
y
y
where x and y denote the rectangular coordinates
of the node in time.
5- Each node computes its cumulative time, P
v
,
which is the time a node can act as a cluster-
head.
6- Each node then calculates its total weight as
follows:
w
v
= w
1
Δ
v
+w
2
D
v
+w
3
M
v
+w
4
P
v
;
where w
1
+w
2
+w
3
+w
4
=1
7- Considering global minima, the node with the
smallest weight value is selected as a cluster-
head.
The remaining nodes repeat the above steps until
the moment when each node starts acting as a cluster
member or a cluster-head. Nodes that belong to the
chosen clusters are not allowed to participate in the
clustering election again and steps 2 to 7 repeats for
the rest of the nodes that are not signed as a cluster
head or cluster member.
2.1.2 Weight based Adaptive Clustering in
Wireless Ad Hoc Networks (WBACA)
Weight based adaptive clustering in wireless ad hoc
networks (WBACA) (Dhurandher and Singh, 2005)
uses the local minima of weight instead of global
minima in order to decrease the number of re-
affiliations and the time delay within the network; it
specifies several parameters such as transmission
power, transmission rate, mobility, battery power
and the degree of a node to make clusters within a
mobile ad hoc network domain (Dhurandher and
Singh, 2005). An initial phase finds neighbourhoods.
Each node periodically broadcasts ‘Hello packet’
messages including its identification number. Nodes
lying within the same transmission range receive the
‘Hello packet’ messages and broadcast it to their
neighbours in response. The second phase includes
calculating weight values. Each node calculates its
weight and sends it to all its neighbours. The
clustering calculation is as follows:
w
n
=w
1
*M+w
2
*B+w
3
*T
x
+w
4
*D+w
5
/T
r
;
w
1
+ w
2
+ w
3
+ w
4
=1
where M is node mobility, B is battery power, T
x
is
transmission range, D is degree difference, and T
r
is
transmission rate.
While running WBACA, in a case when there is
no node with the smallest weight, the node itself
becomes a cluster-head. Otherwise, the node sends a
‘Join-Req’ message to the neighbouring cluster-head
with the smallest weight. The cluster-head sends a
‘Join-Ack’ message to reply ‘Join-Req’ messages.
The cluster-head accepts nodes as its cluster
members until its degree becomes equal to the
defined threshold value. In a case when a node
cannot belong to any cluster, it identifies itself as a
cluster-head. Restarting the algorithm takes place at
the moment when a link between a node and its
cluster-head gets broken.
2.1.3 Weighted Clustering Algorithm using
Local Cluster-Heads Election for QoS
in MANETs
Weighted clustering algorithm using local cluster-
heads election (WCA-L) aims at turning isolated
nodes into cluster-heads and forms their clusters by
invoking an election immediately at the moment
when two cluster-heads are one-hop neighbors
(Bricard-Vieu and Nasser, 2006). The ordinary
nodes attempt to affiliate to another cluster and only
the gateway nodes that lie within the transmission
ranges of two different cluster-heads are successful.
The remaining nodes and the cluster-heads keep
electing clustering process, which is the same as the
one defined in WCA.
2.1.4 Entropy-based Weighted Clustering
Algorithm for Ad Hoc Networks
Entropy-based weighted clustering algorithm
(EBWCA) aims at demonstrating the uncertainty
concerning the amount of disorder within a network
(Wang and Bao, 2007). One of the parameters taken
into account in EBWCA is the relative position
between two nodes, which is set as below:
a
m,n
=
∑
|→,,
|
Where m and n are node IDs and t
i
refers to the time
instant of the i-th calculation and N is the number of
separate times, t
i
. And the entropy of the node m is
H
m
(t, Δt) that is defined as follows:
H
m
(t,Δ
)=
∑
,
,
∈
where
P
k
(t, Δ
)=
,
∑
,∈
F
m
defines the set of the node m’s neighbors and
C(F
m
) is the cardinality of set F
m
. The proposed
LifeTimeSensitiveWeightedClusteringonWirelessSensorNetworks
43
algorithm EBWCA then calculates overall weight
for node v as follows:
w
v
= c
1
Δ
v
+ c
2
D
v
+ c
3
(−H
v
) + c
4
P
v
where c
1
, c
2
, c
3
, c
4
are the corresponding weighing
factors.
2.1.5 Advanced Efficiency and Stability
Combined Weight based Distributed
Clustering Algorithm in MANET
This algorithm has a hierarchical structure, which
aims to optimize network performance by
minimizing energy consumption and improving
probable problems of efficiency and stability that a
network may face (Hwang, et.al., 2007). The initial
phase of this algorithm is the recognition of a
neighbour. Each node calculates its total weight as
follows:
W
v
=w
1
D
v
+w
2
M
v
+w
3
Ev+w
4
∆
v
; w
1
+w
2
+w
3
+w
4
=1
where D
v
is the sum of distances of node v with all
its neighbours, M
v
is the average running speed of
node v, E
v
is the remaining amount of node v’s
battery and ∆
v
is the degree difference of node v.
Finally the node with smallest amount of W acts
as a cluster-head. This algorithm uses local minima
instead of global minima and moreover there is a
maintenance stage, which includes cluster
maintenance when cluster-head role is resigned and
when cluster member nodes move out.
2.1.6 Weight based Adaptive Clustering for
Large Scale Heterogeneous MANET
Weight based adaptive clustering algorithm
(WACHM) attempts to make a large scale
hierarchical MANET by utilizing heterogeneous
nodes to build various layers (Hwang, et.al., 2007).
The objectives of this algorithm are considered to be
choosing the optimal number of cluster-heads, using
optimal hop counts and defined dependency
probability and link stability within the network
domain.
The first step of the algorithm is to find
neighbours, which are categorized as two different
types: type-1 (cluster-heads) and type-0 (cluster
members). After that each node calculates the
following parameters:
w
i
=w
2
AP
s
+w
3
AP
d
+w
4
E
r
-w
1
d
i
; w
1
+w
2
+w
3
+w
4
=1
Where AP
s
is the average of link stability Ps over all
neighbors:
Ap
s
=
∑
,
; (j∈N (i))
AP
d
is the average dependency probability P
d
over
all neighbors:
Aps=
∑
Finally the node with the highest W
i
is chosen as a
cluster-head this time and all the neighbors of the
selected cluster-head are not permitted to participate
in the election process.
2.1.7 Dynamic Energy Efficient Clustering
Algorithm for MANETs
Dynamic energy efficient clustering algorithm
(DEECA) contains two important stages: cluster
formation and network maintenance (Safa, et.al.,
2008). Two defined energy thresholds are taken into
account in order to equilibrate the amount of load
among cluster-heads within the network. At the
beginning all nodes have an undecided status which
means they do not belong to any cluster. After that
each node broadcasts ‘HELLO’ messages during
‘BROADCAST-PERIOD’ interval. Then each node
calculates its own weight as follows:
W
v
= w
1
v+w
2
E
v
+w
3
M
v
; w
1
+w
2
+w
3
+w
4
=1
After the weight calculation process each node sends
‘HELLO’ messages including the amount of its
weight. Therefore, each node is aware of its
immediate neighbour’s weight. Lastly the node with
the minimum weight acts as a cluster-head and the
nodes in its immediate neighbourhood are its cluster-
members.
2.1.8 Improved Weight-based Clustering
Algorithm in MANETs
Improved weight-based clustering algorithm
(IWCA) has been proposed to overcome the problem
of high rate of re-affiliations that leads to an increase
in the network overhead (Zou, et.al., 2008). The
algorithm starts finding the neighbours of each node
and at the end calculates weight as follows:
w=w
1
M
v
+w
2
P
v
+w
3
D
v
+w
4
∆
v
; w
1
+w
2
+w
3
+w
4
=1
where D
v
is the distance of a node with its
neighbours, M
v
is the average speed of node v, ∆
v
is
the degree difference of node v and P
v
is the
cumulative time P which shows how long a node
acts as a cluster-head in a network. Finally each
node chooses the node with minimum weight as a
cluster-head and moreover the isolated nodes also
act as cluster-heads.
SENSORNETS2014-InternationalConferenceonSensorNetworks
44
2.1.9 Energy Efficient and Stable Weight
based Clustering for MANETs
Energy efficient and stable weight based clustering
algorithm (EE-SWBC) tries not to send any
additional weight messages and select the most
promising node as a cluster-head and decrease the
amount of general overhead within the network
(Bouk and Sasase, 2008). It uses Grey Decision
Method (GDM) in order to calculate the weights of
nodes. Firstly, each node sends a ‘Hello message’
which includes ID, status, σ1(u), Mt(u), Pt(u), D(u)
and coordinates. Each node calculates the following
parameters:
• Node Degree of node u [σ1(u)]
• Average Speed of node u [Mt(u)]
• Residual Battery Power of node u[Pt(u)]
• Average Distance of node u [D(u)]
EE-SWBC assumes the node degree and the
residual battery power parameters to be the positive
criteria and the average speed and distance
parameters to be the negative criteria. Finally, the
maximum combined weight of neighbour nodes is
calculated by multiplying the weight factors w
i
by
the relations coefficient matrix utilized in GDM.
2.1.10 Flexible Weighted Clustering
Algorithm based on Battery Power
for MANETs
Flexible weighted clustering algorithm (FWCA)
aims to make a network stable by decreasing the
number of clusters and an amount of overhead due
to forming clusters (Hussein, et.al., 2008). Moreover
it tries to prevent nodes with less battery power act
as cluster-heads. FWCA includes two stages:
clustering algorithm and clustering maintenance.
The moment clustering algorithm starts, each node
broadcasts a ‘beacon’ message to recognize its
neighbors. All the sensor nodes create a neighbor list
considering the received beacons. Then each node
calculates its weight amount as below:
w
i
= w
1
SP+w
2
LCC+w
3
BP
+ w
4
S
i
;
w
1
+w
2
+w
3
+w
4
=1
where SP is the spreading degree (meaning the
difference between cluster’s size (the threshold for
the cluster members) and the real number of
neighbours R(N)), LCC is the local clustering
coefficient (connectivity), BP is the remaining
battery power of the node and S
i
is the average speed
of the node i.
Finally a node with a minimum amount of
weight is selected as a cluster head. Clustering
maintenance is applied on the network in case of less
amount of battery power threshold and a node
separation from its cluster.
2.1.11 Enhanced Weighted Clustering
Algorithm for Mobile Networks
The objectives in enhanced weighted clustering
algorithm (EWCA) are achieving the minimum
number of affiliations and the general amount of
overhead during the formation process of clusters
and increasing the stability of clusters, system
performance and nodes’ life time through the ad hoc
network domain (Li, et.al., 2009). The moment the
clustering algorithm starts, each node calculates its
weight amount as following:
w
i
=w
1
Δ
i
+w
2
M
i
+w
3
D
i
+w
4
E
i
; w
1
+w
2
+w
3
+w
4
=1
where ∆
i
is the degree difference, D
i
is the sum of
the distances to all its neighbours, M
i
is mobility of
node i and E
i
is the consumed energy of a node.
Finally nodes with smaller weight are elected as
cluster-heads and the defined cluster-heads and
members are not allowed to participate in the
clustering elections. Moreover at the network
maintenance stage there is a feature of controlling
the battery power consumption of mobile sensor
nodes.
2.1.12 Maximal Weight Topology Discovery
in Ad Hoc Wireless Sensor Networks
This algorithm specifies two phases. The first one is
the ‘information exchange’ and the second one is the
‘cluster discovery’ (Fayyaz, et.al., 2010). The main
purpose of the algorithm is to minimize the number
of reconfigurations and the number of cluster-heads
within the network domain in order to achieve the
optimal topology for the network. After the neighbor
recognition step, each node calculates the following
parameters:
Ω
ϖ
= ω
1
Ε+ω
2
Μ +ω
3
Δ+ω
4
Πϖ+ω
5
Δρ+ω
6
Τ;
ω
1
+ω
2
+ω
3
+ω
4
+ω
5
+ω
6
=1
where E is the node energy, M is the node mobility,
Δ is the node degree, Π
ϖ
is the neighbouring node
positions, Δ
ρ
is the data rate and T is the target
revisit rate.
The node with the maximum amount of Ω is
selected as a cluster-head and following the second
phase (clustering discovery), it creates its own
cluster based on ‘color’ algorithm (Fayyaz, et.al.,
2010).
LifeTimeSensitiveWeightedClusteringonWirelessSensorNetworks
45
2.1.13 Efficient Cluster-head Election
Algorithm based on Maximum
Weight for MANET
Efficient cluster-head election algorithm (ECAM)
includes two stages of clustering and maintenance.
There are two parameters that are checked during
maintenance stage (Sivaprakasam and Gunavathi,
2011). The first one is the ‘mobility of a cluster’ and
the second one is the ‘cluster maintenance’. The
moment ECAM starts running, each node sends its
identification number to its neighbors in order to
build a neighbor's table. After that each node
calculates its weight as shown below:
w
n
=w
1
n+ w
2
S
n
+w
3
T(n)+w
4
T
C
+w
5
C
n
;
w
1
+w
2
+w
3
+w
4
=1
where n is the set of node’s neighbours, S is the sum
of the distances between a node and all its
neighbours, T(n) is the speed of a node and T
C
is the
cumulative time that a node acts as a cluster-head.
Finally the node with the maximum weight acts
as a cluster-head and sends a ‘CH-MSG’ to its
neighbours in order to build its cluster.
2.2 Weighted Clustering Algorithms
for WSNs
It is necessary to mention that since MANET and
WSN are relatively similar networks, some of the
above weighted clustering algorithms for MANET
are applicable to WSN as well.
2.2.1 Clustering Algorithm for Localization
in WSNs
Clustering algorithm for localization in wireless
sensor networks (CFL) aims at achieving the
minimum number of clusters with maximum number
of nodes inside in order to improve the general
performance of weighted clustering algorithm
(Zainalie and Yaghmaee, 2008). At the moment the
CFL algorithm starts by all nodes broadcasting the
‘Hello’ message through the network and building
their ‘neighbour table’ based on received messages,
which includes estimation of distances also. Then
each node calculates its weight as follows:
w
i
=aN
i
+bE
i
+c
1
/P
i
; (a+b+c≤1)
where E
i
is the remaining energy, N
i
is the number
of node’s neighbours, P
i
is the transmission power
and W
i
is the combined weight.
Lastly, the node with the maximum weight value
acts as a cluster-head and sends a ‘CH-msg’ to its
neighbours and the nodes that receive this message
change their states to cluster members. The
remaining nodes, which do not belong to any
clusters, change to cluster-heads.
2.2.2 Improved Weighted Clustering
Algorithm for Heterogeneous WSNs
Improved weighted clustering algorithm (IWCA)
attempts to increase the network life time and in
addition to forming clusters it includes network
maintenance. Network maintenance checks two
thresholds for energy amount of nodes, which
triggers the recalculation of the clustering algorithm
(Hong, 2011). Each node calculates w
v
as follows:
w
v
=w
1
v
+w
2
D
v
+w
3
M
v
+w
4
T
v
+w5C
v
;
w1+w
2
+w
3
+w
4
=1
where C
v
is the characteristic C of each node (C
v
=(C
* r
v
)/E
v
), C is a constant for amplification, r
v
is the
transmission rate, E
v
is the initial energy of a node,
D
v
is the distance of a node with its neighbours, ∆
v
is
the degree-difference, M
v
is the speed of a node and
T
v
is the cumulative time which shows how long a
node acts as a cluster-head in a network.
The node with minimum weight acts as a cluster-
head and makes its cluster.
2.2.3 Distributed Energy-Efficient
Hierarchical Clustering for WSNs
This algorithm utilizes two parameters – residual
energy and distance with neighbours – in order to
calculate the combined weight of each node
(Ding, et.al., 2005).
w
weight
(s) = (
∑
∈
,
)
where R defines the cluster range, d specifies the
distance from node s to the neighbouring node u,
E
residual
is the residual energy in node S, E
initial
is the
initial energy in node S which is the same for all the
nodes and N
α,c
is the set of the neighbors of the node
S. It is assumed that the number of neighboUring
nodes of a cluster is at most 6.
3 LIFE TIME SENSITIVE
WEIGHTED CLUSTERING
ON WSN (LTS-WCA)
Various characteristics of WSNs, such as mobility
heterogeneity, large scalability requirement and
power restrictions, are all considered in the proposed
SENSORNETS2014-InternationalConferenceonSensorNetworks
46
model. It is expected that during the lifetime of a
sensor network, the network may face several
problems, such as: (1) lack of energy in sensor nodes
that fail in their attempt to cover the environment
properly; (2) overloaded cluster-heads; (3) existence
of some isolated sensor nodes in the network; (4)
fast energy depletion rate used for both transmission
and processing purposes. Life-time sensitive
weighted clustering algorithm (LTS-WCA) is a fully
distributed algorithm, which is applicable for
heterogonous mobile wireless sensor networks. It
aims to solve the predefined problems included in
the reviewed weighted clustering techniques and
modifies these previous works efficiently in order to
apply them on then WSN domain. Although LTS-
WCA is designed for heterogonous WSNs, it can be
used on homogeneous WSNs, too. There are several
significant modifications on the original version,
which can be listed as follows:
• LTS-WCA uses local minima instead of global
minimum, which means each decision can be made
by a group of nodes in a local manner and there is
no need for a node to get aware of the other nodes’
decisions and specifications.
• There is a specific life time assigned to each
protocol packet of a node in terms of hop counts in
order to limit packet retransmissions.
• Sensor nodes communicate in a multi-hop fashion
both for inter- and intra-communications.
• Several additional parameters are included in the
clustering algorithm to be used to calculate node
weights and to find efficient cluster heads. The
additional parameters used are:
• Er: remaining energy of a node
• Tr: transmission range of a node
• S: size of a cluster which a node as a cluster head
can support
• dv: number of 1-hop neighbours of a node
At the exact moment when clustering timer is
triggered through the network, each mobile wireless
sensor node gets prepared to follow the steps below:
Step 1: each node recognizes the nodes in its
neighborhood.
Step 2: each node calculates its parameters as
follows:
S = (NK
2
T
r
2
π)/A
Where S is the ideal number of cluster members
in a cluster,
K is the number of hops that a node can support
inside of its cluster in a case it becomes a cluster
head,
N is the number of nodes that can receive
transmitted packets from a source node,
A is the area of the network,
T
r
is the transmission range of a node,
M
v
is the speed of a node,
Er is the amount of residual energy of a node,
d
v
is the number of 1-hop neighbors of a node
Weight of a node:
w=(w
1
T
r
+w
2
M
v
)/(w
3
d
v
+w
4
E
r
+w
5
S);
w
1
+w
2
=1, w
3
+w
4
+w
5
=1.
Step 3: Each node prepares its data structures
considering the above calculations and broadcasts it.
Step 4: Each node compares its weight using other
neighbors’ weights.
Step 5: Each node checks whether it has the smallest
weight.
• If a node has the least weight, it sends a ‘ch-msg’
including its ID and weight to all its neighbours
and changes its state as a cluster head. Moreover
after receiving each ‘join-req’ it starts to accept
nodes until the number of nodes within its cluster
doesn’t exceed the defined threshold.
• If a node does not have the least weight amount, it
checks whether it receives any ‘ch-msg’. If so it
sends a ‘join-req’ to selected cluster head and after
receiving acceptance from the cluster head it
changes its state as cluster member.
• Isolated nodes, which cannot join to any cluster,
change their state as cluster heads.
• At the end of the clustering algorithm each node
has a cluster head or cluster member state within
the defined clusters. It is worth noting that during
the exchange of information among sensor nodes,
each node checks whether the received data is new
or not. If it is new, it propagates it to its 1-hop
neighbors considering the packet’s life time field,
if it is not, it simply drops it. Moreover, each node
updates the packet life time field once in every run
of the clustering algorithm considering its
remaining energy.
• During the clustering process, in case a node has a
possibility to join different clusters, it checks the
number of hops it is away from the available
cluster heads and selects the least distance. In case
of equality, it checks the residual energy amount of
the cluster heads and chooses the highest one and
joins it.
4 IMPLEMENTATION,
EVALUATION OF LTS-WCA
In our tests, we assumed that there are mobile
wireless nodes in a 1000*1000 square. They are
LifeTimeSensitiveWeightedClusteringonWirelessSensorNetworks
47
categorized into three types of nodes with speeds of
7, 5 and 3 m/s. Node transmission ranges are 200,
150 and 100 meters. Initial energy of nodes are 20,
15 and 10 Joules.
It is worth mentioning that although LTS-WCA
was designed especially for heterogeneous WSNs, it
can be used for homogenous WSNs and it can also
be applied on MANET, if the density of the mobile
nodes within the network is not large. This is
believed to be its biggest advantage.
Table 1: LTS_WCA parameters.
Parameter Value
Transmission ran
g
e 100, 150,200
Area L -1000
Traffic type CBR
Tx ener
gy
0.036 Joules
Rx ener
gy
0.024 Joules
Initial energ
y
20, 15, 10 Joules
N
umber of nodes 50, 100, 200
Max packet in if
q
200 packets
w1,w2,w3,w4,w5 0.5,0.5,0.4,0.4,0.2
In order to compare the result of LTS-WCA with
WCA and WBACA, we applied the same MANET
environment (1000*1000 square) with same values
of speed for nodes (10m/s). The following LTS-
WCA plots are obtained as averages of 50
consecutive runs of the simulation, each starting
with a new randomly assigned node distribution.
The simulation results of CFL, WCA and
WBACA are directly borrowed from the respective
publications (Dhurandher, and Singh, 2005),
(Zainalie and Yaghmaee, 2008). The comparison
results of LTS-WCA performance with the existing
weighted clustering algorithms on MANET are
shown below:
Figure 1: Comparing WCA, WBACA and LTS-WCA in
terms of number of cluster heads and number of nodes.
Figure 1 shows the comparison of LTS-WCA with
two different Weighted Clustering Algorithms
(WCA and WBACA) by considering two
parameters: number of cluster heads and number of
nodes. As seen in the figure, by increasing the
number of nodes the number of clusters increases
until the number of nodes reaches 30. After this
point in both WCA and LTS-WCA the number of
cluster heads decreases. The reason behind this is the
fact that when the node density is small, each node
takes a cluster head role in the environment.
However, by increasing the number of nodes further,
the possibility of nodes belonging to a cluster
increases and this decreases the number of cluster
heads, which in return decreases the energy
consumption to transmit data to sink. As figure 1
shows the performance of LTS-WCA is much better
than that of WCA (Chatterjee, et.al., 2000) and it is
also better than WBACA (Dhurandher and Singh,
2005) when the number of nodes gets larger.
Figure 2: Comparing WCA, WBACA and LTS-WCA in
terms of number of cluster heads and transmission range.
Figure 2 presents results considering two
parameters, namely the number of cluster heads and
transmission range. By increasing the node
transmission range within the network, the number
of cluster heads decreases. As can be seen in the
figure the performance of LTS-WCA in decreasing
the number of clusters and therefore transmission
energy consumption is much better than that of the
other two algorithms.
Figure 3: Comparing CFL and LTS-WCA in terms of
number of clusters and transmission range.
SENSORNETS2014-InternationalConferenceonSensorNetworks
48
Figure 3 shows the comparison between LTS-WCA
and CFL (Zainalie and Yaghmaee, 2008) algorithm
on WSN. By increasing the transmission range, the
number of clusters within the network decreases and
this leads to the decrease of the amount of energy
needed to transmit data from the source to a sink. As
the plot represents LTS-WCA has a considerably
better performance in comparison with CFL
(Zainalie and Yaghmaee, 2008) algorithm.
Figure 4: Comparing CFL and LTS-WCA in terms of
number of nodes and time needed for clustering.
Figure 4 illustrates the change in the time needed for
clustering vs the number of nodes in WSN. As seen
in the figure, LTS-WCA is quite successful to
decrease the clustering time in comparison with CFL
(Zainalie and Yaghmaee, 2008).
Figure 5: LTS-WCA life time performance in function of
number of nodes (homogenous network).
Figures 5, 6 and 7 present the performance of LTS-
WCA in a homogenous WSN to show how energy
efficient it is in terms of network life time. As was
mentioned earlier, the moment the first node dies is
considered as a network life time in LTS-WCA for
simplicity. In Figure 5 by increasing the number of
nodes, the network life time increases gradually.
Figure 6 shows the considerable increase the
network life time if initial energy of nodes within the
environment is increased. Figure 7 presents the
decrease of the network life time of WSN while
Figure 6: LTS-WCA life time performance in function of
energy of nodes (homogenous network).
Figure 7: LTS-WCA life time performance in function of
transmission range of nodes (homogenous network).
node transmission range increases. The reason
behind this is the fact that by increasing the
transmission range of nodes, the size of clusters
increases, too. Finally cluster heads become
overloaded and they start to lose their energy much
faster. As a result, the network life time also
decreases.
Figure 8 represents the performance of LTS-
WCA on a heterogeneous WSN. By increasing the
number of nodes, the network life time also
increases.
Figure 8: LTS-WCA life time performance in function of
transmission range of nodes (heterogeneous network).
LifeTimeSensitiveWeightedClusteringonWirelessSensorNetworks
49
5 CONCLUSIONS
In the present work, we studied the vast amount of
research done in the field of weighted clustering
algorithm for two different network types, namely
mobile ad hoc networks and wireless sensor
networks. We examined their main motivations
concentrating mostly on the energy efficiency and
network overhead. Since in WSN life time is
considered to be a vital issue, researchers mostly
take it as a significant parameter to be improved
within their proposed clustering algorithms (Hong,
2011), (Ding, et.al., 2005). However, along with life
time, the issue of energy efficiency plays an equally
important role. Therefore, it became the second
emphasized area of the present study.
LTS-WCA is a weighted clustering algorithm
which is designed in this work specifically for
distributed heterogeneous wireless sensor networks.
The algorithm includes two phases: clustering and
network maintenance. It employs five key
parameters in order to choose the best cluster head
through the network environment. These parameters
are transmission range of a node (Tr), minimum
distance to a neighbour cluster’s cluster head
(Dmin), speed of a node (Mv), degree of a node
(dv), remaining energy of a node (Er) and number of
nodes that a node can handle inside of its cluster in
case it becomes a cluster head (S). After choosing
cluster heads and grouping the network nodes in
clusters, the maintenance phase starts. In the
maintenance phase, three parameters are checked
periodically within the network environment: the
residual energy of mobile wireless sensor nodes, the
mobility of sensor nodes and the amount of load put
on a cluster head. In the present paper, maintenance
part is not implemented since it is proposed as an
enhancement.
The main purpose of LTS-WCA is to overcome
the problems which a wireless sensor network faces.
LTS-WCA increases network life time by
decreasing the number of clusters within the network
environment. Decreasing the number of clusters
leads to less usage of transmission power and finally
keeping the nodes alive for much longer within the
network environment. Moreover decreasing the time
needed to group the network into clusters also in
increasing the network life time and LTS-WCA acts
successfully to increase the overall network life time
on a Wireless Sensor Network.
One of the advantages of LTS-WCA is that it is
applicable to MANET and homogenous networks
also. As a result, as shown in our simulation study, it
has a much better performance in terms of energy
efficiency in comparison with existing weighted
clustering algorithms on both MANET and WSN
such as WCA (Chatterjee et.al., 2000), WBACA
(Dhurandher and Singh, 2005) and CFL (Zainalie
and Yaghmaee, 2008).
In terms of increasing energy efficiency and
network life time, there is still a lot of work to be
done. There are several parameters such as
‘transmission range’, ‘number of neighbours’,
‘degree differences’, and ‘remaining battery power’
and ‘distances with neighbours’, which play
significant roles in the process of selecting cluster-
heads and clustering formations, and these
parameters should be thoroughly worked out and
developed further. There is still lack of research
done in this area and scant written materials
covering the aforementioned issues.
Further improvements on weighted clustering
algorithms should concentrate on clustering
formation and cluster-heads election for creating a
more stable network structure with less energy cost.
In order to maintain the network, efficient thresholds
should be used in terms of energy amount of nodes,
mobility of nodes and cluster size; this should be
done in order to decrease the number of re-
affiliations as well as the number of re-clustering the
network domain. Replacing some parameters for
calculating the combined weight with some other
parameters may help to keep the amount of load on
the cluster-head balance and decrease the general
overhead within the network.
REFERENCES
Bouk, S. H., and Sasase, I., (2008) ‘Energy efficient and
stable weight based clustering for mobile ad hoc
networks’, 2nd International Conference on Signal
Processing and Communication Systems (ICSPCS’08),
pp.1-10.
Burrell, J., Brooke, T., and Beckwith, R., (2004)
‘Vineyard computing: Sensor networks in agricultural
production’, IEEE Pervasive Computing, vol.3, no.1,
pp. 38-45.
Bricard-Vieu, V., and Nasser, N., (2006) ‘A weighted
clustering algorithm using local cluster-heads election
for QoS in MANETs’, IEEE Global
Telecommunications Conference, (GLOBECOM'06),
pp.1-5.
Chatterjee, M., Sas, S. K., and Turgut, D., (2000) ‘An on-
demand weighted clustering algorithm (WCA) for ad
hoc networks’, IEEE Global Telecommunications
Conference (GLOBECOM'00), vol.3, pp. 1697-1701.
Dechene, D. J., El Jardali, A., Luccini, M. and Sauer, A.,
(2008) ‘Algorithms for node clustering in wireless
sensor networks: A survey’, IEEE Magazine, pp. 295-300.
SENSORNETS2014-InternationalConferenceonSensorNetworks
50
Dhurandher, S. K., and Singh, G. V., (2005) ‘Weight
based adaptive clustering in wireless ad hoc networks’,
IEEE Int. Conf. on Personal Wireless
Communications (ICPWC’05), pp. 95-100.
Ding, P., Holliday, J., and Celik, A., (2005) ‘Distributed
energy-efficient hierarchical clustering for wireless
sensor networks’, First IEEE Int. Conf. on Distributed
Computing in Sensor Systems Proceeding
(DCOSS'05), pp. 322-339.
Fayyaz, Y., Nasim, M., and Javed, M.Y., (2010) ‘Maximal
weight topology discovery in ad hoc wireless sensor
networks’, IEEE 10th Int. Conf. on Computer and
Information Technology (CIT’10), pp.715-722.
Hong, T. P., (2011) ‘An improved weighted clustering
algorithm for determination of application nodes in
heterogeneous sensor networks’, J. of Information
Hiding and Multimedia Signal Processing, vol. 2,
Number 2, pp.173-184.
Hussein, A. H., Abu Salem, A. O., and Yousef, S., (2008)
‘A flexible weighted clustering algorithm based on
battery power for mobile ad hoc networks’, IEEE Int.
Symp. on Industrial Electronics (ISIE’08). pp. 2102-
2107.
Hwang, Y. C., Jeong, Y. S., Lee, S. H., Song, J. Y., and
Kim, Y. I., (2007) ‘Advanced efficiency and stability
combined weight based distributed clustering
algorithm in MANET’, Future Generation
Communication and Networking (FGCN’07), vol.2,
pp.478-483.
Jindal, V., Verma, A. K., and Bawa, S., (2011) ‘How the
two ad hoc networks can be different: MANET &
WSNs’, Int. J. of Comp. Science & Technology, Vol.
2, Issue 4, pp. 122-126.
Li, N., Zhang, N., Das, S. K., and Thuraisingham, B.,
(2009) ‘Privacy preservation in wireless sensor
networks: a state-of-the-art survey’, Ad Hoc Networks
7, pp. 1501–1514.
Li, C., Wang, Y., Huang, F., Yang, D., (2009) ‘A novel
enhanced weighted clustering algorithm for mobile
networks’, 5th Int. Conf. on Wireless
Communications, Networking and Mobile Computing
(WiCom'09), pp.1-4.
MANET vs WSN. Available from: <http://
www.scribd.com/doc/50634760/MANET-vs-WSN>.
(2 December 2012).
Safa, H., Mirza, O., and Artail, H., (2008) ‘A dynamic
energy efficient clustering algorithm for MANETs’,
IEEE Int. Conf. on Wireless and Mobile Computing,
Networking and Communications (WIMOB'08), pp.51-
56.
Sivaprakasam, P., and Gunavathi, R., (2011) ‘An efficient
clusterhead election algorithm based on maximum
weight for MANET’, 3
rd
Int. Conf. on Advanced
Computing (ICoAC’11), pp.315-320.
Wang, Y. X., and Bao, F. S., (2007) ‘An entropy-based
weighted clustering algorithm and its optimization for
ad hoc networks’, 3
rd
IEEE Int. Conf. on Wireless and
Mobile Computing, Networking and Communications
(WiMOB’07), pp.56.
Wang, Y., Chen, H., Yang, X., and Zhang, D., (2007)
‘WACHM: Weight based adaptive clustering for large
scale heterogeneous MANET’, Int. Symp. On
Communications and Information Technologies
(ISCIT'07), pp.936-941.
Zainalie, S., and Yaghmaee, M. H., (2008) ‘CFL: A
clustering algorithm for localization in wireless sensor
networks’, Int. Symp. on Telecommunications
(IST’08), pp. 435-439.
Zou, L., Zhang, Q., and Liu, J., (2008) ‘An improved
weight-based clustering algorithm in MANETs’, 4th
Int. Conf. on Wireless Communications, Networking
and Mobile Computing (WiCOM'08), pp.1-4.
LifeTimeSensitiveWeightedClusteringonWirelessSensorNetworks
51
