Improving the lifetime of wireless sensor networks (WSNs) remains an open and active research area. One of the challenging problems in this field is the partitioning of a WSN into disjoint clusters so that the network lifetime is maximized. In particular, the selection of a head for each cluster should consider various parameters related to transmission costs. In this paper, we propose a novel clustering scheme based on hierarchical agglomerative clustering algorithm. The selection of the cluster heads is based on the proximity with a virtual node representing the optimal head location with respect to energy consumption. The proposed algorithm is re-executed at each packet delivering round to maintain energy efficiency during the whole network lifetime. In the transmission of packets to BS, we consider two cases:

- Single hop transmission between CHs and BS that, each CH directly send packets to BS, and - multi-hop transmission between the BS and CHs that, each CH transmits to another CH or to a base station according to the results obtained by the algorithm of the spanning tree. Experimental results show that our clustering scheme is less energy-consuming than LEACH, HEED and clustering protocol using k-means algorithm.

wireless sensor network, cluster, cluster head, LEACH, HEED, CHSMK-means, energy efficiency, HACSH, HACMH, hierarchical agglomerative clustering algorithm, PRIM algorithm.