Dynamical construction of a core-based group-shared multicast tree in mobile ad hoc networks

A core-based group-shared multicast tree is a shortest path tree rooted at core node that distributes packets to and from all group members. Traditionally, the bandwidth cost consumed by transmitting a packet via the tree is evaluated by the total weights of all the edges. And, the cost is minimized by constructing the multicast tree that has minimum total weights of edges to span all group members. However, when the local broadcasting operation is used to multicast a packet, we found that the cost is supposed to be evaluated by the total weights of all senders that include the core and all non-leaves. Since the multicast tree with the number of nodes greater than or equal to three has minimum cost only when the core is not a leaf it leads us to find the multicast tree with the minimum number of non-leaves when each sender node has a unit weight. However, no polynomial time approximation scheme can be found for the minimum non-leaf multicast tree problem unless P=NP since the problem is not only NP-hard but also MAX-SNP hard. Thus, a heuristic is proposed to dynamically construct and adjust the multicast tree in a mobile ad hoc network. Experimental results show that our multicast tree has smaller number of non-leaves than others in the geometrically distributed network model.