一種新的三維無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法

曾傳璜，蔣紅剛

（江西理工大學(xué)信息工程學(xué)院，江西贛州 341000）

0 引言

無線傳感器網(wǎng)絡(luò)（wireless sensor networks，WSNs）涉及現(xiàn)代微機(jī)電系統(tǒng)（micro-electro-mechanical system，MEMS）、微電子、片上系統(tǒng)（system-on-chip，SoC）、納米材料、傳感器、無線通信、計(jì)算機(jī)網(wǎng)絡(luò)、分布式信息處理等技術(shù)，在國(guó)防軍事、工農(nóng)業(yè)控制、城市管理、衛(wèi)生醫(yī)療、環(huán)境監(jiān)測(cè)、搶險(xiǎn)救災(zāi)、反恐防恐、危險(xiǎn)區(qū)域遠(yuǎn)程控制等領(lǐng)域有著潛在的應(yīng)用前景。美國(guó)《商業(yè)周刊》將WSNs列為21世紀(jì)最有影響力的21項(xiàng)技術(shù)之一，《MIT技術(shù)評(píng)論》將無線傳感器網(wǎng)絡(luò)列于10種改變未來世界新興技術(shù)之首［1］。

無線傳感器網(wǎng)絡(luò)的定位是指自組織的網(wǎng)絡(luò)通過特定方法提供節(jié)點(diǎn)位置信息，這種自組織網(wǎng)絡(luò)定位分為節(jié)點(diǎn)自身定位和目標(biāo)定位。節(jié)點(diǎn)自身定位是網(wǎng)絡(luò)自身屬性的確定過程，可以通過人工標(biāo)定或者各種節(jié)點(diǎn)自定位算法完成。目標(biāo)定位是位置已知的網(wǎng)絡(luò)節(jié)點(diǎn)為參考節(jié)點(diǎn)，確定事件或者目標(biāo)在網(wǎng)絡(luò)中所處的位置［2］。

根據(jù)定位過程中是否實(shí)際測(cè)量節(jié)點(diǎn)間的距離或角度，把傳感器網(wǎng)絡(luò)中的定位分類為基于距離的定位和距離無關(guān)的定位?；诰嚯x的定位機(jī)制就是通過測(cè)量相鄰節(jié)點(diǎn)間的實(shí)際距離或方位來確定未知節(jié)點(diǎn)的位置，通常采用測(cè)距、定位和修正等步驟實(shí)現(xiàn)。根據(jù)測(cè)量節(jié)點(diǎn)間距離或方位時(shí)所采用的方法，基于距離的定位分為基于ToA［3］的定位、基于TDoA［4］的定位、基于 AoA［5］的定位、基于 RSSI［6］的定位等。由于要實(shí)際測(cè)量節(jié)點(diǎn)間的距離或角度，基于距離的定位機(jī)制通常定位精度相對(duì)較高，所以，對(duì)節(jié)點(diǎn)的硬件也提出了很高的要求。距離無關(guān)的定位機(jī)制無須實(shí)際測(cè)量節(jié)點(diǎn)間的絕對(duì)距離或方位就能夠確定未知節(jié)點(diǎn)的位置，目前提出的定位機(jī)制主要有質(zhì)心算法、DV-Hop算法［7］、Amorphous算法、APIT算法等［8］。本文在結(jié)合三邊定位和三角定位的基礎(chǔ)上，提出一種新的基于測(cè)距的三角幾何定位方法。

1 定位算法的提出與定位原理

在節(jié)點(diǎn)定位算法中，與距離相關(guān)的定位算法有三邊測(cè)量法，三角測(cè)量法，極大似然估計(jì)法等。三邊測(cè)量法需要知道與3個(gè)節(jié)點(diǎn)相關(guān)的距離信息;三角測(cè)量法需要知道與未知點(diǎn)相關(guān)的3個(gè)角度信息。本文提出的方法則是要知道未知節(jié)點(diǎn)與某一信標(biāo)節(jié)點(diǎn)相關(guān)的一個(gè)距離，2個(gè)角度的相關(guān)信息。

如圖1，p點(diǎn)為位置未知節(jié)點(diǎn)，o，o1和o2是選取的信標(biāo)節(jié)點(diǎn)，現(xiàn)以oo1為x軸的正半軸，o1oo2為xoy平面建立三維坐標(biāo)系。p1為p點(diǎn)在o1oo2三點(diǎn)所組成的平面上的投影。

圖1 定位算法示意圖Fig 1 Schematic diagram of localization algorithm

已知3個(gè)信標(biāo)節(jié)點(diǎn)空間坐標(biāo)，通過距離運(yùn)算公式

可以得到三點(diǎn)間兩兩之間的距離:loo1，loo2，lo1o2。

利用余弦定理

可以得到角∠o1oo2的大小。

通過3個(gè)信標(biāo)節(jié)點(diǎn)可以測(cè)量得到:lop，∠poo1，∠poo2。

根據(jù)余弦定理有

式（3）和式（4）相比得

根據(jù)三角函數(shù)運(yùn)算有

由式（3）平方與式（6）及三角平方公式得

由式（5）與式（7）及平方公式得

根據(jù)圖1所示和三角運(yùn)算可知p點(diǎn)坐標(biāo)（px，py，pz）

根據(jù)式（3）和式（9）得

根據(jù)式（3），式（5）和式（10）得

根據(jù)式（8）和式（11）得

通過以上的運(yùn)算即可得到p點(diǎn)坐標(biāo)（px，py，pz）。當(dāng)然這是以o點(diǎn)為坐標(biāo)原點(diǎn)，以oo1為x的正半軸，o1oo2為xoy平面建立三維坐標(biāo)系得到的（px，py，pz）。在實(shí)際中這三點(diǎn)坐標(biāo)并不是這樣，但三點(diǎn)確定一個(gè)平面，可以將信標(biāo)節(jié)點(diǎn)坐標(biāo)進(jìn)行平移變換，使其中一點(diǎn)平移變換到坐標(biāo)原點(diǎn)。變換以后，將坐標(biāo)原點(diǎn)的點(diǎn)與另外一點(diǎn)作為x軸，而平移變換后的三點(diǎn)便成為xoy平面，這樣便可以使用上述方法計(jì)算出未知節(jié)點(diǎn)的相對(duì)坐標(biāo)，再進(jìn)行坐標(biāo)變換就可以得到原坐標(biāo)系中未知節(jié)點(diǎn)的實(shí)際坐標(biāo)。

方法改進(jìn)的討論:

通過以上計(jì)算可知在測(cè)量得到與o點(diǎn)相關(guān)的數(shù)據(jù)信息，通過三角幾何運(yùn)算得到p點(diǎn)的相對(duì)坐標(biāo)，再進(jìn)行坐標(biāo)變換即可得到p點(diǎn)在實(shí)際中的坐標(biāo)。在計(jì)算未知節(jié)點(diǎn)的過程中不需要o1點(diǎn)和o2點(diǎn)的距離與角度信息，但是在坐標(biāo)變換中又需要其相關(guān)信息。為了獲取更多與未知節(jié)點(diǎn)相關(guān)的信息，提高定位的精確性，可以合理利用這兩點(diǎn)與未知節(jié)點(diǎn)的相關(guān)信息，在此對(duì)以上方法進(jìn)行改進(jìn)。方法改進(jìn)中，將o1點(diǎn)和未知節(jié)點(diǎn)相關(guān)的一邊與兩角測(cè)量出來，將o1作為坐標(biāo)原點(diǎn)，o1o為x軸和上面的方法一樣，對(duì)未知節(jié)點(diǎn)的相關(guān)數(shù)據(jù)信息進(jìn)行計(jì)算，得到另一組p點(diǎn)的相對(duì)坐標(biāo)。然后再運(yùn)用坐標(biāo)變換，可得到第二組p點(diǎn)實(shí)際坐標(biāo)。同理，通過o2點(diǎn)與未知節(jié)點(diǎn)相關(guān)數(shù)據(jù)可以的到第三組p點(diǎn)實(shí)際坐標(biāo)。當(dāng)然o點(diǎn)，o1點(diǎn)，o2點(diǎn)本生是在同一坐標(biāo)系內(nèi)的，得到的未知節(jié)點(diǎn)的實(shí)際坐標(biāo)應(yīng)該是一樣的。但由于測(cè)量誤差的存在，這三組數(shù)據(jù)不一定相同，這時(shí)可以再運(yùn)用質(zhì)心法求解p點(diǎn)坐標(biāo)。

改進(jìn)算法的優(yōu)點(diǎn)是:

1）測(cè)量數(shù)據(jù)之間是相互獨(dú)立的，數(shù)據(jù)量很大時(shí)測(cè)量誤差就會(huì)趨近于零。

2）通過3個(gè)信標(biāo)節(jié)點(diǎn)就可以獲取三組未知節(jié)點(diǎn)位置坐標(biāo)，本方法在信標(biāo)節(jié)點(diǎn)較少的情況下，仍然能夠得到較多的關(guān)于未知節(jié)點(diǎn)坐標(biāo)的信息（n個(gè)信標(biāo)節(jié)點(diǎn)可以產(chǎn)生C3n×3組數(shù)據(jù)），可以應(yīng)用于信標(biāo)節(jié)點(diǎn)密度較小時(shí)對(duì)未知節(jié)點(diǎn)的定位。

2 算法性能評(píng)估

2．1 衡量標(biāo)準(zhǔn)

本文只針對(duì)定位算法本生所產(chǎn)生的節(jié)點(diǎn)定位精度進(jìn)行

在誤差計(jì)算時(shí)將3個(gè)信標(biāo)節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)的定位誤差分別計(jì)算出來。同時(shí)，利用質(zhì)心法將3個(gè)信標(biāo)節(jié)點(diǎn)的計(jì)算坐標(biāo)進(jìn)行處理。計(jì)算出定位坐標(biāo)與實(shí)際坐標(biāo)之間的誤差，將平均定位誤差作為本方法的最終定位誤差。

其仿真過程如下:

1）在大小100 m×100 m×100 m的空間坐標(biāo)中選取3個(gè)信標(biāo)節(jié)點(diǎn)，假設(shè)分別為o點(diǎn)、o1點(diǎn)、o2點(diǎn)。

2）在上面的基礎(chǔ)上再隨機(jī)產(chǎn)生一個(gè)未知節(jié)點(diǎn)p點(diǎn)，假設(shè)為（x3，y3，z3，）。

3）通過在Matlab中編寫程序計(jì)算出相應(yīng)的角度與長(zhǎng)度，并將其分為三組:

4）將以上計(jì)算得到的長(zhǎng)度，角度分別加上隨機(jī)誤差，作為測(cè)量數(shù)據(jù)。

5）根據(jù)新算法，用三組帶有隨機(jī)誤差的長(zhǎng)度與角度計(jì)算未知節(jié)點(diǎn)的坐標(biāo)，假設(shè)計(jì)算結(jié)果分別為（x，y，z），（x1，y1，z1），（x2，y2，z2），用質(zhì)心法將上面三組數(shù)據(jù)處理得到（xi，yi，zi）。

6）用上面所產(chǎn)生的四組坐標(biāo)數(shù)據(jù)與未知節(jié)點(diǎn)p（x3，y3，z3，），計(jì)算定位誤差。

7）重復(fù)以上運(yùn)算1 000次，顯示每次定位誤差，計(jì)算1000次定位的平均定位誤差。

2．2 實(shí)驗(yàn)仿真

實(shí)驗(yàn)仿真中設(shè)定角度測(cè)量誤差為5°，長(zhǎng)度測(cè)量誤差為5%R（R通信半徑）?，F(xiàn)取3 個(gè)信標(biāo)節(jié)點(diǎn)（0，0，0 m）（53，0，0 m）（32，18，0 m）對(duì)100 m ×100 m ×100 m 內(nèi) 1000 個(gè)任意未知點(diǎn)進(jìn)行定位。計(jì)算出3個(gè)信標(biāo)節(jié)點(diǎn)對(duì)1 000個(gè)未知節(jié)點(diǎn)相應(yīng)的定位坐標(biāo)，將3個(gè)信標(biāo)節(jié)點(diǎn)定位坐標(biāo)再利用質(zhì)心法對(duì)其進(jìn)行相應(yīng)處理，將處理后的坐標(biāo)定為最終的未知節(jié)點(diǎn)的坐標(biāo)。仿真中分別計(jì)算出3個(gè)信標(biāo)節(jié)點(diǎn)的相應(yīng)定位誤差和利用質(zhì)心法處理上述3個(gè)信標(biāo)節(jié)點(diǎn)定位坐標(biāo)的定位誤差，同時(shí)計(jì)算出這1000個(gè)未知節(jié)點(diǎn)定位的平均定位誤差。用Matlab仿真，定位誤差示意圖如圖2～圖5所示。

經(jīng)過質(zhì)心算法改進(jìn)后的平均定位誤差為4．98%（第一個(gè)信標(biāo)節(jié)點(diǎn)為坐標(biāo)原點(diǎn)時(shí)的平均定位誤差為8．62%，第二個(gè)信標(biāo)節(jié)點(diǎn)為坐標(biāo)原點(diǎn)時(shí)的平均定位誤差為8．41%，第三個(gè)信標(biāo)節(jié)點(diǎn)為坐標(biāo)原點(diǎn)時(shí)的平均定位誤差為10．11%）。可見該算法改進(jìn)后的定位誤差相比于其他的定位算法的定位誤差要小得多。分析，利用Matlab對(duì)三角幾何算法進(jìn)行仿真。定位誤差pe定義如下

圖2 第一個(gè)信標(biāo)節(jié)點(diǎn)為坐標(biāo)原點(diǎn)時(shí)的定位誤差示意圖Fig 2 Localization error diagram while the 1st beacon node is the origin of coordinates

圖3 第二個(gè)信標(biāo)節(jié)點(diǎn)為坐標(biāo)原點(diǎn)時(shí)的定位誤差示意圖Fig 3 Localization error diagram while the 2nd beacon node is the origin of coordinates

圖4 第三個(gè)信標(biāo)節(jié)點(diǎn)為坐標(biāo)原點(diǎn)時(shí)的定位誤差示意圖Fig 4 Localization error diagram while the 3rd beacon node is the origin of coordinates

圖5 運(yùn)用質(zhì)心算法改進(jìn)定位誤差示意圖Fig 5 Localization error diagram with the improved centroid algorithm

3 結(jié)束語

本文提出了一種新的基于測(cè)距的三維無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法，通過測(cè)量一邊、兩角，運(yùn)用三角幾何知識(shí)計(jì)算出相對(duì)坐標(biāo)，通過坐標(biāo)轉(zhuǎn)換計(jì)算出實(shí)際坐標(biāo)，實(shí)現(xiàn)定位。該算法改進(jìn)后相對(duì)其他的定位算法來說，定位精度相對(duì)較高。在信標(biāo)節(jié)點(diǎn)相對(duì)較少的情況下仍然能夠得到較多數(shù)據(jù)，適合于信標(biāo)節(jié)點(diǎn)密度相對(duì)較小的情況，即可以應(yīng)用到計(jì)算精度要求比較高，計(jì)算節(jié)點(diǎn)密度較小的三維無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中去。

［1］ 徐勇軍．無線傳感器網(wǎng)絡(luò)實(shí)驗(yàn)教程［M］．北京:北京理工大學(xué)出版社，2007．

［2］ 李曉維．無線傳感器網(wǎng)絡(luò)技術(shù)［M］．北京:北京理工大學(xué)出版社，2007:191．

［3］ Chuang Woo-cheol，Ha Dong-sam．An accurate ultrawideband（UWB）ranging for precision asset location［C］∥Proceedings of the IEEE Conference on Ultra Wideband Systems and Technologies Reston，Piscataway，NJ，USA，2003:389 －393．

［4］ Savvides A，Park H，Srivastava M．The bits and flops of the n-hop multilateration primitive for node localization problems［C］∥The first ACM International Workshop on Wireless Sensor Networks and Application，Atlanta，GA，USA，2002:112 －121．

［5］ Niculescu D，Nath B．Ad Hoc positioning system（APS）using AoA［C］∥Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies（INFOCOM），Piscataway，USA，2003:1734 －1743．

［6］ Niculescu D，Nath B．DV-based positioning in Ad Hoc networks［J］．Journal of Telecommunication Systems，2003，22（1/4）:267－280．

［7］ Bulusu N，Heidemann J，Estrin D，et al．Self-configuring localization system:Design and experimental evaluation［J］．ACM Transaction on Embedded Computing System，2004，3（1）:24 －60．

［8］ 孫利民，李建樹，陳 渝，等．無線傳感器網(wǎng)絡(luò)［M］．北京:清華大學(xué)出版社，2005:156－157．