Focusing on gateway optimal placement with QoS constraints in WMNs and aiming to minimize the cost of gateway placement

firstly

a new concept of limited dominating set（LDS） in graph was presented to addresses the gate-way placement problem

and to find the solution of minimum placement cost is to find the LDS of minimum weight in the graph.Then

in order to find the minimum weighted LDS in graph

a greedy algorithm GREEDY

L

DS was proposed

in which the ratio of LOAD/COST was used as heuristic information to find minimum cost placement of gateway.To get further optimal solution

a particle swarm optimization algorithm PSO

L

DS was propo

sed

in which two premature avoidance methods were presented to improve the algorithm’s ability of searching for global optimal solution.At last

simulation has been done

and experiment result shows that GREEDY

L

DS has lower computing complexity

and when the number of gateway candidate is more than 17% of the total number of node

the result from GREEDY

L

DS is better than the others.Simulation also shows that PSO

L

DS can get the more optimal solution at the price of increasing of executing time.Compared with GREEDY

L

DS and OPEN/CLOSE

the average cost of gateway placement is decreased by about 15% and 9% respectively.