苗少卿，高航，趙國安（南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院，南京 210016）

無線傳感網(wǎng)絡(luò)APIT定位算法的研究與改進※

苗少卿，高航，趙國安
（南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院，南京 210016）

針對APIT定位算法在節(jié)點分布不均勻和信標節(jié)點較少時定位誤差較大的問題，對原算法進行改進，其中包括節(jié)點分布稀疏情況下，采用最短路徑距離估算和三邊測量的方法修正原算法三角形測試產(chǎn)生的Out-To-In Error，以及節(jié)點分布密集情況下，采用相對權(quán)重法修正In-To-Out Error。實驗仿真結(jié)果表明，改進后的APIT算法定位精度和網(wǎng)絡(luò)覆蓋率相比原算法都有明顯的提高。

APIT定位；三角形測試；網(wǎng)格掃描算法；三邊測量

引 言

定位技術(shù)是無線傳感器網(wǎng)絡(luò)關(guān)鍵支撐技術(shù)之一［1］，在無線傳感網(wǎng)絡(luò)實際應(yīng)用中，利用信標節(jié)點獲得未知節(jié)點的絕對地理位置或者相對參照系位置的信息具有十分重要的意義。本文研究的APIT［3］定位算法是一種免于測距的定位算法，該算法基本思想簡單，容易實現(xiàn)，具有功耗低、成本低、節(jié)點定位精度高等特點，因此得到廣泛的應(yīng)用和研究。然而APIT算法在節(jié)點分布稀疏和節(jié)點分布密集情況下容易出現(xiàn)較大定位誤差，因此針對此問題本文提出一種改進的APIT算法。

1 APlT定位算法及誤差分析

APIT定位算法是一種與距離無關(guān)的算法，該算法充分利用了無線傳感網(wǎng)絡(luò)中信標節(jié)點的拓撲結(jié)構(gòu)信息。具體過程如下：

首先，信標節(jié)點覆蓋在整個區(qū)域內(nèi)，選取不共線的三個信標節(jié)點A、B、C組建三角形；其次，判斷未知節(jié)點M是否在ΔABC內(nèi)部，方法如下：未知節(jié)點M沿某一矢量l→移動到新的位置M＇后，如果M＇與三個端點A、B、C的距離滿足關(guān)系式（1），則可以判定點M在ΔABC外部，如果不存在這樣的方向矢量，則判定點M在ΔABC內(nèi)部，并把ΔABC標記為優(yōu)選三角形。定理證明見參考文獻［3］，通過該方法可以找出包含未知節(jié)點的所有優(yōu)選三角形。

最后，利用網(wǎng)格掃描算法（Grid Scan）將優(yōu)選三角形區(qū)域無限重疊得到最佳位置，如圖1所示。

可以看出，APIT算法依靠方向矢量進行三角形判定，要求有較高的網(wǎng)絡(luò)連通度，然而組建一個完備矢量，要求同時滿足：

① 未知節(jié)點與所有鄰居節(jié)點連線方向矢量基本包括了0～2π的范圍，如圖2（a）所示。

② 方向矢量的構(gòu)建要求在一個測試三角形內(nèi)或者測試三角形外完成，如圖2（b）所示。

圖1 網(wǎng)格掃描算法示意圖

圖2 完備矢量構(gòu)建示意圖

在滿足構(gòu)建完備矢量的條件下，APIT測試可以順利進行。相反，當(dāng)節(jié)點分布稀疏或者節(jié)點分布不均勻時，會出現(xiàn)“內(nèi)判外”或“外判內(nèi)”的錯誤判定情況，如圖3和圖4所示。

圖3 不滿足構(gòu)建完備矢量的示意圖

圖4 不同節(jié)點分布下誤判發(fā)生情況

如圖3（a）所示，這種情況下雖然滿足矢量完備性條件1，但是不滿足條件2，在三角形判定過程中，未知節(jié)點若選定鄰居節(jié)點1構(gòu)建方向矢量，則出現(xiàn)同時遠離3個信標節(jié)點的情況，根據(jù)APIT測試，就會得出未知節(jié)點在三角形外的錯誤判斷，稱作內(nèi)到外誤判（In-To-Out Error）。如圖4（b）所示，在節(jié)點分布密集時，遠離或接近信標節(jié)點的方向矢量是很容易找到的，因此會出現(xiàn)較多In -To-Out Error。

如圖3（b）所示，這種情況下不滿足矢量完備性條件1，所有的方向矢量沒有同時遠離或接近3個信標節(jié)點，根據(jù)APIT測試，就會得出未知節(jié)點在三角形內(nèi)的錯誤判斷，稱作外到內(nèi)誤判（Out-To-In Error）。這種錯誤常出現(xiàn)在節(jié)點分布稀疏的時候，如圖4（a）所示。

這兩種情況下APIT算法都會出現(xiàn)錯誤判斷。其次在部署范圍內(nèi)的邊界，信標節(jié)點往往不能將普通節(jié)點全部覆蓋到，造成部分普通節(jié)點獨立于信標節(jié)點外，無法定位，這種情況是由于APIT算法覆蓋率不高造成的，也是APIT定位發(fā)生誤差的主要原因之一。

2 改進的APlT定位算法

在節(jié)點稀疏環(huán)境中，方向矢量少，沒有同時接近或遠離三角形的鄰居節(jié)點，最容易出現(xiàn)較多的Out-To-In Error。處在邊緣環(huán)境中的未知節(jié)點組建的三角形數(shù)目較少或者根本無法組建三角形，也會造成APIT判定失效。針對這兩個問題，可以通過以下方法彌補APIT定位缺陷：

① 首先，信標節(jié)點兩兩通信，記錄到達對方的最短路徑的距值，記為ξ。如圖5所示，信標節(jié)點最短路徑距離：ξAB=3，ξBC=3，ξAC=5。然后根據(jù)信標節(jié)點的位置信息，計算三角形三邊距離總和L和平均最短路徑l，設(shè)A、B、C的坐標分別為A（x1，y1），B（x2，y2），C（x3，y3），有：

5 稀疏環(huán)境下未知節(jié)點與信標節(jié)點的最短路徑示意圖

② 其次，未知節(jié)點通過跳段式的傳播方式與信標節(jié)點通信，記錄到達3個信標節(jié)點所需要的最少跳數(shù)，記為λ，在圖5中未知節(jié)點M到3個信標節(jié)點的最少跳數(shù)分別為λMA=3，λMB=2，λMC=4，這樣估算出未知節(jié)點到3個信標節(jié)點的距離為：③ 最后，利用三邊測量法得：

化簡得：

令：

在節(jié)點密集的環(huán)境中，由于方向矢量的增加，尋找同時遠離或接近信標節(jié)點的方向矢量是很容易的，但會造成APIT算法出現(xiàn)In-To-Out Error。這里采用相對權(quán)重法來解決這個問題，該方法是通過權(quán)重對比，根據(jù)兩種判定影響因素大小決定定位結(jié)果，以降低誤判概率。方法如下：

① 每個節(jié)點設(shè)置計數(shù)器，用來計量權(quán)重值τ，初始狀態(tài)為0。

最后根據(jù)τ的正負進行三角形的最終判斷：若τ＞0，那么未知節(jié)點在三角形內(nèi)；若τ＜0，則在三角形外。

改進后的APIT算法是針對不同的節(jié)點分布情況采用不同的定位方法，當(dāng)節(jié)點分布均勻時仍使用原始的算法，當(dāng)節(jié)點分布不均勻時采用改進算法。這里以節(jié)點密度σ作為判定標準，設(shè)定最低門限為α，最高判決門限為β，當(dāng)節(jié)點密度小于α或大于β時，均視為節(jié)點分布不均勻的情況，流程圖如圖6所示。

3 APlT改進算法仿真分析

為了檢測APIT改進算法與原始算法的性能，釆用MATLAB軟件進行仿真。通過設(shè)置不同的實驗環(huán)境，逐一比較兩者的性能，每設(shè)置一次參數(shù)，仿真10次并對其結(jié)果取平均值作為最終數(shù)據(jù)。

3.1 原算法性能分析

在1000×1000二維平面區(qū)域內(nèi)隨機部署100個未知節(jié)點和50個信標節(jié)點，設(shè)置未知節(jié)點通信距離為100m，信標節(jié)點通信距離為300m。

圖6 改進后的APlT定位算法流程圖

如圖7是APIT原算法在不同密度下節(jié)點的定位誤差，可以看出，在節(jié)點密度低于11%或者高于24%時，定位誤差較大。在節(jié)點密度較低的情況下，一方面導(dǎo)致判定方向矢量不足，在進行APIT判定時會出現(xiàn)較多的Out-To -In Error，另一方面是信標節(jié)點稀疏無法組建有效的三角形，也會造成APIT算法失效；在節(jié)點密度較高情況下，與第一種情況相反出現(xiàn)較多的In-To-Out Error，同樣導(dǎo)致誤差較大。APIT算法在節(jié)點密度11%～24%之間時，定位誤差維持在10%左右。因此，在改進的APIT算法中將最低判決門限α設(shè)為11%，最高判決門限β設(shè)為24%。在后面的仿真實驗中，均按照此閾值進行對比分析。

圖7 不同密度下節(jié)點定位誤差

3.2 不同θ值下改進算法與原算法定位誤差比較

設(shè)Ru是未知節(jié)點通信距離，Rb是信標節(jié)點距離，設(shè)通信半徑比為θ，定義為Rb/Ru，不同θ值下的節(jié)點通信情況略——編者注，可以看出，隨著信標節(jié)點通信距離的增加，網(wǎng)絡(luò)覆蓋面積也越來越大。

圖8是不同θ值情況下原始算法與改進算法定位誤差的比較?？梢钥闯?，改進后的APIT定位算法在不同的通信半徑比情況下，定位誤差相比于原算法都有明顯的降低。

8 不同θ值下改進算法與原算法定位誤差比較示意圖

3.3 不同網(wǎng)絡(luò)連通度下改進算法與原算法定位誤差比較

APIT算法要求有較高的網(wǎng)絡(luò)連通度，連通度是影響定位算法的關(guān)鍵因素，這里設(shè)置未知節(jié)點的通信范圍為Ru，在信標節(jié)點通信距離一定，不同Ru情況下節(jié)點的通信情況略——編者注，可以看出Ru越大，單位面積內(nèi)能夠偵聽到的信標節(jié)點越多，網(wǎng)絡(luò)連通度越好。

圖9是不同的網(wǎng)絡(luò)連通度情況下改進算法與原算法定位誤差的比較?？梢钥闯?，改進后的APIT定位算法在不同的網(wǎng)絡(luò)連通度情況下，定位誤差相比于原算法都有明顯的降低。

圖9 不同網(wǎng)絡(luò)連通度下改進算法與原算法的誤差比較

3.4 改進算法與原算法網(wǎng)絡(luò)覆蓋率的比較

改進算法與原算法網(wǎng)絡(luò)覆蓋率的對比圖略——編者注。可以看出，在信標節(jié)點比例較少的情況下，原始算法的覆蓋率很低，只有極少的節(jié)點可以定位，而改進的APIT算法利用周圍的鄰居節(jié)點，在信標節(jié)點較少的情況下就可以有較高的覆蓋率。改進后的APIT算法相比于原算法在不同的信標節(jié)點密度下，網(wǎng)絡(luò)覆蓋率有明顯的提高。

結(jié) 語

本文主要研究了無線傳感網(wǎng)絡(luò)經(jīng)典定位算法之一的APIT算法，介紹了其定位原理及方法，并詳細分析了APIT算法的缺陷以及產(chǎn)生原因，隨后對算法出現(xiàn)的兩種誤判及稀疏節(jié)點環(huán)境下的定位限制進行改進，仿真結(jié)果表明，改進后的APIT算法定位誤差和網(wǎng)絡(luò)覆蓋率都有很大的改進。

編者注：本文為期刊縮略版，全文見本刊網(wǎng)站www. mesnet.com.cn。

［1］郭龍江，李建中，李金寶.無線傳感器網(wǎng)絡(luò)若干定位算法的研究［J］.計算機工程與設(shè)計，2006，27（12）：2114-2119.

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

［3］T He，C Huang，B M Blum，et al.Range free localization schemes for large scale sensor networks［C］//ACM Int＇l Symptom Mobile Ad Hoc Networking and Computing（MOBIHOC 2003），Maryland，USA，2003.

［4］Z X Jia，C D Wu，Y Z Zhang，et al.Distributed Grid Location Estimation Scheme Based on Euclidean Distance［C］//IEEE 3rd Conference on Industrial Electronics and Applications，2008：1128-1132.

［5］Zhang Rui，Zhao Hang，Labrador，et al.A grid-based sink location service for large-scale wireless sensor network［C］//Proceedings of the 2006International Wireless Communications and Mobile Computing Conference，2006：689-694.

［6］蕭奮洛.無線傳感器網(wǎng)絡(luò)節(jié)點設(shè)計和關(guān)鍵技術(shù)研究［D］.武漢：華中科技大學(xué)，2009.

［7］Liqiang Zhang，Xiaobo Zhou，Qiang Cheng.Landseape3D：A Robust Localization Scheme for Sensor Networks over Complex 3DTerrains［C］//Proceedings of the 31st IEEE Conference on Local Computer Networks，2006：239-246.

［8］王丹.三維無線傳感器網(wǎng)絡(luò)節(jié)點自定位算法研究［D］.成都：西南交通大學(xué)，2006.

苗少卿（研究生），研究方向為嵌入式操作系統(tǒng)；高航（副教授），研究方向為嵌入式系統(tǒng)及應(yīng)用；趙國安（教授），研究方向為信息技術(shù)與物聯(lián)網(wǎng)的應(yīng)用。

Research and lmprovement of APlT Positioning Algorithm for Wireless Sensor Network※

Miao Shaoqing，Gao Hang，Zhao Guoan
（School of Computer Science and Technology，Nanjing University of Aeronautics&Astronautics，Nanjing 210016，China）

Aiming at the large positioning error problem of APIT positioning algorithm in no uniform nodes distribution and beacon less nodes，the article improves the original algorithm，including the distribution of nodes in sparse，amends the original triangle test produced a Out-To-In Error based on the shortest path distance estimation and three edge measurement method and dense nodes distribution situation，using the relative weight method to modify In-To-Out Error.The simulation results show that the positioning accuracy and coverage of APIT network algorithm are all improved compared to the original algorithm.

APIT positioning；the triangle test；the grid scanning algorithm；three edge measurement

TP393

A

??薛士然

2015-01-28）