臧英凱,韓 笑,陳金超,陳雯柏,吳華瑞,趙春江

(1.北京信息科技大學(xué) 自動化學(xué)院,北京 100192;2.國家農(nóng)業(yè)信息化工程技術(shù)研究中心,北京 100097;3.農(nóng)業(yè)農(nóng)村部 農(nóng)業(yè)信息數(shù)字鄉(xiāng)村技術(shù)重點實驗室,北京 100097;4.農(nóng)芯科技有限責(zé)任公司,北京 100097)

0 引言

精準(zhǔn)農(nóng)業(yè)是可持續(xù)高效農(nóng)業(yè)發(fā)展的重要方向[1]。無線傳感器為農(nóng)業(yè)灌溉、環(huán)境監(jiān)測以及作物生長監(jiān)測等應(yīng)用提供了數(shù)據(jù)基礎(chǔ)。無線傳感器網(wǎng)絡(luò)定位系統(tǒng)可以明確感知數(shù)據(jù)的地理位置,且現(xiàn)有農(nóng)田節(jié)點定位技術(shù)的定位精度可以達(dá)到米級,能夠為農(nóng)事精準(zhǔn)決策提供更為全面、豐富的信息[2-3]。但農(nóng)田頻繁變化的開放環(huán)境氣候、動態(tài)生長的密植作物和移動農(nóng)機(jī)裝備等嚴(yán)重影響無線信號傳輸[4-5]。如何實現(xiàn)低成本、高精度的定位是精準(zhǔn)農(nóng)業(yè)無線傳感器網(wǎng)絡(luò)(WSN)定位系統(tǒng)的研究重點之一。

常見測距定位方法包括三邊測量法(Trilateration)[6]、三角測量法(Triangulation)[7]和極大似然估計法(Multilateration)[8],測距定位理論模型簡單,方便實現(xiàn),但測距模型與數(shù)據(jù)的擬合效果易受環(huán)境因素影響,定位誤差較大。DV-Hop[9]、指紋定位算法[10]等基于無線傳感器網(wǎng)絡(luò)連通性以及信號特點進(jìn)行定位,在復(fù)雜環(huán)境下具有較好的定位效果。指紋定位不受信號數(shù)據(jù)與測距模型擬合結(jié)果影響,通過量化場景環(huán)境信息建立特異性指紋數(shù)據(jù)庫,由支持向量機(jī)、K最近鄰、隨機(jī)森林等機(jī)器學(xué)習(xí)算法對待測點與特征數(shù)據(jù)庫進(jìn)行匹配,從而實現(xiàn)目標(biāo)定位。

相較于測距定位與DV-Hop定位,指紋定位無需額外增加硬件,在復(fù)雜環(huán)境中定位效果更好。近年來眾多學(xué)者對其進(jìn)行了深入研究。馬宗方等[11]針對指紋定位中視角單一問題,利用閾值-均值濾波方法處理數(shù)據(jù)并結(jié)合K-means算法對多視角信號進(jìn)行劃分,提高了定位精度。田洪亮等[12]針對位置指紋離散程度不同對指紋數(shù)據(jù)賦予相應(yīng)的權(quán)值,進(jìn)而對KNN算法進(jìn)行改進(jìn)。但KNN算法定位精度依賴K值的正確選擇。徐超藍(lán)等[13]采用引入核函數(shù)的SVM算法在小規(guī)模場景進(jìn)行節(jié)點指紋定位。李軍等[14]將聚類算法與隨機(jī)森林算法進(jìn)行融合定位,有效減小環(huán)境因素對定位精度的影響。現(xiàn)有研究針對優(yōu)化指紋數(shù)據(jù)庫和改進(jìn)定位匹配算法均有較大的進(jìn)展,但僅用匹配的參考點近似代替測試點位置很難達(dá)到較高的定位精度,不適用于農(nóng)田環(huán)境,存在參考點外的定位區(qū)域空缺問題。

針對上述問題,提出一種基于改進(jìn)極限梯度提升(extreme gradient boosting,XGBoost)的高精度農(nóng)田傳感網(wǎng)絡(luò)節(jié)點定位方法。該方法同時考慮信號與物理坐標(biāo)對農(nóng)田區(qū)域進(jìn)行特異性聚類,生成基于區(qū)域劃分的聚類指紋庫;采用XGBoost算法將測試點信號強(qiáng)度與指紋庫中數(shù)據(jù)進(jìn)行匹配,將匹配到的最優(yōu)參考點參與加權(quán)質(zhì)心計算(weighted centroid,WC),從而完成對待測點的精確定位。

1 農(nóng)田指紋定位算法原理

指紋定位算法是一種將實際場景中的物理位置與獨特的指紋信息相關(guān)聯(lián)的方法,通過采集參考點(RP)的信號強(qiáng)度值(稱為“指紋”),根據(jù)物理位置與信號強(qiáng)度值相關(guān)性進(jìn)行定位。農(nóng)田指紋定位示意圖如圖1所示。

圖1 農(nóng)田指紋定位示意圖

農(nóng)田指紋定位過程包括指紋庫建立階段和系統(tǒng)定位階段。

指紋庫建立階段:在定位區(qū)域以固定距離間隔設(shè)置若干指紋參考點,在每個參考點處采集來自所有錨節(jié)點(AP)的信號強(qiáng)度值(RSSI)以及其位置坐標(biāo)信息,構(gòu)建初始指紋數(shù)據(jù)庫。農(nóng)田環(huán)境區(qū)域大,涉及參考點多,為節(jié)約定位算法的計算開銷,常采用聚類算法來劃分定位區(qū)域,形成聚類指紋數(shù)據(jù)庫。指紋數(shù)據(jù)庫結(jié)構(gòu)如下:

(1)

系統(tǒng)定位階段:收集待定位傳感器測得各個錨節(jié)點的信號強(qiáng)度值,并通過無線網(wǎng)絡(luò)傳輸至上位機(jī)。在上位機(jī)使用適當(dāng)?shù)钠ヅ渌惴▽⑹占男盘枏?qiáng)度值與聚類指紋數(shù)據(jù)庫中各個參考點的信號強(qiáng)度值進(jìn)行匹配,信號強(qiáng)度最接近的參考點坐標(biāo)作為待測點的定位結(jié)果。

2 基于雙尺度K-means算法的農(nóng)田指紋庫建立

為減少指紋庫數(shù)據(jù)匹配的計算量,研究K-means 的聚類算法進(jìn)行指紋聚類,獲得聚類指紋數(shù)據(jù)庫[15]。由于農(nóng)田作物遮擋以及土地不平整等原因,RSSI衰落分布不平滑,存在個別離群指紋參考點,若K-means算法只參考RSSI歐式距離度量聚類,則容易導(dǎo)致離群參考點歸類失誤。于是將物理坐標(biāo)引入距離計算中對傳統(tǒng)聚類進(jìn)行改進(jìn),同時考慮參考點與聚類中心間RSSI值與坐標(biāo)位置2個尺度差異,改進(jìn)后距離度量計算公式為:

(2)

式中:rssii和(xi,yi)分別為第i個RP采集的RSSI值以及物理坐標(biāo);rssij和(xj,yj)分別為第j個聚類中心對應(yīng)的RSSI值以及物理坐標(biāo)。

具體的聚類過程如下:

1) 從初始指紋數(shù)據(jù)庫中隨機(jī)挑選K個參考點作為初始聚類中心點C(x,y,rssi1,…,rssim)。

2) 根據(jù)式(2)計算指紋庫中每個參考點到K個聚類中心的距離,將該參考點歸為與其距離度量最小的類簇Cj中,直至參考點全部歸類完畢,得到總共包含n個指紋信息的K個聚類C1,C2,…,CK。

(3)

4) 重復(fù)步驟2)—3),直至沒有參考點被歸到新類或滿足終止條件,輸出簇中參考點,得到聚類指紋數(shù)據(jù)庫。

綜合考慮參考點RSSI與物理坐標(biāo)對聚類效果的影響,根據(jù)農(nóng)田環(huán)境改進(jìn)K-means聚類算法能有效避免將RSSI值相似度高、物理坐標(biāo)相似度低的參考點聚為一類的情況。

3 基于加權(quán)質(zhì)心的XGBoost定位算法

農(nóng)田環(huán)境傳感器所處環(huán)境復(fù)雜,影響信號傳輸?shù)囊蛩囟?包括起伏地勢、作物遮擋等。為實現(xiàn)農(nóng)田環(huán)境下的精準(zhǔn)快速定位,使用XGBoost算法作為指紋庫參考點的匹配模型。進(jìn)一步結(jié)合質(zhì)心四點定位算法對匹配算法進(jìn)行改進(jìn),根據(jù)測試點與匹配指紋點間RSSI相似度確定相應(yīng)權(quán)值,完成對參考點以外區(qū)域的精確定位。

3.1 XGBoost-WC定位算法

XGBoost算法具有較強(qiáng)的抗干擾性、高準(zhǔn)確性和運算速度快等優(yōu)勢,可對多維數(shù)據(jù)指紋進(jìn)行快速有效分類,能夠滿足農(nóng)田場景的初步定位需求[16]。作為一種多決策樹分類器,XGBoost通過集成構(gòu)建多個回歸樹對指紋樣本進(jìn)行訓(xùn)練,并將每棵決策樹的結(jié)果層層疊加獲得最終分類結(jié)果[17]。

算法目標(biāo)函數(shù)為

(4)

為更加精確地逼近損失函數(shù),利用二階泰勒級數(shù)展開該目標(biāo)函數(shù):

(5)

XGBoost算法在目標(biāo)函數(shù)中加入正則函數(shù)控制模型的復(fù)雜度。正則項降低了模型方差,可有效防止過擬合,使模型更為簡單。正則函數(shù)Ω(fk)由葉子數(shù)T以及葉子節(jié)點權(quán)重ωt共同決定,表達(dá)式為:

(6)

將正則項代入式(5)中并對ωt求導(dǎo),令導(dǎo)數(shù)為0,求得最優(yōu)的葉子節(jié)點權(quán)重,得到目標(biāo)函數(shù)的最優(yōu)解為:

(7)

XGBoost算法通過對損失函數(shù)進(jìn)行二階泰勒展開,引入了正則函數(shù),在減少決策樹規(guī)模的同時,提高了分類精度,且并行處理方式也大大加快了指紋數(shù)據(jù)的訓(xùn)練速度。

為解決參考點外區(qū)域定位問題,在XGBoost算法的基礎(chǔ)上,引入加權(quán)質(zhì)心定位算法[18]。通過匹配算法將參考點按照相似度大小排序,篩選與待測點指紋特征相似度最高的4個參考位置作為頂點構(gòu)成目標(biāo)粗定位區(qū)域。由于相似度大小與RSSI值間的歐氏距離有關(guān),因此選取歐式距離作為節(jié)點間的相似性度量,分別計算待定位節(jié)點與區(qū)域4個頂點間的歐氏距離di:

(8)

式中:di為第i個頂點與待測點的歐氏距離;m為錨節(jié)點個數(shù)。

di越小,即待定位節(jié)點與此點指紋相似度越高,位置越接近,此參考點應(yīng)賦予更大的權(quán)值。采用歐氏距離的倒數(shù)作為權(quán)值,以體現(xiàn)不同頂點的貢獻(xiàn)值。權(quán)值表達(dá)式為:

(9)

上述質(zhì)心便是未知節(jié)點預(yù)測坐標(biāo)。改進(jìn)XGBoost定位算法能有效解決在參考點以外區(qū)域的定位問題,從而提高定位精度。

3.2 XGBoost-WC定位算法步驟

圖2為定位算法流程圖,具體步驟如下。

圖2 XGBoost-WC定位算法流程框圖

步驟1利用XGBoost算法建立聚類指紋庫中位置坐標(biāo)與接收信號強(qiáng)度之間的非線性映射模型。實時采集待測點RSSI數(shù)據(jù),通過計算待測點與指紋庫中各聚類中心RSSI值的歐氏距離,獲得與待測點相似度最高的類簇,確定待測點聚類區(qū)域。

步驟2將實時RSSI數(shù)據(jù)輸入訓(xùn)練后的定位模型,通過匹配聚類指紋庫進(jìn)行定位,選出匹配度最高的4個匹配值坐標(biāo)明確粗定位區(qū)域。

步驟3根據(jù)歐氏距離表征匹配點與待測點間的指紋相似度。將兩點間歐氏距離作為權(quán)值對粗定位區(qū)域進(jìn)行加權(quán)質(zhì)心計算,獲得最終定位結(jié)果。

4 實驗驗證及分析

4.1 實驗方案

選取國家農(nóng)業(yè)精準(zhǔn)實驗基地農(nóng)田采集RSSI數(shù)據(jù)。選用CC2530芯片集成的ZigBee傳感器節(jié)點進(jìn)行系統(tǒng)定位實驗,節(jié)點如圖3所示?？紤]傳感器節(jié)點實際數(shù)據(jù)傳輸距離限制,在20 m × 20 m的方形區(qū)域放置4個錨節(jié)點,其坐標(biāo)分別為(0,0),(0,20),(20,0),(20,20);以1 m為間隔將方形區(qū)域柵格化,將格子頂點設(shè)為指紋庫的參考點,實驗共設(shè)置441個參考點。在每個參考點處分別采集4個錨節(jié)點的RSSI值,并記錄相應(yīng)位置坐標(biāo),逐一存儲區(qū)域內(nèi)所有參考點的指紋信息,聚類后實現(xiàn)指紋庫的構(gòu)建。農(nóng)田定位實驗環(huán)境如圖4所示。

圖4 定位實驗環(huán)境

4.2 實驗結(jié)果

在基地隨機(jī)選取20個測試點,記錄其真實坐標(biāo)并測量該位置接收到4個錨節(jié)點的信號強(qiáng)度值。測試點的真實坐標(biāo)和所提算法的預(yù)測結(jié)果分布如圖5所示,預(yù)測坐標(biāo)與測試點的真實坐標(biāo)相近,算法定位效果較好。

圖5 測試點真實及預(yù)測坐標(biāo)分布

基于上述建立的指紋數(shù)據(jù)庫,將Bayes、KNN、RF和XGBoost算法作為對比,繪制估計誤差累積分布函數(shù)(cumulative distribution function,CDF)曲線,如圖6所示。

圖6 不同機(jī)器學(xué)習(xí)定位算法CDF曲線

由圖6可以看出,采用不同機(jī)器學(xué)習(xí)算法所獲得的定位效果有較大的差異,統(tǒng)計的各個算法平均定位精度以及80%分位處的定位精度如表1所示。

表1 定位算法的定位效果

在5種算法中,根據(jù)最大后驗概率決策的Bayes定位算法在進(jìn)行分類時存在一定的錯誤率,導(dǎo)致誤差累計函數(shù)收斂最慢,最大誤差值也較大; KNN算法是基于歐式距離進(jìn)行定位計算的,在樣本分布不均衡時,歐氏距離難以完成節(jié)點的精準(zhǔn)定位計算,定位精度略優(yōu)于Bayes算法,最大定位誤差在3 m左右;相較于Bayes和KNN,集成學(xué)習(xí)算法RF和XGBoost通過集成多個弱學(xué)習(xí)器提升了定位精度。RF算法對于噪聲較大的分類任務(wù)容易產(chǎn)生過擬合的現(xiàn)象,表現(xiàn)差于XGBoost算法,平均定位精度為1.34 m。XGBoost算法在上述算法的比較中表現(xiàn)最好,平均定位精度為1.06 m?；赬GBoost,研究引入加權(quán)質(zhì)心對粗定位區(qū)域進(jìn)行精確定位,提高了模型定位精度,平均定位精度為0.97 m,80%分位處的定位精度在1.05 m以內(nèi)。較XGBoost、RF、KNN、Bayes算法,所提算法的平均定位精確度分別提升了8.5%、27.6%、33.5%、59.6%。

表1比較了上述不同定位算法的時間復(fù)雜度,所提算法采用XGBoost進(jìn)行指紋庫匹配,通過列塊結(jié)構(gòu)預(yù)排序特征列樣本,算法僅進(jìn)行一次排序,時間復(fù)雜度為O(p·logn)。在構(gòu)建決策樹過程中,需要對排序后的特征列進(jìn)行線性查找,時間復(fù)雜度為O(k·d·p)。加權(quán)質(zhì)心算法僅進(jìn)行權(quán)值及定位運算,時間復(fù)雜度相比決策樹查找可忽略不計。因此,XGBoost-WC定位算法的時間復(fù)雜度近似為O(P·logn+k·d·p),與其他算法相比,算法開銷較小,縮減定位系統(tǒng)的運行時間。

5 定位精度影響因素分析

5.1 AP數(shù)量對定位精度的影響

在定位算法中,AP數(shù)量代表著指紋庫的數(shù)據(jù)維度,是影響定位效果的重要參數(shù)。為探究AP數(shù)量對所提算法定位精度的影響,分別設(shè)置2、3、4個AP對實驗區(qū)域內(nèi)的參考點和測試點進(jìn)行數(shù)據(jù)采集并測試,實驗結(jié)果如圖7所示。

圖7 AP數(shù)量對定位結(jié)果的影響曲線

由圖7可知,增大區(qū)域內(nèi)錨節(jié)點數(shù)量會提高定位精度。當(dāng)只有2個錨節(jié)點時,由于特征數(shù)目少不足以對未知節(jié)點進(jìn)行較精確定位,平均定位誤差在4.09 m左右,難以滿足大多數(shù)定位場景的精度需求。AP數(shù)量為4個時定位精度高于3個AP數(shù)量,平均精度提高了58.7%,在該農(nóng)田環(huán)境下可取得較理想的定位效果。

5.2 采樣間隔對定位精度的影響

參考點密度大小直接影響定位精度。為研究采樣間隔對定位性能的影響,分別設(shè)置間隔為1、2、4 m的指紋參考點進(jìn)行采樣,參考點個數(shù)分別為441、121、36。圖8展示了在3種采樣間距下的XGBoost和XGBoost-WC算法的性能,隨著采樣間隔的減小,2種算法的定位性能均有明顯提升,但相同條件下所提算法的定位效果始終優(yōu)于XGBoost算法。圖9為所提算法對15個測試點進(jìn)行節(jié)點定位的定位結(jié)果,當(dāng)參考點間隔為1 m時最大定位誤差為1.83 m,遠(yuǎn)小于間隔2 m的2.72 m和間隔4 m的3.80 m。可見,在信號傳播環(huán)境復(fù)雜的農(nóng)田,適當(dāng)減小參考點間的間隔,增大數(shù)據(jù)庫規(guī)模,可以有效降低算法的定位誤差。

圖8 不同采樣間距的2種算法的CDF曲線

圖9 參考點密度對所提算法定位結(jié)果的影響曲線

綜上所述,可以通過增加AP數(shù)量以及減小采樣間隔來降低算法的定位誤差,但指紋點個數(shù)也會呈冪次方增加,訓(xùn)練時間也會相應(yīng)增加。綜合考慮訓(xùn)練時間與定位精度,在后續(xù)工作中,可選擇4個AP以及1 m的采樣間隔來構(gòu)建指紋庫。

6 結(jié)論

針對農(nóng)田無線傳感網(wǎng)絡(luò)定位系統(tǒng),提出了一種基于指紋定位的高精度節(jié)點定位方法。該算法為減少農(nóng)田環(huán)境中信號離群點的影響,在指紋庫建立階段采用雙尺度K-means聚類算法進(jìn)行聚類,在定位階段利用XGBoost集成學(xué)習(xí)的優(yōu)勢有效提高了粗定位的精度和時效性,引入加權(quán)質(zhì)心算法對粗定位結(jié)果進(jìn)一步精估,解決參考點以外區(qū)域的定位問題。實際農(nóng)田環(huán)境下的實驗分析表明,該算法在80%分位處的定位精度在1.05 m以內(nèi),較只采用XGBoost定位算法精度有所提升,驗證了錨節(jié)點數(shù)量及參考點間隔對算法定位精度的影響。該算法相對于傳統(tǒng)的測距定位算法具有更高的定位精度,能夠為農(nóng)田無線傳感器網(wǎng)絡(luò)提供參考。