(in lingua inglese)

In this paper, an FOPID controller was proposed for LFC in a three-area power system. The parameters of controllers were tuned using ICA. Simulation of comparative cases confirmed that the proposed controller had better performance in LFC of the interconnected power system. Responses of the power system to disturbances were much smoother and less oscillatory using the proposed controllers. In most cases, the settling time and maximum deviation of power system responses diminished when FOPID controllers were implemented.

Articoli tecnico scientifici o articoli contenenti case history

Pubblicato

da Alessia De Giosa

Estratto del testo

ELECTRICAL ENGINEERING A hybrid ACO/PSO based algorithm for QoS

multicast routing problem Manoj Kumar Patel *, Manas Ranjan Kabat, Chita Ranjan Tripathy Dept. of Comp. Sc. & Engg., Veer Surendra Sai University of Technology, Burla, Sambalpur, Orissa, India Received 1 January 2013; revised 22 June 2013; accepted 18 July 2013

Available online 7 October 2013 KEYWORDS Swarm agent;

ACO;

PSO;

Multicast;

QoS routing Abstract Many Internet multicast applications such as videoconferencing, distance education, and online simulation require to send information from a source to some selected destinations. These

applications have stringent Quality-of-Service (QoS) requirements that include delay, loss rate,

bandwidth, and delay jitter. This leads to the problem of routing multicast trafﬁc satisfying QoS

requirements. The above mentioned problem is known as the QoS constrained multicast routing

problem and is NP Complete. In this paper, we present a swarming agent based intelligent algo-

rithm using a hybrid Ant Colony Optimization (ACO)/Particle Swarm Optimization (PSO) tech-

nique to optimize the multicast tree. The algorithm starts with generating a large amount of

mobile agents in the search space. The ACO algorithm guides the agents'' movement by pheromones

in the shared environment locally, and the global maximum of the attribute values are obtained

through the random interaction between the agents using PSO algorithm. The performance of

the proposed algorithm is evaluated through simulation. The simulation results reveal that our algo-

rithm performs better than the existing algorithms. 2013 Production and hosting by Elsevier B.V. on behalf of Ain Shams University. 1. Introduction The rapid development in network multimedia technology has

enabled more and more real-time multimedia services such as

videoconferencing, online games, and distance education to

become the mainstream Internet activities. These services often

require the underlying network to provide multicast capabili- ties. The multicast refers to the delivery of packets from a

single source to multiple destinations. These real-time applica-

tions have a stringent requirement of QoS parameters like

bandwidth, delay, jitter, and so on to ensure smooth,

consistent, and fair transmission to the receivers. The central

problem of QoS routing is to set up a multicast tree that can

satisfy certain QoS parameters. However, the problem of

constructing a multicast tree under multiple constraints is

NP Complete [1]. Hence, the problem is usually solved by

heuristics or intelligent optimization. In recent years, some meta-heuristic algorithms such as the ant colony algorithm [2''9], genetic algorithm [10''12], particle

swarm optimization [13''17], and Tabu search [18,19] have

been adopted by the researchers to solve the multi-constrained

QoS routing problems. * Corresponding author. Tel.: +91 9861461357.

E-mail addresses: patel.mkp@gmail.com (M.K. Patel), manas_kaba-

t@yahoo.com (M.R. Kabat), crt.vssut@yahoo.com (C.R. Tripathy). Peer review under responsibility of Ain Shams University.**Production and hosting by Elsevier** Ain Shams Engineering Journal (2014) 5, 113''120 Ain Shams University Ain Shams Engineering Journal www.elsevier.com/locate/asej www.sciencedirect.com 2090-4479 2013 Production and hosting by Elsevier B.V. on behalf of Ain Shams University. http://dx.doi.org/10.1016/j.asej.2013.07.005 In [2], an intelligent routing algorithm ANTNET based on ant colony algorithm was proposed. Their algorithm has some

attractive distribution features and it can ﬁnd a near-optimal

path from the source node to each destination node. It also pro-

vides the required results in simulation. Although the ANTNET

is a unicast routing algorithm, it can be easily applied to multi-

cast routing with some modiﬁcations. In spite of the said merits

of the ANTNET, it suffers from a serious drawback i.e. the slow

convergence rate. Another ant intelligence algorithm was intro-

duced in [3] for the computation of the QoS multicast tree. A tree

growth based ACO algorithm (TGBACA) has been proposed in

[8]. It generates a multicast tree in the way of tree growth and

optimizes the ant colony parameters through their most efﬁcient

combinations. The major weakness of the ant colony algorithm

is that it converges slowly at the initial step and takes more time

to converge. This happens due to improper selection of the ini-

tial feasible parameter [3]. The overhead also increases due to

merging and pruning of the trees. Subsequently, the genetic algorithm (GA) was used to ﬁnd a multicast tree satisfying the constraints of bandwidth and de-

lay with least cost [10''12]. The GA has three operators: selec-

tion, crossover, and mutation. The individuals are stored in

connective matrices by adopting the binary coding system.

The initial colony is generated randomly without considering

QoS constraints. The selection operation adopts Roulette

wheel algorithm to select the best individuals from the parent

generation to pass onto the child generation. Then, the cross-

over operation is used to ﬁnd out the ﬁttest among the best. A

penalty function is adopted to solve QoS constraints in the

multicast trees, which do not satisfy QoS constraints.

Although sometimes the algorithm''s performance is observed

to be satisfactory, still it encounters some faults, such as the

local search ability, premature convergence, and slow convergence speed. Further, the genetic algorithm does not

assure to ﬁnd a global optimum. It happens very often when

the populations have a lot of subjects. In [13''17], researchers have proposed some PSO algorithms to solve QoS constraint routing problem. The PSO algorithm

proposed in [14] solves the QoS multicast routing problem

and can obtain a feasible multicast tree by exchanging the

paths. This algorithm can converge to the optimal or

near-optimal solution with lower computational cost. Another

algorithm based on the concept of quantum mechanics named

as Quantum-Behaved Particle Swarm Optimization (QPSO)

was proposed in [15]. Here, the proposed method converts

the QoS multicast routing problem into integer programming

problem and then ﬁnally solves using the QPSO. The QPSO

ﬁnds the path from the source node to each destination node

and constructs the tree by merging the paths. A tree based

PSO has been proposed in [17] for optimizing the multicast tree

directly. However, its performance depends on the number of

particles generated. Another drawback of the said algorithm is

the merging of multicast trees. The elimination of directed cir-

cles and nesting of directed circles are also very complex and

are considered as some of the limitations of the PSO [17]. In recent days, many researchers have solved the QoS constrained multicast tree using Tabu search [18,19]. A Tabu

search method was proposed in [18] to search for the multicast

tree with the least cost that satisﬁes the constraints of band-

width and delay. This algorithm obtains a complete graph of

all group members at the initial step and obtains the initial

Steiner tree via the generated tree of the complete graph. In this way, the k-shortest paths replace the edges to ﬁnd the

chances of getting better results. The method mentioned above

is similar to the method of path combination. However, it does

not operate directly on the multicast tree. This weakness makes

it impossible to eliminate the constraints of conventional

multicast routing algorithms. Hence, there arises a need to

proceed further and do more amount of work in searching

paths and integrating the multicast trees. In this paper, we propose a hybrid ACO/PSO algorithm based on the swarming agent architecture for QoS multicast

routing. Our work is inspired by the swarming agent algorithm

proposed by Brueckner and Parunak [20] for distributed data

pattern and Meng [21] for Proteomic Pattern detection of

ovarian cancer. In our work, a large amount of mobile agents

are generated in the search space. Two collective and coordina-

tion process for the mobile agents are proposed. One is based

on the ACO [8] algorithm for guiding the agents'' movements

by pheromones in the shared environment locally and the

another is based on the PSO algorithm [17] for obtaining the

global maximum of the attribute values through the random

interaction between the agents. The rest of the paper is organized as follows: A mathematical model is proposed to model a computer network in Section 2.

The proposed algorithm and its working principles are

presented in Section 3. The results of the simulation are pre-

sented in Section 4. Finally, the Section 5 concludes the paper. 2. Mathematical model This section is devoted toward development of a mathematical

model and problem statement to be used in the next section. A network is modeled as a directed, connected graph G = (V, E), where V is a ﬁnite set of vertices (network nodes) and E is the set of edges (network links), representing connec-

tion of these vertices. Let n = |V| be the number of network

nodes and l = |E| be the number of network links. The link

e = (u, ) from node u e V to node v e V implies the existence of a link e0 = (, u) from node v to node u. Four non-negative

real value functions are associated with each link e(e e E): cost

C (e): E ﬁ R +, delay D(e): E ﬁ R+, loss rate L(e): E ﬁ R+, and available bandwidth B(e): E ﬁ R +. The link cost func- tion, C(e), may be either monetary cost or any measure of re-

source utilization that must be optimized. The link delay, D(e),

is considered to be the sum of switching, queuing, transmis-

sion, and propagation delays. The link loss rate, L(e), is the

packet loss rate on the receiving end on link e. The link band-

width, B(e), is the residual bandwidth functions. D(e), L(e),

and B(e) deﬁne the criteria that must be constrained

(bounded). Because of the asymmetric nature of the communi-

cation networks, it is often the case that C(e) '' C(e0), D (e) '' D(e0), L(e) '' L(e0), and B(e) '' B(e0). A multicast tree T(s, M) is a subgraph of G spanning the source node s e V and the set of destination nodes M ˝ V {s}. Let m = |M| be the number of multicast destination nodes. We refer to M as the destination group and {{s} [M} the multicast group. In addition, T(s, M) may contain relay

nodes (Steiner nodes), the nodes in the multicast tree but not

in the multicast group. Let PT(s, d) be a unique path in the tree

T from the source node s to a destination node d e M. We now introduce the parameters that characterize the quality of the multicast tree below. 114 M.K. Patel et al. The total cost of the tree T(s, M) is deﬁned as sum of the cost of all links in that tree and can be given by C ðTðs; M' ¼ X e 2Tðs;M' C ðe' ð2:1' The total delay of the path PT(s, d) is simply the sum of the de-

lay of all links along PT(s, d): D ðPTðs; d'' ¼ X e 2PTðs;d' D ðe' ð2:2' Hence, the total loss rate of the path: L ðPTðs; d'' ¼ 1 Y e 2PTðs;d' ð1 Lðe'' ð2:3' The bottleneck bandwidth of the path PT(s, d) is deﬁned as

minimum available residual bandwidth at any link along the

path: B ðPTðs; d'' ¼ minfBðe'; e 2 PTðs; d'g ð2:4' The delay jitter of the tree T(s, M) is deﬁned as the average dif-

ference of delay on the path from the source to the destination

node: DJ ðTðs; M'' ¼ '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' X d 2M ðDðPTðs; d' delay avg' 2' q ð2:5' where delay_avg denotes the average value of delay on the path

from the source to the destination nodes. Let D be the delay constraint, f be the loss rate constraint, b be the bandwidth constraint of the path from source to the

destination node d, and d be the delay jitter constraint. The

multi-constrained least-cost multicast problem is deﬁned as

follows: Minimize C(T(s, M)) subjects to: D ðPTðs; d'' 6 D 8 d 2 M L ðPTðs; d'' 6 f 8 d 2 M B ðPTðs; d'' P b 8 d 2 M DJ ðTðs; M'' 6 d ð2:6' 3. The proposed algorithm (hybrid ACO/PSO algorithm for

multicast routing optimization) In this section, ﬁrst, we discuss the relevant aspects of ACO

and PSO. We proceed to create a hybrid ACO/PSO algorithm

for multicast routing using swarming agents. An agent is an independent processing entity that interacts with the external environment and the other agents to pursue

its particular set of goals. By using the ACO algorithm, the

agents in the systems coordinate their behaviors and communi-

cate their results through the pheromone, which is a shared dy-

namic environment. The self-organizing and self-adapting

system-level behaviors can be obtained through these phero-

mone interactions. Each agent can only observe the limited

environment within its local sensors. In other words, the agent

can only sense the pheromone that is close to its current posi-

tion, while it has no idea of the existence of other pheromone

far away. Without a central host, it is possible that most agents

may easily get locked in a local maximum. On the other hand, the agents using PSO algorithm coordi- nate their behaviors through the random interaction with

other agents. By following certain rules of interaction, the

agents in the population adapt their scheme of belief to the ones that are most successful among their social network. Over

the time, a global optimization can be obtained. In this section,

a hybrid ACO/PSO algorithm is proposed for the optimization

of swarming agent based multicast routing problems. Before

introducing the proposed algorithm, we make brief discussion

on ACO, PSO, and swarming architecture. In the following section, we discuss the two most important optimization algorithms: ACO and PSO followed by discus-

sion on swarming architecture. 3.1. ACO algorithm An ACO algorithm is essentially a system that simulates the

natural behavior of ants, including their mechanisms of coop-

eration and adaptation. The ACO algorithms are based on the

following ideas. First, each path followed by an ant is associ-

ated with a candidate solution for a given problem. Second,

when an ant follows a path, the amount of pheromone depos-

ited on that path is proportional to the quality of the corre-

sponding candidate solution for the target problem. Third,

when an ant has to choose between two or more paths, the

path(s) with a larger amount of pheromone are more attractive

to the ant. After some iteration, eventually, the ants will con-

verge to the path, which is expected to be the optimum or a

near-optimum solution for the target problem. 3.2. PSO algorithm The PSO algorithm is population-based, where a set of poten-

tial solutions evolves to approach a convenient solution (or set

of solutions) for a problem. The aim of this optimization meth-

od is ﬁnding the global optimum of a real-valued function (ﬁt-

ness function) deﬁned in a given space (search space). Rather

than simply a social simulation, the PSO can be treated as a

powerful search algorithm, capable of optimizing a wide range

of N-dimensional problems. In the PSO algorithm, each individual is called a ''''particle,'''' and is subject to a movement in a multidimensional space that

represents the belief space. Particles have memory, and thus,

they retain part of their previous states. There is no restriction

for the particles to share the same point in belief space, but in

any case, their individuality is preserved. Each particle''s move-

ment is the composition of an initial random velocity and two

randomly weighted in'uences: individuality (i.e., the tendency

to return to the particle''s best previous position) and sociality

(i.e., the tendency to move toward the neighborhood''s best

previous position). The velocity and position of the particle at any iteration are updated based on the following equations: v t þ1 id ¼ w:v t

id þ c1:randð'ðp t

id x t

id' þ c2:Randð'ðp t

gd x t

id' ð3:1' x t þ1 id ¼ x t

id þ v t þ1 id ð3:2' where vt id is the component in dimension d of the ith particle velocity in iteration t; xt id is the component in dimension d of the ith particle position in iteration t; c1 and c2 are constant

weight factors; pi is the best position achieved by ith particle;

pgd is the best position found by the neighbors of ith particle;

rand() and Rand() are random factors in the [0, 1] interval; and w is the inertia weight. The PSO algorithm requires tuning of some parameters: the individual weight (c1), sociality weight (c2), and the inertia fac-

tor (w). A hybrid ACO/PSO based algorithm for QoS multicast routing problem 115 3.3. Swarming agent architecture Initially, n multicast tree patterns are generated randomly, and

m key values as attributes are calculated for m destinations of each multicast tree pattern. Therefore, the structure of the pat-

tern is deﬁned by the following equation: Ti ¼ fai1; ai2; . . . . . . ; aimg for i ¼ 1::n ð3:3' where Ti denotes the multicast tree pattern i, aij represents the

j th attribute of pattern i in each pattern, and n is the number of the generated patterns. For each pattern, an associated pattern agent is created which is ﬁxed to the pattern. Then, n numbers of mobile agents

are generated to detect the ﬁt patterns from the randomly gen-

erated patterns and recombine some of the selected patterns

together to build a pattern with more ﬁtness value. These mo-

bile agents are referred as particle agents, which can move from

one pattern to another in the search space and interact with

other particle agents dynamically. Initially, the particle agents

are uniformly distributed in the search space. The particle

agents converge to the ﬁttest pattern eventually after some iter-

ations of the algorithm. The particle agents are allowed to deposit pheromones and sense local attributes in each pattern. The pattern agent is

responsible for executing the dynamics of pheromone aggrega-

tion, dispersion, and evaporation. There are two levels of pher-

omones: one is for pattern pheromone and the other is the

attribute pheromone inside the pattern. The pattern with high

pheromone has either high probability to become the best ﬁt

pattern or some of the attributes inside this pattern have the

higher potential to be included in the best ﬁt pattern. This at-

tracts more particle agents to move to the pattern. The phero-

mone gets evaporated over time if no agent deposits more

pheromone on it. Once an agent enters into a pattern, it depos-

its pheromone on the selected attributes and deposits the pher-

omones on the pattern. So, both pattern and the selected

attributes are proportional to their ﬁtness values. 3.4. Proposed hybrid ACO/PSO algorithm (HACOPSO) Initially, n discriminating candidate patterns are generated

randomly. These patterns are ﬁlled into the grids in the search

space of dimension k l, where each pattern corresponds to one grid based on the order of their generation. Next, n parti-

cle agents are generated and uniformly distributed to the

search space, where each particle agent occupies one grid.

Now, the iteration starts, and for each iteration, ﬁrst each par-

ticle agent evaluates the ﬁtness value of the tree pattern from

the cost of the tree, where it is currently located. Using the

ACO algorithm, pheromones are deposited on each attribute

based on their attribute value by the particle agents. Fig. 1 shows the grid of dimension 5 · 6 in which thirty multicast tree patterns are ﬁlled. The pattern agent Ti is asso-

ciated with ith multicast tree pattern and ﬁlled sequentially in

row major fashion. Thirty mobile particle agents are randomly

distributed in search space where each particle agent is at-

tached to one pattern agent. Due to the ﬁxed topology of the particle agents in the search grid, the maximum number of neighbors is 8 as shown

in Fig. 1. Hence, the particle agent can interact with the

maximum 8 neighboring particle agents only. If the ﬁtness of

the best neighbor is higher than the current pattern, then it is set as the agent''s best previous position. Then, the PSO

algorithm is used to update the pattern pheromone and attri-

bute pheromone comparing the ﬁtness of the trees and their

corresponding attributes. This process is repeated for a ﬁxed

number of iterations, and the pattern with the maximum ﬁt-

ness is returned as the solution that satisﬁes all the constraints.

The pseudo-code of the proposed hybrid ACO/PSO algorithm

is outlined below. 3.4.1. Pseudo-code for hybrid ACO/PSO algorithm Algorithm HACOPSO (s, n, m, Countmax) / \ n is the maximum number of pattern generated, s is the source node, m is the number of receivers and Countmax is the maximum number of iterations the HACOPSO runs \/ Generate randomly n discriminating candidate patterns Ti Fill the patterns into the grid of dimension kxl based on the order of their generation. Generate n particle agents randomly and distribute them uniformly over the search space so that each particle agent occupies one grid. while (itr < Countmax) / \ Use ACO algorithm to accept pheromone to the pattern and attributes \ / for i = 1 to n Update the pheromone of the pattern selected by the particle agents i, Otherwise, decrease the pheromone in the pattern. for j = 1 to m Update the pheromone of all attributes trail, by increasing pheromone in the trails followed by agent i. end for end for / \ Use the modified PSO algorithm to adjust the movement of the particle agent in this iteration \ / for i = 1 to n Update the pattern and attribute pheromone If pattern fitness of current position < their best neighbors'' pattern fitness value, Then move to the neighbor''s pattern. If the fitness value of the attribute(s) in the last position is higher than the new position, Then replace those lower-fitness-value attribute with the higher-fitness-value attribute from last position. If the newly generated pattern has more fitness than the earlier fitness, Then update the attribute with higher fitness. end for end while The multicast tree patterns are generated randomly, and these

patterns reside in a search space which is deﬁned as a k · l**T** **1** **p** **5** **T** **2** **p** **9** **T** **3** **p** **25** **T** **4** **p** **30** **T** **5** **p** **2** **T** **6** **p** **8** **T** **7** **p** **6** **T** **8** ** p** **10** **T** **9** **p** **26** **T** **10** **p** **29** **T** **11** **p** **28** **T** **12** **p** **27** **T** **13** **p** **7** **T** **14** **p** **11** ** T** ** p** **1** **T** **16** **p** **24** **T** **17** **p** **12** **T** **18** **p** **22** **T** **19** **p** **4** **T** **20** **p** **14** **T** **21** **p** **21** **T** **22** **p** **17** **T** **23** **p** **20** **T** **24** **p** **19** **T** **25** **p** **23** **T** **26** **p** **18** **T** **27** **p** **16** **T** **28** **p** **15** **T** **29** **p** **13** **T** **30** **p** **3** **15** Figure 1 Arrangement of particle and pattern agents. 116 M.K. Patel et al. rectangular grid. Given source node s, the group member

d1, d2, d3, . . ., dm where m is the number of group members.

The pseudo-code for multicast tree generation is given below. 3.4.2. Pseudo-code for multicast tree pattern generation procedure PatternGeneration (Ti) 1. Begin 2. initialize VT = {s} 3. delaysofar(s) = 1, losssofar(s) = 1, costsofar(s) = 0; 4. cur_node = s 5. repeat 6. Ncur_node = / 7. for each neighbour node v of the cur_node such that v R VT 8. if(B(cur_node,v) P b and delaysofar(cur_node)+ D(cur_node) 6 D and 1-(losssofar(cur_node) \ (1-L(cur_node,v)) 6 f) 9. Ncur_node = Ncur_node [ {v} 10. end if 11. end for 12. j = SelectRandom(Ncur_node) 13. cost = cost + C(cur_node, j) 14. costsofar(j) = costsofar(cur_node) + C(cur_node,j) 15. pheromone(j) = 1/costsofar(j) 16. delaysofar(j) = delaysofar(cur_node) + D(curnode,j) 17. losssofar(j) = losssofar(cur_node) \ (1 L(curnode,j)) 18. if(j R M){ 19. cur_node = j 20. else 21. cur_node = SelectRandom(VT) 22. for all (u e M and u e VT) 23. pheromone(u) = pheromone(u)+pheromone(cur_node) 24. end for all 25. end if 26. until (VT contains all nodes of the multicast group) 27. if Ti satisfies the delay jitter that is DJ(Ti(s,M)) 6 d 28. then calculate pheromone(Ti)from the cost of the tree 29. return Ti 30. end PatternGeneration Initially, the multicast tree VT is set to the source node s, which

is also set as the current node. Accumulated delay and loss up

to source node s, delaysofar(s) and losssofar(s), are set to 0 and 1, respectively. Then, a node j is selected randomly from the

neighbor nodes of the current node that satisﬁes the QoS con-

straints. The node j is added to the multicast VT, and the delay-

sofar (j) and losssofar(j) up to node j are calculated as shown in Steps 14 and 15 of the algorithm, respectively. If the node j is

not the destination node, then the current node is set to j;

otherwise, the current node is selected randomly from VT.

The pheromones of the multicast group member that are al-

ready added to the multicast tree are updated as shown in Step

23. This process is repeated till all the group members are

added to the multicast tree. The particle moves to the new position and brings the last position''s attribute and its associated ﬁtness values along with

its movement to the new position. The new position is updated

with better quality attributes discarding the low quality attri-

bute of the new position. The outcome is a new combined

pattern with higher quality than both original ones. During

the next iteration, the newly built pattern will be executed by

the agents and deposit the pheromone as appropriate. After

much iteration, eventually, the most strong pheromone trail

will be the ﬁttest discriminating pattern. 3.4.3. Time complexity In this subsection, the time complexity of the proposed algo-

rithm is carried out. The proposed algorithm uses procedure

PatternGeneration to generate a QoS aware multicast tree pat- tern randomly. In the PatternGeneration procedure, the lines

02''04 initialize the variables in O(1). The maximum number

of neighboring nodes of a node can be n. Therefore, the worst

case time complexity of line 07 is O(n). The lines 08 and 09 are

computed in O(1). Thus, the lines 07''11 can be computed in

O (n). The lines 12''21 are computed in O(1). The lines 22''24 are computed in O(m), where m is the number of destinations.

The worst case time complexity of computation performed in

lines 6''25 is O(n). Since the lines 6''25 are executed for m num-

ber of iterations, the worst case time complexity of the proce-

dure PatternGeneration is O(mn). The proposed HACOPSO algorithm starts with generating partnum number of tree patterns and runs for a maximum Countmax number of iterations. In each iteration, the n particle

agents interact with maximum 8 numbers of neighbors, and

the pheromone of maximum m number of attributes is up-

dated. The worst case time complexity of our proposed algo-

rithm is O(partnum · Countmax · n · m · 8) i.e. O(m · n · partnum · Countmax). The time complexity of TGBACA [8] is O (Countmax · antnum · n · |E|), and the time complexity of PSOTREE [17] is O(Countmax · partnum · n 2) where Count max is the maximum number of iterations, antnum and partnum

are the number of ants and number of particles, respectively,

n is the number of nodes, |E| is the number of edges, and m is the number of receivers. Thus, it is clear that the complexity

of the proposed algorithm is comparable to the existing algo-

rithms [17,8]. 4. Simulation results We have implemented our proposed algorithm in Visual C ++. The experiments are performed on an Intel Core i3 @ 2.27

G.Hz. and 2 GB RAM based platform running Windows

7.0.The positions of the nodes are ﬁxed randomly in a rectan-

gle of size 4000 km · 2400 km. The Euclidean metric is then**5** **10** **15** **20** **25** **30** **35** **40** **45** **50** **400** **800** **1200** **1600** **2000** **2400** **2800** **Multicast group size** **Multicast** **tree** **cost** **Proposed Algorithm** **PSOTREE[17]** **TGBACA[8]** Figure 2 Multicast tree cost vs. group size (No of nodes = 100). A hybrid ACO/PSO based algorithm for QoS multicast routing problem 117 used to determine the distance between each pair of nodes. The

network topology used in our simulation was generated ran-

domly using Waxman''s topology [22]. The edges are intro-

duced between the pairs of nodes u and v with a probability

that depends on the distance between them. The edge probabil-

ity is given by P(u, ) = b exp ( l(u, v)/aL), where 0 < a, b <=1 l(u, v) is the Euler distance from node u to v and L is the maximum distance between any two points in the network.

The value of a controls the number of short links in the ran-

domly generated network topology. The smaller the value of

a, the higher is the number of shorter links. Similarly, b con-

trols the number of links in the randomly generated network

topology. The lower the value of b, the larger is the number

of links. The value of a and b is set to 0.8 and 0.7, respectively,

in our simulation setup. The delay, loss rate, and band width

of the links are set randomly from 1 to 30, 0.0001 to 0.01,

and 2 to 10 Mbps, respectively. Similarly, the cost parameter

is set to be 1''100. The maximum number of iterations Countmax

is considered to be 30. The source node is selected randomly and destination nodes are picked up uniformly from the set of nodes chosen in the net-

work topology. The delay bound D, the delay jitter bound, and

the loss bound are set 120 ms, 60 ms, and 0.05, respectively. The

bandwidth requested by a multicast application is generated

randomly. We also implemented PSOTREE [17] and TGBACA

[8] algorithms in the same environment to study and compare

the performance of our proposed algorithm with the existing

algorithms. We generated 30 multicast trees randomly to study

the performances of PSOTREE and TGBACA, and next 30

multicast trees are generated for our proposed algorithm. These

30 multicast tree patterns are arranged in a rectangular grid of

size 5 · 6 in the order of their generation. The simulation is run for 100 times for each case, and the average of the multicast

tree cost is taken as the output.**20** **40** **60** **80** **100** **120** **140** **200** **400** **600** **800** **1000** **Number of network nodes (10% destination)** **Multicast tree cost** **Proposed Algorithm** **PSOT REE[17]** **T GBACA[8]** Figure 3 Multicast tree cost vs. network size with 10% nodes as destinations. **20** **40** **60** **80** **100** **120** **140** **200** **400** **600** **800** **1000** **1200** **1400** **1600** **1800** **Number of network nodes (25% destination)** **Multicast tree cost** **Proposed Algorithm** **PSOTREE[17]** **TGBACA[8]** Figure 4 Multicast tree cost vs. network size with 25% nodes as destinations. 85 90 95 100 105 110 115 20 40 60 80 100 120 140 **Number of network nodes (20% destination)** **Multicast Tree Delay (ms)** Proposed Algorithm PSOTREE[17] TGBACA[8] Figure 5 Multicast tree delay vs. network size with 20% nodes as destinations. 0 10 20 30 40 50 60 20 40 60 80 100 120 140 **Number of network nodes (20% destination)** **Delay Jitter (ms)** Proposed Algorithm PSOTREE[17] TGBACA[8] Figure 6 Multicast tree delay jitter vs. network size with 20% nodes as destinations. **10** **20** **30** **40** **50** **60** **70** **0** **25** **50** **75** **100** **125** **150** **175** **200** **Number of Destinations** **Execution Time (ms)** **Proposed Algorithm **

PSOTREE[17]

TGBACA[8] Figure 7 Comparison of execution time (ms) in different topology scales (No of nodes = 100). 118 M.K. Patel et al. The multicast tree cost versus multicast group size for a net- work of 100 nodes is shown in Fig. 2. Figs. 3 and 4 show the

multicast tree cost versus the network size with 10% and 25%

of the nodes as the group size, respectively. The multicast trees

generated by PSOTREE, TGBACA, and our proposed algo-

rithm satisfy the delay, delay jitter, loss rate, and bandwidth

constraints. However, the results clearly reveal that the cost

of the multicast tree generated by our proposed algorithm is

less than the multicast trees generated by the PSOTREE and

TGBACA [8]. The PSOTREE [17] algorithm constructs the

multicast tree by combining the multicast trees and removing

directed cycles. This algorithm in [17] removes the links that

are in any of the trees, but not in both, and have minimum ﬁt-

ness. However, the approach [17] fails to generate a better tree,

because the links deleted from the cycle may be better than the

links not in the directed cycles. The TGBACA algorithm [8]

follows a pheromone updating strategy to construct the best

multicast tree. The algorithm updates pheromones on the links

used by the global best tree and the best tree generated after

each generation. Though this strategy accelerates the conver-

gence process, the solution falls into local optimization. However, our algorithm combines two multicast tree pat- terns by bringing the better attributes of one pattern to another

pattern. It generates a new tree pattern after each iteration,

which is better than both the patterns. Therefore, the proposed

algorithm converges to a multicast tree after a few iterations. Considering the above aspects, our algorithm (HACOPSO)

is found to perform better in comparison with the previous

works PSOTREE [17] and TGBACA [8]. Figs. 5 and 6 show the multicast tree delay and delay jitter for a network of 100 nodes with 20% nodes as destinations,

respectively. It is observed that the proposed algorithm along

with PSOTREE [17] and TGBACA [8] satisﬁes the delay and

the delay jitter constraints. The multicast tree generated by

our algorithm experiences a delay and delay jitter comparable

with PSOTREE [17] and TGBACA [8]. However, the multicast

tree generated by our algorithm performs signiﬁcantly better in

terms of multicast tree cost. The Comparison of execution time in milliseconds is shown in Figs. 7''9. Figs. 8 and 9 show the comparison of execution

time for a network of nodes with 10% nodes as destinations

and for 25% nodes as destinations, respectively. It can be ob-

served that the execution time of our proposed algorithm is

less than that of the existing algorithms. This is because in

our algorithm when two particle agents interact, the path of

one tree pattern is replaced by the better path of another tree

pattern. In PSOTREE, the two trees are merged and the loops

are deleted for which it takes more time. In TGBACA, the

trees are constructed, and then, the ﬁnal tree is constructed

after tree pruning. Thus, the execution time is less than the

PSOTREE and more than our proposed algorithm as shown

in the Figs. 7''9. 5. Conclusions This paper presented a swarming agent based intelligent hy-

brid algorithm (HACOPSO) algorithm using the concept of

ACO and PSO. The performance of the proposed algorithm

was evaluated through extensive simulation. The results of

simulation are compared with two existing algorithms PSO-

TREE [17] and TGBACA [8]. Our algorithm is found to con-

struct the multicast tree patterns more sensibly such that the

tree patterns not only satisfy the QoS constraints, but also tries

to minimize the tree cost. The proposed algorithm also uses the

collective and coordination process for the mobile agents at-

tached to each pattern. The ﬁnal multicast trees generated by

our algorithm are found better compared to the multicast trees

generated by PSOTREE [17] and TGBACA [8]. The time com-

plexity of our algorithm is also found to be comparable to the

existing ones. References [1] Hakimi SL. Steiner problem in graphs and its implementation. Networks 1971;1:113''33. [2] Di Caro G, Dorigo M. AntNet: a mobile agents for adaptive routing. In: Proceedings of the 31st Hawaii international confer-

ence on systems; 1998. p. 74''83. [3] Di Caro G, Dorigo M. AntNet: distributed stigmergetic control for communications networks. J Artiﬁc Intell Res 1998;9:317''65. [4] Dorigo M, Di Caro G. The ant colony optimization meta- heuristic, new ideas in optimization. McGraw-Hill; 1999. [5] Sim KM, Sun WH. Ant colony optimization for routing and load balancing: survey and new directions. IEEE Trans Syst, Man,

Cybernet 2003;33:560''72. [6] Cheng H, Cao J, Wang X. A heuristic multicast algorithm to support QoS group communications in heterogeneous network.

IEEE Trans Vehicul Technol 2006;55(3):831''8.**20** **40** **60** **80** **100** **120** **140** **0** **25** **50** **75** **100** **125** **150** **175** **200** **Number of network nodes (10% destination)** **Execution Time (ms)** **Proposed Algorithm** **PSOTREE[17]**

TGBACA[8] Figure 8 Comparison of execution time (ms) in different topology scales for 10% nodes as destinations. **20** **40** **60** **80** **100** **120** **140** **0** **50** **100** **150** **200** **250** **Number of network nodes (25% destination)** **Execution Time (ms)** **Proposed Algorithm** **PSOTREE[17]** **TGBACA[8]** Figure 9 Comparison of execution time (ms) in different topology scales for 25% nodes as destinations. A hybrid ACO/PSO based algorithm for QoS multicast routing problem 119 [7] Mullen R, Monekosso D, Barman S, Remagnino P. A review of ant algorithms. Exp Syst Appl 2009;36(6):9608''17. [8] Wang H, Xu H, Yi S, Shi Z. A tree-growth based ant colony algorithm for QoS multicast routing problem. Exp Syst Appl

2011;38:11787''95. [9] Gong B, Li L, Wang X. Multicast routing based on ant algorithm with multiple constraints; 2007. [10] Zheng YX, Tian J, Dou WH. Vector constraint multicast routing based on GA. Chin J Comput 2003;26:746''52. [11] Haghighat A, Faez K, Dehghan M, Mowlaei A, Ghahremani Y. GA based heuristic algorithms for bandwidth-delay-con-

strained least-cost multicast routing. Comput Commun 2004;27(1):111''27. [12] Zhou J, Cao Q, Li C, Huang R. A genetic algorithm based on extended sequence and topology encoding for the multicast

protocol in two-tiered WSN. Exp Syst Appl 2010;37(2):1684''95. [13] Kennedy J, Eberhart RC. Particle swarm optimization. In: IEEE International Conference on Neural Network, Perth, Australia;

1995. p. 1942''8. [14] Liu J, Sun J, Xu W. QoS multicast routing based on particle swarm optimization. Lect Notes Comput Sci 2006;4224:936''43. [15] Sun J, Liu J, Xu W. QPSO-based QoS multicast routing algorithm. Lect Notes Comput Sci 2006;4247:261''8. [16] Li C, Cao C, Li Y, Yu Y. Hybrid of genetic algorithm and particle swarm optimization for multicast QoS routing. In: IEEE interna-

tional conference controls automation; 2007. p. 2355''9. [17] Wang H, Meng X, Li S, Xu H. A tree-based particle swarm optimization for multicast routing. Comput Netw 2010;54:

2775''86. [18] Ghaboosi N, Haghighat A. Tabu search based algorithms for bandwidth delay-constrained least-cost multicast routing. Tele-

commun Syst 2007;34(3):147''66. [19] Wang H, Meng X, Zhang M, Li Y. Tabu search algorithm for RP selection in PIM-SM multicast routing. Elsevier Comput Com-

mun 2009;33:35''42. [20] Brueckner SA, Parunak HVD. Swarming agents for distributed pattern detection and classiﬁcation. Lect Notes Artiﬁc Intell

2005;3374:232''45. [21] Meng Y. A swarm intelligence based algorithm for proteomic pattern detection of ovarian cancer. In: IEEE symposium on

computational intelligence in bioinformatics and computational

biology; 2006. p. 1''7. [22] Waxman BM. Routing of multipoint connections. IEEE J Select Areas Commun 1988;6(9):1617''22. Manoj Kumar Patel has received his M.Sc in

Mathematics and MCA from Sambalpur

University and IGNOU, India. He is currently

pursuing Ph.D under Sambalpur University,

India. He is also working as a Technical Asst.

Gr-I(Computer) in the Department of Com-

puter Science & Engineering at Veer Surendra

Sai University of Technology, India. His

research area includes QoS Routing, Reliable

Multicast and Soft Computing Techniques.

He has published about 07 research papers in various International Journals and Conferences. Manas Ranjan Kabat has received his M.E.

degree in Information Technology and Com-

puter Engineering from Bengal Engineering

College, India, and the Ph.D degree in Com-

puter Science and Engineering from Sambal-

pur University, India. He is currently working

as Reader and Head in the Department of

Computer Science and Engineering at Veer

Surendra Sai University of Technology, Odisha, India. His research involves Multicast

Routing, Reliable Multicast, High Speed Computer Networks and e-Governance. He has published about 12

research papers in various International Journals and Conferences. Chita Ranjan Tripathy is a Professor, Department of Computer Science and Engi-

neering, Veer Surendra Sai University of

Technology, Odisha, India. He received his

Master Degree and Ph.D in Computer Science

and Engineering from Indian Institute of

Technology, Kharagpur, India. He has pub-

lished more than 80 research papers in dif-

ferent International journals and conferences.

His research area includes Computer Net-

works, Parallel Processing and Reliability. He has received his ''''Sir Thomas Ward Memorial'''' gold medal for

researches in Parallel Processing. He is a Fellow of Institution of

Engineers (India) and life member of Indian Society for Technical

Education (ISTE), Instrument Society of India and Orissa Information

Technology Society (OITS). 120 M.K. Patel et al.# Document Outline

A hybrid ACO/PSO based algorithm for QoS multicast routing problem 1 Introduction 2 Mathematical model 3 The proposed algorithm (hybrid ACO/PSO algorithm for multicast routing optimization) 3.1 ACO algorithm 3.2 PSO algorithm 3.3 Swarming agent architecture 3.4 Proposed hybrid ACO/PSO algorithm (HACOPSO) 3.4.1 Pseudo-code for hybrid ACO/PSO algorithm 3.4.2 Pseudo-code for multicast tree pattern generation 3.4.3 Time complexity 4 Simulation results 5 Conclusions References

multicast routing problem Manoj Kumar Patel *, Manas Ranjan Kabat, Chita Ranjan Tripathy Dept. of Comp. Sc. & Engg., Veer Surendra Sai University of Technology, Burla, Sambalpur, Orissa, India Received 1 January 2013; revised 22 June 2013; accepted 18 July 2013

Available online 7 October 2013 KEYWORDS Swarm agent;

ACO;

PSO;

Multicast;

QoS routing Abstract Many Internet multicast applications such as videoconferencing, distance education, and online simulation require to send information from a source to some selected destinations. These

applications have stringent Quality-of-Service (QoS) requirements that include delay, loss rate,

bandwidth, and delay jitter. This leads to the problem of routing multicast trafﬁc satisfying QoS

requirements. The above mentioned problem is known as the QoS constrained multicast routing

problem and is NP Complete. In this paper, we present a swarming agent based intelligent algo-

rithm using a hybrid Ant Colony Optimization (ACO)/Particle Swarm Optimization (PSO) tech-

nique to optimize the multicast tree. The algorithm starts with generating a large amount of

mobile agents in the search space. The ACO algorithm guides the agents'' movement by pheromones

in the shared environment locally, and the global maximum of the attribute values are obtained

through the random interaction between the agents using PSO algorithm. The performance of

the proposed algorithm is evaluated through simulation. The simulation results reveal that our algo-

rithm performs better than the existing algorithms. 2013 Production and hosting by Elsevier B.V. on behalf of Ain Shams University. 1. Introduction The rapid development in network multimedia technology has

enabled more and more real-time multimedia services such as

videoconferencing, online games, and distance education to

become the mainstream Internet activities. These services often

require the underlying network to provide multicast capabili- ties. The multicast refers to the delivery of packets from a

single source to multiple destinations. These real-time applica-

tions have a stringent requirement of QoS parameters like

bandwidth, delay, jitter, and so on to ensure smooth,

consistent, and fair transmission to the receivers. The central

problem of QoS routing is to set up a multicast tree that can

satisfy certain QoS parameters. However, the problem of

constructing a multicast tree under multiple constraints is

NP Complete [1]. Hence, the problem is usually solved by

heuristics or intelligent optimization. In recent years, some meta-heuristic algorithms such as the ant colony algorithm [2''9], genetic algorithm [10''12], particle

swarm optimization [13''17], and Tabu search [18,19] have

been adopted by the researchers to solve the multi-constrained

QoS routing problems. * Corresponding author. Tel.: +91 9861461357.

E-mail addresses: patel.mkp@gmail.com (M.K. Patel), manas_kaba-

t@yahoo.com (M.R. Kabat), crt.vssut@yahoo.com (C.R. Tripathy). Peer review under responsibility of Ain Shams University.

attractive distribution features and it can ﬁnd a near-optimal

path from the source node to each destination node. It also pro-

vides the required results in simulation. Although the ANTNET

is a unicast routing algorithm, it can be easily applied to multi-

cast routing with some modiﬁcations. In spite of the said merits

of the ANTNET, it suffers from a serious drawback i.e. the slow

convergence rate. Another ant intelligence algorithm was intro-

duced in [3] for the computation of the QoS multicast tree. A tree

growth based ACO algorithm (TGBACA) has been proposed in

[8]. It generates a multicast tree in the way of tree growth and

optimizes the ant colony parameters through their most efﬁcient

combinations. The major weakness of the ant colony algorithm

is that it converges slowly at the initial step and takes more time

to converge. This happens due to improper selection of the ini-

tial feasible parameter [3]. The overhead also increases due to

merging and pruning of the trees. Subsequently, the genetic algorithm (GA) was used to ﬁnd a multicast tree satisfying the constraints of bandwidth and de-

lay with least cost [10''12]. The GA has three operators: selec-

tion, crossover, and mutation. The individuals are stored in

connective matrices by adopting the binary coding system.

The initial colony is generated randomly without considering

QoS constraints. The selection operation adopts Roulette

wheel algorithm to select the best individuals from the parent

generation to pass onto the child generation. Then, the cross-

over operation is used to ﬁnd out the ﬁttest among the best. A

penalty function is adopted to solve QoS constraints in the

multicast trees, which do not satisfy QoS constraints.

Although sometimes the algorithm''s performance is observed

to be satisfactory, still it encounters some faults, such as the

local search ability, premature convergence, and slow convergence speed. Further, the genetic algorithm does not

assure to ﬁnd a global optimum. It happens very often when

the populations have a lot of subjects. In [13''17], researchers have proposed some PSO algorithms to solve QoS constraint routing problem. The PSO algorithm

proposed in [14] solves the QoS multicast routing problem

and can obtain a feasible multicast tree by exchanging the

paths. This algorithm can converge to the optimal or

near-optimal solution with lower computational cost. Another

algorithm based on the concept of quantum mechanics named

as Quantum-Behaved Particle Swarm Optimization (QPSO)

was proposed in [15]. Here, the proposed method converts

the QoS multicast routing problem into integer programming

problem and then ﬁnally solves using the QPSO. The QPSO

ﬁnds the path from the source node to each destination node

and constructs the tree by merging the paths. A tree based

PSO has been proposed in [17] for optimizing the multicast tree

directly. However, its performance depends on the number of

particles generated. Another drawback of the said algorithm is

the merging of multicast trees. The elimination of directed cir-

cles and nesting of directed circles are also very complex and

are considered as some of the limitations of the PSO [17]. In recent days, many researchers have solved the QoS constrained multicast tree using Tabu search [18,19]. A Tabu

search method was proposed in [18] to search for the multicast

tree with the least cost that satisﬁes the constraints of band-

width and delay. This algorithm obtains a complete graph of

all group members at the initial step and obtains the initial

Steiner tree via the generated tree of the complete graph. In this way, the k-shortest paths replace the edges to ﬁnd the

chances of getting better results. The method mentioned above

is similar to the method of path combination. However, it does

not operate directly on the multicast tree. This weakness makes

it impossible to eliminate the constraints of conventional

multicast routing algorithms. Hence, there arises a need to

proceed further and do more amount of work in searching

paths and integrating the multicast trees. In this paper, we propose a hybrid ACO/PSO algorithm based on the swarming agent architecture for QoS multicast

routing. Our work is inspired by the swarming agent algorithm

proposed by Brueckner and Parunak [20] for distributed data

pattern and Meng [21] for Proteomic Pattern detection of

ovarian cancer. In our work, a large amount of mobile agents

are generated in the search space. Two collective and coordina-

tion process for the mobile agents are proposed. One is based

on the ACO [8] algorithm for guiding the agents'' movements

by pheromones in the shared environment locally and the

another is based on the PSO algorithm [17] for obtaining the

global maximum of the attribute values through the random

interaction between the agents. The rest of the paper is organized as follows: A mathematical model is proposed to model a computer network in Section 2.

The proposed algorithm and its working principles are

presented in Section 3. The results of the simulation are pre-

sented in Section 4. Finally, the Section 5 concludes the paper. 2. Mathematical model This section is devoted toward development of a mathematical

model and problem statement to be used in the next section. A network is modeled as a directed, connected graph G = (V, E), where V is a ﬁnite set of vertices (network nodes) and E is the set of edges (network links), representing connec-

tion of these vertices. Let n = |V| be the number of network

nodes and l = |E| be the number of network links. The link

e = (u, ) from node u e V to node v e V implies the existence of a link e0 = (, u) from node v to node u. Four non-negative

real value functions are associated with each link e(e e E): cost

C (e): E ﬁ R +, delay D(e): E ﬁ R+, loss rate L(e): E ﬁ R+, and available bandwidth B(e): E ﬁ R +. The link cost func- tion, C(e), may be either monetary cost or any measure of re-

source utilization that must be optimized. The link delay, D(e),

is considered to be the sum of switching, queuing, transmis-

sion, and propagation delays. The link loss rate, L(e), is the

packet loss rate on the receiving end on link e. The link band-

width, B(e), is the residual bandwidth functions. D(e), L(e),

and B(e) deﬁne the criteria that must be constrained

(bounded). Because of the asymmetric nature of the communi-

cation networks, it is often the case that C(e) '' C(e0), D (e) '' D(e0), L(e) '' L(e0), and B(e) '' B(e0). A multicast tree T(s, M) is a subgraph of G spanning the source node s e V and the set of destination nodes M ˝ V {s}. Let m = |M| be the number of multicast destination nodes. We refer to M as the destination group and {{s} [M} the multicast group. In addition, T(s, M) may contain relay

nodes (Steiner nodes), the nodes in the multicast tree but not

in the multicast group. Let PT(s, d) be a unique path in the tree

T from the source node s to a destination node d e M. We now introduce the parameters that characterize the quality of the multicast tree below. 114 M.K. Patel et al. The total cost of the tree T(s, M) is deﬁned as sum of the cost of all links in that tree and can be given by C ðTðs; M' ¼ X e 2Tðs;M' C ðe' ð2:1' The total delay of the path PT(s, d) is simply the sum of the de-

lay of all links along PT(s, d): D ðPTðs; d'' ¼ X e 2PTðs;d' D ðe' ð2:2' Hence, the total loss rate of the path: L ðPTðs; d'' ¼ 1 Y e 2PTðs;d' ð1 Lðe'' ð2:3' The bottleneck bandwidth of the path PT(s, d) is deﬁned as

minimum available residual bandwidth at any link along the

path: B ðPTðs; d'' ¼ minfBðe'; e 2 PTðs; d'g ð2:4' The delay jitter of the tree T(s, M) is deﬁned as the average dif-

ference of delay on the path from the source to the destination

node: DJ ðTðs; M'' ¼ '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' X d 2M ðDðPTðs; d' delay avg' 2' q ð2:5' where delay_avg denotes the average value of delay on the path

from the source to the destination nodes. Let D be the delay constraint, f be the loss rate constraint, b be the bandwidth constraint of the path from source to the

destination node d, and d be the delay jitter constraint. The

multi-constrained least-cost multicast problem is deﬁned as

follows: Minimize C(T(s, M)) subjects to: D ðPTðs; d'' 6 D 8 d 2 M L ðPTðs; d'' 6 f 8 d 2 M B ðPTðs; d'' P b 8 d 2 M DJ ðTðs; M'' 6 d ð2:6' 3. The proposed algorithm (hybrid ACO/PSO algorithm for

multicast routing optimization) In this section, ﬁrst, we discuss the relevant aspects of ACO

and PSO. We proceed to create a hybrid ACO/PSO algorithm

for multicast routing using swarming agents. An agent is an independent processing entity that interacts with the external environment and the other agents to pursue

its particular set of goals. By using the ACO algorithm, the

agents in the systems coordinate their behaviors and communi-

cate their results through the pheromone, which is a shared dy-

namic environment. The self-organizing and self-adapting

system-level behaviors can be obtained through these phero-

mone interactions. Each agent can only observe the limited

environment within its local sensors. In other words, the agent

can only sense the pheromone that is close to its current posi-

tion, while it has no idea of the existence of other pheromone

far away. Without a central host, it is possible that most agents

may easily get locked in a local maximum. On the other hand, the agents using PSO algorithm coordi- nate their behaviors through the random interaction with

other agents. By following certain rules of interaction, the

agents in the population adapt their scheme of belief to the ones that are most successful among their social network. Over

the time, a global optimization can be obtained. In this section,

a hybrid ACO/PSO algorithm is proposed for the optimization

of swarming agent based multicast routing problems. Before

introducing the proposed algorithm, we make brief discussion

on ACO, PSO, and swarming architecture. In the following section, we discuss the two most important optimization algorithms: ACO and PSO followed by discus-

sion on swarming architecture. 3.1. ACO algorithm An ACO algorithm is essentially a system that simulates the

natural behavior of ants, including their mechanisms of coop-

eration and adaptation. The ACO algorithms are based on the

following ideas. First, each path followed by an ant is associ-

ated with a candidate solution for a given problem. Second,

when an ant follows a path, the amount of pheromone depos-

ited on that path is proportional to the quality of the corre-

sponding candidate solution for the target problem. Third,

when an ant has to choose between two or more paths, the

path(s) with a larger amount of pheromone are more attractive

to the ant. After some iteration, eventually, the ants will con-

verge to the path, which is expected to be the optimum or a

near-optimum solution for the target problem. 3.2. PSO algorithm The PSO algorithm is population-based, where a set of poten-

tial solutions evolves to approach a convenient solution (or set

of solutions) for a problem. The aim of this optimization meth-

od is ﬁnding the global optimum of a real-valued function (ﬁt-

ness function) deﬁned in a given space (search space). Rather

than simply a social simulation, the PSO can be treated as a

powerful search algorithm, capable of optimizing a wide range

of N-dimensional problems. In the PSO algorithm, each individual is called a ''''particle,'''' and is subject to a movement in a multidimensional space that

represents the belief space. Particles have memory, and thus,

they retain part of their previous states. There is no restriction

for the particles to share the same point in belief space, but in

any case, their individuality is preserved. Each particle''s move-

ment is the composition of an initial random velocity and two

randomly weighted in'uences: individuality (i.e., the tendency

to return to the particle''s best previous position) and sociality

(i.e., the tendency to move toward the neighborhood''s best

previous position). The velocity and position of the particle at any iteration are updated based on the following equations: v t þ1 id ¼ w:v t

id þ c1:randð'ðp t

id x t

id' þ c2:Randð'ðp t

gd x t

id' ð3:1' x t þ1 id ¼ x t

id þ v t þ1 id ð3:2' where vt id is the component in dimension d of the ith particle velocity in iteration t; xt id is the component in dimension d of the ith particle position in iteration t; c1 and c2 are constant

weight factors; pi is the best position achieved by ith particle;

pgd is the best position found by the neighbors of ith particle;

rand() and Rand() are random factors in the [0, 1] interval; and w is the inertia weight. The PSO algorithm requires tuning of some parameters: the individual weight (c1), sociality weight (c2), and the inertia fac-

tor (w). A hybrid ACO/PSO based algorithm for QoS multicast routing problem 115 3.3. Swarming agent architecture Initially, n multicast tree patterns are generated randomly, and

m key values as attributes are calculated for m destinations of each multicast tree pattern. Therefore, the structure of the pat-

tern is deﬁned by the following equation: Ti ¼ fai1; ai2; . . . . . . ; aimg for i ¼ 1::n ð3:3' where Ti denotes the multicast tree pattern i, aij represents the

j th attribute of pattern i in each pattern, and n is the number of the generated patterns. For each pattern, an associated pattern agent is created which is ﬁxed to the pattern. Then, n numbers of mobile agents

are generated to detect the ﬁt patterns from the randomly gen-

erated patterns and recombine some of the selected patterns

together to build a pattern with more ﬁtness value. These mo-

bile agents are referred as particle agents, which can move from

one pattern to another in the search space and interact with

other particle agents dynamically. Initially, the particle agents

are uniformly distributed in the search space. The particle

agents converge to the ﬁttest pattern eventually after some iter-

ations of the algorithm. The particle agents are allowed to deposit pheromones and sense local attributes in each pattern. The pattern agent is

responsible for executing the dynamics of pheromone aggrega-

tion, dispersion, and evaporation. There are two levels of pher-

omones: one is for pattern pheromone and the other is the

attribute pheromone inside the pattern. The pattern with high

pheromone has either high probability to become the best ﬁt

pattern or some of the attributes inside this pattern have the

higher potential to be included in the best ﬁt pattern. This at-

tracts more particle agents to move to the pattern. The phero-

mone gets evaporated over time if no agent deposits more

pheromone on it. Once an agent enters into a pattern, it depos-

its pheromone on the selected attributes and deposits the pher-

omones on the pattern. So, both pattern and the selected

attributes are proportional to their ﬁtness values. 3.4. Proposed hybrid ACO/PSO algorithm (HACOPSO) Initially, n discriminating candidate patterns are generated

randomly. These patterns are ﬁlled into the grids in the search

space of dimension k l, where each pattern corresponds to one grid based on the order of their generation. Next, n parti-

cle agents are generated and uniformly distributed to the

search space, where each particle agent occupies one grid.

Now, the iteration starts, and for each iteration, ﬁrst each par-

ticle agent evaluates the ﬁtness value of the tree pattern from

the cost of the tree, where it is currently located. Using the

ACO algorithm, pheromones are deposited on each attribute

based on their attribute value by the particle agents. Fig. 1 shows the grid of dimension 5 · 6 in which thirty multicast tree patterns are ﬁlled. The pattern agent Ti is asso-

ciated with ith multicast tree pattern and ﬁlled sequentially in

row major fashion. Thirty mobile particle agents are randomly

distributed in search space where each particle agent is at-

tached to one pattern agent. Due to the ﬁxed topology of the particle agents in the search grid, the maximum number of neighbors is 8 as shown

in Fig. 1. Hence, the particle agent can interact with the

maximum 8 neighboring particle agents only. If the ﬁtness of

the best neighbor is higher than the current pattern, then it is set as the agent''s best previous position. Then, the PSO

algorithm is used to update the pattern pheromone and attri-

bute pheromone comparing the ﬁtness of the trees and their

corresponding attributes. This process is repeated for a ﬁxed

number of iterations, and the pattern with the maximum ﬁt-

ness is returned as the solution that satisﬁes all the constraints.

The pseudo-code of the proposed hybrid ACO/PSO algorithm

is outlined below. 3.4.1. Pseudo-code for hybrid ACO/PSO algorithm Algorithm HACOPSO (s, n, m, Countmax) / \ n is the maximum number of pattern generated, s is the source node, m is the number of receivers and Countmax is the maximum number of iterations the HACOPSO runs \/ Generate randomly n discriminating candidate patterns Ti Fill the patterns into the grid of dimension kxl based on the order of their generation. Generate n particle agents randomly and distribute them uniformly over the search space so that each particle agent occupies one grid. while (itr < Countmax) / \ Use ACO algorithm to accept pheromone to the pattern and attributes \ / for i = 1 to n Update the pheromone of the pattern selected by the particle agents i, Otherwise, decrease the pheromone in the pattern. for j = 1 to m Update the pheromone of all attributes trail, by increasing pheromone in the trails followed by agent i. end for end for / \ Use the modified PSO algorithm to adjust the movement of the particle agent in this iteration \ / for i = 1 to n Update the pattern and attribute pheromone If pattern fitness of current position < their best neighbors'' pattern fitness value, Then move to the neighbor''s pattern. If the fitness value of the attribute(s) in the last position is higher than the new position, Then replace those lower-fitness-value attribute with the higher-fitness-value attribute from last position. If the newly generated pattern has more fitness than the earlier fitness, Then update the attribute with higher fitness. end for end while The multicast tree patterns are generated randomly, and these

patterns reside in a search space which is deﬁned as a k · l

d1, d2, d3, . . ., dm where m is the number of group members.

The pseudo-code for multicast tree generation is given below. 3.4.2. Pseudo-code for multicast tree pattern generation procedure PatternGeneration (Ti) 1. Begin 2. initialize VT = {s} 3. delaysofar(s) = 1, losssofar(s) = 1, costsofar(s) = 0; 4. cur_node = s 5. repeat 6. Ncur_node = / 7. for each neighbour node v of the cur_node such that v R VT 8. if(B(cur_node,v) P b and delaysofar(cur_node)+ D(cur_node) 6 D and 1-(losssofar(cur_node) \ (1-L(cur_node,v)) 6 f) 9. Ncur_node = Ncur_node [ {v} 10. end if 11. end for 12. j = SelectRandom(Ncur_node) 13. cost = cost + C(cur_node, j) 14. costsofar(j) = costsofar(cur_node) + C(cur_node,j) 15. pheromone(j) = 1/costsofar(j) 16. delaysofar(j) = delaysofar(cur_node) + D(curnode,j) 17. losssofar(j) = losssofar(cur_node) \ (1 L(curnode,j)) 18. if(j R M){ 19. cur_node = j 20. else 21. cur_node = SelectRandom(VT) 22. for all (u e M and u e VT) 23. pheromone(u) = pheromone(u)+pheromone(cur_node) 24. end for all 25. end if 26. until (VT contains all nodes of the multicast group) 27. if Ti satisfies the delay jitter that is DJ(Ti(s,M)) 6 d 28. then calculate pheromone(Ti)from the cost of the tree 29. return Ti 30. end PatternGeneration Initially, the multicast tree VT is set to the source node s, which

is also set as the current node. Accumulated delay and loss up

to source node s, delaysofar(s) and losssofar(s), are set to 0 and 1, respectively. Then, a node j is selected randomly from the

neighbor nodes of the current node that satisﬁes the QoS con-

straints. The node j is added to the multicast VT, and the delay-

sofar (j) and losssofar(j) up to node j are calculated as shown in Steps 14 and 15 of the algorithm, respectively. If the node j is

not the destination node, then the current node is set to j;

otherwise, the current node is selected randomly from VT.

The pheromones of the multicast group member that are al-

ready added to the multicast tree are updated as shown in Step

23. This process is repeated till all the group members are

added to the multicast tree. The particle moves to the new position and brings the last position''s attribute and its associated ﬁtness values along with

its movement to the new position. The new position is updated

with better quality attributes discarding the low quality attri-

bute of the new position. The outcome is a new combined

pattern with higher quality than both original ones. During

the next iteration, the newly built pattern will be executed by

the agents and deposit the pheromone as appropriate. After

much iteration, eventually, the most strong pheromone trail

will be the ﬁttest discriminating pattern. 3.4.3. Time complexity In this subsection, the time complexity of the proposed algo-

rithm is carried out. The proposed algorithm uses procedure

PatternGeneration to generate a QoS aware multicast tree pat- tern randomly. In the PatternGeneration procedure, the lines

02''04 initialize the variables in O(1). The maximum number

of neighboring nodes of a node can be n. Therefore, the worst

case time complexity of line 07 is O(n). The lines 08 and 09 are

computed in O(1). Thus, the lines 07''11 can be computed in

O (n). The lines 12''21 are computed in O(1). The lines 22''24 are computed in O(m), where m is the number of destinations.

The worst case time complexity of computation performed in

lines 6''25 is O(n). Since the lines 6''25 are executed for m num-

ber of iterations, the worst case time complexity of the proce-

dure PatternGeneration is O(mn). The proposed HACOPSO algorithm starts with generating partnum number of tree patterns and runs for a maximum Countmax number of iterations. In each iteration, the n particle

agents interact with maximum 8 numbers of neighbors, and

the pheromone of maximum m number of attributes is up-

dated. The worst case time complexity of our proposed algo-

rithm is O(partnum · Countmax · n · m · 8) i.e. O(m · n · partnum · Countmax). The time complexity of TGBACA [8] is O (Countmax · antnum · n · |E|), and the time complexity of PSOTREE [17] is O(Countmax · partnum · n 2) where Count max is the maximum number of iterations, antnum and partnum

are the number of ants and number of particles, respectively,

n is the number of nodes, |E| is the number of edges, and m is the number of receivers. Thus, it is clear that the complexity

of the proposed algorithm is comparable to the existing algo-

rithms [17,8]. 4. Simulation results We have implemented our proposed algorithm in Visual C ++. The experiments are performed on an Intel Core i3 @ 2.27

G.Hz. and 2 GB RAM based platform running Windows

7.0.The positions of the nodes are ﬁxed randomly in a rectan-

gle of size 4000 km · 2400 km. The Euclidean metric is then

network topology used in our simulation was generated ran-

domly using Waxman''s topology [22]. The edges are intro-

duced between the pairs of nodes u and v with a probability

that depends on the distance between them. The edge probabil-

ity is given by P(u, ) = b exp ( l(u, v)/aL), where 0 < a, b <=1 l(u, v) is the Euler distance from node u to v and L is the maximum distance between any two points in the network.

The value of a controls the number of short links in the ran-

domly generated network topology. The smaller the value of

a, the higher is the number of shorter links. Similarly, b con-

trols the number of links in the randomly generated network

topology. The lower the value of b, the larger is the number

of links. The value of a and b is set to 0.8 and 0.7, respectively,

in our simulation setup. The delay, loss rate, and band width

of the links are set randomly from 1 to 30, 0.0001 to 0.01,

and 2 to 10 Mbps, respectively. Similarly, the cost parameter

is set to be 1''100. The maximum number of iterations Countmax

is considered to be 30. The source node is selected randomly and destination nodes are picked up uniformly from the set of nodes chosen in the net-

work topology. The delay bound D, the delay jitter bound, and

the loss bound are set 120 ms, 60 ms, and 0.05, respectively. The

bandwidth requested by a multicast application is generated

randomly. We also implemented PSOTREE [17] and TGBACA

[8] algorithms in the same environment to study and compare

the performance of our proposed algorithm with the existing

algorithms. We generated 30 multicast trees randomly to study

the performances of PSOTREE and TGBACA, and next 30

multicast trees are generated for our proposed algorithm. These

30 multicast tree patterns are arranged in a rectangular grid of

size 5 · 6 in the order of their generation. The simulation is run for 100 times for each case, and the average of the multicast

tree cost is taken as the output.

PSOTREE[17]

TGBACA[8]

multicast tree cost versus the network size with 10% and 25%

of the nodes as the group size, respectively. The multicast trees

generated by PSOTREE, TGBACA, and our proposed algo-

rithm satisfy the delay, delay jitter, loss rate, and bandwidth

constraints. However, the results clearly reveal that the cost

of the multicast tree generated by our proposed algorithm is

less than the multicast trees generated by the PSOTREE and

TGBACA [8]. The PSOTREE [17] algorithm constructs the

multicast tree by combining the multicast trees and removing

directed cycles. This algorithm in [17] removes the links that

are in any of the trees, but not in both, and have minimum ﬁt-

ness. However, the approach [17] fails to generate a better tree,

because the links deleted from the cycle may be better than the

links not in the directed cycles. The TGBACA algorithm [8]

follows a pheromone updating strategy to construct the best

multicast tree. The algorithm updates pheromones on the links

used by the global best tree and the best tree generated after

each generation. Though this strategy accelerates the conver-

gence process, the solution falls into local optimization. However, our algorithm combines two multicast tree pat- terns by bringing the better attributes of one pattern to another

pattern. It generates a new tree pattern after each iteration,

which is better than both the patterns. Therefore, the proposed

algorithm converges to a multicast tree after a few iterations. Considering the above aspects, our algorithm (HACOPSO)

is found to perform better in comparison with the previous

works PSOTREE [17] and TGBACA [8]. Figs. 5 and 6 show the multicast tree delay and delay jitter for a network of 100 nodes with 20% nodes as destinations,

respectively. It is observed that the proposed algorithm along

with PSOTREE [17] and TGBACA [8] satisﬁes the delay and

the delay jitter constraints. The multicast tree generated by

our algorithm experiences a delay and delay jitter comparable

with PSOTREE [17] and TGBACA [8]. However, the multicast

tree generated by our algorithm performs signiﬁcantly better in

terms of multicast tree cost. The Comparison of execution time in milliseconds is shown in Figs. 7''9. Figs. 8 and 9 show the comparison of execution

time for a network of nodes with 10% nodes as destinations

and for 25% nodes as destinations, respectively. It can be ob-

served that the execution time of our proposed algorithm is

less than that of the existing algorithms. This is because in

our algorithm when two particle agents interact, the path of

one tree pattern is replaced by the better path of another tree

pattern. In PSOTREE, the two trees are merged and the loops

are deleted for which it takes more time. In TGBACA, the

trees are constructed, and then, the ﬁnal tree is constructed

after tree pruning. Thus, the execution time is less than the

PSOTREE and more than our proposed algorithm as shown

in the Figs. 7''9. 5. Conclusions This paper presented a swarming agent based intelligent hy-

brid algorithm (HACOPSO) algorithm using the concept of

ACO and PSO. The performance of the proposed algorithm

was evaluated through extensive simulation. The results of

simulation are compared with two existing algorithms PSO-

TREE [17] and TGBACA [8]. Our algorithm is found to con-

struct the multicast tree patterns more sensibly such that the

tree patterns not only satisfy the QoS constraints, but also tries

to minimize the tree cost. The proposed algorithm also uses the

collective and coordination process for the mobile agents at-

tached to each pattern. The ﬁnal multicast trees generated by

our algorithm are found better compared to the multicast trees

generated by PSOTREE [17] and TGBACA [8]. The time com-

plexity of our algorithm is also found to be comparable to the

existing ones. References [1] Hakimi SL. Steiner problem in graphs and its implementation. Networks 1971;1:113''33. [2] Di Caro G, Dorigo M. AntNet: a mobile agents for adaptive routing. In: Proceedings of the 31st Hawaii international confer-

ence on systems; 1998. p. 74''83. [3] Di Caro G, Dorigo M. AntNet: distributed stigmergetic control for communications networks. J Artiﬁc Intell Res 1998;9:317''65. [4] Dorigo M, Di Caro G. The ant colony optimization meta- heuristic, new ideas in optimization. McGraw-Hill; 1999. [5] Sim KM, Sun WH. Ant colony optimization for routing and load balancing: survey and new directions. IEEE Trans Syst, Man,

Cybernet 2003;33:560''72. [6] Cheng H, Cao J, Wang X. A heuristic multicast algorithm to support QoS group communications in heterogeneous network.

IEEE Trans Vehicul Technol 2006;55(3):831''8.

TGBACA[8]

2011;38:11787''95. [9] Gong B, Li L, Wang X. Multicast routing based on ant algorithm with multiple constraints; 2007. [10] Zheng YX, Tian J, Dou WH. Vector constraint multicast routing based on GA. Chin J Comput 2003;26:746''52. [11] Haghighat A, Faez K, Dehghan M, Mowlaei A, Ghahremani Y. GA based heuristic algorithms for bandwidth-delay-con-

strained least-cost multicast routing. Comput Commun 2004;27(1):111''27. [12] Zhou J, Cao Q, Li C, Huang R. A genetic algorithm based on extended sequence and topology encoding for the multicast

protocol in two-tiered WSN. Exp Syst Appl 2010;37(2):1684''95. [13] Kennedy J, Eberhart RC. Particle swarm optimization. In: IEEE International Conference on Neural Network, Perth, Australia;

1995. p. 1942''8. [14] Liu J, Sun J, Xu W. QoS multicast routing based on particle swarm optimization. Lect Notes Comput Sci 2006;4224:936''43. [15] Sun J, Liu J, Xu W. QPSO-based QoS multicast routing algorithm. Lect Notes Comput Sci 2006;4247:261''8. [16] Li C, Cao C, Li Y, Yu Y. Hybrid of genetic algorithm and particle swarm optimization for multicast QoS routing. In: IEEE interna-

tional conference controls automation; 2007. p. 2355''9. [17] Wang H, Meng X, Li S, Xu H. A tree-based particle swarm optimization for multicast routing. Comput Netw 2010;54:

2775''86. [18] Ghaboosi N, Haghighat A. Tabu search based algorithms for bandwidth delay-constrained least-cost multicast routing. Tele-

commun Syst 2007;34(3):147''66. [19] Wang H, Meng X, Zhang M, Li Y. Tabu search algorithm for RP selection in PIM-SM multicast routing. Elsevier Comput Com-

mun 2009;33:35''42. [20] Brueckner SA, Parunak HVD. Swarming agents for distributed pattern detection and classiﬁcation. Lect Notes Artiﬁc Intell

2005;3374:232''45. [21] Meng Y. A swarm intelligence based algorithm for proteomic pattern detection of ovarian cancer. In: IEEE symposium on

computational intelligence in bioinformatics and computational

biology; 2006. p. 1''7. [22] Waxman BM. Routing of multipoint connections. IEEE J Select Areas Commun 1988;6(9):1617''22. Manoj Kumar Patel has received his M.Sc in

Mathematics and MCA from Sambalpur

University and IGNOU, India. He is currently

pursuing Ph.D under Sambalpur University,

India. He is also working as a Technical Asst.

Gr-I(Computer) in the Department of Com-

puter Science & Engineering at Veer Surendra

Sai University of Technology, India. His

research area includes QoS Routing, Reliable

Multicast and Soft Computing Techniques.

He has published about 07 research papers in various International Journals and Conferences. Manas Ranjan Kabat has received his M.E.

degree in Information Technology and Com-

puter Engineering from Bengal Engineering

College, India, and the Ph.D degree in Com-

puter Science and Engineering from Sambal-

pur University, India. He is currently working

as Reader and Head in the Department of

Computer Science and Engineering at Veer

Surendra Sai University of Technology, Odisha, India. His research involves Multicast

Routing, Reliable Multicast, High Speed Computer Networks and e-Governance. He has published about 12

research papers in various International Journals and Conferences. Chita Ranjan Tripathy is a Professor, Department of Computer Science and Engi-

neering, Veer Surendra Sai University of

Technology, Odisha, India. He received his

Master Degree and Ph.D in Computer Science

and Engineering from Indian Institute of

Technology, Kharagpur, India. He has pub-

lished more than 80 research papers in dif-

ferent International journals and conferences.

His research area includes Computer Net-

works, Parallel Processing and Reliability. He has received his ''''Sir Thomas Ward Memorial'''' gold medal for

researches in Parallel Processing. He is a Fellow of Institution of

Engineers (India) and life member of Indian Society for Technical

Education (ISTE), Instrument Society of India and Orissa Information

Technology Society (OITS). 120 M.K. Patel et al.

Grassi Mobil™ - Formulati per fornire elevate prestazioni anche in condizioni operative estreme

© Eiom - All rights Reserved P.IVA 00850640186