K-Extended Constrain Independent Relay Node Placement with Base Stations in Two-Tiered Wireless Sensor Network

In 2tWSN(two-tiered wireless sensor network), relay nodes are responsible for delivering the sensed data from sensor nodes to base stations. From the perspective of business, it needs more relay nodes to ensure network connectivity. From the perspective of economy, relay nodes are relatively expensive, so people are intended to place a minimum number of relay nodes while guaranteeing the data collecting and delivering. In this paper, we firstly model fault tolerant RNP(relay node placement) problem in 2tWSN as a graphic problem, denoted by DBY-HCG. It distinguishes relay nodes from base stations. Secondly, we figure out keCi-RNPB algorithm. Moreover, an approximation algorithm aiming at finding the minimum length of k-vertex disjoint paths in connected sub-graph is raised up to support our algorithm´s extensibility. Our algorithm is also the first solution for constrained version of fault tolerant relay node placement problem in 2tWSN. Extensive experiments have been executed in both unconstrained and constrained situations and the numeric results show that our solution is close to optimal solution.