混合WSN中的单层约束中继节点放置研究

针对混合无线传感器网络中的中继节点放置问题,提出了一种满足一定的连通性和生存性要求的最小数量中继节点放置算法,其中中继节点只能放置到候选位置的一个子集上。在连接中继节点的放置问题中,提出一种采用基于最小生成树的STP高效近似算法,以保证传感器节点和基站之间的连通性;在可生存中继节点的放置问题中,提出了基于{0,1,2}-SNDP的多项式时间近似算法,以保证传感器节点和基站之间的双连通性。实验结果表明,单层约束中继节点放置算法具有较小的运行时间和几乎可以达到与最优解结果相媲美的性能.

Research on single tiered constrained relay node placement in hybrid WSN

To solve the problem of relay node placement in hybrid wireless sensor networks, a minimum number of relay nodes placement algorithm is proposed in this paper to meet certain requirements of connectivity and survivability, where relay nodes can only be placed on a subset of candidate locations. In the connected relay node placement problem, an efficient STP approximation algorithm based on minimum spanning tree is proposed to ensure the connectivity between sensor nodes and base stations. In the survivable relay node placement problem, a polynomial time approximation algorithm based on {0,1,2} SNDP is proposed to ensure the bi connectivity between sensor nodes and base stations. Experimental results show that the proposed single tiered constrained relay node placement algorithm has a smaller running time and can almost achieve the performance comparable to the optimal solution.