Weighted graph matching is one of the most fundamental graph theoretical problems used in network design, especially in wireless network services such as radio resource allocation, physical layer security, energy-efficient partner selection and optimizing storage capacity. In this paper we present a distributed heuristic which provides nearly-optimal weighted matchings in polynomial time. We also propose an algorithm to decrease the number of transmitted messages to provide energy-efficient operation. Our approaches assume the asynchronous communication model and small messages having O(log (n)) bits. These assumptions directly fit the battery powered wireless networks such as wireless ad hoc and sensor networks. To the best of our knowledge, we propose the first distributed weighted matching algorithm which benefits from augmentation of augmenting paths having size larger than 3 for these networks. We also provide results of our simulations on synthetic geometric graphs to model wireless networks. Extensive simulations reveal that our algorithm improves the approximation performances of the other weighted matching algorithms and closes the gap between the approximation ratio and the optimum up to 32%.

We present the first self-stabilizing algorithm for finding a maximal b-matching in arbitrary networks and under distributed unfair (adversarial) schedulers. The previous self-stabilizing b-matching algorithm presented by Goddard et al. in 2003 assumes central scheduler. We give proof for the correctness of our new algorithm for both unfair and fair schedulers, as well as the synchronous scheduler. Our algorithm stabilizes in O(Bm) steps under unfair scheduler and in O(n) rounds under distributed fair and synchronous schedulers, where n, m and B are the number of processors, the number of edges and the maximum capacity in the graph, respectively. The time complexity of distributed fair version of our algorithm is better than that of the transformation of Goddard et al.'s sequential self-stabilizing algorithm to the distributed fair one with the conflict manager of Gradinariu and Tixeuil (2007).

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.

Matching problem has been attracting a growing attention in network design, especially in wireless communication networks. Although there is an exact polynomial-time sequential algorithm for the weighted version of the problem, all the related distributed algorithms are approximation algorithms. In this paper we present a distributed heuristic which improves the weight of a given matching in time proportional to the number of nodes. Our algorithm assumes the asynchronous communication model in which the message size is limited to O (log n) bits. To the best of our knowledge, it is the first distributed weighted matching algorithm which benefits from augmentation of alternating paths having size larger than 3 and uses small messages. We also provide results of our simulations on random geometric graphs. Computational results show that our algorithm improves the approximated solutions of other weighted matching algorithms roughly by 1-3% and closes the gap between the approximation ratio and the optimum solution by 9-26%.

Self stabilization is an important paradigm for the autonomous recovery of a distributed system from transient failures such as energy depletion of nodes and disrupted connections. It has been used in wireless sensor networks (WSN) as these networks are expected to automatically recover from a transient fault without human intervention. Graph matching is fundamental a graph theory problem which has a broad application range in WSNs and it has been studied extensively in self-stabilizing settings. In this work, we build a simulation model and perform tests to evaluate the fault tolerance properties of self-stabilizing matching algorithms. To the best of our knowledge, this is the first practical evaluation of these algorithms. Considering WSNs, we assume distributed fair and synchronous schedulers. Simulation results have shown that there is a tradeoff between stabilization time of algorithms and the quality of their results. The improvement algorithms which has better lower bounds give better matchings at the cost of longer durations of instability.

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(n² 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.

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.