Strong minimum energy hierarchical topology in wireless sensor networks

Given a set of $$n$$ n sensors, the strong minimum energy topology (SMET) problem in a wireless sensor network is to assign transmit powers to all sensors such that (i) the graph induced only using the bi-directional links is connected, that is, there is a path between every pair of sensors, and (ii) the sum of the transmit powers of all the sensors is minimum. This problem is known to be NP-hard. In this paper, we study a special case of the SMET problem, namely , the $$k$$ k -strong minimum energy hierarchical topology ( $$k$$ k -SMEHT) problem. Given a set of $$n$$ n sensors and an integer $$k$$ k , the $$k$$ k -SMEHT problem is to assign transmission powers to all sensors such that (i) the graph induced using only bi-directional links is connected, (ii) at most $$k$$ k nodes of the graph induced using only bi-directional links have two or more neighbors, that is they are non-pendant nodes, and (iii) the sum of the transmit powers of all the sensors in $$G$$ G is minimum. We show that $$k$$ k -SMEHT problem is NP-hard for arbitrary $$k$$ k . However, we propose a $$\frac{k+1}{2}$$ k + 1 2 -approximation algorithm for $$k$$ k -SMEHT problem, when $$k$$ k is a fixed constant. Finally, we propose a polynomial time algorithm for the $$k$$ k -SMEHT problem for $$k=2$$ k = 2 .