Faculty Publications
Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736
Publications by NITK Faculty
Browse
2 results
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 Improved Algorithm for Minimum Power 2-Connected Subgraph Problem in Wireless Sensor Networks(Institute of Electrical and Electronics Engineers Inc., 2018) Lakshmi, M.; Shetty D, D.A Wireless Sensor Network (WSN) consists of small sensor nodes which communicate with each other using wireless radio channel and are used to monitor certain environmental parameters. Since the nodes are powered by a small battery of limited capacity, it is important to minimize the energy consumption in a WSN. By using an appropriate topology the energy utilization of the network can be minimized which results in an increased lifetime of a WSN. In practice, the transmission power of a sensor node can be tuned to obtain a required topology that satisfies certain connectivity constraints and this problem is known as Range Assignment Problem. For a given network, a reduced topology is constructed satisfying some connectivity constraints like k-connectivity, bounded diameter etc. Fault tolerance addresses the issue of node or link failure which aims at k-connectivity so that, the network has at least k vertex disjoint paths between any two nodes of the network. With the motivation of achieving fault tolerant network with minimum transmission energy, we consider Minimum power 2-connected subgraph (MP2CS) problem which is proved to be NP-hard. A polynomial time heuristic is proposed in this paper for the MP2CS problem and simulation is performed to compare with the existing algorithm. © 2018 IEEE.