Multicast tree is a key structure for data dissemination from one source to multiple receivers in wireless networks. Minimum length multica modeled as the Steiner tree problem, and is proven to be NP-hard. In this paper, we explore how to efficiently generate minimum length multi wireless sensor networks (WSNs), where only limited knowledge of network topology is available at each node. We design and analyze a simple algorithm, which we call toward source tree (TST), to build multicast trees in WSNs. We show three metrics of TST algorithm, i.e., running and energy efficiency. We prove that its running time is O(√(n log n)), the best among all existing solutions to our best knowledge. We prove that TST tree length is in the same order as Steiner tree, which give a theoretical upper bound and use simulations to show the ratio be only 1.114 when nodes are uniformly distributed. We evaluate energy efficiency in terms of message complexity and the number of forwarding prove that they are both order-optimal. We give an efficient way to construct multicast tree in support of transmission of voluminous data.

The minimum-length multicast tree can achieve efficient multicast transmissions and can be formulated as a Steiner Tree. Its construction is non-trivial and has been proven to be NP-hard. In this paper, we combine the design wisdoms in the minimum spanning tree and the shortest path, and propose a new distributed algorithm for constructing an approximate Steiner Tree, particularly applicable to dynamic wireless networks without centralized control. We rigorously prove the performance bounds of our algorithm in terms of tree length, running time and energy consumption. Let m be the multicast group size and n be the network size. We theoretically show that the ratio of our tree length to the minimum value is upper bounded by 2(1 + δ)/√3 (where δ can be any positive value). Simulation results show that this ratio is in fact very close to 1. We also prove that the running time is O( √(mn log m log3n)). The energy consumption is evaluated in terms of message complexity, and is upper bounded by O(n logm). In all, our algorithm achieves the near-optimal tree length, as well as the shortest running time and the lowest message complexity among all solutions we are aware of. We believe our algorithm provides a significant improvement in designing practical routing policies in wireless networks.

Multicast tree is a key structure for data dissemination from one source to multiple receivers in wireless networks. Minimum length multicast tree can be modeled as the Steiner Tree Problem, and is proven to be NP-hard. In this paper, we explore how to efficiently generate minimum length multicast trees in wireless sensor networks (WSNs), where only limited knowledge of network topology is available at each node. We design and analyze a simple and distributed algorithm, which we call Toward Source Tree (TST), to build multicast trees in WSNs. We show three metrics of TST algorithm, i.e., running time, tree length and energy efficiency. We prove that its running time is O(√nlog n), the best among all existing solutions to our best knowledge. We prove that TST tree length is in the same order as Steiner tree, give a theoretical upper bound and use simulations to show the ratio between them is only 1.114 when nodes are uniformly distributed. We evaluate energy efficiency in terms of the number of forwarding nodes in multicast trees, and prove that it is order-optimal. We give an efficient way to construct multicast tree in support of transmission of voluminous data.