使用最速下降算法提高極大似然估計算法的節點定位精度
2008-12-31 00:00:00石琴琴霍宏方濤李德仁
計算機應用研究 2008年7期
摘 要：闡述了極大似然估計算法用于無線傳感器網絡節點自定位的原理；闡述了最速下降算法求非線性方程組最優解的原理；提出在距離測量誤差較大的情況下，使用最速下降算法優化極大似然估計算法所得的節點定位值，并通過模擬實驗證實其可行性。實驗結果表明，在無須多余通信代價的條件下，優化處理使定位精度得到很大提高，且算法收斂快，計算代價小，適用于無線傳感器網絡的節點自定位。
關鍵詞：無線傳感器網絡；節點自定位；極大似然估計算法；最速下降算法
中圖分類號：TP309 文獻標志碼：A
文章編號：1001-3695(2008)07-2038-03
Using steepest descent method to improve node localization
accuracy of maximum likelihood estimation
SHI Qinqin1，HUO Hong1，FANG Tao1，LI Deren1，2
(1.Institute of Image Processing Pattern Recognition， Shanghai Jiaotong University， Shanghai 200240， China；2.State Key Laboratory of Information Engineering in Surveying， Mapping Remote Sensing， Wuhan University， Wuhan 430072， China)Abstract:This paper expounded the localization principle of maximum likelihood estimation.Also， presented the principle of using steepest descent method to find an optimal solution for a system of nonlinear equations.Proposed steepest descent method to refine the initial node locations gotten by maximum likelihood estimation as the distance measurement error was large， and corresponding simulation experiment was done to testify the validity and advantages of such a disposal. The simulation results show that the refinement can improve the localization accuracy obviously with no more communication cost and small computation cost， fit to be utilized in wireless sensor networks.
Key words:wireless sensor network；node localization；maximum likelihood estimation；steepest descent method
0 引言
節點的自定位問題是無線傳感器網絡需要解決的基本問題，在多數應用中決定著信息的可用性[1，2]。無線傳感器網絡的定位算法需要考慮網絡節點廉價且需大量部署的特點，通常要求滿足自組織性、健壯性、能量高效、分布式計算等要求[3]。
既有的分布式無線傳感器網絡節點定位機制，其基本思路大致相同:在傳感器網絡中部署一定比例的特殊節點，這類節點可以通過特定方式獲取自身坐標（配備GPS接收機或部署時測定），在文獻中通常被稱為參考節點、錨節點或形象地稱為燈塔；其他節點稱為未知節點，通過測量與參考節點之間的距離、角度，或依據相對位置關系、網絡連通性等信息，使用一定的定位算法得出自身的坐標[4~9]。
當未知節點可獲取的定位計算條件為與周圍參考節點之間的距離測量值時，極大似然估計算法是常用的分布式定位算法的選擇[10]。未知節點獲取到與三個以上不在同一直線上的參考節點之間的距離測量值，即可使用極大似然估計算法完成定位。根據文獻[10]的實驗結論可知，極大似然估計算法對測距誤差敏感，以節點平均射程的百分比表示誤差，在網絡測距誤差較小的情況下，算法可以獲得較高的定位精度；但當網絡測距誤差較大時，算法存在較大的定位誤差，距離估計誤差10％可能引起超過30％的定位誤差。
為了改善極大似然估計算法在測距誤差較大環境下的定位精度，并顧及到無線傳感器網絡節點本身在計算能力和通信能耗方面的局限性，本文提出使用最速下降算法對極大似然估計算法獲得的初始定位值進行求精計算。最速下降算法在既有的極大似然估計算法的計算條件下展開，不增加任何通信開銷，將定位問題看做是非線性方程組在一定范圍內求最優解的問題，通過迭代計算達到提高定位精度的目的。
為了降低問題討論的復雜度，本文所述算法及理論只在二維空間層面展開，但可擴展應用于三維空間。
1 極大似然估計算法
如圖1所示，1，2，3，…，n為n個參考節點，其坐標已知，分別為(x1，y1)，(x2，y2)，…，(xn，yn)；它們到未知節點P的距離測量值分別為d1，d2，d3，…，dn。假設節點P的待求坐標為(x，y)，則采用極大似然估計算法對其求解的過程 [3]如下：
首先，存在下列一組方程:
使用標準的最小均方差估計方法可得到節點P的坐標為
X^=(ATA)-1ATb（3）
分析上述公式的推導過程，可以看出式（1）是一組圓的方程，因為測距存在誤差，這組圓不能交于一點，即方程組無解。將式（1）線性化為式（2），得到一組直線方程，使用標準的最小均方差估計方法對其求解，所得的未知數的解為式（2）的最優解，同時也是式（1）的一組近似解，即上述極大似然估計算法可以求得未知節點位置的一個近似值。
2 最速下降算法
最速下降算法也稱為梯度法，是一種極小化的優化方法。最速下降算法是由牛頓法改進而得的。牛頓法的收斂速度雖然很快，但因為牛頓法要求各函數的偏導數，使用起來極不方便，相對而言，最速下降算法的算法簡單，更易于編程。本文參考文獻[11]介紹最速下降算法。
首先，一個非線性代數方程組的一般形式為
最速下降算法的核心原理是將上述方程組的求解問題轉換為求多元函數的極小值的等效問題來解決。其步驟如下：
a)由式（4）構造目標函數：
F(x1，x2，x3，…，xi，…，xn)=ni=1f 2 i(x1，x2，x3，…，xi，…，xn)（5）
式（4）的解就是式（5）的零極小值點；反之亦然。
b)計算初始，每個未知數須要賦予不全為0的初值x1(0)， x2(0)，x3(0)，…，xi(0)，…，xn(0)。
c)假設迭代計算已進行到第k次，此時未知數的值為x1(k)，x2(k)，x3(k)，…，xi(k)，…，xn(k)，目標函數為F=F(x1(k)，x2(k)，x3(k)，…，xi(k)，…，xn(k))。
d)如果|F|＜E(容許誤差)， 則認為x1(k)，x2(k)，x3(k)，…，xi(k)，…，xn(k)就是所求的一組解；否則繼續進行e）。
e)計算差商
然后再從c)開始迭代。
根據上面的介紹，最速下降算法是一種迭代計算求非線性方程組解的方法。在迭代計算開始之前，須對未知變量賦予初始值。此外，最速下降算法求得的最優解是局部最優解，因此初始值的合理性非常重要，會影響最終結果是否合理。
3 使用最速下降算法提高極大似然估計算法的定位精度
3．1 算法描述
極大似然估計算法給出未知節點的一個位置近似值，最速下降算法則以未知數的合理初值為基礎，在一定的范圍內搜索未知數的最優解，兩者在理論上具備結合使用的可行性，而且最速下降算法根據極大似然估計算法現有的信息條件展開，無須額外的通信開銷來獲取計算條件。
根據第1章的介紹，極大似然估計算法對參與計算的參考節點數目沒有特殊要求，本文根據文獻[10]對多跳傳感器網絡仿真實驗一般場景的描述，限定每個未知節點可聯絡到的參考節點個數為4。設未知節點的待求坐標為（x，y），參與計算的四個參考節點編號為A、B、C、D，其已知坐標分別為（xA，yA）、（xB，yB）、（xC，yC）、（xD，yD），未知節點與各參考節點之間的距離測量值分別為dA、dB、dC、dD。每個未知節點首先使用極大似然估計算法估計出自身位置的一個近似值；然后采用最速下降算法對該初始定位值進行迭代優化。具體算法過程如下：
首先，列出以下的非線性方程組
其中：x、y、dA、dB、dC、dD都是式（9）的待定未知數。分別用v1、v2、v3、 v4表示式（9）中四個等式左邊未知數的函數表達式，則迭代過程的目標函數定義為
F(x，y，dA，dB，dC，dD)=v21+v22+v23+v24(10)
式（9）的解即為目標函數F的零極小值點。
迭代初始，x、y的初始值取極大似然估計算法得到的位置近似值，dA、dB、dC、dD的初始值取原測量值，然后根據第2章介紹的迭代步驟展開迭代計算，并求得一組x、y、dA、dB、dC、dD的值，使得F收斂于設定的限值，即為未知數的最優解。
3．2 仿真實驗
如圖2所示，A、B、C、D為監測區域內的4個參考節點，在一塊可以被4個參考節點的信號同時覆蓋的區域內的不同位置選擇10個未知節點作為實驗樣本。根據文獻[12]的研究結論，本文假設未知節點與參考節點之間的距離測量誤差服從N（0，σ2）分布。其中：σ是參考節點與未知節點之間真實距離乘以一個百分比得到的數值，本文取該百分比分別為10％和5％，以測試在不同測距誤差條件下算法的表現。
在MATLAB環境下編程模擬未知節點與參考節點之間的距離觀測值，并實現對10個樣本節點的極大似然估計算法初步定位及最速下降算法優化處理。
采用節點真實位置與仿真計算所得位置之間的距離表示定位誤差，即點位誤差，并作為衡量定位精度的指標。仿真結果顯示，在σ為實際距離10％的測距誤差條件下，最速下降算法可以將極大似然估計算法的定位精度平均提高約38％，最大的迭代次數為13次，最小的迭代次數為6次；在σ為實際距離5％的測距誤差條件下，定位精度平均提高約34％，最大的迭代次數為10次，最小的迭代次數為7次。
在圖3（a）和（b）中分別繪制了在兩種測距誤差條件下，10個樣本節點迭代計算過程中的點位誤差值所成的曲線。圖示使用最速下降算法對極大似然估計算法所得的定位值進行迭代求精的效果。對比兩圖中曲線的初始值可以看出，在σ為實際距離的5％時，樣本節點的平均初始定位誤差明顯低于當σ為真實距離的10％時的平均初始定位誤差，這是由極大似然估計法對測距誤差敏感的屬性決定的。根據兩圖中曲線的趨勢則可以發現，在兩種誤差條件下，使用最速下降算法對各樣本節點均能起到減小定位誤差的作用。
4 結束語
本文剖析了極大似然估計算法應用于無線傳感器網絡節點自定位的原理，指明該算法對網絡測距誤差敏感。在網絡測距誤差較大的情況下，計算結果相對于真實的節點位置可能存在較大誤差；介紹了最速下降算法求解非線性方程組最優解的原理，并指出合理賦予未知數初值是有效求解的關鍵；分析使用最速下降算法對極大似然估計算法所得的初始定位值進行迭代優化的可行性及優越性，并通過仿真實驗進行證實。實驗結果表明，在無須增加任何通信代價的條件下，能夠用較小的計算代價獲得定位精度的提高。因此，使用極大似然估計算法實現節點初步定位后，增加由最速下降算法完成的優化處理步驟可以有效提高其作為無線傳感器網絡節點自定位算法的適用性。
參考文獻：
［1］MAUVE M，WIDMER J，HARTENSTEIN H.A survey on position based routing in mobile Ad hoc networks[J].IEEE Network Magazine，2001，15(6):30-39.
[2]MEGUERDICHIAN S，KOUSHANFAR F，QU Gang，et al.Exposure in wireless Ad hoc sensor networks[C]//Proc of ACM Special Interest Group on Mobility of Systems， Users， Data and Computing.Rome， Italy: ACM Press，2001:139150.
[3]孫利民，李建中，陳渝，等.無線傳感器網絡[M].北京: 清華大學出版社，2005.
[4]NICULESCU D，NATH B.Ad hoc positioning system[C]//Proc of Global Telecommunications Conference.San Antonio， TX:IEEE Communications Society，2001:2926-2931.
[5]NAGPAL R，SHROBE H，BACHRACH J.Organizing a global coordinate system from local information on an Ad hoc sensor network[C]//Proc of the 2nd Int’1 Workshop on Information Processing in Sensor Networks (IPSN’03).Palo Alto， CA:SpringerVerlag Press，2003:333-348.
[6]NICULESCU D， NATH B. DV based positioning in Ad hoc networks[J].Journal of Telecommunication Systems，2003，22(1-4):267-280.
[7]NICULESCU D，NATH B.Ad hoc positioning system (APS) using AOA[C]//Proc of IEEE INFOCOM.San Francisco: IEEE Computer and Communications Societies，2003:17341743.
[8]SAVARESE C，LANGENDOEN K，RABAEY J.Robust positioning algorithms for distributed Ad hoc wireless sensor networks[C]//Proc of USENIX Technical Annual Conference.Monterey，CA:USENIX Press，2002:317-328.
[9]SAVVIDES A，PARK H，SRIVASTAVA M.The bits and flops of the nhop multilateration primitive for node localization problems[C]//Proc of the 1st ACM International Workshop on Wireless Sensor Networks and Application.Atlanta， Georgia:ACM Press， 2002:112121.
[10]LANGENDOEN K，REIJERS N.Distributed localization in wireless sensor networks: a quantitative comparison[J].Computer Networks，2003，43(4):499-518.
[11]角仕云，劉麗婭.實用科學與工程計算方法[M].北京:科學出版社，2000.
[12]WHITEHOUSE K，CULLER D.Calibration as parameter estimation in sensor networks[C]//Proc of the 1st ACM International Workshop on Wireless Sensor Networks and Application.Atlanta，GA:ACM Press，2002:59-67.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”
