Energy-Efficient Design Techniques for Large-scale, Two-tiered Sensor Networks

In two-tiered sensor networks using relay nodes, sensor nodes are arranged in clusters and the higher-powered relay nodes can be used as cluster heads. The lifetime of such a network is determined primarily by the lifetime of the relay nodes. Clustering techniques and routing schemes play a crucial role in determining the useful lifetime of such networks. In two-tiered sensor networks with higher-powered relay nodes as cluster heads, the clustering problem and the routing problem have been traditionally considered independently and solved separately. In this paper, we present a new integer linear program (ILP) formulation that jointly optimizes both clustering and routing to maximize the lifetime of such networks. We show that our integrated approach can lead to significant improvements over techniques that consider clustering and routing separately, particularly for the non-flow-splitting routing model. We also propose a heuristic, based on a LP-relaxation of the routing variables, which can be used for larger networks.