楊凌云， 馮友宏

（安徽師范大學(xué)物理與電子信息學(xué)院，安徽蕪湖 241000）

垂直交點(diǎn)APIT定位改進(jìn)算法

楊凌云， 馮友宏

（安徽師范大學(xué)物理與電子信息學(xué)院，安徽蕪湖 241000）

針對(duì)APIT算法存在的問(wèn)題，提出了一種新的判斷未知節(jié)點(diǎn)位置的方法。首先選擇3個(gè)任意組合的錨節(jié)點(diǎn)，通過(guò)任意一個(gè)錨節(jié)點(diǎn)對(duì)另外兩個(gè)錨節(jié)點(diǎn)所在直線作垂線得到垂直交點(diǎn)，通過(guò)比較這個(gè)錨節(jié)點(diǎn)到交點(diǎn)的距離和它與未知節(jié)點(diǎn)的距離的關(guān)系，初步判斷未知節(jié)點(diǎn)位置，同時(shí)，通過(guò)加權(quán)質(zhì)心定位算法得到未知節(jié)點(diǎn)的精確估計(jì)值。Matlab仿真結(jié)果表明，改進(jìn)后的算法相比較經(jīng)典APIT算法在定位精度上有了很大提高。

APIT；垂直；交點(diǎn)；加權(quán)；質(zhì)心算法

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)是一種基于低成本、低損耗的自組織無(wú)線定位網(wǎng)絡(luò)，能夠?qū)崿F(xiàn)惡劣環(huán)境下的信息采集和跟蹤工作［1］。在無(wú)線傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)內(nèi)傳感器節(jié)點(diǎn)的自身定位是一項(xiàng)非常關(guān)鍵的技術(shù)，定位精確的高低直接影響著整個(gè)網(wǎng)絡(luò)在以后工作中的定位跟蹤能力。節(jié)點(diǎn)自身定位方法一

般分為基于距離的定位算法和距離無(wú)關(guān)的定位算法兩大類［2］，后者因?yàn)椴恍枰雷约号c錨節(jié)點(diǎn)的角度、距離等信息，而通過(guò)信息連通度等信息估計(jì)出節(jié)點(diǎn)位置信息，這種定位方法因?yàn)樾枰獋鬟f的信息少，能很好地節(jié)約節(jié)點(diǎn)能力，實(shí)現(xiàn)較長(zhǎng)的工作時(shí)間而得到廣泛應(yīng)用和研究，比較常見(jiàn)的與距離無(wú)關(guān)的定位算法有：dv-hop、質(zhì)心定位［3］、APIT定位［4］等。其中質(zhì)心定位算法是一個(gè)粗定位算法［5］，APIT算法在節(jié)點(diǎn)連通度比較大的情況下定位精度較高［6］，后來(lái)就有人把質(zhì)心定位與APIT結(jié)合［7］，提出了基于APIT的質(zhì)心定位算法。文中針對(duì)這種算法的APIT算法在定位過(guò)程中的一些問(wèn)題，在基于APIT的質(zhì)心定位算法的基礎(chǔ)上提出了改進(jìn)措施，提高了APIT的定位精度。

1 APIT算法

1.1 PIT測(cè)試

在能夠通信的范圍內(nèi)，找出所有能夠與未知節(jié)點(diǎn)通信的錨節(jié)點(diǎn)，任意選取其中的3個(gè)節(jié)點(diǎn)，判斷未知節(jié)點(diǎn)是否在這3個(gè)節(jié)點(diǎn)組成的三角形內(nèi)部，如果再進(jìn)行下一步定位運(yùn)算，如果不在三角形內(nèi)部，則丟棄這個(gè)三角形。判斷是否在三角形內(nèi)部的方法如果未知節(jié)點(diǎn)朝某個(gè)方向發(fā)生移動(dòng)，是否是同時(shí)遠(yuǎn)離或者同時(shí)接近這3個(gè)錨節(jié)點(diǎn)，如果是，則未知節(jié)點(diǎn)在三角形外面，如果同時(shí)有接近和遠(yuǎn)離的節(jié)點(diǎn)，則在三角形里面［8］。

在實(shí)際應(yīng)用中，節(jié)點(diǎn)的移動(dòng)是非常緩慢的，或者說(shuō)在一定條件下可以近似地認(rèn)為我們的很多無(wú)線傳感器網(wǎng)絡(luò)是一個(gè)靜態(tài)網(wǎng)絡(luò)，節(jié)點(diǎn)是靜止的。針對(duì)靜態(tài)無(wú)線傳感器網(wǎng)絡(luò)，文獻(xiàn)［4］提出可以根據(jù)未知節(jié)點(diǎn)的鄰居節(jié)點(diǎn)是否同時(shí)遠(yuǎn)離和接近三角形節(jié)點(diǎn)來(lái)判斷未知節(jié)點(diǎn)是否在三角形內(nèi)部的近似PIT算法（簡(jiǎn)稱in-out算法）。

靜態(tài)無(wú)線傳感器網(wǎng)絡(luò)中的近似PIT測(cè)試是APIT算法的核心，判斷的正確與否直接關(guān)系著未知節(jié)點(diǎn)定位的精確度。但是在這種算法中，未知節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的分布是一個(gè)隨機(jī)分布，它們之間的距離可大可小，方向可左可右，特別是靠近三角形某一邊時(shí)，對(duì)選取不同的鄰居節(jié)點(diǎn)，得到的結(jié)論可能就會(huì)不同，從而造成較大誤差。為此，文中根據(jù)三角形中垂線的一些特征，可以粗略估計(jì)未知節(jié)點(diǎn)位置信息［9］，提出一種新的未知節(jié)點(diǎn)判斷方法，可以相對(duì)準(zhǔn)確地判斷出未知節(jié)點(diǎn)的位置。

1.2 定位算法

如果找到由3個(gè)以上錨節(jié)點(diǎn)組成的三角形的未知節(jié)點(diǎn)，就可以對(duì)未知節(jié)點(diǎn)進(jìn)行定位，假設(shè)一般情況下未知節(jié)點(diǎn)僅可以接收到已知錨節(jié)點(diǎn)的位置和發(fā)出時(shí)的能量值和接收到的能量，那么根據(jù)通用的能量傳遞公式［10］，能量的傳遞與距離的平方是成反比例的關(guān)系，即

式中：E1——到達(dá)未知節(jié)點(diǎn)的能量；

E0——錨節(jié)點(diǎn)發(fā)送時(shí)刻的能量；

d1——未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離；

k1——常數(shù)，它與信號(hào)波長(zhǎng)、傳輸環(huán)境等信息有關(guān)，特定的條件下為一常數(shù)。

通過(guò)能量比值可以得到相對(duì)精確的距離值。在求錨節(jié)點(diǎn)包圍的未知節(jié)點(diǎn)的位置信息時(shí)，常見(jiàn)到的就是網(wǎng)格掃描算法和質(zhì)心定位算法。在網(wǎng)格掃描算法中，網(wǎng)格的精度直接關(guān)系著定位精度，所以很容易出現(xiàn)位置估計(jì)不足的問(wèn)題［11］。在質(zhì)心定位算法的基礎(chǔ)上加入相應(yīng)權(quán)值，可以得到較為精確的估計(jì)值［12］，文中提出加權(quán)質(zhì)心定位算法，加入與能量有關(guān)的加權(quán)因子，可以得到更為精確的位置估計(jì)值。

2 算法改進(jìn)

這里提出一種新的基于APIT的改進(jìn)算法

NP-APIT算法，首先根據(jù)三角形垂直分割線的特征［13－14］，提出一種新的in-out判別方法，然后對(duì)質(zhì)心定位算法加入與能量有關(guān)的權(quán)值估計(jì)，提出APIT算法的估計(jì)精度。

2.1 in-out算法改進(jìn)

定理1 如果一個(gè)點(diǎn)位于三角形的內(nèi)部，那么該點(diǎn)與任意三角形的上點(diǎn)位于另外兩個(gè)點(diǎn)位于的直線的劃分的平面的一側(cè)，如圖1所示。

圖1 D點(diǎn)在三角形內(nèi)部

圖中，如果D點(diǎn)位于三角形ABC內(nèi)部，BC所在直線把平面劃分兩部分，那么A點(diǎn)和D點(diǎn)一定在直線的同一邊，同樣可以證明，B點(diǎn)與D點(diǎn)的關(guān)系、C點(diǎn)與D點(diǎn)的關(guān)系也成立。

證明 圖1中，D點(diǎn)為未知節(jié)點(diǎn)，A點(diǎn)、B點(diǎn)和C點(diǎn)為已知錨節(jié)點(diǎn)，假設(shè)在D點(diǎn)能接收到3個(gè)錨節(jié)點(diǎn)分別發(fā)送過(guò)來(lái)的各自坐標(biāo)信息和能量信息，那么由式（1）可得，通過(guò)接收到的能量值與錨節(jié)點(diǎn)發(fā)送時(shí)的能量進(jìn)行比值，可以得到兩者之間的距離，即可以得到未知節(jié)點(diǎn)分別到3個(gè)錨節(jié)點(diǎn)距離為：

過(guò)未知節(jié)點(diǎn)D作BC的垂直平分線，與BC的交點(diǎn)為E，根據(jù)數(shù)學(xué)直線計(jì)算公式很容易求出E點(diǎn)坐標(biāo)與錨節(jié)點(diǎn)B和C之間的位置關(guān)系，得到E點(diǎn)坐標(biāo)。如果A點(diǎn)與D點(diǎn)在同一平面內(nèi)，那么D點(diǎn)到A點(diǎn)的距離dA一定小于AE的值，如果dA大于AE的值，則A點(diǎn)和D點(diǎn)在不同的平面上。同樣的方法可以判斷B點(diǎn)、C點(diǎn)與D點(diǎn)的關(guān)系，從而得出D點(diǎn)是在ABC所組成的三角形內(nèi)部，那么它到某一個(gè)錨節(jié)點(diǎn)的距離一定小于它到另外兩個(gè)錨節(jié)點(diǎn)所在直線的垂直交點(diǎn)的距離。

定理2 如果一個(gè)點(diǎn)位于三角形的外部，那么至少有一個(gè)三角形的頂點(diǎn)與未知節(jié)點(diǎn)分別位于另外兩點(diǎn)所在直線劃分的平面。

D點(diǎn)在三角形外部如圖2所示。

圖2 D點(diǎn)在三角形外部

證明 圖中，A點(diǎn)和D點(diǎn)分別位于BC所在直線劃分的兩個(gè)平面上，B點(diǎn)也和D點(diǎn)在AC所在直線劃分的兩個(gè)平面上，而C點(diǎn)與D點(diǎn)在AB劃分的同一平面內(nèi)。我們只需要證明只要有一個(gè)點(diǎn)與D點(diǎn)不同面就可以證明D點(diǎn)在ABC組成的三角形外。

對(duì)于圖2中未知節(jié)點(diǎn)位于三角形外面的情況，如果說(shuō)D點(diǎn)位于離三角形比較近的地方（由D點(diǎn)所作三角形一個(gè)邊的垂直平分線正好位于三角形的兩頂點(diǎn)之間，圖1中E的位置），那么上述方法很容易判斷，但是如果所作垂線的交點(diǎn)在連線的外部，那么根據(jù)接收到的信息就有可能判斷不出來(lái)或者出現(xiàn)判斷錯(cuò)誤的情況。我們的方法是，先假設(shè)未知節(jié)點(diǎn)是在三角形內(nèi)部的，這樣利用直線公式，很容易計(jì)算出F的位置，F(xiàn)點(diǎn)與真正的垂直交點(diǎn)E是三角形的頂點(diǎn)C的對(duì)稱（CF＝CE），如果AF＜AD的值，D點(diǎn)在三角形外，反之在三角形內(nèi)。同樣的方法可以另外兩邊。

具體說(shuō)明如下：

1）圖2給出了三角形中兩個(gè)點(diǎn)與D點(diǎn)不在一個(gè)平面的情況，它具有一定代表性。通過(guò)不斷實(shí)驗(yàn)發(fā)現(xiàn)，在判斷中可能出現(xiàn)3個(gè)錨節(jié)點(diǎn)中的一個(gè)錨節(jié)點(diǎn)、兩個(gè)錨節(jié)點(diǎn)甚至3個(gè)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)不在直線所劃分的同一平面內(nèi)，可以推導(dǎo)得出同樣的結(jié)論。

2）在位置判斷過(guò)程中，如果未知節(jié)點(diǎn)在離三角形外不遠(yuǎn)處的位置，有可能出現(xiàn)三角形的某一個(gè)節(jié)點(diǎn)的誤判，但只會(huì)出現(xiàn)本來(lái)在兩個(gè)節(jié)點(diǎn)在不同平面內(nèi)，結(jié)果誤判的情況，但這不會(huì)影響整個(gè)判斷結(jié)論，另外兩個(gè)節(jié)點(diǎn)肯定會(huì)判斷出來(lái)的，圖2中的情況就是一個(gè)有可能出現(xiàn)一邊誤判，但不會(huì)影響最終結(jié)果的情況。

3）對(duì)于未知節(jié)點(diǎn)可能在三角形某一個(gè)邊所在直線的情況，未知節(jié)點(diǎn)在三角形外部時(shí)，我們?nèi)〉慕稽c(diǎn)其實(shí)是一個(gè)對(duì)折過(guò)去的虛交點(diǎn)，可以很好地區(qū)分未知節(jié)點(diǎn)在兩個(gè)錨節(jié)點(diǎn)中間某個(gè)位置還是外側(cè)。定理2同樣適用。

2.2 加權(quán)質(zhì)心定位

對(duì)于已知未知節(jié)點(diǎn)位于由已知錨節(jié)點(diǎn)組成的三角形內(nèi)部的節(jié)點(diǎn)，采用質(zhì)心加權(quán)的方法來(lái)估計(jì)未知節(jié)點(diǎn)的未知，同時(shí)，把未知節(jié)點(diǎn)一定在3個(gè)垂直交點(diǎn)所組成的三角形內(nèi)作為約束條件，來(lái)進(jìn)一步精確未知節(jié)點(diǎn)。

加權(quán)垂直平分節(jié)點(diǎn)組成的約束區(qū)間如圖3所示。

圖3 加權(quán)垂直平分節(jié)點(diǎn)組成的約束區(qū)間

在圖1中，分析了錨節(jié)點(diǎn)三角形內(nèi)部未知節(jié)點(diǎn)與其中一個(gè)邊的位置關(guān)系，找到了其中的過(guò)未知節(jié)點(diǎn)的垂直平分交點(diǎn)，同樣的方法可以找到另外兩邊的垂直平分交點(diǎn)，把這三點(diǎn)連接起來(lái)構(gòu)成新的三角形，而未知節(jié)點(diǎn)D一定在這個(gè)新三角形內(nèi)部陰影部分（見(jiàn)圖3），這就縮小了選擇的范圍。在對(duì)錨節(jié)點(diǎn)進(jìn)行加權(quán)質(zhì)心加權(quán)的同時(shí)，滿足約束條件的點(diǎn)才符合我們要求的估計(jì)值。

同時(shí)對(duì)三角形質(zhì)心加權(quán)定位估計(jì)值為：

這里設(shè)三角形的3個(gè)點(diǎn)分別是A點(diǎn)坐標(biāo)（xA，yA）、B點(diǎn)坐標(biāo)（xB，yB）和C點(diǎn)坐標(biāo)（xC，yC），未知節(jié)點(diǎn)到這3個(gè)錨節(jié)點(diǎn)的距離分別為dA，dB，dC。因?yàn)榫嚯x的平方與初始能力和接收能量成正比例關(guān)系，所以權(quán)值實(shí)際上是E0／Ei，E0為初始能量值，Ei為接收到的能量值。實(shí)驗(yàn)證明，對(duì)能量進(jìn)行加權(quán)（即對(duì)距離的平方進(jìn)行加權(quán)）比簡(jiǎn)單的對(duì)距離進(jìn)行加權(quán)可以得到更高的準(zhǔn)確度。

3 算法仿真

采用Matlab對(duì)上面兩種算法進(jìn)行仿真分析，并在40m×40m的環(huán)境中進(jìn)行測(cè)試，對(duì)不同錨節(jié)點(diǎn)、不同的通信半徑下，通過(guò)兩種不同的算法對(duì)未知節(jié)點(diǎn)進(jìn)行位置估計(jì)的誤差進(jìn)行比較，如圖4所示。

圖4 定位誤差隨著通信距離的變化圖

圖4中的通信半徑的變化范圍為10～30m?？梢钥吹?，改進(jìn)的基于垂直交點(diǎn)算法幾乎在每個(gè)不同的通信范圍下，都可以得到更低的而且相對(duì)穩(wěn)定的定位誤差，誤差減少為APIT誤差的20%左右，同時(shí)，因?yàn)闇y(cè)試的區(qū)域范圍是40m的一個(gè)正方形，可以看到在錨節(jié)點(diǎn)通信距離大于20m后變化趨于平穩(wěn)，所以，并不是錨節(jié)點(diǎn)的通信距離越大越好，合適的通信距離既可以節(jié)約成本，也可以得到很好的定位效果。

定位誤差隨著錨節(jié)點(diǎn)個(gè)數(shù)的變化如圖5所示。

圖5 定位誤差隨著錨節(jié)點(diǎn)個(gè)數(shù)的變化圖

圖5中錨節(jié)點(diǎn)的個(gè)數(shù)是從20個(gè)開始仿真的，每次增加5個(gè)錨節(jié)點(diǎn)，通過(guò)仿真可以看到，改進(jìn)后的NP-APIT算法的誤差幾乎下降到APIT算法的40%左右，而且誤差值相對(duì)穩(wěn)定。綜上所述，改進(jìn)的NP-APIT算法的誤差將比APIT算法減少了定位誤差，有效提高了定位精度。

4 結(jié) 語(yǔ)

在靜止無(wú)線傳感器網(wǎng)絡(luò)中，針對(duì)APIT算法中的in-out判斷方法和質(zhì)心定位算法進(jìn)行了改進(jìn)，提出了通過(guò)對(duì)加權(quán)垂直分割節(jié)點(diǎn)到錨節(jié)點(diǎn)距離和未知節(jié)點(diǎn)到錨節(jié)點(diǎn)距離的比較，來(lái)判斷一個(gè)錨節(jié)點(diǎn)和未知節(jié)點(diǎn)是否同在兩個(gè)錨節(jié)點(diǎn)形成的直線所劃分的同一個(gè)平面內(nèi)來(lái)進(jìn)行未知節(jié)點(diǎn)的inout判斷，同時(shí)在位置估計(jì)中，采用了加權(quán)質(zhì)心定位和未知節(jié)點(diǎn)一定在垂直分割點(diǎn)形成的三角形中的約束條件，有效提高了定位精度。

［1］孫利民，李建中，陳渝，等.無(wú)線傳感器網(wǎng)絡(luò)［M］.北京：清華大學(xué)出版社，2005：151-152.

［2］Niculescu D，Nath B.DV based positioning in ad hoc networks［J］.Journal of Tele-communication Systems，2003，22（4）：267-280.

［3］Bulusu N，Heidemann J，Estrin D.GPS-less low cost outdoor localization for very small devices［J］.IEEE Personal Communications Magazine，2000，7（5）：28-34.

［4］He Tian，Huang Chengdu，Blum B M，et al.Range-free localization schemes in large scale sensor networks［C］／／Proceedings of the 9th Annual International Conference on Mobile Computing and Networking，USA：MOBICOM′2003，San Diego，CA，2003：81-95.

［5］Rout C S，Krishna S H，Vivekchand S R C.Hydrogen and ethanol sensors based on ZnO nano wires and nanotubes［J］.Chemical Physics Letter，2006， 418：586-590.

［6］徐小玲，張福強(qiáng)，李少彪.基于APIT的無(wú)線傳感器網(wǎng)絡(luò)質(zhì)心算法研究［J］.傳感器與微系統(tǒng)，2011，7（30）：57-63.

［7］陳維克，李文鋒，首珩，等.基于RSSI的無(wú)線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法［J］.武漢理工大學(xué)學(xué)報(bào)，2006，30（2）：265-268.

［8］馮秀芳，崔秀鋒，祈會(huì)波，等.無(wú)線傳感網(wǎng)絡(luò)中基于移動(dòng)錨節(jié)點(diǎn)的APIT的改進(jìn)定位算法［J］.傳感技術(shù)學(xué)報(bào)，2011，24（2）：269-274.

［9］楊驥，劉鋒.無(wú)線傳感器網(wǎng)絡(luò)基于中垂線分割的APIT的改進(jìn)定位算法［J］.傳感技術(shù)學(xué)報(bào)，2008，21（8）：1453-1457.

［10］Li D，Hu Y H.Energy based collaborat ive source localizat ion using acoust ic micro-sensor array［J］.Journal EUROS IP Applied Signal Processing，2003（4）：321-337.

［11］姚艷，禹繼國(guó)，郭強(qiáng).基于網(wǎng)格掃描的無(wú)線傳感器網(wǎng)絡(luò)定位算法［J］.計(jì)算機(jī)工程，2012，38（9）：86-89.

［12］周彥，文寶，李建勛.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)近點(diǎn)加權(quán)質(zhì)心定位方法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48（1）：87-89.

［13］萬(wàn)國(guó)峰，鐘俊.基于三角形理論的無(wú)線傳感器網(wǎng)絡(luò)定位算法［J］.計(jì)算機(jī)應(yīng)用研究，2013，1（7）：249-251.

［14］楊凌云，馮友宏.一種新的無(wú)線傳感器網(wǎng)絡(luò)半動(dòng)態(tài)分簇路由協(xié)議［J］.長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，30（1）：48-51.

A modified APIT localization algorithm based on perpendicular intersection features

YANG Ling－yun， FENG You-hong

（The College of Physics and Electronic Information，Anhui Normal University，Wuhu 241000，China）

To overcome the flaws in APIT algorithm，a new method to identify the unknown nodes is put forward.First，three random anchor nodes are chosen，and then the perpendicular intersection is obtained，where the vertical through any one node goes to the line of other two nodes.By comparing the distance of the node to the intersection with the one to the unknown node，the location of the unknown node can be determined.The position of the node can be calculated with the centroid algorithm.Matlab simulation results show that the modified APIT algorithm is with higher precision than that of classic one.

APIT；perpendicular；intersection；weighting；centroid algorithm.

TP 393

A

1674-1374（2014）01-0096-05

2013-11-21

安徽省高校自然科學(xué)基金（KJ2010B350）；國(guó)家“863”電動(dòng)汽車重大專項(xiàng)基金（2011AA11216A）

楊凌云（1983－），女，漢族，河南周口人，安徽師范大學(xué)講師，主要從事無(wú)線網(wǎng)絡(luò)方向研究，E-mail：lingyun716＠126.com.＊通訊作者：馮友宏（1979－），男，漢族，安徽池州人，安徽師范大學(xué)副教授，主要從事無(wú)線網(wǎng)絡(luò)方向研究，E-mail：yhfeng0215＠126.com.