傳感器網絡中閾值Nesterov加速梯度下降定位方法*

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

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

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

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

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

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

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

1 系統模型

1.1 通信模型

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

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

(6)

式中:

(7)

1.2 多約束目標函數轉化

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

(8)

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

μ[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)

的表現形式。

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

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

(10)

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

2 NAGT算法

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

2.1 基本NAG基本原理

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

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

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

(11)

θt=θt-1-vt

(12)

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

圖1 NAG尋優中的變量關系圖

2.2 梯度等效

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

(13)

2.3 損失限制閾值

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

(14)

(15)

2.4 算法流程

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

步驟1 初始化 設置θ0,γ,η,v0=0,j=1,迭代監測間隔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 輸出參數θN,退出。

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

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

3 仿真實驗

為了驗證定位算法的性能,實驗采用MATLAB仿真平臺,場景設置為100 m×100 m的正方形區域,UBase(xu,yu)的真實坐標不作特殊說明時為(50,50),已知基站Basei位置隨機設定,且彼此間能保證正常的信號通信。結合文獻[14]和實驗測試,仿真參數設置如下:γ=0.9;η=0.001;閾值設置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為尋優核心的定位算法,進行定位性能的對比。在仿真實驗中,為降低PSO陷入局部最優的概率,將其搜索粒子數設為100,粒子的個體最優權重系數設置為c1=1,群體最優值的權重系數設置為c2=4,慣性權重設置為w=0.8[10]。

3.1 定位精度分析

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

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

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

3.2 對基站數的敏感性

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

圖3 基站數N對各算法影響示意圖

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

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

3.3 定位速率的比較

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

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

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

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

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

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

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

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

4 總結

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

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