The Scalability and Stability Analysis of KLEACH Routing Protocol in Wireless Sensor Networks
Автор: Abdelkader Bourzek, Abderrahmane Hajraoui, Saad Chakkor, Mostafa Baghouri
Журнал: International Journal of Computer Network and Information Security(IJCNIS) @ijcnis
Статья в выпуске: 4 vol.8, 2016 года.
Бесплатный доступ
The scalability and stability in wireless sensor networks (WSNs) are considering as an important issue due to the large numbers of nodes and consequently their node density and deployment. While the network size increase, the need of scalable and efficient routing protocols is indispensable. Moreover, sensor nodes have to be alive to guarantee the network operation for the period which the first node died doesn't appear. This period, named network stability region, is ameliorated by many techniques. In fact, the balancing energy consumption and clustering method are among those techniques. In this paper, we present the scalability and stability analysis of the routing protocol LEACH based on K-means clustering algorithm (KLEACH). Accordingly, the simulation results of the performance metrics verify the efficiency and the scalability of KLEACH protocol compared to LEACH.
Scalability, stability, K-means, clustering, node density, routing protocol, balancing of energy consumption
Короткий адрес: https://sciup.org/15011515
IDR: 15011515
Текст научной статьи 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:
-
• E TX , E RX : are respectively energy transmission and
energy reception of k bits toward distance d.
-
• Eelec is the electronic energy required for coding, modulation, filtering, etc.
-
• EDA 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 1st node died Number of rounds before the 1st 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 mod1^)
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.
Список литературы The Scalability and Stability Analysis of KLEACH Routing Protocol in Wireless Sensor Networks
- I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "Wireless sensor networks: a survey," Computer networks, Vol. 38, No. 4, pp. 393–422, 2002.
- A. Hać, "Wireless sensor network designs," Chichester, West Sussex, Englandd; Hoboken, NJ: J. Wiley, 2003.
- M. S. V. Dhage, A. N. Thakre, and S. W. Mohod, "A Review on Scalability Issue in Wireless Sensor Networks," International Journal of Innovative Research in Advanced Engineering (IJIRAE), Vol. 1, pp. 463–466, November 2014.
- S. P. Singh and S. C. Sharma, "A Survey on Cluster Based Routing Protocols in Wireless Sensor Networks,"Procedia Computer Science, Vol. 45, pp. 687–695, 2015.
- D. Bhattacharyya, T. Kim, and S. Pal, "A Comparative Study of Wireless Sensor Networks and Their Routing Protocols," Sensors, Vol. 10, No. 12, pp. 10506–10523, Nov. 2010.
- K. Akkaya and M. Younis, "A survey on routing protocols for wireless sensor networks," Ad Hoc Networks, Vol. 3, No. 3, pp. 325–349, May 2005.
- F. Kiani, E. Amiri, M. Zamani, T. Khodadadi, and A. Abdul Manaf, "Efficient Intelligent Energy Routing Protocol in Wireless Sensor Networks," International Journal of Distributed Sensor Networks, Vol. 2015, pp. 1–13, 2015.
- J.-S. Leu, T.-H. Chiang, M.-C. Yu, and K.-W. Su, "Energy Efficient Clustering Scheme for Prolonging the Lifetime of Wireless Sensor Network With Isolated Nodes," IEEE Communications Letters, Vol. 19, No. 2, pp. 259–262, Feb. 2015.
- N. A. Pantazis, S. A. Nikolidakis, and D. D. Vergados, "Energy-Efficient Routing Protocols in Wireless Sensor Networks: A Survey," IEEE Communications Surveys & Tutorials, Vol. 15, No. 2, pp. 551–591, 2013.
- C. Li, H. Zhang, B. Hao, and J. Li, "A Survey on Routing Protocols for Large-Scale Wireless Sensor Networks," Sensors, Vol. 11, No. 12, pp. 3498–3526, Mar. 2011.
- W. B. Heinzelman, "Application-specific protocol architectures for wireless networks," Massachusetts Institute of Technology, 2000.
- W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, "Energy-efficient communication protocol for wireless microsensor networks," in System sciences, Proceedings of the 33rd annual Hawaii international conference, 2000.
- R. Patel, S. Pariyani, and V. Ukani, "Energy and throughput analysis of hierarchical routing protocol (LEACH) for wireless sensor network," International Journal of Computer Applications, Vol. 20, No. 4, 2011.
- B. Mostafa, C. Saad, and H. Abderrahmane, "Fuzzy logic approach to improving Stable Election Protocol for clustered heterogeneous wireless sensor networks," Journal of Theoretical and Applied Information Technology, Vol. 53, No. 3, 2013.
- M. Hadjila and M. Fehman, "A comparative study of the wireless sensor networks routing protocols scalability," International Journal of Distributed and Parallel Systems (IJDPS), Vol. 2, No. 4, pp. 26–33, 2011.
- L. K. Alazzawi, A. M. Elkateeb, A. Ramesh, and W. Aljuhar, "Scalability Analysis for Wireless Sensor Networks Routing Protocols" 22nd International Conference on Advanced Information Networking and Applications, 2008 IEEE, pp. 139–144, 2008.
- S. Raghuwanshi and A. Mishra, "A self-adaptive clustering based algorithm for increased Energy-efficiency and Scalability in Wireless Sensor Networks," in Vehicular Technology Conference, 2003. VTC 2003-Fall. 2003 IEEE 58th, Vol. 5, pp. 2921–2925, 2003.
- W. M. McEneaney and W. H. Fleming, Eds., "Stochastic analysis, control, optimization and applications," a volume in honor of W. H. Fleming. Boston: Birkhäuser, 1999.
- I. Dietrich and F. Dressler, "On the lifetime of wireless sensor networks," ACM Transactions on Sensor Networks, Vol. 5, No. 1, pp. 1–39, Feb. 2009.
- Y. Gong, G. Chen, and L. Tan, "A balanced serial k-means based clustering protocol for wireless sensor networks," in Wireless Communications, Networking and Mobile Computing, 2008. WiCOM'08. 4th International Conference, pp. 1–6, 2008.
- S. Sirsikar and K. Wankhede, "Comparison of Clustering Algorithms to Design New Clustering Approach," Procedia Computer Science, Vol. 49, pp. 147–154, 2015.
- W. Peng and D. J. Edwards, "K-means like minimum mean distance algorithm for wireless sensor networks," in Computer Engineering and Technology (ICCET), 2010 2nd International Conference, Vol. 1, pp. V1–120, 2010.