A Low Energy Consumption Clustering Routing Protocol Based on K-Means

Shan Zhong, Guihua Wang, Xiaohui Leng, Xiaona Wang, Lian Xue, Yue Gu

Computer Science and Engineering College, Changshu Institute of Technology, Suzhou, China..

DOI: 10.4236/jsea.2012.512117                

Abstract

A low energy consumption clustering algorism based on LEACH is researched. Firstly, A method for obtaining the number of clusters k is given, then using the K-Means algorism to divide all the sensor nodes in WSN to the k clusters, in the whole network life cycle the cluster will not changed, and when the energy of cluster head is lower than some threshold, it will be changed. The data transmission between cluster heads to sink node use mixed model, namely, the cluster near the sink node using the single hop and the one far from it using the multiple hops. The experiment shows our method has the longer life cycle and more received information. It is an effective clustering protocol.

Keywords

Clustering Routing; Low Energy Consumption; K-Means

1. Introduction

WSN (Wireless Sensor Network) is composed of amounts of sensor nodes with low-power and limited-processing capability random deployed in the monitoring area [1], and now it is an active research branch in the computer science area. The routing protocol is the main research of WSN. In the view of topological structure of network, the protocols generally can be divided to two types such as flat routing protocol and hierarchical protocol.

The clustering protocol as a hierarchical protocol is more extensive than the other types of protocols, and the clustering protocols generally contains two steps: one is forming the cluster and the other is transmitting the data [2,3].

LEACH protocol (Low-Energy Adaptive Clustering Hierarchy) is firstly introduced by Heinzelman in 2000, and its operation can be described as wheels, every wheel contains forming cluster and data transmission, using the random selection method to select the cluster head, therefore the energy load of the whole network can be assigned to each node to prolong the network cycle.

LEACH protocol has the following defects:

1) The Cluster head is generated by random method, so it can not guarantee the even distribution of cluster heads, and the selection not considering the transmission distance and the node remain energy, leading the uneven energy consumption for different nodes.

2) The communication between cluster head and sink node is using the single hop model, and it will make the node far from the sink node dead in earlier time.

In order to solve the above problem, HEED [4], TEEN [5], PEGASIS [6], EEUC [7] were all realized some improvement on LEACH protocol, but they still existed the uneven energy consumption.

PAN [8] designed an energy efficient routing protocol, the main idea is to strike a value of cluster radius in every level from the most far level to the nearest one and make the radius of the clusters near the sink node less than the radius far from the sink node.

LI [9] presented a clustering strategy for energy balance based on the improved particle swarm optimization clustering algorism.

The above works has big importance, so in this paper we propose a new low energy consumption clustering routing protocol, it also can be described as the two steps such as forming the cluster and transmitting the data.

2. Network Communication Model

The network model is given the following condition:

1) All the sensor nodes in the network are homogeneous and energy constrained, the node is fixed and can not move.

2) The base station is fixed and located far from the sensor node.

3) According the distance from the receiving node, the sending node can adjust transmit power to save the energy.

For the main energy consumption of wireless sensor network is from data communication, so missing the data fusion and managing, the energy consumption model can be represented as follows:

(1)

(2)

In Equation (1) denotes the data transmit energy consumption, denotes the data receiving energy consumption, n is the bit of data packet. is the wireless transceiver circuit energy consumption, and is the amplifier circuit power coefficient for free-space model and multi-path fading model respectively. d is the distance between the sending node and the receiving node.

3 The Clustering Protocol

3.1. The Introduction for K-Means Algorism

K-Means algorism [10] is an unsupervised clustering algorism, namely, assigning every data element to some cluster with the goal of the high similarity of data in the same cluster and the low similarity in different cluster.

3.2. The Number of Clusters

The number of clusters is very important for the operation of K-Means algorism, so we use the value from literature [11] as follows:

(3)

In the above equation, N represents the number of sensor nodes, and the sensor node is distributed in area.

3.3. K-Means Clustering Algorism

Initialize: The number of the clusters can be obtained from Equation (1), iteration time t = 1，the max iteration time T;

Step 1: Choose k sensor nodes from all the n sensor nodes as the initial data centers;

Step 2: Obtain the clusters. According the Equation (5) to obtain the k clusters:

(4)

In Equation (4), is the Euclidean distance between x_i and c_h. From Equation (4) we can find every sensor node will be assigned the cluster which has the least distance form cluster center.

Step 3: Adjust the cluster center and the clusters according the follow equation:

(5)

Step 4: If the iteration time reaches the max value T or the obtained cluster center has not changed for three iterations, then the algorism end and output the clusters, else go to the step 2.

When the algorism is ended, the cluster is formed, but the cluster center may not corresponding to the sensor node position, so we need to according the Euclidean distance assign the some sensor node:

(6)

In Equation (6), is one of the cluster center from the set c, so the cluster center is assigned to x_i, and then x_i is the really sensor node position.

3.4. Data Transmission

After the clusters are formed and the cluster head is selected, the cluster head will broad timeslot to every cluster member. The cluster member only transmits the data in its timeslot, and it sleeps in other time. The cluster head collects the data from the cluster member and fuse it then send to the sink node.

There is a distance threshold R for the cluster head to the sink node. If their distance is less than R, they use single hop and else they use multiple hops.

There is also a energy threshold E for all the cluster heads, if the cluster head is lower than E, then the cluster head will broadcast quit message, and the other nodes which have the biggest energy will success the cluster head.

4. Experiment

Using Matlab as the simulation platform, and the experiment parameters are showed as follows (Table 1).

The Figure 1 shows the numbers of remain live nodes according to the wheels.

From Figure 1 we can find the network life cycle our method is 950 wheels, and it is longer than LEACH 720 and EEUC 840 respectively. The first death node in our method is appeared in 330 wheels, where LEACH and LEACH-C are 140 an 180 respectively. Our method has such big superiority for using K-means to cluster and the multiple hops between cluster head and sink node which can balance the energy consumption.

The Figure 2 shows the total information received by sink node, which shows our method having received more information than LEACH and EEUC. This is because we use the mix transmission model such as single hop and multiple hops, making the cluster head far from the sink node can also send data.

Table 1. Experiment parameters.

Figure 1. The live nodes.

Figure 2. The information received by sink.

5. Conclusion

Routing protocol is very important area in wireless sensor network, so in this paper, we use the K-Means algorism to cluster in wireless sensor network according the clustering idea. The experiment shows our method has realized the even distribution for cluster head and the less distance between cluster member and the cluster head, having the longer life cycle and less total energy consumption.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	J. L. Zhou, Q. Y. Cao, R. C. Huang, et al., “A Genetic Algorithm Based on Extended Sequence and Topology Encoding for the Multicast Protocol in Two-tiered WSN,” Expert Systems with Applications, Vol. 37, No. 2, 2010, pp. 1684-1695. doi:10.1016/j.eswa.2009.06.043
[2]	C. Y. Chong and S. P. Kumar, “Sensor Networks: Evolution, Opportunities, and Challenges,” Proceedings of the IEEE, Vol. 91, No. 8, 2003, pp. 1247-1256. doi:10.1109/JPROC.2003.814918
[3]	J.-J. Chen and P. Jiang, “Algorism for Wireless Sensor Network Based on Fuzzy C-Means,” Computer Engineering, Vol. 37, No. 12, 2011, pp. 62-67. (in Chinese)
[4]	O. Youni and S. Fahmy, “HEED: A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks,” IEEE Transactions on Mobile Computing, Vol. 3, No. 4, 2004, pp. 366-379. doi:10.1109/TMC.2004.41
[5]	A. Manjeshwar and D. P. Agrawal, “TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Net-works,” Proceedings of 15th IEEE International Parallel and Distributed Processing Symposium, San Francisco, 23-27 April 2001, pp. 2009-2015.
[6]	S. Lindsey and C. S. Raghavendra, “Pegasis: Power Efficient Gathering in Sensor Information Systems,” Proceedings of the IEEE Aerospace, Los Angeles, 2002, pp. 1125-1130.
[7]	C.-F. Li, G.-H. Chen, M. Ye and J. Wu, “An Uneven Cluster-Based Routing Protocol for Wireless Networks,” Chinese Journal of Computers, Vol. 30, No. 1, 2007, pp. 27-36.
[8]	Z.-Q. Pan, L.-L. Liu and D. Zhang, “An Energy Efficient Routing Protocol Based on Uneven Clustering for Wireless Sensor Networks,” Microelectronics & Computer, Vol. 29, No. 1, 2012, pp. 93-96.
[9]	H.-B. Li, C.-B. Yu, J.-H. Yan and Y.-L. Li, “Clustering Strategy for Energy Balance of Wireless Sensor Networks Based on Improved Particle Swarm Optimization Clustering Algorithm,” Application Research of Computer, Vol. 28, No. 2, 2011, pp. 657-660.
[10]	S. L. Chiu, “Fuzzy Model Identification Based on Cluster Estimation,” Journal of Intelligent and Fuzzy Systems, Vol. 2, No. 3, 1994, pp. 267-278.
[11]	R.-C. Wang, W.-S. Juang and C.-L. Lei, ?Robust Authentication and Key Agreement Scheme Preserving the Privacy of Secret Key,” Computer Communications, Vol. 34, No. 3, 2011, pp. 274-280. doi:10.1016/j.comcom.2010.04.005