基于改進粒子群算法的精準農業無線傳感器定位研究

程 磊，劉勇軍

(黃淮學院智能制造學院，河南 駐馬店 463000)

0 引 言

精細農業以最少的投入獲得優質的高產出和高效益，借助無線傳感器網絡，能實時遠程獲取農田土壤、植物生態等信息，精確地進行作業，有效節約資源[1,2]。

精準農業無線傳感器定位算法主要分為兩類[3]：一類為基于測距的定位算法，利用信標節點的位置信息實現未知節點的位置估計，需要無線傳感器網絡中的節點有測距功能，通過節點之間的距離或角度信息，使用三邊定位、三角定位或最小最大法等方法計算節點位置。三邊定位測量法在計算中沒有考慮節點測距誤差，若誤差過大，可能導致無法定位[4]；三角定位測量方法測試次數越多，對位置精度的計算也就越高[5]；最小最大法對錨節點的密度只有在較高的情況下定位才準確[6]；測距的定位涉及到的算法特征主要有接收信號強度 (Received Signal Strength，RSS)、基于到達時間差(Time Difference of Arrival，TDOA)、基于到達時間(Time of Arrival，TOA)等。另一類為基于非測距的定位算法，如近似三角形內點測試 (Approximate Point-in-Triangulation Test，APIT)，若錨節點稀疏則定位精度下降[7]；距離向量跳段 (Distance Vector Hop，DVH)，不足之處在于計算平均跳距及定位坐標時會產生誤差[8]，通常非測距算法的實用性差。測距定位成本較低，應用廣泛，但是若無線信號受到干擾，則導致測量過程不穩定，定位出現誤差，目前解決方法有：最大似然方法(Maximum likelihood method，MIM)，通過兩次加權進行最小二乘法[9]，能夠對定位坐標獲得較精確數據，但是需要依賴較多的先驗知識避免測量誤差；交互式多模型-改進卡爾曼濾波(Interacting multiple model-Improved Kalman filter, IMM-IKF), 對非視距誤差具有魯棒性，在未知信道傳播狀態和非視距誤差參數情況下，有效抑制非視距誤差，實現高精度定位[10]；擬牛頓算法(Quasi-Newton Methods, QNM)方法，通過傳統的牛頓迭代法求解[11]，但是目標函數具有高非線性，迭代法求解會使定位誤差累積，無法獲得全局最優解，雖然可以增加參考基站數量來提高定位精度，但基站數量增加使得誤差積累同樣也增加。在大型傳感器網絡中通過智能算法進行尋優，解決未知基站坐標的求解問題，主要算法有：粒子群算法(Particle Swarm Optimization,PSO)利用對數障礙函數對目標函數改進，但需要以未知基站的鄰站作為必要的參考信息[12]，容易陷入局部最優；遺傳算法(Genetic Algorithm，GA)，通過優化初始種群、自適應調整適應度的選擇操作以及加入誤差修正算子等方法[13]，提高定位算法的性能，但是算法很容易陷入局部最優的問題；鏈路質量指示 (Link Quality Indicator，LQI)算法，通過改進硬件改善測距精度，再結合粒子群算法改進尋優結果，但沒有考慮信道衰減系數變化對量測距離的影響。雙階段位置循環(Two Phase Positioning,TPP)求解算法[14]，即啟動和細化，啟動過程使用HOP模型，細化只涉及節點位于同一跳鄰域內，提高了測距精度，但通信量與計算量之間消耗能源較大；粒子群-蟻群算法優化(Particle Swarm Optimization Ant Colony Algorithm，PSOACA)，搜尋從距匯聚節點最近的簇頭節點出發[15]，遍歷所有簇頭節點，最終到達匯聚節點的最優路徑，每個粒子對應于一個簇，只在簇內跳動，并且不重復之前經過的節點，從而實現最小誤差。

本文對粒子群算法的慣性權重進行非線性優化，粒子群規模根據粒子的聚集度、多樣性函數進行收縮擴張控制，前期快速進行全局尋優，后期緩慢進行局部搜索，最后通過實驗仿真對算法的性能進行驗證，定性分析相比其他算法具有優勢。結果表明本文算法收斂性能較好，相比其他算法能有效地抑制測距誤差對定位的影響，能夠提高節點的定位精度。

1 基于改進粒子群算法的精準農業無線傳感器定位過程

1.1 問題描述

假設網絡中存在N個未知節點和M個錨節點[16]，節點的坐標集為φ=[φ1,φ2,…,φM+N]，錨節點的坐標分別為(x1,y1)，(x2,y2)，…，(xM,yM)，未知節點的坐標為φ=(φx,φy)，φx=(xM+1,xM+2,…,xM+N)，φy=(yM+1,yM+2,…,yM+N)，則定位誤差模型為：

(1)

因此，無線傳感器網絡節點定位問題可轉化為約束條件下方程的最優解問題。改進粒子群搜索算法是一種基于全局誤差函數的最小化算法，可以利用該算法迭代求解未知節點的位置，減小未知節點坐標的誤差，直到獲得目標函數的最優值。

1.2 改進粒子群搜索算法

1.2.1 基本粒子群算法

粒子群算法(Particle Swarm Optimization，PSO)通過學習因子c1和c2及慣性權重ω進行更新速度vq,h和位置zq,h:

(2)

式中：q=1,2,…；h=1,2,…；t為迭代次數；vq,h(t)為第q個粒子在第t次迭代中第h維的速度；zq,h(t)為第q個粒子在第t次迭代中第h維的位置；pq,h為當前最優值；pg,h為歷史最優值；r1∈(0,1)、r2∈(0,1)為相互獨立的隨機函數；ω越大越適合在更大的范圍內進行搜索，ω越小越能夠保證群體收斂到最優位置；c1和c2用于調整粒子飛行，若c1=c2=0, 粒子將一直以當前的速度飛行到邊界，一般都設定為2。

1.2.2 慣性權重優化

合適的ω能夠控制粒子以往速度對當前速度的影響，平衡全局和局部搜索能力，以較少的迭代次數找到最優解。為了使慣性權重ω適應搜索要求，算法運行初期強化全局搜索能力采用較大的慣性權重，ω遞減變化緩慢，后期進行精確的局部搜索采用較小的慣性權重，ω遞減變化較快，使用非線性遞減(No-Linearly Decreasing Weight,NLDW)策略：

(3)

其中：tmax為最大迭代次數；ωmin=0.35，ωmax=0.95。

1.2.3 收縮擴張控制過程

為避免粒子群聚集在某一特定位置或某幾個特定位置現象的發生，能夠保持多樣性的同時具有較好的收斂率[17]，引入收縮擴張因子ε。

粒子聚集度G判別公式為：

G(t)=Pg(t)/avgPi(t)

(4)

式中：avgPi(t)是所有粒子個體極值的平均值；Pg(t)是當前粒子的全局極值。

0

(5)

式中：c為粒子總個數；|L|為搜索空間的最長半徑；S為問題的維數；Pij為第i個粒子的第j個分量。

算法進化前期需要迅速接近全局極值，故此時收縮擴張系數的值應當處在較大的位置。而在算法進化后期，應減慢速度以加強算法的局部搜索能力，因此收縮擴張系數的值需適當減小，來提高算法的精確度，則ε：

(6)

式中：εstart為ε初值；εend為ε終值。

根據慣性權重優化和收縮擴張控制，粒子群的速度vq,h和位置zq,h修正為:

(7)

1.3 適應度函數選擇

傳感器網絡中待確定位置節點設置為(x,y),n個參考點的坐標為n1(x1,y1)，n2(x2,y2)，…，nn(xn,yn)，待確定位置節點到參考點距離為di，由于誤差，di與計算值不相等，為了減小誤差累積[18]，適應值函數選擇為距離估算值與實際值的均方根誤差f(x,y)：

(8)

式中：(xi,yi)表示第i個參考點坐標；n為目標點鄰近參考點數目，n≥3。

由于f(x,y)會將不同節點對應的殘差視為同等地位[19]，待定位節點的估計位置將傾向于滿足殘差小的錨節點約束，收斂于真實位置，通過對錨節點區分可信程度，在f(x,y)對未知節點設置不同的權重wi，提高定位精度：

(9)

式中：n為未知節點總數；節點u的鄰居錨節點ID號為1，2，…；距離測量值分別為du1，du2，…；dul為節點u到鄰居錨節點l的距離測量值；duk為節點u到鄰居錨節點k的距離測量值；dlk為錨節點l到錨節點k的距離測量值。

則適應度函數選擇重新構造為：

(10)

wi由未知節點到錨節點的距離測量值決定，其關系為反比關系，為避免迭代算法中出現局部最優，控制某個錨節點的損失或所有錨節點的累計損失過大，增設錨節點定位誤差閾值與所有錨節點定位誤差累積閾值分別為bth、Bth，避免算法陷入局部最優：

(11)

這樣有效地增強可信錨節點的作用，抑制不可信錨節點的影響。

1.4 算法流程

(1)隨機初始化粒子群搜索算法的相關參數，主要包括粒子群總數、速度、位置，其中粒子位置為傳感器節點的坐標。

(2)根據公式(10)計算粒子的適應值，得到粒子的pq,h和pg,h，選擇當前最優適應值f(xi,yi)所對應的最佳粒子群位置(xi,yi)。

(3)根據公式(7)更新粒子群的位置、速度、pq,h、pg,h，獲得新一代粒子位置(xj,yj)。

(4)保留較優的f(xi,yi)與f(xj,yj)，并將該適應值對應的粒子群位置記為(x*,y*),(x*,y*)表示當前種群中最優位置。

(5)判斷是否滿足算法定位精度，若滿足，輸出全局最優解對應的粒子群位置，否則轉至步驟(3)。

2 實驗仿真

選擇200 m×200 m的高粱試驗場地進行了未知傳感器節點定位試驗，場地內栽種的大豆植株平均約高30 cm，且植株栽種整齊。將終端監測節點在隨機散布于場地中，每個節點擁有相同的通信半徑，未知節點和信標節點位置信息隨機產生。參數設置如下：初始化粒子總數為120，最大迭代次數為300。

2.1 收斂性能對比

PSO、GA、PSOACA、IPSO算法在精準農業無線傳感器定位過程中目標函數適應值的變化曲線如圖1所示。

圖1 不同算法目標函數適應值變化曲線Fig.1 Variation of fitness function of different algorithm objective function

實驗結果表明，IPSO算法的求解速度明顯快于其他算法，能夠用較少的迭代次數獲得更精確的解。這主要是由于IPSO算法使用慣性權重優化、收縮擴張控制，從而能夠較好地進行局部、全局搜索，避免搜索的單一性，IPSO增加了PSO算法收斂速度和全局收斂性，最終收斂得到最優解，能夠使無線傳感器獲得精確定位。

2.2 定性分析

歸一化平均定位誤差評價指標E[20]：

(12)

歸一化平均定位誤差與消耗時間的對比關系如圖2所示，涉及的算法有MIM 、IMM-IKF、 QNM、PSO、GA、PSOACA、IPSO。

圖2 歸一化平均定位誤差與消耗時間的關系Fig.2 Relationship between normalized mean location error and consumption time

從圖2可以看出，隨著消耗時間的增加，各種歸一化平均定位誤差都逐漸下降，但是IPSO消耗時間明顯優于其他定位算法，在1 s時刻即可獲得較低的定位誤差，在3 s左右開始保持不變，表明該算法具有很強的穩定性，而且具有很高的定位精度。

2.3 錨節點個數對定位性能的影響

圖3為各種算法在錨節點數量不同的情況下的歸一化平均定位誤差。

圖3 錨節點個數對定位性能的影響Fig.3 Influence of anchor node number on positioning performance

從圖3可以看出，隨著錨節點比例不斷的增大，各種算法的平均定位誤差都逐漸減小，并逐漸趨于穩定。在相同錨節點比例情況下，IPSO算法優化后的平均定位誤差更小，這說明IPSO算法在少量的錨節點的情況下，能取得較好的定位效果。

2.4 測距誤差對定位性能的影響

圖4為各種算法的定位誤差隨著測距誤差變化的曲線。

圖4 定位誤差隨著測距誤差變化曲線Fig.4 Location error versus range error curve

從圖4可以看出，隨著測距誤差的增加，各種算法定位誤差都呈上升的趨勢。但是，相對于其他算法，IPSO算法受測距誤差的影響相對較小，能夠在一定程度上抑制節點測距誤差的累加；當測距誤差比較大時，IPSO算法的定位效果更加穩定。說明IPSO算法優化定位有著更好的抗誤差性。

3 結 語

本文算法對粒子群算法優化主要包括慣性權重參數、群體規模收縮擴張控制，慣性權重參數采用非線性方法，即算法運行初期強化全局搜索能力采用較大的慣性權重，后期進行精確的局部搜索采用較小的慣性權重，提高群體算法對起始錨節點的精確度；群體規模收縮擴張控制算法前期群體規模擴張操作，后期收縮操作，提高算法對錨節點的穩定性，仿真實驗結果表明，本算法獲得了較好的定位效果，能夠提高網絡工作效率、優化網絡性能，降低農業生產成本，為農業智能化研究提供了新的思路和方法。