基于殘差修正法的無線傳感器網(wǎng)絡(luò)定位技術(shù)*

吳曉平，談士力，胡軍國

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

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

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

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

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

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

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

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

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

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

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

2 殘差修正法定位

2.1 數(shù)學(xué)模型

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

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

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

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

未知節(jié)點(diǎn)的坐標(biāo)增量矩陣H=(h，k)，有:

則殘差矩陣:

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

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

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

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

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

3 仿真分析

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

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

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

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

3.2 測距誤差的估計(jì)值

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

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

圖2 測距誤差估計(jì)值相似度

3.3 殘差修正法的定位

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

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

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

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

4 結(jié)論

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

[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].北京:清華大學(xué)出版社，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ù)學(xué)報(bào)，2007，20(11):2526－2530.

[7]趙昭，陳小惠.無線傳感器網(wǎng)絡(luò)中基于RSSI的改進(jìn)定位算法[J].傳感技術(shù)學(xué)報(bào)，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]徐向華，高學(xué)勇，萬健.無線傳感器網(wǎng)絡(luò)中故障容忍的事件定位算法[J].傳感技術(shù)學(xué)報(bào)，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.