针对无线Mesh网络网关部署和AP分组问题,提出了一种基于聚类思想的启发式算法.首先设计了一个最小跳数权重指标,其大小反映网关数以及最小跳数的辩证关系,通过这个指标,利用启发式算法获得一个较好的初始解;然后利用聚类k-means方法来对此初始解进行调整优化,使AP分组尽可能均匀;最后通过仿真实验验证该算法的有效性.结果表明：通过有限次数调整,网络可以取得最小网关数、最小AP到网关平均跳数和最小负载均衡指数3个优化目标之间的平衡.

Aiming at the gateway deployment and AP clustering of wireless Mesh networks,a heuristic algorithm based on clustering is proposed.In this algorithm,first,a weight index of the minimum hops is designed to reflect the relationship between the gateway number and the minimum hops,with which a suitable initial solution is obtained by a heuristic algorithm.Then,the initial solution is adjusted and optimized via the k-means clustering to obtain a symmetrically network distribution.Finally,some simulations are carried out to verify the effectiveness of the proposed algorithm.The results show that,with the help of the algorithm,the three optimization objectives,namely,the minimum number of gateways,the minimum average number of hops from AP to gateway and the minimum load-balancing index,reach a good balance after the adjustment with finite times.