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

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

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

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

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

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

引 言

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

1 APlT定位算法及誤差分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 改進(jìn)的APlT定位算法

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

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

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

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

化簡得：

令：

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

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

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

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

3 APlT改進(jìn)算法仿真分析

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

3.1 原算法性能分析

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

圖6 改進(jìn)后的APlT定位算法流程圖

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

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

3.2 不同θ值下改進(jìn)算法與原算法定位誤差比較

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

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

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

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

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

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

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

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

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

結(jié) 語

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

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

［1］郭龍江，李建中，李金寶.無線傳感器網(wǎng)絡(luò)若干定位算法的研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，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é)點(diǎn)設(shè)計(jì)和關(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é)點(diǎn)自定位算法研究［D］.成都：西南交通大學(xué)，2006.

苗少卿（研究生），研究方向?yàn)榍度胧讲僮飨到y(tǒng)；高航（副教授），研究方向?yàn)榍度胧较到y(tǒng)及應(yīng)用；趙國安（教授），研究方向?yàn)樾畔⒓夹g(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）