無線傳感網絡APIT定位算法的研究與改進※

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

無線傳感網絡APIT定位算法的研究與改進※

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

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

APIT定位；三角形測試；網格掃描算法；三邊測量

引 言

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

1 APlT定位算法及誤差分析

APIT定位算法是一種與距離無關的算法，該算法充分利用了無線傳感網絡中信標節點的拓撲結構信息。具體過程如下：

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

最后，利用網格掃描算法（Grid Scan）將優選三角形區域無限重疊得到最佳位置，如圖1所示。

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

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

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

圖1 網格掃描算法示意圖

圖2 完備矢量構建示意圖

在滿足構建完備矢量的條件下，APIT測試可以順利進行。相反，當節點分布稀疏或者節點分布不均勻時，會出現“內判外”或“外判內”的錯誤判定情況，如圖3和圖4所示。

圖3 不滿足構建完備矢量的示意圖

圖4 不同節點分布下誤判發生情況

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

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

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

2 改進的APlT定位算法

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

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

5 稀疏環境下未知節點與信標節點的最短路徑示意圖

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

化簡得：

令：

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

① 每個節點設置計數器，用來計量權重值τ，初始狀態為0。

最后根據τ的正負進行三角形的最終判斷：若τ＞0，那么未知節點在三角形內；若τ＜0，則在三角形外。

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

3 APlT改進算法仿真分析

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

3.1 原算法性能分析

在1000×1000二維平面區域內隨機部署100個未知節點和50個信標節點，設置未知節點通信距離為100m，信標節點通信距離為300m。

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

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

圖7 不同密度下節點定位誤差

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

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

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

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

3.3 不同網絡連通度下改進算法與原算法定位誤差比較

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

圖9是不同的網絡連通度情況下改進算法與原算法定位誤差的比較。可以看出，改進后的APIT定位算法在不同的網絡連通度情況下，定位誤差相比于原算法都有明顯的降低。

圖9 不同網絡連通度下改進算法與原算法的誤差比較

3.4 改進算法與原算法網絡覆蓋率的比較

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

結 語

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

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

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

［2］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京：清華大學出版社，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］蕭奮洛.無線傳感器網絡節點設計和關鍵技術研究［D］.武漢：華中科技大學，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］王丹.三維無線傳感器網絡節點自定位算法研究［D］.成都：西南交通大學，2006.

苗少卿（研究生），研究方向為嵌入式操作系統；高航（副教授），研究方向為嵌入式系統及應用；趙國安（教授），研究方向為信息技術與物聯網的應用。

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）