Cluster Head Selection using Vertex Cover Algorithm

Cluster Head Selection using Vertex Cover Algorithm

Shwetha Kumari V

1. ech Scholar (Computer Network Engineering), Dept. of Information Science & Engineering, NMAMIT, Nitte

   Vasudeva Pai

   Assistant Professor, Dept. of Information Science & Engineering, NMAMIT, Nitte, India

   Ravi B

   Assistant Professor, Dept. of Computer Science & Engineering, NMAMIT, Nitte, India

   Abstract The lifetime of wireless sensor network can be prolonged by the method of Clustering. Clustering is nothing but grouping sensor nodes into many clusters and identifying a coordinator node to regulate the activities of remaining sensor nodes. We call this coordinator node as Cluster heads. There are various techniques for selecting cluster heads based on sensor node attributes. The main responsibility of cluster- head nodes is to receive and aggregate data from the sensor nodes. Due to this, cluster head dissipates more energy when compared to sensor nodes. Moreover, cluster-head nodes consume more energy as they relay data of the sensor nodes that are far away from the base station which in turn decreases network lifetime. In this paper, a different approach has been used to cluster the sensor network. We apply Vertex Cover Algorithm to find the cluster heads. The vertex cover set obtained from Vertex Cover Algorithm are made as cluster heads. A heuristics algorithm was developed to further optimize the cluster heads. Once after we find the cluster heads we apply Prims algorithm to find minimum spanning tree. Finally we find a traversal order for these cluster heads for the mobile sink to visit by using Depth First Search algorithm. The simulation results show that the vertex cover algorithm resulted optimum number of cluster heads and analyzed for various parameters like throughput, network lifetime, pdf and residual energy.

   Keywords Vertex cover; Cluster-head; Wireless sensor network.

   1. INTRODUCTION

      Wireless sensor network is an environment where a large number of sensor nodes are deployed to sense the data from the surrounding and transmit the sensed data to the base-station through wireless communication for further processing. Sometimes we make use of intermediate nodes to relay the data from the sensor nodes that are outside the transmission range.

      Wireless sensor network has an extensive applications in the areas such as security and military applications, disaster relief applications, medicines and healthcare etc [1]. The production of WSN components has been increased as it has been used in different applications. The main demerit of WSN is the battery life of sensor nodes that is they cannot be replaced or recharged. The energy of the sensor nodes gets depleted near the sink as it has to be overburdened with heavy traffic. The nodes near the sink will always be engaged in transferring data to base station and thus drains their energy quickly [2]. So, improving the energy efficiency of sensor network is necessary. In general, if communication in sensor networks is more,

      energy consumption is also more. Hence, it is a challenging task to reduce the energy consumption during sensor node deployment in sensor networks.

      The basic WSN architecture consists of Sink node, Sensor nodes and Cluster heads. In layered architecture sink node gets the information from sensor nodes through one hop or multi hop communication. Clustered architecture consists of cluster heads responsible for collecting data from sensor nodes within a cluster. Sink node visits only these cluster heads to buffer the data. In mobile sink node architecture, mobile sink travel in sensing area and collects data from sensor nodes [3].

      There are several techniques to minimize energy consumption in wireless sensor networks. The sensed data from the sensors are always transmitted to far away located Base Station. The aggregated data to the sink from the sensor nodes is sent either directly or using multiple hops. One hop transmissions directly send the data to the sink (base station). The far away nodes from the base station consume more energy. Thus, to reduce energy consumption clustering approach is used.

      In the clustering approach, we select a sensor node as a cluster-head either based upon the factors such as residual energy, reliability, threshold value, degree of mobility, distance to neighbor nodes, etc. or they are self elected. Remaining sensor nodes in the cluster make use of cluster head to transmit their data to the base station. Now all the sensed data is aggregated by the cluster heads along with its own data and transmits it to the base station. So cluster head node drains out its energy quickly but the energy consumed at each node level is reduced. This quick depletion of energy can be avoided by changing the cluster heads in every round in every round. Thus, cluster head selection plays a major role in energy consumption minimization in wireless sensor networks.

      When a problem is NP-complete it belongs to NP and NP-Hard. One example for NP-complete problem is Vertex cover problem. We can define vertex cover problem for a graph G = (V, E) with V set of vertices and E set of edges, a vertex cover V is a subset of V such that V contains at least one end vertex of every edge. The process of finding minimum sized vertex cover in an undirected graph is known as a vertex cover problem.

      In this paper, we find minimal vertex covers by using existing polynomial-time algorithm in undirected graphs. The vertices in the vertex cover set are made as cluster heads for gathering the neighbour data. Once clusters are

      formed we construct spanning tree and apply DFS algorithm for the cluster heads to identify the traversal of the mobile sink. A heuristic algorithm is developed to further reduce the number of cluster heads. The results show that this method identifies optimal number of cluster heads and visits each cluster heads without any data loss.

   2. RELATED WORK

      Existing methods have shown that mobile sink can be used for energy efficient data collection and to improve the overall network life time. There are two classes of WSN with mobile sink [4]. In Direct method, mobile sink collects the data via single hop. In Rendezvous method mobile sink visits only RPs aiming for minimized energy consumption.

      In [5], an approach for clustering is proposed to reduce the latency. Here sensor nodes are at one hop distance from the CHs. Cluster head assumes the role of Collection points (CP). In Cluster based Collection Point (CCP) algorithm, Mobile element visits reduced number of collection points. Tour length is further reduced using Clustering based-Rendezvous collection Points (CRP) algorithm. The algorithm identifies the rendezvous points. The two algorithms have performed the best known algorithms in terms of latency and tour length. There are two types of nodes in the clustering approach, Cluster- Head node and Cluster-member nodes. Cluster head node collects data from the member sensor nodes and mobile sink transmits it to the base station for further processing [6].

      The most popular clustering algorithm is LEACH (Low Energy Adaptive Clustering Hierarchy) [7]. LEACH forms clusters based on the sensor nodes signal strength. Cluster Heads are chosen randomly and member are assigned to it based upon the signal strength received by that node from the cluster head. CHs die quickly as they have to work more. Cluster head keeps on rotating in every round. There are two phases in LEACH: Start up and steady phase. Within each cluster, LEACH performs local aggregation of data so that the amount of data that needs to be trasmitted to the base station is reduced. LEACH also has disadvantages as Cluster heads are randomly selected, they are non-uniformly distributed, does not cover a large area, dynamic clustering leads to overload.

      Due to limited energy supply in wireless senor networks, it is difficult to develop an energy efficient self organization protocols which can provide redundancy and network survivability features. Hybrid-Distributed-Energy- Efficient-Dual-Homed (HDED) Clustering Algorithm is one such highly energy efficient self organization Protocol which based on clustering [8]. This protocol finds the optimal cluster heads, improves the cluster heads selection and the communication between nodes. In addition, fault tolerance, cost scalability, power consumption and topology change are the constraints satisfied by HDED. This protocol prolongs the network lifetime by improving the energy utilization rate. In this protocol, cluster head is chosen based on the criterias such as, average node distance in the cluster and largest energy. In each cluster

      nodes calculates their weights and the node with highest weight becomes the Cluster-Head for that particular cluster. The protocol provides a mechanism called cluster head backup to reduce the network lifetime degradation. If a cluster head fails, a backup cluster head is chosen as the next cluster head.

      Vertex cover problem is also called node cover problem belongs to one of Karp's 21 NP-complete problems. These problems are used to prove NP-hardness of complex problems in complexity theory. For solving NP-complete problem exactly, we need to find polynomial- time algorithm.

      There are two approaches to solve NP-completeness; one is to find an algorithm with an exponential running time for smaller inputs, or to identify near-optimal solutions in polynomial-time. In practice it is good to use near optimal solutions. Such algorithm is called as Approximation algorithm. Various algorithms are implemented for the solving vertex cover problem viz. Approximation algorithm, Greedy algorithm, Alom's algorithm, Genetic algorithm and many more [9]. An approximation algorithm for vertex cover problem is described by Coreman with time complexity O (E). In the real world, vertex cover problem has many useful applications. The solution vertex cover problem can be applied for terrorist communication network, airline network communication, Wireless sensor network, routing in a delay tolerant network, bi o-informatics and network traffic measurement [10].

      From the Fig. 2.1 (1, 3, 5, 6) shows the vertex cover of size 4. But this is not the smallest, we can have vertex cover of size 3, (2, 4, 5) or (1, 2, 4).

      Fig. 2.1 Example for Vertex Cover

      Vertex-Cover problem can also be used in wireless sensor networks to find the solution for communication problems. In coverage or communication problem, it is necessary to find minimum number or minimal set of sensor nodes which covers entire service area. Here, vertex cover set is nothing but the set of coverage sensor nodes which are used as communication sensors. In [11], author has used Genetic Algorithm to find the minimal vertex cover set which can used to solve coverage problem. The result shows that less-than 16 percent of nodes are used as communication sensors and 91 percent of service area is covered by these sensors.

   3. METHODOLGY

      In this paper, we consider WSN as an undirected graph G = (V, E) where V represents the set of vertices and E

      represents the set of edges. The degree of a vertex v, d (v), is the number of edges incident to v. The maximum degree of G is denoted by d. The input to the program is an n×n adjacency matrix. If there is an edge between u and v then adjacency matrix is set to 1 otherwise set to 0. A Vertex_Cover C of G is defined as the set of vertices which contains at least one end vertex of every edge. A vertex v is removable from C if and only if its removal still retains the vertex cover set C of G. the number of removable vertices of a vertex cover C is denoted by (C). A minimal_vertex_cover is a vertex cover with the less number of vertices that has no removable vertices [12].

      {

      Output <- C

      }

      Else

      {

      if (v has exactly one neighbour w outside C)

      Cv,w = C-{v} +{w}

      Rem_vertices(Cv,w) and output the resulting vertex cover

      }

      By using above algorithm we get the minimal vertex covers of size k. We can make these vertex covers as cluster heads in a wireless sensor networks. We can also reduce the size of k by the following algorithm:

      For each cluster heads {

      If C1 and C2 cluster heads are connected { C2 collects its neighbour data

      Send gathered data along with C2 data to C1 Unmark C2 as cluster head.

      Fig. 3.1 Wireless sensor network Fig. 3.2 Simplified model

      ALGORITHM: Vertex Cover Algorithm

      Input: A simple graph G with n vertices, vertex cover of size k.

      For i = 1 to n Ci = V{i}

      Rem_vertices(Ci)

      For r = 1 to nk

      Repeat Vertex_cover() r times. MinVC <- Ci

      For each pair of (Ci, Cj) found Ci, j = CiCj Rem_vertices(Ci, j)

      For r = 1 to nk

      Repeat Vertex_cover() r times MinVC <- Ci, j

      ALGORITHM: Rem_vertices()

      Input: An Un-directed graph G with n number of vertices and vertex-cover C

      If (no removable vertices in C)

      {

      Output<- C

      }

      Else

      {

      obtain the number of removable vertices (C{v})

      if (vmax), where vmax =maximum number of removable vertices then

      VC <- C{vmax}

      Repeat until there are no removable vertices in C

      }

      ALGORITHM: Vertex_cover()

      Input: An Un-directed graph G with n number of vertices and vertex-cover C

      If no vertex v in C has exact one neighbour w outside C

      }

      }

      Here, we check for each cluster heads. If two cluster heads are connected then allow one cluster head to collect its neighbor data and along with its own data send it to other cluster head. Unmark this node as clus ter head. By using this technique we can still more reduce the cluster head numbers and can obtain optimum number of cluster heads even for large networks. We have also showed the traversal order of cluster heads by first constructing minimum spanning tree for the cluster heads. We use Prims algorithm for constructing minimum spanning tree. We then have applied DFS algorithm to find the traversal order. Thus in context of WSN we can make the mobile sink to travel across these cluster heads to collect the data in a particular order.

   4. SIMULATION RESULTS

      Consider an undirected graph of 6 vertices's shown in Fig 4.1. The input to the program is given as 6×6 adjacency matrix and vertex cover of size 4. The following steps show the working of the algorithm:

      Fig. 4.1 Example Graph for Vertex cover

      Initially, C = {1, 2, 3, 4, 5, 6}. For i=1, delete the

      vertex 1, i.e., C1-{1}={2, 3, 4, 5, 6}. Now apply

      Rem_vertices() for C1={2, 3, 4, 5, 6}. Find the removable vertices from the graph. Since vertex 1 is removed from the

      graph we cannot remove the vertices 2, 3, 5, 6. Only possibility is to remove the vertex 4. When 4 is removable we cannot remove any other vertex in this case. In some cases there may be other removable vertices. Here, the number of removable vertices when 4 is removed is 0. Thus, Vmax = 0. When we remove 4 from C we get a vertex cover of required size 4. The final vertex cover set is C=

      {2, 3, 5, 6}. Thus we make 2 3 5 and 6 as cluster heads. Since cluster heads 2 and 3 are directly connected, we can retain any of these as cluster head. Allow 3 to collect its neighbor data from 4, 5 and 1. Now along with its own data and collected data send it to 2. Unmark 3 as cluster head. Similarly doing this for 5 and 6, the final optimized set of cluster heads include only 2 and 5.

      We have checked for optimized cluster heads by applying this algorithm for various numbers of nodes. The following table 4.1 shows the outcome of the result.

      Number of Nodes	Number of Cluster heads	Optimized cluster heads
      15	7	7
      35	20	12
      55	29	19
      75	39	26

      Table 4.1 Reduced number of cluster heads for different number of nodes.

      The simulation is carried out using NS-2 simulator with 15, 35, 55 and 75 numbers of sensor nodes and one sink node. We apply polynomial time vertex cover algorithm to all these number of sensor nodes to find the cluster heads of required size k. The following Table 4.1 shows the cluster heads obtained after executing the algorithm. The table 4.2 shows the simulation parameters used in this project:

      Parameter	Value
      Network area	200x200m2
      Number of sensor nodes	15, 35,55, 75
      Mobile sink speed	5 metre per second
      Packet length	512 bytes
      Energy of sensor node	100joules
      Simulation time	805 seconds
      Routing protocol	AODV

      The following figures show the analysis of various parameters for various number of nodes. Figure 4.2 shows that as the number of node increases the packet delivery fraction decreases. In figure 4.3 throughput is increasing for the increased nodes.

      Fig 4.2 Number of nodes vs PDR

      Fig 4.3 Number of nodes vs Throughput

      The figure 4.4 shows the average residual energy in joules of the network versus number of nodes. The residual energy is higher for different number of nodes.

      Fig 4.4 Number of nodes vs Avg Residual energy

      Fig . 4.5 Simulation of 35 nodes

   5. CONCLUSION

In this paper the vertex cover algorithm is given with varied number of nodes as input. As a result we obtain optimized number of cluster heads. Simulation is done for these numbers of nodes to visualize the process. The graph are plotted for various parameters and the results shows that by using this approach of clustering the residual energy is higher when compared to other approaches. We have also found the traversal order for mobile sink to visit the selected cluster heads. As a result vertex cover algorithm approach can also be used in wireless sensor networks.

REFERENCES

1. Ian F.Akiyildiz, Weilian Zu, A survey on sensor networks, IEEE communications magazine, August, 2002.

2. Arun A Somasundra, Aditya Ramamoorthy and Mani B Srivastava,Mobile Element Scheduling for Efficient Data Collection in Wireless Sensor Networks with Dynamic Deadlines, Proceedings of the 25th IEEE International Real-Time Systems Symposium (RTSS), IEEE, 2004.

3. Suchita R.Wankhade, Nekita A.Chavhan, A Review on Data Collection Method with sink Node in Wireless Sensor Network, International Journal of Distributed and Parallel Systems (IJDPS) Vol.4, No.1, January 2013.

4. X Li, A Nayak and Stojmenovic, Sink Mobility in Wireless Sensor networks, pp.153-184, Wiley, Hoboken, NJ, USA, 2010.

5. J Siva Prashanth, Satyanarayana V Nandury, Cluster-based Rendezvous Points Selection for Reducing Tour Length of Mobile Element in WSN, in IEEE International Advance Computing Conference (IACC), 2015.

6. M. Younis, and K. Akkaya, A survey on routing protocols for wireless sensor networks, Elsevier, Ad Hoc Networks, vol. 3, pp. 325349, 2005.

7. W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, An application-specific protocol architecture for wireless microsensor networks, IEEE Transactions on Wireless Communications, vol. 1, no. 4, 2002.

8. A. Maizate, N. El kamoun, A New Metric Based Cluster Head Selection Technique for Prolonged Lifetime in Wireless Sensor Networks, International Review on Computers and Software (I.RE.CO.S.), Vol. 8, n. 6.

9. Smit Patel, Sowmya Kamath S, Improved Approximation Algorithm for Vertex Cover Problem using Articulation Points, 5th ICCCNT 2014 July 11-13, 2014, Hefei, China, IEEE 33044.

10. http://www.gdeepak.com/thesisme/thesis- Choosing%20the%20Efficient%20Algorithm%20for%20Vertex%20 Cover%20problem.pdf

11. Maytham Safar, Mohammad Taha and Sami Habib, Modeling the communication problem in wireless sensor networks as a vertex cover, IEEE, 2007.

12. http://www.dharwadker.org/vertex_cover.