Gateway deployment and channel assignment are important for the wireless mesh network planning because they influence the network quality of service directly. Traditionally, the two problems are studied separately. In this paper, a comprehensive strategy is proposed to minimize both the link collision and the cost of gateway deployment for wireless mesh network. In addition, the load balance is also considered in the planning stage and characteristics of the aggregation of flow traffic near the gateway in wireless mesh network are reflected by the degree of link collision. For the gateway deployment, it has been proved to be NP-hard. Here a novel multi-objective particle swarm algorithm is proposed to optimize both channel assignment and gateway deployment. The route of nodes is built through creating a tree algorithm after the channel are assigned and gateway are selected. Thus, the two problems are decoupled. The channel assignment and gateway deployment are then obtained in polynomial time for wireless mesh network planning. Comparing with the existing algorithms based on balanced channel repartition, the simulation results show that our proposed algorithm can reduce network collision effectively and improve network performance significantly, while reducing the path length and obtaining load balance of the gateways.