A Top-Down Clustering and Cluster-Tree-Based Routing Scheme for Wireless Sensor Networks

Cluster-based organization of large sensor networks is the basis for many techniques aimed at enhancing power conservation and network management. A backbone network in the form of a cluster tree further enhances routing, broadcasting, and in-network processing. We propose a configurable top-down cluster and cluster-tree formation algorithm, a cluster-tree self-optimization phase, a hierarchical cluster addressing scheme, and a routing scheme. Such self-organization makes it possible to effectively deliver messages to a sink as well as within the network. For example, a circular sensor field with a sink in the center can establish cross-links and circular-paths within the cluster tree to deliver messages through shorter routes while reducing hotspots and consequently increasing network lifetime. Cluster and cluster-tree formation algorithm is independent of physical topology, and does not require a priori neighborhood information, location awareness, or time synchronization. Algorithm parameters allow for formation of cluster trees with desirable properties such as controlled breadthdepth, uniform cluster size, and circular clusters. Characteristics of clusters, cluster tree, and routing are used to demonstrate the effectiveness of the schemes over existing techniques.