2015 | OriginalPaper | Chapter
k-Distinct Strong Minimum Energy Topology Problem in Wireless Sensor Networks
Authors : Bhawani Sankar Panda, D. Pushparaj Shetty, Arti Pandey
Published in: Distributed Computing and Internet Technology
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a set of sensors, the strong minimum energy topology (SMET) problem is to assign transmit power to each sensor such that the resulting topology containing only bidirectional links is strongly connected and the total energy of all the nodes is minimized. The
SMET
problem is known to be
NP
-hard. Currently available sensors in the market support a finite set of transmission ranges. So we consider the
k
-
Distinct-SMET
problem, where only
k
transmission power levels are used. We prove that the
k
-
Distinct-SMET
problem is
NP
-complete for
k
≥ 3. However, on the positive side, we show that the 2-
Distinct-SMET
problem can be solved in polynomial time. The energy cost of transmitting a bit is higher than the cost of computation, and hence it may be advantageous to organize the sensors into clusters and form a hierarchical structure. This motivated the study of
k
-Distinct-
r
Strong Minimum Energy Hierarchical Topology (
k
-Distinct-
r
SMEHT) problem:
Given a sensor network consisting of
n
sensors, and integers
k
and
r
, assign transmit powers to all sensors out of the
k
distinct power levels such that (
i
) the graph induced using only the bi-directional links is connected, (
ii
) at most
r
sensors are connected to two or more sensors by a bidirectional link and (
iii
) the sum of the transmit powers of all the sensors is minimum. We Propose a
$\frac{r+1}{2}$
- approximation algorithm for the
k
-Distinct-
r
SMEHT problem for any fixed
r
and arbitrary
k
.