Clustering strategies for improving the lifetime of two-tiered sensor networks

In hierarchical sensor networks, sensor nodes are arranged in clusters, and higher-powered relay nodes can be used as cluster heads. Due to the limited transmission range and battery power of the nodes, it is important to develop techniques that minimize energy dissipation of the nodes, and thus extend the lifetime of network. Proper techniques for assigning sensor nodes to clusters have been shown to improve the lifetime of the network. In this paper, we have proposed two fast and efficient integer linear program (ILP) formulations for assigning sensor nodes to clusters in a two-tiered network, where the relay nodes are used as cluster heads. The first is for single hop routing and the second is a generalized formulation that can be used with any multi-hop routing strategy. The objective, in both cases, is to maximize the lifetime of the relay node network. Comparisons with existing heuristics for clustering demonstrate that our ILP's significantly extend the network lifetime and are fast enough to be used for practical networks with hundreds of sensor nodes. (C) 2008 Elsevier B.V. All rights reserved.