Please use this identifier to cite or link to this item:
Title: Approximation algorithm for receiver interference problem in dual power Wireless Sensor Networks
Authors: Shetty, D.P.
Lakshmi, M.P.
Issue Date: 2019
Citation: Journal of Applied Mathematics and Computing, 2019, Vol.61, 43862, pp.87-99
Abstract: The problem of assigning power levels to the nodes of a wireless sensor network from a given a set of two power levels is called Dual power management problem and the underlying network is called Dual power network. We consider the problem of minimizing the maximum receiver interference of such a network. The interference disrupts the communication and forces the data packets to be retransmitted. The motivation is to conserve the energy by minimizing the interference and maintaining the connectivity of the dual power network. Receiver interference problem is proved to be NP-hard. In this paper, an approximation algorithm is derived for minimizing the maximum receiver interference of a dual power network by utilizing the approximation algorithm for Dual Power Management Problem. The proposed algorithm is supported by the simulation results. We term this problem as Dual Power Receiver Interference Problem and show that it is NP-complete using a polynomial time reduction from Degree Constrained Minimum Spanning Tree problem. We also prove the NP-completeness of Dual Power Management Problem by a polynomial reduction from Vertex Cover Problem. 2019, Korean Society for Computational and Applied Mathematics.
Appears in Collections:1. Journal Articles

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.