網路技術與電腦科技之快速發展，許多網路服務被廣泛地運用於日常生活，如影像會議、隨選視訊、網路教學、網路遊戲、網路廣播服務等。這些服務往往需要同時傳送大量的資料給非常多的接收者。傳統一對一(unicast)的傳輸方式並不適用於這類之服務，因為不僅浪費頻寬也會增加傳輸延遲。群播技術由於可以同時傳輸資料給多個使用者，因此成為提供這些新型網路服務的最佳技術。但群播技術是架構在網路層協定上，需要在路由器與網路服務提供業者之配合。但網路服務的提供業自訂之網路管理規範的限制導致群播技術一直無法在網際網路間大量應用。近來多種架構在應用層上的群播技術被陸續提出，這些技術不需網路層協定之協助即可運作。這些新的技術將要參與資料傳輸的使用者連結成一個邏輯網路，稱為疊加網路，在該網路上的每個邊都對應至實體網路上之一條路徑。經過這樣的轉換後，使得在實體網路的群播問題變成在疊加網路上之廣播問題。而不論群播或廣播都需要先建立一個有效率之資料傳輸樹，傳送端再將資料沿傳輸樹上之路徑傳給所有接收者。雖然這些架構在應用層的群播技術可以很容易地應用在現有之網路上，但要將這個技術支援即時的多媒體網路服務卻是一個非常困難的課題，因為這些服務為滿足使用者的需求，需要網路在傳輸資料上達到一定程度之服務品質，例如最大之傳輸延遲，最大分支度，最大之封包遺失率等。如何建構一個有效率且滿足所需之服務品質的傳輸樹便成為今日網路技術上一個重要之課題。本論文探討如何在最大傳輸延遲與最大分支度的限制下，在疊加網路上建構最低成本之傳輸樹。在本論文中首先針對相關問題及技術作一深入之探討，而後以目前最重要的兩種演化式演算法，基因演算法和螞蟻演算法，為基礎設計解決方法，最後再以一系列之實驗來驗證本研究所提之方法的效率與效能。

With the development of the Internet, many new applications, like video conference, distance learning, network games and so on, need group communication services and require QoS guarantee from underlying networks. In contrast to many one-to-one unicast to support group communication, multicast is an efficient transmission mechanism, because multicast sends packets to the receivers along a transmission tree and replicates packets only at the branching points. This makes applications more scalable and leads to more efficient use of network resources.
Currently, most multicast protocols are developed from IP-layer. However, IP-layer multicast protocols that function multicast on the network layer leave many unsolved problems that hinder the deployment of IP-layer multicast. Therefore recent studies have implemented such applications by application layer multicasting through organizing the multicast group in a peer-to-peer overlay network. This enables faster deployment of multicast services and adds flexibility to the service infrastructure. Moreover, the IP-layer multicasting problem in the Internet is transformed to the application-layer broadcasting problem in the overlay multicast network.
On the other hand, many of the group applications have the QoS requirements, which limit the transmission time and the number of receivers to which each node can transmit, because data arriving later than a deadline are simply useless and the required bandwidth might excess the maximum link-bandwidth if the number of receivers is too high. Such a communication scheme in an overlay network can be regarded as a degree- and-delay constrained minimum-cost broadcasting problem, and appears to be NP-complete.
This study proposes a novel genetic algorithm and an ant-based algorithm for resolving this difficult broadcasting problem and, then, compares them with some state-of-the-art methods. Simulation results with a series of problems demonstrate the efficiency and effectiveness of the proposed algorithms.

[1]A. Mauthe, D Hutchison, G. Coulson, S. Namuye, Multimedia group communications: towards new services, Distrib. Syst. Engng 3 (1996) 197-210.
[2]J. Moy, Multicast Routing Extensions for OSPF, Communications of the ACM 37 (8) (1994) 61-67.
[3]D. Waitzman, C. Partridge, S. E. Deering, Distance Vector Multicast Routing Protocol, IETF RFC 1075, 1988.
[4]A.J. Ballardie, P.F. Francis, J. Crowcroft, Core based trees, in: Proceedings of the ACM SIGCOMM, 1992.
[5]http://en.wikipedia.org/wiki/Overlay_network
[6]G. Zhou, M. Gen, Genetic algorithms on leaf-constrained minimum spanning tree problem, Beijing Mathematics 7 (2) (1998) 50–62.
[7]B.A. Julstrom, Codings and operators in two genetic algorithms for the leaf-constrained minimum spanning tree problem, International Journal of Applied Mathematics and Computer Science 14 (3) (2004) 385-396.
[8]G.R. Raidl, B.A. Julstrom, Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem. In: Proceedings of the 2003 ACM Symposium on Applied Computing, Melbourne, FL, USA, 2003. pp. 747-752.
[9]S.C. Narula, C.A. Ho, Degree-constrained minimum spanning trees, Computers and Operations Research 7 (1980) 239-249.
[10]G. Zhou, M. Gen, Approach to degree-constrained minimum spanning tree problem using genetic algorithm, Engineering Design & automation 3 (2) (1997) 157–165.
[11]J. Knowles, D. Come, A new evolutionary approach to the degree-constrained minimum spanning tree problem, IEEE Transactions on Evolutionary Computation 4 (2000) 125-134.
[12]Y. Liu, J. Wu, A genetic algorithm for the degree-constrained multicasting problem, In: Proceedings of the Fifth IEEE International Conference on High Speed Networks and Multimedia Communications. Jeju Island, Korea, (2002) 315–319.
[13]Y. Feng, Z. Yu, Y. Pan, Heuristic genetic algorithm for degree-constrained multicast routing problem, In: Proceedings of 2004 International Conference on Machine Learning and Cybernetics, Shanghai, China, (2004) 2448–2452.
[14]H.F. Salama, D.S. Reeves, Y. Viniotis, The delay-constrained minimum spanning tree problem, In: Proceedings of the Second IEEE Symposium on Computers and Communications, Alexandria, Egypt, (1997) 699–703.
[15]R. Sriram, G. Manimaran, C. Murthy, R. Siva, Algorithms for delay-constrained low-cost multicast tree construction, Computer Communications 21 (18) (1998) 1693-1706.
[16]M. Parsa, Q. Zhu, J.J. Garcia-Luna-Aceves, An iterative algorithm for delay-constrained minimum-cost multicasting, IEEE/ACM Transactions on Networking 6 (4) (1998) 461-474.
[17]A. Tawfig, Z. Taieb, Delay-constrained, low-cost multicast routing in multimedia networks, Journal of Parallel and Distributed Computing 61 (9) (2001) 1307-1336.
[18]A. Hać, K. Zhou, A new heuristic algorithm for finding minimum-cost multicast trees with bounded path delay, International Journal of Network Management 9 (4) (1999) 265-278.
[19]Z. Wang, B. Shi, E. Zhao, Bandwidth-delay-constrained least-cost multicast routing based on heuristic genetic algorithm, Computer Communications 24 (2001) 685-692.
[20]J.H. Holland, Adaptation in natural and artificial system, Ann Arbor, The University of Michigan Press, 1975.
[21]M. Dorigo, V. Maniezzo and A. Colorni, The ant system: Optimization by a colony of cooperating agents, IEEE Transaction on System, Man, and Cybernetics, Part B, 26(1) (1996) 1-13.
[22]M. Dorigo and L.M. Gambardella, Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation 1(1) (1997) 53-66.
[23]B. Bullnheimer, R.F. Hartl and C. Strauss, A new rank based version of the ant system: a computational study, Central European Journal for Operations Research and Economics, 7(1) (1999) 25-38.
[24]T. Stüzle and H.H. Hoos, MAX-MIN ant system, Future Generation Computer Systems Journal, 16(8) (2000) 889-914.
[25]M. Gen and R. Cheng, A survey of penalty techniques in genetic algorithms In: Proceedings of the IEEE Conference on Evolutionary Computation, (1996) 804−809.
[26]C. Palmer, An approach to a problem in network design using genetic algorithms, Ph.D. thesis, Polytechnic University, 1994.
[27]M. Gen and R. Cheng, Genetic algorithms and engineering design, John Wiley & Sons, Inc., New York, 1997.
[28]H. Prüfer, Neuer beweis eines stazes über permutation, Arch, Math. Phys., 27 (1918) 742-744.
[29]R. Prim, Shortest connection networks and some generalizations, Journal of Bell Systems Technology, 36 (1957) 1389-1401.
[30]J. Bean, Genetic algorithms and random keys for sequencing and optimization, ORSA Journal on Computing 6 (1994) 154-160.
[31]L. Chen, Z.Y. Yang, Z.Q. Xu, A degree-delay-constrained genetic algorithm for multicast routing tree. In: Proceedings of the Fourth International Conference on Computer and Information Technology 2004. Wuhan, China
[32]J. Knowles, D. Come, A new evolutionary approach to the degree-constrained minimum spanning tree problem, IEEE Transactions on Evolutionary Computation 4 (2000) 125-134.
[33]Z. Wang, B. Shi, E. Zhao, Bandwidth-delay-constrained least-cost multicast routing based on heuristic genetic algorithm, Computer Communications 24 (2001) 685-692.
[34]Y. Li, An Effective Implementation of a Direct Spanning Tree Representation in GAs, in: Proceedings of the EvoWorkshops on Applications of Evolutionary Computing, 2003. pp.11-19.
[35]Raidl GR, Julstrom BA (2003) Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem. In: Proceedings of the ACM Symposium on Applied Computing 2003. Melbourne, FL, USA
[36]Haghighat, A.T., Faez, K., Dehghan, M., Mowlaei, A., Ghahremani, Y., GA-based heuristic algorithms for bandwidth-delay-constrained least-cost multicast routing, computer communications 28 (2003)
[37]Di Caro G., Dorigo M. (1998) AntNet: Distributed Stigmergetic Control for Communications Networks, Journal of Artificial Intelligence Research (9): 317-365
[38]Martin Gruber, Jano I. van Hemert, Günther R. Raidl, Neighbourhood searches for the bounded diameter minimum spanning tree problem embedded in a VNS, EA, and ACO. GECCO (2006) 1187-1194
[39]Thang N. Bui and Catherine M. Zrncic, An ant-based algorithm for finding degree-constrained minimum spanning tree, In: Proceeding of the 8th annual conference on Genetic and evolutionary computation 2006. Seattle, Washington, USA
[40]Q. Zhang, Y.W. Lenug, An orthogonal genetic algorithm for multimedia multicast routing, IEEE Transactions on Evolutionary Computation 3 (1) (1999) 53–62
[41]C.C. Palmer, An approach to a problem in network design using genetic algorithms, PhD Dissertation in Computer Science, Polytechnic University, April 1994.
[42]R. Prim, Shortest connection networks and some generalizations, Bell System Technical Journal 36 (1957) 1389-1401.
[43]B.M. Waxman, Routing of multipoint connections. IEEE Journal on Selected Area on Communications 6 (9) (1988) 1617-1622.
[44]http://www.talkorigins.org/faqs/genalg/genalg.html