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

郭诚欣，李陶深，葛志辉

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

1 引言

作为下一代无线网络的核心技术之一，无线mesh网络（wireless mesh network，WMN）拥有组网灵活、动态自组织自愈、维护方便、覆盖范围广、能满足人们高容量和高速率的上网要求等优点，已成为众多研究者关注的热点之一[1]。无线mesh网络是一种通过无线介质进行多跳传输的网络，主要包括3类节点：网关（gateway，GW）、mesh路由器（mesh router，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]在IEEE 802.11s标准下提出了类似的结构，在不同的方向上使用不同的固定波束天线，每一条天线覆盖一个固定区域，能达到覆盖全角度的目的，同时减少了路由开销。上述的研究工作主要集中于MAC层，网络部署方面的研究仍不多，参考文献[11]将Delaunay图应用于定向天线下WMN骨干网的部署优化，通过删除三角形的多余边，达到简化网络拓扑、降低部署的定向天线数量、减少部署花费的目的。参考文献[12]则研究定向天线下无线mesh骨干网的网关部署问题，提出了基于节点通信量的启发式算法，达到最小化网关数量以及最小化路由器到最近网关的平均跳数和最大跳数的目的，但文中研究的网关部署是在随机化网络拓扑结构的基础上进行的，而随机的拓扑结构并不利于充分发挥定向天线的优势，如某些链路间的夹角过小、节点间的距离过小，均会导致定向天线间过大的干扰出现。

Delaunay三角因其良好的数学特性被广泛应用于无线网络的部署中，如无线传感器网络部署[13,14]，可增加网络的覆盖率，最小化网络部署成本。本文将研究定向天线下无线mesh骨干网的网关部署问题，以Delaunay三角作为网络的部署拓扑结构，综合考虑网络部署成本和通信时延等因素，根据图论的紧密中心性理论，将MR-GW总距离最短问题归结为寻找图的中心点问题，同时在满足一定的QoS约束下，使得网关数量最小。

2 问题描述和网络模型

2.1 问题描述

网关节点是整个WMN与互联网相连的关键节点，WMN中任何节点对于互联网的服务请求都要经过网关节点，相对于其他只负责转发数据或提供接入服务的路由节点，网关节点需要有更高的性能与可靠性，以保证网络的正常运行。除此之外，网关节点在网络中的位置也影响着整个网络的性能，网关节点的位置关系着网络时延、网络吞吐量等网络性能指标，需要在多个约束条件下进行部署。本文研究WMN骨干网的优化，每个节点上部署适当数目的定向天线，在满足用户带宽需求和网络性能的基础上，把WMN逻辑上划分为互不相交的簇，根据算法合理地选择节点作为网关，以降低部署成本和MR到网关的时延，同时兼顾网关的负载均衡和控制节点的介质竞争，即对MR的总流通量进行合理的划分以及对每个网关所服务的节点总数进行约束。由于网关的成本远大于普通的MR，所以可通过网关的数量反映网关部署的成本，MR到网关的时延则反映在MR-GW的路径长度，因此本文研究的问题有两个优化目标：最小化网关数量和最小化MR-GW的路径长度。

2.2 网络模型

本文将整个无线mesh网络的骨干网建模为一个无向连通Delaunay图G(V,E)，V={v1,v2,…,vn}代表节点集合，n为网络的节点总数，E为边的集合，即无线链路集合。节点的位置坐标可用二元组(x,y)表示，则节点vi与vj之间的欧氏距离为假设定向天线的最大传输距离为Lmax，为了减少定向天线存在的干扰，设定节点间的最小传输距离为Lmin。因此无线链路集合E={(vi,vj)|Lmin≤Lmin(i,j)≤Lmax,i≠j}，则图G的邻接矩阵为：

其中，ai,j表示节点vi和节点vj之间是否存在无线链路，若(vi,vj)∈E，则ai,j=1；否则，ai,j=0。节点间的链路距离表示为ω，大小等于两节点间的欧几里德距离，网关节点集合表示为VG，则非网关节点集合表示为VNG。

向量Z={z1,z2,…,zn}表示网关的选取情况，当节点vi被选为网关节点时，zi=1；否则，zi=0。Ti表示节点vi的最大流通量。分簇C是G的一个子图，即C(V′,E′)哿G(V,E),V′哿V,E′哿E,Cg表示以网关vg为根节点的分簇，|Cg|表示以网关vg为根节点的分簇的节点数量。λ(i,j)表示节点vi通过单跳或多跳的方式连接到网关vj，δ(i,j)表示节点vi通过单跳或多跳与节点vj间的最短距离，Tg表示网关vg的最大流通量，S表示分簇的节点数量上限。根据以上的设定，本文研究的网络数学模型表示如下。

优化目标：

约束条件：

式（2）表示最小化网关的数量，式（3）表示MR到网关的总距离最短，式（4）表示每个非网关节点仅与1个网关节点相连，式（5）表示每个以网关节点为根的分簇节点数量不超过S，式（6）表示分簇中的MR总流通量不超过网关的最大流通量。

3 基于紧密中心性的网关部署算法

3.1 算法描述

本文将网关优化部署问题归结为线性规划问题，根据图的紧密中心性（closeness centrality）理论，提出了一种基于紧密中心性的网关部署（gateway deployment based on closeness centrality，GDCC）算法。根据图论的紧密中心性理论，紧密度是图中一个节点的中心性度量，而在网络分析中，节点的紧密度定义为节点到其他节点的总路径和的倒数，因此，如果一个节点越靠近中心，该节点到其他节点的总路径和越小。GDCC算法的设计思想是：在满足流通量或网关服务节点数量约束的子图中，以贪心算法找出图的中心节点或是靠近中心的节点，达到子图中MR到网关总路径最短的目标，从而使得MR-GW总距离最短。GDCC算法的另外一个目标则是根据网络流通量进行合理的网络划分，使之实现在满足QoS约束条件下，网关数量最小的目标。GDCC算法的步骤如下。

步骤1收集网络的信息（包括节点最大流通量、坐标等），形成Delaunay图，计算网络的总流通量，决定是否进行划分。

步骤2从左下角的节点开始进行宽度优先的节点遍历，当所遍历的节点总流通量达到网关的最大流通量或达到上限S时，形成Delaunay子图。

步骤3根据子图中的节点坐标求出图的中心点坐标，求出图中各节点到中心坐标的欧式距离，选出距离最短的3个节点，分别计算到各个节点的总距离，总距离最短的节点作为网关的部署节点。将所遍历的节点从邻接矩阵中删除。

步骤4在剩余的邻接矩阵中重复步骤2和步骤3，直到遍历所有的节点，选出所需的网关。

步骤5输出所选的网关节点坐标。

3.2 算法过程的实例说明

本节通过一个实例，说明GDCC算法的执行过程。为了简化演示过程，以下使用一个包含25个节点的网络作为一次遍历后形成的Delaunay子图，拓扑结构如图1所示。

首先计算图1网络拓扑结构的中点坐标，求出子网络中各节点到中点的欧几里德距离，得到距离最小的3个节点作为候选网关集，如图2所示。

然后算法分别计算3个候选网关到其他节点的总距离，总距离最小的节点作为最后的网关节点。经过计算，节点2到其他节点的总距离最小，则选该节点为此子网络的网关节点，如图3所示，六角星表示网关节点。

图1 遍历后得到Delaunay子图

图2 获得候选网关集

图3 完成网关部署

4 实验结果和算法性能分析

本文利用MATLAB工具对提出的算法进行仿真实验。对比分析本文的GDCC算法、Degree based GDTSP[2]算法和随机算法的实验结果，进而对GDCC算法的有效性和可行性进行评价。

在实验中，各节点按照最短路径与网关进行连接通信，节点随机均匀分布，节点间的距离近似相等，因此实验中使用MR-GW的总跳数表示MR-GW的总距离。为了方便计算，设定所有MR节点的本地流通量为单位1，网关vg的最大流通量Tg为25，此时网关的最大流通量相当于服务的节点数，即分簇节点数量的上限S也为25个。

实验一将GDCC算法与Degree based GDTSP算法进行网关数量的比较，分析两种算法在相同情况下网关数量的差异以及原因，实验结果如图4所示。

图4 网关数量与网络总节点数的关系

为了更好地进行比较实验，实验二将网络的网关节点数量限制为1个，比较GDCC算法、Degree based GDTSP算法和随机算法所得的MR-GW总跳数，实验结果如图5所示。

图5 单网关下各算法的MR-GW总跳数比较

从图5中可以看出，在网络节点较少时，3种算法得到的MR-GW总跳数几乎没有差别，这是因为此时3种算法得到的网关节点位置大致相同且节点数量较少，不同网关位置带来的总跳数的增加并不明显。随着网络节点数量增加到15个以后，GDCC算法的优势开始体现，MR-GW总跳数明显较少。这是由于Degree based GDTSP算法在多跳邻接图中选择的是邻居节点最多的节点，随着网络节点的增加，相同情况下邻居节点数量相同的节点数会增加，从这些节点中选择网关位置时则会出现所选网关位置并不总能使网络的MR-GW总跳数最小的情况，最后的结果略优于随机算法。

实验三是根据节点的位置生成Delaunay图，分别计算出GDCC算法和随机算法的网关节点位置，考察两个算法的MR-GW总跳数变化情况，实验结果如图6所示。从图6中可以看出，当节点数量增加时，GDCC算法的MR-GW总跳数小于随机算法，而且随着节点数量的增加，这种差距变得更为明显，因此在最小化MR-GW总跳数上，GDCC算法通过计算选取的网关节点比随机网关节点更有优势。

不同的网关最大流通量对MR-GW总跳数也有一定的影响。实验三主要是研究分析网关最大流通量与MR-GW总跳数的关系。在实验中，假定实验骨干网包含100个节点，网络拓扑结构保持不变，实验结果如图7所示。从图7中可以看出，在网络节点数量和拓扑结构相同的情况下，随着网关vg最大流通量Tg的增大，MR-GW总跳数也随之增加。原因在于GDCC算法从网关的最大流通量Tg出发，以Tg限制分簇节点数量，当Tg较小时，分簇内的节点数量较少，以网关为根的分簇数量增加，使得MR-GW总跳数减少；当Tg增大时，分簇内的节点数增加，以网关为根的分簇数量减少，使得MR-GW总跳数增加。另外，图6中显示，当Tg从25增加到30时，MR-GW的总跳数却没有明显增加，原因在于GDCC算法从网关的最大流通量Tg出发对网络进行划分，将网关的数量控制为 ，这是在网关的负载能力之内能满足用户需求的最小网关数量，因此，当Tg分别为25和30时，网关数量皆为4个，MR-GW总跳数没有明显增加。

图6 不同节点数量对MR-GW总跳数的影响

图7 不同的网关最大流通量对MR-GW总跳数的影响

综上所述，GDCC算法依据网关最大流通量的不同对网络进行合理划分，在一定的QoS约束下，保证在网关的负载能力之内满足用户的需求，获得最少的网关数量，同时MR-GW的总距离最短。

5 结束语

本文研究定向天线下无线mesh骨干网络的网关部署问题，将Delaunay图应用于网关部署中，提出了基于中心性理论的无线mesh骨干网络网关部署算法GDCC。该算法先根据网络流通量进行网络划分，再利用图的紧密中心性理论，找出到各节点总距离最短的网关节点。仿真实验结果表明，在一定的QoS约束下，GDCC算法得到的网关数量最少，MR-GW总距离最短。

下一步工作是研究整个无线mesh网络的优化部署，通过限制每个节点的度来简化网络的拓扑结构，在保持网络连通性的前提下，减少定向天线的使用数量，进一步降低网络的部署费用。

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～1275

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 multichannel 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,Japan,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