汪 濤 張 武,2* 苗犇犇 劉 波 王瑞卿 張立付徐少翔 饒 元,2 江朝暉,2
(1.安徽農業(yè)大學 信息與計算機學院,合肥 230036; 2.智慧農業(yè)技術與裝備安徽省重點實驗室,合肥 230036)
土壤墑情傳感器(Soil moisture sensor,SMS)的選取和布置直接影響灌溉系統的決策和系統成本。SMS通常采用均勻分布,但若農田形狀不規(guī)則,均勻分布實施起來比較困難;此外,如果傳感器均勻分布的太稀疏,傳感器網絡不能全覆蓋,反之極大增加了數據冗余度。SMS布局優(yōu)化是一個多目標決策問題,采取的布點方法不僅要讓傳感器能覆蓋整個區(qū)域,保證傳感器數據全面準確,也要考慮各種性能約束和成本約束,同時還要考慮數據的冗余度。
傳感器布局優(yōu)化方法廣泛應用于設備故障檢測、結構健康監(jiān)測,航空航天等領域,在節(jié)水灌溉系統中SMS布局方法的研究比較少見。李飚等提出基于Delaunary三角剖分的傳感器布點方法以實現全方位的布點監(jiān)測,對于墑情變化劇烈的區(qū)域能更好地實現傳感器網絡全覆蓋;吳振宇等提出基于遺傳算法的SMS優(yōu)化布局策略,以傳感半徑和傳感器成本為約束條件,提高傳感器覆蓋率,降低傳感器成本;Mukherjee等采用了重新稱重的方法替換重復函數模擬以估計期望影響值,并提出了一種用于非線性不確定系統傳感器放置的模式分析方法;這些研究只考慮到覆蓋算法的優(yōu)化卻未涉及土壤墑情數據冗余問題,而在傳感器實際監(jiān)測中,會產生大量的冗余數據,一方面是因為物理現象的連續(xù)性,同一節(jié)點一段時間內的采樣數據之間具有較高的時間相關性,另一方面是因為根據Miller提出的“地理學第一定律”,無線傳感器網絡中傳感器節(jié)點在相鄰地理區(qū)域采集數據,物理參數具有連續(xù)性和相似性,使得相鄰節(jié)點的監(jiān)測數據具有空間相關性。為此,李泳霖等研究了同一土壤剖面不同深度的墑情的相關性,優(yōu)化了傳感器埋設的數量;張瑞瑞提出了基于網絡節(jié)點四叉樹編碼的數據聚合方法,其對土壤濕度的無損聚合率為33.34%;賈玉生等提出了基于壓縮感知的傳感器布局優(yōu)化方法,改進了現有的稀疏隨機測量矩陣,以確定給定區(qū)域所需的傳感器數量和每個傳感器的具體位置函數,該方法只適合于數據波動小的環(huán)境。Rossini等提出了基于模糊C均值聚類劃分土壤水分管理區(qū)并采用輪廓聚類評價方法確定最佳土壤水分管理區(qū),從而確定傳感器部署的最佳數量和位置;張武等提出基于AP聚類算法的SMS布局策略降低了系統成本和數據冗余度,但這些研究只考慮了單一天氣條件下的聚類結果。K-medoids聚類算法在無線傳感器網絡節(jié)點分簇中有所應用,王宗山等將遺傳算法與K-medoids算法結合;Wang等將近鄰傳播算法與K-medoids算法結合提出能量高效的分簇路由協議,綜合考慮簇內節(jié)點的剩余能量、地理位置等因素選舉簇首,使簇首節(jié)點分布均勻,均衡網絡能耗,譜排直算法常用于生物信息學領域;胡軍等基于譜排直算法衡量蛋白質序列的相似度;徐偉提出將譜排直算法與層次聚類結合實現對時間序列形式的基因芯片數據聚類。
本研究擬采用基于改進K-medoids算法的SMS布局方法,確定傳感器最佳部署位置并剔除冗余傳感節(jié)點,以期為灌溉系統的建立節(jié)約成本,為灌溉系統的決策提供可靠依據。
數據采集于安徽農業(yè)大學國家高新技術農業(yè)園一塊長約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型土壤墑情測定儀采集土壤相對含水率數據,該儀器基于介電理論并運用頻域測量技術研制開發(fā),能夠精確測量土壤和其他多孔介質的體積含水量,測量范圍為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
試驗區(qū)域的土壤為土層較厚的黃棕壤,含沙量小,黏粒含量達到20%,為黏質土類,具有滲水速率慢,保水性能好,通風效果一般的特征。采集各布點25 cm深度的土壤,并用環(huán)刀法測定土壤的孔隙度,孔隙度的平均值為45.52%,標準差為1.7%,該區(qū)域土壤具有較好的均一性。試驗區(qū)域的地勢呈中間高,四周低,最大落差約為2.8 m,坡度約4°。
1
.2
.1
K-
medoids算法簡介K-medoids是一種典型的基于劃分的無監(jiān)督聚類算法,是對K-means算法的優(yōu)化,二者都通過隨機方式初始化聚類中心。K-medoids每一次迭代都從樣本中選取新的中心點,選取的標準不是直接將樣本均值作為新的聚類中心,而是嘗試遍歷當前簇內所有樣本點并計算其到簇內其他點距離之和,選擇最優(yōu)的樣本點作為新的中心點,所以它比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ù)函數。給定譜x
(t
)和y
(t
),要求是分段線性函數或者連續(xù)可積函數,譜排直的含義就是把y
(t
)朝著x
(t
)進行豎直移動,使譜之間的誤差平方積分為最小值。是移動后的y
(t
),定義域t
∈(0,L
)內,x
(t
)和之間的面積表示譜之間的誤差,a
為y
(t
)豎直平移的距離。對x
(t
)和y
(t
)進行譜排直,即找到最優(yōu)的a
,使式(1)取得最小值:f
(x
,y
)=[x
(t
)-[y
(t
)-a
]]dt
(1)
對a
求一次導數得:(2)
令得到:
(3)
因為f
(x
,y
)的二階導數>0,所以a
為最小值。因而,存在唯一的移動變量a
,使得誤差平方積分取最小值。x
(t
)和移動后的y
(t
)的誤差積分為:x
(t
)-y
(t
)]dt
+a
L
=0(4)
基于譜排直的數據預處理,本研究提出時間序列數據距離函數:
dis(x
,y
)=f
(a
)+|a
L
|=x
(t
)-[y
(t
)-a
]]dt
+|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:利用三次樣條插值的方法將離散數據擬合成連續(xù)函數,也即將樣本集={,,…,}擬合為譜集(t
)={x
(t
),x
(t
),…,x
(t
)}。步驟2:對任意2個譜x
(t
),x
(t
)進行排直操作,由式(1)~(3)求出x
(t
)最優(yōu)平移距離a
使得2個排直后譜的誤差平方積分取得最小值。步驟3:由式(5)求出x
(t
),x
(t
)之間的譜距離。步驟4:初始化數據樣本,通過“手肘法”確定最優(yōu)簇的個數K
。步驟5:基于方差優(yōu)化初始中心的方法從樣本選擇K
個傳感器布點作為初始聚類中心。步驟6:計算傳感器節(jié)點到每個聚類中心的譜距離并進行比較,將其分配到最近的簇中。
步驟7:選擇到簇內其他傳感器布點距離之和最短的傳感器作為新的簇中心。
步驟8:當簇中心點不發(fā)生變化或迭代次數達到1 000,聚類結束,否則返回步驟6。
B
、C
、B
、C
附近表現為明顯的凹點,凹點位置與該區(qū)域的海拔高點基本重合。因此,初步判斷該區(qū)域的土壤相對含水率空間分布差異主要受到地形結構的影響。圖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
的關系從而確定最優(yōu)簇數,試驗Ⅰ和試驗Ⅱ中SSE隨K
的變化趨勢見圖4。K
值從1增大到4時,SSE值急劇下降,K
值大于4時,SSE值下降平緩,最優(yōu)簇個數為4,在此基礎上利用方差優(yōu)化初始聚類中心。圖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簇內節(jié)點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簇內節(jié)點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布局優(yōu)化方法和基于改進Dijkstra算法的SMS布局優(yōu)化方法,分別計算以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)。綜上,在試驗區(qū)選擇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 Ⅱ
本研究提出一種基于改進K-medoids算法的SMS優(yōu)化布局策略并應用于茶園SMS布局優(yōu)化的實際問題中。針對不同時期采集的茶園土壤相對含水率數據使用K-medoids和改進的K-medoids進行聚類,改進的K-medoids算法所得簇中心相對含水率與簇均值相對偏差相較于改進前降低了約30%;改進的K-medoids聚類結果具有較強的穩(wěn)定性,多種天氣條件下的所得聚類中心相對含水率平均值與隨機點相對含水率平均值的相對偏差(絕對值)都較小(不超過2%),說明譜排直算法定義的譜距離將時間尺度考慮進去,相較于用歐氏距離衡量時間序列數據相似性更為適合;K-medoids易與其他算法融合,對于農業(yè)中其他傳感器的布局問題也可提供有益的參考。本研究也有其局限性,試驗數據的采集時間短,跨度小,土壤性質單一,后期將不斷擴充數據量,擴大時間跨度,在不同的特性的土壤上進行試驗,提高方法的通用性。