Approximation algorithms for minimum power k backbone node r-connected subgraph problem in wireless sensor networks

Abstract

The minimum power assignment problem in a Wireless Sensor Network (WSN) is to assign transmission range to the nodes of the network with specified connectivity constraints minimizing the total power. This problem is termed as Strong Minimum Energy Topology (SMET) problem. Fault tolerance addresses the issue of a node or link failure in a WSN. So, with an objective of achieving high connectivity, we consider SMET problem with an additional property, i.e., the resultant network must satisfy the property of two or high connectivity. Minimum Power r-Connected Subgraph (MPrCS) problem is to contrive an r-connected network with minimum power. Minimum Power 2-Connected Subgraph (MP2CS) problem is proved to be NP-hard. Minimum Power k Backbone node r-Connected Subgraph (MPkBrCS) problem is a special case of MPrCS problem, which seeks a power assignment satisfying r-connectivity with k backbone nodes. We study MPkBrCS problem for k backbone nodes, r-connectivity and derive the approximation ratios. We also propose an algorithm of approximation ratio n+2 2, for Minimum Power k Backbone node 3-Connected Subgraph (MPkB3CS) problem for k = 2 that runs in O(n4) time and generalize for the case r = k + 1 for any k and r. © 2020 World Scientific Publishing Company.