基于紧密中心性的无线mesh骨干网网关部署

doi:10.3969/j.issn.1000-0801.2015045

摘要/Abstract

摘要：

将定向天线和Delaunay图应用于无线mesh骨干网络的网关部署，提出了基于紧密中心性的无线mesh骨干网络网关部署算法。根据已知的mesh路由器和网关的最大流通量对网络进行划分，形成Delaunay子图，在划分的子图中根据欧几里德距离找出距离中心点最近的3个节点，形成候选网关集，在候选网关集中选择到其他节点总路径最短的节点作为网关的部署位置，将每个子图的网关位置输出。仿真结果表明，根据网关最大流通量进行合理网络划分后，算法能最小化网络的网关数量，由mesh路由器到网关的总路径长度优于随机算法。

关键词: 无线mesh网络, 网关部署, 定向天线, Delaunay图

Abstract:

Directional antenna and Delaunay graph were used in the gateway deployment optimization of wireless mesh backbone network and a gateway deployment optimization algorithm of wireless mesh backbone network based on closeness centrality was proposed. Firstly, according to the largest traffic of mesh router and gateway, the algorithm divides the network into a few clusters forming Delaunay sub-graph. In the sub-graph, according to the Euclidean distance of each nodes to the center nodes, the algorithm find out the closest three nodes to the center nodes and form the gateway candidate set. The node in this gateway candidate set, which has the shortest route path to the other nodes, is the location of gateway of this cluster. Gateway location of each sub-graph will be achieved in the end. Simulation experimental results show that, after reasonable network partitioning according to the largest traffic of gateway, the algorithm can minimize the number of network gateway. The total path length from the mesh routers to the gateway of the algorithm is better than that of the random algorithm.

Key words: wireless mesh network, gateway deployment, directional antenna, Delaunay graph

郭诚欣,李陶深,葛志辉. 基于紧密中心性的无线mesh骨干网网关部署[J]. 电信科学, 2015, 31(2): 80-85.

Chengxin Guo,Taoshen Li,Zhihui Ge. Gateway Deployment Optimization in Wireless Mesh Backbone Network Based on Closeness Centrality[J]. Telecommunications Science, 2015, 31(2): 80-85.

图/表 8

图1

图2

图3

图4

图5

图6

图7

2014

参考文献 14

1	Akyildiz I F , Wang X D , Wang W L . Wireless mesh networks: a survey. Computer Networks, 2005,47(4): 445～487
2	He B , Xie B , Agrawal D P . Optimizing deployment of internet gateway in wireless mesh networks. Computer Communications, 2008,31(7): 1259～1257
3	曾锋，陈志刚，邓晓衡．无线mesh 网中费用最小且 QoS 约束的网关部署算法研究．通信学报， 2009,30(6): 80～88 Zeng F , Chen Z G , Deng X H . Minimum-cost gateway placement in wireless mesh networks with QoS constraints. Journal on Communications, 2009,30(6): 80～88
4	翦鹏，漆华妹，陈志刚．无线mesh网络中基于最小权有限支配集的网关部署算法研究．计算机工程与科学, 2011,33(8): 14～18 Jian P , Qi H M , Chen Z G . Research of a gateway deployment algorithm for wireless mesh networks based on the limited dominating set. Computer Engineering&Science, 2011,33(8): 14～18
5	吴文甲，杨明，罗军舟等．干扰约束和负载均衡的无线 mesh网络网关部署策略．计算机学报, 2012,35(5): 883～897 Wu W J , Yang M , Luo J D , et al. A gateway placement scheme with interference constraints and load balance in wireless mesh networks. Chinese Journal of Computers, 2012,35(5): 883～897
6	Dai H N , Ng K W , Wu M Y , et al. On the capacity of multi-channel wireless networks using directional antennas. Proceedings of INFOCOM, Phoenix,AZ,USA, 2008
7	Yeh P C , Stark W E , Zummo S A . Performance analysis of wireless networks with directional antennas. IEEE Transactions on Vehicular Technology, 2008,57(5):3187～3199
8	Kandasamy S , Campos R , Morla R , et al. Using directional antennas on stub wireless mesh networks: impact on throughput, delay, and fairness. Proceedings of 19th International Conference on Computer Communications and Networks, Zurich, Switzerland, 2010:1～6
9	Okada H , Mase K . Performance analysis of wireless mesh networks with three sector antennas. Proceedings of the 6th International Wireless Communications and Mobile Computing Conference, Caen,France, 2010
10	Ben-Othman J , Mokdad L , Cheikh M O . A new architecture of wireless mesh networks based IEEE 802.11s directional antennas. Proceedings of IEEE International Conference on Communications, Kyoto, apan, 2011:1～5
11	Li W G , Li T S , Ge Z H . A delaunay triangulation based method for optimizing backbone wireless mesh networks. Proceedings of International Conference on Computer Science and Service System, Nanjing, China, 2011:959～962
12	Hu Z P , Verma P K . Gateway placement in backbone wireless mesh networks using directional antennas. Proceedings of the 9th Annual Communication Networks and Services Research Conference, Ottawa,ON,Canada, 2011:175～180
13	Wu C H , Lee K C , Chung Y C . A Delaunay triangulation based method for wireless sensor network deployment. Proceedings of the 12th International Conference on Parallel and Distributed Systems, Minneapolis, MN, USA, 2006
14	Gao J J , Zhou J P . Delaunay-based heterogeneous wireless sensor network deployment. Proceedings of the 8th International Conference on Wireless Communications, Networking and Mobile Computing, Shanghai,China, 2012:1～5

指标名称	单位	本月末到达	比上年末净增	本月净增
固定电话用户合计	万户	25 086.8	-1 611.7	-129.0
公用电话用户	万部	2 074.5	-158.9	-20.7
城市电话用户	万户	17 696.9	-759.9	-43.0
住宅电话用户	万户	9 918.9	-555.4	-56.0
农村电话用户	万户	7 389.9	-851.8	-86.0
住宅电话用户	万户	5 837.3	-806.1	-77.9
移动电话用户合计	万户	128 103.2	5 191.9	437.1
其中：3G用户	万户	48 102.5	7 941.4	-55.0
互联网拨号用户	万户	444.4	-40.6	-1.3
互联网宽带接入用户	万户	20 066.0	1 175.1	26.1
其中：xDSL用户	万户	9 239.9	-1 476.6	-215.8
移动互联网用户	万户	86 973.3	6 217.0	-439.3
固定电话普及率	部/百人	18.6
移动电话普及率	部/百人	93.5

[1]	李明明,乐光学,代绍庆,马柏林. 无线mesh网络中可信协同信道资源分配策略[J]. 电信科学, 2017, 33(5): 62-74.
[2]	王明伟,张会生,李立欣,何立风. 基于定向天线的多中继DF协作通信系统性能分析[J]. 电信科学, 2016, 32(6): 129-135.
[3]	乐光学,宋昊,熊小峰,刘建生,马柏林. 基于多目标的MIMO无线mesh网络信道优化策略[J]. 电信科学, 2016, 32(11): 16-25.
[4]	李陶深,张宏宇,叶进,葛志辉. 基于M/M/1的无线mesh网络网关分析模型[J]. 电信科学, 2015, 31(1): 2015044-.
[5]	李陶深,张宏字,叶进,葛志辉. 基于M/M/1的无线mesh网络网关分析模型[J]. 电信科学, 2015, 31(1): 58-64.
[6]	乐光学,骆丹,刘建生,李明明. 无线Mesh网络中的搭便车行为分析与抑制策略研究[J]. 电信科学, 2014, 30(5): 65-74.
[7]	乐光学,骆丹,刘建生,李明明. 无线mesh中传输速率抖动抑制策略研究[J]. 电信科学, 2014, 30(10): 89-98.
[8]	郑鹏宇,何世彪,戴昊峰,张晖. 一种基于博弈论的无线mesh网络信道分配算法[J]. 电信科学, 2013, 29(7): 59-65.
[9]	陆春龙,曹玉春,乐光学. 无线mesh网络中能量空洞规避策略研究[J]. 电信科学, 2013, 29(11): 29-37.
[10]	唐琳,夏越. 基于定向天线的无线传感网络环境自适应定位算法[J]. 电信科学, 2012, 28(7): 80-85.
[11]	李陶深,陈阳,葛志辉. 无线Mesh网络可用带宽估计方法的研究[J]. 电信科学, 2012, 28(1): 1-78.
[12]	李陶深,陈阳,葛志辉. 无线Mesh网络可用带宽估计方法的研究[J]. 电信科学, 2012, 28(1): 70-74.
[13]	李陶深,丘小兰,葛志辉. 基于选播机制的无线Mesh网络网关选取路由算法[J]. 电信科学, 2011, 27(12): 72-76.
[14]	葛志辉,李陶深,韦亚欢. 一种新的基于最大流的无线Mesh网络信道分配算法[J]. 电信科学, 2011, 27(12): 53-56.
[15]	黄昭文,冯穗力,叶梧,庄宏成. 一种多出口的WiMAX Mesh回程网络资源调度算法[J]. 电信科学, 2009, 25(4): 68-73.