傳感器網(wǎng)絡(luò)中閾值Nesterov加速梯度下降定位方法*

秦寧寧,陳 肯,孫文心(江南大學輕工過程先進控制教育部重點實驗室,江蘇 無錫 214122)

無線傳感器網(wǎng)絡(luò)技術(shù)的快速發(fā)展對基站的定位精度和定位效率提出了更高的要求?；跍y距的定位算法相對于非測距的定位算法[1],有著更高的定位精度[2]。作為間接測距的代表,RSSI定位算法,由于不依賴于外設(shè)硬件的易于實現(xiàn)性,促使其成為了研究的熱點。但另一方面,受無線信號強度易擾特性的影響[3],其量測過程中的不穩(wěn)定性,也會導致測距存在誤差,進而影響定位精度。

為平衡RSSI信號的不確定性引發(fā)的定位偏差問題,通常從數(shù)據(jù)預處理與定位求解2個方面著手解決[4]。在預處理環(huán)節(jié)中,通常采用增加信道參數(shù)的測量頻次、利用濾波器對RSSI數(shù)據(jù)進行前置處理[5],或者對信號傳輸模型進行高斯擬合[6]等方法來提高模型精度,從而達到精確距離估計的目的。

而在定位求解的過程中,對于參考基站較少的傳感器網(wǎng)絡(luò),極大似然估計技術(shù)[7]可以被用來求解聯(lián)立方程中的未知基站坐標。恰如文獻[8]給出的一種基于最大似然求解的定位算法,利用兩次加權(quán)最小二乘法,獲得了更為精確的定位坐標,但其未考慮信道模型的衰減系數(shù)對信號傳輸距離的影響,過分依賴先驗知識來減小測量誤差。針對環(huán)境因素考慮的缺失問題,一種基于RSSI的加權(quán)概率定位算法[9]被提出,在一定程度上強調(diào)了環(huán)境對定位模型的影響,但存在環(huán)境參數(shù)一旦確定就不再調(diào)整的弊端,因此該算法并不能很好地克服通信環(huán)境的不穩(wěn)定性,對定位精度的改善也不明顯。

雖然可以通過增加參考基站,提高定位精度,但隨著基站數(shù)的增加,基站與基站間的RSSI值的誤差積累,也會降低未知基站的定位精度。因此,在多基站的大型傳感器網(wǎng)絡(luò)中,通常使用群智能的尋優(yōu)策略,解決未知基站坐標的求解問題。

文獻[10]就曾基于RSSI信息,提出了一種基于粒子群PSO(Particle Swarm Optimization)的定位算法,利用對數(shù)障礙函數(shù)對目標函數(shù)進行改進,但該方法容易陷入局部最優(yōu)且必須以未知基站的鄰站作為必要的參考信息。針對以上問題,馮秀芳等人提出了一種分步粒子群IPSO(Split-step Particle Swarm Optimization)的定位算法[11],一定程度上避免了局部最優(yōu)的情況,但數(shù)據(jù)處理量會出現(xiàn)陡增現(xiàn)象,很難滿足定位的實時性需求。針對多數(shù)算法尋優(yōu)速度慢的問題,文獻[12]提出了基于鏈路質(zhì)量指示LQI(Link Quality Indicator)的RSSI測距方法,利用硬件提高了測距精度的同時,改進了粒子群算法尋優(yōu)精度,但未考慮信道衰減系數(shù)變化對量測距離的影響。

綜上,論文以參考基站的RSSI信息為基礎(chǔ),在傳感器網(wǎng)絡(luò)的定位過程中,同時兼顧精度與求解效率,提出了一種閾值Nesterov加速梯度下降定位方法NAGT(Nesterov Accelerated Gradient Descent with Threshold)。新方法將每個參考基站的RSSI量測信息等效為單次梯度,通過更新尋優(yōu)動量,加速收斂速度并提高尋優(yōu)精度,增加損失函數(shù)閾值環(huán)節(jié)以降低陷入局部最優(yōu)的風險概率,從而在優(yōu)化定位精度的同時,也保證了求解速率。

1 系統(tǒng)模型

1.1 通信模型

無線通信中普遍采用的基本的信號傳輸模型如式(1)所示[4]

Pr(d)=P0-10αlog(d/d0)+Xσ

(1)

式中:Pr(d)為基站對距離d處的接收信號強度,P0為基站對參考距離d0處接收信號強度,α為信號衰減系數(shù),Xσ是服從N(0,σ2)分布的高斯白噪聲。

(2)

可得Pri亦服從高斯過程分布,其概率密度函數(shù)為

(3)

利用Xσi的對稱特性,得:

(4)

因此,對于N個已知基站Basei而言,存在關(guān)于參數(shù)θ=(x,y,P0,α)的最大似然函數(shù),如式(5)所示:

(5)

(6)

式中:

(7)

1.2 多約束目標函數(shù)轉(zhuǎn)化

鑒于直接求解形如式(6)的多約束最優(yōu)化問題十分困難的情況,受文獻[10]的啟發(fā),引入對數(shù)障礙函數(shù)將多約束目標函數(shù)轉(zhuǎn)化成無約束函數(shù)。其中,對數(shù)障礙函數(shù)的一般通用形式如下:

(8)

式中:μ為障礙變量,ci(z)≥0,ci(z)=|θ-θbound|,θbound為所求參數(shù)θ的各分量的取值邊界,可以將式(6)中的約束條件轉(zhuǎn)化為:

μ[ln(P0-P0min)+ln(P0max-P0)+ln(α-αmin)+
ln(αmax-α)+ln(x/d0)-(xmin/d0)+ln(xmax/d0-x/d0)+
ln(y/d0-ymin/d0)+ln(ymax/d0-y/d0)]

(9)

的表現(xiàn)形式。

需要說明的是,觀察式(7)可以發(fā)現(xiàn),由于P0和α不包含于log(·)內(nèi),因此P0和α的微量擾動會對目標函數(shù)f產(chǎn)生較大的波動影響,不利于定位精度的提高。而利用式(9)的障礙函數(shù)變形,重新規(guī)劃變量的表達,從形式上一定程度地抑制了P0和α的擾動引發(fā)大誤差的現(xiàn)象。

基于上述推演分析,將式(7)與式(9)結(jié)合,式(6)可以更新表達為式(10)

(10)

至此關(guān)于式(6)的多約束定位求解問題已經(jīng)規(guī)劃為無約束尋優(yōu)問題,使得利用NAGT方法成為可能。

2 NAGT算法

在信道環(huán)境參數(shù)未知,已知N個基站Basei的網(wǎng)絡(luò)中,解決1個未知基站UBase的多約束定位求解問題,在規(guī)劃成式(10)的基礎(chǔ)上,可將定位過程中基站增加等效為梯度迭代中時間的遞增,利用基本NAG的迭代原理,在不斷的更新尋優(yōu)過程中,實現(xiàn)對新目標函數(shù)式(10)的求參。

2.1 基本NAG基本原理

Nesterov加速梯度下降法(Nesterov Accelerated Gradient Descent NAG)在隨機梯度下降法SGD(Stochastic Parallel Gradient Descent)的基礎(chǔ)上,通過結(jié)合動量法思想,優(yōu)化了尋優(yōu)效率。

NAG方法的基本迭代公式如下式所示:

vt=γvt-1+ηθJ(θt-1-γvt-1)

(11)

θt=θt-1-vt

(12)

式中:第t時刻的動量vt,動量項γ,θJ(θt-1-γvt-1)為損失函數(shù)J關(guān)于θt-1的梯度,η為步長,θt為所求當前t時刻的參數(shù)。各變量之間的尋優(yōu)關(guān)系,如圖1所示。

圖1 NAG尋優(yōu)中的變量關(guān)系圖

2.2 梯度等效

為構(gòu)建N個基站之間的迭代關(guān)系,基本NAGT將第i個基站對應于式(11)中的t時刻,遍歷每個已知基站來更新動量及參數(shù)來達到定位誤差最小。鑒于式(10)是包含N個基站信息的整體目標函數(shù),為每個獨立基站Basei定義損失函數(shù)ei作為獨立目標函數(shù),以力求盡可能無損地等效整體目標函數(shù)。

(13)

2.3 損失限制閾值

為克服迭代算法中出現(xiàn)的局部最優(yōu)的痼疾,NAGT增設(shè)單基站的損失函數(shù)的閾值bth與所有基站累積閾值Bth,分別控制某個基站的損失或所有基站的累計損失過大,避免算法陷入局部最優(yōu)。即應確保下式成立:

(14)

(15)

2.4 算法流程

通過梯度等效步驟,可以利用提出的NAGT算法來獲取UBase坐標。NAGT算法的基本步驟如下:

步驟1 初始化 設(shè)置θ0,γ,η,v0=0,j=1,迭代監(jiān)測間隔kth與迭代上限Kth;獲取N個Basei坐標(xi,yi),及其與UBase間的Pri,i=1,2,3,…,N;

步驟2i=1;

步驟3 計算vi,θi,ei,i+1→i;

步驟4 若i≤N,返回步驟3;

步驟5j+1→j,vN→v0,θN→θ0;

步驟6 若j≥Kth,則進入步驟9;

步驟8 返回步驟2;

步驟9 輸出參數(shù)θN,退出。

考慮到NAGT算法本身對θ0=(x0,y0,P0,α)的不敏感特性,因此根據(jù)式(6)的約束條件,隨機設(shè)置θ0的取值。

算法中,步驟3～步驟4完成了對所有已知基站Basei的遍歷,等效為梯度的遞推尋優(yōu)過程;步驟5～步驟7中,通過限制ei(θ;xi,yi,Pri)的大小以達到控制局部最優(yōu)的目的。因此,設(shè)置迭代監(jiān)測間隔kth,定時檢測并避免算法陷入局部最優(yōu)?？v觀步驟2～步驟8,算法將每j輪遍歷基站得到的最優(yōu)值,作為下一輪尋優(yōu)的初始值,保證了迭代的連續(xù)性,有利于提高結(jié)果的準確性。

3 仿真實驗

為了驗證定位算法的性能,實驗采用MATLAB仿真平臺,場景設(shè)置為100 m×100 m的正方形區(qū)域,UBase(xu,yu)的真實坐標不作特殊說明時為(50,50),已知基站Basei位置隨機設(shè)定,且彼此間能保證正常的信號通信。結(jié)合文獻[14]和實驗測試,仿真參數(shù)設(shè)置如下:γ=0.9;η=0.001;閾值設(shè)置bth=6,Bth=10;μ=5;kth=50;Kth=200;P0min=-25 dB,P0max=-50 dB;αmin=1;αmax=6;xmin=ymin=0;xmax=ymax=100。

實驗將論文提出的NAGT算法與以NAG、 SGD和PSO為尋優(yōu)核心的定位算法,進行定位性能的對比。在仿真實驗中,為降低PSO陷入局部最優(yōu)的概率,將其搜索粒子數(shù)設(shè)為100,粒子的個體最優(yōu)權(quán)重系數(shù)設(shè)置為c1=1,群體最優(yōu)值的權(quán)重系數(shù)設(shè)置為c2=4,慣性權(quán)重設(shè)置為w=0.8[10]。

3.1 定位精度分析

通過圖2所示的定位誤差分布箱式圖,可以看出:無論是從誤差中值、誤差分布的范圍,還是異常點數(shù)目分析,和其他3種算法相比,論文給出NAGT方法,具有分布集中且最小的定位誤差,同時定位偏失引發(fā)的誤差異常情況也最為稀少。這是由于,NAGT在尋優(yōu)過程中,不斷利用動量對上一時刻獲得的參數(shù)進行修正,提高了尋優(yōu)精度與定位精度。

圖2 4種算法定位誤差分布比較

PSO算法通過空間中的粒子尋優(yōu),定位精度雖不及NAGT,但也表現(xiàn)良好。NAG算法由于沒有添加閾值對定位損失函數(shù)進行限制,因此精度尚不如PSO。SGD由于更側(cè)重于提高尋優(yōu)的速率,降低計算機的運算負載,忽略了尋優(yōu)的精度,因此在4種算法比較中,定位精度最低。

3.2 對基站數(shù)的敏感性

雖然基站數(shù)目N的增長對于定位精度的提升有著正向激勵,但不同機理驅(qū)動下的算法受N的影響程度和范圍也不盡相同。因此,本實驗分析了4種算法中,基站數(shù)目N對定位精度的影響情況。設(shè)定6個不同基站數(shù)目的實驗場景,N=5,10,15,20,25,30,4種算法分別對每個場景進行1 000次仿真,通過對其平均定位誤差的比較,分析不同算法對基站數(shù)目的敏感性,仿真數(shù)據(jù)分析結(jié)果如圖3所示。

圖3 基站數(shù)N對各算法影響示意圖

實驗中,可以看出4種算法的定位精度均隨著基站數(shù)目N的增加有所提高,在數(shù)據(jù)曲線上體現(xiàn)為平均定位誤差的下降。這種下降的趨勢在N<10的小規(guī)模網(wǎng)絡(luò)中更為陡峭,但隨著N的增加,對于減少定位誤差的貢獻,逐漸減緩。相比其他3種算法,NAGT在多數(shù)實驗場景中,具有最小的平均定位誤差。

需要說明的是,由于PSO的定位機理是將所有基站列入尋優(yōu)的目標函數(shù),因此在N<10的小規(guī)模場景中,PSO算法相比于其他3種算法具有更小的平均定位誤差。但隨著N的增加(N≥10)對定位誤差的貢獻減少,PSO算法的優(yōu)勢減緩,而基于自適應調(diào)節(jié)動量為核心的NAGT算法優(yōu)勢凸顯,其平均定位誤差基本保持在1 m～2 m微小區(qū)間內(nèi)。

3.3 定位速率的比較

若以定位過程的時長作為定位速率的考量,在N=20個Basei的場景中,針對同一UBase,對3種算法(NAGT,PSO和SGD)進行1 000次定位,并計算平均單次定位時長,計算數(shù)據(jù)如表1所示。

表1 3種算法定位時長對比表

3種算法中,SGD和NAGT法的定位速度相對較快,時長控制在0.4 s之內(nèi),PSO定位速率最差,平均定位耗時接近3 s。PSO方法在尋優(yōu)過程中需要并行處理所有Basei坐標,而基于梯度思想的NAGT和SGD,在尋優(yōu)過程中每次迭代,只需利用一個Basei坐標信息,因此計算負荷較小。可見,NAGT在保證定位精度的同時,也能將定位速率穩(wěn)定在較高的算法水平上,體現(xiàn)了NAGT方法的實用價值。

3.4 未知基站坐標對精度影響

本實驗通過對UBase 位于不同位置的定位誤差測試,考量4種算法定位精度對UBase 位置的敏感程度。分別設(shè)定UBase 位于區(qū)域?qū)蔷€上11個不同位置,以UBasei(xu,i,yu,i),i=1,2,…,11進行標識,其中xu,i=yu,i=10·(i-1)。基于上述11個位置場景,分別對N=20個隨機分布的已知基站進行 1 000 次重復實驗,實驗數(shù)據(jù)為平均定位誤差,實驗數(shù)據(jù)分析結(jié)果如圖4所示。

圖4 不同UBase 對定位誤差的影響分析

從圖4曲線的整體分布和趨勢可以看出,NAGT的定位精度優(yōu)于其他3種算法,PSO與NAG的性能基本相當,而SGD因為具有超過15 m的平均定位誤差,定位精度最差。當UBasei位于區(qū)域中心地帶(即i=2,3,…,10)時,4種算法的平均定位誤差均能穩(wěn)定在各自較低的誤差范圍內(nèi)。相對于其他算法,論文提出的NAGT,具有最小的平均定位誤差,即定位誤差穩(wěn)定在1 m左右。

當UBasei位于區(qū)域角落,即i=1,11時,由于自身位置較為偏遠,因此接收到的RSSI信號衰減相對嚴重,4種算法的平均定位誤差均均呈現(xiàn)出陡升增長。且相對于同時利用所有Basei信息的PSO方法,NAGT算法對于信號衰減所受不良的影響略微明顯,因此在UBasei位于邊界附近時,會出現(xiàn)短暫的定位誤差略高于PSO的現(xiàn)象。

4 總結(jié)

基于RSSI的定位算法雖然有精度相對較高,所需硬件成本低的定位優(yōu)勢,但因通信模型易擾性使其應用具有很大的局限性[15]。針對上述缺陷,論文將包含信道衰減系數(shù)范圍的對數(shù)障礙函數(shù)進行拆分,利用 NAGT方法進行迭代尋優(yōu),在保證定位速率的情況下,得到了更加準確的定位結(jié)果。

雖然NAGT方法解決了一般智能算法定位速率慢、定位精度相對較低的問題,但存在尋優(yōu)結(jié)果易陷入局部最優(yōu)導致定位誤差大、小型傳感器網(wǎng)絡(luò)定位精度較低的缺陷。因此,提高RSSI定位模型精度和降低局部最優(yōu)概率也將被作為未來提升NAGT定位方法的有效途徑,以此開展進一步的研究。