Browsing by Author "Shetty, D.P."

Now showing 1 - 5 of 5

Algorithms for minimizing the receiver interference in a wireless sensor network
(2016) Shetty, D.P.; Lakshmi, M.P.
Limiting Interference between the nodes in a Wireless Sensor Network (WSN) is of considerable importance for energy-efficiency of the network. Minimizing the interference in a WSN minimizes the overall energy consumption of the network by reducing the number of conflicting transmissions. We consider Receiver interference minimization problem. Two types of interference are defined in a WSN, namely Sender interference and Receiver interference. In this paper we consider the Receiver interference problem, where the objective is to minimize the maximum Receiver interference. The problem of minimizing the maximum Receiver interference is proved to be NP-hard. In this paper we propose two algorithms named MinMax-RIP and a modified version of the same to minimize the maximum Receiver interference in a WSN. We evaluate the performance of our algorithms through simulation. We then consider the interference minimization problem in a broadcast network. We propose MinMax-BRIP algorithm for optimal range assignment which gives minimum total Receiver interference for connectivity predicate Broadcast. � 2016 IEEE.
Approximation algorithm for receiver interference problem in dual power Wireless Sensor Networks
(2019) Shetty, D.P.; Lakshmi, M.P.
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.
Approximation algorithms for minimum power k backbone node r -connected subgraph problem in wireless sensor networks
(2019) Shetty, D.P.; Lakshmi, M.P.
The minimum power assignment problem in a Wireless Sensor Network (WSN) is to assign transmission range to the nodes of the network with specified connectivity constraints minimizing the total power. This problem is termed as Strong Minimum Energy Topology (SMET) problem. Fault tolerance addresses the issue of a node or link failure in a WSN. So, with an objective of achieving high connectivity, we consider SMET problem with an additional property, i.e., the resultant network must satisfy the property of two or high connectivity. Minimum Power r-Connected Subgraph (MPrCS) problem is to contrive an r-connected network with minimum power. Minimum Power 2-Connected Subgraph (MP2CS) problem is proved to be NP-hard. Minimum Power k Backbone node r-Connected Subgraph (MPkBrCS) problem is a special case of MPrCS problem, which seeks a power assignment satisfying r-connectivity with k backbone nodes. We study MPkBrCS problem for k backbone nodes, r-connectivity and derive the approximation ratios. We also propose an algorithm of approximation ratio n+2 2, for Minimum Power k Backbone node 3-Connected Subgraph (MPkB3CS) problem for k = 2 that runs in O(n4) time and generalize for the case r = k + 1 for any k and r. 2020 World Scientific Publishing Company.
K-distinct strong minimum energy topology problem in wireless sensor networks
(2015) Panda, B.S.; Shetty, D.P.; Pandey, A.
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.
Total Power Minimization Using Dual Power Assignment in Wireless Sensor Networks
(2016) Sisodiya, N.; Shetty, D.P.
To minimize the energy consumption in a wireless sensor network (WSN) is very important task as the sensors are generally very small and have a power battery attached to it which cannot have very large power capacity. In a wireless sensor network any sensor node must be able to retrieve information from any other sensor node in the network, so the connectivity of the network is also very important concern. The range assignment problem in WSN is to assign transmission power levels to the nodes of a WSN such that some constraints like connectivity is satisfied. In practice it is usually impossible to assign arbitrary power levels to the sensor nodes in a wireless sensor network. Most sensors available in the market operate with discrete power levels. So in this paper we consider the sensor nodes with only two possible power levels assigned to them. Our aim is to minimize the total power consumption while maintaining the strong connectivity between the sensor nodes in the network. We present a nearly optimal heuristic algorithm and also the experimental results. Our SCDPA algorithm gives an average approximation of 1.51. We also present a heuristic algorithm to minimize total power using 3 power levels. � 2015 IEEE.