ACDS: Adaptive Topology Construction for R-random Sensor Deployment in Wireless Sensor Networks

Connected Dominating Set (CDS) could be used to construct virtual backbone as topology control scheme in Wireless Sensor Networks (WSNs). As recent studies show, k-Connected k-Dominating Set (kCDS) enhances robustness of virtual backbone by forming k-path virtual backbone instead of single-path. On the other hand, sensor nodes positions affect the operation and performance of WSNs. In R-random node deployment approach sensor nodes are deployed in network area non-uniformly, with high density around the sink. Multi-path schemes are desirable solutions in sparse network regions to achieve energy efficiency and in the meantime preserve a reasonable level of fault tolerance in dense regions. However, since in existing multi-path schemes it is assumed that k is constant, they lose flexibility of operation in heterogeneous density scenarios. As a result, if kCDS is employed to construct topology of WSNs with non-uniform node deployment, using adaptive k (i.e., the number of paths) is more efficient rather than constant k. In this article, we propose a new approach for constructing kCDS which takes into account node density to adaptively tune number of paths. As simulation results show, our proposed mechanism renders better trade-off between virtual backbone robustness and energy efficiency in WSNs with R-random node deployment.