A Robust Cluster Head Selection Method Based on K-Medoids Algorithm to Maximize Network Life Time and Energy Efficiency for Large WSNs

A Robust Cluster Head Selection Method Based on K-Medoids Algorithm to Maximize Network Life Time and Energy Efficiency for Large WSNs

Priyanka Devi, Doaba Institute of Engineering and Technology

Khushneet Kaur, Doaba Institute of Engineering and Technology

Abstract – WSNs are utilized in number of fields like healthcare, weather, military, etc. These sensor nodes are battery running devices. Hence, the energy becomes the major issue. A number of researches are being conducted to increase their battery life. Sensing process is the primary process of Sensor nodes. A number of WSN processes are having great possibilities of improvement: 1) Clustering, 2) Routing 3) Routing Data Management. In this paper, we are improving an existing clustering algorithm which is based on k-medoids clustering algorithm. In this paper, we are proposing an effective and efficient cluster head selection method using k- Medoids to solve the stated problem, especially for large WSNs consisting of thousands or millions of nodes. k-Medoids is more efficient and correct than k-Means for large clusters. Both of K-Means and k-Medoids utilize expectation maximization (EM) strategy to converge to a minimum error condition. While k-Medoids require the cluster centers to be centroids, in k-Means the centers could be anywhere in the sample space. k- Medoid is more robust to outliners than k-Means therefore results in more quality clustering. It is also computationally more complex. Computer simulation will be performed in the NS2 environment and the proposed approach will be compared with LEAH and HEED.

INTRODUCTION

In the last half century, the computers have exponentially increased in processing power and at the same time decreased in both size. These rapid developments led to large market in which computer based devices are being used more and more in our societys daily activities. In the last years, computers are reduced in size and becoming so small and so cheap, that single-purpose computers with embedded sensors are almost practical from both economical and theoretical points of view. Wireless sensor networks are the computers which are beginning to become a reality, and therefore some of the long overlooked limitations have become an important area of research.

FIGURE 1: Wireless Sensor Network Architecture

/usr/staudek/vyuka/PA151/07_wpan_zb.ps.pdf&ust=139944 0775533106&usg=AFQjCNHj2reTSqQ0xQ7lDoxx2rvc- nuNig]

In latest research on WSN, the researchers have attempted to overcome the limitations of the wireless sensor networks such as: limited battery resources, varying energy consumption based on location, high cost of transmission, and limited processing capabilities. All of these characteristics of wireless sensor networks are complete opposites of their wired network counterparts, in which energy consumption is not an issue, transmission cost is relatively cheap, and the network nodes have plenty of processing capabilities. Routing approaches that have worked so well in traditional networks for over twenty years will not suffice for this new generation of networks.

FIGURE 2: Representation of a network in which a node goes down due out of battery and a different path is chosen with a Single-path algorithm

Besides maximizing the lifetime of the sensor nodes, it is preferable to distribute the energy dissipated throughout the wireless sensor network in order to minimize maintenance and maximize overall system performance. Any communication protocol that involves synchronization between peer nodes incurs some overhead of setting up the communication. WSN routing or clustering protocols determine whether the benefits of more complex routing algorithms overshadow the extra control messages each node needs to communicate. Each node could make the most informed decision regarding its communication

options if they had complete knowledge of the entire network topology and power levels of all the nodes in the network. This indeed proves to yield the best performance if the synchronization messages are not taken into account. However, since all the nodes would always need to have global knowledge, the cost of the synchronization messages would ultimately be very expensive. For both the diffusion and clustering algorithms, we will analyze both realistic and optimum schemes in order to gain more insight in the properties of both approaches.

The usual topology of wireless sensor networks involves having many network nodes dispersed throughout a specific physical area. There is usually no specific architecture or hierarchy in place and therefore, the wireless sensor networks are considered to be ad hoc networks. An ad hoc wireless sensor network may operate in a standalone fashion, or it may be connected to other networks, such as the larger Internet through a base station. Base stations are usually more complex than mere network nodes and usually have an unlimited power supply. Regarding the limited power supply of wireless sensor nodes, spatial reuse of wireless bandwidth, and the nature of radio communication cost which is a function of the distance transmitted squared, it is ideal to send information in several smaller hops rather than one transmission over a long communication distance.

FIGURE 4: A standard clustering algorithm example

In our research, we propose a new clustering method for the wireless sensor nodes which will be better than the existing clustering algorithms. We propose the use of kmedoids algorithm for the wireless sensor network clustering. Kmedoids is effective algorithm than kmeans, as it find the more accurate centers of the clusters, which can results as better communication between sensor nodes, less energy consumption and lower packet delay. This leads to better maintainability of the system, such as replacing the batteries all at once rather than one by one, and maximizing the overall system performance by allowing the network to function at its best capacity throughout most of its lifetime instead of having a steadily decreasing node population.

Literature Review

Geon Yong Park et. al. has worked on Wireless sensor network and proposed an efficient cluster head selection method using K-means algorithm to maximize the energy efficiency of wireless sensor network. Their results have shown that the proposed approach allows better performance than the existing hierarchical routing protocols such as LEACH and HEED in terms of network lifetime.

Sonam Palden Barfunga et. al. have proposed an energy efficient routing protocol, which is hierarchical and cluster based. Sajal Sarkar et. al. have proposed A Trust Based Protocol for Energy-Efficient Routing in Self-Organized MANETs. Geon Yong Park et. al. proposed a cluster head selection method based on K-Means clustering algorithm for WSNs. Issue of Energy efficiency due to Limited Battery is addressed in this paper. K-means algorithm is used to maximize the energy efficiency of wireless sensor network. It is based on the concept of finding the cluster head minimizing the sum of Euclidean distances between the head and member nodes. Sonam Palden Brfunfga et. al. has been proposd an routing protocol based on energy efficiency for WSNs. In this protocol, the Base Station selects the Cluster Heads (CH). The selection procedure is carried out in two stages. In the first stage, all candidate nodes for becoming CH are isted, based on the parameters like relative distance of the candidate node from the Base Station, remaining energy level.

Problem Fo1rmulation

Wireless sensor nodes run on limited battery without direct power supply. The energy consumption is the most important research area for the research on WSNs. Because wireless nodes run on battery, they carry a limited battery life. Sensing process is the primary functionality of sensor nodes. Changing sensing process may degrade the performance of wireless nodes whereas routing process is the secondary process and carries a great possibility of improvements. In this paper, we are improving an existing routing algorithm, which outperforms Proposed Algorithm in the base paper, LEACH and HEED protocol in the smaller or larger WSN networks. In this paper, we are proposing an effective and efficient cluster head selection method using k-Medoids clustering algorithm for the cluster head selection in almost the center of the cluster. K- Medoids require the cluster centers to be centroids, whereas in k-Means the centers could be anywhere in the sample space. k-Medoid is more robust to outliners than k-Means therefore results in more quality clustering. It is also computationally more complex. Computer simulation will be performed in the NS2 environment and the proposed approach will be compared with LEAH and HEED.

Methodology

At first, the literature on the WSN clustering protocols and WSN processes would be studied in detail. Then the algorithm flow would be reviewed and refined in case any changes are required. Afterwards, the algorithm would be programmed in NS2. The experiment results would be thoroughly analyzed and compared with the existing algorithm results. This is also very important to get the information about the parameters used for wireless sensor network clustering protocol simulations. This project would be implemented in the NS2 Simulator. A thorough performance and feature testing model would be formed and utilized to analyze the performance of the simulated clustering protocol, to detect the flaws and to recover them. Afterwards, the experiment results would be thoroughly

analyzed and compared with the existing clustering algorihtms to examine the performance of the new WSN clustering algorithm.

CONCLUSION

In this paper, we are proposing an effective and efficient cluster head selection method using k-Medoids to solve the stated problem, especially for large WSNs consisting of thousands or millions of nodes. k-Medoids is more efficient and correct than k-Means for large clusters. Both of K- Means and k-Medoids utilize expectation maximization (EM) strategy to converge to a minimum error condition. While k-Medoids require the cluster centers to be centroids, in k-Means the centers could be anywhere in the sample space. k-Medoid is more robust to outliners than k-Means therefore results in more quality clustering. It is also computationally more complex. Computer simulation will be performed in the NS2 environment and the proposed approach will be compared with LEAH and HEED.

REFERNECES

1. Geon Yong Park, Heeseong Kim, Hwi Woon Jeong, and Hee Yong Youn, A Novel Cluster Head Selection Method based on K-Means Algorithm for Energy Efficient Wireless Sensor Network, AINAW, vol. 1, pp. 910-915, IEEE, 2013.

2. Energy Efficient Cluster Based Routing Protocol for Wireless Sensor Networks by Sonam Palden Barfunga Prativa Rai, Hiren Kumar Deva Sarma, ICCCE IEEE 2012, 3-5 July 2012, Kuala Lumpur, Malaysia

3. A Trust Based Protocol for Energy-Efficient Routing in Self- Organized MANETs by Sajal Sarkar, Student Member, IEEE and Raja Datta, Senior Member, IEEE, 2012

4. Hierarchical Adaptive Balanced energy efficient Routing Protocol (HABRP) for heterogeneous wireless sensor networks BY Said BEN ALL*, Abdellah EZZATI, Abderrahim BENI HSSANE, Moulay Lahcen HASNAOUI, IEEE, 2010

5. Study on WSN Topology Division and Lifetime XU Jiu-qiang, WANG Hong-chuan,LANG Feng-gao,WANG Ping,HOU Zhen-peng,

   IEEE, 2011

6. William B. Davis, "Graphical Model Theory for Wireless Sensor Networks" (December 8, 2002). Lawrence Berkeley National Laboratory. Paper LBNL-53452.

7. J. Kusuma, L. Doherty, and K. Ramchandran, Distributed Compression for Sensor Networks, International Conference on Image Processing (ICIP), October 2001.

8. Dragan Petrovi, Rahul C. Shah, Kannan Ramchandran, Jan Rabaey, Data Funneling: Routing with Aggregation and Compression for Wireless Sensor Networks, First IEEE International Workshop on Sensor Network Protocols and Applications, May 11, 2003.

9. Sundeep Pattem, Bhaskar Krishnamachari, and Ramesh Govindan, "The Impact of Spatial Correlation on Routing with Compression in Wireless Sensor Networks," ACM/IEEE International Symposium on Information Processing in Sensor Networks (IPSN), April 26-27, Berkeley, CA 2004.

10. Raymond Wagner, Shriram Sarvotham, Hyeokho Choi, Richard Baraniuk, Distributed Multiscale Data Analysis and Processing For Sensor Networks, Rice University Technical Report, February 9, 2005.

11. Karim Seada, Marco Zuniga, Ahmed Helmy, Bhaskar Krishnamachari, "Energy Efficient Forwarding Strategies for Geographic Routing in Lossy Wireless Sensor Networks," ACM Sensys 2004, November 2004.

12. Scott Briles, Joseph Arrowood, Dakx Turcotte, Etienne Fiset, Hardware-In-The-Loop Demonstration of a Radio Frequency Geolocation Algorithm, Proceedings of the Mathworks International Aerospace and Defense Conference, May 24-25, 2005.