Paper Info
Title
Strong minimum energy hierarchical topology in wireless sensor networks
Abstract
Given a set of 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 -strong minimum energy hierarchical topology (-SMEHT) problem. Given a set of sensors and an integer , the -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 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 is minimum. We show that -SMEHT problem is NP-hard for arbitrary . However, we propose a -approximation algorithm for -SMEHT problem, when is a fixed constant. Finally, we propose a polynomial time algorithm for the -SMEHT problem for .
Year
DOI
Venue
2016
10.1007/s10878-015-9869-7
J. Comb. Optim.
Keywords
Field
DocType
Sensor networks,Topology control problem,Graph algorithms,NP-complete,Approximation algorithms
Integer,NP-complete,Time complexity,Special case,Approximation algorithm,Graph algorithms,Discrete mathematics,Topology,Graph,Mathematical optimization,Combinatorics,Wireless sensor network,Mathematics
Journal
Volume
Issue
ISSN
32
1
1382-6905
Citations 
PageRank 
References 
0
0.34
19
Authors
2
Name
Order
Citations
PageRank
B. S. Panda19921.18
D. Pushparaj Shetty2163.75