Position Identification of Cluster Head for Wireless Sensor Networks

Position Identification of Cluster Head for Wireless Sensor Networks

A. Chandra Sekhar Reddy [M.Tech]

S.R.M University, Kattankulathur Dept. of Computer Science Engineering

G. Vijayalakshmi [Assistant Professor]

1. University, Kattankulathur Dept. of Computer Science Engineering

   Abstract A WSN is a self-configured network being composed of a large number of sensors, which gathering various data including temperature, sound, location, etc and they provides unprecedented opportunities in several domains ranging from military to civil use, such as healthcare, industrial control, environmental monitoring. The nodes in a WSN are powered by battery and the difficulty of replacing or recharging their batteries in nature such harsh environment like forests, chemical factories, thus it need be carefully planned to prolong the network lifetime. Clustering techniques have emerged as a popular choice for achieving energy efficiency and scalable performance in large scale sensor networks. A clustering algorithm is composed of three parts first electing cluster head (CH), selection of cluster membership and transfer data from members to CH. In order to efficiently use the power, we design a new version of clustering algorithm named as PICH (Position Identification of Cluster Head), that owns advantages of scalability, energy efficiency and efficient communication.

   Keywords PICH, clustering, cluster-head, base-station, sensor nodes.

   1. INTRODUCTION

      Wireless sensor networks are a trend of the past few years, and they involve deploying a large number of small nodes. The nodes then sense environmental changes and report them to other nodes over flexible network architecture. Sensor nodes are great for deployment in hostile environments or over large geographical areas. Moreover in a densely deployed sensor network the physical environment would produce very similar data in near-by sensor nodes and transmitting such data is more or less redundant.

      Therefore, all these facts encourage using some kind of grouping of nodes such that data from sensor nodes of a group can be combined or compressed together in an intelligent way and transmit only compact data. This can not only reduce the global data to be transmitted and localized most traffic to within each individual group, but reduces the traffic in a wireless sensor network. This process of grouping of sensor nodes in a densely deployed large-scale sensor network is known as clustering.

      Network structure typically follows two different routing paradigms in WSNs, flat routing and hierarchical routing [7]. In flat routing, all nodes with the same functions and performing the same tasks deliver data by flooding hop-by- hop. This approach best suits small-scale networks. In

      hierarchical routing [5], nodes function differently and are organized into many clusters. Some nodes are selected as cluster heads (CHs) which manage clusters, processing data from cluster members, and delivering it to the BS or other cluster heads. The other nodes join clusters and become members of clusters, which sense and deliver data to cluster heads. Cluster heads can be layered into additional hierarchical levels. Hierarchical routing best suits large-scale networks.

      There are some issues involved with the process of clustering in a wireless sensor network. First issue is, how many clusters should be formed that could optimize some performance parameter. Second could be how many nodes should be taken into a single cluster.

      Third important issue is the selection procedure of cluster- head in a cluster. Another issue that has been focused in many research papers is to introduce heterogeneity in the network. It means that user can put some more powerful nodes, in terms of energy, in the network which can act as a cluster-head and other simple node work as cluster-member only.

   2. RELATED WORK

      Many clustering algorithms and protocols have proposed for improving energy efficiency and extending network lifetimes in past few years. We review a few important clustering protocols below.

      1. LEACH

         The idea of Low-Energy Adaptive Clustering Hierarchy (LEACH) is to organize the nodes into clusters to distribute the energy among the sensor nodes in the network. LEACH is one of the most popular clustering algorithms used in WSNs to increase the network lifetime. LEACH is an adaptive, self organizing and clustering protocol. It introduces the concept of rounds, where each round includes two phases, a setup phase and a steady phase. In the setup phase, LEACH randomly selects sensor nodes as Cluster Heads (CHs), subsequently rotating roles in each round in order to distribute energy dissipation to all sensor nodes of the network. In the steady- state phase, data are delivered from sensor nodes to CHs and from CHs to the BS per a TDMA/CDMA [7] schedule. LEACH assumes that the BS is fixed and located far from the sensors, all sensor nodes are homogenous and have limited energy source, sensors can sense the environment at a fixed

         rate and can communicate among each other and communicate with BS.

      2. TEEN

         TEEN (Threshold sensitive Energy Efficient sensor Network) is a cluster based hierarchical routing protocol based on LEACH. This protocol is used for time-critical applications. In this protocol, nodes sense the medium continuously, but the data transmission is done less frequently. The network consists of simple nodes, first-level cluster heads and second-level cluster heads. TEEN uses LEACHs strategy to form cluster. First level CHs are formed away from the BS and second level cluster heads are formed near to the BS. A CH sends two types of data to its neighbours one is the hard threshold (HT) and other is soft threshold (ST). In the hard threshold, the nodes transmit data if the sensed attribute is in the range of interest and thus it reduces the number of transmissions. On the other hand, in soft threshold mode, any small change in the value of the sensed attribute is transmitted. The nodes sense their environment continuously and store the sensed value for transmission. Thereafter the node transmits the sensed value if one of the following conditions satisfied:

         1. Sensed value > hard threshold (HT).

         2. Sensed value ~ hard threshold >= soft threshold (ST).

      3. PEGASIS

         PEGASIS (Power Efficient Gathering Sensor Information System) is a chain based power efficient protocol based on LEACH [4]. According to this protocol, all the nodes have information about all other nodes and each has the capability of transmitting data to the base station directly. It assumes that all the sensor nodes have the same level of energy and they are likely to die at the same time. Chain creation is started at a node far from BS. Each node transmits and receives data from only one closest node of its neighbours. To locate the closest neighbour node, each node uses the signal strength to measure the distance from the neighbours and then adjusts the signal strength. Node passes token through the chain to leader from both sides. Each node fuses the received data with their own data at the time of constructing the chain. In each round, a randomly chosen node (leader) from the chain will transmit the aggregated data to the BS. Node i (mod N) is the leader in round i. The chain consists of those nodes that are closest to each other and form a path to the base station. The aggregated data is sent to the base station by the leader.

      4. HEED

         Hybrid Energy-Efficient Distributed clustering (HEED) is an energy-efficient protcol. It selects CHs periodically based on residual energy and on intra-cluster communications costs among sensor nodes. HEED is fully distributed and adaptive. CHs can be uniformly distributed throughout the network thereby balancing the load. However, like LEACH, it requires re-clustering each round which brings significant overhead and diminishes energy gains. Furthermore, HEED cant avoid the hot spot issue.

      5. Motivation

         In contrast with the LEACH, LEACH with Distance-based Thresholds (LEACH-DT) is efficient protocol, in terms of electing a CH. In LEACH-DT [3], the probability for a node to

         become a CH depends on its distance to the BS. The advantage of this protocol is a very few nodes are participating in the CH election and elected node is nearer to BS among the nodes in a cluster.

         The idea of this protocol in multi-hop extension is to have the sensors formed different sensor groups (SG) [3] based on their distances of the BS. Each SG runs the single-hop LEACH-DT to select the CH as before. Data is then relayed from the far- away SGs to the closer ones on a hop by-hop basis with each CH closer to the BS acting as the BS for the sensors in the upstream SG.

         Drawbacks of LEACH-DT

         • This protocol is not balancing energy to all sensor nodes in a cluster. So which sensor nodes are far away from cluster head those are run out energy early.

         • Even though the nodes having high energy that are far away from the BS, they are not participating in CH election.

   3. NETWORK MODEL

      To overcome the drawbacks of LEACH-DT, we proposed a new protocol Position Identification of Cluster Head (PICH). The basic operations of PICH are organized in two distinct phases. The first phase consists of cluster formation and position identification of CH. The second phase consists of data transmission and data aggregation. The duration of the first phase is assumed to be relatively shorter than the second phase to minimize the protocol overhead. There are two different types of sensor nodes in our protocol. The category-1 nodes have higher initial energy, a bigger transmission range, GPS and mobility. The category-2 nodes having lower initial energy and static.

      1. Cluster Formation

         Cluster-Heads (CHs) broadcast their location information to all the sensor nodes in the network. Each sensor node selects the closest CH and joins the cluster by sending its location information directly to the CH. The CH transmits the join confirm message back to the sensor node. Each CH computes the center of all the member sensor nodes based on our algorithm, moves to the center location. It broadcasts the center location information to all sensor nodes.

         The center of each CH is adjusted according to our algorithm.

         Figure 1. Clustering network, before execution of our algorithm

         Our algorithm uses a two-step round. First, each sensor node selects the nearest CH, joins it and becomes the clusters member. The second step is to calculate and update the center of each cluster. Our approach is to find the center of the enclosing all sensor nodes in a cluster and moves the cluster head to center.

         Figure 2. After execution of our algorithm

         In addition, the clustering formation is only required in the beginning and there is no re-clustering at a later time. In case some sensor nodes are dead or partial damage surfaces in a specific cluster after a period in first phase, the CH of that cluster can calculate the new center location, move to there and broadcast the new location to the rest of the sensor nodes in the cluster. Except for typically nominal

         costs to the specific CH for computing and moving, the whole process dont affect other clusters and other sensor nodes, which still keep their existing topology. This feature makes our protocol robust despite partial damage and able to self recovery.

      2. Data Transmission

         Once the clusters are formed, according to the number of sensor nodes in each cluster, each CH creates a TDMA schedule and broadcasts it to all the sensor nodes in its cluster [5]. The TDMA schedule of the cluster arranges time slots for each sensor node in the cluster to transmit data. Each sensor node can just transmit data in its allocated time slot and is in sleeping state in other time slots. Using the TDMA schedule for the cluster can reduce intra-cluster transmission collisions and save energy dissipation. Data transmission starts after each sensor node gets its time slot. The CHs always turn their receivers on to receive all the data from their member sensor nodes.

      3. Data Aggregation

      In energy constrained sensor networks of large size, it is inefficient for sensors to transmit the data directly to the base station. In such scenarios, sensors can transmit data to a cluster head which aggregates data from all the sensors in its cluster and transmits the concise digest to the base station. This results in significant energy savings for the energy constrained sensors.

      In this paper, we describe the some important factors on performance measures of data aggregation algorithms.

      Network lifetime: The main idea is to perform data aggregation such that there is uniform energy drainage in the network.

      Latency: Latency is defined as the delay involved in data transmission, routing and data aggregation. It can be measured as the time delay between the data packets received at the sink and the data generated at the source nodes.

   4. RESULTS

      To compare performance of the proposed algorithm with the LEACH-DT, we measure the following metrics.

      Network Lifetime: Network lifetime strongly depends on the lifetimes of the single nodes that constitute the network. The lifetime of a sensor node depends basically on two factors such as how much energy it consumes overtime, and how much energy is available for its use.

      Cost Efficiency: In a clustered network, the cost is divided into intra-cluster and inter-cluster cost. The intra-cluster communication cost is from the nodes inside a cluster to the head. The inter-cluster communication cost is from the heads

      to the base station. The cost of clustering is a key issue to validate the effectiveness and scalability enhancement of a cluster structure.

      The following graphs are drawn based on below two assumptions.

      Assumption 1: 30J of energy is required for every 10m distance between node and CH.

      Assumption 2: one CH for every 30 m2 area.

      In LEACH-DT if the distance is increases from cluster head to sensor node the required number of CHs more compared to PICH. So the cost efficiency of our protocol is less compared to LEACH-DT.

   5. CONCLUSION

In this paper we present an energy efficient clustering scheme, PICH (Position Identification of Clustering Hierarchy) protocol for heterogeneous sensor networks. Cluster heads can move and having higher initial energy. The sensor nodes directly transmit their data to their cluster heads. The cluster heads collect data from sensors, process it and transmit data to a base station either single-hop or multi-hop. Our extensive evaluation study has demonstrated considerable improvements achieved by PICH compared to LEACH-DT[3] clustering algorithm to save sensors energy and to prolong network lifetime.

Figure 3. Network Lifetime

In LEACH-DT if the distance is increases from cluster head to sensor node energy consumption also increases, so all sensor nodes doesnt having equal energy. In PICH all sensor nodes are having equal distance to CH, so all sensor nodes having equal energy to improving network lifetime.

Figure 4. Cost Efficiency

REFERENCES

1. M.Y.M. Youssef, A.Youssef An overlapping multi-hop clustering for wireless sensor networks, in IEEE Trans., China, 2013, pp. 43754380.

2. Raed M.Bani Hani1 and Abdalraheem A.Ijjeh A Survey on LEACH- Based Energy Aware Protocols for Wireless Sensor Networks Jordan, arch 2013, pp. 192-206.

3. Sang H. Kang and Thinh Nguyen Distance Based Thresholds for Cluster Head Selection in Wireless Sensor Networks in IEEE COMMUNICATIONS LETTERS, U.S.A, September 2012, VOL. 16, NO. 9.

4. Ravi Kishore Kodali and Prof. Narasimha Sarma Energy Efficient Routing Protocols for WSN's in International Conference on Computer Communication and Informatics, Coimbatore (India), January 2013.

5. Yang Jing and Li Zetao Improved Routing Algorithm Based on LEACH for WSN in IEEE, China, March 2013.

6. M.F Khaton Abad and M.A Jabraeil Jamali Modify LEACH Algorithm for Wireless Sensor Network in IJCSI International Journal of Computer Science Issues, Iran, September 2011, Vol. 8, Issue 5, pp.219- 224.

7. Qing Yan, Yizong K-Centers Min-Max Clustering Algorithm over Heterogeneous WSN in IEEE, USA, 2013.

8. Geon Yong Park, Heeseong Kim, and Hee Yong Youn A Novel Cluster Head Selection Method based on K-Means Algorithm in IEEE, Suwon, 2013.

9. Solaiman Ali, Tanay Dey, Advanced LEACH Routing Protocol for Wireless Sensor Networks in ICECE, Dhaka, December 2008.

10. Ramesh Rajagopalan, Pramod K. Varshney Data aggregation techniques in sensor networks: A Survey in SURFACE, USA, 2006.

11. Hyunsook KimCluster Head Selection Scheme for Minimizing Changes of Cluster Members Considering Mobility in Mobile Wireless Sensor Networks in ICACT, Korea, January 2013.