Performance Evaluation of Capacitated Vertex Cover Algorithms for Security Applications in Wireless Sensor Networks

Monitoring the links of wireless sensor networks (WSNs) is a very crucial operation to detect security attacks targeted to the legitimate nodes in internet of things. To achieve this, identifying the monitor nodes (secure points) among the nodes in a WSN and assigning their links are of utmost importance. Vertex cover is a popular problem in the areas of graph theory, approximation algorithms and optimization. Vertex coveris a set of nodes where an edge (link) is incident to at least one of nodes in this set. Hence, vertex cover can be used as the set of the monitor nodes. Capacitated vertex cover, which restricts the edge count that a node can cover, is a specialized version of the vertex cover problem. It provides energy-efficient link monitoring by restricting the link count. In this study, we evaluate capacitated vertex cover algorithms in terms of the cardinality of vertex cover, running time, and approximation ratio. To the best of our knowledge, this is the first evaluation in this manner. Firstly, we theoretically analyze the capacitated vertex cover algorithms, then implement these algorithms in SageMath language that is utilized for solving linear programming and mathematical problems. From our obtained extensive measurement results, we reveal that Naor 8-approximation algorithm performs best having the lowest approximation ratio with 1.13 by selecting 1.12 times fewer vertices in the feasible execution time, although its approximation ratio is worse than the others.