Full Text:   <1669>

CLC number: TP18; TP393

On-line Access: 2008-05-10

Received: 2007-09-25

Revision Accepted: 2008-01-07

Crosschecked: 0000-00-00

Cited: 0

Clicked: 3072

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2008 Vol.9 No.6 P.791~798


Two-stage evolutionary algorithm for dynamic multicast routing in mesh network

Author(s):  Li ZHU, Zhi-shu LI, Liang-yin CHEN, Yan-hong CHENG

Affiliation(s):  School of Computer Science, Sichuan University, Chengdu 610065, China; more

Corresponding email(s):   zhulicdsu@126.com

Key Words:  Dynamic multicast, Routing, Encoding, Quality of Service (QoS), Evolution, Genetic algorithm (GA)

Li ZHU, Zhi-shu LI, Liang-yin CHEN, Yan-hong CHENG. Two-stage evolutionary algorithm for dynamic multicast routing in mesh network[J]. Journal of Zhejiang University Science A, 2008, 9(6): 791~798.

@article{title="Two-stage evolutionary algorithm for dynamic multicast routing in mesh network",
author="Li ZHU, Zhi-shu LI, Liang-yin CHEN, Yan-hong CHENG",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Two-stage evolutionary algorithm for dynamic multicast routing in mesh network
%A Zhi-shu LI
%A Liang-yin CHEN
%A Yan-hong CHENG
%J Journal of Zhejiang University SCIENCE A
%V 9
%N 6
%P 791~798
%@ 1673-565X
%D 2008
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.A071519

T1 - Two-stage evolutionary algorithm for dynamic multicast routing in mesh network
A1 - Li ZHU
A1 - Zhi-shu LI
A1 - Liang-yin CHEN
A1 - Yan-hong CHENG
J0 - Journal of Zhejiang University Science A
VL - 9
IS - 6
SP - 791
EP - 798
%@ 1673-565X
Y1 - 2008
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.A071519

In order to share multimedia transmissions in mesh networks and optimize the utilization of network resources, this paper presents a Two-stage evolutionary Algorithm (TEA), i.e., unicast routing evolution and multicast path composition, for dynamic multicast routing. The TEA uses a novel link-duplicate-degree encoding, which can encode a multicast path in the link-duplicate-degree and decode the path as a link vector easily. A dynamic algorithm for adding nodes to or removing nodes from a multicast group and a repairing algorithm are also covered in this paper. As the TEA is based on global evaluation, the quality of the multicast path remains stabilized without degradation when multicast members change over time. Therefore, it is not necessary to rearrange the multicast path during the life cycle of the multicast sessions. Simulation results show that the TEA is efficient and convergent.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1] Chen, L., Xu, Z.Q., 2006. Effective multicasting algorithm for dynamic membership with delay constraint. J. Zhejiang Univ. Sci. A, 7(2):156-163.

[2] Dalal, Y.K., Metcalfe, R.M., 1978. Reverse path forwarding of broadcast packets. Commun. ACM, 21(12):1040-1048.

[3] Erlangung, Z., 2003. Algorithms for the Steiner Problem in Networks. Ph.D Thesis, University of Saarlandes, Saarbrücken, Germany.

[4] Fu, H.Z., Li, C.P., 2005. An Improved Genetic Algorithm for Cost-Delay-Jitter QoS Multicast Routing. Proc. IEEE Int. Conf. on Computational Intelligence for Modelling, Control and Automation, 2:1098-1103.

[5] Garrozi, C., Araujo, A.F.R., 2006. Multiobjective Genetic Algorithm for Multicast Routing. IEEE Congress on Evolutionary Computation. Vancouver, BC, Canada, p.2513-2520.

[6] Kompella, V., 1993. Multicast Routing Algorithms for Multimedia Traffic. Ph.D Thesis, University of California, San Diego, USA.

[7] Liu, C.H., Chiang, T.C., Huang, Y.M., 2006. A Near-Optimal Multicast Scheme for Mobile Ad Hoc Networks Using a Hybrid Genetic Algorithm. Proc. 20th Int. Conf. on Advanced Information Networking and Applications, 1:465-470.

[8] Medina, A., Lakhina, A., Matta, I., Byers, J., 2001. BRITE: An Approach to Universal Topology Generation. Proc. 9th IEEE Int. Symp. on Modeling, Analysis and Simulation of Computer and Telecommunications Systems, p.346-353.

[9] Raghavan, S., Manimaran, G., Siva, R.M.C., 1999. A rearrangeable algorithm for the construction of delay-constrained dynamic multicast trees. IEEE/ACM Trans. on Networking, 7(4):514-529.

[10] Sun, L.J., Wang, R.C., Liu, C.L., 2007. A QoS multicast routing approach based on parallel quantum genetic algorithm. J. Nanjing Univ. Posts Telecommun. (Nat. Sci.), 27(2):72-75 (in Chinese).

[11] Vijay, A., Thierry, T., Shivkumar, K., 2005. Encoding of multicast path. LNCS, 3462:992-1004.

[12] Viswanath, K., Obraczka, K., Tsudik, G., 2006. Exploring mesh and path-based multicast routing protocols for MANETs. IEEE Trans. on Mobile Computing, 5(1):28-42.

[13] Waxman, B.M., 1988. Routing of multipoint connections. IEEE J. Sel. Areas Commun., 6(9):1617-1622.

[14] Wu, J.G., Yang, Y.Y., Chen, Y.X., Ye, X.G., 2006. A QoS aware overlay multicast routing protocol. Chin. J. Computers, 29(11):1937-1947 (in Chinese).

[15] Yue, C.J., Zheng, X.P., Jing, Y.W., 2007. QoS multicast routing based on chaotic genetic algorithm. J. Northeastern Univ. (Nat. Sci.), 128(10):1446-1449 (in Chinese).

[16] Zhou, J.Y., Lin, Y., Hu, H.P., 2007. Dynamic Zone Based Multicast Routing Protocol for Mobile Ad Hoc Network. Proc. IEEE Int. Conf. on Wireless Communications, Networking and Mobile Computing, 3:1528-1531.

[17] Zhu, L., Li, Z.S., Xing, J.C., Cheng, Y.H., 2007. An Immune Genetic Routing Algorithm for Mesh Network with QoS Constraints. Proc. IEEE Int. Conf. on Wireless Communications, Networking and Mobile Computing, 3:1701-1704.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE