基于四面體體積判斷的三維APIT 定位算法

徐磊磊， 徐保國

(江南大學 輕工過程先進控制教育部重點實驗室，江蘇 無錫214122)

無線傳感器網絡(Wireless Sensor Networks，WSNs)是一種新型信息感知、收集和處理技術，其應用能否成功實施的關鍵是節(jié)點提供的位置信息是否準確［1-2］。目前，應用在傳感器網絡中的定位方法主要分為基于測距技術和非基于測距兩類［3］。基于測距技術通常通過測量節(jié)點間的距離或角度關系，使用常用的定位方法(如三角測量法、三邊測量法以及最大似然估計法等)估算出待定位節(jié)點的位置［4］。由于需要額外的硬件支撐且易受環(huán)境的影響，不太適用大規(guī)模傳感器網絡的部署。非基于測距的技術一般利用節(jié)點之間的鄰近關系和連通性實現(xiàn)定位，無需額外的硬件，能夠滿足多數(shù)應用的定位要求，性價比較高。典型的算法有質心法、APIT算法［5］、凸規(guī)劃算法、DV-Hop 算法［6］等。

目前，三維定位算法的研究通常在二維定位算法的基礎上擴充維數(shù)形成新的三維定位算法。劉玉恒等［7］將二維的APIT 算法引入到三維空間，提出了APIT-3D 定位算法，在通信開銷未顯著增加的條件下獲得了較好的定位精度，但此過程中容易發(fā)生邊界效應，影響定位精度;相衛(wèi)華等［8］提出利用三維網格定位解決重疊四面體區(qū)域的定位問題;胡偉等［9］提出了四面體質心迭代解決網格掃描算法計算復雜度問題，但在鄰居節(jié)點數(shù)量較少或未知節(jié)點處于四面體邊界時，會出現(xiàn)測試錯誤。

針對以上問題，文中提出一種基于四面體體積測試三維近似內點測試(VJ-APIT)的無線傳感器網絡定位算法，該算法利用推導出的體積公式改進內點測試方法，同時修正RSSI 測距誤差。與傳統(tǒng)的算法相比，改進后的算法減少了未知節(jié)點誤判的概率，從而提高了定位精度。

1 APIT-3D 算法

APIT-3D 算法的基本原理:假設存在一個方向，待定位未知節(jié)點沿著此方向運動，同時接近或者遠離四面體4 個頂點A，B，C，D，則未知節(jié)點在四面體區(qū)域外，否則，在四面體內［10］。同二維平面類似，由于實際的網絡是靜態(tài)網絡，利用高節(jié)點密度模擬移動，通過無線信號傳播特性判斷未知節(jié)點接近還是遠離錨節(jié)點，即通過比較鄰居節(jié)點接收到的信號強度大小判定未知節(jié)點與該鄰居節(jié)點跟錨節(jié)點的遠近關系，從而有效模擬未知節(jié)點的移動，即APIT-3D測試。

在網絡部署完成后，對監(jiān)控區(qū)域進行網格劃分，設網格分辨率為q，以一個錨節(jié)點為中心建立空間直角坐標系。設三維立體空間區(qū)域為正方體ψ，體積為V，對于任何一個立方體網格有φi∈ψ，則共有V/a3個網格，每個網格均為動態(tài)網格，初始化為0，可根據情況加減1。APIT-3D 測試結束后，所有包含待定位節(jié)點四面體區(qū)域的網格加1，不包含的網格減1。統(tǒng)計所有網格數(shù)值，找到權重最大的區(qū)域，即為需要尋找的區(qū)域。將重疊區(qū)域的質心作為待定位節(jié)點的估算位置。

2 VJ-APIT 算法原理

和二維算法類似，APIT-3D 同樣存在著In-to-Out Error 和Out-to-In Error 兩種誤判，文中提出的改進APIT-3D 算法從避免兩種誤判發(fā)生的角度出發(fā)，基本思路是通過所推導的體積計算公式，利用四面體體積和判斷未知節(jié)點位于四面體內部還是外部，從而改進內點測試方法。

2.1 新內點測試方法

體積判斷原理如圖1 所示。設錨節(jié)點A，B，C，D組成的四面體ABCD 的體積為V，未知節(jié)點M 與4 個錨節(jié)點組成4 個小四面體ABCM，ABMD，AMCD，MBCD，體積記為V1，V2，V3，V4。若V1+ V2+ V3+V4=V，則可判斷未知節(jié)點在四面體內部(見圖1(a));若V1+V2+V3+V4＞V，則可判斷未知節(jié)點在四面體外部(見圖1(b))。

圖1 體積判斷原理Fig.1 Volume estimation principle

該方法改進了內點測試方法，相比原來的方法更簡明適用。其關鍵是如何計算四面體的體積，分兩種情況考慮:

1)對于錨節(jié)點而言，本身位置已知，可獲得其坐標，設A，B，C，D 4 個坐標分別為(x1，y1，z1)，(x2，y2，z2)，(x3，y3，z3)，(x4，y4，z4)。由數(shù)學知識可以求出四面體ABCD 的體積為VABCD，其計算公式為

2)對于待定位節(jié)點和錨節(jié)點構成的四面體而言，由于待定位節(jié)點的坐標未知，所以不能用式(1)直接計算。體積計算的推導如圖2 所示。

圖2 體積計算的推導Fig.2 Derivation of the volume calculation

由圖2 可知，利用RSSI 測距技術可以測出未知節(jié)點和任意3 個錨節(jié)點組成的四面體(不妨以四面體ABCM 為例)的六條棱長分別為l，m，n，p，q，r。為推導方便，以M 為坐標原點建立空間直角坐標系，由式可知:

將式(2)兩邊同時平方得

由矢量數(shù)量積的坐標表達式及數(shù)量積的定義得

根據余弦定理

x1x2+ y1y2+ z1z2= MA·MB =

將式(4)和式(5)代入式(3)，求出四面體的體積

同理，可以求出其他3 個四面體的體積，從而判斷出待定位未知節(jié)點是否在四面體內。該方法改進了內點測試方法。

2.2 修正RSSI 測距誤差

在VJ-APIT 算法中，要利用RSSI 測距技術計算未知節(jié)點到錨節(jié)點之間距離。RSSI 測距技術是利用接收信號強度對比發(fā)射信號強度算出信號在傳播過程中的損耗值，根據理論或經驗的傳播模型將傳播損耗轉化為距離值。實際應用中，由于受到反射、天線增益、非視距、多徑傳播等各種環(huán)境因素的影響，測距誤差較大。針對上述問題，文中提出了一種修正RSSI 測距誤差的方法以提高測距精度。

無線傳感器網絡中，由于錨節(jié)點的位置已知，可由節(jié)點的坐標計算出任意兩個錨節(jié)點的距離。這個距離是真實的距離，稱為實際距離，記為d1。也可由RSSI 測距方法獲得距離，這個距離稱為測量距離，記為d2。比較測量距離和實際距離，將兩者相減可得到RSSI 測距的誤差值Δd，即Δd = d2－ d1，網絡中所有錨節(jié)點平均測距誤差如下:

其中，Δd 為平均RSSI 測距誤差值;n 為錨節(jié)點總數(shù);m 為錨節(jié)點通信半徑內的錨節(jié)點數(shù);dij為錨節(jié)點i 到錨節(jié)點j 的實際距離;d'ij為錨節(jié)點i 到錨節(jié)點j 的測量距離。

將平均RSSI 測距誤差值修正到節(jié)點到其他節(jié)點的測量距離，具體表示為

其中，d'u為修正后的測量距離;du為修正前的測量距離。

修正方法降低了網絡中任意兩點的距離測量誤差，提高了測量精度，可使節(jié)點的定位精度獲得提高。

3 VJ-APIT 定位算法步驟

VJ-APIT 算法主要從改進內點測試方法和RSSI測距誤差兩個方面提高節(jié)點的定位精度，具體步驟如下:

1)網絡部署完成后，錨節(jié)點廣播自身信息，包括標識號ID、位置、信號強度等。錨節(jié)點和待定位節(jié)點均接收其通信范圍內的鄰居錨節(jié)點信息。若未知節(jié)點收到錨節(jié)點的個數(shù)n ≥4，則繼續(xù)執(zhí)行下一步，否則節(jié)點M 定位結束。

3)用三維網格掃描算法計算出四面體的重疊區(qū)域，即所有包含未知節(jié)點的四面體的交集，將權值最大的部分作為優(yōu)選區(qū)域。

4)將重疊區(qū)域的質心位置坐標作為未知節(jié)點M 的估算位置，完成節(jié)點M 的定位。

4 仿真實驗分析

為有效評估VJ-APIT 算法的性能，通過與原APIT-3D 算法對比分析，采用Matlab7.1 進行一系列模擬仿真。為了減少隨機分布和降低實驗的偶然性，最終仿真數(shù)據取20 次相同參數(shù)環(huán)境結果的平均值。

仿真實驗采用隨機部署模型，將所有的節(jié)點(錨節(jié)點和待定位節(jié)點)隨機部署在1 000 m ×1 000 m ×1 000 m 的標準立方形監(jiān)控區(qū)域內。節(jié)點總數(shù)為300，未知節(jié)點通信半徑為200 m，錨節(jié)點與未知節(jié)點通信半徑比為1.2，傳輸模型采用規(guī)則模型。

圖3 為在其他條件不變的情況下改變錨節(jié)點比例的實驗結果。

圖3 錨節(jié)點比例對定位誤差的影響Fig.3 Effect of the anchor node proportion on the positioning error

由圖3 可以看出，兩種定位算法定位誤差都隨著錨節(jié)點比例的增大而下降，并逐漸趨于平穩(wěn)。錨節(jié)點比例較低時，兩種算法定位誤差均較大。當錨節(jié)點比例逐漸增大，相比于APIT-3D 定位算法，改進的VJ-APIT 算法定位精度提高很多。這是由于VJ-APIT 算法改進了內點測試方法，減少了兩種誤判發(fā)生的概率，從而提高了定位精度。從曲線的趨勢來看，改進算法更適合大規(guī)模、連通度高的網絡。

圖4 為不同通信半徑比對定位誤差的影響。

由圖4 可以看出，在通信半徑d 在1 ～1.75 時，由于處于錨節(jié)點稀少地區(qū)的未知待定位節(jié)點容易出現(xiàn)兩類誤判，因此定位誤差較高，改進算法相比原算法大幅提高了定位精度。隨著通信半徑比的增大，網絡連通度增大，兩者定位誤差均呈下降趨勢。從圖4 中可以看出，改進算法定位精度相對于原算法定位性能更好。

錨節(jié)點比例對定位耗時的影響如圖5 所示。

圖4 不同通信半徑比對定位誤差的影響Fig.4 Effect of the communication radius ratio on the positioning error

圖5 錨節(jié)點比例對定位耗時的影響Fig.5 Effect of the anchor node proportion on the locating time-consuming

由圖5 可以看出，隨著錨節(jié)點比例的增大，定位耗時也相應增加。這是由于錨節(jié)點數(shù)目增大能夠構成的四面體數(shù)目增多，定位計算消耗的時間也隨之變大，VJ-APIT 定位算法相比原算法增加少量通信耗時，但提高了顯著定位精度，這是合理的代價。

5 結 語

文中從改進內點測試方法和RSSI 測距誤差兩個方面，提出了一種改進的APIT-3D 算法，即VJ-APIT 算法。該算法提出的修正RSSI 測距誤差方法提高了測量精度，有效降低了節(jié)點間的測距誤差，提高了節(jié)點定位精度，改進內點測試方法，減少了In-to-Out Error 和Out-to-In Error 兩種誤判的概率。算法雖增加了少量通信耗時，但實現(xiàn)了更準確的定位。改進算法更適合大規(guī)模、連通度高的網絡。

［1］Akyildiz I F，Weilian S，Sankarasubramaniam Y，et al.A survey on sensor networks［J］.Communications Magazine，IEEE，2002，40(8):102-114.

［2］XU E Y，DING Z，Dasgupta S.Sourcelocalization in wireless sensor networks from signal time-of-arrival measurements［J］.IEEE Transations on Signal Processing，2011，59(6):2887-2897.

［3］周勇，夏士雄，丁世飛，等.基于三角形重心掃描的改進APIT 無線傳感器網絡自定位算法［J］.計算機研究與發(fā)展，2009，46(4):566-574.

ZHOU Yong，XIA Shixiong，Ding Shifei，et al.An improved APIT node self-localization algorithm in WSN based on triangle-center scan［J］.Journal of Computer Research and Development，2009，46(4):566-574.(in Chinese)

［4］LI S，DING X，YANG T. Analysis of five typical localization algorithms for wireless sensor networks［J］. Wireless Sensor Network，2015，7(4):27-29.

［5］HE T，Huang C D，Blun B M，et al.Range-free localization schemes in large scale sensor networks［C］//Proc of the 9th Annual Int’l Conf on Mobile Computing and Networking.New York:ACM，2003:81-95.

［6］LIN Z G，LI L，ZHANG H Q，et al.An APIT algorithm based on DV-HOP multi-hop［J］.Advanced Materials Research，2013，787(2):1038-1043.

［7］劉玉恒，蒲菊花，赫陽，等.無線傳感器網絡三維自身定位方法［J］.北京航空航天大學學報，2008，34(6):647-651.

LIU Yuheng，PU Juhua，HE Yang，et al. Three-dimensional self-localization scheme for wireless sensor networks［J］. Journal of Beijing University of Aeronautics and Astronautics，2008，34(6):647-651.(in Chinese)

［8］相衛(wèi)華，賈超，王華奎，等.無線傳感器網絡三維APIT 網格化算法［J］.傳感技術學報，2012，25(5):639-643.

XIANG Weihua，JIA Chao，WANG Huakui，et al. Three-dimensional grid of APIT algorithm in wireless sensor network［J］.Chinese Journal of Sensors and Actuators，2012，25(5):639-643.(in Chinese)

［9］胡偉，朱西平，文紅，等.基于四面體質心迭代的三維APIT 定位算法研究［J］.傳感技術學報，2013，26(10):1432-1436.

HU Wei，ZHU Xiping，WEN Hong，et al. Three-dimensional APIT localization algorithm based on tetrahedron centroid iteration［J］.Chinese Journal of Sensors and Actuators，2013，26(10):1432-1436.(in Chinese)

［10］陳月娥，余敏.無線傳感器網絡中APIT-VP 三維定位算法［J］.傳感器與微系統(tǒng)，2014，33(5):148-153.

CHEN Yuee，YU Min. APIT-VP 3D localization algorithm for WSNs［J］. Transducer and Microsystem Technologies，2014，33(5):148-153.(in Chinese)