The Scalability and Stability Analysis of KLEACH Routing Protocol in Wireless Sensor Networks

Published Online April 2016 in MECS

Wireless Sensor Networks (WSNs) have emerged as a key for numerous applications. The WSNs are commonly used in various military and civil applications [1]. Due to the hostile deployment of WSNs, it isn’t practicable to substitute the batteries of hundreds and thousands of nodes [2]. Considering this deployment in difficult areas knowing as inaccessible environment, the network must manage independently without any human intervention. In addition, sensor nodes known serious restrictions of resources like limitation bandwidth, limitation of processing capabilities, limitation in memory storage and limitation in energy, etc … [1], [2]. Thereafter, the existing sensor node design which has those several limitations incites the task of sensing and reporting to be an enormous discusses about performance efficiency problems. Therefore, the performances of WSNs like energy and scalability has been attracting the interest of many researchers and there are many methods to make this performance more efficient [3]. One of these methods is the clustering procedure [4]. In fact, the action that divides the network into many groups of nodes is named Clustering. The utility of this combination of nodes is manifested in a variety of contexts. In general, the members’ nodes (MN) in a cluster are closers, by a measure of distance; a representative node called Cluster Head (CH) allows the attachment of all their MN. Inside each of these clusters, the master node (CH) is elected to collect the data from sensor nodes. All member nodes MNs transmit sensed data to their CH, while the CH aggregate data received and forward to the Base Station (BS) [4]. Indeed, the node CH handles, as a manager, acts such as data aggregation and routing. In fact, the amount of data after the data aggregation by CH node is reduced. The Figure 1 represents WSNs where MNs send the data to their own CHs. These last send in their turn the data to the BS.

Fig.1. Clustering in Wireless Sensor Network

However, the routing of data is possible without the use of clusters, but the need for a complete routing table of each node is necessary, which does not stretch across a large number of sensor nodes. Hence, the usefulness of clustering is vital to insure an efficient routing [5–9]. In another hand, the nodes distribution and density have an important influence on network scalability [10]. In fact, the scalability is a significant issue of an efficient routing protocol for WSN. A good routing protocol has to be scalable to the changes in the network topology and size.

This work evaluate the performance analysis of the scalability in WSN for two hierarchical routing protocols (LEACH and KLEACH) in terms of throughput (packets received by the base station), total energy consumed, total number of nodes alive, when the network is subject to various sizes. Otherwise, the network stability is also studied.

This paper is organized as follows: section 2 presents the related work. Section 3 explores the scalability analysis of WSN. In section 4, the description of KLEACH is developed followed by section 5 in which the simulation results and discussions are presented before concluding the paper in section 6.

• II.    Related Works

Heinzelman and al. [11] launch a hierarchical clustering algorithm for sensor networks, called Low Energy Adaptive Clustering Hierarchy (LEACH) for homogeneous WSNs. LEACH is a cluster-based protocol, which takes account of distributed cluster formation. LEACH selects at random a small number of sensor nodes as cluster heads (CHs) and alternates this role to uniformly distribute the energy stack among the sensors in the network by epochs [12].

Many significant works, focused on hierarchical routing protocols based on clustering which has improved the network scalability. LEACH protocol is analyzed in terms of energy, throughput and lifetime [13]. Researches [8], [13], [14] explain that scalability of LEACH is influenced by the randomized rotation of CHs which degrade the performance of this protocol.

Considerable works have been examined in literature with view to scalability [3], [10], [15], [16]. In [15] and [16], authors exploit a simulation to test the energy and throughput.

In the paper [17], the authors analyze the performance and presented issues in WSNs. Purposely for node energy and the network lifetime, they suggest an energy efficient routing algorithm based on self-adaptive clustering of CH. It enhances energy efficiency, balances energy consumption of sensor nodes, and improves scalability and network lifetime.

• III.    Scalability Analysis of Wsn

The scalability is the capability of hierarchical routing protocols to preserve a performance efficiency of WSN by increasing node density [16]. Thus, to determinate the scalability in WSN, there is numerous parameters to be taken in consideration like as (number of nodes, node density, node deployment, etc.) [3].

On the other hand and in order to evaluate the scalability of the routing protocols, there are many metrics to be analyzed such as network lifetime, throughput, energy consumption, etc [10], [16].

In the objective to investigate the scalability, Figure 2 present some metrics considered in WSN performance.

Fig.2. Performance Metrics of a Sensor Network

The set of these metrics can be described briefly as follows [2], [18]:

• A.    Network lifetime

There are multiplicity definitions of network lifetime for the basis that it depends on the network requirements. The authors in [19] resume some of the important used definitions as follow:

• •    The round which the first node died (FND);

• •    The round which a certain fraction β of total number of sensor nodes died;

• •    The round which the last node died (LND);

• B.    Network throughput

The network throughput determines the number of packets transmitted at the base station.

• C.    Success rate

The totality of packets received by the BS compared as the totality of packets transmitted from the sensor nodes .

• D.    Energy consumption

It is the total of consumed energy of sensor nodes in the network. Figure 3 illustrates the energy model of k bits transmitted over the distance d as in [9].

Fig.3. Energy Model in WSN

The equations are used to compute transmission and receiving energy for k bit message are shown below:

(k,d)= k£ , + ^£ d^ elec       js kE , + ^£ d4 elec       amp d< d> do do (1) (k) = RX v 7      elec (2) To aggregate data of k bits length, the energy consumption was calculated as: k EDA.

• •    E TX , E RX : are respectively energy transmission and

energy reception of k bits toward distance d.

• •    E_elec is the electronic energy required for coding, modulation, filtering, etc.

• •    E_DA is the energy required for data aggregation.

• •    s _fs, s amp is the amplification energy.

Here, the equation used to compute average total energy (Eavg) per round is expressed as:

Total energy consumption of the 1^st node died Number of rounds before the 1^st node died

• IV.    Description of Protocol Kleach

• A.    LEACH Algorithm

Commonly, there are two elementary strategies of node deployment; deterministic and random. The deterministic way is unfeasible in applications like monitoring environment and other military applications. The random deployment approach is more possible in most of applications [12].

To prolong the lifetime of WSN by increasing energy efficiency has been one of the main deal in WSN. The lifetime network is strongly dependent on the battery life and the requirement for improving energy efficiency that take routing protocols into consideration has been a foremost research domain in WSN. In fact, to reduce the cost of energy consumption caused by overloading of communication among sensor nodes, WSN use efficient routing protocols [13].

Homogenous and heterogeneous clustering is two kinds of networks. Homogenous means that nodes of WSNs have a same energy. The basic ones are LEACH (Low Energy Adaptive Clustering Hierarchy) [12].

A routing protocol LEACH [11] presents a clustering that uses randomized rotation of CH of a cluster to uniformly distribute energy between the sensors in the network. In addition, CH realizes data aggregation to compress the information. Concerning the protocol LEACH, it runs with numerous rounds. In beginning, the clusters are formed in a set-up phase followed by a steady-state phase [11, 12].

• a)    Setup Phase

The first step is the election of nodes to become CHs. This selection process guarantees that CH function rotates surrounded by nodes to share our energy consumption regularly transversely all nodes.

The CH selection algorithm is defined by using a random alternative for CH selection. The decision of the choice of a node to become CH is generated by a random number between 0 and 1 which is comparing with a fraction T (n) calculated as follows:

P

T ( n )= ^

1- P ( r mod¹^)

1°

i f n e G otherwise

• •   T(n): is designed to ensure with high probability

that a pre-determined fraction of nodes

• •    P: is percentage that the cluster head in all nodes

• •    r: denote number of round be haven completed

• •    G: is a set of nodes be consisted of nodes which

did not be cluster head in the last 1/P round.

After selecting the cluster head, the cluster head began broadcasting this information to inform ordinary node in the network for the purpose to become a MN.

• b)    Steady State Phase

For the period of this step, MN nodes periodically gather sensor data and transmit it to CH. The total steadystate operation is divided into frames which are additional split up into slots of constant duration. MN nodes send collected data to their respective CH at most once per frame during their allocated transmission.

• B.    KLEACH algorithm

Figures 4 and 5 present the comprehensive description of protocol KLEACH and its K-means algorithm for clustering [20–22].

Fig.4. Flow chart of K-means Algorithm

The K-means algorithm is employed to determine the centroids in the order to form the clusters. In fact, the algorithm K-means is based principally on the Euclidian distance determination. Consequently, CH selection depends on residual energies of nodes. Accordingly, the central nodes gather the information concerning the nodes id, coordinates and residual energy of all nodes and accumulate this information in a list of the central nodes.

After receiving this information from all nodes, the performing of the clustering algorithm (K-means) is done [21], [22]. Concerning the protocol LEACH, it runs with numerous rounds. In beginning, the clusters are formed in a set-up phase followed by a steady-state phase when data are transferred from the nodes to the cluster head and on to the BS [13]. Whereas, the protocol KLEACH uses K-means clustering in the first phase which sensor nodes are allowed to select CH and forms clusters as shown in Figure 6. In the second phase, KLEACH adopts the same behavior as that a steady-state phase of LEACH.

Fig.5. Flow Chart of KLEACH Protocol

50  24

0     10    20    30    40    50    60    70    80    90    100

Fig.6. K-mean Clustering with the Parameters (K=5, N=100)

• V.    Simulation Results

In this paper, we use MATLAB simulator to evaluate the routing protocols scalability for WSNs. Some assumptions and parameters are described as follows [10]:

• A.    Network settings

The simulation variables are set up as follows:

• •    Sensor area: 100m x 100m;

• •    Number of sensor nodes (N): 100 to 1000 nodes uniformly deployed;

• •    Initial energy of sensor nodes (E0): 0.5 (J);

• •    The coordinate of base station: (50m, 50m);

Our simulation model uses the parameters as shown in Table 1.

Table 1. Simulation Parameters

Parameters	Value
elec	50nJ/bit
ε fs	10 pJ/bit/m2
ε amp	0,0013 pJ/bit/m4
E DA	5 nJ/bit
k	4000 Bits

In our simulation environment, we assume that all nodes contain data to send and sensor nodes are not in mobility, and they have the same initial energy. Data packets can be correctly transmitted by nodes and received by the base station. Furthermore, initially base station makes available address localization for each sensor node. The optimal number of cluster heads is 5% of number of sensor nodes as in [1], [12].

• B.    Performance analysis of KLEACH

At the beginning, the performance analysis for routing protocols KLEACH and LEACH has been analyzed on the basis of following constraints as shown in figures 7, 8 and 9:

• •    Lifetime of sensor nodes.

• •    Energy consumption by sensor nodes.

• •    Number of packets received by BS .

Figure 7 shows the network lifetime of KLEACH and LEACH. Based on these results, we conclude that KLEACH lifetime is prolonged compared to LEACH. In the figure 8, we observe the energy consumption of sensor nodes in the network. The total initial energy of the network is 50 J which decreases linearly up to 1800 rounds. The dissipated energy is achieved in 2408 rounds. The results shown in figure 9 illustrate the throughput evolution depending on the rounds number of both of protocol.

We can see from the Figure 9 that with the protocol KLEACH, the packets received by the BS are considerably superior to LEACH. This improvement can be justified by the fact that the KLEACH network lifetime is more prolonged.

Also, we introduce the comparison of both algorithms based on proportion of stable region. The proportion of stability means the ratio of the stability period of KLEACH by the stable period of LEACH. The protocol KLEACH has a higher stability region regarding to LEACH. In addition, the results of this last figure confirm the choice of clustering algortithm K-means. In fact, KLEACH perform better than LEACH by 35% in terms of stability.

Fig.7. A comparison Lifetime between KLEACH and LEACH

Fig.8. Residual Energy of KLEACH and LEACH

Fig.9. Packets Received Over Rounds of KLEACH and LEACH

• C.    Scalabilty analysis of KLEACH

In this section, the performance analysis of the scalability for routing protocols LEACH and KLEACH has been analyzed on the basis of following metrics:

• •    Stability Period: is the period (or rounds) up to which all nodes are alive. This period lies between first round and the round at which the first node dies.

• •    Instability period: is the period between the first dead node and last dead node. This period should be small as possible.

• •    Energy consumption by sensor nodes.

• •    Number of packets received by base station .

• 1)    Network lifetime

In order to compare the network lifetime of the both routing protocols, we consider two factors: FND and LND as illustrated in Figure 10.

From Figure 10, we observe that the protocol KLEACH overpass LEACH concerning the FND generally. KLEACH have a descending evolution which reaches an asymptotic value 1285 rounds when a number of nodes increase from 100 to 400. For this same interval of number nodes, the protocol LEACH has a different behavior which raises until a maximal value 965 rounds. Thereafter, the FND of LEACH has a fluctuate evolution which stabilize at an asymptotic value as 940 rounds. Based on these findings, we can interpret the behavior of KLEACH by the fact that the cluster heads are sorted in an increasing manner with respect to their distance from the Centroid Virtual (CV) of each cluster.

(a)

(b)

Fig.10. FND (a) LND (b) Comparison of KLEACH and LEACH

• 2)    Network stability

In this section, we present the comparison of both algorithms based on proportion of stable and unstable region as shown in Figure 11.

• •    Proportion of stability: ratio of the stable period of KLEACH by the stable period of LEACH.

• •    Proportion of instability: ratio of the unstable period of KLEACH by the unstable period of LEACH.

Numberof nodes

Fig.11. Proportion of Stable and Unstable Region of KLEACH over LEACH

Table 2 presents the set of proportion values of improvement stable and declination unstable period by KLEACH over LEACH.

While calculating instability period, we are considering only those rounds in which some data is transferred to the BS. It is clear from the Table 2 that the stable region of KLEACH proves better stable region as compare to LEACH, but it shows a remarkable declination in unstable region over LEACH.

Table 2. Stability and instability region of KLEACH over LEACH

N	Stable period			Unstable period
	LEACH	KLEACH	Prop. stable (%)	LEACH	KLEACH	Prop. unstabl e(%)
100	883	1316	49,04	392	1159	195,66
200	914	1289	41,03	482	1195	147,93
300	945	1289	36,40	490	1198	144,49
400	967	1286	32,99	492	1201	144,11
500	962	1286	33,68	507	1202	137,08
600	945	1285	35,98	554	1203	117,15
700	952	1285	34,98	544	1203	121,14
800	947	1285	35,69	564	1203	113,30
900	949	1285	35,41	575	1203	109,22
1000	946	1285	35,84	570	1203	111,05

As compared to LEACH, KLEACH has an improvement over the stability period as shown in the Table 2. The detailed results obtained with various numbers of nodes from 100 to 1000 have been shown in Table 2.

• 3)    Network throughput

The results of throughput evolution depending on the number of nodes are taken in the round at which the FND and the LND for each protocol.

We can see from the Figure 12 that with the protocol KLEACH, the packets received by the BS are considerably superior to LEACH. This improvement can be justified by the fact that the KLEACH network lifetime is more prolonged.

(a)

(b)

Fig.12. Number of received packets for KLEACH and LEACH in FND round (a) and LND round (b)

• 4)    Network energy consumption

The results of energy consumption evolution depending on the number of nodes are taken in the round at which the FND and the LND for protocol LEACH.

About the energy consumed, KLEACH reduces this energy not only for the stable region but also for the unstable region as shown in Figure 13. The ratio gain of energy saving is respectively about approximately 36% and 30%.

Fig.13. Ratio Gain of Energy Saving (%) for KLEACH and LEACH in FND round and LND round

We summarize the obtained results, the performance metrics that are compared are illustrated in Table 3 as follows:

Table 3. Performance Metrics Comparison

Metrics analyzed	Improved performances over LEACH
Number of packets received in FND	Ameliorated by 37%
Average packets received ratio	Increased by 62%
Network life	Prolonged by 35%
Average energy consumption	Decreased by 36%

• VI. Conclusions

In this paper, we focus on the scalability and the stability analysis of KLEACH protocol for WSN. Several tests were carried out using different network parameters. The protocol KLEACH is compared to a classical algorithm named LEACH using MATLAB simulator. The performance of routing protocol is measured to determine the efficient scalability. The results show that KLEACH presents considerable reductions of energy consumption and extend network lifetime remarkably. After evaluating several metrics, the simulation results show that KLEACH have the capability to improve the packet ratio sending by the sensor nodes to the base station. In addition, KLEACH provides a satisfactory stability network. Generally, it can be concluded that the performance analysis demonstrates clearly that KLEACH it is an efficient and scalable protocol with respect to network size compared to LEACH. As perspective of this work, it is proposed to extend this study to investigate other metrics like latency, delivery packets, and success rate. In addition, it would be interesting to examine these different metrics with other clustering algorithms and make in evidence a comparative study of the various methods of clustering combined with traditional routing protocols.