基于烟花爆炸式混合蛙跳算法的LoRa网络参数分配策略*

周 超，章 辉，杨茂恒，郑天宇，姜美君

(南开大学 天津市光电传感器与传感网络技术重点实验室，天津 300350)

0 引 言

随着物联网(Internet of Things，IoT)的发展，网络需要承载的终端设备数量呈指数级递增，许多新兴的物联网技术方案逐步出现[1]，其中低功耗广域网(Low-Power Wide-Area Network，LPWAN)凭借超低的功耗和较低的组网成本实现超远距离传输，受到了广泛关注。而作为众多LPWAN技术中的一员，LoRaWAN以其组网简单灵活、可在免许可频段使用以及能够以极低的功耗进行远程通信等优点，被认为是当今最有前景的低功耗广域网技术之一[2]。

LoRaWAN采用星型拓扑结构[3]，该星型拓扑由网关和多个LoRa终端节点互连组成。原则上，每个节点都可以选择网关能正确接收的最小扩频因子(Spreading Factor，SF)进行通信，这也是当前在LoRaWAN中使用的自适应速率策略(Adaptive Data Rate，ADR)的目标[4]。但是，随着 LoRa技术的普及，在相近的区域内存在许多LoRa终端，在终端正常传输的时候，各个终端之间势必会出现干扰问题，大量终端同时请求发起通信也会导致信道拥塞、传输质量下降等问题。目前一些研究主要聚焦在LoRa系统的性能和系统可扩展性分析等问题上[5-12]，LoRa设备的性能不仅取决于通信技术，还取决于网关如何管理无线资源。

混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)最初由Eusuff[13]在2006年提出，算法模拟青蛙群体在湿地上跳动觅食的行为，通过青蛙个体间的合作与竞争实现在多维空间中对最优解的搜索。但混合蛙跳算法与上文提及的遗传算法、粒子群算法等在进行求解时都存在着传统群体智能算法通有的易陷入局部最优解、收敛精度低等缺陷。基于此，本文提出了一种基于烟花爆炸式混合蛙跳算法的LoRa网络资源分配策略。首先，对混合蛙跳算法引入反向学习、自适应烟花爆炸、高斯变异算子和欧氏距离分配种群等机制，提高算法的搜索性能；其次，将带有约束系数的平均传输成功率作为适应度函数，保证节点在数据可达网关的同时分配最佳参数，从而获得更好的可靠性；最后，使用基于LoRaSim的仿真平台对分配好的节点参数进行测试。实验结果表明本文算法优于其他算法，相较于其他算法具有更好的收敛精度，同时相较于传统ADR策略显著提升了信息接收率，能显著降低节点传输过程中的碰撞概率。

1 问题描述及模型

1.1 LoRa接收特性

LoRa技术在我国主要工作在433 MHz和470 MHz频段，在欧美等国家主要工作在868 MHz和915 MHz频段[14]。带宽主要使用125 kHz、250 kHz和500 kHz，传输速率可达0.1～120 kb/s，实际传输速率受每个节点的扩频因子、带宽和编码率等参数的限制，具体计算方式如下：

(1)

式中：SF表示扩展因子，BW表示带宽，CR表示编码率。

LoRa数据包传输时间Ts由有效负载的传输时间和前导码的传输时间组成[11]，其中发送单个符号所需的时间Tsym表示如下：

Rs=BW/2SF，

(2)

Tsym=1/Rs。

(3)

式中：Rs为符号速率。前导码传输时间Tpreamble为

Tpreamble=(npreamble+4.25)·Tsym。

(4)

式中：npreamble为前导码的长度，有效负载需要的传输时间Tpayload为

payload=8+max(ceil((8PL-4SF+28+16-20H)/

(4(SF-2DE)))(CR+4),0) ，

(5)

Tpayload=payload·Tsym。

(6)

式中：payload为有效负载的符号数，PL为有效负载的长度，H表示选择的报头类型，DE表示数据传输过程中是否采用低速率优化，ceil为取整函数。最终数据包传输时间为

Ts=Tpayload+Tpreamble。

(7)

信号接收强度Pr(d)可根据发射功率Ptx和天线增益G得到

Pr(d)=Ptx+G-Lp(d) 。

(8)

根据LoRa网络的应用场景和大规模部署的特点，本文使用对数路径损耗模型：

(9)

式中：d是从终端节点到网关的距离，d0是参考距离，Lp(d0) 是参考距离处的路径损耗，γ是路径损耗指数，Xσ是服从均值为0标准差为δ的正态分布。

1.2 碰撞分析

LoRa终端节点采用了一种基于ALOHA的协议进行传输，只要LoRa终端产生信息就会尽量发送。虽然这种传输协议简单易实现，但同样存在很多弊端——当小区内LoRa节点数量增多或者同一时刻产生的数据包数量增多时，数据包发生碰撞的概率会大大增加，信息传输成功率急剧下降。

在LoRa网络中，当两个或多个数据包到达网关时，同时满足以下条件，则认为发生冲突：到达时间上发生重叠；具有相同的载波频率；两个数据包使用了相同的扩频因子。此外，当两个数据包发生冲突时，当功率较大的LoRa数据包比功率较小的LoRa数据包大6 dB以上时，会发生捕获效应[15]：功率较大的数据包可以被接收，功率较小的数据包丢失。并且一些研究表明，在某些信噪比较低情况下，LoRa的不完美正交性也会影响数据包的接收[16]。为了便于建模，本文假设所有SF都是正交的。

1.3 系统模型

本文对只有一个接收网关的小区进行建模，其中网关位于小区中心，在这个网关附近存在n个LoRa节点以随机分布的方式分布在网关周围半径为R的区域中，每个LoRa节点生成数据包的概率服从泊松分布，平均信息生成率为λ，同时忽略该小区存在的外部干扰，系统场景如图1所示。

图1 系统场景

本文使用信息接收率(Data Extraction Rate，DER)作为性能指标，其定义为接收到的消息与发送的消息在一段时间的比率。直接求解最大信息接收率过于困难，故本文将问题转化为如何分配参数得到最大平均传输成功率，其中每个节点的传输成功率为

(10)

通常认为使用相同SF的所有节点都被视为相互干扰，但考虑到捕获效应，可以对模型进行如下优化：

Cij表示使用相同的SF节点j是否会和节点i发生碰撞：

(11)

(12)

Ni始终小于或等于使用SF的节点总数。根据LoRa接收特性，仅当接收信号强度大于接收灵敏度时才可以接收到数据包。本文将接收灵敏度作为约束系数来约束扩频因子和带宽的选择，使得节点可以保证在数据可达网关的同时分配最佳参数，从而获得更好的可靠性：

(13)

表1 接收阈值[17]

带有约束系数的节点平均传输成功率及约束条件如下：

(14)

(15)

由公式(1)～(7)可知，较小的SF和较大的BW可以得到较大的传输速率，从而缩短传输时间；另一方面，较大的SF和较小的BW可以获得较高的灵敏度，但传输速率较低。故本文求解的是一种非线性规划问题，接收功率、冲突节点数以及传输时间三者之间相互制约，最优解需要遍历所有可能的分配方式，复杂度过高。因此，采用烟花爆炸式混合蛙跳算法寻找次优的分配方案来降低复杂度。

2 烟花爆炸式混合蛙跳算法

文献[18-19]的研究表明，混合蛙跳算法能够有效地解决函数优化问题，然而算法在求解过程中也存在易早熟、易陷入局部最优等不足。为了解决非线性规划问题，本文通过对SFLA进行改进，提出了一种自适应烟花爆炸式混合蛙跳算法。

2.1 混合蛙跳算法

SFLA是对青蛙群体在湿地上跳动觅食行为的一种模拟，通过青蛙个体间的合作与竞争在多维空间中实现对最优解的搜索。SFLA首先在可行域内生成N只青蛙构成初始群体，每一只青蛙都代表一个解，第i只青蛙代表问题的解为Xi=(xi,1,xi,2,…,xi,n)，其中n为解的维数。求解每只青蛙的目标函数初始值f(Xi)，将每只青蛙的初始值按递减顺序排序，再将青蛙群划分成m个种群，每个种群含k只青蛙。对每个种群，将目标初始值最优解记为Xbest，最差解记为Xworst，而在整个青蛙群体中将函数最优解记为Xg。在算法迭代中，只对族群中的Xworst进行更新，其策略为

d=rand·(Xbest-Xworst)，

(16)

(17)

当每个种群都完成一轮内部进化后，将各个种群中的个体进行混合，并重新排序分组，再进行局部搜索。重复上述操作，直到满足停止条件。

2.2 自适应烟花爆炸式混合蛙跳算法

结合本文的待优化的场景，为了提高算法在离散空间的搜索效率，对基本的混合蛙跳算法引入反向学习、烟花爆炸、高斯变异算子和欧氏距离分配种群等操作，提高算法的搜索性能。

2.2.1 反向学习初始化

由于SFLA的初始解和最优解离得很远，所以迭代次数会很多。而且在局部搜索中，种群中的青蛙个体不能广泛分布，造成算法的全局搜索能力大大降低。针对这些情况，引入反向学习，即加入反向解初始化种群，使青蛙种群具有多样性。Xi=(xi,1,xi,2,…,xi,n)的反向解定义如下：

(18)

2.2.2 烟花爆炸机制

SFLA容易出现种群多样性不足的现象，容易受到局部最优解的束缚。为了增加算法进化过程中的种群多样性，本文引入烟花爆炸机制，其思想源自烟花算法。烟花算法受夜空中烟花爆炸启发，通过烟花爆炸产生火花，从而达到增加种群多样性的目的。烟花爆炸机制只在算法陷入瓶颈时再进行干预，即当青蛙种群中Xg超过m代没有更新时，再通过烟花爆炸机制产生子代青蛙，并将最优个体保留至下一代。

在父代青蛙周围产生子代青蛙数量如下：

(19)

式中：Si是由Xi产生的子代青蛙数量；fg是当前青蛙种群中适应度最大值；ε是为避免除零操作设置的常数；Smax为常数，用来调整产生子代青蛙的数目。

产生子代青蛙的搜索半径如下：

(20)

式中：Ai是由Xi产生子代青蛙的搜索半径；fb是当前青蛙种群中适应度最小值；ξ是为避免除零操作设置的常数；Amax为常数，用来调整搜索半径。

根据上述自适应烟花爆炸机制产生的子代个体，与父代青蛙进行对比，若优于父代，则更新当前青蛙，否则不更新。

2.2.3 欧氏距离分配种群

在原始SFLA算法中对青蛙分群按其适应度值的高低进行分配。结合本文的编码规则，该方法的不足可能会使得相距较远的个体分在同一个种群中，从而使迭代的距离较大，使一部分更新后的个体超出编码范围(无效解)，影响算法的更新效率，因此本文引入欧氏距离对青蛙划分种群。新的分配规则如下：

(1)在群体内找到适应度值最好的青蛙Xg；

(2)在群体中挑选与青蛙Xg距离最近的p-1只青蛙，将Xg与挑选出的p-1只青蛙组成一个种群；

(3)在种群中除去已挑选过的p只青蛙；

(4)重复(1)～(3)，直到所有青蛙都分配到属于自己的种群，每个种群的青蛙数量为p。

2.2.4 高斯变异算子

SFLA算法迭代过程中的进化能力主要依靠最差个体和最优个体之间的相互作用，与其他群体智能算法不同的是算法本身不具备变异机制，这就导致当算法陷入局部最优解时没有变异机制很难走出局部最优解的陷阱，算法只在局部最优解附近搜索，使整体种群多样性降低。本文在SFLA更新最差个体时引入高斯变异，新的更新策略如下：

(21)

式中：N(0,1)为标准高斯分布。高斯变异产生的个体会和距离迭代产生的个体进行竞争，并保留适应度值较好的个体。

2.3 烟花爆炸式混合蛙跳算法主要步骤

2.3.1 个体编码

假设种群中有N只青蛙，需要优化的场景中共有n个节点，每一只青蛙都代表一个解，第i只青蛙代表的解为Xi=(xi,1,xi,2,…,xi,n)，xi,j(j∈n)代表节点j的参数配置。由式(15)可知,待分配的参数SF和BW共18种组合，故xi,j∈[0,17],xi,j∈。同时按照传输时间Ts升序排列，传输时间越长，编码越大。具体编码见表2。

表2 编码表

2.3.2 算法流程

烟花爆炸式混合蛙跳算法主要思想如下：首先，通过反向学习生成初始种群；其次，判断是否达到烟花爆炸条件；然后，根据欧氏距离分配种群；最后，引入高斯变异算子，更新最差青蛙的位置。其搜索过程如图2所示。

图2 算法流程

3 仿真结果与性能分析

本文在Python3.6平台上使用上述烟花爆炸式混合蛙跳算法对目标函数进行仿真分析，参数设置如表3所示。

表3 算法仿真参数

为了验证本文提出的算法有效性和优越性，将本文算法与传统混合蛙跳算法、粒子群算法[12]和遗传算法[11]进行对比。图3展示了半径R=1 000 m、节点个数为100和500场景下的不同算法适应度函数曲线，可以看出本文提出的算法相较于混合蛙跳算法、粒子群算法和遗传算法具有更高的收敛精度，相同场景下适应度值高2%～5%；同时相较于传统混合蛙跳算法具有更高的初始值。

(a)节点个数为100

(a)节点个数为500图3 适应度值与迭代次数关系曲线

从图3还可看出，本文算法相较于另外三种算法不易陷入局部最优解。这是因为粒子群算法局部搜索能力较差，粒子移动搜索行为不够精细，往往会错过全局最优目标值，导致算法早熟收敛，这时粒子的速度几乎为零，都聚合在一起。虽然此时粒子距离全局最优解不远，但是几乎为零的移动速度无法使其跳出局部最优解。同样遗传算法在面对高维复杂问题时局部搜索能力较差，单纯的遗传算法比较费时，在进化后期搜索效率较低，容易产生早熟收敛的问题。而传统混合蛙跳算法由于进化主要靠种群间的相互作用，容易出现早熟、陷入局部最优的现象。经过改进后的算法在寻优过程中不断进化直到收敛，当算法陷入瓶颈时引入烟花爆炸机制，在适应度值越好的青蛙周围产生越多的子代青蛙，引导算法向包含全局最优的解空间逼近，避免陷入局部优化，虽然其收敛速度没有粒子群算法和遗传算法快，但是换取了更好的收敛精度。

为了验证本文算法分配的参数是否有效，使用基于LoRaSim的仿真平台进行仿真测试。按照算法已分配好的参数，计算一个小时里小区内LoRa节点的信息接收率，并与混合蛙跳算法、粒子群算法、遗传算法和ADR算法分配结果进行对比。如图4所示，本文算法分配的结果高于混合蛙跳算法、粒子群算法和遗传算法5%～10%，相较于ADR提高了40%～50%的信息接收率。

图4 信息接收率与节点个数关系曲线

本文算法相较于传统的ADR算法，信息接收率有较大提升，这是因为ADR算法选择参数的思路是选择尽可能小的满足网关接受条件的参数。如图5所示，当单位区域内存在较多节点时，大部分节点参数都集中在SF=7和SF=8，使传输过程中碰撞概率大大增加，而本文算法通过优化带有惩罚系数的平均传输成功率函数，合理分配每种扩频因子数量，能显著提高每个节点的传输成功率。

图5 分配结果

4 结 论

为了改善LoRa传输过程中的干扰冲突问题，本文提出了一种基于烟花爆炸式混合蛙跳算法的LoRa网络参数分配策略。在SFLA算法的基础上，加入反向学习机制提升算法的全局搜索能力；加入高斯变异算子提高了算法摆脱局部最优解的能力；使用烟花爆炸机制对个体邻域进行搜索，提高整体种群的多样性，同时引导算法向全局最优解移动，避免陷入局部优化。在目标优化上，以最大化节点平均传输成功率为目标，并将接收灵敏度作为约束系数，使得节点可以保证在数据可达网关的同时分配最佳参数。仿真结果表明本文提出的算法相较于其他算法具有更好的收敛精度，同时本文算法分配结果比传统ADR策略具有更高的信息接收率，能显著减少传输过程中的碰撞概率。实际应用中，在高密度节点场景下，可在满足LoRa节点传输距离的前提下，通过本文提出的策略分配LoRa网络参数，提高信息传输成功率，有效改善传输过程中的干扰冲突问题。