中文摘要：

几何K中心网关部署问题是无线网状网拓扑优化中一个难题,将几何K中心网关部署问题转化为节点K中心问题进行求解是一种可行的方法,但是转化过程产生的大量虚拟节点扩大了网络节点规模,从而降低了求解效率和效果.为了缩减虚拟网络规模,文中结合无线Mesh网络拓扑结构和邻接节点的包含关系,提出了基于拓扑学的替代原理,并分析和证明了该理论的完备性.首先将平面中不可列的节点按连通性分成有限类,并将不同的类视为虚拟节点加入到原来的无线Mesh网络中,形成新的虚拟网络.然后利用多阶替代原理剔除大量的冗余节点,获得一个与原虚拟网络等价但规模很小的替代网络.最后设计了基于替代网络的遗传算法（GASK）求解该问题.实验仿真结果和分析表明,替代原理能充分优化网络结构并缩小虚拟网络规模,基于替代网络的遗传算法能够获得更优的覆盖半径,其求解效果、效率和稳定性均优于传统算法.

英文摘要：

Geometric K-center gateway deployment is a hard problem of topology optimization in wireless mesh networks,and converting the geometric K-center problem into a node K-center problem is a feasible method.However,large amounts of virtual nodes will be produced during the conversion process,and the size of the network nodes will be expanded thus the solving efficiency and effectiveness will decrease.To reduce the size of the virtual network,taking into wireless mesh network topology and the adjacent node contains relations,substitution principle is proposed based on topology theory in the paper,and theory completeness of the substitution principle is analyzed and proved.To solve the problem,first the plane nodes are classified intonumber of categories according to connectivity,and each class is incorporated as a virtual node to the original network structure to form a new virtual network.Then by using multi-stage substitution principle,a large number of redundant nodes can be removed and the original virtual network can be converted into a much smaller scale and equivalent substituted network structure.Finally,we proposed a genetic algorithm based on substituted network（GASK）to solve the problem of geometric K-center gateway deployment.Simulation results show that substitution principle can fully optimize the network structure and reduce the size of the virtual network,and the GASK algorithm is more effective,efficient and stable than other traditional algorithms based on original network.