无线Mesh网络中基于最小权有限支配集的网关部署算法研究

J4 ›› 2011, Vol. 33 ›› Issue (8): 14-18.

无线Mesh网络中基于最小权有限支配集的网关部署算法研究

翦鹏,漆华妹,陈志刚

(中南大学信息科学与工程学院，湖南长沙 410083)

收稿日期:2010-10-10 修回日期:2011-02-15 出版日期:2011-08-25 发布日期:2011-08-25
作者简介:翦鹏(1987),男,湖南常德人，硕士生，研究方向为无线Mesh网络。漆华妹(1979),女,江西南昌人，博士，研究方向为无线Mesh 网络、网络演算。陈志刚(1964),男，湖南益阳人，博士，教授，研究方向为网络计算与分布式处理。
基金资助:
国家863计划资助项目(2008AA7034060B)；国家自然科学基金资助项目(60873082)；总参预研基金资助项目(9140A15030308QT4801)

Research of a Gateway Deployment Algorithm for Wireless Mesh Networks Based on the Limited Dominating Set

JIAN Peng,QI Huamei,CHEN Zhigang

(School of Information Science and Engineering,Central South University,Changsha 410083,China)

Received:2010-10-10 Revised:2011-02-15 Online:2011-08-25 Published:2011-08-25

摘要/Abstract

摘要：

无线Mesh网络中网关是网络性能的瓶颈，网关部署至关重要。本文对无线Mesh网络中网关QoS性能进行分析，提出基于最小权有限支配集，以部署费用为贪心策略的贪婪算法(Greedy_LDSC)，该算法用贪心法提高了网关的性价比。同时，提出了基于最小权有限支配集改进的贪婪算法(Greedy_LDSI)，以降低网关的部署费用。仿真实验表明，从网关性价比方面来看，Greedy_LDSC算法的网关性价比之和比基于最小权有限支配集的网关部署算法(GREEDY_LDS)要高；从网关部署费用方面来看，Greedy_LDSI算法的网关部署费用比GREEDY_LDS算法会低。

关键词: 无线Mesh网络, 网关, QoS, 网关部署算法

Abstract:

The gateway in wireless mesh networks always acts as the bottleneck of network performance. Therefore, the deployment of gateways is very important. This paper analyzes the QoS performance of gateways in wireless mesh networks, and proposes a Greedy Algorithm Based on the Limited Dominating Set with a Cost Strategy(Greedy_LDSC). This algorithm improves the cost performance by using a greedy algorithm. In addition, to reduce the cost of the deployed gateway, an Improved Greedy Algorithm Based on the Limited Dominating Set(Greedy_LDSI) is proposed. From the aspect of the cost performance, simulation experiments show that Greedy_LDSC is higher than GREEDY_LDS at the sum of the cost performance of the gateway. In terms of the cost of the gateway deployment, Greedy_LDSI shows better performance than GREEDY_LDS.

Key words: wireless mesh network;gateway;QoS;gateway deployment algorithm

翦鹏,漆华妹,陈志刚. 无线Mesh网络中基于最小权有限支配集的网关部署算法研究[J]. J4, 2011, 33(8): 14-18.

JIAN Peng,QI Huamei,CHEN Zhigang. Research of a Gateway Deployment Algorithm for Wireless Mesh Networks Based on the Limited Dominating Set[J]. J4, 2011, 33(8): 14-18.

[1]	苟平章, 马琳, 郭保永, 原晨. 基于软件定义网络的多约束QoS双路径路由优化方法[J]. 计算机工程与科学, 2023, 45(01): 46-56.
[2]	罗磊, 陈照云, 王俪璇. 用户QoS感知的GPU集群深度学习任务动态调度[J]. 计算机工程与科学, 2021, 43(08): 1331-1340.
[3]	罗莉, 周宏伟, 周理, 潘国腾, 周海亮, 刘彬. 一种多核处理器直连接口QoS的设计与验证[J]. 计算机工程与科学, 2021, 43(04): 620-627.
[4]	童钊, 叶锋, 刘碧篮, 邓小妹, 梅晶, 刘宏. 移动边缘计算中多约束下的任务卸载和资源分配算法[J]. 计算机工程与科学, 2020, 42(10高性能专刊): 1869-1879.
[5]	蒋冰婷1，胡志刚1，马华2，姚景1. 基于时间感知排序的云服务QoS预测方法研究[J]. 计算机工程与科学, 2018, 40(07): 1173-1179.
[6]	羊秋玲1,2，解冰珊2,3，金志刚2，苏毅珊2，黄向党1. 基于嵌入式技术的水声传感网和#br# VHF通信网络的互联网关设计[J]. 计算机工程与科学, 2018, 40(04): 642-648.
[7]	唐勇，王卫振，汪文勇，徐宾伟. SDN与传统IP网络互联架构的设计与实现[J]. 计算机工程与科学, 2017, 39(12): 2210-2216.
[8]	李娅楠，肖美华，李伟，梅映天，钟小妹. 基于事件逻辑的无线Mesh网络认证协议安全性证明[J]. 计算机工程与科学, 2017, 39(12): 2236-2244.
[9]	羊秋玲1，2，金志刚1，黄向党2. 无线Mesh网络中基于业务价值的组播带宽分配方案[J]. 计算机工程与科学, 2016, 38(10): 1986-1993.
[10]	戴荣倩1，左德承1，张展1，李士雷2. 云计算弹性评测模型的研究与实现[J]. 计算机工程与科学, 2016, 38(08): 1581-1587.
[11]	颜丽燕，张桂珠. 基于蜂群算法的多维QoS云计算任务调度[J]. J4, 2016, 38(04): 648-655.
[12]	陈燕燕. 基于跨层设计的认知无线Mesh网络拥塞反馈研究[J]. J4, 2015, 37(05): 925-929.
[13]	段玉聪1,高洪皓2,唐朝胜1,杜文才1,万世想1,卢俊星1. 基于过设计与欠设计约束的服务质量控制方法收[J]. J4, 2015, 37(01): 84-92.
[14]	蔡小波1,2，张学杰1. 一种基于QoS参数归约的云计算环境能效评估方法[J]. J4, 2014, 36(12): 2305-2311.
[15]	肖文娟，段玉聪. 基于时间序列的感知QoS的云服务组合[J]. J4, 2014, 36(11): 2061-2066.