无线mesh网中费用最小且QoS约束的网关部署算法研究  

Minimum-cost gateway placement in wireless mesh networks with QoS constraints

作　　者：曾锋[1] 陈志刚[1] 邓晓衡[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《通信学报》2009年第6期80-88,共9页Journal on Communications

基　　金：国家自然科学基金资助项目(60873082);中国博士后科学基金资助项目(20060400879);湖南省教育厅资助项目(08C510)~~

摘　　要：基于图的支配集理论,提出图的有限支配集的概念应用于满足QoS约束的无线mesh网网关优化部署,以获取费用最小网关部署方案,进而把QoS约束的费用最小网关部署问题归结为图的最小权有限支配集的问题。为求解图的最小权有限支配集,提出了贪婪算法GREEDY_LDS,该算法以网关的部署性价比作为启发信息,依次挑选部署性价比高的节点加入有限支配集,最后得到权值较小的有限支配集;为得到更加优化的解,利用粒子群优化算法的全局寻优优势,提出粒子群优化算法PSO_LDS,该算法通过阻止粒子在狭小区域运动来防止算法陷入早熟收敛。模拟实验表明,GREEDY_LDS算法执行速度快,当网关候选节点数超过总节点数的17%时,能得到比其他算法更好的结果;PSO_LDS算法以增加执行时间为代价,与GREEDY_LDS和OPEN/CLOSE算法相比,得到的网关部署方案的费用分别减少约15%和9%。Focusing on gateway optimal placement with QoS constraints in WMNs and aiming to minimize the cost of gateway placement, firstly, a new concept of limited dominating set （LDS） in graph was presented to addresses the gateway placement problem, and to find the solution of minimum placement cost is to find the LDS of minimum weight in the graph. Then, in order to find the minimum weighted LDS in graph, a greedy algorithm GREEDY_LDS was proposed, in which the ratio of LOAD/COST was used as heuristic information to find minimum cost placement of gateway. To get further optimal solution, a particle swarm optimization algorithm PSO_LDS was proposed, in which two premature avoidance methods were presented to improve the algorithm＇s ability of searching for global optimal solution. At last, simulation has been done, and experiment result shows that GREEDY_LDS has lower computing complexity, and when the number of gateway candidate is more than 17% of the total number of node, the result from GREEDY_LDS is better than the others. Simulation also shows that PSO_LDS can get the more optimal solution at the price of increasing of execnting time. Compared with GREEDY_LDS and OPEN/CLOSE, the average cost of gateway placement is decreased by about 15% and 9% respectively.

关 键 词：无线MESH网 网关部署 QoS 支配集 贪婪算法 粒子群优化算法 

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