Strong minimum energy hierarchical topology in wireless sensor networks

Given a set of \(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\)-strong minimum energy hierarchical topology (\(k\)-SMEHT) problem. Given a set of \(n\) sensors and an integer \(k\), the \(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\) 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\) is minimum. We show that \(k\)-SMEHT problem is NP-hard for arbitrary \(k\). However, we propose a \(\frac{k+1}{2}\)-approximation algorithm for \(k\)-SMEHT problem, when \(k\) is a fixed constant. Finally, we propose a polynomial time algorithm for the \(k\)-SMEHT problem for \(k=2\).