基于替代原理的无线网状网网关部署问题研究  

Gateway Deployment of Wireless Mesh Networks Based on Substitution Principle

作　　者：黄书强[1] 王高才[2] 张震[3] 徐勇军[4] 安竹林[4] 邓玉辉[3] 李阳[3] 

机构地区：[1]暨南大学网络与教育技术中心,广州510632 [2]广西大学计算机与电子信息学院,南宁530004 [3]暨南大学信息科学技术学院,广州510632 [4]中国科学院计算技术研究所,北京100086

出　　处：《计算机学报》2016年第6期1120-1134,共15页Chinese Journal of Computers

基　　金：国家"八六三"高技术研究发展计划项目基金(2013AA040404);国家自然科学基金(61262003;61272073;61373125;61303245);广东省自然科学基金项目(S2013020012865;2014A030313386);广东省教育厅科技创新项目(2013KJCX0018);暨南大学科研培育与创新基金项目(21615439;21615443)资助

摘　　要：几何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.

关 键 词：无线MESH网络 网关部署 几何K中心 虚拟节点 替代原理 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]