基于极大全连通子图的无线Mesh网络网关部署研究  

Research of Gateway Deployment for Wireless Mesh Networks Based on the Great Full Connected Sub-graphs

作　　者：范人胜 黄书强[2] 李阳[1] 

机构地区：[1]暨南大学信息科学技术学院,广州510632 [2]暨南大学网络与教育技术中心,广州510632

出　　处：《小型微型计算机系统》2015年第11期2526-2530,共5页Journal of Chinese Computer Systems

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

摘　　要：无线Mesh网络中,网关部署直接影响到网络的服务质量,合理的网关部署对网络性能提升具有非常重要的作用.为解决几何K中心网关部署问题,本文以节点和网关之间的路径长度最小为优化目标,提出基于极大全连通子图的中心粒子群优化(Center PSO,CPSO)算法.该算法归结为在给定的网络拓扑中寻找全连通子图,并筛选出功能最完备的极大全连通子图,求得初始中心点位置,然后结合粒子群优化算法,利用这些初始中心点位置对粒子群优化算法进行初始化,引入随机生成的惯性权重,并设计适值函数计算方法,使得算法更容易获得最优解.通过仿真实验,将所提的CPSO算法与其它算法进行对比,结果表明本文所提方法具有更好的优化效果和收敛速度.In Wireless Mesh Networks,the deployment of gateways has a direct effect on network quality of service and plays an important role to improve network performance. In this paper,to solve the geometric K-center problem,an improved PSO algorithm based on great full connected sub-graphs is proposed to optimize the minimum coverage radius. The algorithm can be described as to find full connected sub-graphs in given network topology,then great full connected sub-graphs with the most complete function are filtered out,and the position of initial center points are obtained by great full connected sub-graphs. Combining initial center points with PSO,the particles are initialized at the position of initial center points,random inertia weight is introduced,and the fitness function is redesigned,the algorithm can get optimal solution. Comparing CPSO with other algorithms,the simulation results showthat the proposed method can achieve better optimization effect and convergence rate.

关 键 词：MESH网络 网关部署 几何K中心 粒子群算法 全连通子图 

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