Clustering Techniques Using Min Heap Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.


Clustering is one of the key mechanisms for load balancing. Clustering Algorithm is an efficient techniques to improve life time and scalability of a Wireless Sensor Network. In this paper, We have proposed an Energy Efficient Load Balanced Clustering Techniques. In these Techniques used to find energy efficient as well as load balancing. Energy Efficient Load Balanced Clustering Techniques is a min heap based Clustering algorithm. In our proposed work we improve a cluster algorithm for load balancing in clusters. Efficiency of WSNs measured by the total distance between nodes to the base station and data amount that has is transfer. Cluster-Head which is totally responsible for the creating cluster and cluster nodes may affect the performance of the cluster .The result show the efficiency of the proposed algorithm in terms of load balancing ,energy efficiency, and the number of sensor nodes die during the network period.

Keywords: Wireless sensor networks, clustering , load balancing, energy efficiency.


The sensor nodes consist of sensing, data processing, and communicating components along with a power unit. In WSN, all the sensor nodes collect local information, process them and send it to a remote base station (called sink). The sink is connected to the Internet for the public notice of the phenomena. One of the most important constraints on sensor nodes is the requirement of low power consumption. Sensor nodes are energy constrained because they carry a limited energy. Because nodes are deployed randomly in a harsh environment so replacement or recharging of battery is not quite possible. Energy consumption in transmission is directly proportional to the square of the distance between transmitter and receiver. So, reducing energy consumption for maximizing network lifetime is thus considered as the most critical challenge in WSN Clustering of nodes is a scalable and energy efficient process for wireless sensor networks. In conventional clustering, network is divided into small group of nodes called cluster . One node from each cluster is selected as a cluster head . All the remaining nodes in the cluster send their data to their respective cluster head. Cluster head aggregate the data and sends to the base station. This scheme works far better than direct transmission but network depends on lifetime of cluster head and cluster head consumes more energy than other nodes and may die early. Every node has the possibility of being a cluster head. Because cluster had selection is done randomly, energy load balancing is achieved among the sensor nodes in the network. In a few WSN scenarios, some high-energy nodes called "Gateways" are deployed in the network. These gateways group sensors to form distinct clusters in the system and act as a CH. The CHs manage the network in the cluster, perform data fusion and send the processed data to the sink through other CHs or sensor nodes. . Each sensor node only belongs to one and only one cluster and communicates with its CH. The advantages of a cluster based WSN are as follows. It reduces energy consumption significantly; conserves communication bandwidth and improves the overall scalability of the network.

However, improper assignment of the sensor nodes for the formation of clusters can make some CHs overloaded with high number of sensor nodes. Such overload may increase latency in communication and degrade the overall performance of the WSN. Therefore, load balancing is also a crucial issue that mu st be taken care while clustering sensor nodes. In this paper, we propose a clustering algorithm that addresses both the issues, i.e., energy efficiency and load balancing. The algorithm is based on min-heap on the number of sensor nodes allotted to the CHs.


Clustering of nodes in a cluster is an energy efficient approach by avoiding the long distance communication of nodes. In static clustering scheme, clusters are fixed and one node acts as a cluster head for each cluster. Cluster head is responsible for gathering data of nodes in the respective cluster and for sending the data o base station located at far distance. A cluster head node is consuming more energy than other nodes and hence is more prone to energy failure. Cluster head node failure results in loss of data of that cluster.


In WSN a number of clustering algorithm have been focused in Olutayo Boyinbode, Ammer Ahamed Abbasi et al. The LEACH was Developed by Heinzelman W.B in 2002. It is a popular clustering technique and it forms clusters by a distributed algorithm. The LEACH is a node with very low energy may be selected as a CH which one quickly die. So overcome this problem a large number of algorithms have been developed for improve LEACH such as TEEN,HEED,APTEEN,PEGASIS. To form cluster, Chor Ping Low et have considered a bipartite graph of the sensor nodes and the gateways to address the maximum matching for sensor node to a CH. The algorithm has the time complexity of O. In a large scale WSN, execution time is very high and also building a BFS tree for individual sensor node takes a substantial amount of memory space. The algorithm proposed in this article takes care of both these issues with the following advantages over the algorithms by Chor Ping Low and Gaurav Gupta et al:

It is additional efficient in terms of sensor dead nodes.

It is supplementary energy efficient and load balanced.


In our algorithm, we are concerned in studying the performance of the following metrics:

4.1 Average number of cluster formation

That means the total number of clusters that are formed in network space. Every cluster is headed by a single cluster head. This is defines the number of the dominated set and it ranges between 1 and N, where N is the number of node in the network.

4.2 Stability

The number of nodes which will be remaining in the cluster during the simulation time. The stability is decremented when a node is moved out from the current cluster and attached to

another cluster.

4.3 Load Balancing

Cluster head can handle the same number of nodes at the same time.

4.4 Min Heap

A min binary heap is an almost complete binary tree with keys and objects stored at the nodes, such that a node's key is greater than or equal to its parent's. The name "heap" is appropriate: we have described a sort of spreading mound of objects with the smallest ones at the top. Note also that the maximum depth of the heap is O(log2n), so provided our operations just move "up and down" the tree, they should run in O(log n) time as required.

EELBCA correctly addresses the issues of load balancing of the CHs and the energy consumption of the sensor nodes. At each assignment we pick up the rooted CH from the min-heap, i.e., the CH which has the minimum number of sensor nodes allotted to it and assign a sensor node to that CH. Therefore, the load is distributed over minimum loaded CHs, thereby balancing the load of the CHs. Energy consumption heavily depends on the distance between two nodes. At each assignment of the sensor nodes, we select and assign that sensor node which is nearest to the minimum loaded CH .Thereby reducing the overall energy consumption of the sensor nodes. Thus the algorithm considers both the issues, i.e., load balancing of the CHs and the energyefficiency of the sensor nodes.

4.5 Restricted Node

Restricted nodes are those sensor nodes, which can communicate with one and only one gateway.

4.6 Restricted Set

Restricted set is the set of all restricted nodes in the WSN

4.7 Open Node

Open nodes are those sensor nodes, which can communicate with more than one gateway.

4.8 Open Set

Open set is the collection of all open nodes in Wireless Sensor Networks.



In this paper we have presented a clustering scheme for wireless sensor networks, in which some far above the ground energy gateways are treated as cluster heads (CHs). The algorithm takes care of the load balancing as well as energy efficiency. The algorithm has been shown to run in O (n log m) time for n sensor nodes and m CHs assuming equal load of the sensor nodes. Our future research will be towards the enlargement of load balancing and energy efficient clustering, for the sensor networks with unpredictable loads of the sensor nodes. We also make an effort to devise a scheme for the cluster head selection.


Akyildiz I.F., W. Su, Sankarasubramaniam Y., Cayirci E., 2002. Wireless Sensor Networks: A Survey. Computer Networks, Vol. 38, Issue 4, pp. 393-422.

Kyung Tae Kim et al., 2009. An Energy Efficient Routing Protocol in Wireless Sensor Networks, Proc. of Int. Conf. on Comp. Sc. And Engg., IEEE, pp. 132 139.

Emanuele Lattanzi et al., 2007. Energetic sustainability of routing algorithms for energy-harvesting wireless sensor networks, Computer Communication, Vol. 30, pp. 2976 2986.

Chor Ping Low et al., 2008. Efficient Load-Balanced Clustering Algorithms for wireless, Computer Communications, Vol. 31, pp. 750 759.

Gaurav Gupta, Younis M., 2003. Load-balanced clustering of wireless sensor networks, ICC '03, IEEE International Conference, Vol. 3, pp. 1848-1852.

Ameer Ahamed Abbasi, Mohamad Younis, 2007. A Survey on clustering algorithms for wireless sensor networks, Computer Communications, Vol. 30, pp. 2826-2841.

Olutayo Boyinbode et al., 2010. A Survey on Clustering Algorithms for Wireless Sensor Networks, 13th International Conference on Network-Based Information Systems, IEEE, pp. 358-364.

Congfeng Jiang, Daomin Yuan, Yinghui Zhao, 2009. Towards Clustering Algorithms in Wireless Sensor Networks-A Survey, Wireless Communications and Networking Conference (WCNC), IEEE, pp.1-6.

Heinzelman W.B., A.P. Chandrakasan, H. Balakrishnan, 2002. Application specific protocol architecture for wireless microsensor networks, IEEE Transactions on wireless communications, Vol. 1, No. 4, pp. 660-670.

S.K. Dhurandher & G.V. Singh, 'Weight based adaptive clustering in wireless ad Hoc Networks", IEEE International Conference on Personal Wireless Communications, New Delhi, India, 2005, 95-100.

D.J. Baker and A. Ephremides, "A distributed algorithm for organizing mobile Radio telecommunication networks", in: Proceedings of the 2nd International Conference on Distributed Computer Systems, April 1981, pp. 476-483.

A.K. Parekh, "Selecting routers in ad-hoc wireless networks", in: Proceedings of The SBT/IEEE International Telecommunications Symposium, August 1994.

P. Basu, N. Khan, and T. D. C. Little, "A Mobility Based Metric for Clustering In Mobile Ad Hoc Networks," in Proc. IEEE ICDCSW' 01, Apr. 2001, pp. 413-18.

M. Gerla and J.T.C. Tsai, Multicluster, mobile, multimedia radio network, Wireless Networks 1(3) (1995) 255-265.

S. Basagni, "Distributed clustering for ad hoc networks", in: Proceedings of International Symposium on Parallel Architectures, Algorithms and Networks, June 1999, pp. 310-315.

S. Basagni, "Distributed and mobility-adaptive clustering for multimedia support in Multi-hop wireless networks", in: Proceedings of Vehicular Technology Conference, VTC, Vol. 2, 1999-Fall, pp. 889- 893.