吳曉平，談士力，胡軍國

(1.浙江農(nóng)林大學低碳與物聯(lián)網(wǎng)技術(shù)聯(lián)合實驗室，浙江 臨安311300;2.上海大學機器人研究所，上海200444)

對于無線傳感器網(wǎng)絡(luò)的大部分應用場合，采用無線傳感器網(wǎng)絡(luò)進行信息收集和處理，這些數(shù)據(jù)必須和位置信息相捆綁才有意義，甚至有時需要傳感器發(fā)回單純的位置信息[1－2]。從應用角度來講，傳感節(jié)點的定位是傳感網(wǎng)絡(luò)中最為重要和傳統(tǒng)的問題，研究具有低成本、高精度的傳感器網(wǎng)絡(luò)定位系統(tǒng)是該領(lǐng)域的主要問題之一[3]。

無線傳感器網(wǎng)絡(luò)節(jié)點定位算法可分為基于測距和非測距方法兩大類，非測距的節(jié)點定位技術(shù)定位不需要額外的硬件設(shè)備，成本低，在定位精度要求不高的場合下使用有較大優(yōu)勢。對定位精度要求較高的場合建議使用測距定位技術(shù)。目前定位技術(shù)中使用最廣泛的定位系統(tǒng)當屬全球定位系統(tǒng)(Global Positioning System，GPS)，GPS系統(tǒng)利用精確的同步衛(wèi)星時鐘提供授時和測距以對用戶節(jié)點進行定位，具有定位精度高、實時性好、抗干擾能力強等優(yōu)點，但是GPS定位僅僅適應于無遮擋的室外環(huán)境，其用戶設(shè)備通常能耗高、體積大、成本高[4]。這使得它不適用于大規(guī)模環(huán)境下的無線傳感器網(wǎng)絡(luò)定位。這種方法的局限性激發(fā)了一種新的傳感器網(wǎng)絡(luò)節(jié)點定位方法，即利用已知位置的信標節(jié)點去推算其余未知的節(jié)點位置坐標，這種方法需要未知節(jié)點與信標節(jié)點間的一些信息，比如距離或角度。在無線傳感器網(wǎng)絡(luò)領(lǐng)域，信號接受強度指示(RSSI)距離測量被認為是一種具有較高性價比的測量方法。RSSI測距無需額外硬件，實現(xiàn)簡單，具備低功耗、低成本等特點，應用十分廣泛[5－7]。如果在 RSSI實際測量中，節(jié)點剛好處于一個坑中，天線出錯，節(jié)點供電不足，嚴重的障礙物遮擋，會導致距離測量出現(xiàn)潛在的大量非高斯誤差的數(shù)據(jù)。也就是說，某些距離測量結(jié)果嚴重失真(壞測距)，有些測量結(jié)果誤差較少(好測距)。壞測距數(shù)據(jù)的出現(xiàn)嚴重地降低了傳感器節(jié)點定位的準確性。Lirong Jian等基于冗余的測距節(jié)點提出了以剛性理論識別和判斷出壞測距節(jié)點，以提高定位精度[8]。徐向華等針對傳感網(wǎng)測量中出現(xiàn)的錯誤數(shù)據(jù)，提出了一種故障容忍的事件定位算法，以提高定位精度[9]。H.T.Kung等提出了誤差容忍的定位算法，對判斷出的壞測距數(shù)據(jù)進行容忍定位，減少了壞測距帶來的定位誤差放大[10]。

采用極大似然相似法是目前無線傳感器網(wǎng)絡(luò)定位所采用的主要方法，極大似然相似法的解法有很多，其中非線性最小平方殘差是所有方法中定位精度較高的一種算法。采用非線性最小平方殘差定位時，如果沒有加以區(qū)分好測距與壞測距，沒有對壞測距引起的殘差項加以修正，會導致定位誤差的放大。針對于此，本文提出一種能有效估計壞測距的測距誤差的方法，并由此設(shè)計了一種非線性最小平方殘差下無線傳感器網(wǎng)絡(luò)定位的誤差控制方法，以提高定位精度。

1 非線性最小平方殘差定位原理

在二維平面上，節(jié)點定位至少需要知道與三個信標節(jié)點的距離(不共線)[11]。假設(shè)未知節(jié)點坐標為(x，y)，已知信標節(jié)點 i的坐標為(xi，yi)，以及未知節(jié)點到信標節(jié)點的真實距離，應該滿足:

在實際測量中，距離測量經(jīng)常是不準確的，假設(shè)實際距離測量值為 di，則。

定位可以被歸納為一個非線性最小平方殘差優(yōu)化問題。以距離測量值作為約束，找到一個滿足最小平方殘差時的坐標(x，y)。定位過程中，殘差的定義為距離測量值和定位中所產(chǎn)生的估計值之差。式(2)表示了未知節(jié)點與信標節(jié)點i之間的距離殘差ri。

定位過程是通過最小化平方殘差，即是下列目標函數(shù):

式(4)中，n為與未知節(jié)點間可測距的信標節(jié)點數(shù)量，通過該式求出的坐標(x，y)即為未知節(jié)點的坐標。

式(4)所描述的非線性最小平方問題可以采用高斯牛頓迭代法求解。但采用高斯牛頓迭代法采用近似的線性模型，可能會陷入局部最優(yōu)。為全局最優(yōu)，建議采用Levenberg-Marquardt(LM)算法迭代求解。由于采用了二階導數(shù)信息，LM算法比傳統(tǒng)的高斯牛頓法收斂速度更快[12]。

2 殘差修正法定位

2.1 數(shù)學模型

實現(xiàn)二維平面上的未知節(jié)點定位，僅需要三個不共線的信標節(jié)點。在實際的大規(guī)模定位系統(tǒng)中，信標節(jié)點的數(shù)目往往超過這個數(shù)目，也就是說，信標節(jié)點的數(shù)目是有冗余的。測距誤差的大小對于定位誤差的控制起到了關(guān)鍵的作用，理想的定位結(jié)果是盡量多利用測距誤差較小的好測距數(shù)據(jù)，抑制測距誤差較大的壞測距數(shù)據(jù)對于殘差的放大。為追求較高的定位精度，有必要對測距的誤差進行正確區(qū)分，區(qū)分是好測距還是壞測距，對估計出的壞測距數(shù)據(jù)進行修正。為此，對式(4)進行改進:

式(5)中，Δdi是測距誤差的估計值，其理想值是測量距離di的真實誤差值。該式中利用測距誤差的估計值修正了原有的殘差。當然Δdi的估計值與真實值越靠近，定位誤差就越小。如果能有效地估計出測距誤差值，然后再用式(5)修正，定位效果會顯著提高。殘差是由測距誤差引起的，在高斯分布的測距誤差作用下，各個節(jié)點的殘差分布具有一定的隨機性，各個信標節(jié)點的測距誤差難以估計。但對于非高斯測距數(shù)據(jù)，具有較大誤差的壞測距誤差值在殘差項中了占了絕對優(yōu)勢，測距誤差較小的好測距誤差在殘差中的作用較小。忽略測距誤差較小的好測距數(shù)據(jù)對于殘差的影響，突出測距誤差較大的壞測距數(shù)據(jù)對殘差的影響，可以將壞測距數(shù)據(jù)的測距誤差大致估計出來。方法就是通過分析殘差與誤差間的分布關(guān)系，對引起殘差的測距誤差分解，找出壞測距數(shù)據(jù)，大致估計出壞測距的測距誤差，然后再通過式(5)修正定位結(jié)果，下面就非高斯分布下的測距誤差進行分解。

設(shè)未知節(jié)點坐標的真實坐標為(x，y)，由非線性最小平方殘差法，通過式(4)，定位出的未知節(jié)點坐標為(x0，y0)，則未知節(jié)點到信標節(jié)點i的真實距離應為，對此采用泰勒級數(shù)展開，忽略高次項，有:

因此，梯度矩陣J可以表示為:

未知節(jié)點的坐標增量矩陣H=(h，k)，有:

則殘差矩陣:

式(9)中，A=J(JTJ)－1J－I殘差矩陣可由式(4)計算，梯度矩陣J由式(6)求出。由于矩陣A非滿秩，誤差矩陣無法求解。式(9)表示了測距誤差對于殘差的分配關(guān)系。當此系統(tǒng)中，壞測距信標節(jié)點數(shù)目小于好測距信標節(jié)點數(shù)，壞測距信標節(jié)點分配給好測距信標節(jié)點的殘差較小，所以殘差矩陣中具有較大殘差的往往有較大的測距誤差，可將矩陣A按殘差值大小進行好測距與壞測距分解:

A11表示了好測距的測距誤差對好測距殘差的分配關(guān)系;A12表示了好測距的測距誤差對壞測距殘差的分配關(guān)系;A21表示了壞測距的測距誤差對好測距殘差的分配關(guān)系;A22表示了壞測距的測距誤差對壞測距殘差的分配關(guān)系。從內(nèi)在含義上看，矩陣A表示了殘差對誤差的分配關(guān)系。具有好測距的測距誤差較小，壞測距節(jié)點的測距誤差較大。忽略好測距對于壞測距節(jié)點的殘差分配，可以將壞測距節(jié)點的測距誤差大致分離出來。同樣地，對也進行分解，有

因此，壞測距的測距誤差可由式(13)近似估計:

2.2 算法的實現(xiàn)流程

①以非線性最小平方殘差原理，根據(jù)式(4)采用LM迭代算法計算出初次定位結(jié)果和殘差矩陣。②以初次定位的未知節(jié)點坐標代入式(6)計算梯度矩陣J，進而計算出誤差與殘差間的關(guān)系矩陣A。③根據(jù)殘差值大小對殘差矩陣判斷是好測距還是壞測距，并以此為依據(jù)對A按式(10)進行分解，同時對和也進行分解，按式(13)計算出壞測距誤差的近似估計值。④假設(shè)好測距誤差為零，采用③計算出的測距誤差作為壞測距誤差估計值，并代入式(5)，修正壞測距項的殘差值，好測距項的殘差不需要修正，計算出的即是經(jīng)過一次修正后的定位結(jié)果。⑤若有④計算出的一次修正后的殘差分布大小均勻，可認為修正已基本完成;若殘差項大小變化顯著，可重新按步驟②進行再次修正。

3 仿真分析

用MATLAB進行算法仿真，無線傳感器網(wǎng)絡(luò)在100 m×100 m區(qū)域內(nèi)。在該區(qū)域內(nèi)上隨機部署了12個信標節(jié)點，將未知節(jié)點的坐標預先設(shè)置在(50，50)點。每個仿真實驗運行200次，所有仿真結(jié)果取200次的平均值。仿真實驗首先測試了殘差與測距誤差間的關(guān)系。

3.1 殘差與測距誤差關(guān)系

壞測距與好測距的判斷依據(jù)主要是殘差值大小。當壞測距誤差顯著大于好測距誤差時，壞測距項的殘差值也顯著大于好測距項的殘差值。隨著壞測距數(shù)量的增加，好測距的殘差受到壞測距的影響，也隨之增加，兩者之間的區(qū)分度不夠明顯。在12個信標節(jié)點中隨機選擇了2或4個節(jié)點作為壞測距節(jié)點，其余信標節(jié)點的測距誤差服從高斯分布N(0，12)，改變2或4個壞測距節(jié)點的測距誤差，圖1繪出了隨著壞測距節(jié)點測距誤差增加時，好測距與壞測距項殘差值的變化關(guān)系。由圖1可見，壞測距項的殘差明顯大于好測距項的殘差，同時，隨著壞測距數(shù)量的增加，好測距項與壞測距項的殘差差異會有所減少，采用殘差值大小來區(qū)分是好測距與壞測距也會越不可靠。

圖1 平均絕度值殘差與測距誤差關(guān)系

3.2 測距誤差的估計值

采用式(15)評價測距誤差估計值的準確性，定義si為測距誤差估計值的相似度。

式(15)中，Δdi為測距誤差的估計值為真實的測距誤差。在12個信標節(jié)點中隨機選擇了4個節(jié)點作為壞測距節(jié)點，其余信標節(jié)點的測距誤差服從高斯分布N(0，12)，改變4個壞測距節(jié)點的測距誤差，采用算法分解出的測距誤差估計值的相似度在圖2中繪出。從圖2可以看出，在測距誤差較小時，由于節(jié)點間的殘差也服從高斯分布，壞測距的測距誤差難以從節(jié)點中分離開。但是隨著壞測距的測距誤差增大，壞測距的誤差在殘差中占主要成分，可以很容易將壞測距節(jié)點的測距誤差分解并計算出來。

圖2 測距誤差估計值相似度

3.3 殘差修正法的定位

實驗的初始設(shè)置同上，也在12個信標節(jié)點中隨機選擇了4個節(jié)點作為壞測距節(jié)點，其余信標節(jié)點的測距誤差服從高斯分布N(0，12)，改變4個壞測距節(jié)點的測距誤差，圖3說明了兩種不同定位方法的定位誤差結(jié)果。從圖3中可看出，未經(jīng)過修正的非線性最小平方殘差定位法，定位誤差隨著測距誤差的增加也劇烈加大，但經(jīng)過一次殘差修正后，定位誤差基本保持穩(wěn)定，定位效果大大改善。

圖3 兩種不同定位方法下的定位誤差

隨著壞測距數(shù)目的增加，由于好測距信標節(jié)點的殘差項受到壞測距的分配影響，壞測距信標節(jié)點的測距誤差分配給好測距節(jié)點，所以壞測距節(jié)點的誤差估計越來越不準確。好測距信標節(jié)點的測距誤差服從高斯分布N(0，12)，壞測距的測距誤差設(shè)置在10 m，改變壞測距信標節(jié)點的數(shù)目，圖4繪出了隨著壞測距節(jié)點數(shù)量的增加，兩種不同的定位方法下的定位誤差。從圖4可以看出，隨著壞測距節(jié)點數(shù)目的增加，定位誤差稍有加大，經(jīng)過修正后的定位結(jié)果明顯優(yōu)于原有的定位值。

圖4 壞測距數(shù)目對定位誤差的影響

4 結(jié)論

本文提出了在非線性最小平方殘差法定位時，采用誤差與殘差的關(guān)系矩陣分解出壞測距項的測距誤差值，并以此修正相應項的殘差，這種方法對于提高非高斯測距誤差分布下的定位效果，具有顯著作用。但該算法也有不足的一面，當壞測距信標節(jié)點數(shù)量較多時，由于好測距節(jié)點的殘差項受到壞測距節(jié)點殘差項的影響，好測距項的殘差值與壞測距節(jié)點的殘差沒有顯著區(qū)別，所以難以區(qū)分是好測距還是壞測距，壞測距的測距誤差也就難以估計。

[1]Yunhao Liu，Zheng Yang，Xiaoping Wang.Location，Localization，and Localizability[J].JournalofComputer Science and Technology，2010，25(2):274－297.

[2]Dragos Niculescu，Badri Nath.DV Based Positioning in Ad Hoc Networks[J].Journal of Telecommunication Systems，2003，22(4):267－280.

[3]孫立民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學出版社，2005.

[4]Capkun S，Hamdi M，Hubaux J P.GPS-Free Positioning in Mobile Ad-Hoc Networks[J].Cluster Computing，2002，5(2):157－167.

[5]Ziguo Zhong，Tian He.Achieving Range-Free Localization beyond Connectivity[C]//Proceedings of the 7th International Conference on Embedded Networked Sensor Systems，2009:281－294.

[6]方震，趙湛，郭鵬.基于 RSSI測距分析[J].傳感技術(shù)學報，2007，20(11):2526－2530.

[7]趙昭，陳小惠.無線傳感器網(wǎng)絡(luò)中基于RSSI的改進定位算法[J].傳感技術(shù)學報，2009，22(3):391－394.

[8]Lirong Jian，Zheng Yang，Yunhao Liu.Beyond Triangle Inequality:Sifting Noisy and Outlier Distance Measurements for Localization[C]//Proceedings of the 28th Conference on Computer Communications，2009:1972－1980.

[9]徐向華，高學勇，萬健.無線傳感器網(wǎng)絡(luò)中故障容忍的事件定位算法[J].傳感技術(shù)學報，2009，24(3):429－435.

[10]Kung H T，Chit-Kwan Lin，Tsung-Han Lin，et al.Localization with Snap Inducing Shaped Residuals(SISR):Coping with Errors in Measurement[C]//Proceedings of the 15th Annual International Conference on Mobile Computing and Networking，2009:333－344.

[11]Juan Liu，Ying Zhang，F(xiàn)eng Zhao.Robust Distributed Node Localization with Error Management[C]//Proceedings of the 4th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing，2006:250－261.

[12]Madsen K，Nielsen H B，Tingleff O.Optimization with Constraints[M].2nd Edition.IMM，DTU，2004.