USING LEARNING AUTOMATA AND GENETIC ALGORITHMS TO IMPROVE THE QUALITY OF SERVICES IN MULTICAST ROUTING PROBLEM

USING LEARNING AUTOMATA AND GENETIC ALGORITHMS TO IMPROVE THE QUALITY OF SERVICES IN MULTICAST ROUTING PROBLEM

• 1.
  International Journal ofComputer Science, Engineering and Applications (IJCSEA) Vol.2, No.5, October 2012 DOI : 10.5121/ijcsea.2012.2507 75 USING LEARNING AUTOMATA AND GENETIC ALGORITHMS TO IMPROVE THE QUALITY OF SERVICES IN MULTICAST ROUTING PROBLEM Mohammad Reza Karami Nejad1 1 Department of Computer Engineering, Dezful Branch , Islamic Azad university, Dezful, Iran Mr.karami.nejad@gmail.com ABSTRACT A hybrid learning automata–genetic algorithm (HLGA) is proposed to solve QoS routing optimization problem of next generation networks. The algorithm complements the advantages of the learning Automato Algorithm(LA) and Genetic Algorithm(GA). It firstly uses the good global search capability of LA to generate initial population needed by GA, then it uses GA to improve the Quality of Service(QoS) and acquiring the optimization tree through new algorithms for crossover and mutation operators which are an NP–Complete problem. In the proposed algorithm, the connectivity matrix of edges is used for genotype representation. Some novel heuristics are also proposed for mutation, crossover, and creation of random individuals. We evaluate the performance and efficiency of the proposed HLGA-based algorithm in comparison with other existing heuristic and GA-based algorithms by the result of simulation. Simulation results demonstrate that this paper proposed algorithm not only has the fast calculating speed and high accuracy but also can improve the efficiency in Next Generation Networks QoS routing. The proposed algorithm has overcome all of the previous algorithms in the literature.. KEYWORDS Routing, Quality of Service, Multicaset, Learning Automata, Genetic, Next Generation Networks 1. INTRODUCTION Next Generation Networks (NGN) have low-cost, high-bandwidth technology [17]. The NGN mainly bear Internet business, so the QoS routing technology is more important[19,27,30]. This paper mainly discusses the multi-constrained QoS routing problem of NGN. This problem has been proved to be NP-complete [25,26,28,2]. In recent years, some intelligent algorithms such as genetic algorithm(GA) [2,26] and learning automata [15] have been been applied to solve NP-complete problems. So this paper also adopt intelligent algorithms to solve NGN QoS routing problem. LA has wide range and fast global search capability [11,15]. However, LA can't take full advantage of the system feedback information, so LA gets local minimization too easily and converges slowly. Therefore, it is used to obtain the initial population. GA is a distributed global optimization algorithm. It has ability of positive feedback[2,26] which provides a fast convergency and an optimized solution. GA has stronger robustness and better parallel computing features in the heuristic search process, It is widely used in QoS routing field. Considering NGN QoS routing features, this paper proposes a Hybrid Learning atomata-Genetic Algorithm (HLGA) by combining LA with GA. HLGA can not only make full advantages of the two algorithms but also overcome the defects of them.
• 2.
  International Journal ofComputer Science, Engineering and Applications (IJCSEA) Vol.2, No.5, October 2012 76 2. NEXT GENERATION NETWORKS MULTI-CONSTRAINTED QOS ROUTING MODEL In NGN, routers are fixed nodes with no constraints on power supply, so routers contain advanved routing functionalities to support NGN network[16,21,24]. The characters of NGN routers guarantee the feasibility of optimization NGN QoS routing based on HLGA. This paper assumes that the nearest router can receive the request firstly when a client requests a QoS routing, and routing message will be send back after the appropriate routing is calculated[17] .The definitions relevant to NGN QoS routing are presented as follow [17,7,12,18,29]: Defination 1: G=(V,E) is represented NGN model, where V is node set, E is link set, r(r∈ V)is the node transmitting range, d is the distance between two adjacent nodes and if d≤r then there is a two-way link e( e∈E) between them. Defination 2: Path set and edge set. For given G=(V,E), let P as the path set from source node S (S∈V)to destination node t(t∈V), let E(p) and N(p) as the edge set and the node set of a path p(p∈P) respectively. Then the QoS parameters are defined as follow: Delay(p) = Delay(e) ∈ ( ) + Delay(n) ∈ ( ) )1( BandWidth(p) = min{BandWidth(e), e ∈ E(p)} )2( Packet Lossration, Loss(p) = 1 − (1 − Loss(n)) ∈ ( ) )3( cost(p) = |E(p)|isthehopsofpath )4( According to the characteristics of NGN, the target of executing QoS routing algorithms is to find the minimum cost path P and it must meet the following conditions: Delay(p,) ≤ D BandWidth(p,) ≥ B Loss(p,) ≤ L Cost(p,)is minimum )5( Path P must be satisfied that the bandwidth is greater than the minimum, the delay is less than the maximum, the packet loss ratio is less than maximum and the cost is minimum. 2.1. Learning Automata Algorithm A learning automaton [11, 15] is an adaptive decision-making unit that improves its performance by learning how to choose the optimal action from a finite set of allowed actions through repeated interactions with a random environment. The action is chosen at random based on a probability distribution kept over the action-set and at each instant the given action is served as the input to the random environment. The environment responds the taken action in turn with a reinforcement signal. The action probability vector is updated based on the reinforcement feedback from the environment. The objective of a learning automaton is to find the optimal action from the action- set so that the average penalty received from the environment is minimized. Learning automata have been found to be useful in systems where incomplete information about the environment exists. Learning automata are also proved to perform well in complex, dynamic and random environments with a large amount of uncertainties. A group of learning automata can
• 3.
  International Journal ofComputer Science, Engineering and Applications (IJCSEA) Vol.2, No.5, October 2012 77 cooperate to cope with many hardto-solve problems. To name just a few, learning automata have a wide variety of applications in combinatorial optimization problems, computer networks, queuing theory, signal processing, information retrieval, adaptive control, and pattern recognition [11,8,4,1,9,14,3,10]. The environment can be described by a triple E ≡ {α,β, c}, where α ≡ {α1,α2, . . . , αr } represents the finite set of the inputs, β = {β1,β2, . . . , βm} denotes the set of the values that can be taken by the reinforcement signal, and c = {c1, c2, . . . , cr } denotes the set of the penalty probabilities, where the element ci is associated with the given action αi . If the penalty probabilities are constant, the random environment is said to be a stationary random environment, and if they vary with time, the environment is called a nonstationary environment. The environments depending on the nature of the reinforcement signal β can be classified into P -model, Q-model, and Smodel. The environments in which the reinforcement signal can only take two binary values 0 and 1 are referred to as P -model environments. Another class of the environment allows a finite number of the values in the interval [0, 1] can be taken by the reinforcement signal. Such an environment is referred to as Q-model environment. In S-model environments, the reinforcement signal lies in the interval [0, 1]. Learning automata can be classified into two main families [11]: fixed structure learning automata and variable structure learning automata. Variable structure learning automata are represented by a triple <α,β,T>, where β is the set of inputs, α is the set of actions, and T is learning algorithm. The learning algorithm is a recurrence relation which is used to modify the action probability vector. Let αi(k)∈α and p(k) denote the action selected by learning automaton and the probability vector defined over the action set at instant k, respectively. Let a and b denote the reward and penalty parameters and determine the amount of increases and decreases of the action probabilities, respectively. Let r be the number of actions that can be taken by learning automaton. At each instant k, the action probability vector p(k) is updated by the linear learning algorithm given in (6), if the selected action αi(k) is rewarded by the random environment, and it is updated as given in (7) if the taken action is penalized. (6) )](1[)()1( npanpnp iii −+=+ ijjnpanp jj ≠∀−=+ )()1()1( (7) )()1()1( npbnp ii −=+ ijjnpb r b np jj ≠∀−+ − =+ )()1( 1 )1( If a=b, the recurrence equations (6) and (7) are called linear reward-penalty (LR−P ) algorithm, if a >> b the given equations are called linear reward-∈ penalty (LR−∈P ), and finally if b = 0 they are called linear reward-Inaction (LR−I ). In the latter case, the action probability vectors remain unchanged when the taken action is penalized by the environment[9]. 2.2. Genetic Algorithm The action range of the genetic algorithm is very vast [13,20,22,23]. Genetic algorithm, a global search methods that mimic natural biological evolution rules. Genetic algorithm on a series of solutions of the problem, hoping to get better answers, the survival law will apply the best. Better approximations of the final response can be acquired in each generation through a selection process proper to responses value and the production of the selected responses through imitating actions based on natural genetic .this process causes more compatible new generations to the problem. The steps of this algorithm are as follows:
• 4.
  International Journal ofComputer Science, Engineering and Applications (IJCSEA) Vol.2, No.5, October 2012 78 1) Encoding rules: The random search algorithm LA gets the tree from source node to destination nodes according to the network topology. In GA, an individual corresponds to a network tree, so the coding of individual chromosome is represented with the node sequence of tree, and chromosome length can be varied (each individual is represented by a tree prufer). 2) Fitness function: Fitness function is the evaluation criterion of individual superiority. The establishment of the fitness function must meet the following conditions: (a) The cost of selected routing is minimum. (b )There is only one path from source node to destination node. (c )The selected routing must be existent link. (d)The path must meet the transmission constraints. The fitness function is composed of the objective function and the penalty function. It is defined as follow: Objectivefunction ∶ f = 1 Cost(p) )8( Delaypenaltyfunction ∶ f = ∅ {Delay(p) − D} ∅ (z) = 1 , z ≤ 0 r , z > 0 (0 < r < 1) )9( Packetlossratiopenaltyfunction ∶ f = ∅ {Loss(p) − L} ∅ (z) = 1 , z ≤ 0 r , z > 0 (0 < r < 1) )10( BandWidthpenaltyfunction ∶ f = b{B − BandWidth(p)} ∅ (z) = 1 , z ≤ 0 r , z > 0 (0 < r < 1) )11( Fitnessfunction ∶ F(p) = f (Af + Bf + Cf ) )12( Where A, B and C are the normalization coefficients and positive real numbers, they respectively means the proportion of delay, packet loss rate and bandwidth in the objective function. The size of rd, rl and rb determine the penalty degree. When the routing meet the QoS constraints, the penalty function value is 1 else its value is a real number from 0 to 1. The objective function fc reflect the influence of the path cost on the individual. 3) Initialization population: The initial population can be get by encoding the multiple paths searched randomly through the total network by GA. N is optimal population size. 4) Selection function: Using the optimum individual maintaining combined with roulette wheel selection method. 5) Crossover operation: To avoid the illegal path, two point crossover method is adopted. This method randomly selectes two trees p1, p2 from the tree set firstly, then finds out all the same nodes between p1 and p2, and randomly selectes two nodes a,b from the same nodes (the order of a,b should be the same), then exchanges the part between a and b and delete the duplicate parts of the path. 6) Mutation operation: This mutation operation firstly randomly selectes a tree named d and randomly find a node k on tree d. All the nodes before k should be added to the offspring, and the node k is to be as the start point and the original destination node as the end point, a tree which can't contain nodes before k randomly searched, and it is added to the offspring. This method can avoid the illegal tree and can ensure population diversity. 7) Terminal conditions: the final condition means after a proper repetition time, the algoarithm ends up.
• 5.
  International Journal ofComputer Science, Engineering and Applications (IJCSEA) Vol.2, No.5, October 2012 79 3. DESIGN AND IMPLEMENTATION OF IMPROVED HYBRID LEARNING AUTOMATA-GENETIC ALGORITHM First, the developed LA algorithm is used to Create optimized solutions because, LA with quick and regular global convergence is that LA is used to generate the initial population.Then the GA to get the optimal solutions using crossover and mutation operators are used several times. Because, GA has a positive feedback and parallelism, and it creates a new population is optimal. In this section, a approach based on learning automata-Genetics (HLGA) for QoS routing problem solving is proposed. The first step in using genetic algorithm is coding chromosomes. This means that the chromosome should be indicated information about the solutions offered by it. In each chromosome there are some genes which each of them represents a charateristic of that chromosome. In the proposed approach, each gene is corresponding a node in each graph, so each chromosome is presented with a vector in a graph which represents a routing tree in the graph. Each gene in Learning Automata with a variable structure is equipped with two actions. When the number of actions is a lot of automata, the probability of choosing a special action is low and therefore the algorithm convergence time increases. In order to improve the convergence rate of a Learning Automata, It could be a number of Learning Automata, Connected through a hierarchical architecture, See, This means that a network of learning automata is called distributed learning automata. Learning Automata advantage this approach is that it can actions on a smaller number to work. Since the Learning Automata has two action and the corresponding probabilities sum of these two action, is equal to one, Only one chance is enough storage for Learning Automata. In the proposed algorithm, For each gene is kept only the probability of choice .Therefore each chromosome is shown with a vector of probabilities The value of each bit of this vector, The presence probability its corresponding bit in the routing tree. Algorithm at the beginning, the value of this probability is equal to 0.5. In other words, probability of being a zero or one gene is considered equal. Therefore first generation of completely random individuals are selected. The algorithm consists of the chromosomes for genetic algorithm using learning automata is presented. Process of learning automata, this is when the first repeat (itr = 1) are All those first-generation vector, is the same. so that in each chromosome the selection probable of non-terminal node equals 0.5 and the probable for selecting terminals equals 1. This will cause to select all the first generation individuals very randomly . also, The other reason is that the connection matrix edge, to form a routing tree, the algorithm uses learning automata, That does not have any effect on Quality of Service parameters and the learning algorithm is used. So for an individual of the first generation of according to algorithm (1) so that initially all automata are inactive, Then a learning automata are randomly activated And a number of actions connected to the automata is calculated, If a number of actions is not empty, a p probability vector will be formed according to equation (13) in which i is the action automata and r is the number of actions connected to the automata and p represents the probablity of j th action in i th automata. Then action will be selected according to p probability vector and And its selective edge is added to the current tree. To prevent the cycle, Selected edges, are removed every passive automata And this algorithm will be repeated as much as the N specified population, so As N is the initial individual.
• 6.
  International Journal ofComputer Science, Engineering and Applications (IJCSEA) Vol.2, No.5, October 2012 80 )13(P′ = P  ∑ P α For creating next generation individul the process is that, at the beginning , just like the the first generation ,one solution is selected with each chromosome according to following the corresponding Sequence probabilities. If the i th individual form the current generation wasn't better than the previous generation i th individual , the previous generation i th individual will be Replaced Genetic operators are used to produce better individuals. Algorithm(1):Creating chromosome by learning automata When the initial population was created according to automata, Genetic algorithms are used to find the optimal population, through genetic algorithm which This, according to the algorithm (2) is done. the NGN QoS routing problem is converted into optimization problem. This paper assume that each node executes the same routing algorithm, the characteristics of node are added to the link, so the HLGA only considers the link and loses sight of the characteristics of the node. Then the nodes and links which unsatisfied the Qos constraints are removed and a new network topology to be formed. so , GA algorithm is performed as follows: 1) HLGA randomly generate a network topology inculuding N nodes, then describe the problems as QoS routing problems and initializ it. 2) Algorithm randomly generate a group of coding and generate initial population p(g) used by LA, g=0; //g is generation. 3) The fitness value of individual in P(0) is caculated. For i=1 to Population Do Ti ← ϕ Assign an automaton to each node and initially set it to the passive state Let A denotes the set of activated automata which is initially null While |Ti| < |V −1| OR A< nDo Select one of the passive automata at random and call it Ai If |αi |≠φThen Automaton Aichooses one of its actions According to Probability vector A←A+ Ai Ti←Ti + e(i, j) Each passive automaton prunes its action‐set for cycle avoidance Else A←A+ Ai End If End While Chromosomei(itr)=Ti End For
• 7.
  International Journal ofComputer Science, Engineering and Applications (IJCSEA) Vol.2, No.5, October 2012 81 4) The GA defined in (2-2) is executed repeatedly until it meet the end conditions. The process of GA is as follow: a. According to the fitness function and selection operation defined in (2-2), the choice probability of each individual in p(g) is determined. b. The two individuals with highest fitness in p(g) are directly inherited to the next generation. c. According to crossover operation and mutation operation described in (2-2), GA execute the crossover operation and mutation operation. 5) From the p(g), 10% individual which have the better adaptbility are choosed as majorized set. 6) The individuals obtained in the above steps, vector update operation according to equation (6) and (7) to establish a new population for the next generation is used. 7) Outputting the optimal solution 4. SIMULATION EXPERIMENTS AND RESULTS ANALYSIS The simulation experiment uses NS2 to analyze QoS routing optimal performance of the HLGA in NGN. Simulation scenario is 1000* 1000 square area. The parameters of system simulation environment are showned in table 1. In the experiment, the available bandwidth of the QoS parameters is generated randomly and it is an integer from 1 to 10, the delay is an integer from 10 to 20, packet loss ratio is a decimal from 0.01 to 0.1. we set the crossover probability of GA Pc=0.45, aberrance probability Pm=0.05, and N = 50 is considered. In the learning automata algorithm , the control parameters amounts use LRP for updating, a and b are equal to 0.3 and in the Probability vector α is considered 0.05. Table(1) : simiulation environment parameters ParameterClassification 1024 byteData Packet Length 150mWireless Transmission Range 250sSimulation Time 100Nodes Number 20Data Flow Transmission Rate 1MbpsChannel Transmission Rate
• 8.
  International Journal ofComputer Science, Engineering and Applications (IJCSEA) Vol.2, No.5, October 2012 82 Algorithm 2: Algorithm performance automata - Genetics in this paper,, HGLA algorithm is compred with two GA algorithms [2,26] in the same environment to test its performance. figure (1) represents a comparison of average delay in three algorithm. The results show that HGLA delay average is less than two orther algorithms because GA and LA specifications are combined in it. During routing process in HLGA , LA was used for acquiring the primary population in genetic algorithm and Due to the speed and global convergence is that it was used then HLGA used GA to get the exact solutions for it has the characteristics of parallel, positive feedback and high solving efficiency. So the improve algorithm HLGA can quickly find the routing satisfying multiple QoS constraints and reduce end-to-end delay. Figure 2 shows the comparison of relationship between solving time and node size of three algorithms. It illustrates that the HLGA execution efficiency is significantly better than two GA algorithm with the increase of nodes size. The experiment results demonstrate that the new algorithm is more efficient and more economical than the genetic algorithm and the LA algorithm.
• 9.
  International Journal ofComputer Science, Engineering and Applications (IJCSEA) Vol.2, No.5, October 2012 83 Figure 1: Average delay comparison 5. CONCLUSIONS This paper analyzes the structure features of the NGN and combines the characteristics of LA and GA, proposes an improved algorithm HLGA to solve the NGN QoS routing problem. HLGA uses the good global search capability of LA to Creating initial population At late stage, the GA is used to get exact solution becase of its positive feedback characteristics. The simulation results indicate that HLGA algorithm not only has fast convergence but also has high accuracy, so it is more effective to solve QoS routing problem of NGN than using single LA and GA. Figure 2: Relationship between time and node size REFERENCES [1] Osteen, RE. Lin,PP.,(1974), Picture skeletons based on eccentricities of points of minimum spanning trees, SIAM J Comput,pp.23–40. [2] Na Lin,Chen X,Li X.(2010). QoS Multicast Routing Algorithm based on Immune Genetic method in NGN.IEEE.1-4. [3] Gower, JC., Ross, GJS.,(1969), Minimum spanning trees and single linkage cluster analysis, J R Stat Soc pp. 54–64. [4] Graham,RL., Hell, P.,(1985), On the history of the minimum spanning tree problem, IEEE Ann HistComput,pp.43–57. [5] Salama, H.F., Reeves, D.S.,Viniotis, Y.,(1997), Evaluation of multicast routing algorithms for real- time communication on high-spee networks, IEEE Journal on Selected Areas in Communications,pp. 332–345.
• 10.
  International Journal ofComputer Science, Engineering and Applications (IJCSEA) Vol.2, No.5, October 2012 84 [6] Hao,Yu., Huang, Zhang., Rui, Song.,(2007), Principles and techniques [M],Beijing: Publishing House of Electronics Industry. [7] Hutson, KR., Shier, DR.,(2006), Minimum spanning trees in networks with varying edge weights, Ann Oper Res ,pp.3–18. [8] Jain, A., Mamer, JW,(1988), Approximations for the random minimal spanning tree with application to network provisioning,Oper Res 36: pp.575–584. [9] Kang, ANC., T, Lee, RC., Chang, CL., Chang,SK.,(1977), Storage reduction through minimal spanning trees and spanning forests, IEEE Trans Comput, C-26:pp.425–434. [10] Lakshmivarahan, S., Thathachar, MAL.,(1976), Bounds on the convergence probabilities of learning automata. IEEE Trans Syst Man Cybern, SMC-6: pp.756–763. [11] Lakshmivarahan, S., Thathachar, MAL.,(1976),Bounds on the convergence probabilities of learning automata. IEEE Trans Syst Man Cybern, SMC-6:pp.756–763. [12] Parsa, M., Zhu, Q.J., Garcia-Luna-Aceves,(1998), An iterative algorithm for delay-constrained minimum-cost multicasting, IEEE/ACM Transactionson Networking 6 (4) pp. 461–474. [13] Valleho, A., Zaballos, A., Vernet, D., Cutiller, D., Dalmau, J.,(2008), Implementation of Traffic Engineering in NGNs using Hybrid Genetic Algorithms, IEEE,pp.262-267. [14] Marchand-Maillet, S., Sharaiha,YM.A.,(1996), minimum spanning tree approach to line image analysis, In: Proceedings of 13th international conference on pattern recognition (ICPR’96), pp 225. [15] Narendra,KS.,Thathachar, KS.,(1989), Learning automata: an introduction,Printice-Hall, New York. [16] Schollmeier,Gero., Winker, Christian.,(2004), Providing sustainable QoS in nextgeneration networks, IEEE Communications Magazine , pp 102–107. [17] WahabKaram, F., Jensen, T.,(2010), A Survey on QoS in Next Generation Networks, Information Sciences and Service Sciences,pp 91-102. [18] Kompella, V.P., Pasquale, J.C.,Polyzos G.C.,(1993), Multicast routing for multimedia communication, IEEE/ACM Transactions on Networking ,pp 286–292. [19] Wang, Z.,Crowcroft,J.,(1996), Quality of service for supporting multimedia applications,IEEE Journal On Selected Areas in Communications,pp.1228—1234,. [20] Wei-yan, L.,Shun-yi,(2005), AQoS Multicast Routing Algorithms Based on Genetic Algorithm in Next-Generation Networks,Journal of Electronics & Information Technology. [21] Yunjie,Liu.,Yunyong, Zhang.,(2005), The next generation network service and quality[M], Beijing: Publishing House of Electronics Industry. [22] Wang, Z., Shi, B., Zhao, E.,(2001), Bandwidth-delay-constrainted least-cost multicast routing based on heuristic genetic algorithm,Computer Communications, pp.685–692. [23] Qian, L.,(2005), A New Qos Routing Architecture In NGI .Phd Thesis,Université Du Québec À Montréal,pp1-64. [24] Wang,Y.,Li, L.,Xu,D.,(2008), PervasiveQoS routing in next generation networks,Elsevier,pp.3485– 3491. [25] Younes,Hamed,A., (2011), An Ant Algorithm for Solving QoS Multicast Routing Problem, International Journal of Computer Science and Security (IJCSS),pp. 157-167. [26] Wang, X., Liu, P., Huang, M.,(2007), Genetic Algorithm and Pareto Optimum Based QoS Multicast Routing Scheme in NGI,Springer-Verlag Berlin Heidelberg,pp.115-122. [27] Ravikumar, C.P.,Bajpai, R.,(1998), Source-based delay-bounded multicasting in multimedia networks, Computer Communications 21, pp. 126–132. [28] Zhang,Kun., Wang,Heng., Liu,Feng-Yu.,(2004), Distributed multicast routing for delay and delay variation bounded Steiner tree using simulated annealing, Elsevier, pp.1356-1370. AUTHORS Mohammad Reza Karami Nejad was born in Dezful, Khuzestan, Iran on 1985. He received her BSc degree in Computer Communication Engineering from Dezful Branch Islamic Azad university, Dezful, in 2008, and the MSc degree in Computer Science from Dezful University of Computer Engineering, Dezful, Khuzestan, Iran, in 2012. Her research involves multicast routing, network security and high-speed computer networks.