Journal of Computer and Communications
Vol.06 No.11(2018), Article ID:88330,11 pages
10.4236/jcc.2018.611001

Optimized Algorithm for Clustering Routing for Wireless Sensor Networks

Tieyuan Chang*, Weina Liu, Yan Zhang

College of Electronic and Information Engineering, Hebei University, Baoding, China

Copyright © 2018 by authors and Scientific Research Publishing Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

Received: October 8, 2018; Accepted: November 4, 2018; Published: November 7, 2018

ABSTRACT

LEACH protocol randomly selects cluster head nodes in a cyclic manner. It may cause network to be unstable, if the low energy node is elected as the cluster head. If the size of cluster is too large or too small, it will affect the survival time of the network. To address this issue, an improved solution was proposed. Firstly, the scheme considered the average and standard deviation of the nodes’ residual energy and the distance between the node and the base station, then considered the distance between the node and the cluster head and the energy of the cluster head to optimize the cluster head selection and clustering. The performance analysis results showed this scheme could reduce premature deaths of the cluster heads and too high energy consumption of some clusters. Thus, the proposed algorithm could prompt the stability and prolong the lifetime of the network.

Keywords:

Wireless Sensor Network (WSN), LEACH Routing Protocol, Optimize Clustering, Residual Energy, Stability, Network Lifetime

1. Introduction

Wireless sensor network (WSN) is a new generation sensor network. The representative discussion related to it appeared as early as 1999. With the development of science and technology, some experts predict that the development and wide application of WSN will bring great influence and impetus to people’s social life and industrial transformation [1] . WSN is a kind of wireless communication network composed of a large number of sensor nodes without infrastructure. It integrates sensor technology, embedded technology, distributed information processing technology and wireless communication technology. It senses and collects environmental information (such as temperature, humidity, noise, light intensity, etc.) of the node deployment area, then processes the data to remove redundancy based on the ability to obtain detailed and accurate information, and eventually transmits the data to the observer over the wireless network [2] . The development of wireless sensor network technology has experienced three stages: intelligent sensor phase, wireless intelligent sensor phase and wireless sensor network phase [3] . For the future of wireless sensor network technology, its development prospects are more optimistic; in environmental monitoring, emergency relief, smart home, medical care, industrial production control and commercial and other fields will have a wide range of applications [4] .

Different from traditional networks, WSN network has its own characteristics, so the routing protocols and algorithms used in traditional networks cannot meet the requirements of WSN applications. In WSN, sensor nodes form a data transmission path by cooperating with each other and send the data from the source node to the destination node. Data transmission cannot be separated from routing protocol; routing protocol is the basis of networking. Because sensor nodes have little energy and distribute randomly, long-distance transmission of data consumes a lot of energy. Unreasonable routing algorithm can easily lead to rapid death of local nodes. It can even lead to the energy black hole. As an important factor for network performance, routing directly determines the efficiency of sensor nodes in the transmission of data [5] . The different speed and time of data transmission in different paths can influence the energy consumption. Sensor nodes are microelectronic devices with limited energy, and their lifetime is largely dependent on battery power [6] . They are mostly distributed in work places where the environment is very bad, so it is very difficult to replace batteries. Therefore, it is very important to design a routing algorithm with low energy consumption, high data transmission speed and high success rate, which directly affects the performance of the whole wireless sensor network system [7] . This paper introduced the typical LEACH protocol, and pointed out its problems, improper selection of cluster heads and uneven distribution of energy consumption. We took steps to improve its shortcomings. First, we used a new threshold probability formula to improved cluster head electing phase. Second, we optimized clustering phase by adding a reference for clustering. This improvement method aiming at two aspects performed better than the previous methods.

2. Related Model

2.1. Network Model

This paper assumes that the sensor network has the following properties:

・ The base station is unique, located in the center of the network area. The location is known to all other nodes, and the energy is not limited.

・ Nodes are randomly distributed in the network, the locations are known and fixed.

・ Each node has limited energy.

・ Each node has same initial energy and data processing capability.

・ Base stations can communicate with all nodes [8] .

2.2. Energy Model

The simulation model of this experiment is based on the first order radio model, as shown in Figure 1 [9] .

According to Figure 1, the energy E T , consumed by the sensor node to transmit k bit data is composed of two parts, one is the energy consumption of the signal transmitting circuit, and the other is the energy consumption of the signal amplifying circuit, as in (1).

E T = { k E e l e c + k ε f s d 2 d < d 0 k E e l e c + k ε m p d 4 d d 0 (1)

where, E e l e c is the energy consumption for transmitting or receiving each bit of data, ε m p is the power amplification factor of the multipath fading model, ε f s is the power amplification factor of the free space model, d is the distance for transmitting data, d 0 = ε f s / ε m p . When the transmitting distance d d 0 , the multipath fading model is adopted, the energy consumption is proportional to the 4th power of the distance; when d < d 0 , the free space model is adopted, and the energy consumption is proportional to the 2nd power of the distance [10] .

The energy E R , consumed by the sensor node to receive k bit data is shown as (2).

E R = k E e l e c (2)

3. LEACH Protocol

Combined with the limited energy of sensor nodes, many effective algorithms have been designed, among which, the most classical one is the low energy adaptive cluster hierarchical protocol (LEACH). The idea of this algorithm was to select cluster head nodes randomly in a cyclic way, it’s shown in Figure 2. The cluster head nodes collected data from member nodes and sent them to the base station. In that way, the energy consumption can be evenly distributed to each node of the network [11] .

LEACH routing protocol was a low power adaptive clustering routing algorithm designed by Heinzelman (MIT, Department of Electronics and Computing) for WSN in 2000. The concept of “wheel” was introduced into the working process of LEACH protocol. Each round was divided into three phases: cluster head selecting phase, clustering phase and stable communicating phase. In the cluster head selecting phase, all nodes ran for cluster head nodes in a specific method. The unselected nodes chose a appropriate cluster head to participate in the cluster a in the clustering phase. In the stable communicating phase, the member nodes transmited data to the cluster heads. The cluster heads then sent them to the base station.

Figure 1. First order radio model.

Figure 2. Clustering diagram of LEACH protocol.

Cluster head selecting phase and clustering phase were the core parts of the LEACH protocol. The details are described as follows:

・ Each node generated a random number between [0] and 1.

・ Each node got a threshold T(i) according to the following formula, which we can get in [7] .

T ( i ) = { P 1 P × [ r mod ( 1 P ) ] i G 0 otherwise (3)

where, P was the percentage of cluster heads in all nodes, r was round, G was the set of nodes that had not been selected as cluster head.

・ The nodes whose random number was less than the threshold were selected as cluster heads and sent the massages to other nodes. Remarkably, those selected nodes could not be cluster heads in the after rounds.

・ The unselected nodes chose a cluster head according to the strength of the received information to participate in the cluster.

・ The cluster heads generated a time division multiple access (TDMA), and sent them to their member nodes.

・ Member nodes collected the around data then sent to their cluster heads on the basis of TDMA.

・ The cluster heads fused the data and then sent them to the base station [12] .

In the LEACH protocol, the balanced distribution of the load in the network saved the energy consumption caused by communication. The method of being cluster head circularly could distribute the load to different nodes in turn. It could also prolonged the system lifetime. Cluster heads fused the data from member nodes reduced the amount of data. However, there were still some shortcomings in LEACH protocol. Scholars had put forward different improvement methods for different problems. In LEACH protocol, no matter how far the cluster head was from the base station, it was necessary to send the data directly to the base station. The energy consumption for data transmission showed exponential relationship with the distance. When the distance was over a certain level, the energy consumption would increase sharply. The author in [13] took an improvement by selecting a sub-cluster head in each cluster. It allowed the cluster head far away from the base station to transmit data by multi-hops through the sub-cluster head, so as to reduce energy consumption for long distance transmission. In [14] , a self-guided adaptive clustering method was proposed to prolong the lifetime of network by allowing or prohibiting nodes to participate in the clustering phase. Some nodes in dense clusters were allowed to enter dormant mode. It could reduce the communication with cluster heads. Thus, it prolonged the network lifetime. This paper introduced an improved algorithm, optimized clustering LEACH protocol based on energy and distance of cluster head (O-LEACH). The algorithm took two steps to improve the LEACH. Firstly, optimize the cluster head selecting to prolong the stability period. Then optimize the clustering phase to average energy consumption among clusters.

4. Improvement Plans

4.1. Optimize Cluster Head Selecting Phase

The cluster head is randomly selected in LEACH algorithm, regardless of the current energy remaining of the node and the transmitting distance between the node and the base station. The node which is selected as the cluster head could be low in energy or far from the base station. This may result in uneven distribution of energy consumption. In this case, the node will die prematurely and the network will be unstable. In order to solve this problem, there is an improved algorithm, Cluster-head-selecting Optimized Advanced LEACH Protocol (COAL). A new threshold probability is used in the algorithm. The new threshold probability has two parts, as shown in (4). C P includes parameters such as the mean and standard deviation of the current energy of the node in each round and the distance between the node and the base station. The energy parameter and distance parameter make the nodes with higher energy and shorter distance from the base station more likely be selected as the cluster heads.

T h r ( i ) = ( 1 P ) G P + P C P i G (4)

There are still problems in the COAL protocol. Since the generation of clusters in each round has great randomness, the number of cluster heads may be too much or too small, and the sensor nodes are randomly distributed. The density of nodes around each cluster head is different. In the same time, member nodes join the cluster only depending on the strength of the received message. Because of those, there will be minimal clusters or maximal clusters. The minimal cluster indicates that excessive cluster heads need communication with the base station. This will increase the energy consumption in per round. The maximal cluster indicates that there are large numbers of member nodes in the cluster. This will increase the energy consumption for cluster head to receive the information member nodes, and the coverage of the cluster will increase. Some nodes have to communicate with the cluster head for a long distance, which increases the energy consumption of the member nodes and shortens the network life cycle. Maximal cluster also means that the range covered by the cluster is very large. Some nodes have to communicate with the cluster head over a long distance. It increases the energy consumption of member nodes. Thus, network’s lifetime will be greatly shortened. Therefore, it is necessary to optimize the clustering phase [15] .

4.2. Optimize Clustering Phase

In order to optimize the clustering phase and prolong network’s lifetime, the clustering optimized LEACH Protocol based on energy and distance of cluster head (O-LEACH) is proposed.

O-LEACH protocol has three phases, cluster head selecting phase, clustering phase and stable communicating phase. In cluster head selecting phase, each node generates a random number between 0 and 1 to compare with a threshold calculated according to (4). And if the random number is less than the threshold, the node is selected as a cluster head; In clustering phase, each member nodes calculate a parameter, P c , according to (5), the parameter is related to the cluster heads. Each node chooses a appropriate cluster head to participate in according to the value of P c . Its stable communicating phase is the same as LEACH protocol. The steps in cluster head selecting phase and clustering phase are shown in Figure 3.

The key part of O-LEACH protocol is the clustering phase. It is important to calculate P c and choose the cluster head which minimum value of P c corresponding to.

P c = d 2 C H d max + E o E c u r i f i N (5)

where, d 2 C H indicates the distance from the node to the cluster head, d max The maximum distance between any two surviving nodes, E o and E c u r represent the initial energy and the current energy of the cluster head, N represents a collection of non-cluster head nodes. The smaller d 2 C H is, the smaller P c is. And the larger a is, the smaller b is. The minimum value indicates that the cluster head is closer to the node or has higher residual energy.

5. Simulation and Results

5.1. Simulation Environment

We use MATLAB to simulate these three protocols (LEACH, COAL and O-LEACH). Then compare and analyze the results. The simulation parameters are listed in Table 1. We set this experiment to run 250 rounds. The two evaluation steps are to analyze the behavior of the three protocols in terms of the dead nodes and average of current energy. As shown in Figure 4, 100 nodes distribute randomly.

Table 1. Simulation environment parameters.

Figure 3. Chart of cluster head selecting phase and clustering phase.

Figure 4. Node distribution.

5.2. Simulation Results

The energy of the node decreases with each round. If its energy is less than zero, the node is considered dead. When most nodes in the network die, the monitoring has no mean. The network’s life ends, if the proportion of dead nodes reaches 98% [16] .

As shown in Figure 5, the number of dead nodes varied over rounds of simulation. It could be seen that all nodes survive until 30th rounds. The first dead node appeared in the 31st round. Later, the number of death nodes increased dramatically. The network’s lifetime completely ended in the 125th round. The Figure 6 illustrated the average of current energy varies over simulation rounds. The energy decreased drastically. Until the 125th round, it was close to zero.

Figure 7 showed the comparison of the number of dead nodes for the three protocols in one experiment. From the simulation results we could see in LEACH protocol the first node died in the 39th round, and the network’s lifetime ended in the 126th round; In COAL protocol the first node died in the 58th round, and the network’s lifetime ended in the 128th round; In O-LEACH protocol the first node died in the 60th round, and the network’s lifetime ended in the 245th round.

To avoid contingency, we did several experiments, and then calculated the mean value of the simulation results. According to the first node dead time (FND) and the most nodes dead time (MND), we listed the improvement effect in Table 2. The data show, LEACH protocol and COAL protocol had almost the same MND, but COAL protocol had later FND, its network-stability increased by 54%; Compared to LEACH protocol, O-LEACH protocol had both later FND and MND, its network-stability increased by 62%, its network lifetime prolonged by 92%. O-LEACH protocol has made two improvements. In the new threshold probability of the cluster head selecting phase, we added the average value and the standard deviation of the current energy. As we all know, that the standard deviation can describe the stability of the data. The smaller the variance, the higher the stability. Because of the parameters, the more stable nodes were more likely to be selected a cluster head. This could make the COAL protocol have longer stablility period and shorter unstability period. So the network is more stable. After we optimized the clustering phase by adding a parameter. Number nodes could select a cluster head depend on a more specific basis. So the clusters were more uniformity and rational. The energy consumption distributed more evenly. Thus the network lifework was longer. This could also be seen from the change in the residual energy of the network in Figure 8.

Figure 8 showed the comparison of the average of current energy for the three protocols in one experiment. Along with the simulation rounds, the death of nodes continued to increase and the current energy of nodes continued to decrease. According to Figure 8, from the beginning to the 40th round the current energy of the three protocols was similar. From 40th to about 120th, the current energy of the three protocols all recreased rapidly. At the same time, the difference among them gradually increased. The value of the two improved protocols were higher than LEACH protocol. After the 120th round, the energy of LEACH protocol and COAL protocol was almost zero. In the simulation process, under the same round, two improvement protocols always had more energy.

Table 2. Comparison of node dead time.

Figure 5. Change of death node number of LEACH protocol.

Figure 6. Change of average residual energy of LEACH protocol.

Figure 7. Comparison of death node number.

Figure 8. Comparison of average residual energy.

6. Conclusion

This paper introduced the LEACH protocol and analyzed its problems. In response to its problems, the O-LEACH protocol was proposed. The improved protocol optimized cluster head selecting phase through adding parameters, the mean and standard deviation of the current energy of the node and the distance between the node and base station, and also optimized clustering phase through adding parameters, the current energy of the cluster head and the distance between the node and clusters. The simulation results showed that the O-LEACH protocol increased the network stability and prolonged the network lifetime.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

Cite this paper

Chang, T.Y., Liu, W.N. and Zhang, Y. (2018) Optimized Algorithm for Clustering Routing for Wireless Sensor Networks. Journal of Computer and Communications, 6, 1-11. https://doi.org/10.4236/jcc.2018.611001

References

  1. 1. Ding, X.X., Ling, M. and Wang, Z.J. (2017) DK-LEACH: An Optimized Cluster Structure Routing Method Based on LEACH in Wireless Sensor Networks. Wireless Personal Communications, 4, 6369-6379. https://doi.org/10.1007/s11277-017-4482-y

  2. 2. Padmavati, T.C.A. (2014) Comparison of Routing Protocols in Wireless Sensor Network Using Mobile Sink—A Survey. Engineering and Computational Sciences, Chandigarh, 6-8 March 2014, 1-4. https://doi.org/10.1109/RAECS.2014.6799601

  3. 3. Liu, M. (2016) Analysis of Wireless Sensor Network Technology Development. Information and Communications, 6, 286-287.

  4. 4. Li, T.F., Du, X.J. and Niu, K. (2014) Wireless Sensor Network Data Fusion in Layer Based on Hierarchy. Modern Electronic Technology, 20, 11-13.

  5. 5. Wang, Z.J., Zhang, Q. and Luo, J.H. (2014) C Optimization Simulation Analysis of Wireless Sensor Network Communication. Computer Simulation, 1, 282-285.

  6. 6. Xu, J.S., Yang, G. and Chen, S.S. (2009) A Global Information Based Protocol for LEACH Improvement. Journal of Nanjing University of Posts and Telecommunications (Natural Science), 4, 55-63.

  7. 7. Heinzelman, W.R., Chandrakasan, A. and Balakrishnan, H. (2000) Energy-Efficient Communication Protocol for Wireless Microsensor Networks. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, Maui, HI, 7 January 2000, 10. https://doi.org/10.1109/HICSS.2000.926982

  8. 8. Guo, D. and Xu, L. (2012) Proceedings of the International Conference on Information Engineering and Applications (IEA). Springer, London, 153-160.

  9. 9. Heinzelman, W.B., Chandrakasan, A.P. and Balakrishnan, H. (2002) An Application Specific Protocol Architecture for Wireless Microsensor Networks. IEEE Transactions on Wireless Communication, 1, 660-670. https://doi.org/10.1109/TWC.2002.804190

  10. 10. Aghera, K. (2017) MMR-LEACH: Multi-Tier Multi-Hop Routing in LEACH Protocol. Proceedings of International Conference on Communication and Networks. 205-214. https://doi.org/10.1007/978-981-10-2750-5_22

  11. 11. Thakkar, A. (2017) DEAL: Distance and Energy Based Advanced LEACH Protocol. International Conference on Information and Communication Technology for Intelligent Systems, Ahmedabad, 25-26 March 2017, 370-376.

  12. 12. Darabkh, K.A., Al-Rawashdeh, W.S. and Al-Zubi, R.T. (2017) C-DTB-CHR: Centralized Density- and Threshold-Based Cluster Head Replacement Protocols for Wireless Sensor Networks. Journal of Supercomputing, 5, 1-22. https://doi.org/10.1007/s11227-017-2089-4

  13. 13. Li, A.C. and Chen, G.F. (2017) An Improved Clustering Routing Algorithm for Heterogeneous Wireless Sensor Networks. Chinese Journal of Sensors Actuators, 11, 1712-1718.

  14. 14. Manjeshwar, A. and Agrawal, D.P. (2002) TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks. Parallel and Distributed Processing Symposium, San Francisco, 23-27 April 2002, 189.

  15. 15. Ye, C., Sun, L.M. and Liao, Y. (2004) An Overview of Energy Management in Sensor Networks. Computer Engineering and Applications, 8, 196-198.

  16. 16. Chen, C. and Jia, Z.H. (2011) An WSN Clustering Algorithm Based on Optimal Cluster Number and Local Energy Optimization. Modern Computer, 10, 14-17.