连通度要求不同的单层无线传感网络放置问题

Algorithms for Single-tiered Relay Node Placement with Different Connectivity Requirement

该文讨论含有基站的有位置约束无线传感器网络的放置问题,要求添加最少数目的中继器,使得对某些传感器和基站之间存在至少两条边不相交的路,而另一些传感器和基站之间至少存在一条点不相交的路。该文在传感器连通度要求不同的问题上进行了研究,并且在对中继器位置进行限制之后给出了一个性能比为10的近似算法。

In this paper,we discuss the constrained relay node placement in single-tired wireless sensor networks with basestations.We want to find the minimum relay nodes such that there are at least two edge-disjoint paths between some sensor node and basestations,while there is at least one edge-disjoint path between the other sensor nodes and basestations.We are the first to discuss this problem and give a 10-approximation algorithm.