考虑无线传输损耗的农业物联网节点分布规划算法研究

谢家兴 梁高天 高 鹏 王卫星,3

(1.华南农业大学电子工程学院， 广州 510642； 2.广东省智慧果园科技创新中心， 广州 510642；3.广东省农情信息监测工程技术研究中心， 广州 510642)

0 引言

在无线信号传输的过程中，信号不仅会随着传输距离增大而衰减，还会因为地形的高低起伏而存在一定的绕射损耗[1]。然而目前农场物联网节点的选址大多依靠经验，没有综合考虑地形、信号损耗等因素，从而造成了不必要的发射功率浪费。因此设计一种合理的节点选址方法对于延长节点续航，减少电能消耗具有重大意义。

对于类似的规划问题，常见的解决方法有蚁群算法[2]、粒子群算法[3]等群智能算法，也有Bug算法[4]、A*算法[5]、Dijkstra算法等图搜索算法，以及聚类算法[6]等无监督学习方法。

在无线节点的选址上，文献[7]基于基站选址优化问题的约束条件构建一种基站选址优化模型,该模型使用鲸鱼优化改进算法，仿真发现算法能够获得更理想的优化解,且具有较快的收敛速度。文献[8]通过把单跳Sink节点选址问题转换为区间数学全局寻优问题,结合粒子群算法与质心理论，提出了质心重选址算法，实现了多Sink节点的最优化选址。文献[9]将人工鱼群算法应用到基站选址规划上,提出了变步长的人工鱼群算法，仿真发现该算法只需要更少的待建基站数目就能满足覆盖95%以上的目标。

然而目前已有文献在节点的选址问题上很少考虑信号传输过程中的损耗问题，尤其是由于地形因素导致的绕射损耗，因此本文提出一种结合K-means聚类算法以及粒子群优化(Particle swarm optimization，PSO)算法的物联网节点选址方法。该方法通过K-means算法确定每个路由的管辖终端以及初始位置，根据电磁波损耗模型建立合适的适应度函数，利用PSO算法得到路由节点的最终位置，再次使用K-means算法确定每个网关的管辖路由以及初始位置，通过PSO算法确定网关的最终位置。

1 物联网系统概述

农场无线物联网一般包括终端、路由以及网关3种节点，其拓扑结构如图1所示。终端节点负责采集温湿度等环境信息以及控制电磁阀等设备的工作；路由节点是网关与终端之间通信的桥梁，用于转发网关对终端的下行指令以及终端到网关的上行信息，一个路由对接在它附近的多个终端；网关节点负责把终端采集到的数据通过4G等方式上传到后台服务器，以及接收来自服务器的控制指令并通过路由传达给终端，一个网关对应多个路由。

图1 农业物联网拓扑结构Fig.1 Topology of agricultural internet of things

在农场物联网节点的铺设中，一般需要安装3种节点：终端节点、路由节点与网关节点。为了方便建模，做如下假设：

(1)终端位置已知。终端需要控制电磁阀的开关与采集农情信息，它的安装位置需要根据场地的实际情况人为决定。

(2)一个终端只能连接到一个路由，终端间不存在任何连接。需要确定每个路由所负责的终端，对终端的分割可以视为一类聚类问题。

(3)聚类中的元素一经确定后不再改变。在确定路由对接的终端后，无论路由位置如何改变，其下属的终端都不会增加或减少。

(4)模型的目标是降低最大通信损耗。最大通信损耗指路由到多个终端或者网关到多个路由间最大的无线传输损耗，只要终端到其所属的路由或者路由到网关的无线传输损耗小于等于最大无线传输损耗，即视为可以通信成功。

(5)网关只有一个，且只能与路由通信，每个路由都必须连接到网关。

2 模型建立

2.1 自由空间损耗

没有任何障碍物的情况下电磁波在自由空间中传播时，会存在自由空间损耗，根据国际电信联盟(International Telecommunication Union，ITU)在2019年发布的关于自由空间损耗的参考计算方法[10]，自由空间损耗计算式为

Lfs=32.44+20lgf+20lgd

(1)

式中Lfs——自由空间损耗，dB

f——电磁波频率，MHz

d——信号发射点与接收点的直线距离，km

2.2 绕射损耗

如果电磁波在传输过程中遇到凸起的障碍物，则会产生绕射损耗，根据ITU于2019年发布的关于绕射损耗的计算方法[11]，绕射损耗的计算存在2种情况，如图2、3所示。

图2 端点水平线在山峰下方Fig.2 Horizontal line below spike

图3 端点水平线在山峰上方Fig.3 Horizontal line above tip

计算几何参数的综合量，其计算式为

(2)

式中v——全部几何参数的综合量，它是一个归一化的、无量纲参数

h——端点的水平连线与峰顶的垂直距离，当端点水平线在山峰上方时(图3)，h为负值，反之为正值(图2)

λ——电磁波波长

d1、d2——障碍物顶部与路径两端间的距离

绕射损耗计算式为

(3)

式中J——绕射损耗，dB

C——复数菲涅尔积分实部

S——复数菲涅尔积分虚部

复数菲涅尔积分结果计算式为

(4)

式中Fc——复数菲涅尔积分结果

s——被积变量

为了计算方便，ITU建议在v大于-0.78时，绕射损耗J的近似值计算式为

(5)

以上仅为一种比较简单的绕射损耗计算方式，有文献表明在林区、丘陵、森林等不同环境中测得的绕射损耗与ITU建议公式的计算结果均有差异[12-16]，本文为了方便展示方法原理，仅使用了比较简单的绕射损耗计算方法，在实际使用时应该根据实际的环境选择合适的绕射损耗计算方法。

2.3 适应度模型

在本模型中，传输损耗的计算主要考虑的是节点发射的电磁波在传播过程中存在的自由空间损耗以及绕射损耗，目的在于减少通信时最大传输损耗，所以设计路由或者网关的适应度方程式为

(6)

其中

(7)

Jp——节点p与管理节点p的终端或网关之间的绕射损耗

Ci——属于第i个路由或网关管理的节点的集合

poslin——正值线性传输函数

由于传输损耗为非负值，当发射点与接收点距离较少时，根据式(1)计算的损耗有可能达到负无穷，为了使PSO算法正常执行，对自由空间损耗添加一个正值线性传输函数。

节点p不止一个，路由或者网关的最大发射功率应该高于最大传输损耗，故用max函数取最大的传输损耗作为适应度。

3 算法设计

3.1 K-means算法

K-means算法[17]是一种无监督的聚类算法，对于给定的样本集，可以按照样本之间的距离，将样本划分为k个簇。该算法用于确定路由节点的初始位置，种子与路由节点的距离采用的是平面距离，其计算方法为

(8)

式中D——种子(即终端)与路由的距离

(x1、y1)——路由坐标

(x2、y2)——终端坐标

在确定好路由的初始位置以及每个路由所负责的终端后，使用PSO算法进行位置优化。

3.2 PSO算法

PSO算法[18]是一种全局优化算法，通过群体中粒子间的合作与竞争产生的群体智能指导优化算法，它可根据对环境的适应度，将群体中的粒子移动到更好的区域，从而实现对函数全局最优的求解。

文献[19]建议在一般情况下将个体认知分量和群体社会分量的权重设置为常数更有利于PSO算法迭代到全局最优点。为了加速PSO算法收敛，参照文献[20]与可变学习率反向传播(Variable learning rate back propagation)算法[21]，设计了可变惯性权重因子算法，该算法在每次迭代后都需要执行一次以获得新的惯性权重因子，该算法的伪代码入：全局最优点是否更新标志，目前的d值，目前的惯性权重因出：新的惯性权重因子，新的d值

Function[new_inertia, new_d] = new_inertia(flag, d, inertia)

If flag == true

new_d= max(0,d-1)

If d<2

new_inertia = inertia*2

If d>5

new_inertia = inertia/2

else

new_d =d+1

new_inertia=inertia

以上算法用变量d记录全局最优位置不更新的次数，当d小于2时，提高惯性权重因子以提高粒子搜索最优点的能力，当全局最优位置大于5次不更新时，减少惯性权重因子以加快算法收敛。

为减少PSO执行时间，设置了最优位置不更新的最大容许时间，如果已知最优位置超过此容忍时间没有更新时，退出PSO算法的执行，取当前最优结果作为最终优化结果。

3.3 本文算法使用步骤

本文算法使用步骤为：①对农场地形进行建模，得到地形描述函数。②根据地形描述函数，依据终端实际的分布得到终端坐标。③根据实际情况确定路由部署数量以及网关部署数量。④利用K-means聚类算法对终端进行分组，取每组的中心作为路由的初始中心。⑤针对每组终端，在该组的初始中心附近初始化若干个粒子，通过式(6)得到适应度函数，利用PSO算法确定路由的最终位置。⑥初始化若干个粒子，通过式(6)得到适应度函数，利用PSO算法确定网关的最终位置。

4 仿真分析

4.1 仿真参数

4.1.1地形描述函数

仿真使用的地形描述函数为

(-500 m≤x≤500 m,-500 m≤y≤500 m)

(9)

式中 terr(x,y)——坐标(x,y)处的地形高度

该描述函数对应地形的立体图如图4所示。

图4 仿真地形立体图Fig.4 Three-dimensional map of simulated terrain

4.1.2波长

目前大部分的物联网节点主要工作在2.4 GHz频段，根据电气与电子工程师协会(Institute of Electrical and Electronics Engineers，IEEE)颁布的标准[22]，该频段的频率范围为2.401～2.495 GHz，为了计算方便，采用其中心频率f(2.448 GHz)进行仿真，则波长为

(10)

式中c——真空中的光速，取3×108m/s

可算得波长约为0.12 m。

仿真的终端数目为500个，它们的位置由系统随机生成，分布在上述地形描述函数的定义域内。路由为5个。

4.1.3PSO算法参数

PSO算法参照文献[23]选择3组参数进行测试，如表1所示。

表1 PSO仿真参数Tab.1 PSO simulation parameters

为了确定PSO算法仿真最终使用的参数，进行预实验，测试每组参数下PSO算法执行所需要的时间，每组测试5次，结果如表2所示。

表2 PSO算法不同参数组耗时测试结果Tab.2 Time-consuming test results of different parameter groups of PSO algorithm s

可见，参数组3的平均耗时显著小于参数组1和参数组2，因此选择参数组3作为PSO算法的参数。

设置PSO算法粒子最大迁移次数为400次；最小容忍迁移距离为10-6m；最优位置不更新的最大容许时间为120 s。当满足以下条件之一时结束PSO算法：①迁移达到400次。②所有的粒子迁移距离小于最小容忍距离。③群体最优位置超过120 s没有更新。

4.2 仿真结果

4.2.1分类

对随机初始化的500个终端使用K-means算法分成5类，结果如图5所示。

图5 K-means分类结果Fig.5 K-means classification results

图5中处在同一聚类中的终端用同一种颜色表示，可见分类结果有明显的分类边界。因为K-means算法存在一定的随机性，所以将该算法运行了10次，取最好的一次进行绘图以及下一步的分析。

4.2.2路由位置优化

使用PSO算法，在图5的聚类中心附近初始化20个粒子，执行算法进行路由位置择优，优化结果如图6所示。

图6 路由位置优化结果Fig.6 Route location optimization results

优化前后各个路由的最大传输损耗如表3所示。可见，通过PSO算法的位置优化，5个路由最大传输损耗均得到了减少，其中路由4的最大传输损耗减少率达到了27.82%。

表3 PSO算法位置寻优结果比较Tab.3 Comparison of PSO algorithm location optimization results

4.2.3网关位置确定

使用PSO算法确定网关位置，先求出到5个路由距离和最小的点，在此点附近初始化20个粒子，执行优化算法，结果如图7所示。优化前后网关的最大传输损耗分别为90.91 dB和89.66 dB，通过优化，最大传输损耗降低了1.37%。

图7 网关的位置Fig.7 Location of gateway

5 实地检验

为了验证算法的有效性，选取华南农业大学园艺教学实验基地作为测试场地，其俯视图如图8所示。

图8 实验场地俯视图(航拍)Fig.8 Top view of experimental site (aerial photography)

5.1 地形建模与通信质量分析

图9 地形采样仪Fig.9 Terrain sampler

为了得到场地的地形情况以便建模分析，自主设计了一款地形采集装置，该装置实物如图9所示，采用RadioLink公司生产的“SE100”GPS定位器获取样点的经纬度，利用GoerTek公司的“SPL06-001”数字大气压力传感器得到样点的高度信息。

地形信息采样后，为了对地形进行分析，取所有样点经纬度的中心为原点，建立直角坐标系，并根据采样点的经纬度得到每个点相对于原点的坐标(x,y)，通过最邻近插值法对地形做数字化建模分析，样点以及建模结果如图 10所示，其中蓝色点为用于地形建模的转换后采样点，曲面为对实验场地进行插值建模的结果，曲面的颜色表示地势高度。

图10 地形采样点以及地形建模结果Fig.10 Terrain sampling points and terrain modeling results

物联网通信模拟测试采用TI公司的CC2530芯片作为信号收发端，使用同一公司旗下的CC2591芯片作为信号功率放大器，通过CC2530芯片接收数据包时返回的接收信号强度指标(Received signal-strength indication，RSSI)评判通信质量,RSSI值越大表示通信质量越好。在实地测试时，把RSSI回传至上述自制地形采样仪，从而得到对应GPS坐标位置的信号强度。

5.2 实验过程与结果

受到实际情况限制，在实地验证时只使用5个终端与1个路由器节点，终端安装到指定位置，实验人员手持采样仪，在算法分析得到的最优点及其附近测量RSSI值，从而验证算法结果的有效性。终端GPS坐标以及算法给出的最佳路由位置如表4所示。

表4 终端与路由的坐标Tab.4 Coordinates of terminal and route

在算法推荐的最优点及其附近，采集路由分别到5个终端的RSSI，共采样160个点，其中最优点及其东南西北2 m处的采样结果如表5所示。

表5 部分测量点RSSI数据Tab.5 RSSI data of some measuring points

可见，最优点到5个终端RSSI的最小值均比其附近的点大，最优点的最小RSSI相比其附近的点提升了12%～20%，说明本文算法可提高无线通信质量。

6 结论

(1)在考虑无线传输损耗的基础上，提出了一种基于K-means聚类算法与PSO算法的农场物联网规划算法，该算法首先对农场建模得到地形描述函数，通过已经部署好的终端的坐标，利用K-means算法得到路由的管辖终端与大概的位置，在考虑地形因素对节点间信号传输影响的前提下，建立了以自由空间损耗和绕射损耗最小化为目标的数学模型，结合PSO算法得到路由和网关的安装位置。

(2)仿真分析发现，该算法有助于为路由与网关的铺设位置提供参考建议，使用PSO算法可以显著降低最大传输损耗，最大减少率为27.82%。实地检验发现，本算法所选取的最优点通信质量显著高于其附近的点，RSSI提升了12%～20%。

(3)对于地表覆盖物的不同，绕射损耗的实际值与ITU推荐的理论值有差别，因此在实际应用中，应根据地表覆盖物的种类对绕射损耗的计算方法进行改进。