Minimum Range Assignment Problem for Two Connectivity in Wireless Sensor Networks

摘要

A wireless sensor network (WSN) is modeled as weighted directed graph, with each sensor in the plane representing a vertex. The edges represent the link between two sensors. A cost function c : E → R~+ is associated with each edge E. The power of a node v is the maximum cost of its incident edges. The sum of powers of all nodes v ∈ V is the total power of the graph. A graph G = (V, E) is 2-connected and remains connected even if any one node is deleted from the graph. Fault tolerance is an important property of a network, which demands two or higher connectivity. In this paper we consider the problem of assigning transmit power to the nodes of a WSN, such that the resulting topology is two node-connected and the the total power of the network is minimized. The minimum power two-connected subgraph (MP2CS) problem is known to be NP-hard. We give a polynomial reduction from strong minimum energy topology problem to MP2CS problem. This leads to an alternate NP-hard proof for MP2CS problem. We propose a heuristic for MP2CS, which is based on MST augmentation. Through simulation we show that the proposed heuristics performs better than the existing heuristic for MP2CS problem. We then consider a special case of MP2CS problem, called the minimum power k backbone 2-connected subgraph(MPκB2CS) problem. We prove that MPκB2CS problem can be solved optimally in O(n~3) time for κ = 2, and propose a 2-approximation algorithm for κ = 3. We show that MPκB2CS problem admits an approximation algorithm with approximation ratio 3(κ+1)/2 for κ ＞ 3.