中文摘要：

目前无线Mesh网络中几何K中心网关部署问题没有得到很好地解决,该问题可以归结为在给定的几何平面上部署合适的网关节点,以满足覆盖条件的同时提高网络服务质量.为解决该问题,文中首次提出了极大备选区域的思想和生成算法.根据网络拓扑和单位覆盖圆的性质,将节点的平面区域按照连接性能的差异划分为不同的备选区域,并筛选出功能最完备的极大备选区域作为虚拟节点,插入到原始的Mesh网络图中,生成一个新的网络拓扑图,从而将几何K中心问题转化为传统的节点K中心问题.然后以最小最大跳数为优化目标,利用改进的遗传算法对该问题进行求解.与Kmeans算法进行比较,遗传算法具有较好的网关中心聚类效果.研究结果表明,文中所述方法可以较好地解决几何K中心网关部署问题.

英文摘要：

Now there is no good solution to the problem of geometric K-center gateway deploy- ment in wireless mesh networks, and the problem is deploying some gateways in given geometric plane to meet coverage conditions and improve the quality of service. To solve the problem, the concept and algorithm of great alternative region are first proposed in the paper. The plane area is divided into different alternative regions in accordance with the nature of network topology and the unit disk and the difference connectivity. Then great alternative regions with the most com- plete function are filtered out and each great alternative region is inserted into the original net- work as a virtual node, a new network topology is generated and the geometric K-center problem is transformed into a node K-center problem. Regarding maximum minimum hops as object opti- mization, an improved genetic algorithm is proposed. Comparing with Kmeans algorithm, the ge- netic algorithm can achieve better gateway clustering effect, and the simulations show that the proposed method can solve the geometric K-center wireless gateway deployment problem.