Faculty Publications
Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736
Publications by NITK Faculty
Browse
Search Results
Item Construction of minimum power 3-connected subgraph with k backbone nodes in wireless sensor networks(Springer International Publishing, 2019) Shetty D, D.; Lakshmi, M.Minimizing the total power in a wireless sensor network (WSN) has great significance, since the nodes are powered by a small battery of limited capacity. By using an appropriate topology, the energy utilization of the network can be minimized which results in an increased lifetime of a WSN. In reality, WSN is modeled as an undirected graph in which each vertex represents a sensor node and an edge represents the link between the two sensor nodes. We define a distance function that maps a pair of vertices to a positive real number, i.e., Euclidean distance between the two vertices. On this initial topology, we construct a reduced topology satisfying special connectivity constraints like bi-connectivity, k-connectivity, bounded diameter, degree restricted, etc. We assign power to each node as the maximum distance of all its adjacent edges, and total power of the network is the sum of the powers of all the vertices. Fault tolerance addresses the issue of a node or link failure in a WSN. Fault-tolerant network aims at k-connectivity in the network so that there exist at least k vertex disjoint paths between any two sensor nodes of the network. Minimum power 2-connected subgraph (MP2CS) problem is to contrive a 2-connected network with minimum total power. It is proved that MP2CS problem is NP-hard. Minimum power k backbone node 2-connected subgraph (MPkB2CS) problem is a special case of MP2CS problem, which seeks a power assignment satisfying 2-connectivity with k backbone nodes. In this paper, the problem of finding a 3-connected network for a given set of nodes, which minimizes the total power with k backbone nodes, is addressed which is termed as MPkB3CS problem. We propose an algorithm for MPkB3CS problem and establish that the proposed algorithm has an approximation ratio of 4k + 1, for k ≥ 3. © Springer Nature Switzerland AG 2019.Item Minimizing the total range with two power levels in wireless sensor networks(Springer Verlag service@springer.de, 2019) Shetty D, D.; Lakshmi, M.Minimizing the total energy consumed by wireless sensor network (WSN) is a significant problem, since the sensor nodes are attached with a small battery of restricted capacity. In a WSN, any pair of sensor nodes must be able to communicate with each other in the network, so bidirectional connectivity of WSN is an important characteristic to be achieved. The range assignment problem in a WSN aims to assign transmission range to each sensor node of the network such that the specified connectivity constraints such as strong connectivity, k-connectivity are to be satisfied by the reduced network. Most sensors in recent days operate with discrete power levels. So, in this paper, we consider the range assignment problem with two power levels. Our aim is to assign each sensor node in the network with one of the available set of power levels such that the reduced topology is strongly connected and the total power consumption is minimized. The dual power assignment problem is well studied in the literature. We present an improved algorithm for dual power assignment problem in which the power levels are taken as input. Performance of the proposed algorithms is analyzed through extensive simulation. We establish the theoretical approximation ratio bound of the proposed algorithm for dual power assignment problem as 2. But, the simulation results indicate that the performance ratio is much less than 2. © 2019, Springer Nature Singapore Pte Ltd.Item Minimizing the maximum sender interference by deploying additional nodes in a wireless sen- sor network(Indonesian Combinatorics Society ebaskoro@math.itb.ac.id, 2019) Shetty D, D.; Lakshmi, M.Interference is one of the major challenges faced by communication networks. Since the inter- ference leads to packet loss, packet collision and data re-transmission, higher the interference, higher is the energy consumption. Several algorithms were proposed for reducing the interference in a wireless sensor network (WSN). By deploying additional nodes at an appropriate position in a WSN, it is possible to reduce the interference. We propose an algorithm in which, the main objective is to reduce the maximum Sender interference by deploying the additional nodes in the network, while the connectivity of the network is preserved. We use the properties of Gabriel graph to achieve the reduction in interference. We present the simulation results which show the number of additional nodes to be deployed. The comparison of the maximum Sender interference obtained by the proposed algorithm with that of the Euclidean minimum spanning tree (MST) of the given network is presented through simulation. We show that the additional number of nodes required for deployment has an upper bound of n=2, where n is the number of nodes. We also compute the average reduction in Sender interference of the network for a various number of nodes. © 2019 Indonesian Combinatorics Society.