  Vertex covering has important applications for wireless sensor networks such
as monitoring link failures, facility location, clustering, and data
aggregation. In this study, we designed three algorithms for constructing
vertex cover in wireless sensor networks. The first algorithm, which is an
adaption of the Parnas & Ron's algorithm, is a greedy approach that finds a
vertex cover by using the degrees of the nodes. The second algorithm finds a
vertex cover from graph matching where Hoepman's weighted matching algorithm is
used. The third algorithm firstly forms a breadth-first search tree and then
constructs a vertex cover by selecting nodes with predefined levels from
breadth-first tree. We show the operation of the designed algorithms, analyze
them, and provide the simulation results in the TOSSIM environment. Finally we
have implemented, compared and assessed all these approaches. The transmitted
message count of the first algorithm is smallest among other algorithms where
the third algorithm has turned out to be presenting the best results in vertex
cover approximation ratio.

Distributed, Parallel, and Cluster Computing;Networking and Internet Architecture