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

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

郭诚欣;李陶深;葛志辉

【摘要】将定向天线和Delaunay图应用于无线mesh骨干网络的网关部署,提出

了基于紧密中心性的无线mesh骨干网络网关部署算法.根据已知的mesh路由器

和网关的最大流通量对网络进行划分,形成Delaunay子图,在划分的子图中根据欧

几里德距离找出距离中心点最近的3个节点,形成候选网关集,在候选网关集中选择

到其他节点总路径最短的节点作为网关的部署位置,将每个子图的网关位置输出.仿

真结果表明,根据网关最大流通量进行合理网络划分后,算法能最小化网络的网关数

量,由mesh路由器到网关的总路径长度优于随机算法.

【期刊名称】《电信科学》

【年(卷),期】2015(031)002

【总页数】6页(P80-85)

【关键词】无线mesh网络;网关部署;定向天线;Delaunay图

【作者】郭诚欣;李陶深;葛志辉

【作者单位】广西大学计算机与电子信息学院南宁530004;广西大学计算机与电

子信息学院南宁530004;广西大学计算机与电子信息学院南宁530004

【正文语种】中文

1引言

作为下一代无线网络的核心技术之一，无线mesh网络（wirelessmeshnetwork，

WMN）拥有组网灵活、动态自组织自愈、维护方便、覆盖范围广、能满足人们高

容量和高速率的上网要求等优点，已成为众多研究者关注的热点之一[1]。无线

mesh网络是一种通过无线介质进行多跳传输的网络，主要包括3类节点：网关

（gateway，GW）、mesh路由器（meshrouter，MR）、mesh终端，其中网

关和mesh路由器组成了无线mesh网络的骨干网络，负责给终端提供网络服务。

作为大部分网络流量汇聚的节点，网关是整个网络的瓶颈所在，网关部署的好坏制

约着整个无线mesh网络的性能。

多目标优化的网关部署问题是一个NP难的问题[2]，在以往的研究中，研究者将

网关部署问题形式化为线性规划问题，根据不同的目标提出相应的网关部署算法。

参考文献[2]根据网络的R跳连通图提出了两种启发式算法，达到最小化网关数量

和最小化MR-GW路径跳数的目的。参考文献[3]和参考文献[4]则把最小化网关部

署费用且受到一定的QoS约束问题归结为求解图的最小支配集问题，其中，参考

文献[3]提出了基于贪心算法的GREEDY_LDS算法和基于粒子群算法的PSO_LDS

算法，前者能在较短时间内获得局部的最优部署方案，后者则通过增加运算时间，

获得全局的最优解。参考文献[4]在GREEDY_LDS算法的基础上进行了改进，提出

了GREEDY_LDSC算法和GREEDY_LDSI算法，分别提高了网关部署的性价比和

部署费用。参考文献[5]提出了基于负载权重的贪心式网关部署算法，在最小化网

关数量的同时消减链路干扰，实现网关间的负载均衡。上述的网关部署算法都是基

于全向天线的环境，不可避免地要考虑通信干扰等问题。相对于全向天线，定向天

线的使用能提高整个无线mesh网络的性能，包括降低节点间的干扰、提高空间

复用率、增加网络吞吐量[6,7]等。

近年来，越来越多的学者开始研究将定向天线应用于无线mesh网络的问题，以

达到提高网络整体性能的目的。参考文献[8]介绍了使用定向天线对于整个网络性

能的提升程度，将网络的拓扑结构设定为一个网格结构，其中每一个节点装备一条

4阵列的波束天线，分析了网络在吞吐量、时延、公平性上获得的增益大小。参考

文献[9]介绍了在WMN中使用三扇天线系统的性能，指出使用三扇天线能解决以

往使用定向天线后出现的许多问题，如隐藏终端和暴露终端、“盲点

（deafness）”等。参考文献[10]在IEEE802.11s标准下提出了类似的结构，在

不同的方向上使用不同的固定波束天线，每一条天线覆盖一个固定区域，能达到覆

盖全角度的目的，同时减少了路由开销。上述的研究工作主要集中于MAC层，网

络部署方面的研究仍不多，参考文献[11]将Delaunay图应用于定向天线下WMN

骨干网的部署优化，通过删除三角形的多余边，达到简化网络拓扑、降低部署