Improved Algorithm for Minimum Power 2-Connected Subgraph Problem in Wireless Sensor Networks

Abstract

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.