An Energy-Efficient and Fault-Tolerant Convergecast Protocol in Wireless Sensor Networks

The simple graph theory is commonly employed in wireless sensor networks topology control. This paper uses hyper-graph theory to solve the practical problems and proposes a Spanning Hyper-Tree algorithm (SHTa) to compute the minimum transmitting power delivery paths set for WSNs convergecast. There are three main contributions of this paper: the authors present a novel hyper-graph model to abstract large-scale and high connectivity WSNs into a robust hyper-tree infrastructure; they present a precise mathematical derivation that solves the "Hyper-tree existence" problem; SHTa is proposed to compute the delivery paths set, which is the minimum power transmitting convergecast hyper-tree. Variable scale hyper-edges represented as computing units limit solution space and reduce computing complexity. Mutual backup delivery paths in one hyper-edge improve the capability of fault tolerance.