一種基于指紋定位的高精度農田節點定位算法

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

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

0 引言

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

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

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

針對上述問題,提出一種基于改進極限梯度提升(extreme gradient boosting,XGBoost)的高精度農田傳感網絡節點定位方法。該方法同時考慮信號與物理坐標對農田區域進行特異性聚類,生成基于區域劃分的聚類指紋庫;采用XGBoost算法將測試點信號強度與指紋庫中數據進行匹配,將匹配到的最優參考點參與加權質心計算(weighted centroid,WC),從而完成對待測點的精確定位。

1 農田指紋定位算法原理

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

圖1 農田指紋定位示意圖

農田指紋定位過程包括指紋庫建立階段和系統定位階段。

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

(1)

系統定位階段:收集待定位傳感器測得各個錨節點的信號強度值,并通過無線網絡傳輸至上位機。在上位機使用適當的匹配算法將收集的信號強度值與聚類指紋數據庫中各個參考點的信號強度值進行匹配,信號強度最接近的參考點坐標作為待測點的定位結果。

2 基于雙尺度K-means算法的農田指紋庫建立

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

(2)

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

具體的聚類過程如下:

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

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

(3)

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

綜合考慮參考點RSSI與物理坐標對聚類效果的影響,根據農田環境改進K-means聚類算法能有效避免將RSSI值相似度高、物理坐標相似度低的參考點聚為一類的情況。

3 基于加權質心的XGBoost定位算法

農田環境傳感器所處環境復雜,影響信號傳輸的因素多,包括起伏地勢、作物遮擋等。為實現農田環境下的精準快速定位,使用XGBoost算法作為指紋庫參考點的匹配模型。進一步結合質心四點定位算法對匹配算法進行改進,根據測試點與匹配指紋點間RSSI相似度確定相應權值,完成對參考點以外區域的精確定位。

3.1 XGBoost-WC定位算法

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

算法目標函數為

(4)

為更加精確地逼近損失函數,利用二階泰勒級數展開該目標函數:

(5)

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

(6)

將正則項代入式(5)中并對ωt求導,令導數為0,求得最優的葉子節點權重,得到目標函數的最優解為:

(7)

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

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

(8)

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

di越小,即待定位節點與此點指紋相似度越高,位置越接近,此參考點應賦予更大的權值。采用歐氏距離的倒數作為權值,以體現不同頂點的貢獻值。權值表達式為:

(9)

上述質心便是未知節點預測坐標。改進XGBoost定位算法能有效解決在參考點以外區域的定位問題,從而提高定位精度。

3.2 XGBoost-WC定位算法步驟

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

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

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

步驟2將實時RSSI數據輸入訓練后的定位模型,通過匹配聚類指紋庫進行定位,選出匹配度最高的4個匹配值坐標明確粗定位區域。

步驟3根據歐氏距離表征匹配點與待測點間的指紋相似度。將兩點間歐氏距離作為權值對粗定位區域進行加權質心計算,獲得最終定位結果。

4 實驗驗證及分析

4.1 實驗方案

選取國家農業精準實驗基地農田采集RSSI數據。選用CC2530芯片集成的ZigBee傳感器節點進行系統定位實驗,節點如圖3所示。考慮傳感器節點實際數據傳輸距離限制,在20 m × 20 m的方形區域放置4個錨節點,其坐標分別為(0,0),(0,20),(20,0),(20,20);以1 m為間隔將方形區域柵格化,將格子頂點設為指紋庫的參考點,實驗共設置441個參考點。在每個參考點處分別采集4個錨節點的RSSI值,并記錄相應位置坐標,逐一存儲區域內所有參考點的指紋信息,聚類后實現指紋庫的構建。農田定位實驗環境如圖4所示。

圖4 定位實驗環境

4.2 實驗結果

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

圖5 測試點真實及預測坐標分布

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

圖6 不同機器學習定位算法CDF曲線

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

表1 定位算法的定位效果

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

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

5 定位精度影響因素分析

5.1 AP數量對定位精度的影響

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

圖7 AP數量對定位結果的影響曲線

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

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

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

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

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

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

6 結論

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