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_LDS 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_LDS 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 GREEDY_LDS 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_LDS is better than the others. Simulation also shows that PSO_LDS can get the more optimal solution at the price of increasing of exe-cuting time. Compared with GREEDY_LDS and OPEN/CLOSE, the average cost of gateway placement is decreased by about 15% and 9% respectively.