基于改进K-medoids算法的土壤墒情传感器布局优化

汪 涛 张 武,2* 苗犇犇 刘 波 王瑞卿 张立付徐少翔 饶 元,2 江朝晖,2

(1.安徽农业大学 信息与计算机学院，合肥 230036； 2.智慧农业技术与装备安徽省重点实验室，合肥 230036)

土壤墒情传感器(Soil moisture sensor，SMS)的选取和布置直接影响灌溉系统的决策和系统成本。SMS通常采用均匀分布，但若农田形状不规则，均匀分布实施起来比较困难；此外，如果传感器均匀分布的太稀疏，传感器网络不能全覆盖，反之极大增加了数据冗余度。SMS布局优化是一个多目标决策问题，采取的布点方法不仅要让传感器能覆盖整个区域，保证传感器数据全面准确，也要考虑各种性能约束和成本约束，同时还要考虑数据的冗余度。

传感器布局优化方法广泛应用于设备故障检测、结构健康监测，航空航天等领域，在节水灌溉系统中SMS布局方法的研究比较少见。李飚等提出基于Delaunary三角剖分的传感器布点方法以实现全方位的布点监测，对于墒情变化剧烈的区域能更好地实现传感器网络全覆盖；吴振宇等提出基于遗传算法的SMS优化布局策略，以传感半径和传感器成本为约束条件，提高传感器覆盖率，降低传感器成本；Mukherjee等采用了重新称重的方法替换重复函数模拟以估计期望影响值，并提出了一种用于非线性不确定系统传感器放置的模式分析方法；这些研究只考虑到覆盖算法的优化却未涉及土壤墒情数据冗余问题，而在传感器实际监测中，会产生大量的冗余数据，一方面是因为物理现象的连续性，同一节点一段时间内的采样数据之间具有较高的时间相关性，另一方面是因为根据Miller提出的“地理学第一定律”，无线传感器网络中传感器节点在相邻地理区域采集数据，物理参数具有连续性和相似性，使得相邻节点的监测数据具有空间相关性。为此，李泳霖等研究了同一土壤剖面不同深度的墒情的相关性，优化了传感器埋设的数量；张瑞瑞提出了基于网络节点四叉树编码的数据聚合方法，其对土壤湿度的无损聚合率为33.34%；贾玉生等提出了基于压缩感知的传感器布局优化方法，改进了现有的稀疏随机测量矩阵，以确定给定区域所需的传感器数量和每个传感器的具体位置函数，该方法只适合于数据波动小的环境。Rossini等提出了基于模糊C均值聚类划分土壤水分管理区并采用轮廓聚类评价方法确定最佳土壤水分管理区，从而确定传感器部署的最佳数量和位置；张武等提出基于AP聚类算法的SMS布局策略降低了系统成本和数据冗余度，但这些研究只考虑了单一天气条件下的聚类结果。K-medoids聚类算法在无线传感器网络节点分簇中有所应用，王宗山等将遗传算法与K-medoids算法结合；Wang等将近邻传播算法与K-medoids算法结合提出能量高效的分簇路由协议，综合考虑簇内节点的剩余能量、地理位置等因素选举簇首,使簇首节点分布均匀,均衡网络能耗，谱排直算法常用于生物信息学领域；胡军等基于谱排直算法衡量蛋白质序列的相似度；徐伟提出将谱排直算法与层次聚类结合实现对时间序列形式的基因芯片数据聚类。

本研究拟采用基于改进K-medoids算法的SMS布局方法，确定传感器最佳部署位置并剔除冗余传感节点，以期为灌溉系统的建立节约成本，为灌溉系统的决策提供可靠依据。

1 数据来源与研究方法

1.1 数据来源

数据采集于安徽农业大学国家高新技术农业园一块长约80 m，宽约40 m的茶园(北纬31°56′11″，东经117°11′48″)。试验采用无线传感网络传输数据，经过测试无线传感网络的可靠传输距离约为15 m，为保证无线传感网络全覆盖，横向和纵向均选择10 m的间隔布置传感器。数据采集点分布见图1。

Am、Bm、Cm、Dm(m=1,2,…,8)为数据采集点,虚线圆圈为传感范围。Am, Bm, Cm and Dm (m=1,2,…,8) are the data collection points, and the dashed circles are the sensing range.图1 茶园数据采集点分布Fig.1 Distribution of tea plantation data collection points

使用浙江托普云农科技股份有限公司的TZS型土壤墒情测定仪采集土壤相对含水率数据，该仪器基于介电理论并运用频域测量技术研制开发，能够精确测量土壤和其他多孔介质的体积含水量，测量范围为0%～100%，测量精度为±3%。

于2018-07-01—2018-08-15，每隔2天采集1次25 cm深度的土壤墒情数据；于2020-12-17—2020-12-31，每隔1天采集1次茶园25 cm深度的土壤墒情数据。各数据采集日天气情况见表1。

表1 数据采集日天气情况
Table 1 Weather conditions of the data collection day

日期Dates天气Weather温度/℃Temperature日期Dates天气Weather温度/℃Temperature日期Dates天气Weather温度/℃Temperature2018-07-01小雨～多云26～322018-07-25多云27～382020-12-17多云～阴0～72018-07-04小雨27～332018-07-28雷阵雨～多云27～352020-12-19晴-4～72018-07-07小雨25～312018-07-31雷阵雨～多云26～352020-12-21晴-4～102018-07-10阴～多云26～322018-08-03中雨24～322020-12-23阴～多云0～112018-07-13多云28～352018-08-06多云27～352020-12-25多云～阴2～122018-07-16多云27～362018-08-09多云～晴27～382020-12-27小雨～晴2～132018-07-19晴26～372018-08-12多云～雷阵雨27～372020-12-29中雨～晴-7～52018-07-22小雨26～342018-08-15多云26～342020-12-31小雪～晴-7～1

试验区域的土壤为土层较厚的黄棕壤，含沙量小，黏粒含量达到20%，为黏质土类，具有渗水速率慢，保水性能好，通风效果一般的特征。采集各布点25 cm深度的土壤，并用环刀法测定土壤的孔隙度，孔隙度的平均值为45.52%，标准差为1.7%，该区域土壤具有较好的均一性。试验区域的地势呈中间高，四周低，最大落差约为2.8 m，坡度约4°。

1.2 研究方法

1

.

2

.

1

K

-

medoids算法简介

K-medoids是一种典型的基于划分的无监督聚类算法，是对K-means算法的优化，二者都通过随机方式初始化聚类中心。K-medoids每一次迭代都从样本中选取新的中心点，选取的标准不是直接将样本均值作为新的聚类中心，而是尝试遍历当前簇内所有样本点并计算其到簇内其他点距离之和，选择最优的样本点作为新的中心点，所以它比K-means更为鲁棒，对孤立数据和“噪声”不敏感。K-medoids聚类算法中用欧氏距离定义相似度的方法对于时间序列类型数据的聚类并不合适，因此基于谱排直算法定义新的适合时间序列数据的相似度函数再结合K-medoids进行聚类。

1

.

2

.

2

谱排直

谱排直算法最先由Bari等提出，应用于基因芯片数据的聚类中，算法的思想是竖直地移动2个谱，使移动后的2个谱均方误差取到最小。

设数据集={,,…,}，其中=[

x

1,

x

2,…,

x

]是一个

t

维的特征向量，代表传感器

i

在

t

个时间点上的值，把分为

k

个不相交的子集,,…,，其中=∪∪…∪，且∩=∅，对∀

i

,

j

,

i

≠

j

。设,∈，简单谱排直的目的是找出新的向量使得取最小值，最小化

f

(

a

)得到Ntmanul等对简单谱排直做出改进，首先用分段线性函数或者三次样条函数将数据拟合成连续函数。给定谱

x

(

t

)和

y

(

t

)，要求是分段线性函数或者连续可积函数，谱排直的含义就是把

y

(

t

)朝着

x

(

t

)进行竖直移动，使谱之间的误差平方积分为最小值。是移动后的

y

(

t

)，定义域

t

∈(0,

L

)内，

x

(

t

)和之间的面积表示谱之间的误差，

a

为

y

(

t

)竖直平移的距离。对

x

(

t

)和

y

(

t

)进行谱排直，即找到最优的

a

，使式(1)取得最小值：

f

(

x

,

y

)=[

x

(

t

)-[

y

(

t

)-

a

]]d

t

(1)

对

a

求一次导数得：

(2)

令得到：

(3)

因为

f

(

x

,

y

)的二阶导数>0，所以

a

为最小值。因而，存在唯一的移动变量

a

，使得误差平方积分取最小值。

x

(

t

)和移动后的

y

(

t

)的误差积分为：
[

x

(

t

)-

y

(

t

)]d

t

+

a

L

=0

(4)

基于谱排直的数据预处理，本研究提出时间序列数据距离函数：

dis(

x

,

y

)=

f

(

a

)+|

a

L

|=
[

x

(

t

)-[

y

(

t

)-

a

]]d

t

+|

a

|

L

(5)

式中：

f

(

a

)为平移后样本间误差平方积分，可以衡量样本变化趋势差异的大小；|

a

|

L

为其中一条曲线平移走过的面积，可以衡量样本数值上差异的大小。将二者求和作为衡量时间序列数据相似度的尺度，并结合K-medoids算法，替换该算法中原先的相似度函数即多维空间欧氏距离，对采集的茶园土壤墒情数据进行聚类。

1

.

2

.

3

改进K

-

medoids算法基本原理及流程

改进K-medoids综合算法的流程见图2，具体步骤如下。

图2 改进K-medoids算法流程图Fig.2 Flow chart of improved K-medoids algorithm

步骤1：利用三次样条插值的方法将离散数据拟合成连续函数，也即将样本集={,,…,}拟合为谱集(

t

)={

x

(

t

),

x

(

t

),…,

x

(

t

)}。步骤2：对任意2个谱

x

(

t

)，

x

(

t

)进行排直操作，由式(1)～(3)求出

x

(

t

)最优平移距离

a

使得2个排直后谱的误差平方积分取得最小值。步骤3：由式(5)求出

x

(

t

)，

x

(

t

)之间的谱距离。步骤4：初始化数据样本，通过“手肘法”确定最优簇的个数

K

。步骤5：基于方差优化初始中心的方法从样本选择

K

个传感器布点作为初始聚类中心。

步骤6：计算传感器节点到每个聚类中心的谱距离并进行比较，将其分配到最近的簇中。

步骤7：选择到簇内其他传感器布点距离之和最短的传感器作为新的簇中心。

步骤8：当簇中心点不发生变化或迭代次数达到1 000，聚类结束，否则返回步骤6。

2 结果与分析

根据采集的土壤墒情数据，运用克里金插值法对试验区域其他点的墒情值进行预测，图3示出的2018-07-25和2020-12-25茶园土壤相对含水率空间分布。可见，该茶园四周相对含水率高，中间相对含水率低，

B

、

C

、

B

、

C

附近表现为明显的凹点，凹点位置与该区域的海拔高点基本重合。因此，初步判断该区域的土壤相对含水率空间分布差异主要受到地形结构的影响。

图3 茶园土壤相对含水率空间分布Fig.3 Spatial distribution of soil relative moisture content in tea plantation

针对同一片茶园不同时期采集的土壤墒情数据进行2次试验，采用改进前和改进后的K-medoids方法对2018-07—2018-08(试验Ⅰ)和2020-12(试验Ⅱ)采集的土壤墒情数据进行聚类，分析2次试验聚类结果的一致性和代表性以说明本研究提出方法的有效性。

通过“手肘法”得到误差平方和(Sum of the squared errors，SSE)与聚类簇数

K

的关系从而确定最优簇数，试验Ⅰ和试验Ⅱ中SSE随

K

的变化趋势见图4。

K

值从1增大到4时，SSE值急剧下降，

K

值大于4时，SSE值下降平缓，最优簇个数为4，在此基础上利用方差优化初始聚类中心。

图4 试验Ⅰ、试验Ⅱ的聚类误差与聚类簇数的关系Fig.4 The relationship between the clustering error and the number of clusters in experiments Ⅰ and Ⅱ

在K-medoids聚类计算过程中，迭代次数设为1 000，试验Ⅰ与试验Ⅱ的聚类结果见表2：32个布点被聚成4个簇

P

、

P

、

P

、

P

，簇中心分别为

A

、

A

、

C

、

C

。

表2 K-medoids聚类结果
Table 2 Results of K-medoids clustering

簇名Clustername簇中心Clustercenters簇内节点ClustermembersP1A5A4,A5,B2,B8,C1,C3,C5,C7P2A7A1,A2,A7,A8,B1,C1,D1,D2,D3,D5,D6,D7,D8P3C4B3,B4,B5,B6,B7,C2,C4P4C8A3,A6,C6,C8,D4

试验Ⅰ和试验Ⅱ使用K-medoids聚类所得各簇中心相对含水率与簇平均相对含水率的变化分别见图5和图6，各簇中心相对含水率与簇平均相对含水率的相对偏差分别见表3和表4。

P1,P2,P3,P4为32个布点由K-medoids聚成的4个簇，图6同。P1, P2, P3 and P4 are four clusters of 32 distribution points clustered by K-medoids. The same in Fig.6.图5 试验Ⅰ由K-medoids得到的各簇中心相对含水率及簇平均相对含水率Fig.5 The relative moisture content of each cluster center and the average relative moisture content of clusters obtained by K-medoids in experiment Ⅰ

图6 试验Ⅱ由K-medoids得到的各簇中心相对含水率及簇平均相对含水率Fig.6 The relative moisture content of each cluster center and the average relative moisture content of clusters obtained by K-medoids in experiment Ⅱ

表3 试验Ⅰ由K-medoids得到的各簇中心相对含水率与簇平均相对含水率的相对偏差
Table 3 The relative bias between the relative moisture content in the center of each cluster and the average relative moisture content of the cluster obtained by K-medoids in experiment Ⅰ %

簇中心Clustercenter日期(2018年) Date (2018)07-0107-0407-0707-1007-1307-1607-1907-2207-2507-2807-3108-0308-0608-0908-1208-15A5-3.19-3.143.033.146.325.98-0.620.571.351.37-3.16-2.921.420.741.871.83A7-0.59-0.58-5.11-5.28-4.93-4.71-6.04-5.61-4.70-4.77-5.83-5.374.204.792.192.15C4-2.77-2.72-2.42-2.52-3.63-3.472.213.832.652.70.980.90.62-0.590.92-0.90C8-1.28-1.27-1.461.021.196.293.182.763.994.05-1.28-1.184.482.732.842.54

表4 试验Ⅱ由K-medoids得到的各簇中心相对含水率与簇平均相对含水率的相对偏差
Table 4 The relative bias between the relative moisture content in the center of each cluster and the average relative moisture content of the cluster obtained by K-medoids in experiment Ⅱ %

簇中心Cluster center日期(2020年) Date (2020)12-1712-1912-2112-2312-2512-2712-2912-31A52.141.472.391.120.372.220.340.98A70.343.113.832.882.462.784.551.25C41.891.532.411.571.532.290.340.33C81.013.194.834.421.830.371.003.54

在改进K-medoids聚类计算过程中，迭代次数设为1 000，试验Ⅰ与试验Ⅱ聚类结果见表5。32个布点被聚成4个簇

S

、

S

、

S

、

S

，簇中心分别为

B

，

C

，

D

，

D

。

表5 改进的K-medoids聚类结果
Table 5 Results of improved K-medoids clustering

簇名Cluster name簇中心Cluster center簇内节点Cluster memberS1B2A4,A5,A6,B1,B2,B3,B8,C1,C3,C5,C6,C7,C8,D3,D4,D5S2C4B4,B5,B6,B7,C2,C4S3D6A1,A2,A3,D2,D6,D7S4D8A7,A8,D1,D8

试验Ⅰ和试验Ⅱ使用改进K-medoids聚类所得各簇中心相对含水率与簇平均相对含水率的变化分别见图7和图8，各簇中心相对含水率与簇平均相对含水率的相对偏差分别见表6和表7。

S1,S2,S3,S4为32个布点由改进的K-medoids聚成的4个簇，图8同。S1, S2, S3, S4 are four clusters of 32 distribution points clustered by improved K-medoids. Same as Fig.8.图7 试验Ⅰ由改进的K-medoids得到的各簇中心相对含水率及簇平均相对含水率Fig.7 The relative moisture content of each cluster center and the average relative moisture content of clusters obtained by improved K-medoids in experiment Ⅰ

图8 试验Ⅱ由改进的K-medoids得到的各簇中心相对含水率及簇平均相对含水率Fig.8 The relative moisture content of each cluster center and the average relative moisture content of clusters obtained by improved K-medoids in experiment Ⅱ

表6 试验Ⅰ由改进的K-medoids得到的各簇中心相对含水率与簇平均相对含水率的相对偏差
Table 6 The relative bias between the relative moisture content in the center of each cluster and the average relative moisture content of the cluster obtained by improved K-medoids in experiment Ⅰ %

簇中心Clustercenter日期(2018年) Date (2018)07-0107-0407-0707-1007-1307-1607-1907-2207-2507-2807-3108-0308-0608-0908-1208-15B21.711.681.57-1.17-4.23-1.32-4.11-3.80-0.38-0.38-1.28-5.841.373.08-4.16-4.08C4-0.59-0.58-0.43-0.45-2.01-1.931.173.152.352.38-0.57-0.53-1.41-1.35-2.64-2.59D61.511.49-0.93-0.96-0.51-0.50-0.81-0.75-1.53-1.55-1.20-3.272.342.25-6.30-6.23D8-0.77-0.760.121.991.24-0.661.022.861.701.732.082.241.753.981.591.36

根据表3和表6结果计算可知：试验Ⅰ中K-medoids得到的各簇中心(

A

、

A

、

C

、C)相对含水率与簇均值相对偏差(绝对值)的平均值分别为2.54%，4.18%，2.11%和2.60%；改进K-medoids得到的各簇中心(

B

、

C

、

D

、

D

)相对含水率与簇均值相对偏差(绝对值)的平均值分别为2.51%、1.51%、2.01%、1.62%，后者比前者的相对偏差(绝对值)减少0.94%。由表4和表7结果计算可知：试验Ⅱ中K-medoids得到的各簇中心(

A

、

A

、

C

、C)相对含水率与簇均值相对偏差(绝对值)的平均值分别为1.38%，2.65%，1.49%和2.52%；改进K-medoids得到的各簇中心(

B

、

C

、

D

、

D

)相对含水率与簇均值相对偏差(绝对值)的平均值分别为2.23%、0.94%、1.15%、1.38%，后者比前者的相对偏差(绝对值)减少0.58%。

表7 试验Ⅱ由改进的K-medoids得到的各簇中心相对含水率与簇平均相对含水率的相对偏差
Table 7 The relative bias between the relative moisture content in the center of each cluster and the average relativemoisture content of the cluster obtained by improved K-medoids in experiment Ⅱ %

簇中心Cluster center日期(2020年) Date (2020)12-1712-1912-2112-2312-2512-2712-2912-31B21.772.543.031.850.362.923.082.27C40.380.391.621.571.150.380.691.32D61.260.670.680.371.070.700.983.49D80.691.050.711.441.042.761.891.47

根据Zhang M M 等提出的基于改进蚁群算法的SMS布局优化方法和基于改进Dijkstra算法的SMS布局优化方法，分别计算以2组聚类中心为起点，以边界点为路由终点(

A

处)的传感器布点路径长度和路径上的传感器数量，经过

A

、

A

、

C

、

C

的布点路径长度为106.5 m，需要10个传感器，经过

B

、

C

、

D

、

D

的布点路径长度为82.4 m，需要个传感器。因此，

B

、

C

、

D

、

D

更适合作为该茶园SMS的布点。为验证试验Ⅰ的聚类结果，于2018-11-13—2018-12-08采集了7天簇中心和随机选取的13个验证点(图9)的相对含水率，并对二者相对偏差进行分析，结果见表8。可见，相较于

A

、

A

、

C

、

C

，

B

、

C

、

D

、

D

相对含水率的平均值与13个随机采样点相对含水率平均值更为接近，相对偏差最大为1.8%；为了验证试验Ⅱ的聚类结果，于2021-06-28—2021-07-03采集了3天簇中心和随机选取的15个验证点(图10)的相对含水率，结果表明，相较于

A

、

A

、

C

、

C

，

B

、

C

、

D

、

D

相对含水率的平均值与15个随机采样点相对含水率平均值更为接近，相对偏差最大为1.13%(表9)。综上，在试验区选择

B

、

C

、

D

、

D

4个点布置SMS，测定的值能够反映茶园土壤墒情的整体状况。

表8 试验Ⅰ各簇中心点和验证点的相对含水率平均值以及二者的相对偏差
Table 8 Average relative moisture content of clusters centers and verification points and their relative bias in experiment Ⅰ %

日期DateK-medoids所得簇中心Cluster center by K-medoidsImproved K-medoids所得簇中心Cluster center by improved K-medoids验证点Verificationpoints相对偏差Relative biasA5A7C4C8μ1B2C4D6D8μ2μ3δ1δ22018-11-1328.132.326.830.729.4828.426.830.731.229.2828.961.781.092018-11-1529.434.730.332.631.7532.230.334.635.433.1332.54-2.431.802018-11-1928.833.228.531.830.5829.728.531.433.930.8831.38-2.57-1.612018-11-2327.430.725.730.128.4827.925.729.232.728.8829.31-2.85-1.482018-11-2826.629.523.828.227.0325.923.828.531.827.5027.80-2.79-1.082018-12-0333.537.331.437.534.9333.231.436.238.634.8534.251.971.752018-12-0837.441.634.838.538.0837.934.840.541.438.6539.15-2.75-1.28

注：、、分别为K-medoids所得簇中心、Improved K-medoids所得簇中心、验证点的相对含水率平均值；、分别为与、与的相对偏差。
Note: , , are the average relative moisture content of K-medoids cluster centers, Improved K-medoids cluster centers and verification points in experiment I; , are the relative bias of and , and respectively.

图9 为验证试验Ⅰ结果随机选取的13个验证点Fig.9 13 randomly selected verification points for verifying the results of experiment Ⅰ

表9 试验Ⅱ各簇中心和验证点的相对含水率平均值以及二者的相对偏差
Table 9 Average relative moisture content of clusters centers and verification points and their relative bias in experiment Ⅱ %

日期DateK-medoids所得簇中心Cluster center by K-medoidsImproved K-medoids所得簇中心Cluster center by improved K-medoids验证点Verificationpoints相对偏差Relative biasA5A7C4C8μ4B2C4D6D8μ5μ6δ3δ42021-06-2837.640.738.939.739.2339.838.941.242.740.6540.32-2.720.822021-07-0136.240.137.638.138.0038.437.639.741.339.2538.87-2.240.982021-07-0340.145.443.841.242.6345.343.841.940.742.9343.42-1.83-1.13

注：、、分别为K-medoids所得簇中心、Improved K-medoids所得簇中心、验证点的相对含水率平均值；、分别为与、与的相对偏差。
Note: , , are the average relative moisture content of K-medoids cluster centers, improved K-medoids cluster centers and verification points in experiment I, respectively. and are the relative bias of and , and , respectively.

图10 为验证试验Ⅱ结果随机选取的15个验证点Fig.10 15 randomly selected verification points for verifying the results of experiment Ⅱ

3 结 论

本研究提出一种基于改进K-medoids算法的SMS优化布局策略并应用于茶园SMS布局优化的实际问题中。针对不同时期采集的茶园土壤相对含水率数据使用K-medoids和改进的K-medoids进行聚类，改进的K-medoids算法所得簇中心相对含水率与簇均值相对偏差相较于改进前降低了约30%；改进的K-medoids聚类结果具有较强的稳定性，多种天气条件下的所得聚类中心相对含水率平均值与随机点相对含水率平均值的相对偏差(绝对值)都较小(不超过2%)，说明谱排直算法定义的谱距离将时间尺度考虑进去，相较于用欧氏距离衡量时间序列数据相似性更为适合；K-medoids易与其他算法融合，对于农业中其他传感器的布局问题也可提供有益的参考。本研究也有其局限性，试验数据的采集时间短，跨度小，土壤性质单一，后期将不断扩充数据量，扩大时间跨度，在不同的特性的土壤上进行试验，提高方法的通用性。