Minimum-cost gateway placement in wireless mesh networks with QoS constraints - ZENG Feng; CHEN Zhi-gang; DENG Xiao-heng (Tongxin xuebao)
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 GREEDYLDS 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 PSOLDS was proposed,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 GREEDYLDS has lower computing complexity,and when the number of gateway candidate is more than 17% of the total number of node,the result from GREEDYLDS is better than the others.Simulation also shows that PSOLDS can get the more optimal solution at the price of increasing of executing time.Compared with GREEDYLDS and OPEN/CLOSE,the average cost of gateway placement is decreased by about 15% and 9% respectively.