垂直交點APIT定位改進算法

楊凌云， 馮友宏

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

垂直交點APIT定位改進算法

楊凌云， 馮友宏

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

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

APIT；垂直；交點；加權；質心算法

0 引 言

無線傳感器網絡是一種基于低成本、低損耗的自組織無線定位網絡，能夠實現惡劣環境下的信息采集和跟蹤工作［1］。在無線傳感器網絡中，網絡內傳感器節點的自身定位是一項非常關鍵的技術，定位精確的高低直接影響著整個網絡在以后工作中的定位跟蹤能力。節點自身定位方法一

般分為基于距離的定位算法和距離無關的定位算法兩大類［2］，后者因為不需要知道自己與錨節點的角度、距離等信息，而通過信息連通度等信息估計出節點位置信息，這種定位方法因為需要傳遞的信息少，能很好地節約節點能力，實現較長的工作時間而得到廣泛應用和研究，比較常見的與距離無關的定位算法有：dv-hop、質心定位［3］、APIT定位［4］等。其中質心定位算法是一個粗定位算法［5］，APIT算法在節點連通度比較大的情況下定位精度較高［6］，后來就有人把質心定位與APIT結合［7］，提出了基于APIT的質心定位算法。文中針對這種算法的APIT算法在定位過程中的一些問題，在基于APIT的質心定位算法的基礎上提出了改進措施，提高了APIT的定位精度。

1 APIT算法

1.1 PIT測試

在能夠通信的范圍內，找出所有能夠與未知節點通信的錨節點，任意選取其中的3個節點，判斷未知節點是否在這3個節點組成的三角形內部，如果再進行下一步定位運算，如果不在三角形內部，則丟棄這個三角形。判斷是否在三角形內部的方法如果未知節點朝某個方向發生移動，是否是同時遠離或者同時接近這3個錨節點，如果是，則未知節點在三角形外面，如果同時有接近和遠離的節點，則在三角形里面［8］。

在實際應用中，節點的移動是非常緩慢的，或者說在一定條件下可以近似地認為我們的很多無線傳感器網絡是一個靜態網絡，節點是靜止的。針對靜態無線傳感器網絡，文獻［4］提出可以根據未知節點的鄰居節點是否同時遠離和接近三角形節點來判斷未知節點是否在三角形內部的近似PIT算法（簡稱in-out算法）。

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

1.2 定位算法

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

式中：E1——到達未知節點的能量；

E0——錨節點發送時刻的能量；

d1——未知節點與錨節點的距離；

k1——常數，它與信號波長、傳輸環境等信息有關，特定的條件下為一常數。

通過能量比值可以得到相對精確的距離值。在求錨節點包圍的未知節點的位置信息時，常見到的就是網格掃描算法和質心定位算法。在網格掃描算法中，網格的精度直接關系著定位精度，所以很容易出現位置估計不足的問題［11］。在質心定位算法的基礎上加入相應權值，可以得到較為精確的估計值［12］，文中提出加權質心定位算法，加入與能量有關的加權因子，可以得到更為精確的位置估計值。

2 算法改進

這里提出一種新的基于APIT的改進算法

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

2.1 in-out算法改進

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

圖1 D點在三角形內部

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

證明 圖1中，D點為未知節點，A點、B點和C點為已知錨節點，假設在D點能接收到3個錨節點分別發送過來的各自坐標信息和能量信息，那么由式（1）可得，通過接收到的能量值與錨節點發送時的能量進行比值，可以得到兩者之間的距離，即可以得到未知節點分別到3個錨節點距離為：

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

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

D點在三角形外部如圖2所示。

圖2 D點在三角形外部

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

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

具體說明如下：

1）圖2給出了三角形中兩個點與D點不在一個平面的情況，它具有一定代表性。通過不斷實驗發現，在判斷中可能出現3個錨節點中的一個錨節點、兩個錨節點甚至3個錨節點與未知節點不在直線所劃分的同一平面內，可以推導得出同樣的結論。

2）在位置判斷過程中，如果未知節點在離三角形外不遠處的位置，有可能出現三角形的某一個節點的誤判，但只會出現本來在兩個節點在不同平面內，結果誤判的情況，但這不會影響整個判斷結論，另外兩個節點肯定會判斷出來的，圖2中的情況就是一個有可能出現一邊誤判，但不會影響最終結果的情況。

3）對于未知節點可能在三角形某一個邊所在直線的情況，未知節點在三角形外部時，我們取的交點其實是一個對折過去的虛交點，可以很好地區分未知節點在兩個錨節點中間某個位置還是外側。定理2同樣適用。

2.2 加權質心定位

對于已知未知節點位于由已知錨節點組成的三角形內部的節點，采用質心加權的方法來估計未知節點的未知，同時，把未知節點一定在3個垂直交點所組成的三角形內作為約束條件，來進一步精確未知節點。

加權垂直平分節點組成的約束區間如圖3所示。

圖3 加權垂直平分節點組成的約束區間

在圖1中，分析了錨節點三角形內部未知節點與其中一個邊的位置關系，找到了其中的過未知節點的垂直平分交點，同樣的方法可以找到另外兩邊的垂直平分交點，把這三點連接起來構成新的三角形，而未知節點D一定在這個新三角形內部陰影部分（見圖3），這就縮小了選擇的范圍。在對錨節點進行加權質心加權的同時，滿足約束條件的點才符合我們要求的估計值。

同時對三角形質心加權定位估計值為：

這里設三角形的3個點分別是A點坐標（xA，yA）、B點坐標（xB，yB）和C點坐標（xC，yC），未知節點到這3個錨節點的距離分別為dA，dB，dC。因為距離的平方與初始能力和接收能量成正比例關系，所以權值實際上是E0／Ei，E0為初始能量值，Ei為接收到的能量值。實驗證明，對能量進行加權（即對距離的平方進行加權）比簡單的對距離進行加權可以得到更高的準確度。

3 算法仿真

采用Matlab對上面兩種算法進行仿真分析，并在40m×40m的環境中進行測試，對不同錨節點、不同的通信半徑下，通過兩種不同的算法對未知節點進行位置估計的誤差進行比較，如圖4所示。

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

圖4中的通信半徑的變化范圍為10～30m。可以看到，改進的基于垂直交點算法幾乎在每個不同的通信范圍下，都可以得到更低的而且相對穩定的定位誤差，誤差減少為APIT誤差的20%左右，同時，因為測試的區域范圍是40m的一個正方形，可以看到在錨節點通信距離大于20m后變化趨于平穩，所以，并不是錨節點的通信距離越大越好，合適的通信距離既可以節約成本，也可以得到很好的定位效果。

定位誤差隨著錨節點個數的變化如圖5所示。

圖5 定位誤差隨著錨節點個數的變化圖

圖5中錨節點的個數是從20個開始仿真的，每次增加5個錨節點，通過仿真可以看到，改進后的NP-APIT算法的誤差幾乎下降到APIT算法的40%左右，而且誤差值相對穩定。綜上所述，改進的NP-APIT算法的誤差將比APIT算法減少了定位誤差，有效提高了定位精度。

4 結 語

在靜止無線傳感器網絡中，針對APIT算法中的in-out判斷方法和質心定位算法進行了改進，提出了通過對加權垂直分割節點到錨節點距離和未知節點到錨節點距離的比較，來判斷一個錨節點和未知節點是否同在兩個錨節點形成的直線所劃分的同一個平面內來進行未知節點的inout判斷，同時在位置估計中，采用了加權質心定位和未知節點一定在垂直分割點形成的三角形中的約束條件，有效提高了定位精度。

［1］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京：清華大學出版社，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］徐小玲，張福強，李少彪.基于APIT的無線傳感器網絡質心算法研究［J］.傳感器與微系統，2011，7（30）：57-63.

［7］陳維克，李文鋒，首珩，等.基于RSSI的無線傳感器網絡加權質心定位算法［J］.武漢理工大學學報，2006，30（2）：265-268.

［8］馮秀芳，崔秀鋒，祈會波，等.無線傳感網絡中基于移動錨節點的APIT的改進定位算法［J］.傳感技術學報，2011，24（2）：269-274.

［9］楊驥，劉鋒.無線傳感器網絡基于中垂線分割的APIT的改進定位算法［J］.傳感技術學報，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］姚艷，禹繼國，郭強.基于網格掃描的無線傳感器網絡定位算法［J］.計算機工程，2012，38（9）：86-89.

［12］周彥，文寶，李建勛.無線傳感器網絡節點近點加權質心定位方法［J］.計算機工程與應用，2012，48（1）：87-89.

［13］萬國峰，鐘俊.基于三角形理論的無線傳感器網絡定位算法［J］.計算機應用研究，2013，1（7）：249-251.

［14］楊凌云，馮友宏.一種新的無線傳感器網絡半動態分簇路由協議［J］.長春工業大學學報：自然科學版，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

安徽省高校自然科學基金（KJ2010B350）；國家“863”電動汽車重大專項基金（2011AA11216A）

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