Fault Tolerant Clustering in Dense Wireless Sensor Networks

Wireless Sensor Networks are an important focus of research in distributed computing due to their many envisioned applications. Self-organizing these networks using clustering algorithms has been studied extensively in the literature as a means to conserve energy in sensor nodes. In clustering, the network organizes around a small set of cluster-heads which then gather data from their local cluster, aggregate this data and transmit it to the base station. In this paper we present a model for adding fault-tolerance to clustering algorithms in dense sensor networks. Since sensor nodes are often deployed in harsh environments, they are prone to failure. Cluster-head failure can leave a cluster disconnected from the base station until the network reorganizes again. We use the density of the network to improve the lifetime of the network by about 80% while allowing for recovery from the failure of a cluster head. This comes at the cost of a slightly increased number of clusters.