无线M esh网络中骨干节点部署算法研究

凌 权，李枚毅

（湘潭大学信息工程学院，湖南湘潭411105）

无线M esh网络中骨干节点部署算法研究

凌 权，李枚毅

（湘潭大学信息工程学院，湖南湘潭411105）

无线Mesh网络是下一代无线网络的关键技术，其骨干网络的拓扑结构是实现网络连接和网络覆盖率的决定性因素。针对无线Mesh网络骨干网络的部署优化问题，在满足用户带宽需求和网络连接的前提下，以最小化M esh路由器（MR）数量为目标提出一种有效的MR部署算法。使用粒子群算法确定网关的位置，之后不断往骨干网络添加权重最大的相邻节点直至覆盖所有需求。实验结果表明，该算法在均匀分布和正态分布场景下所部署MR的数量均少于NF-Greedy和ILSearch算法，能有效减少部署成本。

无线Mesh网络；Mesh路由器部署；骨干节点；贪心算法；启发式算法；粒子群

1 概述

随着互联网的普及，无线Mesh网络作为一个高性能、低成本的宽带互联网接入解决方案，吸引了越来越多的人关注［1］。无线Mesh网络（Wireless Mesh Network，WMN）［2］是一种动态自组织和自配置的多跳无线网络，其带宽高、可靠性好、覆盖范围广、部署成本低、可扩展性好，具有较好的发展前景。

无线M esh网络基础框架由3个不同类型的节点组成：M esh路由器（M esh Router，MR），网关（M esh Gatew ay，MG）以及M esh终端（Mesh Client，MC）。在WMN中，MR给其覆盖范围内的M esh终端提供互联网访问，并以多跳的方式转发网络中其他Mesh路由器的数据到网关；MG是一种特殊的MR，它不仅具有MR的所有功能，还是连接WMN和Internet的桥梁，MG通过有线的方式与Internet连接，WMN网络中的所有节点通过MG与Internet通信；M esh终端通常笔记本电脑、移动电话和其他无线设备，其通过MC连接到Internet。

WMN的核心部分是骨干网络，骨干网络由MR和MG组成，WMN的性能主要由骨干网络的拓扑结构（MR和MG的地理位置）所决定，合理的网络部署方案可以在满足用户流量需求和网络连通性（任何一个M esh路由器都能通过一个或多个多跳网络连接到网关）的前提下，有效提高网络性能，减少部署费用（部署节点个数最小）。关于WMN骨干网络的部署优化是当前的研究热点，Mesh路由器是骨干网络的重要组成部分，M esh路由器的部署合理性对提高WMN网络性能具有重要意义。M esh路由器的部署问题与设施选址问题和覆盖集问题一样都属于NP-hard问题，目前已有很多学者针对M esh路由器的部署优化问题提出了许多解决算法［3-6］，但是还存在如下问题：（1）不能完全满足某些约束条件，如用户带宽需求；（2）分开考虑了MR和MG的部署优化问题。因此，本文以无线Mesh骨干网络部署为研究背景，以满足用户带宽需求和MR接入容量为前提，将覆盖和连通相结合进行考虑，研究如何部署MR和MG。

2 相关工作

文献［7］使用模拟退火算法（Simulated Annealing，SA）和遗传算法（Genetic A lgorithm，GA）进行求解，实验结果表明SA在覆盖方面有很好的表现，但是部署的节点数量比较多；而GA部署节点数量比较少，但在大多数情况下不能完全覆盖所有需求。文献［8］给出了一种动态环境下的Mesh路由部署方法。针对这种场景，他们以最大化网络连接和客户覆盖为目标，提出了一种粒子群优化方法，该方法允许Mesh路由器在连续的区域高度灵活的放置在移动位置。文献［9］提出一种启发式部署算法ILSearch，通过添加节点先满足网络的覆盖性，然后满足网络的连通性。文献［10］提出了一种基于网络流的MR部署贪心算法NFGreedy。该算法在满足网络连通和覆盖的前提下以最小化节点数量为目标，按照贪心策略，以迭代的方式进行MR选择，直到网络能够满足所有用户的带宽需求。每次迭代首先计算可部署MRC的权重值；然后从其中选择权重值（节点可覆盖的流量）最大的节点，使其扩展路径中的所有节点成为MR。最后对可部署MR候选位置集合及其扩展路径进行更新，除去一些不再符合部署条件的MR。

MR部署优化是具有NP-hard难度的问题，其问题的求解复杂度随着问题规模的增加而成几何倍数增长，在一定的花费内很难求出问题的最优解，因此，学者们尝试引入各种方法进行求解。如上所述，目前针对MR部署优化问题的算法主要分为2类：（1）基于数学模型的优化方法［5］，如数学规划法；（2）基于智能算法的优化方法［3-4，6，11］，如启发式算法、遗传算法和模拟退火算法等。使用常规算法进行求解具有求解精度高、运行结果好等优点，但其计算复杂度高，对较大规模的问题无法求出可行解。基于智能算法的优化方法是目前研究的热点，智能算法是一种全局搜索算法，具有很好的全局优化能力，但其容易陷入局部最优。文献［10］提出的基于网络流的MR部署贪心算法在保证网络连通和需求覆盖的前提下，考虑了MR接入带宽等约束条件，部署结果比以往算法有很大提高，但该算法还有以下不足：（1）算法是在假定网关已部署的前提下研究如何部署MR，而网关位置与MR位置是相互影响、密切关联；（2）该算法通过添加可覆盖流量最大的节点扩展骨干网络以满足需求覆盖约束，在部署前期性能很好，但是在后期可能会产生大量的零碎流量，导致部署MR的数量增加。因此，本文在该算法的模型基础上，使用粒子群算法对网关位置优化，并使用启发策略减少零碎流量的产生。

3 问题描述及模型

MR部署问题可以简化为在二维平面上的MR部署问题，假设在开始阶段已经选择了足够多的可部署MR的位置，并已把连续的用户需求离散化成需求点［7］。本文借鉴文献［10］所建立的数学模型并加以改进。

3.1 相关定义与符号说明

无线M esh网络对应着一个复杂的网络拓扑图，该拓扑图可以用G（V，E）表示，V=｛v1，v2，…，vn｝表示网络中的路由器节点和网关节点，其中网关数量为L；邻接矩阵E=｛ei，j|i，j∈｛1，2，…，n｝｝表示节点之间的关系，假设每一个节点的通信半径都相等且为Rt，则当拓扑图中的两节点i与j之间的距离小于节点之间的通信半径Rt时，即dist（vi，vj）≤Rt，eij= 1，否则eij=0。

在拓扑图中路由节点通过一跳或者多跳的方式连接到网关，但是每增加一跳都会大大的降低通信时延。为了保证服务质量，限制骨干节点到网关的最大跳数为H。

假设骨干节点采用多频通信技术，即骨干节点之间的通信和对覆盖范围内的终端所提供的服务采用不同的频率互不干扰，骨干节点还具有以下属性：

Rc：节点覆盖范围，是指以节点为中心的圆形区域，该节点可以对在这个范围内的终端提供服务。

Rt：节点通信半径，是指以节点为中心的圆形区域，该节点可以与在这个范围内的其他节点进行通信。

Cap：节点接入容量，是指节点能提供的最大接入带宽。

根据上述定义，该问题可以描述为给定MRC集合C、UDN集合U和网关数量L，在满足所有UDN带宽需求、保证所有MR到网关的连通性和骨干节点实际接入流量小于最大接入流量的前提下，从MRC中选择最少数量的节点作为MR，同时还要确定网关的位置。

为了更好地量化模型，下面给出一系列算法过程中需要的变量：

UDN带宽需求B=｛b1，b2，…，bm｝，bj表示第j个带宽需求点的带宽需求值。其中，m表示需求点的数量。

网关Gw=｛g1，g2，…，gn｝，gi=1表示候选位置ci被选做网关，gi=0表示ci没有被选做网关，n为MRC个数。

已部署MRC X=｛x1，x2，…，xn｝，表示已部署的MR集合，xi=1表示在MRC集合中的vi点放置MR；xi=0表示MRC集合中的vi点没有放置MR，n为MRC个数。

节点剩余带宽R=｛r1，r2，…，rn｝，表示已放置的节点可分配的带宽集合，其初始值为Cap。

节点最小跳数H=｛h1，h2，…，hn｝，表示骨干节点到网关的最小跳数，n为MRC个数。

3.2 数学模型

按照3.1节说明，该问题的数学模型如下：优化目标：

优化目标函数式（1）计算布置WMN骨干网络需要的MR的数量。约束条件式（2）和约束条件式（3）表明只有当该节点能够连接到网关和该节点覆盖范围内存在UDN，该节点才会被选作MR。条件式（4）和条件式（5）表明某个UDN被MRC承担，当且只当该MRC已被选择部署MR且该UDN在该MRC覆盖范围内。条件式（6）表明所有的用户带宽需求都必须被满足。条件式（7）表明每个节点承担的UDN之和不能超过其接入容量Cap。条件式（8）表明每个节点到达网关的最小跳数不能超过H。条件式（9）～条件式（11）表明节点i和j都被选作MR且两者之间的距离小于通信距离是节点k通过该路径连接到网关的前提。条件式（12）～条件式（15）给出了节点k存在多跳MR路径到达网关所需要满足的条件。

4 MR部署算法

MR部署算法的基本设计思想如下：在确定网关的位置之后，然后使用迭代的方式从可部署MRC集合中选择节点的添加到骨干网络集合并更新部署状态直到每一个UDN的带宽需求都被满足。

4.1 节点选择

上述部署算法最关键的问题是如何从可部署MRC中选择节点部署MR，其具体过程如下：在每次迭代的过程中，从剩余MRC集合中（未部署MR的候选位置）筛选出现有骨干网络的相邻候选位置，按照可覆盖流量最大、实际覆盖半径最小的优先法则选择节点添加到骨干网络；若当前网络不存在相邻候选位置，则按照上述优先法则添加满足符合条件的路径到骨干网络。该方法能有效避免产生零碎流量，减少部署节点的个数。如图1所示，节点vi和vj是已经部署的MR，编号为1～9的候选节点是当前部署状态下的相邻候选位置，圆表示节点的实际覆盖半径，假设MR的接入容量为54 M b/s，每个用户需求点的需求值为25 M b/s，显然编号为1，4，6，8的节点其最大覆盖流量为节点接入流量，而其他节点的最大覆盖流量小于节点接入流量，在确定下一个放置位置时，优先选择可覆盖流量最大的节点，若有几个节点的最大覆盖流量相等且都为最大值，则从这些节点中选择实际覆盖半径最小节点。因此，从1，4，6，8节点中选择节点1添加到网络。

图1 节点选择示意图

定义3 实际覆盖半径是指节点与其最远能够提供接入服务的UDN之间的距离，若节点vi的节点覆盖范围Rc内的UDN带宽需求总和小于等于节点剩余带宽ri时，实际覆盖半径为Rc；若节点vi的节点覆盖半径Rc内的UDN带宽需求总和大于节点剩余带宽ri时，实际覆盖半径为dist（vi，uk），其中uk满足把节点可覆盖需求表中节点vi所在行按从小到大排序，cur-b为节点uk前面所有节点的流量和，cur-b≤ri且cur-b+bk＞ri。

定义4 相邻候选位置是指距离骨干网络跳数为1且与骨干网络中间不存在未覆盖用户需求点的可部署候选位置。相邻候选位置存在2种情况，如图2所示。已部署节点vi是在骨干网络中与可部署节点vj距离最近的节点，Ri和Rj是节点vi和vj的实际覆盖半径，若2个节点实际覆盖半径有叠加，即dist（vi，vj）≤Ri+Rj，则vj称为相邻候选节点，如图2（a）所示；若2个节点实际覆盖范围没有叠加但是其连接线vivj的邻域Ω内不存在未覆盖UDN，则vj称为相邻候选节点，本文取邻域宽度ε=m in（Ri，Rj）/2，如图2（b）所示。

图2 相邻候选位置示意图

4.2 算法步骤

为提高算法运行效率，本文采用十字链表存储数据，算法步骤如下：

（1）初始化已部署MR、已覆盖UDN和其他放置变量，根据UDN和MRC的坐标计算需求覆盖表，更新网关集合。

（2）更新已部署MR、已覆盖UDN和需求关联表，计算当前网络可满足的最大带宽需求，判断当前网络可满足流量是否等于总流量，如等于则转步骤（5）。

（3）计算节点剩余带宽、已部署MR到网关的最小跳数并更新骨干层节点最短路径，更新节点可覆盖需求表，根据4.1节所述方法更新可用MRC集合。

（4）从相邻MRC集合中选择一个权重最大的节点添加到已部署路由节点集中，若不存在可用的相邻MRC，择选择权重最大的路径，转步骤（2）。

（5）评估部署结果，算法结束。

4.3 算法分析

在算法初始化阶段，需要构建覆盖关系矩阵，时间复杂度为O（nm）；需要构建候选节点之间连接关系的无向图，时间复杂度为O（n2）；需计算UDN到MRC的距离，时间复杂度为O（nm）；还需要初始化MRC的扩展路径，时间复杂度为O（n2）。在放置节点阶段，每次放置分为2个阶段：（1）选择节点，其时间复杂度为O（n2）；（2）更新流量及覆盖信息，时间复杂度为O（nm）。由于每一次放置都会去掉一个节点，因此放置最多执行n次。综上，算法的时间复杂度为O（2nm+2n2+n（n2+nm）），即O（n2m）。

5 基于离散粒子群的网关优化部署算法

上一节所述的MR部署算法是在预先确定网关的前提下进行部署的，但是网关位置与MR位置是相互影响、密切关联的。

5.1 粒子群算法

粒子群算法是文献［12］提出的一种进化优化算法，其思想是对鸟群和鱼群的模拟。粒子群算法一个并行算法，能够模拟粒子群体在解空间搜索极值的各种飞行状态。由于基本粒子群优化算法主要针对连续函数进行搜索计算，但许多实际工程问题都描述为离散的组合优化问题，为此Kennedy和Eberhart于1997年提出了一种离散二进制粒子群优化算法（Binary Particle Swarm Optim ization，BPSO）。BPSO算法具有很强全局搜索能力且由于其搜索空间的二进制特性该算法适合求解只包含2种状态的问题。BPSO的粒子搜索空间是D维的二进制空间，记为BD，PopSize个粒子在D维的目标空间进行搜索，为了将粒子群优化算法用于离散变量优化，将该算法中每个粒子的位置矢量属于二进制空间（由0和1组成的二进制字符串），记为Z=［z1，z2，…，zD］，其中，zi为0或1，但是其速度矢量仍然属于实数空间RD，即有v∈［-vmax，vmax］。这样，算法可以保留基本粒子群算法中的速度公式，而只对其位置更新公式进行修改得到，每个粒子的速度和位置更新公式为：

其中，i=1，2，…，PopSize；d=1，2，…，D；k是迭代次数；ρ，r1，r2是［0，1］之间的随机数；w为惯性因子；c1，c2为学习因子。由式（17）可知，vk+1i越靠近vmax，候选位置ci被选作网关的可能性越大。

5.2 网关优化部署算法

一个由PopSize个粒子组成的粒子群，在D维二进制空间搜索极值，第i个例子表示为，其中，zj为0或1，在网关部署问题中，zj=1表示第j个候选位置被选作网关，粒子根据历史最优解和全局最优解不断修正搜索位置，从而获得最优解。

按照式（16）和式（17）更新计算速度和位置，产生的结果可能会不满足网关数量的约束，为此做一点改进，更新位置的时候按照位置稳定性进行排序，从最不稳定的候选位置i开始更新，若位置状态改变，则从序列中删除该候选位置；否则跳过该候选位置；然后重复上面的操作，直到网关数量满足条件要求为止，本文取vmax=4，w=0.25，c1=0.4，c2= 0.6。粒子适度值根据式（19）计算：

算法步骤如下：

（1）随机产生规模为PopSize的粒子群，初始化离散粒子的位置和速度。

（2）根据第4节所述的MR部署算法放置MR，根据式（19）计算粒子群适度值。

（3）若有更好的适度值，更新历史最佳位置和全局最佳位置。

（4）根据式（16）更新粒子的速度和位置。

（5）判断是否达到最大迭代次数或输出结果满足要求，否则转步骤（2）。

（6）输出粒子群最优结果（网关和MR位置及数量）。

6 实验与结果分析

本文实验在Visual Studio 2012开发环境中采用VC++编码，其硬件环境是Intel酷睿i3 3220 3.3 GHz，4 GB DDR3，操作系统为W indows 7 Ultimate。

本文依据麻省理工学院（M IT）搭建的Roofnet实验网络平台设置实验参数，取节点覆盖范围Rc为150 m，节点通信半径Rt为250 m，节点接入容量Cap为54 M b/s，骨干节点到网关的最大跳数H为4跳。在实际场景中人口群落的分布并非均匀分布而更接近正态分布，本文模拟现实人口分布产生符合正态分布的用户需求点集，然后在该正态分布的包罗圆内随机产生MR候选位置。

在不同的部署场景下测试本文算法与现有部署算法ILSearch［9］和NF-Greedy［10］的优化效果，部署场景包括场景大小、MRC数量、网关数量和UDN数量4个因素，实验设定UDN的带宽需求值为10 M b/s，其部署场景为（200 m×200 m，10，1，15），（300 m× 300 m，20，1，25），（400 m×400 m，40，2，45），（600 m× 600 m，80，3，80），（800 m×800 m，150，4，110），（1 000 m×1 000 m，200，8，140），（1 500 m×1 500，300，12，120）、（2 000 m×2 000 m，450，16，360）。表1给出了3种算法在不同部署场景下部署MR个数的平均值，从中可以看出，当部署规模较小的时本文算法能找到最佳部署方案，当规模较大时部署MR的数量远小于ILSearch算法，比NF-Greedy算法部署的MR数量少8%左右。

表1 3种算法在正态分布场景下的部署结果

表2给出了3种算法在均匀分布场景下部署MR的个数。

表2 3种算法在均匀分布场景下的部署结果

通过上述实验结果可以得知，本文算法不论是在均匀分布或者正态分布情况下，部署的MR个数均少于ILSearch算法和NF-Greedy算法，证明了本文算法的有效性。

7 结束语

为解决无线M esh网络中决定网络性能的骨干网络部署优化问题，本文提出一种网关与M esh路由器同时部署的优化算法，使用二进制离散粒子群算法优化网关位置，在满足用户带宽需求和网络连通性的前提下，利用启发策略迭代扩展骨干网络，直到所有带宽需求都被满足，根据部署MR的数量评估网关布置结果。实验结果表明，该算法部署MR的数量少于NF-Greedy和ILSearch算法。

无线Mesh网络是一种新兴的无线网络结构，具有很好的发展前途，但是关于无线Mesh网络优化问题的研究才刚刚起步。本文使用启发算法结合粒子群算法部署MR，启发算法不具备全局搜索能力，其部署结果可能是局部最优，使用的粒子群算法也有改进的空间。此外，本文算法没有考虑到无线网络的可靠性以及节点之间的干扰。因此，下一步工作计划使用智能算法优化MR部署问题。

［1］ Rezgui J，Hafid A，Gendreau M.Distributed Admission Control in Wireless Mesh Networks：Models，Algorithm s，and Evaluation［J］.IEEE Transactions on Vehicular Technology，2010，59（3）：1459-1473.

［2］ Benyam ina D，Hafid A，Gendreau M.Wireless Mesh Networks Design——A Survey［J］.IEEE Communications Surveys&Tutorials，2012，14（2）：299-310.

［3］ 黄书强，王高才，单志广，等.智慧城市中无线网络节点部署优化方案研究［J］.计算机研究与发展，2014，51（2）：278-289.

［4］ Xhafa F，Sanchez C，Barolli L.Ad Hoc and Neighborhood Search Methods for Placement of Mesh Routers in Wireless Mesh Networks［C］//Proceedings of the 29th IEEE International Conference on Distributed Computing System s Workshops.Montreal，Canada：IEEE Press，2009：400-405.

［5］ Xhafa F，Sánchez C，Barolli L.Local Search Methods for Efficient Router Nodes Placement in Wireless Mesh Networks［J］.Journal of Intelligent Manufacturing，2012，23（4）：1293-1303.

［6］ Wang Junfang，Xie Bin，Cai Kan，et al.Efficient Mesh Router Placement in Wireless Mesh Networks［C］// Proceedings of IEEE Internatonal Conference on Mobile Adhoc and Sensor Systems.Pisa，Italy：IEEE Press，2007：1-9.

［7］ Sakam oto S，Kulla E，Oda T，et al.A Comparison Study of Simulated Annealing and Genetic Algorithm for Node Placement Problem in Wireless Mesh Networks［J］. Journal of Mobile Multimedia，2013，9（1/2）：101-110.

［8］ Lin Chuncheng.Dynam ic Router Node Placement in Wireless Mesh Networks：A PSO Approach with Constriction Coefficient and Its Convergence Analysis［J］. Information Sciences，2013，232：294-308.

［9］ Wang Junfang，Cai Kan，Agrawal D R.A Multi-rate Based Router Placement Scheme for Wireless Mesh Networks［C］//Proceedings of the 6th IEEE International Conference on Mobile Adhoc and Sensor System s. Washington D.C.，USA：IEEE Press，2009：100-109.

［10］ 吴文甲，杨 明，罗 军.无线M esh网络中满足带宽需求的路由器部署方法［J］.计算机学报，2014，37（2）：344-355.

［11］ Xhafa F，Sánchez C，Barolli L.Genetic Algorithm s for Efficient Placement of Router Nodes in Wireless Mesh Networks［C］//Proceedings of the 24th IEEE International Conference on Advanced Information Networking and Applications.Perth，Australia：IEEE Press，2010：465-472.

［12］ Kennedy J，Eberhart R.Particle Swarm Optimization［C］// Proceedings of IEEE International Conference on Neural Networks.Perth，Australia：IEEE Press，1995：1942-1948.

编辑 金胡考

Research on Backbone Nodes Deployment Algorithm in Wireless Mesh Network

LING Quan，LI Meiyi
（College of Information Engineering，Xiangtan University，Xiangtan 411105，China）

Wireless Mesh Network（WMN）is a key technology of new generation Wireless networks，and the structure of the backbone network is a decisive factor in achieving the connectivity and coverage of the network.Aiming at optimizing the deployment of WMN's backbone network，an effective Mesh Router（MR）deployment algorithm for minimizing the number of MR under the premise of network connection and meeting the user's demand of the bandwidth is proposed.Particle swarm algorithm is used to determine the location of the gateway.Then it adds nodes to the backbone network constantly until covers all requirements.Experimental results prove that the number of MR deployed of the proposed algorithm is less than NF-Greedy algorithm and ILSearch algorithm under uniform distribution and normal distribution，it can reduce the deployment cost effectively.

Wireless Mesh Network（WMN）；Mesh Router（MR）deployment；backbone node；greedy algorithm；heuristic algorithm；particle swarm

凌 权，李枚毅.无线Mesh网络中骨干节点部署算法研究［J］.计算机工程，2015，41（11）：147-152.

英文引用格式：Ling Quan，Li Meiyi.Research on Backbone Nodes Deployment Algorithm in Wireless Mesh Network［J］. Computer Engineering，2015，41（11）：147-152.

1000-3428（2015）11-0147-06

A

TP393

10.3969/j.issn.1000-3428.2015.11.026

凌 权（1990-），男，硕士，主研方向：移动互联网，智能计算；李枚毅，教授、博士。

2014-09-17

2014-12-12 E-m ail：lingquan-1990@126.com