0 引言

    随着物联网技术的飞速发展和日益普及，6LoWPAN广泛应用于智能家居、环境监测和楼宇自动化等领域。单网关架构的6LoWPAN存在网关瓶颈问题，且不利于大规模部署。因此，多网关系统将是实现WSN和Internet互联的高效模式，网络系统示意如图1所示，其中A为根网关，B、C为部署网关。在多网关系统中，网关位置的选择不仅影响节点间的链路质量和通信延迟，而且还决定了网络整体的容量。因此，合理的网关部署是实现6LoWPAN网络性能优化的关键。

    针对6LoWPAN负载均衡问题的研究，文献[1]利用子节点根据邻居节点的排队率和跳距选择父节点实现负载分担，并在文献[2]中对路由方案进行了补充和更新。文献[3]提出一种基于负载均衡的分层路由算法，保证网络负载平衡的同时提高网络生存周期。在6LoWPAN多网的研究中，文献[4]提出一种多网关系统方案，解决网关瓶颈问题并提高网络吞吐量。文献[5]在多网关架构的基础上，提出一种分布式动态负载平衡方案实现全局负载平衡。近年来基于LoRa技术的远距离无线广域网（Long Rage WAN，LoRoWAN）采用多网关系统，并且在LoRaWAN上实现了6LoWPAN标准。

    在WSN网络的sink部署研究中，从用多sink节点代替单sink节点的网络划分方案^[6]的提出，到在多sink网络中考虑布局和能耗，提出一种基于启发式算法的部署优化方案^[7]。为了提高多跳WSN的网络生存周期，提出基于粒子群算法的多sink节点部署算法^[8]和分布式贪婪簇生成算法^[9]，而文献[10]提出两种基于能量的sink局部搜索策略。多网关部署问题研究常见于WMN网络，以负载均衡为目标，通过基于权值的贪婪算法^[11]、改进杂交粒子群优化算法^[12]和优化类聚K-means算法^[13]完成网关部署。在考虑网关实际容量的情况下，文献[14]在贪婪算法的基础上定义饥饿度，提出一种能更好实现负载均衡的饥饿算法。文献[15]以最小化网络能耗为目标，提出一种基于启发式的贪婪算法实现绿色WMN的网关部署。

    上述研究中，WSN网络为星型拓扑，WMN网络为网状拓扑，其拓扑结构对网关部署的约束性小。6LoWPAN网络为树型拓扑，网关部署算法需要考虑节点位置和网络拓扑的关系。在6LoWPAN网络中，产生的数据流量多跳路由经过不同的路由器（6LoWPAN Router，6LR），在边界路由器（6LoWPAN Border Router，6LBR）汇聚发往Internet。即使采用多网关系统，由于缺少网关均衡，也会导致网关之间负载不平衡。本文以最小化网关数量和网关间负载均衡为目标，在贪婪算法的思想上结合6LoWPAN树型拓扑网络的特殊性，提出一种基于负载的多网关部署算法，以最少网关数量实现网关负载均衡。

1 网络模型搭建

    在6LoWPAN中考虑多网关部署问题，用图G(V，E)表示待优化网络。节点v∈V为6LoWPAN中的节点，可为6LR或者6LBR。在6LoWPAN网络中，6LR负责转发和路由IPv6数据包；而6LBR负责6LoWPAN网络和其他IP网络的数据交互，即实现网关功能。设v具有一个圆形的可通信范围，根据目标函数选择与在该范围内的节点建立拓扑连接。在构建好的拓扑结构中，与v连接的节点分为父节点N_p(v)和子节点集N_c(v)，N(v)=N_p(v)+N_c(v)。由于6LoWPAN的DODAG树型网络拓扑的特殊性，v至多有一个父节点但可以有多个子节点或者没有子节点。对于节点u∈N(v)，存在边e(u，v)∈E，e(u，v)为v和u之间的双向通信链路，表示节点v和u之间已经建立拓扑连接。

2 问题描述

    研究6LoWPAN多网关网络设计，通过合理部署网关，使得各网关间负载平衡，同时将链路质量和网关剩余能量作为参考因素，保证网络的稳定性。网关部署问题就是在单网关架构下的6LoWPAN网络中，根据节点流量负载和综合因子进行网关选择，用最少的网关数量实现网关间的负载均衡。然后，根据网关部署的结果划分子网分支，将在树型拓扑中以同一网关作为根的节点划分到一个子网分支。

    条件（1）表示V中任一节点有且只有一个网关；条件（2）表示候选网关需要满足的负载门限要求；条件（3）表示选择候选网关中综合因子最大的节点作为网关节点；条件（4）表示网关的负载为子网分支内所有节点和网关节点本身的权值之和。将6LoWPAN多网关部署问题具体化：以最小网关数量实现网关间负载均衡。通过考虑节点负载得到候选网关，再根据链路质量和剩余能量的综合因子，从候选网关中选出最优网关。本文在贪婪算法的基础上，结合6LoWPAN网络树型拓扑的特点，提出一种多网关部署算法Load-base_Placement(LP)来获得问题的最优解。

3 多网关部署算法

3.1 算法思路

    由于6LoWPAN网络采用的是树型拓扑结构，其网络中节点的流量负载具有累加特性。位于根节点和叶子节点之间的中间路由节点不仅要承担自身流量负载，还要负责其子节点的数据转发。在树型拓扑网络中，从叶子节点至根节点流量负载累积增加。因此，算法采取从叶子节点开始沿树型拓扑往上至根接网关的策略，搜索候选网关，并确定最佳网关。

    算法大致过程如下：在现有6LoWPAN树型拓扑网络中，根据各节点流量负载统计结果，进行权值化处理。从距根节点跳距最大且有较大流量负载的叶子节点开始，往上至根节点，搜索满足流量负载条件的候选网关节点。根据链路质量和剩余能量所构成的评价因子，在候选网关选择最佳网关并确定对应子网分支，移除该分支与网络中其他节点的链路连接。在移除已经确定的子网分支后，更新网络中剩余节点的流量负载值，并再次执行搜索，当访问至根网关时算法结束。

3.2 算法描述

    输入：初始的网关节点序列（只有一个根网关）；

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

    算法步骤如下。

    (1)访问当前网络中距根节点跳距最大且有较大流量负载的叶子节点。

    (2)对节点流量负载进行判断，如果L(v_i)<L_threshold，则向上访问其父节点，如果其父节点为根网关，则将此分支移除；如果L(v_i)>L_threshold，则向下回溯其子节点，判断是否存在满足L(v_i)>L_threshold-T的节点（即候选网关节点）。如果有，则判断评价因子μ(v_i)并选择μ(v)值最大的作为最佳网关；否则，确定该节点为网关。移除该网关分支并更新各节点流量负载值，并向上访问其父节点。

    (3)如果访问至网关节点，则算法结束；否则，跳转至步骤(1)。

3.3 情形分析

    网关部署算法根据树型拓扑从下往上进行搜索访问过程中，会出现3种典型情况，具体各情况的节点位置关系示意图如图2所示。

    类型1：N1节点的流量负载小于L_threshold，此时将N1连同其所有子节点一起划分到根网关分支；类型2：N3、N4均满足候选网关流量负载条件，此时根据综合因子μ(v)选择链路质量和剩余能量综合因子较优的节点为最佳网关；类型3：N4节点的流量负载小于L_threshold-T，同时其父节点N5流量负载大于L_threshold，此时选择N5最为最佳网关。

4 算法仿真

    为了验证算法的正确性和有效性，在MATLAB软件平台上进行仿真实验。模拟构建6LoWPAN树型拓扑网络，并将网络中节点的流量负载、链路质量和剩余能量因素进行数值化体现。在上述构建的网络中，分别运行基于流量负载的多网关部署算法LP和基于节点数量的Number-base_Placment(NP)算法完成网关部署。NP算法以节点数作为依据，划分出树型拓扑中满足节点数量要求的子网分支，并选择分支的根节点作为网关。对比两个算法所得到的网关数量K和网关负载均衡度Var，分析多网关部署算法的性能优势。

4.1 仿真参数

    实验在120×120的区域内随机放置36个节点，模拟DODAG生成树型网络拓扑图。在6LoWPAN网络中, 网关负载门限值L_threshold=30、T=5，节点负载按λ=5的泊松分布生成，链路质量和剩余能量综合因子按λ=5指数分布生成。

    在以上仿真参数下，生成的6LoPWAN网络如图3所示，其中标识的7号节点为根网关。

4.2 网关部署方案比较

    在相同网络中，分别应用LP算法和NP算法进行网关部署。实验结果如图4和图5所示，LP算法和NP算法将网络划分成多个分支，其中黑色标识的节点为各分支的网关。分析可知，LP算法最终得到6个网关，节点编号为：7、11、15、20、29、33。而NP算法最终也得到6个网关，节点编号为：7、15、18、20、27、28。结果表明，两种算法都能实现6LoWPAN网络的多网关部署。

4.3 网关数量和负载均衡比较

    在不同节点数量的条件下随机生成100个网络拓扑图，分别运行LP算法和NP算法。根据实验所得到的数据统计，求出两个算法所得到的网关数量K和网关负载均衡度Std的平均值，并对比分析。

    网关数量比较结果如图6所示，在相同节点数量的网络中，LP算法和NP算法所得到的网关数量大体相近。随着网络中节点数的增加，网络整体负载增加，网关数量随之增加。负载均衡度的比较结果如图7所示，在几个不同网络节点数量的网络中，LP算法所得到的Std值均小于NP，具有更好的网关负载均衡。

    因此，LP算法能够实现6LoWPAN的多网关部署，并且在利用与同等算法数量接近的网关实现更好的负载均衡。于此同时，还考虑了数据链路质量和网关剩余能量这两个因素，完成了6LoPWAN多网关系统的多网关部署。

5 结论

    本文提出基于负载的网关部署算法LP，利用6LoWPAN树型拓扑网络的特殊性，从最深子节点出发搜索候选网关，根据综合因子得到最佳网关。仿真实验表明，本算法在网关负载均衡方面的表现优势明显，并且所需网关数量与其他算法接近。在实现了负载均衡的同时兼顾网关数量，还考虑了链路质量和剩余能量的额外因素。

参考文献

[1] KIM H S，PAEK J，BAHK S.QU-RPL：queue utilization based RPL for load balancing in large scale industrial applications[C].IEEE International Conference on Sensing，Communication，and Networking.IEEE，2015：265-273.

[2] KIM H S，KIM H，PAEK J，et al.Load balancing under heavy traffic in RPL routing protocol for low power and lossy networks[J].IEEE Transactions on Mobile Computing，2017，16(4)：964-979.

[3] 姚玉坤，刘耀瑞，徐栋梁.6LoWPAN网络中基于负载均衡的分层路由算法[J].南京邮电大学学报(自然科学版)，2017，37(4)：78-83.

[4] 罗鹏，刘争红，郑霖.6LoWPAN多网关设计与实现[J].计算机工程与应用，2016，52(23)：148-152.

[5] HA M，KWON K，KIM D，et al.Dynamic and distributed load balancing scheme in multi-gateway based 6LoWPAN[C].IEEE International Conference on Internet of Things.IEEE Computer Society，2014：87-94.

[6] REHENA Z，ROY S，MUKHERJEE N.Topology partitioning in wireless sensor networks using multiple sinks[C].International Conference on Computer and Information Technology.IEEE，2011：251-256.

[7] 邵开丽，付辉.能耗均衡的无线传感器网络多Sink节点部署优化方法[J].仪表技术与传感器，2015(9)：106-110.

[8] DANDEKAR D R，DESHMUKH P R.Energy balancing multiple sink optimal deployment in multi-hop wireless sensor networks[C].Advance Computing Conference.IEEE，2013：408-412.

[9] CHATTERJEE P，DAS N.Multiple sink deployment in multi-hop wireless sensor networks to enhance lifetime[C].Applications and Innovations in Mobile Computing.IEEE，2015：48-54.

[10] BHATTACHARJEE S，AGARWAL K.Energy efficient multiple sink placement in wireless sensor networks[C].International Conference on Networking，Systems and Security，2017：1-7.

[11] WU W，LUO J，YANG M.Gateway placement optimization for load balancing in wireless mesh networks[C].International Conference on Computer Supported Cooperative Work in Design.IEEE，2009：408-413.

[12] 刘春晓，常桂然，贾杰，等.无线网状网中面向负载均衡的网关部署算法[J].计算机工程，2012，38(21)：107-109.

[13] 黄书强，周继鹏.基于聚类的无线Mesh网关选择及AP分组算法[J].华南理工大学学报(自然科学版)，2011，39(4)：38-43.

[14] 赵云飞，陈志刚，曾锋.WMN中基于网关饥饿度的部署算法优化[J].中南大学学报(自然科学版)，2013(11)：4492-4498.

[15] ASHRAF U.Energy-aware gateway placement in green wireless mesh networks[J].IEEE Communications Letters，2017，21(1)：156-159.

作者信息:

何艾洲，郑  霖，屈启吉

（桂林电子科技大学 广西无线宽带通信与信号处理重点实验室，广西 桂林541004）