With recent and continue advances in sensor technology, electronics and micro
electro-mechanical system designs have assisted in the development of relatively
inexpensive, small in size, low power sensor nodes. Sensor nodes are incorporated
with sensing, processing and wireless communication (He
et al., 2006). These are used to acquire data, process and communicate
to the other sensors within the networks usually, through radio frequency channel
(Rozyyev et al., 2011). Sensor nodes in most
cases are immobile and they are more densely deployed to monitor particular
area of interest than mobile ad-hoc networks. One of the advantages of wireless
sensor networks is their ability to operate unattended in harsh environments
where it may be difficult or dangerous for human being to reach (Sohrabi
et al., 2000).
Sensor networks have a wide range of applications. Some of the application
areas are home automation, in which sensor nodes and actuators are inserted
into home appliances such as electric bulbs, refrigerators, micro-wave ovens.
This makes it possible for end users to control these devices remotely. Environmental
monitoring applications, sensor networks can be used to monitor changes in air,
water and soil. Healthcare applications, they can be used to administer drugs
in the hospitals, diagnose patients for diseases remotely, monitor both the
medical staff and patients inside the hospitals. Other application areas include
building security, earth movement prediction, weather and climate analysis and
prediction and so on (Akyildiz et al., 2002).
Sensor nodes networks are powered by batteries which often deployed in remote
areas, rough physical environments or some unreachable areas. It is expected
that these batteries lasted for years before they can be replaced (Wang
et al., 2007; Wang et al., 2011b).
For example, in a battle field scenario, soldiers may not have time to change
or recharge the batteries of their wireless devices and running out of batteries
means a loss of all of their communication capacity (Yu
et al., 2009). Therefore, it is necessary to minimize energy consumption
of wireless sensor in order to increase network lifetime.
Energy efficiency is of primary importance in WSNs (Wang
et al., 2011a). However, sensing, data processing and data communication
are the main energy consumption in which data communication is a major source
of energy consumption (Pottie and Kaiser, 2000). For
instance, the energy used to transmit 1 kb of data by a radio communication
to a distance of 100 m, the same amount of energy can be used by a 100 MHz processor
to process 300000 kb of data in one second (Xin et al.,
2008). In addition, if all data sensed by sensor nodes in WSNs are transmitted
to the base station directly, the data will be too enormous and large amount
of energy will be consumed during transmission (Lu et
For this reason, we need methods for combing data into high-quality information
at the sensors or intermediate nodes which can reduce the number of data transmitted
to the base station resulting in conservation of energy and good bandwidth utilization
(Guo et al., 2010; Liu et
al., 2010; Sabari and Duraiswamy, 2010).
In order to minimize the energy consumption of WSNs, a uniformly distributed cluster heads algorithms for WSNs have been proposed. In recent time, many clustering algorithms have been proposed with different protocols by different researchers, there still need to look for other techniques in which energy can be optimized in WSNs.
Some traditional clustering algorithms for wireless ad-hoc networks have been
extensively discussed by Amis et al. (2000),
Baker and Ephremides (1981) and Hong
et al. (1999). However, these clustering algorithms are not suitable
for sensor networks because in ad-hoc networks, the primary concern is quality
of service (QoS) while energy efficiency is the secondary (Chen
et al., 2008). While in sensor networks energy optimization and scalability
are the primary concern for extending network lifetime.
However, energy efficient algorithm using Low Energy Adaptive Clustering Hierarchy
(LEACH) was proposed by Heinzelman et al. (2002a).
Other algorithms developed thereafter were based on this algorithm. The operation
of LEACH is divided into rounds, each round begins with a set-up phase when
the clusters are organized and cluster heads are determined. Follow by steady
state phase where data are transmitted from cluster heads to the base station.
In order to determine the Cluster Heads (CHs), LEACH uses randomization technique
based on probability (Heinzelman et al., 2002b).
The cluster heads broadcast their new status to all sensors in the networks.
Other nodes determine the cluster to join based on the received signal strength
from these CHs. Each sensor node informs the appropriate CH that it will be
a member of the cluster and the node clusters are organized.
During the steady phase, the sensor nodes begin to sense and transmit data
to the CHs using Time Division Multiple Access (TDMA). Cluster heads collect
data from sensor nodes, aggregate and send it to the base station for processing
(Bandyopadhyay and Coyle, 2003).
Considering a single round of LEACH, a stochastic CH selection will not automatically
lead to minimum energy consumption during the steady phase for data transfer
of a given set of sensor nodes. Although, LEACH clustering terminates in a finite
number of iteration but does not guarantee good CHs distribution. CHs may be
chosen from one part of the network (Heinzelman et al.,
Finally, LEACH protocol is not suitable to networks deployed in large regions where we have thousands of sensor nodes.
Power-Efficient Gathering in Sensor Information System (PEGASIS) protocol was
proposed by Lindsey and Raghavendra (2002). It is an
improvement over LEACH. It allows only one CH to transmit to its local neighbor
in the data aggregation phase instead of a node sending sensed data directly
to its CH as in the case of LEACH.
The main idea of PEGASIS is to form a single chain among sensor nodes using Greedy algorithm. Each node in the chain acts as cluster head which receives data from a neighbor node, fuse it and send it to the next neighbor node closer to the base station. The algorithm make sure that only one node transmits data from source to the base station in any given transmission time frame. This ensures that only relevant data gets to the base station while all redundant data might have been removed down the chain. Energy efficiency is achieved with this approach, since each node acts as CH in the chain and responsible for data transmission to the base station. However, if a node dies within the chain, a new node will be selected based on calculation to avoid transmission failure. Selection of a new node as a result of dead of a node can bring significant overhead especially in a large network. PEGASIS approach avoid the clustering overhead of LEACH protocol but each sensor node needs to know the status of its neighbour so that it will have the knowledge where to send the data to.
The main objective of this study is to reduce energy consumption of sensor nodes within the network by:
||Developing an algorithm that will uniformly distribute cluster
heads within the clusters so that non-cluster heads will transmit to the
cluster heads with minimum distance
||Developing an algorithm that will reduce communication distance
among cluster heads in the hierarchy
BASIC RADIO ENERGY MODEL
High amount of energy is consumed during communication (Stemm
and Katz, 1997; Xin et al., 2008). Therefore,
it is necessary to minimize number of communications of sensor nodes. Energy
consumption for communication depends on various factors such as the transmit
power level, hardware profile, packets size and distance (Zhou
et al., 2008). Energy consumption of sensor node is due to data transmission
Fig. 1 is the radio energy consumption model as stated by
Heinzelman et al. (2002a).
The energy consumed in transmitting one message of size k-bit over a transmission
distance d is stated in Eq. 1 as:
|| Radio energy consumption model
||Length of the message
||Transmission distance between transmitter and receiver
||Path-loss component (2 = n = 4)
Also, the energy consumed in the same message by the receiver is given by:
Hence, the total energy consumption when sensor receives a message and forwards it over to a distance d is given by:
THE PROPOSE ALGORITHMS
This algorithm uniformly distributes Cluster Heads (CHs) in each cluster so that energy consumption by each node when transmitting data to the CHs will be minimized.
The following assumptions are made about the Clustering algorithms and to simplify the analysis of the algorithm:
||At the initial stage (first round) all the sensor nodes in
the network have the same energy and equal amount of energy is consumed
||The base station has all the information about location of
||All sensor nodes and base station are stationary after deployment
||Each sensor node has the probability (P) to become CH in the
first round and after 1/P rounds; a node which has been CH is eligible to
||Every node determines its cluster to which it will belong
||CHs perform data reception, aggregation and transmission to
the base station
||Total number of 100 sensor nodes is deployed in the network
Low Energy Adaptive Clustering Hierarchy (LEACH) algorithm: We are going
to consider LEACH algorithm clusters formation and cluster heads selection since
other algorithms were developed based on this algorithm (Chang
and Kuo, 2006). Then our propose algorithms will be presented. LEACH algorithm
is divided into rounds.
Round one (Setup Phase): At the Setup Phase clusters are organized and
cluster heads are determined.
||The location information of all the sensor nodes in the network
are collected by the base station and partitions it into different groups
called clusters (assuming into 10 clusters).
Each cluster below contains these sensor nodes in the set:
||Cluster1 = (S5, S13, S25,.....,S81)
||Cluster10 = (S2, S45, S73,.....,S98)
where, S denotes sensor node:
||At the current round, all the nodes have the same maximum
energy. Each node has probability P to become Cluster Head (CH) in each
cluster (Heinzelman et al., 2002b). Hence,
CHs are chosen randomly from each cluster.
||After CHs have been elected, each CH node broadcasts an advertisement
message to the rest of the non-cluster head nodes in the cluster using Carrier
Sense Multiple Access (CSMA) MAC Protocol.
||Based on the received signal strength of the advertisement from each CH,
each non-cluster head node determines which clusters it wants belong to,
by choosing CH that requires minimum communication energy.
||Each non-cluster node sends back message to the CHs about the cluster
it wants to belong using CSMA MAC Protocol.
||TDMA is set-up for each node to transmit by the CH and to turn-off radio
components of each node at all time except during transmission to avoid
data collision and to save energy.
||The CHs receive data from each sensor node perform signal processing and
send it to the base station where it will finally process and access by
IMPROVEMENT OVER LEACH ALGORITHM
New cluster head selection method: A new cluster head is chosen if the existing residual energy of the cluster heads in the current round is below the set threshold value.
If the following conditions hold:
||That sensor node has not become cluster head for the past
(1/P) 1 rounds
||That the residual energy of a node is higher than the average
energy of all the nodes in that clustering
Then the probability of a node becoming cluster head is given as:
where, Erem is the remaining energy in node (I), Eavg is the average energy of all the nodes in a cluster g is the expected number of cluster head in each round N is the number of nodes in each cluster.
The essence of equation (1) is to make sure that nodes with
morwe energy have stronger probability of becoming cluster heads than nodes
with less energy.
In order for the CHs to distribute uniformly within the clusters, we introduced these rules.
||Every node must be k-hop from one CH
||Every node that is k+1 from CH must turn-off its radio transmission
when others nodes are transmitting
These two rules absolutely help to achieve uniform distribution of CHs in each cluster, so that each node will transmit its sensed data to the CH with the minimum energy because the transmission distance has been reduced.
Inter-cluster communication: In order to the achieve energy efficiency, only cluster heads need to transmit sensed data by sensor nodes in to each cluster to the next cluster heads and finally to the base station. This reduces the amount of data received by the base station for processing, hence prolong the network lifetime in WSNs.
Algorithm for hierarchical clustering: The general procedure of the hierarchical clustering with 3 layers from bottom-up fashion is now described. This can also be extended to M layers.
Layer 1 is the lowest layer and layer 3 is the highest in the hierarchy as shown in Fig. 2 below.
|| 3-Layer hierarchical clustering
At the lowest layer, layer one elects itself cluster heads (CHs), follow by layer 2 and layer 3.
Cluster heads election:
||A node at layer 1 elects itself to be a CH based on stochastic
probability and announces its decision to all other nodes in the networks
through broadcasting using CSMA MAC protocol. Each node that receives the
message with minimum signal strength will join the cluster
||Among the clusters in layer 1, CHs elect themselves at layer 2 CHs based
on method used in layer 1 and broadcast their decisions. CHs at layer 3
will also be elected using the same method
||After the formation of the hierarchical clustering and CHs have been selected
for the clusters, sensor nodes at layer 1 begin to transmit their sensed
data to the CHs. The CHs in layer 1 are able to communicate with each other
to aggregate the data, removing the redundant and send it to CHs in layer
2 and from layer 2 to layer 3
||Finally, CH in layer 3 will further compress the data and transmit them
to the base station where it will be accessible to the user to perform final
processing on it to give useful information for decision making
Significant amount of energy will be saved with this algorithm, because instead of each CH to transmit directly to the base station which is at a far distance. CHs will now communicate with each other via multi hops to aggregate data and the last CH(s) nearest to the base station will do final data transmission to the base station.
SIMULATION RESULTS AND ANALYSIS
In this section, we evaluate the performances of our propose algorithms through
simulation. We simulated our proposed algorithm, Uniformly Distributed Clustering
Algorithms (UDCA) and LEACH protocol in order to see the level of energy optimization
that our protocol can achieve. 100 sensor nodes were randomly distributed over
the sensor field of 100x100 m2 as shown in the Fig.
3 below and the base station is located far away from the sensor field.
Each node started with an initial energy of 0.5J. Other parameters used for
the test can be found by Heinzelman et al. (2002a).
Cluster head probability P used is 5% (0.05) which means about 5 sensor nodes in each round become cluster heads and fuse collected data to 5% of its initial size.
The main concern in this test is to prolong network lifetime. There is need to know number of Alive nodes, that is the time when the first node dies and time the last node dies during network runtime (number of rounds).
The performance of our algorithm, UDCA and LEACH protocol were examined in the simulation test based on number of sensor nodes that were alive after certain number of rounds.
From Fig. 4 above, it shows that time taken for the first node to die and time taken for the last node to die in UDCA is greater than LEACH protocol which means more number of nodes are Alive in UDCA than in LEACH after each round. This is achieved because sensor nodes in each cluster transmit their sensed data to the cluster heads with minimum energy due to short distance between them and cluster heads were uniformly distributed.
|| 100 sensor nodes randomly distributed
|| The number of Alive nodes over the simulation time (No. of
|| Total number of data transmitted to the base station after
However, Fig. 5 shows the number of data sent to the base station through the cluster heads in hierarchical form.
The graph shows number of data sent by cluster heads to the base station is more in UDCA than LEACH in each round. The reason is that there are more Alive nodes and cluster heads in UDCA than LEACH to transmit data to the next cluster heads and finally to the base station. UDCA, unlike LEACH protocol its selection of cluster heads in a round does not base on random number generator.
In present study, energy optimization for WSNs using uniform distributed clustering algorithms called UDCA has been presented. UDCA partitioned the sensor field into different clusters, each cluster nodes transmits its data to the cluster heads with short distance. Nodes with maximum residual energy are elected as new cluster heads based on the algorithms for uniform energy distribution among all the nodes and aggregated data is transmitted by cluster heads to the base station. Simulation results showed that better performances of UDCA are achieved than LEACH protocol because the technique significantly minimizes total energy consumption among cluster member nodes due to short range communication. In UDCA, energy consumption is more uniformly distributed among all nodes and extends the lifetime of sensor nodes in the network.