Algorithms for k-fault tolerant power assignments in wireless sensor networks

This paper addresses fault-tolerant many-to-many routing power assignments in heterogeneous wireless sensor networks. We introduce the k-fault tolerant power assignments problem with the objective of assigning each sensor node transmission power such that (1) any pairwise sensor node is k-vertex connected and (2) the total power consumption is minimized. We propose three solutions for this problem: two centralized algorithms, a greedy algorithm and an O(√-n/ε)-approximation algorithm, and an h-hop distributed and localized algorithm. Related theorems and proofs are presented to prove the correctness of our approaches. Furthermore, simulation and experiment results are presented to verify the efficiency of our approaches.