Fault-Tolerant Relay Node Placement Problem With Base Stations In Wireless Sensor Networks

In two tiered wireless sensor network (2tWSN), it has been proposed to deploy relay nodes, such that relay nodes are responsible for delivering the sensed data from sensor nodes to base stations, which makes the structure of wireless sensor network infrastructure more flexible and help prolong wireless sensor networks lifetime a lot ultimately. From the perspective of business, it requires more relay nodes to ensure network connectivity so as to improve the fault tolerance in wireless sensor network. 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 focus on fault tolerant relay node placement (RNP) problem while ensuring suitable economic condition. Firstly, we model fault tolerant RNP problem in two-tiered wireless sensor network with base station as a graphic problem, denoted by Diff-B node and Y node hybrid communication graph (DBY-HCG). It distinguishes the difference between relay nodes and base stations, declines the extra consume brought by total nodes’connectivity requirement. Moreover, DBY-HCG is constrain independent. Secondly, on the basis of DBY-HCG and basic infrastructure raised above, we conduct research on proof of approximation ratio and algorithm scalability on different requirement of fault tolerance respectively. On the one hand, we figure out a multi-coverage bi-connectivity RNPB approximation and prove the approximation ratio to be (18+(?)) in detail, which is comparatively enhanced. And the number of relay nodes deployed using this algorithm is expected to be superior to existed relay node placement solutions.On the other hand, for algorithm’s extensibility and practicality, we figure out keCi-RNPB approximation algorithm in order to ensure multi-coverage and k-connectivity. Moreover, an algorithm aiming at finding the minimum length of k-vertex disjoint paths in bipartite graph is raised up to support our algorithm’s extensibility. As we found our algorithm is the first k-extended solution for constrained version of fault tolerant relay node placement problem in two-tiered WSN. Finally, extensive experiments have been executed in both unconstrained and constrained situations and the numeric results show that our solutions put forward above are both close to optimal solution in corresponding scenarios and superior to existed researches.