A fast and efficient multicast algorithm for QoS group communications in heterogeneous network

With the development of MANETs (mobile ad hoc networks), more and more mobile nodes need to access the Internet. To benefit the integration of MANETs and the Internet, a new heterogeneous network architecture has been proposed, which consists of several MANETs (e.g., working teams) attached to the backbone Internet through different gateway nodes. In such a heterogeneous network, group communications occur when several team leaders need to work in a cooperative way. Furthermore, strict QoS requirements on delay and delay variation are required for some time-sensitive applications. In wireline network, such a problem is defined as DVBMT (Delay- and delay Variation-Bounded Multicast Tree) problem [N.R. George, B. Ilia, Multicast routing with end-to-end delay and delay variation constraints, IEEE Journal on Selected Areas in Communications 15 (3) (1997) 346–356] and proved to be NP-complete. To solve the DVBMT problem in the heterogeneous network, we propose a fast and efficient multicast algorithm. It takes the wireless routing delay into account and can construct a low delay variation multicast tree spanning all the gateway nodes involved in the group communications. It improves an existing algorithm called DDVCA (Delay and Delay Variation Constraint Algorithm) [P.-R. Sheu, S.-T. Chen, A fast and efficient heuristic algorithm for the delay- and delay variation-bounded multicast tree problem, Computer Communications 25 (8) (2002) 825–833], which is known to be the best for the DVBMT problem. To the best of our knowledge, our algorithm is the first one which really outperforms DDVCA. Theoretical analysis has explained the drawbacks of both DDVCA and an improvement algorithm previously proposed in Kim et al. [M.S. Kim, Y.-C. Bang, H.S. Choo, On core selection algorithm for reducing delay variation of many-to-many multicasts with delay-bounds, in: Proc. IFIP Networking (2004)]. In addition, theoretical proof on the performance improvement of our algorithm over DDVCA is provided. Experimental results also show that the proposed algorithm outperforms DDVCA in terms of multicast delay variation with the same time complexity as DDVCA.