On the construction of k‐connected m‐dominating sets in wireless networks

On the construction of k‐connected m‐dominating sets in wireless networks

0.00 Avg rating0 Votes
Article ID: iaor2012241
Volume: 23
Issue: 1
Start Page Number: 118
End Page Number: 139
Publication Date: Jan 2012
Journal: Journal of Combinatorial Optimization
Authors: , , ,
Keywords: graphs, combinatorial optimization, heuristics, simulation: applications
Abstract:

Connected dominating sets (CDS) that serve as a virtual backbone are now widely used to facilitate routing in wireless networks. A k‐connected m‐dominating set (kmCDS) is necessary for fault tolerance and routing flexibility. In order to construct a kmCDS with the minimum size, some approximation algorithms have been proposed in literature. However, the proposed algorithms either only consider some special cases where k=1, 2 or km, or not easy to implement, or cannot provide performance ratio. In this paper, we propose a centralized heuristic algorithm, CSAA, which is easy to implement, and two distributed algorithms, DDA and DPA, which are deterministic and probabilistic methods respectively, to construct a kmCDS for general k and m. Theoretical analysis and simulation results indicate that our algorithms are efficient and effective.

Reviews

Required fields are marked *. Your email address will not be published.