92


Chain of Clusters for Improving Network Lifetime of
                   Sensor Network
                                             Rashmi L. Jain1, Sachin Jain2
           1. Computer Science and Engineering Department, Rajiv Gandhi College of Engineering & Research, Nagpur, India.
                                                E-mail: rashmilalitjain@gmail.com
                  2. Information Technology Department, Yeshwantrao Chavan College of Engineering, Nagpur, India.
                                             E-mail: sachinjain98440@rediffmail.com


   Abstract: In wireless sensor network increasing life time             a cross over distance) then communication energy required is
of sensor node and there by network is the main motive                   less and is in proportion to d2, where as if the distance is
for development of a protocol for the sensor network.                    more than d 0 then more energy is consumed and is in
LEACH (Low Energy Adaptive Clustering Hierarchy) is                      proportion to d4. So if long distance communication is done
an energy-efficient hierarchical protocol that balances the              frequently node battery will drain quickly. Efforts are being
energy consumption, saves the node energy as compared                    taken to reduce this communication power and boost the life
to flat communication protocols and hence prolongs the                   of the nodes in the network so that they can serve the purpose
lifetime of the network. Here, we planned a new                          for longer time. Such energy efficient wireless sensor
hierarchical cluster based protocol for varied sensor                    network applications are highly demanded, for different
networks. Instead of selecting the cluster head randomly,                scenarios.
we include chain forming concept of PEGASIS (Power                       The forthcoming paper is divided in following sections. Part
Efficient Gathering in Sensor Information System). In                    2 will discuss about LEACH protocol and PEGASIS
our work we consider heterogeneous nodes. Unlike                         protocols. In section 3, discussion about proposed protocol
LEACH, proposed protocol uses the selection criteria for                 and radio energy model is done. Section 4 will tell about
Cluster-Head depending on the residual energy of the                     results of proposed method in comparison with LEACH and
nodes and relative distance of cluster heads. A chain of                 PEGASIS protocol. Lastly in section 5conclusion and future
Cluster Head will be formed using chain formation                        scope of proposed method are discussed.
technique      of     PEGASIS       protocol.    Successful
implementation of data aggregation has reduced the                                        II.     RELATED WORKS
energy-consumption.                                                         Protocols have been developed for communication purpose
   Keywords: Energy efficiency, chain formation, LEACH                   in WSN since its inception. Earlier Direct Transmission,
protocol, PEGASIS protocol, Heterogeneous wireless                       Minimum Energy Transmission (MTE) protocols were used,
network, Data aggregation.                                               which are considered as flat routing. W.R.Heinzelman then
                                                                         added a milestone to these protocols with design of LEACH
                     I.    INTRODUCTION                                  protocol [1]. In the cluster based approach given by LEACH,
    Wireless sensor networks (WSNs), are generally used for              considerable energy saving was achieved when the base
monitoring some phenomena or certain parameters. They are                station is distant as compared to the sensor nodes
generally formed with ample number of small, resource                    deployment. Lot of work is done on this protocol and various
constrained, sensing nodes which are spread either with some             enhancements are available. Chandrashekharan provided
criteria or randomly in a geographical area of interest.                 another concept of chain based communication, which
Sensing data and communicating them to the data collecting               outperformed as compared to LEACH. But certain limitations
sink are major operations taking place. But major component              were there. In this section we discuss about these protocols in
for success of the wireless sensor network applications is the           brief.
way of communication among the sensor nodes. This is                     A. The LEACH protocol
because more energy of the energy restricted nodes gets
                                                                            LEACH protocol is proposed by W.R. Heinzelman [1].
drained for communication in comparison with energy
                                                                         LEACH i.e. Low Energy Adaptive Cluster Hierarchy, is
consumed in computation or processing the information
                                                                         hierarchical clustering protocol. It is self organized protocol
collected. So for designing any wireless sensing application
                                                                         and nodes are divided in clusters for sharing information to
one has to keep in mind the critical parameter of energy
                                                                         base station via cluster head (CH). The idea of hierarchical
utilization in the network. Delivery of data in a specific time
                                                                         routing approach provided in LEACH is an inspiration, an
slot is again very essential for the successful task completion
                                                                         anchor for development of many other hierarchical protocols,
of nodes that’s why routing parameters are essential. Routing
                                                                         although some of them are having novice idea and are
path of the data in WSN determines how data hops from node
                                                                         developed independently [2]. This protocol assumes that all
to node in order to reach the destination when the destination
                                                                         the nodes have equal initial energy, E 0 , they are
is not directly reachable from the source node. If source and
                                                                         homogeneous in nature and they are randomly placed in the
destination nodes are at a shorter distance (d<d 0 , where d 0 is



                          ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic
                                                                  93

sensor field. It includes two operations performed in each                       III.   THE PROPOSED PROTOCOL
round of working, namely setup and steady state operation.
                                                                          The proposed protocol uses the advantages of the clustering
Clusters of nodes are formed in first phase- setup, where, a
                                                                       mechanism of improved LEACH protocol and chain formation
part of nodes, P, which is predetermined, elect themselves as          technique of PEGASIS protocol. The protocol results in improved
CHs as follows.                                                        life of sensor node which ultimately increases lifetime of
Here, a random number r, between 0 and 1is selected by the             network. In this section we will discuss the details of our
sensor node. T(n), a threshold value, is considered as given in        protocol. Unlike LEACH, proposed protocol uses
below mentioned Eq.1. If r is less than T(n), then this node           heterogeneous nodes in the network; also cluster heads are
declares itself as CH for present round. The threshold value           selected on basis of residual energy of nodes. In basic
depends upon the expected percentage P, for number of CH               LEACH, selection of CH is depends upon the probability
in present round. Only that set of nodes can become a CH               function but this criteria is useful only if energy of nodes in
that has not yet become CH in the previous (1/P) rounds.               the network is uniform. Second most important issue in
Such nodes which are involved in cluster head selection [14],          LEACH is that, there is no certainty about whether the CHs
are denoted by set G. This T(n) is calculated by:                      are distributed uniformly in network or not. This problem of
                                                                       LEACH is resolved by forming clusters according to the
            T(n) = P/(1-P(r mod (1/P)), if n ϵ G            (1)        distances of nodes along the x-axis.
                                                                          Secondly, in PEGASIS all nodes have probability to
   In the current epoch T(n) value is zero for the nodes who           become leader node for a particular round. Therefore there
have been the cluster heads in subsequent rounds. Each CH              are chances that node selected as leader node for that round
elected transmits an announcement message to other nodes in            may not have sufficient amount of energy to survive in the
the network about their role as the new cluster-heads. Other           network for longer time. If the leader node dies then no
Non-CH nodes select the nearest CH and join that respective            communication can be done with the base station and results
cluster as a member. CHs create and broadcast a TDMA plan              in breakage of network. Also there are chances that selected
for their associate nodes for data transmission so that                leader node is located far away from a base station.
collisions are avoided.                                                Therefore, time and energy dissipation for sending network
   During the steady state phase actual work of the sensor             data to base station is high. This issue of PEGASIS protocol
nodes begins. They sense and transmit the data to the cluster-         is resolved by selecting a leader node which will have
heads. The cluster head receives the data from members and             maximum amount of energy and which is located nearer to
aggregates it to reduce the size, before sending it to the sink        the base station. Only this last leader node will be
and then transmits this data. This data compaction will reduce         communicating with the base station.
the communication energy needed during transmission.
   In the next round again the setup and steady state                  A. Working of protocol
operations are repeated.                                                  The heterogeneous nodes are deployed randomly in the
                                                                       sensor field and groups are formed by arranging sensor nodes
B. The PEGASIS protocol                                                according to x-axis at some fixed point in the network area.
   PEGASIS i.e. Power-Efficient Gathering in Sensor                    This process leads to the formation of clusters in network
Information Systems (PEGASIS) protocol is proposed by S.               along x- direction. After creating clusters, energy of each
Lindsey and C. S. Raghavendra [2]. This is chain based                 sensor node of cluster is calculated and two nodes with
protocol in which each node in network will form a chain and           highest energy are selected. First node with the highest
can only communicate with their adjacent node. Each node               energy is the CH node and second highest energy node is
finds its closest node with the help of signal strength                stand by CH. If first cluster head dies then sensor node with
received.                                                              second highest energy i.e. stand by CH will act as CH. Once
In this, main communicating node, the leader, is chosen                this clustering is over, formation of chain between CHs of
based on energy remained with the nodes. Leader will be                neighbouring clusters is done. All the sensor nodes of cluster
responsible for gathering data from each node in chain and             will send their information to the respective CH of the
then sending that data to BS. PEGASIS does not form cluster            cluster. Then selected CH will perform aggregation of this
and uses only leader node for communicating with sink. This            information and forward this to the CH of neighbouring
will reduce overhead of cluster head selection as well as the          cluster. CH of neighbouring cluster will add this received
bandwidth needed in messaging.                                         information with its own cluster’s information and then again
                                                                       it will carry forward this whole information to the next
   But drawback with LEACH and PEGASIS is that, In                     neighbouring CH of cluster. This process will continue till
LEACH there is no certainty about cluster head selection               information of every cluster will reaches to the CH of last
since CH is selected randomly. In PEGASIS, it may be                   cluster of the network. Now, this CH will aggregate this
possible that leader that is responsible for sending network           whole information in small but meaningful message and send
information to BS, will be located at some point which far             it to the base station. CH of last cluster is selected so that
from BS. So, leader may consume more energy for sending                distance between this CH and base station is minimum.
information from longer distance to BS. These two major                Following Fig.1 shows the entire process of clustering and
drawbacks of LEACH and PEGASIS are overcome in our                     chain formation between CHs.
proposed method.




                         ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic
                                                                          94




                                                   Fig. 1. Cluster and chain formation of nodes.
B. Radio and energy model                                                      Therefore the energies of the nodes will always be different,
                                                                               keeping the nodes heterogeneous. Table I below lists the
   In the proposed method the nodes are communicating to                       simulation parameters considered.
their neighbouring nodes, so long distance communications
are avoided. Radio models for a distance less than cross-over                           TABLE I: NS2 SIMULATION PARAMETERS
distance and for distance greater than cross-over distance are
                                                                                            Parameter                    Value
projected by W.R. Heinzelman [1], that are used here.
In our protocol d2 path loss model is utilized for data                                 Network Size (x, y)            1300*1000
transmission, since the nodes communicate the data to their                             Transmission Power               2.0W
CH in close vicinity. Transmission and reception costs for                               Receiving Power                 1.0W
message with k bits over a distance d are as given in Eq. 2
and Eq. 3.                                                                                  Ideal Power                   1.0W
Cost for Transmission:                                                                      No. of nodes                  40
                                         2
   ET x (k,d)   =   E elec *k + E amp *k*d ,       if d < d0        (2)                      Packet size               1000bits
                                                                                        Base Station location         1400*1100
Cost for Reception:                                                               Fig. 2 shows the placement of nodes in the network area.
                      ER x (k)   =     E elec *k                    (3)        Clusters are formed according to x-distances of the nodes.
                                                                               Node 40 is the sink node. From each cluster two nodes will
                                                                               be selected as cluster head having maximum residual energy
   In the equations, d is path-loss exponent depending on
                                                                               among all nodes in cluster. As shown in Fig. 2, node contains
distance between source and destination. Here it has been
                                                                               in square and hexagon is the cluster heads of respective
taken of order d2 for experimentation. Again k, the number of
                                                                               cluster. Base station node is shown in green color circle
bits transmitted and received should be less because high
                                                                               contain in red square box.
amount of energy is spent in transmission and reception of
data in comparison data processing. Long distance
communication may take place only between the leaders and
sink node if it is placed beyond the cross-over limit in the
network. The network scenario used is given in the next
section.

C. Network parameters
  The proposed protocol has been simulated in one of the
most popular and appropriate Network simulator i.e. NS2,
version ns2.35. In the scenario considered there are total 40
nodes in network which are placed randomly in the area 1300
X 1000 meters. Each node has different initial energy as the
nodes are of heterogeneous type. Initial energies of the nodes
are also assigned randomly, indicating values between 0 and
1000. Energy dissipation during data communication is
dependent on distance between the source and sink node.                                         Fig. 2. Deployment of nodes.




                          ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic
                                                                95

  Energy of each node is compared and node with highest              over the functionality of cluster head when present CH goes
energy is chosen as the cluster head. Second highest energy          down. `Fig .3 below shows selection of CH depending upon
node is selected as deputy cluster head. This node will take         the energy level of the nodes in a cluster.




                                                  Fig. 3. Cluster Head selection.

           IV.     RESULTS AND DISCUSSION                            respectively. From the graph it is clear that energy
                                                                     consumption in our proposed protocol is less as comapre to
  The network consisting of 40 heterogeneous nodes,                  LEACH and PEGASIS.This result is obtain by using same
deployed in an area of 1300 X 1000 and a base station                parameters for all three protocols. In case of LEACH direct
located at 1400 X 1100, is considered for simulation purpose.        communication to base station by each CH consumes more
7 rounds are simulated here. Three protocols are considered          energy and cluster formation also consumes overhead energy.
here namely LEACH, PEGASIS and ours P-LEACH. The                     In PEGASIS leader node may be at a longer distance from
comparative results are discussed in this section. We                BS, that consumes more energy. In case of proposed method,
considered energy consumption per round, mean delay per              energy requirement for communication between nodes is less
round and packet delivery ratio as the parameters for                because CH selected will have maximun residual energy and
comparison.                                                          distance between adjacent CH nodes is very less as compare
A. Energy consumption                                                to other protocols.
   Energy consumption of the nodes depends on two tasks,             B.   Packet delivery ratio (PDR)
i.e. communication and computation. Major energy is spent             Following Fig. 5 shows comparison of proposed method,
during communication, as its an energy intensive task. As            LEACH protocol and PEGASIS protocol.
compared to communication computation energy requirement
is very very small. In this section, we will discuss about
energy consumption in proposed protocol in comparison with
LEACH and PEGASIS protocol.




                                                                              Fig. 5. Packet Delivery Ratio in communication.
                                                                        In above graph,yellow line indicates the PDR in proposed
                                                                     method. Red and blue line indicates PDR in simpleleach and
                                                                     PEGASIS protocol respectivly. Graph clearly indicates that
         Fig. 4. Energy consumption in proposed method.
                                                                     in proposed method packet delivery ratio is more as compaire
   In the above Fig. 4 energy consumption in proposed P-             to other two protocol. In this we have taken the interval 0.3-
LEACH protocol, LEACH and PEGASIS is calculated. As                  0.5sec to send packet from one node to anothet node. PDR in
shown in figure, yellow line indicates energy consumption in         proposed protocol is coming out to be in the range of 80-100
proposed method, red and blue line indicates energy                  which is good enough for network to become efficient
consumption in LEACH and PEGASIS protocols                           network.



                         ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic
                                                                  96

                                                                       communication is breaks that network will not be useful. In
                                                                       proposed method no. of dead is very less in whole network
                                                                       communication as compare to LEACH and PEGASIS. This
                                                                       result will increase the network’s lifetime and efficiency of
                                                                       network.
                                                                                                REFERENCES
                                                                       [1]. A.P. Chandrakasan, H.Balakrishnan and W.R Heinzelman,
                                                                             “Energy efficient communication protocol for wireless
                                                                             microsensor networks,” 33rd Hawaii Int.Conf. Sys.Sci., Jan
                                                                             2000.
                                                                       [2]. Lindsey, Stephanie, and Cauligi S. Raghavendra. "PEGASIS:
                                                                             Powerefficient gathering in sensor information systems." In
                  Fig. 6. Delay for packet sending.                          Aerospace conference proceedings, 2002. IEEE, vol.3, pp. 3-
                                                                             1125.
   Above Fig: 6 shows delay in the network. Yellow line                [3]. Al-Karaki, Jamal N., and Ahmed E. Kamal. "Routing
indicates delay in proposed method where as red and blue                     techniques in wireless sensor networks: a survey." Wireless
lines indicate delay in LEACH and PEGASIS protocol                           communications, IEEE 11, no.6 (2004):6-28.
repectivly. As shown in figure, in proposed method dealy is            [4]. Abdul Razaque, Musbah Abdulgader,Chaitrali Joshi, Fathi
very less and it is in the range of 0.001msec to 0.002msec                   Amsaad, Mrunal Chauhan.” P-Leach : Energy efficient routing
                                                                             Protocol” IEEE,2016
where as in case of LEACH and PEGASIS this delay vary in
                                                                       [5]. Alekha       Kumar       Mishra,    Rukhan       Rahman,Rahul
the range of 0.003msec to 0.0075msec. This result shows that                 Bharadwaj,Rohit Sharma.”An Enhancement of PEGASIS
delay in proposed method is very less in comparison with                     protocol with Improved Network Lifetime for WSN”, IEEE
other two protcols which proves that network established                     2015
using this protocol will be a very efficient network. Above            [6]. Agrawal, Palak, and P. R. Pardhi. "Routing Protocols For
discussed observations show that poposed method gives                        WSN." International Journal of Computer Science And
better result in terms of energy, packet delivery ratio and                  Applications 8, no. 1 (2015).
dealy. Also number of dead nodes in proposed method is less            [7]. Chenmin Li, Guoping Tan, Jingyu Wu, Zhen Zhang , Lizhong
as compared to LEACH and PEGASIS protocol.                                   Xu “Analyzing Cluster-head Selection Mechanisms and
                                                                             Improving the LEACH ” 2011 IEEE.
                   V.      CONCLUSIONS                                 [8]. Naveen Kumar, Jasbir Kaur, “Improved LEACH Proto col
                                                                             for Wireless Sensor Networks.” In Proceedings of 7 th
   The proposed method Improved P-LEACH protocol has                         International Conference on Wireless Communications
been proven to produce a better result as compared to prior                  Networking and Mobile Computing, Wuhan, China, 2011.
protocols such as LEACH and PEGASIS in WSN.                            [9]. Rashmi Jain, Manali Kshirsagar “Energy Saving in
Following are the key points which prove that proposed                       Heterogeneous Wireless Sensor Networks”. International
method is better as compare to LEACH and PEGASIS                             Journal of Scientific & Engineering Research, Volume 4, Issue
protocol.                                                                    8, August-2013 .
   Minimum energy consumption: In this protocol, energy                [10].      Santar Pal Singh, S.C.Sharma “ A Survey on Cluster
                                                                             Based Routing Protocol In Wireless Sensor Network” .
required for communication between nodes is very less which                  International    Conference     on    Advanced      Computing
results in improving network lifetime and network stability.                 Technologies and Applications (ICACTA-2015).
   Less PDR: Packet delivery ratio is one of measure of                [11]. Padmavati, T.C. Aseri, “Performance Analysis of Cluster based
judging network efficiency in WSN .In proposed method                        Routing Protocols in Heterogeneous Wireless Sensor
PDR is communing out to be 97.77% .Which means that                          Network”, International Journal of Computer Applications
there is very less packet drop while node communicates with                  (0975 – 8887) Volume 83 – No.16, December 2013.
each other. This results shows that there is less congestion in        [12]. Zhezhuang Xu, Chengnian Long, Cailian Chen, Xinping Guan
network which results in improving network efficiency.                       “Hybrid Clustering and Routing Strategy with Low Overhead
   Less Delay: In WSN, the network which has minimum                         for Wireless Sensor Networks”. IEEE ICC 2010.
                                                                       [13]. Rashmi Jain, Manali Kshirsagar, Latesh Malik “Analysis of
delay that network will consider as more efficient network.
                                                                             Setup Energy of LEACH Protocol for Wireless Sensor
Because, it takes less time to send packet from source to                    Networks”. International Journal of Scientific and Engineering
destination. In proposed protocol, delay is near about                       Research, June, 2016, Volume 7, Issue 5, May-2016 ISSN-
0.009sec, which is less as compare to other two protocols.                   2229-5518.
This shows that node takes minimum time to send packet                 [14]. Rashmi Jain, Manali Kshirsagar, Latesh Malik, “Heteroleach
from source to destination. This results in fast                             Protocol for Improvement of Stable Operation of Wireless
communication between nodes and minimum packet drop.                         Sensor Networks”. IOSR Journal of Computer Engineering
Due to this network lifetime get increase.                                   (IOSR-JCE) e-ISSN: 2278-0661, p-ISSN: 2278-8727, Vol
   Number of Dead Nodes: Dead nodes are responsible for                      18,Issue 2.
breaking network communication and once the




                         ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic