Optimization Of Wireless Mesh Network Computer Science Essay

Published:

A hybrid genetic algorithm is proposed to solve wireless mesh network QoS routing optimization problem.The algorithm using the advantages of the genetic algorithm(GA) to produce the original results,and be transformed into the initial pheromones value needed by ant colony optimization(ACO).Moreover, quality and robustness of solutions are improved by the nature of feedback and parallel paradigm of ACO. For taking advantage of the two algorithm,The best combination time with ACO is determined dynamically while running GA. Experimental result shows that this paper proposed algorithm is high-efficiency in wireless mesh network QoS routing and the performance is much better than GA and ACO.

Wireless mesh network(WMN) is a new broadband and multi-hop wireless network, it has the capability of self-forming,self-organization,self-configuration routing and forwarding function. According to the network nodes function, mesh is divided into mesh routers and mesh clients.Mesh routers form a self-configuration and self-healing network.It has the routing and gateway/network bridge functions. The position of mesh roter is weak mobility and smaller topology changes.Mesh clients constitute peer-to-peer network.In order to enhance the ability of network covering, clients can be accessed to Internet, WiFi, WiMAX, cellular and sensor network in multi-hop minner[1]. The WMN mainly bearing Internet business, so the QoS routing technology is more important. This paper mainly discusses the multi-constrained QoS routing problem of WMN.The multi-constrained QoS routing problem is proveed to be NP-complete problem[2],and usually adopts the heuristic algorithm to solve.In recent years,many domestic and foreign scholars using intelligent algorithm such as neural network, genetic algorithm(GA) and ant colony optimization(ACO) to solve NP complete problems and achieve certain results.

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

GA has wide range and fast global search capability[3].It is widely used in QoS routing field[4-5].However,GA can't take full advantage of the system feedback information. It make algorithm reduces convergence speed of the optimal solution when solution arrives on a certain extent,so it is easy to fall into local optimum.ACO is a distributed global optimization algorithm.It has positive feedback mechanism.It can constantly update the pheromone to make the optimal solution efficient convergence.ACO has stronger robustness and better parallel computing features in the heuristic search process,and it has been applied in the QoS routing optimization[6].However, the algorithm lack the initial pheromones at the beginning, so the time is longer for initial pheromones..

Considering WMN QoS routing features, this paper brrows the method of Reference [7],and combines with the performance of ACO and GA to propose a Hybrid Genetic Algorithm (HGA) .HGA not only can exert respective advantages but also overcome the defects.

Wireless Mesh network multi-constrainted QoS routing model

WMN composed of WMN backbone network constituted by Mesh router and mesh client constituted by some mobile nodes. Backbone network is accessed to Internet or other differentnets by gateway or router. The client uses multi-hop to communicate with mesh router. in WMN,the routing can be established by routing algorithm between routers.As the mesh routers generally have very little mobility,and there is no energy problems,so while designing WMN routing protocols, the impact of mobility on the protocol can be weaken.WMN use routers collect the whole network information,it provide guarantee for HGA optimization Mesh QoS routing.This paper assumes that when a client requests a QoS routing, the request is sent to the nearest router firstly,and the router calculates appropriate routing, then routing message will be send back.

Defination 1 G=(V,E) is represented WMN model,where V node set,E is link set,r(r∈V)is the node transmitting range,d is the distance between two adjacent nodes.If d≤r, there is two-way link e(e∈E) between them.

Defination 2 Given G=(V,E), The path set from source node s (s∈V)to destination node t(t∈V) is P.The edge set of a path p(p∈P) is E(p) and the node set is N(p),then the QoS parameters are defined as follow:

Delay(p)= +

BandWidth(p)=min{BandWidth(e),e∈E(p)}

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

packet loss ratio, Loss(p)=1-(1-Loss(n))

Cost(p)=|E(P)| is the hops of path

According to the characteristics of WMN, the target of executing QoS routing algorithms is to find the minimum cost path P and The P must meet the following conditions:

Delay(p')≤D

BandWidth(p')≥B

Loss(p')≤L

Cost(p')is minimum

P must be satisfied that the bandwidth is greater the minimum, the delay less than the maximum,packet loss ratio less than maximum and the cost is the least.

Design and Implementation of Improved Hybrid Genetic Algorithm

The Improved algorithm firstly uses the rapidity,randomness and global convergence of GA to generate more excellent solution,then on the better path the pheromones are lefted to form the initial pheromones.Then,the algorithm uses the parallelism, positive feedback of ACO to get the optimal solution by iteration local and global pheromone many times.If several successive iterations evolutionary rates of the offspring groups are all less than a certain threshold value,it shows that the optimal solution convergence rate of GA is in lower,then turn to the ACO.

Genetic Algorithm Design

Encoding rules. The random search algorithm get the path from tsource node to destination node according to the network topology.A path corresponds to an individual.Individual chromosome coding is the node sequence of path.Chromosome length can be varied.

Fitness function. Fitness function is the criterion of evaluation 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 inexistent link can't be selected as the routing.d)The path must be meet the transmission constraints.The fitness function is composed of the objective function and the penalty function. It is defined as follow[8].

1,z≤0

rd,z>0 (0<rd<1)

Objective function: fc=

Delay penalty function: fd=Φd{Delay(p)-D } Φd(z)=

1,z≤0

rl,z>0 (0<rl<1)

Packet loss ratio penalty function: fl=Φl{Loss(p)-L} Φl(z)=

1,z≤0

rb,z>0 (0<rb<1)

Bandwidth penalty function: fb=Φb{B- BandWidth (p)} Φb(z)=

Fitness function: F(p)= fc(Afd+Bfl+Cfb)

Where A,B and C are the normalization coefficients and posistive real numbers,they respectively means the proportion of delay,packet loss rate and the weight of bandwidth in the objective function. The size of rd,rl and rb determine the penalty degree.When the routing meet the QoS constraints,penalty function value is 1,otherwise is a real between 0 to 1.The objective function fc reflect the influence of the path cost to the individual good degree.

Initialize population. The initial population size N can be get by encoding the N paths searched randomly on the network.

Selection operation.Using the best individual preservation method combined with roulette selection method.

Crossover operation.To avoid the illegal path,the paper adopts two-point crossover method.This method main idea is to random selecte two paths p1,p2 from the path set,and find out all the same nodes between them, random selecte two nodes a,b from the same nodes (the order of a,b in the p1, p2 should be the same),then exchange the part between a and b and delete the duplicate parts of the path.

Mutation operation. A path is random selected and a node k is random finded in it.All the nodes before k should be added to the offspring.Then let k as the start point and the original destination node as the end point, random searching a path which doesn't contain all the nodes before k.Then adding the path to the back of offspring.This method can avoid the illegal path and can ensure population diversity.

Terminal conditions.The GA terminal condition is the best combination time of GA and ACO.Set the iteration number GN of GA(GNmin<GN<GNmax), where GNmin/GNmax represent minimum and maximum genetic iteration.According to the mesh wireless route optimization target, the evolutionary rate R=- should be calculated for each iteration,where is the group average cost after the ith (GNmin<i≤GN)iteration of GA.If continuous 3 times the R is satisfied 0<R<Rmin,GA is terminated,then turn to the ACO. Rmin is the given minimum threshold.

The design of ACO

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

Objective function and Fitness function are same as that of GA.

Initial pheromone.Pheromone initial setting is based on the results of GA. The initial pheromone value of each edge eij(0≤i,j≤n)is defined as formula(1):

(1)

Where τ(i,j)C is a pheromone constant of eij , τ(i,j)G is a pheromone converted from the GA results,it's initial value is 0.When GA is terminated, the 10% of the paths that have the best fitness value are selected as the genetic optimize set.The τ(i,j)G of eij on each path in the set add a constant.If eij is on severl paths,the corresponding τ(i,j)G should be accumulated.

Path selection.When the ant k at node i, the next node j should be selected according to the formula(2).

Pk(i,j)=

(2) j∈Lk(i)

0 otherwise

where Pk(i,j) is the probability that the ant k of node i select eij , Lk(i) is a adjacent node set of i,η(i,j)=1/Cost(i,j) is visibility function, α,βare parameters.Adopting formula (2) to select a path can avoid falling into local optimization.

Partial update.In order to prevent excessive residual pheromone from submerging heuristic information, eij needs to update the pheromone iteratively according to the formula(3)when the ant k successfully complete a hop from i to j.

τ(i,j)=(1-ρ)τ(i,j)+ 0<ρ<1 (3)

whereρis pheromone residual coefficient,1-ρis the pheromone evaporation rate,m is the ants total number,-τk(i,j) is the pheromone concentration lefted by the kth ant when it pass eij .To select the best meet the QoS requirements path, -τk(i,j) is caculated by formula(4).

-τk(i,j)=

Q·eγPjb/(Delay(i,j)·Loss(i,j)·Cost(i,j)) kth ant moving from i to j

(4)

0 otherwise

where Q is a constant.Pjb =B/BL is the bandwidth seleciton probability of choosing the next hop node j,B is bottleneck bandwith from j to destination node,BL is link bandwidth.Formula(4) represents the increment of pheromone concentration can be adjusted dynamically according to the QoS parameters of the path.Ants are more likely to choose a path that has large availbe bandwidth,delay,packet loss rate and hop minimum.

Global update.To searching for the global optimal solution, the pheromone of each edge need to be global updated when all the ants complete one cycle.Firstly,a path Lbes which has the maximum fitness function value is selected.Then global pheromone update can be completed according to formula(5).

τ(i,j) =(1-ρ1) ·τ(i,j)+ ρ1·-τ (5)

whereρ1 is volatile coefficient,-τ is calculated by formula(6).

-τ=

Q1/Fmax Lbest

(6)

0 otherwise

where Q1 is constant, Fmax is fitness function value of the best path.

End conditions. When ACO iterations reach the maximum value ANmax,the ACO terminates.

Hybrid genetic algorithm

Firstly,the problem is described as the WMN QoS routing model.Then,the model is initialized.Node features will be added to the link, the algorithm only consider link. The unsatisfied Qos constraints links are removed,and a new network topology to be formed .

Algorithm Description:

Random generate network topology of N nodes.The problem is described as QoS routing problems and initialized.

Random generate a group of coding,and generate initial population P(g),g=0; //g is genetic algebra.

Caculate the fitness value of individual in P(0).

Repeat the following GA until meet the end conditions of GA:

According to the fitness function and selection operation to determine the choice probability of each individual in P(g);

The two individuals with highest fitness in P(g) directly inherited to the next generation;

Execute crossover and mutation operation;

From the P(g) choose 10% of strong adaptbility individual as majorizedset.

To every individual in the majorizedset, the results of GA is set to the initial pheromone of ACO according formula(1).

Repeat the following ACO until meet the end conditions of ACO.

M ants are put the source node s.m is equal to the network nodes.

Each ant determine the next node according to formula (2).

After the ants the completion one step, formula(4) is used to excute local update for link pheromone.

When all ants complete a routing selection, it adopt formula(6) to excute global update of routing pheromone that each ant selectes.

Output optimal solutions.

Simulation experiments and analysis of the results

Using the NS2 to analyze QoS routing optimal performance of the HGA in WMN.Simulation scenario is 1000*1000 square area.System simulation environment parameters showned in table 1.

Table 1 simulation environment parameters

Classification

Parameter

Datapacket length

512byte

Wireless transmission range

250m

Simulation time

200s

Nodes

100

Data folw transmission rate

10

Channel transmission rate

2Mbps

Available bandwidth generated randomly is an integer between 1 to 10,delay is an integer between 10 to 20,packet loss ratio is a decimal between 0.01 to 0.1. In GA,Pc=0.45,Pm=0.05,GNmin=15,GNmax=60,Rmin=2%,N=50.In ACO,T(i,j)C=60, T =2,α=0.8,β=2,Q=100,Q1=10,ρ=ρ1=0.5,γ=0.7,ANmax=100.

HGA proposed in this paper is compared with the ACO and GA in the same environment to test its performance.Figure 1 shows the average delay comparison of algorithms. The results show that average delay of HGA is less than the other two algorithms,because this algorithm combines with the advantages of GA and ACO,then it can quickly find the routing satisfying multiple QoS constraints and reduce end-to-end delay.Figure 2 describes the relationship between time and node size.When the nodes are fewer,the algorithm is slightly better than the other two algorithms.As the number of nodes increases,the HGA execution efficiency is significantly better than GA and ACO.

Figure 1 Average delay comparison Figure 2 Relationship between time and node size

Conclusions

This paper analyzes the structural features of the WMN,Combine with the characteristics of GA algorithm and ACO,proposed a HGA to solve the WMN QoS routing problem. The algorithm uses the rapid global search ability of GA to compensate the shortcoming of lacking initial pheromone and solving speed slowly.At initial stage, the GA is used to generate initial pheromone, the pheromones are leaved on better path.At late stage, the ACO is used to get exact solution becase of its positive feedback characteristics.By computing evolution rate to ensure the integration time of the two algorithm.Simulation results show that HGA algorithm is more suitable than using single GA and ACO for QoS routing of wirless Mesh network.

References

1. Ian F. Akyildiz, Xudong Wang, Weilin Wang, Wireless Mesh Networks:A Survey.Computer Networks and ISDN Systems (Elsevier), 2005,47,(4).445-487

2. WANG Z,GROWCROFT J.Quality of service for supporting multimedia application.IEEE JSAC,1996,14(7):1228-1234

3. Gao Shang,Yang Jing-yu.Swarm intelligence algorithm and its application. China Waterpower Press,Beijing.2006

4. LI La-yuan, LI Chun-lin.QoS multicast routing algorithm based on GA.Journal of Systems Engineering and Electronics,2004,15(1): 90-97.

5. Ke Zong-wu,Li La-yuan.GA-based QoS multicast routing for wireless mesh networks. Computer Engineering and Applications, 2007,43(3):5-7.

6. Sun Dan-dan,Miao Jian-song.Routing selected algorithm based on ant-colony optimization in Ad Hoc networks.Journal of Jilin University(Information Science Version) ,2007,25(6):582-586.

7. Xiong Zhi-hui,Li Si-Kun. Hardware/Software partitioning based on dynamic combination of genetic algorithm and ant algorithm. Journal of software,2005,16(4):503-512.

8. Huan Xiao-wen,He Xi-ping,Tang Xian-ying. QoS Routing Selection Based on Genetic Algorithm and Simulation.Computer simulation , 2003, 20(6): 43-45.

.