Algorithm of Minimum Power Relay Node Placement in Wireless Sensor Networks
Kezhong Lu, Gang Liu, Yaodong Tao, Zhong Ming · Journal of Chinese Computer Systems · 2011
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.