An Architecture for Robust Sensor Network Communications

Abstract

Node clustering in sensor networks increases scalability, robustness, and energy-efficiency. In hostile environments, unexpected failures or attacks on cluster heads (through which communication takes place) may partition the network or degrade application performance. We propose REED (Robust Energy-Efficient Distributed clustering), for clustering sensors deployed in hostile environments in an interleaved manner with low complexity. Our primary objective is to construct a k-fault-tolerant (i.e., k-connected) clustered network, where k is a constant determined by the application. Fault tolerance is achieved by selecting k independent sets of cluster heads (i.e., cluster head overlays) on top of the physical network, so that each node can quickly switch to other cluster heads in case of failures. The independent cluster head overlays also give multiple vertex-disjoint routing paths for load balancing and security. Network lifetime is prolonged by selecting cluster heads with high residual energy and low communication cost, and periodically re-clustering the network. We prove that REED asymptotically achieves k-connectivity if certain conditions on node density are met. We also discuss inter-cluster routing and MAC layer considerations, and investigate REED clustering properties via extensive simulations.

Keywords:

• Sensor Networks;
• Clustering;
• Robustness;
• k-Connectivity;
• Disjoint Paths

The authors would like to thank Andrew Campbell (Columbia University) for his helpful comments on this work.

Notes

¹Due to our probabilistic clustering approach, the number of cluster head announcements per iteration is small. Observe also that even if node u misses an announcement in one iteration, it is likely to receive one in a subsequent iteration(s).