无线mesh网中费用最小且QoS约束的网关部署算法研究.doc

第6期曾锋等：无线mesh网中费用最小且QoS约束的网关部署算法研究89无线mesh网中费用最小且QoS约束的网关部署算法研究曾锋，陈志刚，邓晓衡(中南大学 信息科学与工程学院，湖南 长沙 410083)摘 要：基于图的支配集理论，提出图的有限支配集的概念应用于满足QoS约束的无线mesh网网关优化部署，以获取费用最小网关部署方案，进而把QoS约束的费用最小网关部署问题归结为图的最小权有限支配集的问题。为求解图的最小权有限支配集，提出了贪婪算法GREEDY_LDS，该算法以网关的部署性价比作为启发信息，依次挑选部署性价比高的节点加入有限支配集，最后得到权值较小的有限支配集；为得到更加优化的解，利用粒子群优化算法的全局寻优优势，提出粒子群优化算法PSO_LDS，该算法通过阻止粒子在狭小区域运动来防止算法陷入早熟收敛。模拟实验表明，GREEDY_LDS算法执行速度快，当网关候选节点数超过总节点数的17%时，能得到比其他算法更好的结果；PSO_LDS算法以增加执行时间为代价，与GREEDY_LDS和OPEN/CLOSE算法相比，得到的网关部署方案的费用分别减少约15%和9%。关键词：无线mesh网；网关部署；QoS；支配集；贪婪算法；粒子群优化算法中图分类号：TP393 文献标识码：B 文章编号：1000-436X(2009)06-0080-09Minimum-cost gateway placement in wireless mesh networks with QoS constraintsZENG Feng, CHEN Zhi-gang, DENG Xiao-heng (School of Information Science and Engineering, Central South University, Changsha 410083, China)Abstract: Focusing on gateway optimal placement with QoS constraints in WMNs and aiming to minimize the cost of gateway placement, firstly, a new concept of limited dominating set (LDS) in graph was presented to addresses the gateway placement problem, and to find the solution of minimum placement cost is to find the LDS of minimum weight in the graph. Then, in order to find the minimum weighted LDS in graph, a greedy algorithm GREEDY_LDS was proposed, in which the ratio of LOAD/COST was used as heuristic information to find minimum cost placement of gateway. To get further optimal solution, a particle swarm optimization algorithm PSO_LDS was proposed, in which two premature avoidance methods were presented to improve the algorithms ability of searching for global optimal solution. At last, simulation has been done, and experiment result shows that GREEDY_LDS has lower computing complexity, and when the number of gateway candidate is more than 17% of the total number of node, the result from GREEDY_LDS is better than the others. Simulation also shows that PSO_LDS can get the more optimal solution at the price of increasing of executing time. Compared with GREEDY_LDS and OPEN/CLOSE, the average cost of gateway placement is decreased by about 15% and 9% respectively.收稿日期：2008-05-27；修回日期：2009-03-10基金项目：国家自然科学基金资助项目(60873082)；中国博士后科学基金资助项目(20060400879)；湖南省教育厅资助项目(08C510)Foundation Items: The National Natural Science Foundation of China (60873082); The Research Foundation for Postdoctors in China (20060400879); The Scientific Research Fund of Hunan Provincial Education Department (08C510)Key words: wireless mesh network; gateway placement; QoS; dominating set; greedy algorithm; particle swarm optimization 1 引言无线mesh网（WMN, wireless mesh networks）是重要的无线宽带接入技术，具有自组织、易于维护、覆盖范围大、网络可扩展性好、成本低等优点，是Internet“最后一公里”延伸的重要选择1。无线mesh网是多跳传输网络，其中有3种类型的节点： 网关、mesh路由器和mesh终端。网关不仅具有mesh路由器的功能，而且与Internet直接通过有线电缆相连，是无线mesh网与Internet连通的桥梁。所有mesh路由器和网关节点构成了WMN的骨干网， mesh终端用户的数据经由mesh路由器的多跳传输到达网关，再通过网关的转发实现终端的Internet访问。图1为无线mesh网络的一种典型拓扑结构。如图中所示，无线mesh网拓扑结构分成3个层次：Internet接入层、mesh网骨干层和终端接入层。mesh网骨干层由网关和mesh路由器组成，是影响终端用户网络服务质量的关键。图1 无线mesh网络拓扑结构图1无线mesh网的显著特点表现在2个方面：1)网络中大部分流量汇聚于网关，网关常常成为网络性能的瓶颈2；2)离网关较近的节点能得到较好的服务质量，较远的节点得到的服务质量较差，各节点间存在服务质量的不公平性35。基于上述特点，本文关注mesh骨干层的设计，研究如何合理部署网关节点以提升网络性能和保证网络QoS。网关部署的合理与否是网络性能好坏的重要因素。在WMN中，网关节点越多其性能越好，但是成本也越高。因此，在部署网关节点的同时，应该考虑网络的建设成本。网关部署问题就是在给定的节点中，选择少量的节点作为网关，通过这些网关能为所有终端用户提供QoS保证的服务。在以前的WMN网关部署研究中，学者们把网关部署问题归结为为线性规划优化问题，并针对不同的约束条件提出网关部署算法。Wong6等人提出了最小化通信时延和最小化通信代价的2个独立的网关部署问题，并对这两个问题分别提出基于统计方法的启发式算法，算法的主要思想是每一步去掉不适合部署网关的点，最后达到问题的优化。Chandra7等人在保证各个节点带宽要求的前提下，试图最小化网关的数量，并提出贪婪算法来实现它的目标，但是由于该算法每一次迭代都是让网关节点服务尽可能多的节点，可能会导致网关节点负载的不平衡。Bejerano8和Aoun9等人也把网关部署问题转化为线性规划优化问题，并采用分簇的思想，提出不同的贪婪算法来构造满足QoS约束的网关数量最少的部署方案。He10和Prasad11等人同样把网关部署问题化为线性规划问题，并提出不同的启发式算法求费用最小的网关部署方案。Li12等人研究吞吐量优化的网关部署问题，提出了基于网格拓扑结构的网关部署方案，并使用跨层设计的方法来优化吞吐量。上述大部分网关部署算法都试图在保证QoS的条件下，尽可能地减少网关数量，或者优化某一项QoS性能。但是，在不同的地理位置和网络拓扑环境中，部署网关的费用是不同的，网关数量少不一定就是网关部署的费用小，QoS性能的提升也增加了网关部署的成本。本文在分析上述算法的基础上，研究满足QoS约束的网关部署问题，并以最小化网关部署费用为目标。与之前的研究不同的是，本文基于网关部署问题与图的支配集问题的异同性，提出图的有限支配集的概念，并把网关部署问题归结为图的最小权有限支配集问题，同时，设计贪婪算法和粒子群算法来求解满足QoS条件的费用最小的网关部署方案。2 网络模型及问题描述网关部署问题与图的支配集问题有相似性，但也有很多不同点，不能直接把图的支配集理论应用于网关部署问题。为此，本文建立满足QoS条件的网关部署问题的模型，并提出图的有限支配集的概念，以支持该问题。2.1 网络模型本文用无向图G(V, E)来表示WMN骨干网。V为图的节点集，节点总数为N，由2部分组成，即V=SM，S为n个网关候选节点的集合，M为Nn个mesh路由器节点集合。V中的每一个节点都有一个传输范围，在该传输范围内的节点都可与其直接通信，对任意的节点uV，如果存在节点v在其传输范围内，则有(u, v)E，边(u, v)为节点u和v之间的双向传输链路。对任意两节点sS和tS，由于都为网关候选节点，在现实中不可能相邻，因此，图G中s与t之间不存在边。集合S中的节点都可以通过有线电缆与Internet直接相连，都可部署为网关节点，但是各个节点部署为网关的费用可能是不一样的。对任给的节点vS，定义Cost(v)为该节点部署为网关节点的费用；而且，各个网关节点的性能是有限的，定义Cap(v)为网关节点v的最大负载量（容量）。集合M中的节点为普通的路由器的节点，主要作用是汇聚终端流量和转发其他mesh路由器流量，对任一节点uM，定义W(u)来表示mesh路由器u所汇集的终端流量。在WMN中，mesh路由器汇聚的流量经多跳传输到达网关，最后通过网关实现Internet访问。为节约WMN建设成本，网关部署的费用应尽可能小。因此，网关部署问题就是从网关候选节点集合S中，选择k(kn)个节点构成部署费用最小的网关集合GW=g1, g2, gk()，并且要求GW中的网关节点能为M中的所有节点提供满足QoS要求的服务。对任意网关节点giGW，定义其负载为L(gi)。图2为网关部署示例。图2 无线mesh网网关部署其中，S=S1, S2, S3为网关候选节点集合，节点旁标明的是网关部署费用和最大负载值，如S1的部署费用为3，最大负载为35；M=M1, M2, M3, M4, M5, M6, M7, M8, M9, M10为mesh路由器节点，节点旁边标明的数值为其汇聚流量；该例中，S1和S3部署为网关节点，即GW=S1, S3，网关部署费用为10，S1承担的负载为L(S1)=32，S3承担的负载为L(S3)=53。在部署网关时，还应该考虑网关与mesh路由器之间端到端的QoS因素，本文通过构造网关为根的路由分发树来讨论其中的QoS。2.2 网关为根的QoS约束路由树为考虑网关与mesh路由器之间端到端的QoS保证，以网关候选节点为根建立满足以下条件的路由树：1) 路由树中的所有非根节点的汇聚流量之和不能超过根（网关）节点的最大负载能力；2) 路由树中的所有节点到根的距离（跳数）不能超过上限R；3) 路由树中的任一节点的转发流量不能超过上限T；4) 路由树中的任一节点的度不能超过上限D；5) 路由树中的节点总数不能超过上限S。网关与mesh路由器之间通过路由树实现数据的分发，以上五条件保证了网关为路由树中的mesh路由器提供满足QoS条件的服务。条件1)保证了网关负载在其承受能力范围内；条件2)一定程度上保证了端到端的时延；条件3)保证了路由中中间节点提供的服务质量；条件4)和5)限制了节点密度，对缓解节点周围的介质竞争有一定帮助。在构造路由树时，上述条件（参数R，T，D，S）越严格，得到的路由树能实现的服务质量就越好，但是，需要部署的网关节点也越多。因此，参数R，T，D，S的选取需视实际情况而定，如要求较低的通信时延，则参数R应取较小值。本文通过对网络图从各网关候选节点出发进行广度优先遍历，并考虑上述条件，来构造路由树，由于不是本文重点，在此不做详述。图2中各网关候选节点为根建立的路由树如图3所示（R=2，T=15，D=3，S=8）。其中，网关节点标明的是（费用，容量，负载），mesh路由器节点标明的是（汇聚流量，转发流量），各路由树网关负载不能大于其容量；树中节点到根的距离不大于2跳；各节点转发流量不大于15；各节点的度不大于3；路由树节点总数不大于8。图3 网关为根的路由树路由树由一个网关候选节点和若干mesh路由器节点组成，这些mesh路由器节点构成了该网关侯选节点的覆盖集。根据构建的路由树，任一mesh路由器可找到至少一个能为其提供QoS保证的网关侯选节点，因此，可以构建出无线mesh网中网关与mesh路由器之间的QoS约束关系图（QoS约束图）。2.3 QoS约束图定义图G (V, E)为无线mesh网络图G(V, E)的QoS约束图，其中V=V= SM；如果mesh路由器u被以网关v为根构造的路由树覆盖，则(u, v)E。例如，图2的QoS约束图如图4所示。图4 QoS约束图QoS约束图简化了mesh路由器与网关侯选节点之间的QoS因素，只要mesh路由器与网关节点之间存在一条满足QoS要求的端到端链路，即mesh路由器节点被网关为根的路由树覆盖，QoS约束图中两节点间就存在一条边。在QoS约束图的基础上，下文提出有限支配集的概念用于描述费用最小的网关部署问题。2.4 有限支配集与问题描述定义1 图的支配集13(dominating set)对任意的简单无向图G(V, E)，其中，V为节点集，E为边集，若找到一个节点子集 ()，且G中的任何节点要么属于DS，要么与DS中的一节点相邻，则称节点集合DS为图G的支配集。定义2 图的有限支配集（limited dominating set）对图G(V, E)，V= SM，S为网关候选节点集，M为mesh路由器节点集，若找到一个子集，且对M中的任意节点u，都存在一节点vGW与u相邻，即(u, v)E，则GW为图G的有限支配集。定义3 最小权有限支配集对任一节点vS，给定其权值为W(v)，图的有限支配集GW的权值为其中所有节点的权值之和，即W(GW)=，图G的所有有限支配集中，权值最小的一个为其最小权有限支配集。定理1 对给定的无线mesh网G(V, E)，只要满足QoS约束的网关部署方案存在，那么，网关候选节点集合S为其QoS约束图G(V, E)的一个支配集。证明 由无线mesh网存在满足QoS约束的网关部署方案可知，对集合M中的任一节点，至少存在一棵以某网关候选节点为根的路由树覆盖该节点。因此，根据2.3节构造的图G的QoS约束图G(V, E)中，对M中的任意节点u，都存在一节点vS与u相邻，即(u, v)E，又节点集V=V= SM，可见，对V中的任一节点，要么属于S，要么与S中至少一个节点相邻，根据图的支配集定义，S即为图G的一个支配集。推论1 对给定的无线mesh网G(V, E)，只要满足QoS约束的网关部署方案存在，那么，图G(V, E)至少存在一个有限支配集。证明 由定理1，集合S为图G的一个支配集，根据有限支配集的定义，S也为图G的一个有限支配集。定理2 求无线mesh网络G满足QoS约束的费用最小的网关部署方案问题即为求图G的最小权有限支配集问题。证明 如果无线mesh网络G满足QoS约束的网关部署方案存在，那么，根据定理1和推论1得出图G存在有限支配集。再根据有限支配集的定义，对M中的任一节点u，在有限支配集中至少存在一个节点v与u相邻，即链路(u, v)满足本文所讨论的QoS约束，因此，图G的有限支配集中的节点代表部署的网关节点，有限支配集代表无线mesh网络G满足QoS约束的网关部署方案。对任一节点vS，令W(v)=Cost(v)，那么图G的最小权有限支配集代表本文所研究的无线mesh网络G中费用最小的网关部署方案。可见，求本文研究的费用最小的网关部署方案即为求图G的最小权有限支配集问题。定理2得证。根据定理2，本文所研究的网关部署问题转化为求图G的最小权有限支配集问题。该问题是NP难的问题，下文将分别提出贪婪算法和粒子群算法来求图G的最小权有限支配集，以得到费用最小的网关部署方案。3 基于最小权有限支配集的网关部署算法3.1 求最小权有限支配集的贪婪算法Greedy_LDS对部署的网关而言，我们希望网关处理的流量越多越好，只要不超过它的最大负载量，同时，希望它的部署费用尽可能的小。为衡量网关的性价比，对任一网关侯选节点vS，定义其部署性价比指标p(v)如式(1)所示。其中L(v)为网关v的负载，Cost(v)为部署费用；p(v)值越大，网关v的部署性价比就越高。在贪婪算法Greedy_LDS中，根据网关候选节点的部署性价比依次选择节点部署为网关。(1)假设任一节点vS为根的路由树覆盖的mesh路由器节点集合为Mv，求图G(V, E)的最小权有限支配集贪婪算法Greedy_LDS可描述如下。其中，算法输入包括QoS约束图G、各网关覆盖集等信息，算法输出为图G的有限支配集及更新后的各网关覆盖集。1 LDS Greedy_LDS(G, S, M, Mv1, Mv2, )2 3 ST=S，GW=，C=；4 while(C != V)5 Calculate_pv(ST); /计算部署性价比6 v=Max_pv(ST); /找性价比最好的节点7 ST= STv; /把已选择的网关剔除8 GW=GW+v;/加入有限支配集9 C=C+Mv; /把网关v覆盖的节点加入集合C10 Update_CovermeshRouter(ST); /更新覆盖集11 Update_GatewayLoad(ST); /更新网关负载12 13 return GW;14 由于在算法执行前，一个mesh路由器节点可能属于多个网关覆盖集，所以，当一个mesh路由器节点确定了它的所属网关后，必须从其他网关覆盖集中剔除该节点（算法第10行）。最后算法得到部署的网关节点集和互不相交的网关覆盖集，给每个mesh路由器节点分配唯一的服务网关。 3.2 求最小权有限支配集的粒子群优化算法使用贪婪算法不容易找到全局优化的解，而粒子群算法(PSO)、遗传算法(GA)等群体智能算法具有全局搜索优化能力，经过一定次数的迭代可以找到问题最优解。与其他进化算法相比较，PSO算法简单容易实现，没有许多参数需要调整，是一种高效的并行搜索算法，它保留了基于种群的全局搜索策略，但是其采用的速度一位移模型操作简单，避免了像遗传算法中复杂的遗传操作14。本文利用PSO算法求解图的最小权有限支配集，以取得更为优化的网关部署方案。PSO算法是由Kennedy和Eberhart15, 16等于1995年开发的一种演化计算技术，来源于对鸟群捕食行为的模拟。算法中的每个粒子都有一个适应度函数所决定的适应值，都具有位置和速度2个属性，且以粒子位置坐标所对应的适应度函数值来确定粒子的好坏，并根据当前的局部最优位置(pbest)和全局最优位置(gbest)来调整粒子的速度。更多PSO算法的细节请参考文献15, 16，本文求解QoS约束图G(V, E)的最小权有限支配集的PSO算法(PSO_LDS)设计如下。1) 粒子的编码表示及其属性本文用长度为n(n=|S|)的二进制串来表示粒子，每个粒子代表图G的一个有限支配集，也表示一个网关部署方案。假设某个粒子Xi的编码表示为Xi=xi1xi2xin，也表示该粒子在运动中的位置，其中n=|S|，为候选网关数，xij0, 1，i1, 2, , L，j1, 2, , n，L为种群中的粒子总数（本文取L=20）。如果xij为“1”，表示粒子i所代表的网关部署方案中，节点j部署为网关。在PSO算法中，每个粒子都有位置和速度2个属性，它们用n维向量表示。粒子i在t时刻的位置、速度和局部最优位置向量分别用Xi(t)、Vi(t)和Pi(t)表示，xij(t)、vij(t)和pij(t)分别与它们的第j维变量对应；G(t)表示t时刻的粒子群全局最优位置，gj(t)表示其第j维变量。2) 粒子适应度函数本文研究满足QoS约束的费用最小的网关部署方案，用部署费用来衡量问题解的优劣，因此把粒子对应的网关部署费用的倒数作为它的进化适应度。对任一粒子Xi，定义其适应度函数为f(Xi)，如式(2)所示。其中n=|S|，Cost(j)为S中节点j的部署费用。粒子的适应度值越大，表示其所处的位置越好，希望找到适应度值最大的粒子位置。(2)3) 粒子位置和速度的更新公式JKennedy和Eberhart对二进制粒子群算法做了大量的研究17, 18。在他们提出的模型中将每一维xij(t)、pbij(t)和gbij(t)限制为1或者为0，速度vij(t)不做这种限制。粒子i的速度更新公式如式(3)所示，其中，w为惯性权重，c1、c2为加速常数，r1、r2为区间(0, 1)上均匀分布的随机变量。 (3)用速度来更新位置时，如果vij(t+1)的值大一些，对应维的粒子位置更有可能为1；若vij(t+1)小一点则xij(t+1)为0的概率大些，阀值在0，1之间，而具有这种特点的函数就是Sigmoid函数17，如式(4)所示。应用Sigmoid函数得到粒子位置的更新公式如式(5)所示。其中r0, 1为均匀分布的随机数。此外，粒子每一维的速度被一个最大速度vmax所限制。文献19令|vmax|=4，使得0.018Sig(vij(t+1)0.982，粒子位置将以较大概率发生变化，避免早熟收敛。本文同样令|vmax|=4。(4)(5)4) 避免早熟的措施PSO算法参数选择存在很大的复杂性，文献14研究发现PSO算法在开始阶段有很好的表现，但是当接近最优值时存在一些问题。为避免PSO算法陷入早熟收敛，本文提出2种措施。 防止粒子长时间处于狭小区域为描述粒子的运动范围，定义粒子i在时刻t，最近的时间段T中经历过的区域范围大小为R(Xi, t, T)：(6)(7)式(7)为粒子的k时刻位置与j时刻位置的距离，粒子经历过的区域范围大小为其经历过的任意2个位置距离的最大值。为限制粒子在较小的区域运动，对给定的时间段T，如果其经历过的区域范围小于一个给定的阀值e1，那么将重新初始化该粒子，如下面伪代码所示，T和e1为给定参数。算法伪代码：1 Avoidence_Method1(i, t, T, e1)2 3 /如果T时间内的运动区域小于阀值e14 /则重新初始化粒子5 if(R(Xi, t, T) e1)6 ReInitialParticle(i);7 防止粒子适应度长时间得不到优化粒子移动的目标是全局最优位置，如果粒子的适应值长时间得不到明显的优化，说明粒子陷入早熟收敛，必须进行调整。为改善这一状况，对粒子i适应值变化不大的情况进行计数，其伪代码如下：1Avoidence_Method2(i, t, count, e2, C)23for(i=1; i=n; i+)4/连续时刻粒子适应值优化不超过e2则计数5if(|fi(t) fi(t+1)|C) 11ReInitial(i); 12135) PSO_LDS算法步骤令粒子运动总时间为Tmax，也是算法循环迭代的次数，给定算法所需参数，PSO_LDS算法描述如下：1Particle PSO_LDS(n, L, Tmax, )23 InitialGroup(L); /产生初始种群4 for(iter=0; iterTmax; iter+)5 GetPbest(X, L);/设置粒子局部最好位置6 GetGbest(X,L);/设置粒子全局最好位置7 UpdateVelocity(V, L);/更新速度8 UpdateLocation(X, L);/更新位置9 for(i=1; i= L; i+)10 /粒子合法性更新11 ValidateByGreedy_LBC(X, i);12 /防早熟措施 13 Avoidence_Method1(i, iter, T, e1); 14 Avoidence_Method2(i, t, count, e2, C);15 16 17 return GetGbest(X, L); /输出全局最优粒子18 3.3 费用最小的网关部署方案求解过程本文把费用最小的网关部署问题归结为QoS约束图G的最小权有限支配集的求解问题，并分别提出了求解最小权有限支配集的贪婪算法Greedy_LDS和粒子群优化算法PSO_LDS。费用最小的网关部署方案求解过程如下：1) 根据实际需求，得到无线mesh网络原型图G(V, E)，V=SM，S为网关候选节点集合，M为mesh路由器节点集合；2) 根据给定的QoS约束，构建网关候选节点为根的路由树；3) 根据各路由树覆盖的节点情况，构造QoS约束图G(V, E)；4) 根据提出的贪婪算法Greedy_LDS或者粒子群算法PSO_LDS求解图G的最小权有限支配集；5) 图G的最小权有限支配集代表费用最小的网关节点集，同时得到各网关的覆盖集。4 实验仿真为验证本文工作的正确性和有效性，我们进行了仿真实验。实验使用Microsoft Visual C+ 6.0在个人计算机上编程实现相关算法，主机配置：CPU Pentium 4 3.06GHz，主存512MB，操作系统为Windows XP。实验首先随机生成一定数量的网络图，对每一幅图G，在网络的各个区域随机选取若干节点为网关候选节点，构成网关候选节点集合S，各网关候选节点的部署费用在1, 10随机取值，最大负载在200, 400随机取值；其余节点构成mesh路由器集合M，各节点汇聚流量在1, 20随机取值，然后分别应用OPEN/CLOSE算法11、Greedy_LDS算法和PSO_LDS算法对随机图构造满足参数R、T、D和S的网关部署方案，并对运行结果进行比较。4.1 部署费用比较实验在1515的区域放置若干节点，每个节点的传输距离为1个单位，随机生成500个网络拓扑图，求取各种情况下3算法得到的网关部署费用的平均值，结果如图5所示。实验中，QoS参数R=4、D=4、S=20、T=300；PSO_LDS算法参数w=1、c1=2、c2=2，种群大小L=20，粒子运动时间（迭代次数）Tmax=30。如图5所示，3算法得到的网关部署费用都随着节点数增多而增多，GREEDY_LDS算法稍差于OPEN/CLOSE算法，数值平均来看，与GREEDY_LDS和OPEN/CLOSE算法相比，PSO_LDS算法得到的网关部署方案的费用分别减小约15%和9%。图5 不同的节点数对部署费用的影响另外，不同的网关候选节点数量对算法结果也有一定影响，如图6所示。当网关候选节点数超过总节点数的17%时，GREEDY_LDS算法能找到费用较小的解。本文的解释是，随着网关候选节点的增多，解空间扩大，在特定的迭代次数下PSO_LDS算法不能找到最好的解，此时，GREEDY_LDS算法以较好的敏感性，有较好的表现。实验还发现，增加种群大小和迭代次数，PSO_LDS算法有更好的表现。图6 不同的网关候选节点数对部署费用的影响4.2 算法执行时间分析在前面的实验中，记录下各算法的执行时间，得到的算法执行平均时间如表一所示。从中可见GREEDY_LDS算法有最快的执行速度，OPEN/CLOSE算法次之，PSO_LDS算法由于其迭代寻优的特点，执行速度较慢。但是，由于网关部署方案是在网络设计阶段制定，对算法执行时间相对不敏感，PSO_LDS以其良好的表现仍可适用。表13种算法执行时间比较 (单位：ms)算法节点数30507090110130150GREEDY_LDS1.572.042.974.226.098.7511.1OPEN/CLOSE8.2413.4117.4623.6733.7848.8660.48PSO_LDS60.69118.34196.63275.53347.75416.94476.41从本文得到的实验数据来看，GREEDY_LDS算法和PSO_LDS算法有不同的特点，有各自的适用范围。GREEDY_LDS算法可以快速得到费用较小的部署方案，PSO_LDS算法则以执行时间的增加为代价，可以找到更为优化的网关部署方案。与OPEN/CLOSE算法相比，本文提出的两算法都有其优势，GREEDY_LDS算法在网关候选节点较多时能得到较好的解；增加种群大小和迭代次数，PSO_LDS算法也可以得到优化的解。5 结束语本文在分析已有研究工作的基础上，以最小化网关部署费用为目标，研究满足QoS约束的网关部署问题。以往的研究把无线mesh网网关部署问题归结为整数线性规划优化问题，与之不同的是，本文提出图的有限支配集的概念，并把费用最小网关部署问题归结为求图的最小权有限支配集问题。同时，本文提出了贪婪算法GREEDY_LDS和粒子群算法PSO_LDS来求解图的最小权有限支配集，实验表明两算法各有特点，有各自的适用范围。在无线mesh网设计阶段，网关的合理部署对网络性能、服务质量和建设成本有重要意义。但是，随着网络的运行，网络流量分布的变化，网关之间的协作与负载均衡对网络性能及服务质量有重要影响。下一步工作将会集中于网关协作机制的研究，提高网关间的负载均衡，进一步优化网络性能。参考文献：1AKYILDIZ IAN F, WANG X. A survey on wireless mesh networksJ. Communications Magazine, IEEE, 2005,43(9):23-30.2WU X, LIU J, CHEN G. Analysis of bottleneck delay and throughput in wireless mesh networksA. IEEE MASSC. 2006. 765-770.3张勇, 蔡杰, 宋梅等. 无线mesh网络公平性研究J. 中国科学技术大学学报,2007,37(2):164-170.ZHANG Y, CAI J, SONG M, et al. Study on the fairness of wireless mesh networksJ. Journal of University of Science and Technology of China, 2007, 37(2): 164-170.4杨盘隆, 陈贵海. 无线网状网容量分析与优化理论研究J. 软件学报, 2008,19(1):111-125.YANG P L, CHEN G H. Research paradigm of capacity analysis and optimizing theory on wireless mesh networkJ. Journal of Software, 2008, 19(1): 111-125.5JUN J, SICHITIU M L. Fairness and QoS in multihop wireless networksA. Vehicular Technology ConferenceC. 2003. 2936- 2940.6WONG J, JAFARI R, POTKONJAK M. Gateway Placement for Latency and Energy Efficient Data AggregationA. Local Computer Networks, 29th Annual IEEE International ConferenceC. 2004. 490-497.7CHANDRA R, QIU L, JAIN K, et al. Optimizing the placement of integration points in multi-hop wireless networksA. Proceedings of IEEE ICNPC. 2004, Berlin.8BEJERANO Y. Efficient integration of multihop wireless and wired networks with QoS constraintsJ. Networking,IEEE/ACM Transactions, 2004, 12(6):1064-1078.9AOUN B, BOUTABA R, IRAQI Y, et al. Gateway placement optimization in wireless mesh networks with QoS constraintsJ. IEEE Journal on Selected Areas in Communications, 2006,24(11): 2127-2136.10HE B, XIE B, AGRAWAL D. Optimizing the Internet gateway deployment in a wireless mesh networkA. Mob