Lifetime Approximation Schemes Allow Multicast Algorithm with Linear Message Complexity in Wireless Sensor Networks

We consider an optimization problem in wireless sensor networks (WSNs) that is to find a multicast tree with maximum lifetime. While a recently proposed distributed algorithm for this problem guarantees to obtain optimal solutions, its high message complexity may prevent such contribution from being practically used in resource-constrained WSNs. In this paper, we proposed a new distributed algorithm that achieves a good balance on the algorithm optimality and message complexity. We use a graph theoretical approach, by the first time, to derive the bounds of both approximation ratio and message complexity in an analytical expression for this algorithm. The theoretical analysis on the tradeoff between these two performance metrics is also validated by our simulation studies.