The two-tiered wireless sensor network is a network that data can only be transmitted between relay nodes or sensor nodes and relay nodes,and there is no data stream between sensor nodes.An approximation algorithm is proposed based on two foundational works:The k-disk cover problem and the single-tiered 3-connectivity relay node placement problem,with a specialstructure,called “hexagon” , to keep 3-connectivity for the network.The performance ratio is 8α+β ,where α is the performance ratio of approximation algorithm for the k-disk cover problem,and β is the performance ratio of approximation algorithm for the single-tiered 3-connectivity relay node placement problem.%主要研究双层无线传感网络模型,即数据信息流只能在传感器和中继器或中继器和中继器之间传输,而不能在传感器之间传输,近似算法基于两个子问题:k圆盘覆盖问题和单层传感网络的k连通问题,而后在部分中继器周围设置"等六边形"结构的中继器点,最终达到整个网络的3-连通水平.该算法的最终性能比为8α+β,其中α为k圆盘覆盖近似算法的性能比,β为单层传感网络的k连通近似算法的性能比.
展开▼
