Vertex cover (VC) is one of the most fundamental graph-theoretical problems and has been widely used in wireless sensor networks (WSNs), particularly for the link monitoring problem. It is well known that a solution to the independent set problem (IS), which is another fundamental graph-theoretical problem, is complement of a VC. Self- stabilization is an important concept for designing fault tolerance systems. There have been many self-stabilizing VC and IS algorithms in the field. Even though a self-stabilizing IS algorithm can provide VC solutions, it does not give a theoretical guarantee on approximation ratio. In this work, we focus on practical fault tolerance performance of self- stabilizing IS algorithms in case of a vertex cover problem, particularly link monitoring in WSNs. We implement all existing self-stabilizing VC and IS algorithms and make simulations assuming a WSN in which nodes run synchronously. Results show that self-stabilizing IS algorithms in general are able to find better covers than VC algorithms, as they provide roughly 15% smaller solution sets. Furthermore, IS algorithms that run under distributed scheduler converges to a desired configuration in considerably less number of rounds than VC algorithms.
Graph matching is a fundamental graph theory problem which has a broad application range including information retrieval, pattern recognition, graph partitioning, chemical structure analysis, protein function prediction, backup placement and cellular coverage. This problem has gained attention in distributed computing as there are distributed matching algorithms with asymptotically guaranteed time bounds and approximation ratios. On the other side, we do not know the practical performance of these algorithms. In this paper, we provide a detailed performance evaluation of asynchronous distributed maximum weighted matching (MWM) algorithms. We assume a message-passing system in CONGEST model in which the message size is limited to O(log n) where n is the number of nodes. This model is popular for energy-efficient networks such as wireless sensor networks. We used a discrete event simulator, SimPy, to model the assumed network structures. We provide the implementations of Watthenhofer and Wattenhofer's algorithm, Hoepman's algorithm, Lotker et al.'s algorithm and Lotker et al.'s improvement algorithm. The results show that the greedy algorithm of Hoepman performed best in approximating the optimum result in all types of networks, even achieving an approximation ratio of 0.99 in some instances. To the best of our knowledge this is the first study which provides an extensive performance evaluation of distributed MWM algorithms.
Devices running on Wireless Sensor Networks (WSNs) generally have limited energy resources, which makes it important to design energy-aware algorithms. Capacitated Minimum Spanning Tree (CMST) algorithms can be designed for finding energy-aware routing paths and for load-balancing among sub-trees connected to the sink device. Despite being studied extensively in central settings, there has not been any energy-efficient algorithm for the WSNs. The bit complexity of applying a central approach in the sink node is O(n2 logn) bits on a network having n nodes. In this work, we present the design of an algorithm which aims to solve CMST problem in WSNs and is based on Esau-Williams (E-W) algorithm. The bit complexity of the proposed algorithm is O(nlogn) bits. We compare the performance of the algorithm with the straightforward implementation of E-W where the problem is solved by the sink node and the result is sent to the other nodes. According to the computational results, our algorithm is more efficient than this version with respect to the energy consumption. Our algorithm (MCO) consumes up to 3 times less energy than central algorithm.
An undirected graph can be represented by G(V,E) where V is the set of vertices and E is the set of edges connecting vertices. The problem of finding a vertex cover (VC) is to identify a set of vertices VC such that at least one endpoint of every edge in E is incident to a vertex V in VC. Vertex cover is a very important graph theoretical structure for various types of communication networks such as wireless sensor networks, since VC can be used for link monitoring, clustering, backbone formation and data aggregation management. In this chapter, we will define vertex cover and related problems with their applications on communication networks and we will survey some important distributed algorithms on this research area.