k-Connected m-Dominating Set Based Fault-Tolerant Virtual Backbone: A Survey

Abstract

Virtual backbone is employed to facilitate routing in ad hoc networks, which lack the physical infrastructure.
In these networks, node and link failure are a common phenomenon, which makes the virtual backbone vulnerable. Even
if any one of the backbone nodes fail, the virtual backbone is prone to break which ultimately breaks the network. Hence,
the virtual backbone needs to have some sort of fault-tolerance capability which will help it to function even during node
and link failures.k-Connected m-Dominating Set (kmCDS) has been used in the literature to construct fault-tolerant
virtual backbones. kmCDS based virtual backbone structures can withstand upto k – 1 path failures and m – 1 dominator
failures, and thereby the fault-tolerance capability of the network is enhanced. This paper focuses on the various kmCDS
construction algorithms that have been put forth in the literature. A comparison of the major works is provided,
emphasizing the technique used, k-factor and m-factor combination, performance metric used, algorithms proposed and
their outcome.