干扰约束和负载均衡的无线Mesh网络网关部署策略  

A Gateway Placement Scheme with Interference Constraints and Load Balance in Wireless Mesh Networks

作　　者：吴文甲[1] 杨明[1] 罗军舟[1] 王维[1] 

机构地区：[1]东南大学计算机科学与工程学院,南京211189

出　　处：《计算机学报》2012年第5期883-897,共15页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2010CB328104);国家自然科学基金(60903162);高等学校博士点学科专项科研基金(20110092130002);江苏省自然科学基金(BK2008030);江苏省网络与信息安全重点实验室(BM2003201);教育部计算机网络与信息集成重点实验室(93K-9)资助~~

摘　　要：网关部署是无线Mesh网络规划面临的重要挑战之一.在Mesh路由器(MR)已完成部署的前提下,如何计算同时满足网络性能要求和用户流量需求的最小网关(GW)集合,已经被证明是一个NP-hard问题.文中提出了一种满足干扰约束和支持负载均衡的网关部署策略ICLB-GPS,在部署网关时消减链路干扰并实现网关负载均衡.ICLB-GPS策略综合网关选择、转发树构建和转发树间的节点迁移来完成负载均衡的网关部署,主要包含覆盖重叠和干扰消减的网关选择、基于树间节点迁移的网关负载均衡两个算法.仿真实验将ICLB-GPS算法与其它算法在网关数量、MR-GW路径长度、链路干扰程度及负载均衡指数方面进行比较,其结果表明该算法在不增加部署成本,不提高MR-GW路径长度的情况下,消减了链路干扰,实现了网关负载均衡.How to achieve proper gateway placement is one of the most important challenges in planning wireless mesh networks.Before gateway placement,MRs must be placed and cover the target region completely.The problem of obtaining the minimal gateway set satisfying both network performance and traffic requirements has been proved to be NP hard.In this paper,a novel Gateway Placement Scheme with Interference Constraints and Load Balance（ICLB-GPS） is proposed,considering link interference reducing and gateway load balancing.The scheme combines gateway selection,relay tree construction and node migration between relay trees to achieve load balancing gateway placement,and mainly includes two algorithms： the first one is coverage overlapping and interference reduction gateway selection algorithm,while the second one is gateway load balancing algorithm based on node migration between relay trees.Our simulation compares ICLB-GPS with other existing algorithms on the number of gateways,the MR-GW path length,link interference degree and load balance index,and the results show that ICLB-GPS achieves load balance among gateways and link interference reduction without deployment costs and MR-GW path length increased.

关 键 词：无线MESH网络 网关部署 负载均衡 干扰约束 

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