Relay Node Placement for Maximizing Network Lifetime in Wireless Sensor Networks

A wireless sensor network consists of many low-cost, low-power sensor nodes to perform sensing environment and transmitting sensed information to a base station. Energy efficient is a main design factor for wireless sensor network. It is a significative method to prolong the lifetime of sensor network through deploying some relay nodes. In this paper, we present an approximate algorithm for the relay node placement problem to maximize sensor network lifetime. At first, some relay nodes are placed to connect the whole wireless sensor network through a greedy scheme. Next, some redundant relay nodes are placed to maximize the network lifetime. And then, we prove that the network lifetime can achieve maximum value through our algorithms. At last, some experiments have been carried out to show the performance of our algorithm compared with the optimal placement.