Aggregate node placements in sensor networks

In this paper we consider the design issue of sensor networks by placing a few powerful aggregate nodes into a dense sensor network such that the network lifetime is significantly prolonged when performing data gathering. Specifically, the problem is to place K aggregate nodes into a dense sensor network of n sensor nodes with K?n such that the lifetime of the resulting network is maximized, subject to the constraints that both the maximum transmission range of an aggregate node and the maximum transmission delay between an aggregate node and a sensor node covered by the aggregate node are met. Clearly, this is a joint optimization problem of aggregate node placement and the communication structure, which is NP-hard. We approach the problem by devising a fast and scalable heuristic algorithm. We also conduct experiments by simulation to evaluate its performance, and the experimental results show that the proposed algorithm outperforms a commonly equal distance placement schema significantly.