Local and adaptive amendment to data aggregation tree in wireless sensor networks

Fault tolerant is critical to data aggregation in wireless sensor networks. This paper mainly studies how to maintain a fault tolerant data aggregation tree effciently. Our goal is to design an amendment strategy that minimizes the number of nodes affected by the failed nodes. Since not all networks are reparable, we mainly study the k-hop (k > 1) reparable data aggregation tree amendment problem. When a node is out of service, we say the network is k-hop reparable if it satisfies the following conditions: all of the node's children nodes can find at least one alternate path within at most k-hops neighbors of the corrupted node. Nevertheless, not all nodes within its k - 1 hops can find their alternate paths. We first present a sorting and searching algorithm to facilitate the tree amendment process when we construct the aggregation tree. We then propose a local aggregation tree amendment strategy. The amendment algorithm only affects a very limited number of nodes around the corrupted node, and it is transparent to the other nodes. The proposed amendment algorithm does not change current aggregation tree structure nor the scheduling of other nodes. Theoretical analysis show that the maximum number of nodes afected by the corruption, the message and time complexity of our proposed tree amendment algorithm are all at most O(k). The results show that our proposed local amendment strategy is efficient with respect to both time complexity and message complexity.