Please use this identifier to cite or link to this item: https://idr.l4.nitk.ac.in/jspui/handle/123456789/8382
Title: K-distinct strong minimum energy topology problem in wireless sensor networks
Authors: Panda, B.S.
Shetty, D.P.
Pandey, A.
Issue Date: 2015
Citation: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2015, Vol.8956, , pp.187-192
Abstract: 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-rStrong Minimum Energy Hierarchical Topology (k-Distinct-rSMEHT) 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(formula presented.) approximation algorithm for the k-Distinct-rSMEHT problem for any fixed r and arbitrary k. � Springer International Publishing Switzerland 2015.
URI: http://idr.nitk.ac.in/jspui/handle/123456789/8382
Appears in Collections:2. Conference Papers

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.