一種基于指紋定位的高精度農(nóng)田節(jié)點(diǎn)定位算法

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

(1.北京信息科技大學(xué) 自動化學(xué)院,北京 100192;2.國家農(nóng)業(yè)信息化工程技術(shù)研究中心,北京 100097;3.農(nóng)業(yè)農(nóng)村部 農(nóng)業(yè)信息數(shù)字鄉(xiāng)村技術(shù)重點(diǎn)實驗室,北京 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é)點(diǎn)定位技術(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)的研究重點(diǎn)之一。

常見測距定位方法包括三邊測量法(Trilateration)[6]、三角測量法(Triangulation)[7]和極大似然估計法(Multilateration)[8],測距定位理論模型簡單,方便實現(xiàn),但測距模型與數(shù)據(jù)的擬合效果易受環(huán)境因素影響,定位誤差較大。DV-Hop[9]、指紋定位算法[10]等基于無線傳感器網(wǎng)絡(luò)連通性以及信號特點(diǎn)進(jìn)行定位,在復(fù)雜環(huán)境下具有較好的定位效果。指紋定位不受信號數(shù)據(jù)與測距模型擬合結(jié)果影響,通過量化場景環(huán)境信息建立特異性指紋數(shù)據(jù)庫,由支持向量機(jī)、K最近鄰、隨機(jī)森林等機(jī)器學(xué)習(xí)算法對待測點(diǎn)與特征數(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é)點(diǎn)指紋定位。李軍等[14]將聚類算法與隨機(jī)森林算法進(jìn)行融合定位,有效減小環(huán)境因素對定位精度的影響。現(xiàn)有研究針對優(yōu)化指紋數(shù)據(jù)庫和改進(jìn)定位匹配算法均有較大的進(jìn)展,但僅用匹配的參考點(diǎn)近似代替測試點(diǎn)位置很難達(dá)到較高的定位精度,不適用于農(nóng)田環(huán)境,存在參考點(diǎn)外的定位區(qū)域空缺問題。

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

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

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

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

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

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

(1)

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

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

為減少指紋庫數(shù)據(jù)匹配的計算量,研究K-means 的聚類算法進(jìn)行指紋聚類,獲得聚類指紋數(shù)據(jù)庫[15]。由于農(nóng)田作物遮擋以及土地不平整等原因,RSSI衰落分布不平滑,存在個別離群指紋參考點(diǎn),若K-means算法只參考RSSI歐式距離度量聚類,則容易導(dǎo)致離群參考點(diǎn)歸類失誤。于是將物理坐標(biāo)引入距離計算中對傳統(tǒng)聚類進(jìn)行改進(jìn),同時考慮參考點(diǎ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個參考點(diǎn)作為初始聚類中心點(diǎn)C(x,y,rssi1,…,rssim)。

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

(3)

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

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

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

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

3.1 XGBoost-WC定位算法

XGBoost算法具有較強(qiáng)的抗干擾性、高準(zhǔn)確性和運(yù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é)點(diǎn)權(quán)重ωt共同決定,表達(dá)式為:

(6)

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

(7)

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

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

(8)

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

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

(9)

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

3.2 XGBoost-WC定位算法步驟

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

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

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

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

步驟3根據(jù)歐氏距離表征匹配點(diǎn)與待測點(diǎn)間的指紋相似度。將兩點(diǎn)間歐氏距離作為權(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é)點(diǎn)進(jìn)行系統(tǒng)定位實驗,節(jié)點(diǎn)如圖3所示?？紤]傳感器節(jié)點(diǎn)實際數(shù)據(jù)傳輸距離限制,在20 m × 20 m的方形區(qū)域放置4個錨節(jié)點(diǎn),其坐標(biāo)分別為(0,0),(0,20),(20,0),(20,20);以1 m為間隔將方形區(qū)域柵格化,將格子頂點(diǎn)設(shè)為指紋庫的參考點(diǎn),實驗共設(shè)置441個參考點(diǎn)。在每個參考點(diǎn)處分別采集4個錨節(jié)點(diǎn)的RSSI值,并記錄相應(yīng)位置坐標(biāo),逐一存儲區(qū)域內(nèi)所有參考點(diǎn)的指紋信息,聚類后實現(xiàn)指紋庫的構(gòu)建。農(nóng)田定位實驗環(huán)境如圖4所示。

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

4.2 實驗結(jié)果

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

圖5 測試點(diǎn)真實及預(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é)點(diǎn)的精準(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)值及定位運(yùn)算,時間復(fù)雜度相比決策樹查找可忽略不計。因此,XGBoost-WC定位算法的時間復(fù)雜度近似為O(P·logn+k·d·p),與其他算法相比,算法開銷較小,縮減定位系統(tǒng)的運(yùn)行時間。

5 定位精度影響因素分析

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

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

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

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

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

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

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

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

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

6 結(jié)論

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