A Variant of Connected Dominating Set for Application in Communication Networks
Loading...
Date
2015-03-30
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
CERIST
Abstract
This paper considers a variant of the connected
dominating set (CDS) problem in a graph G = (V;E). The
considered problem consists in minimizing the number of CDS
vertices that belong to a subset V ′ in V . As far as we know,
this problem has not been treated in the literature. Nevertheless,
its resolution would be useful in many communication network
applications, such as the selection of relay nodes in heterogenous
wireless ad hoc networks where only a subset of powerful nodes
(e.g., energy or memory rich nodes) may form the network
backbone act as relays, or where it is preferable to select relays
from these nodes and minimize the number of non-powerful
nodes that act as relays. Replacement of non-powerful nodes
might be necessary either at the initialization (after deployment),
or during the network lifetime, which justifies the need to
minimize their number. The problem is first modeled and reduced
to the minimum weighted connected dominating set (WCDS)
problem in a vertex weighted graph, and then it is resolved by
taking advantage of the simple form of the weight function using
integer linear programming (ILP). A heuristic is also proposed
for large scale resolution. Simulation results confirms closeness
of the proposed heuristic to the optimal solution obtained by the
ILP, and scalability of the heuristic.
Description
Keywords
Graph theory applications, minimum dominating set