Solving multicast routing problem Using Particle Swarm Optimization


Prasanta Kumar Raut 1P3#yIS1, Siva Prasad Behera 1


1 Department of Mathematics, C.V. Raman Global University, Bhubaneswar-752054, Odisha, India





In a given network there exist many paths from source to destination, among all selected paths finding the optimal shortest path is a challenging task. In this research paper, we proposed a new concept of particle swarm optimization technique, called swarm intelligence, to solve the multicast routing problem to find out the optimal route associated with a network, here we also used triangular fuzzy number tools to encode particles in PSO (particle swarm optimization), first it breaks the network into small spaces and from the small space it computes the optimal path.


Received 05 April 2022

Accepted 08 May 2022

Published 26 May 2022

Corresponding Author

Siva Prasad Behera,

DOI 10.29121/IJOEST.v6.i3.2022.330   

Funding: This research received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.

Copyright: © 2022 The Author(s). This work is licensed under a Creative Commons Attribution 4.0 International License.

With the license CC-BY, authors retain the copyright, allowing anyone to download, reuse, re-print, modify, distribute, and/or copy their contribution. The work must be properly attributed to its author.



Keywords: Multicast Routing, Particle Swarm Optimization, and Swarm Intelligence






There exist many routes from a source to a destination in a given graph but finding the optimum route at the lowest cost is extremely difficult. The term “swarm” comes from the field of artificial intelligence. In swarm intelligence, there are a number of shortest path techniques used to overcome this problem. Many research papers are available to tackle routing problems using PSO Rehab and Abdel-Kader (2011), all of which employ the same technique but use various particles encoding in the discrete form Baburaj and Vasudevan (2008). To tackle this problem, we designed a simple encoding approach it breaks the space into smaller space of reduced size after that combine all the results for evaluating the optimal path, it works on the the greedy approach principle.



Swarms are a group of particles in PSO that are used to discover the shortest path from source to destination of a network. Every particle has an initial location (its current position in time), a personal best position (its best position among all particles in search space), and associated   velocity of every particle. During this method, every particle tries to move towards the particle closest to the optimal solution, but the best solution is obtained from Xu et al. (2007)






In the swarm, i=1,2,3,4……n and Pi_pest is the particle best solution, where g(ibest)is the global best solution, v is the particles velocity and p,g are control parameters that regulate the particle’s efficiency



Assume that G is a multicast tree

             The initial root of the multicast tree is denoted by symbol “S”

              D is the final root multicast tree

Create an initial swarm at random

·        Continuing for each particle i until you have reached the maximum number of iterations

Calculate the best fitness value possible.

·        Best position should be updated.

1)     Velocity update

2)     Refresh the global position

Until the threshold termination is reached




Figure 1                  


Figure 1 Multicast Network


To solve multicast routing problem by using PSO, in this network vertex   is a source vertex and  called destination vertex .In starting iteration of PSO we have initially determined the random route from source to destination because every particle associated in multicast network has capable to give the solution of problem .In initial stage network break the paths sequentially into small space.

Table 1

Table 1


Route number

Route list












Consider the starting velocity of each particle is zero in equation (2), for which the “P best “defines initial routes as the current best paths of particles as follows


                                                       P best =


From the above three particle we have to find the global best of the particles which have minimum cost among all particles .minimum cost of the particle we can find by using Euclidean distance between two configurations s = (, .....) and t = (,.....) in euclidean space. i.e., Mathematically define by




we get Gbest is 1−6−7−8, by using Euclidean distance formula

Now velocity of particle (vpart) is evaluated by taking the difference between Gbest & Pbest

  Now consider particle velocity associated in path 3 in Table 1


V part [3] [] = G best []- P best []


V part [3] [] = (1 6   7   8) – (1   6   5    8)


                                                                = 7


Similarly, the particle’s velocity can be determined for path -1, path-2 and path-3 in Table 1 obtained as follows




                                                                 V part [] [] =


The position of each particle is updated in accordance with the new velocity. Final result, the procedure for modified the position s of all particles associated network in Figure 1 is defined as


C part [] [] =   V part [] [] + C part [] []

For last (3rd) particle we find the new position


C part [] [] = (7) + (1 6 5 8)


C part [] [] = (1 5 6 7   8)


The three p-best represented in Figure 1 by dark line. Using a dark dashed line ,one G is preferable .Following the update of the second particle ,we now have a set of nodes from which we can try to discover a route from source to destination .one advantage of this strategy is that we don’t have to search all nodes in the network ;instead, we only have to explore paths between these nodes .As a result ,all networks are divided into little networks, and we search inside this small group of networks ,with the node positions of these small closed networks changing by  dynamically .when the associated particle’s velocity and position are changes simultaneously ,every   particles eventually produce a better solution.


C part [3] [] = 1-5-7-8


Figure 2


Figure 2




Figure 3


Figure 3 The network cost path is lowered from 6.62 to 5.17 after updating particle 1-2-7-8 to 1-2-3-8


 Figure 4


Figure 4 Network after updating


Position of particle is changed from (1,2,3,8) to (1,2,7,8) by doing cost path reduced from 6.62 to 5.17 which is shown in Figure 2. similarly, Figure 3 show path of third particle position is update from (1,6,5,7,8) to (1,5,7,8) and cost of path is modified from 6.16 to 5.15


Simulation Result

There are 35 nodes in this example, and each link connecting the nodes has a cost. To test the influence of particles, two simulation procedures were used. The first simulation uses 10 particles,30 nodes, and 40 iterations, whereas the second uses 15 particles, 35 nodes, and 40 iterations.

Figure 5 shows that the cost of the path is 45 after 10 iterations, but after 50 iterations, the minimal cost path is 12, which is the network’s ideal path.  At 10th iteration the cost route in the network is 35, while in 8 in the 50 iterations, as seen in the second Figure 6. As a result of which we obtain a decent path in the second iteration because they have spread so widely in the network


Figure 5


Figure 5  Simulation Result of 10 Particles


Figure 6


Figure 6 Simulations Result Of 15 Particles



Many approaches to solve the routing problem using PSO have been described, but this one stands out since it uses simple encoding particles and is straight forward to implement. when by increasing the number of particles or iterations, the result is more accurate. This method can be implemented to tackle not only routing but also discrete problems.


Conflicts Of Interest

The authors declare that they have no conflicts of interest.



This research is supported and funded by C.V Raman Global University, Bhubaneswar, Odisha, India.



Ahn, C.W. Ramakrishna, R.S. (2002). A Genetic Algorithm for Shortesh Path Routing Problem And Sizing of Populations, Ieee Transactions on Evolutionary Computation. 6(6).

Baburaj, E. and Vasudevan, V. (2008). An Intelligent Mesh Based Multicast Routing Algorithm for MANETs using particle Swarm Optimization, IJCSNS International Journal of Computer 214 Science and Network Security, 8(5).

Behera, S.P.  Pati, J.K. Raut, P.K. and Mahanta, K.L. (2022). Calculation of Linear Fractional Fuzzy Transportation Problem Using Simplex Method. International Journal of Engineering Science Technologies, 6(2), 38-47.

Behera, S.P. Mishra, D. Bhattacharjee, S. Raut, P.K. (1969). A Modified Approach in Shortest Path Algorithm, International Journal of Advance Research, Ideas and Innovations in Technology, 7(4), 1489-1493.  

Raut, P.K. Behera, S.K. Pati, J.K. (2021). Calculation of Shortest Path in a Closed Network in Fuzzy Environment, International Journal of Mathematics Trends and Technology, 67(11), 31-37.

Raut, P.K. Behera, S.P. (2021). Application of Fuzzy Optimal Path Algorithm for Bus Route Expansion in Bhubaneswar city, Odisha, International Journal of Research Culture Society Issn, 5(11).  

Rehab, F. and Abdel-Kader, (2011). An Improved Discrete PSO with GA Operators for Efficient Qos- Multicast Routing, International Journal of Hybrid Information Technology, 4(2).

Sombuntham, P. and Kachitvichayanukul, V. (2010). A Particl Swarm Optimization Algorithms for Multi-depot Vehicle Routing problem with Pickup and Delivery Requests.

Xu, Y. Hu, J. Hirasawa, K. Pang, X. (2007). A New Cooperative Approach to Discrete Particle Swarm Optimization, SICE Annual Conference.

Xue, G. (2003). Minimum Cost Multicast and Unicast Routing in Communication Network, Ieee Transactions on Communications, 51(5).






Creative Commons Licence This work is licensed under a: Creative Commons Attribution 4.0 International License

© Granthaalayah 2014-2022. All Rights Reserved.