中文摘要：

在无线传感器网络中,如何布置给定数量的中继节点以最小化传输数据的整体功耗是个值得关注的问题.对中继节点的最小功耗布置问题进行了形式化描述,提出一种时间复杂度为O（n2）的近似算法,其中n为传感器节点数目.该算法先构造一棵中继节点数目不受限制时的最优生成树,然后每次从生成树中删除一个使得整体功耗增加最少的中继节点,直至生成树中的中继节点数目满足要求.实验结果表明该算法的执行时间较短,在传输数据的整体功耗方面要优于现有算法.

英文摘要：

In wireless sensor networks,how to place a given number of relay nodes to minimize the whole power consumption spent in transferring data is a noticeable problem.In this paper a formal description of the minimum power relay node placement problem is given.Then an approximation algorithm with time complexity of O（n2） is proposed,where n is the number of sensor nodes.This algorithm first constructs the optimum spanning tree when the number of relay nodes is not restricted.Then,each time the relay node that brings the least increment of the whole power consumption is removed from the spanning tree,until the number of relay nodes in the spanning tree satisfies the requirement.Experiment results have shown that this algorithm has short execution time and outperforms the existing algorithm in respect to the whole power consumption spent in transferring data.