Hausdorff Clustering and Minimum Energy Routing for Wireless Sensor Networks

We present a new method for data gathering that maximizes lifetime for wireless sensor networks. It involves three parts. First, nodes organize themselves into several static clusters by the Hausdorff clustering algorithm based on node locations, communication efficiency, and network connectivity. Second, clusters are formed only once, and the role of the cluster head is optimally scheduled among the cluster members. We formulate the maximum lifetime cluster-head scheduling as an integer-programming problem and propose a greedy algorithm for its solution. Third, after cluster heads are selected, they form a backbone network to periodically collect, aggregate, and forward data to the base station using minimum energy (cost) routing. This method can significantly lengthen the network lifetime when compared with other known methods.