Improving scalability for longest-lived multicast using localized operations in WANETs

We consider the problem of maximizing the multicast lifetime in multihop wireless networks in which each node has limited energy, bandwidth, memory, and computation capabilities. We explore some important properties of this optimization problem from a graph theory perspective and obtain a min-max-tree max-min-cut theorem, which connects some important while separated results in recent literature together under the same philosophy. We also apply the theorem to derive our algorithms and localized operations that can construct a global optimal maximum lifetime multicast tree for a static resource-constrained (e.g. memory and computation capability) wireless multihop network. The distributed algorithms have low complexity for both memory and computation requirements at each node. Our localized operations allow our distributed algorithms with expected linear communication complexity. To our best knowledge, this is the first contribution that possesses all the desirable properties of distributed, localized, and scalable for the maximum-lifetime multicast problem, and is especially beneficial to the large-scale resource-limited wireless multihop networks, like sensor networks.