程 磊,劉勇軍
(黃淮學(xué)院智能制造學(xué)院,河南 駐馬店 463000)
精細(xì)農(nóng)業(yè)以最少的投入獲得優(yōu)質(zhì)的高產(chǎn)出和高效益,借助無線傳感器網(wǎng)絡(luò),能實(shí)時(shí)遠(yuǎn)程獲取農(nóng)田土壤、植物生態(tài)等信息,精確地進(jìn)行作業(yè),有效節(jié)約資源[1,2]。
精準(zhǔn)農(nóng)業(yè)無線傳感器定位算法主要分為兩類[3]:一類為基于測距的定位算法,利用信標(biāo)節(jié)點(diǎn)的位置信息實(shí)現(xiàn)未知節(jié)點(diǎn)的位置估計(jì),需要無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)有測距功能,通過節(jié)點(diǎn)之間的距離或角度信息,使用三邊定位、三角定位或最小最大法等方法計(jì)算節(jié)點(diǎn)位置。三邊定位測量法在計(jì)算中沒有考慮節(jié)點(diǎn)測距誤差,若誤差過大,可能導(dǎo)致無法定位[4];三角定位測量方法測試次數(shù)越多,對(duì)位置精度的計(jì)算也就越高[5];最小最大法對(duì)錨節(jié)點(diǎn)的密度只有在較高的情況下定位才準(zhǔn)確[6];測距的定位涉及到的算法特征主要有接收信號(hào)強(qiáng)度 (Received Signal Strength,RSS)、基于到達(dá)時(shí)間差(Time Difference of Arrival,TDOA)、基于到達(dá)時(shí)間(Time of Arrival,TOA)等。另一類為基于非測距的定位算法,如近似三角形內(nèi)點(diǎn)測試 (Approximate Point-in-Triangulation Test,APIT),若錨節(jié)點(diǎn)稀疏則定位精度下降[7];距離向量跳段 (Distance Vector Hop,DVH),不足之處在于計(jì)算平均跳距及定位坐標(biāo)時(shí)會(huì)產(chǎn)生誤差[8],通常非測距算法的實(shí)用性差。測距定位成本較低,應(yīng)用廣泛,但是若無線信號(hào)受到干擾,則導(dǎo)致測量過程不穩(wěn)定,定位出現(xiàn)誤差,目前解決方法有:最大似然方法(Maximum likelihood method,MIM),通過兩次加權(quán)進(jìn)行最小二乘法[9],能夠?qū)Χㄎ蛔鴺?biāo)獲得較精確數(shù)據(jù),但是需要依賴較多的先驗(yàn)知識(shí)避免測量誤差;交互式多模型-改進(jìn)卡爾曼濾波(Interacting multiple model-Improved Kalman filter, IMM-IKF), 對(duì)非視距誤差具有魯棒性,在未知信道傳播狀態(tài)和非視距誤差參數(shù)情況下,有效抑制非視距誤差,實(shí)現(xiàn)高精度定位[10];擬牛頓算法(Quasi-Newton Methods, QNM)方法,通過傳統(tǒng)的牛頓迭代法求解[11],但是目標(biāo)函數(shù)具有高非線性,迭代法求解會(huì)使定位誤差累積,無法獲得全局最優(yōu)解,雖然可以增加參考基站數(shù)量來提高定位精度,但基站數(shù)量增加使得誤差積累同樣也增加。在大型傳感器網(wǎng)絡(luò)中通過智能算法進(jìn)行尋優(yōu),解決未知基站坐標(biāo)的求解問題,主要算法有:粒子群算法(Particle Swarm Optimization,PSO)利用對(duì)數(shù)障礙函數(shù)對(duì)目標(biāo)函數(shù)改進(jìn),但需要以未知基站的鄰站作為必要的參考信息[12],容易陷入局部最優(yōu);遺傳算法(Genetic Algorithm,GA),通過優(yōu)化初始種群、自適應(yīng)調(diào)整適應(yīng)度的選擇操作以及加入誤差修正算子等方法[13],提高定位算法的性能,但是算法很容易陷入局部最優(yōu)的問題;鏈路質(zhì)量指示 (Link Quality Indicator,LQI)算法,通過改進(jìn)硬件改善測距精度,再結(jié)合粒子群算法改進(jìn)尋優(yōu)結(jié)果,但沒有考慮信道衰減系數(shù)變化對(duì)量測距離的影響。雙階段位置循環(huán)(Two Phase Positioning,TPP)求解算法[14],即啟動(dòng)和細(xì)化,啟動(dòng)過程使用HOP模型,細(xì)化只涉及節(jié)點(diǎn)位于同一跳鄰域內(nèi),提高了測距精度,但通信量與計(jì)算量之間消耗能源較大;粒子群-蟻群算法優(yōu)化(Particle Swarm Optimization Ant Colony Algorithm,PSOACA),搜尋從距匯聚節(jié)點(diǎn)最近的簇頭節(jié)點(diǎn)出發(fā)[15],遍歷所有簇頭節(jié)點(diǎn),最終到達(dá)匯聚節(jié)點(diǎn)的最優(yōu)路徑,每個(gè)粒子對(duì)應(yīng)于一個(gè)簇,只在簇內(nèi)跳動(dòng),并且不重復(fù)之前經(jīng)過的節(jié)點(diǎn),從而實(shí)現(xiàn)最小誤差。
本文對(duì)粒子群算法的慣性權(quán)重進(jìn)行非線性優(yōu)化,粒子群規(guī)模根據(jù)粒子的聚集度、多樣性函數(shù)進(jìn)行收縮擴(kuò)張控制,前期快速進(jìn)行全局尋優(yōu),后期緩慢進(jìn)行局部搜索,最后通過實(shí)驗(yàn)仿真對(duì)算法的性能進(jìn)行驗(yàn)證,定性分析相比其他算法具有優(yōu)勢。結(jié)果表明本文算法收斂性能較好,相比其他算法能有效地抑制測距誤差對(duì)定位的影響,能夠提高節(jié)點(diǎn)的定位精度。
假設(shè)網(wǎng)絡(luò)中存在N個(gè)未知節(jié)點(diǎn)和M個(gè)錨節(jié)點(diǎn)[16],節(jié)點(diǎn)的坐標(biāo)集為φ=[φ1,φ2,…,φM+N],錨節(jié)點(diǎn)的坐標(biāo)分別為(x1,y1),(x2,y2),…,(xM,yM),未知節(jié)點(diǎn)的坐標(biāo)為φ=(φx,φy),φx=(xM+1,xM+2,…,xM+N),φy=(yM+1,yM+2,…,yM+N),則定位誤差模型為:
(1)
因此,無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位問題可轉(zhuǎn)化為約束條件下方程的最優(yōu)解問題。改進(jìn)粒子群搜索算法是一種基于全局誤差函數(shù)的最小化算法,可以利用該算法迭代求解未知節(jié)點(diǎn)的位置,減小未知節(jié)點(diǎn)坐標(biāo)的誤差,直到獲得目標(biāo)函數(shù)的最優(yōu)值。
1.2.1 基本粒子群算法
粒子群算法(Particle Swarm Optimization,PSO)通過學(xué)習(xí)因子c1和c2及慣性權(quán)重ω進(jìn)行更新速度vq,h和位置zq,h:
(2)
式中:q=1,2,…;h=1,2,…;t為迭代次數(shù);vq,h(t)為第q個(gè)粒子在第t次迭代中第h維的速度;zq,h(t)為第q個(gè)粒子在第t次迭代中第h維的位置;pq,h為當(dāng)前最優(yōu)值;pg,h為歷史最優(yōu)值;r1∈(0,1)、r2∈(0,1)為相互獨(dú)立的隨機(jī)函數(shù);ω越大越適合在更大的范圍內(nèi)進(jìn)行搜索,ω越小越能夠保證群體收斂到最優(yōu)位置;c1和c2用于調(diào)整粒子飛行,若c1=c2=0, 粒子將一直以當(dāng)前的速度飛行到邊界,一般都設(shè)定為2。
1.2.2 慣性權(quán)重優(yōu)化
合適的ω能夠控制粒子以往速度對(duì)當(dāng)前速度的影響,平衡全局和局部搜索能力,以較少的迭代次數(shù)找到最優(yōu)解。為了使慣性權(quán)重ω適應(yīng)搜索要求,算法運(yùn)行初期強(qiáng)化全局搜索能力采用較大的慣性權(quán)重,ω遞減變化緩慢,后期進(jìn)行精確的局部搜索采用較小的慣性權(quán)重,ω遞減變化較快,使用非線性遞減(No-Linearly Decreasing Weight,NLDW)策略:
(3)
其中:tmax為最大迭代次數(shù);ωmin=0.35,ωmax=0.95。
1.2.3 收縮擴(kuò)張控制過程
為避免粒子群聚集在某一特定位置或某幾個(gè)特定位置現(xiàn)象的發(fā)生,能夠保持多樣性的同時(shí)具有較好的收斂率[17],引入收縮擴(kuò)張因子ε。
粒子聚集度G判別公式為:
G(t)=Pg(t)/avgPi(t)
(4)
式中:avgPi(t)是所有粒子個(gè)體極值的平均值;Pg(t)是當(dāng)前粒子的全局極值。
0 (5) 式中:c為粒子總個(gè)數(shù);|L|為搜索空間的最長半徑;S為問題的維數(shù);Pij為第i個(gè)粒子的第j個(gè)分量。 算法進(jìn)化前期需要迅速接近全局極值,故此時(shí)收縮擴(kuò)張系數(shù)的值應(yīng)當(dāng)處在較大的位置。而在算法進(jìn)化后期,應(yīng)減慢速度以加強(qiáng)算法的局部搜索能力,因此收縮擴(kuò)張系數(shù)的值需適當(dāng)減小,來提高算法的精確度,則ε: (6) 式中:εstart為ε初值;εend為ε終值。 根據(jù)慣性權(quán)重優(yōu)化和收縮擴(kuò)張控制,粒子群的速度vq,h和位置zq,h修正為: (7) 傳感器網(wǎng)絡(luò)中待確定位置節(jié)點(diǎn)設(shè)置為(x,y),n個(gè)參考點(diǎn)的坐標(biāo)為n1(x1,y1),n2(x2,y2),…,nn(xn,yn),待確定位置節(jié)點(diǎn)到參考點(diǎn)距離為di,由于誤差,di與計(jì)算值不相等,為了減小誤差累積[18],適應(yīng)值函數(shù)選擇為距離估算值與實(shí)際值的均方根誤差f(x,y): (8) 式中:(xi,yi)表示第i個(gè)參考點(diǎn)坐標(biāo);n為目標(biāo)點(diǎn)鄰近參考點(diǎn)數(shù)目,n≥3。 由于f(x,y)會(huì)將不同節(jié)點(diǎn)對(duì)應(yīng)的殘差視為同等地位[19],待定位節(jié)點(diǎn)的估計(jì)位置將傾向于滿足殘差小的錨節(jié)點(diǎn)約束,收斂于真實(shí)位置,通過對(duì)錨節(jié)點(diǎn)區(qū)分可信程度,在f(x,y)對(duì)未知節(jié)點(diǎn)設(shè)置不同的權(quán)重wi,提高定位精度: (9) 式中:n為未知節(jié)點(diǎn)總數(shù);節(jié)點(diǎn)u的鄰居錨節(jié)點(diǎn)ID號(hào)為1,2,…;距離測量值分別為du1,du2,…;dul為節(jié)點(diǎn)u到鄰居錨節(jié)點(diǎn)l的距離測量值;duk為節(jié)點(diǎn)u到鄰居錨節(jié)點(diǎn)k的距離測量值;dlk為錨節(jié)點(diǎn)l到錨節(jié)點(diǎn)k的距離測量值。 則適應(yīng)度函數(shù)選擇重新構(gòu)造為: (10) wi由未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離測量值決定,其關(guān)系為反比關(guān)系,為避免迭代算法中出現(xiàn)局部最優(yōu),控制某個(gè)錨節(jié)點(diǎn)的損失或所有錨節(jié)點(diǎn)的累計(jì)損失過大,增設(shè)錨節(jié)點(diǎn)定位誤差閾值與所有錨節(jié)點(diǎn)定位誤差累積閾值分別為bth、Bth,避免算法陷入局部最優(yōu): (11) 這樣有效地增強(qiáng)可信錨節(jié)點(diǎn)的作用,抑制不可信錨節(jié)點(diǎn)的影響。 (1)隨機(jī)初始化粒子群搜索算法的相關(guān)參數(shù),主要包括粒子群總數(shù)、速度、位置,其中粒子位置為傳感器節(jié)點(diǎn)的坐標(biāo)。 (2)根據(jù)公式(10)計(jì)算粒子的適應(yīng)值,得到粒子的pq,h和pg,h,選擇當(dāng)前最優(yōu)適應(yīng)值f(xi,yi)所對(duì)應(yīng)的最佳粒子群位置(xi,yi)。 (3)根據(jù)公式(7)更新粒子群的位置、速度、pq,h、pg,h,獲得新一代粒子位置(xj,yj)。 (4)保留較優(yōu)的f(xi,yi)與f(xj,yj),并將該適應(yīng)值對(duì)應(yīng)的粒子群位置記為(x*,y*),(x*,y*)表示當(dāng)前種群中最優(yōu)位置。 (5)判斷是否滿足算法定位精度,若滿足,輸出全局最優(yōu)解對(duì)應(yīng)的粒子群位置,否則轉(zhuǎn)至步驟(3)。 選擇200 m×200 m的高粱試驗(yàn)場地進(jìn)行了未知傳感器節(jié)點(diǎn)定位試驗(yàn),場地內(nèi)栽種的大豆植株平均約高30 cm,且植株栽種整齊。將終端監(jiān)測節(jié)點(diǎn)在隨機(jī)散布于場地中,每個(gè)節(jié)點(diǎn)擁有相同的通信半徑,未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)位置信息隨機(jī)產(chǎn)生。參數(shù)設(shè)置如下:初始化粒子總數(shù)為120,最大迭代次數(shù)為300。 PSO、GA、PSOACA、IPSO算法在精準(zhǔn)農(nóng)業(yè)無線傳感器定位過程中目標(biāo)函數(shù)適應(yīng)值的變化曲線如圖1所示。 圖1 不同算法目標(biāo)函數(shù)適應(yīng)值變化曲線Fig.1 Variation of fitness function of different algorithm objective function 實(shí)驗(yàn)結(jié)果表明,IPSO算法的求解速度明顯快于其他算法,能夠用較少的迭代次數(shù)獲得更精確的解。這主要是由于IPSO算法使用慣性權(quán)重優(yōu)化、收縮擴(kuò)張控制,從而能夠較好地進(jìn)行局部、全局搜索,避免搜索的單一性,IPSO增加了PSO算法收斂速度和全局收斂性,最終收斂得到最優(yōu)解,能夠使無線傳感器獲得精確定位。 歸一化平均定位誤差評(píng)價(jià)指標(biāo)E[20]: (12) 歸一化平均定位誤差與消耗時(shí)間的對(duì)比關(guān)系如圖2所示,涉及的算法有MIM 、IMM-IKF、 QNM、PSO、GA、PSOACA、IPSO。 圖2 歸一化平均定位誤差與消耗時(shí)間的關(guān)系Fig.2 Relationship between normalized mean location error and consumption time 從圖2可以看出,隨著消耗時(shí)間的增加,各種歸一化平均定位誤差都逐漸下降,但是IPSO消耗時(shí)間明顯優(yōu)于其他定位算法,在1 s時(shí)刻即可獲得較低的定位誤差,在3 s左右開始保持不變,表明該算法具有很強(qiáng)的穩(wěn)定性,而且具有很高的定位精度。 圖3為各種算法在錨節(jié)點(diǎn)數(shù)量不同的情況下的歸一化平均定位誤差。 圖3 錨節(jié)點(diǎn)個(gè)數(shù)對(duì)定位性能的影響Fig.3 Influence of anchor node number on positioning performance 從圖3可以看出,隨著錨節(jié)點(diǎn)比例不斷的增大,各種算法的平均定位誤差都逐漸減小,并逐漸趨于穩(wěn)定。在相同錨節(jié)點(diǎn)比例情況下,IPSO算法優(yōu)化后的平均定位誤差更小,這說明IPSO算法在少量的錨節(jié)點(diǎn)的情況下,能取得較好的定位效果。 圖4為各種算法的定位誤差隨著測距誤差變化的曲線。 圖4 定位誤差隨著測距誤差變化曲線Fig.4 Location error versus range error curve 從圖4可以看出,隨著測距誤差的增加,各種算法定位誤差都呈上升的趨勢。但是,相對(duì)于其他算法,IPSO算法受測距誤差的影響相對(duì)較小,能夠在一定程度上抑制節(jié)點(diǎn)測距誤差的累加;當(dāng)測距誤差比較大時(shí),IPSO算法的定位效果更加穩(wěn)定。說明IPSO算法優(yōu)化定位有著更好的抗誤差性。 本文算法對(duì)粒子群算法優(yōu)化主要包括慣性權(quán)重參數(shù)、群體規(guī)模收縮擴(kuò)張控制,慣性權(quán)重參數(shù)采用非線性方法,即算法運(yùn)行初期強(qiáng)化全局搜索能力采用較大的慣性權(quán)重,后期進(jìn)行精確的局部搜索采用較小的慣性權(quán)重,提高群體算法對(duì)起始錨節(jié)點(diǎn)的精確度;群體規(guī)模收縮擴(kuò)張控制算法前期群體規(guī)模擴(kuò)張操作,后期收縮操作,提高算法對(duì)錨節(jié)點(diǎn)的穩(wěn)定性,仿真實(shí)驗(yàn)結(jié)果表明,本算法獲得了較好的定位效果,能夠提高網(wǎng)絡(luò)工作效率、優(yōu)化網(wǎng)絡(luò)性能,降低農(nóng)業(yè)生產(chǎn)成本,為農(nóng)業(yè)智能化研究提供了新的思路和方法。1.3 適應(yīng)度函數(shù)選擇
1.4 算法流程
2 實(shí)驗(yàn)仿真
2.1 收斂性能對(duì)比
2.2 定性分析
2.3 錨節(jié)點(diǎn)個(gè)數(shù)對(duì)定位性能的影響
2.4 測距誤差對(duì)定位性能的影響
3 結(jié) 語