Minimum 2-connected distance-k p-dominating set in wireless sensor networks

In wireless sensor networks connected dominating sets are often used to form a virtual backbone. However, a connected dominating set is often vulnerable due to frequent node failures in sensor networks. Hence, to provide a degree of fault-tolerance, we consider a 2-connected distance-k p-dominating set, denoted D_2;k;p, as a virtual backbone for wireless sensor networks. Ideally, the backbone should constitute the smallest percentage of nodes in the network. To find a minimum D_2;k;p in unit disk graphs as well as in general graphs is of unknown complexity. We propose two centralized approximation algorithms to construct a D_2;k;p in unit disk graphs as well as in general graphs.