# A Novel Hybrid Ant Colony Optimization for a Multicast Routing Problem
## 2 Problem Description  
In general, a communication network may be defined as a graph \(G\), \(G\) = (\(V\),\(E\)), in which \(V\) represents a set of transmission nodes, \(V\) = {\(v_{1}\), \(v_{2}\),..., \(v_{n}\)}, and \(E\) is the set of all edges, \(E\) = {(\(i\),\(j\)) \(\mid\)\(v_{i}\),\(v_{j}\)\(\in\)\(V\)} denoting physical link of these nodes. We define \(n\) = \(\mid\)\(V\)\(\mid\) as the network node number, and \(l\) = \(\mid\)\(E\)\(\mid\) as the network edge number. Each edge is bidirectional, i.e., the edge \(e\) = (\(u\), \(v\)) between node \(u\)\(\in\)\(V\) and node \(v\)\(\in\)\(V\) represents existence of another edge \(e^{\prime}\) = (\(v\), \(u\)) between node \(v\) and node \(u\). For each edge \(e\)\(\in\)\(E\), let us make some definitions about some metrics: transmission cost \(C(e)\): \(E\)\(\rightarrow\)\(R^{+}\), edge delay \(D(e)\): \(E\)\(\rightarrow\)\(R^{+}\), bandwidth \(B(e)\): \(E\)\(\rightarrow\)\(R^{+}\), transmission delay jitter \(J(e)\): \(E\)\(\rightarrow\)\(R^{+}\), packet loss rate \(PL(e)\): \(E\)\(\rightarrow\)\(R^{+}\), in which \(R^{+}\) denotes a set of non-negative real numbers. Let \(D(e)\) be the transmission delay on link \(e\), and \(B(e)\) denote the bandwidth functions of edge \(e\). Packet loss \(PL(e)\) represents the loss rate of a receiving termination on edge \(e\). Delay jitter \(J(e)\) denotes the delay change in different time intervals between the packets arriving. The cost \(C(e)\) represents the cost of transmitting a packet on edge \(e\), and it may take a measurement to make full use of resource optimization. For multicast network communications, information messages should be delivered starting from a source node to every destination node. Let a node \(s\)\(\in\)\(V\) be a transmission source node. A subset \(M\)\(\subseteq\)\(V\)-{\(s\)} represents destination nodes. Given \(m\) = \(\mid\)\(M\)\(\mid\) is the destination node number. Let the set \(M\) be a destination set, \(\{s\}\)\(\cup\)\(M\) be a multicast group, and \(T(s\), \(M)\) denote a QOS multicast tree. The multicast tree represents a subgraph of weighted graph \(G\) spanning the nodes in \(\{s\}\)\(\cup\)\(M\). \(T(s\), \(M)\) may exist Steiner nodes. The Steiner nodes belong to a multicast tree, but these nodes do not in \(\{s\}\)\(\cup\)\(M\). \(p_{T}\)(\(s\), \(d\)) represents a route path in a tree \(T\) between a node \(s\) and a destination \(d\)\(\in\)\(M\), one of destination nodes. As an example, consider the graph of Figure 1. The network graph has 9 nodes with node 0 shaded in the Figure 1a being the transmission source node, and \(M\) = {\(d_{1}\), \(d_{2}\), \(d_{3}\)} being the destination node set. The destination nodes are marked with yellow shadows. A tree \(T(s\), \(M)\) with solid lines is the minimum spanning tree of sub-graph induced by {0, 2, 4, 5, \(d_{1}\), \(d_{2}\), \(d_{3}\)}. The multicast tree includes three steiner nodes number 2, 4, and 5, see Figure 1b. \(T(s\), \(M)\) represents a QOS multicast tree. Let the cost of \(T(s\), \(M)\) be the cost sum of its edges, and it be described as:  
\[C(T(s,M))=\sum_{e\in T(s,M)}C(e) \tag{1}\]  
Figure 1: Example of constructing multicast tree. In this paper, we aim to minimize costs. Thus, the objective function of this paper is to seek a tree \(T(s,M)\) to minimize costs of C(\(T(s,M)\)) with the QoS constraint condition being guaranteed. For all the above descriptions, the model of QoS multicast problem should be expressed as the following:  
\[\min C(T(s,M)) \tag{2}\]  
\[\text{s.t.}\sum_{e\in_{PT}(s,d)}D(e)\leq D_{d} \tag{3}\] \[\min\{B(e),e\in_{T}(s,d)\}\geq B_{d}\] (4) \[\sum_{e\in p(s,d)}J(e)\leq J_{d}\] (5) \[1-\prod_{e\in_{PT}(s,d)}(1-PL(e))\leq PL_{d} \tag{6}\]  
In this formulation, delay \(D_{d}\) is an upper limit between a source node and a destination. Constraint (3) guarantees that the delay total of all edges along \(p_{T}(s,d)\) should be less than the upper bound limits. Let \(B_{d}\) be the bandwidth requirement.