WMN中基于网关饥饿度的部署算法优化

赵云飞^{1, 2}，陈志刚^{1, 2}，曾锋¹

(1. 中南大学 软件学院，湖南 长沙，410075；

2. 中南大学 信息科学与工程学院，湖南 长沙，410083)

摘要：研究满足QoS约束条件的网关负载均衡部署优化问题，定义网关饥饿度衡量网关负载均衡性，并提出网关部署的饥饿算法，在为每一簇分配网络节点时，都尽量使其簇头(网关)饥饿度最大程度接近网络总的平均值，最终实现网关间负载均衡，同时满足QoS约束。仿真实验结果表明：饥饿算法得到的网关数量与其他传统算法得到的结果非常接近，甚至更优；而在网关负载均衡方面，饥饿算法优势较明显，与Greedy_Partition算法相比，网关饥饿度样本标准方差约减少54%。

关键词：无线Mesh网；网关部署；负载均衡；饥饿算法；饥饿度

中图分类号：TP393           文献标志码：A         文章编号：1672-7207(2013)11-4492-07

Placement algorithm optimization in wireless mesh networks based on gateways’ hungry-value

ZHAO Yunfei^{1, 2}, CHEN Zhigang^{1, 2}, ZENG Feng¹

(1. School of Software, Central South University, Changsha 410075, China;

2. School of Information Science and Engineering, Central South University, Changsha 410083, China)

Abstract: The problem of gateways deployment was addressed to achieve the goal of load balance in gateway placement with QoS requirements being satisfied, the gateways’ hungry-value was defined to measure the load-balance of gateways, and a hungry algorithm was presented for network clustering. When network nodes was assigned for each cluster, the hungry value of gateway should become close to their average of hungry value as much as possible and achieve load balance placement of gateways in the end. At the same time, it always meets the QoS constraints during the entire clustering process. The results show that the number of gateways generated by the hungry algorithm is nearly equal to those from other gateway placement algorithms, and as far as the load balance of gateways is concerned, the hungry algorithm performs much better than the others. Specially, compared with Greedy_Partition algorithm, the hungry algorithm improves the load balance of gateways with the standard deviation of the gateways’ hungry value decreased by 54%.

Key words: wireless mesh network; gateway placement; load balance; hungry algorithm; hungry-value

无线Mesh网络(wireless mesh network, WMN)是一种高速率、高容量的分布式网络，具有组网方便、简单和可扩展等优点，是解决“最后1 km”问题的网络结构^[1]。无线Mesh网络是一种多跳传输网络，由Mesh路由器节点、网关节点和客户端节点3种类型的节点组成。其中，网关节点是一种特殊的Mesh路由器节点，不单是具有Mesh路由器节点的功能，还通过有线电缆与Internet直接相连。全部的Mesh路由器节点构成了无线Mesh网的骨干网，客户节点的数据经由多个Mesh路由器转发汇聚到网关，再通过网关实现客户端对Internet的访问。除了节点偶尔发生(部署)失败或增加外，无线Mesh网有相对固定的拓扑结构。几乎全部的流量汇聚到或者来自网关节点，而不像Ad hoc网络中任意2个节点直接可以进行流量传输。网关节点将直接连接固定网络，从而构成了无线Mesh网的流量汇聚地和流量源头，这样在实际的网络运行中，合理部署网关可以提升无线Mesh网的性能^[2]，反之就很容易形成网关流量负载不均衡的现象。网关流量负载不均衡将会导致以下问题：(1) 负载过大(饥饿度过小)的网关不能保证全部客户端节点的QoS(服务质量)。由于无线Mesh网中存在QoS的不公平^[3-5]，离网关较近的客户端节点能够得到较优的服务。对离网关较远的客户端节点，网关负载过大导致QoS难于保证；(2) 负载较小(饥饿度较大)的网关不能充分利用其资源为更多的客户端节点提供服务。为提升性能并降低路由复杂性，无线Mesh网常常划分为互不相交的若干簇，每个簇由一网关担当簇首，并为簇内的节点提供服务，因此每一个网关节点所服务的客户端节点数量是相对固定的，负载较轻的网关节点不能充分利用其剩余的资源为更多的客户端提供服务；(3) 由于网关节点是无线Mesh网性能的瓶颈^[6]，即使网络汇聚的流量远远低于其最大容量，网关负载的不均衡也会导致较差的网络QoS。解决无线Mesh网中网关部署问题，主要是达到最小化网关数量和网关之间的负载均衡的目标，同时能确保满足QoS约束。定义网关饥饿度来衡量网关间负载均衡性，并提出饥饿算法来把无线Mesh网划分成满足QoS约束的若干簇。针对无线Mesh网中网关部署问题，设计一个较优的分簇算法，尽可能地实现网关之间的负载均衡，同时保证满足QoS要求。

1  相关工作

网关部署问题可被视为在运筹学和近似算法领域研究中更为一般的容量设备选址问题的一个实例。在过去的几年中，研究者已经做了大量关于设备选址问题的近似算法^[7]的设计和分析的工作，如非固定容量设备选址问题^[8]和K中心聚类问题^[9]。其他的研究工作提出了K跳分簇算法，但都不能满足分簇问题的所有要求，并且几乎都不能在性能优化方面得到保证。

针对无线Mesh网中网关部署问题，有些学者把它模型化为线性规划优化问题，并针对不同的约束条件提出了许多网关部署算法^[10-14]。Chandra等^[10]研究部署网关数量优化的问题，部署中考虑到各节点的带宽要求，提出了具有容错能力的贪婪分簇算法。Wong等^[11]考虑网关部署中通信代价最小化及通信时延最小化2个独立的问题，并把问题归结成整数线性规划优化问题，提出了基于统计方法的启发式算法。曾锋等^[12]等提出了利用遗传算法在多目标优化方面的优势，并与贪婪算法相结合来求解达到网关数量最小和网关负载均衡的网关部署策略。Aoun等^[13]提出QoS约束下的网关部署贪婪算法Recursive_DS。Bejerano等^[14]在研究网关部署问题中，考虑各种无线链路模型，并提出了相关的贪婪算法。

上述算法都试图在确保满足QoS的条件下，尽可能地使部署的网关数量减少，在各自的网络模型下也都收到了较好的效果。但是，仍有一些方面需要改善，如减少网关数量的同时应考虑网关间的负载均衡情况，以及在实际的无线Mesh网络应用场景中，各网关的最大容量不同，那么此时用网关流量的平均值及方差来衡量负载均衡性，就显的不尽合理，例如，假设2网关G₁和G₂，最大容量分别是100和30，若流量负载平均值太小(＜30)，则G₁的网关的利用率太低，反之太大(＞30)，已超过G₂的最大容量，都会引起网关负载失衡现象。

本文在分析以上算法的基础上，研究满足QoS约束条件下的网关部署问题，与以上研究不同的是：本文以网关数量最小化和网关之间的负载均衡的双重优化为目标，用网关资源(容量)的实际利用比例来衡量网关间负载均衡性，即本文定义的网关饥饿度，并提出了网关部署饥饿算法来求解达到网关数量最小化和网关负载均衡的部署策略。

2  网络模型及问题描述

2.1  网络模型

在无线Mesh网中考虑网关部署的问题。WMN的骨干网可用1个无向连通图G(V, E)表示。每个节点表示1个网络节点，可以是WMN中的路由器节点或网关节点，并具有若干个单位的圆形传输范围，在该传输范围内的相邻节点都可以直接通信。v的邻居节点集，定义为N(v)，是在它的传输范围内的节点集合。在节点v和其任一邻居节点之间存在一条双向无线链路，并用边表示。顶点v的邻居节点数称为v的度，定义为δ(v)。图G中最大度数成为图的度数△(G)=△。

节点u和v之间的距离定义为d(u, v)，是它们之间最小的跳数值。图G(V, E)中v的半径是v和其他任一节点之间的最大距离。图中最小的半径值定义为图半径。另外，图直径是任意2个节点间的最大距离(或最大半径)。

在集合V中，有一些节点通过有线电缆直接与Internet相连，称为网关，WMN中的流量经过网关节点到达Internet，用G={g₁, g₂, …, g_c}表示网关的集合。剩下的节点为普通的路由器节点，主要作用是汇聚转发客户端的流量至各自的网关节点。为研究方便，用权值W(v)表示Mesh路由器v汇集的客户端流量。对任意网关g_i∈G，假设网关的容量为C(g_i)，实际负载量为L(g_i)，相关计算公式如下：

(，)       (1)

                    (2)

                  (3)

                 (4)

其中：L(g_i)为网关负载量；为网关饱和度；为网关饥饿度；为网关饥饿度均值。

另外，用1个邻接矩阵来表示连通图。图G(V, E)的邻接矩阵是1个用行和列标记顶点V的矩阵，根据V_m和V_n是否是直接相连接，来判定(m, n)位置是1或0(直接相连为1，反之则为0)。对于无向图G，邻接矩阵是对称的。

2.2  问题描述

在本文中，要达到无线Mesh网和有线网络的高效融合，同时确保满足QoS要求。这包括在逻辑上把WMN分成不相交的若干个簇，覆盖网络中的所有节点。在每个簇中，1个节点会担当网关，直接与有线网连接，并为簇内节点提供服务。

基于运作的原因，网关部署或分簇问题是服从QoS约束的。网关部署问题要考虑QoS(服务质量)约束，如延时和带宽问题。在1个多跳网络中，由于存在无线信道的竞争、包处理和排队延迟等问题，显著延时发生在每一跳中。延迟是一个与源端和网关之间的通信跳数相关的函数。延迟约束可以转化为一个有上界的簇半径R，或者是以网关为根的生成树的最大深度R；通过链路干扰模型^[15]分析网络性能，可以了解到瓶颈干扰域决定端到端的带宽，而节点的度数越大，其受到干扰的可能性越大，其干扰域的权值就会越大，因此，为确保端到端的带宽，节点在簇中的度数不能超过有上界的节点度数D；同时，给簇规模一个上界S，以确保网络的各项性能。因此，网关部署问题转化为在逻辑上把WMN划分成覆盖全部节点的不相交簇集合，并全部满足3个QoS约束。

本文研究的网关部署问题，就是尽量保持网关数量最少和网关负载间均衡，同时，各簇的规模、节点的度及节点与网关间的距离满足上界S，D和R，则该问题可以抽象为整数线性规划优化问题，定义N=V为网络节点集合，为网关集合，G是V的子集。定义y_i∈{0,1}，对于节点v_i∈V，若v_i∈G(G为网关集合)，则y_i=1；否则y_i=0。定义x_ij∈{0, 1}，若节点v_j的指定网关为g_i，则x_ij=1；否则x_ij=0。定义h_ij为节点v_j与网关v_i之间的最短距离，单位为跳。定义δ(v)为节点v在簇内的度数。目标函数如下：

                 (5)

       (6)

符合条件：

(a)                      (7)

(b) ≥x_i,j                 (8)

(c) ≤R              (9)

(d) ≤S                   (10)

(e) ≤D                   (11)

(f) ,    (12)

这样，优化部署问题化为2个总体目标：即最小化网关数量K和网关负载均衡，其中E_var为网关饥饿度的样本标准差。同时，条件(a)表示V中任一节点有且仅有1个指定网关；条件(b)表示网关在做为簇头前需要先建立；条件(c)表示在节点和指定网关间存在一条路径并且最短距离不大于R跳；条件(d)和(e)提供了簇规模和簇内度数的上界约束；最后一个条件(f)表示y_i和x_ij是二进制变量。

据上所述，本文研究的网关负载均衡的部署问题抽象为整数线性规划优化问题，该问题是NP难问题^[10]。因此，本文提出饥饿算法，根据给定网关进行WMN分簇，利用饥饿算法Hungry_ Placement来求问题的较优解。

3  网关部署优化的饥饿算法

3.1  算法描述

在实际的无线Mesh网络应用场景中，各网关的最大容量不相同(容量足够大)，本文提出网关饥饿度来度量网关间负载均衡性，并设计了饥饿算法来对WMN分簇，更好地提高网关间的负载均衡程度。

饥饿算法Hungry_Placement，算法如下。

输入：初始的网关节点序列；

输出：完整的网关节点序列和分簇方案。

算法步骤如下。

步骤1：g_i∈G为根QoS约束广度遍历，建立可能簇集合I_Ci(各簇间可含重复节点)；

步骤2：若有节点没被可能簇集合簇覆盖，在未覆盖的节点中随机(按概率)选择一节点，假设为v_u，G=G+{v_u}，并以v_u为根QoS约束广度遍历建可能簇集合I_Ci，若所有节点都被可能簇集合簇覆盖，则继续下一步；否则，转步骤2。

步骤3：把没有重复的节点直接分在相应的确定簇集合中C_Ci。

步骤4：把网关集合G按负载均衡排序(插入排序)，≤≤…≤，求出网关饥饿度的均值，在g_k可能簇集合I_Ck中寻找合适的节点，该节点负载流量可以使网关g_k的饥饿度最大程度的接近网络平均“饥饿”水平，并把该节点加入g_k的确定簇集合C_Ck，并在所有可能簇集合中剔除该节点。

步骤5：若所有节点都被确定簇集合簇覆盖，则算法结束；否则转步骤4。

3.2  算法图示

饥饿算法简单示例如下图1~4所示，图1所示为无线Mesh网拓扑结构，其中随机选取R₁和R₂ 2节点为网关节点，网关节点R₁和R₂的最大容量分别为60和80，其余节点为普通路由节点；利用饥饿算法建立可能簇集合，由于不能覆盖所有节点，在未覆盖的节点中按概率选择一节点(假设R₉，容量为55)为网关，并建立第3个可能簇，如图2中不同的虚线所圈表示，I_C1={R₃, R₄, R₅, R₇}，I_C2={R₄, R₅, R₆, R₈}，I_C9={R₈, R₁₀}，由3个可能簇集合可知：节点R₂被网关R₁唯一覆盖，所以直接把R₂加到网关R₁的确定簇中，即C_C1={R₁}，以此类推，C_C2={R₆}，C_C9={R₁₀}，网关集合G={R₁, R₂, R₉}；按照饥饿算法的定义公式计算可得：各网关饥饿度分别为β(R₁)=80.0%，β(R₂)=90.0%，β(R₉)=72.0%，网关的饥饿均值为=80.9%，由此可知网关R₂的饥饿度最大，那么在可能簇I_C2中选择一个合适节点，其节点流量可以使网关R₂的饥饿度最大程度的接近网络平均“饥饿”水平，经计算得到，该合适节点为R₅，则将节点R₅加入网关R₂的确定簇中，即C_C2={R₅，R₆}，并把R₅从所有可能簇集合中剔除；以此类推，最终计算得到如图4所示的分簇结果及网关节点信息，C_C1={R₁, R₃, R₄, R₇}，C_C2={R₅, R₆, R₈}, C_C9={R₉, R₁₀}，最终各网关饥饿度分别为β(R₁)=68.3%，β(R₂)=71.2%，β(R₉)=70.0%，总的网关饥饿度均值为=69.8%，由以上数据可知：各网关的流量负载较均衡(网关资源利用率较高)，因而得到的网络分簇方案较优。该算法结束条件是所有的可能簇集合均为空。

图1  原网络拓扑图

Fig.1  Original network topology

图2  以网关节点为簇头的可能簇集合I_Ci

Fig.2  Gateways with head node of possible cluster collections I_Ci

图3  对节点R₅的选择与分簇

Fig.3  Selecting and clustering for node R₅

图4  最终分簇结果及网关节点信息

Fig.4  Last clustering result and information of gateways

4  实验仿真

为验证本文提出算法的正确和有效性，进行了仿真实验。实验使用Microsoft Visual C++ 6.0在PC上编程实现，主机配置：CPU为Intel Core2 -2.93 GHz，内存为1.96 G，操作系统为Windows Xp。

首先实验随机生成一定数量的网络拓扑图，图中节点权值在[1, 20]随机取值，然后，分别应用Greedy_Partition算法^[12](图中略为Greedy)、本文提出的Hungry_ Placement算法(图中略为Hungry)对随机图构造满足节点度数上限D、跳数上限R以及簇规模上限S的网关部署方案，并从网关数量K比较和网关负载均衡度Var的比较对实验结果平均值进行分析。

4.1  网关数量和负载均衡的综合比较

实验在15×15的区域随机放置150个节点，随机生成500个网络拓扑图，并对节点度数上限D、跳数上限R以及簇规模上限S取不同值，求各种情况下Hungry_ Placement算法与Greedy_Partition算法构造得到的网关数量平均值K和网关负载均衡度E_var的情况，结果如图5~11所示。

图5  R取值对网关数量的影响(D=6, S=20)

Fig.5  Impact of hop R value on number of gateways

图6  R取值对网关负载均衡的影响(D=6, S=20)

Fig.6  Impact of hop R value on load balance of gateways

由图5和图6可见：在QOS约束下，节点度数上限D和簇规模上限S固定不变，随着跳数上限R的逐渐增大，Hungry_Placement算法与Greedy_Partition算法构造得到的K值逐渐减少，但两者非常接近；2种算法得到的E_var在R由2跳逐渐变为4跳间直线增加，当R＞4后，呈现缓慢增加的走势，但Hungry_Placemen算法取得的E_var远低于Greedy_Partition算法取得的值。

由图7和图8可见：在QOS约束下，节点跳数上限R和簇规模上限S固定不变，随着度数上限D的逐渐增大，Hungry_Placement算法与Greedy_Partition算法构造得到的K逐渐减少，但两者非常接近，前者甚至更优；Greedy_Partition算法得到的E_var随着D的加大而急速增大，并在D=8时E_var最大，而Hungry_Placemen算法取得的E_var随着D的加大变化不大，较平稳，在R=4时取得最小值。同时，Hungry_Placemen算法取得的E_var远低于Greedy_ Partition算法取得的值。

图7  D取值对网关数量的影响(R=4, S=20)

Fig.7  Impact of degree D value on number of gateways

图8  D取值对网关负载均衡的影响(R=4, S=20)

Fig.8  Impact of degree D value on load balance of gateways

图9  S取值对网关数量的影响(D=6, R=4)

Fig.9  Impact of cluster size S value on number of gateways

图10  S取值对网关负载均衡影响(D=6, R=4)

Fig.10  Impact of cluster size S value on load balance of gateways

由图9和图10可见：在QOS约束下，节点跳数上限R和度数上限D固定不变，随着簇规模上限S的增大，Hungry_ Placement算法与Greedy_Partition算法构造得到的K值逐渐减少，但两者非常接近；2种算法得到的E_var也随着D的加大而呈直线走势增大，但Hungry_Placemen算法取得的E_var远低于Greedy_ Partition算法取得的值。

由图11可见：在QOS约束下，节点跳数上限R=4，度数上限D=6，簇规模上限S=20，进行的10次试验所得E_var的平均值显示，与Greedy_Partition算法相比，Hungry_ Placement算法网关取得的E_var约减少54%，表现较好。

图11  10次试验数据平均值对比分析(D=6, R=4, S=20)

Fig.11  Var’ average value of 10 times experiments

综上分析可得：Hungry_ Placement算法得到的K值与Greedy_Partition算法得到的数据非常接近，甚至更优，但取得的E_var值远远低于Greedy_Partition算法取得的值。因此，饥饿算法实现了网关部署的网关负载均衡。

5  结论

(1) 无线Mesh网网关部署问题是影响网络性能的瓶颈。本文在分析已有算法的基础上，以网关数量最小化和网关间负载均衡为双重优化目标，研究满足QoS约束下的网关部署问题。提出饥饿算法，定义网关“饥饿”度来度量网关间负载均衡性，并用算法实现对WMN分簇，得到较优的解，更好地提高了网关间的负载均衡程度。

(2) 饥饿算法得到的网关数量与其他算法得到的结果非常相近，甚至更小；而在网关负载均衡方面，饥饿算法优势明显，达到了网关数量最小化与负载均衡的双重优化目标。

(3) 下一步将继续展开在无线Mesh网拓扑结构动态变化下的网关负载均衡部署策略方面的研究。

参考文献：

[1] 王玉磊. 无线Mesh网关键技术分析[J]. 网络安全技术与应用, 2007(4): 92-94.

WANG Yulei. Analysis of the key technology of wireless mesh networks[J]. Network Security Technology & Application, 2007(4): 92-94.

[2] Robinson J, Knightly E W. A performance study of deployment factors in wireless mesh networks proc[C]// INFOCOM 2007. 26th IEEE Int. Conf. Computer Communications. Anchorage: IEEE, 2007: 2054-2062.

[3] 张勇, 蔡杰, 宋梅, 等. 无线mesh网络公平性研究[J]. 中国科学技术大学学报, 2007, 37(2): 164-170.

ZHANG Yong, CAI Jie, SONG Mei, et al. Study on the fairness of wireless mesh networks[J]. Journal of University of Science and Technology of China, 2007, 37(2): 164-170.

[4] 杨盘隆, 陈贵海. 无线网状网容量分析与优化理论研究[J]. 软件学报, 2008, 19(1): 111-125.

YANG Panlong, CHEN Guihai. Research paradigm of capacity analysis and optimizing theory on wireless mesh network[J]. Journal of Software, 2008, 19(1): 111-125.

[5] Jun J, Sichitiu M L. Fairness and QoS in multihop wireless networks[C]// Proc VTC 2003-Fall Vehicular Technology Conf. 2003 IEEE 58^th. Orlando: IEEE, 2003: 2936-2940.

[6] WU Xiaobing, LIU Jiangchuan, CHEN Guihai. Analysis of bottleneck delay and throughput in wireless mesh networks[C]// Proc IEEE Int Mobile Adhoc and Sensor Systems (MASS) Conf, 2006: 765-770.

[7] David B S. Approximation algorithms for facility location problems[J]. APPROX, 2000(9): 27-32.

[8] Kuehn A, Hamburger M J. A heuristic program for locating warehouses[J]. Management Science, 1963, 9: 643-666.

[9] Arora S, Raghavan P, Rao S. Approximation schemes for Euclidean k-medians and related problems[J]. ACM Symposium on Theory of Computing, 1998: 106-113.

[10] Chandra R, Qiu L, Jain K, et al. Optimizing the placement of Internet TAPs in wireless neighborhood networks[C]// Proc 12th IEEE Int. Conf. Network Protocols ICNP 2004. Washington: IEEE, 2004: 271-282.

[11] Wong J L, Jafari R, Potkonjak M. Gateway placement for latency and energy efficient data aggregation[C]// Proc 29th Annual IEEE Int Local Computer Networks Conf. Tampa: IEEE, 2004: 490-497.

[12] 曾锋, 陈志刚, 赵明, 等. 无线Mesh网中实现网关负载均衡部署的混合算法[J]. 系统仿真学报, 2009, 21(10): 3029-3034.

ZENG Feng, CHEN Zhigang, ZHAO Ming, et a1. Hybrid algorithm for load-balance placement of gateways in wireless mesh network[J]. Journal of System Simulation, 2009, 21(10): 3029-3034.

[13] Aoun B, Boutaba R, Iraqi Y, et al. Gateway placement optimization in wireless mesh networks with QoS constraints[J]. IEEE Journal Selected Areas in Communications: 2127-2136.

[14] Bejerano Y. Efficient integration of multihop wireless and wired networks with QoS constraints[J]. Networking, IEEE/ACM Transactions, 2004, 12(6): 1064-1078.

[15] Jun J, Sichitiu M L. The nominal capacity of wireless mesh networks[J]. Wireless Communications, IEEE, 2003, 10: 8-14.

(编辑  何运斌)

收稿日期：2012-08-20；修回日期：2012-10-10

基金项目：国家自然科学基金资助项目(61103202，61073186)；教育部优先资助领域项目资助(20120162130008)

通信作者：陈志刚(1964-)，男，湖南益阳人，博士，教授，从事网络计算与分布式处理研究；电话：13787249417；E-mail: zyf@csu.edu.cn