一種改進(jìn)的無線傳感器網(wǎng)絡(luò)定位算法

張欣慧，熊肖肖，趙學(xué)健，孫知信

(1.南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210003；2.南京郵電大學(xué) 現(xiàn)代郵政學(xué)院，江蘇 南京 210003)

0 引 言

無線傳感器網(wǎng)絡(luò)具有低功耗、低成本、分布式和自組織的特征，可以廣泛構(gòu)造信息訪問的平臺以實(shí)現(xiàn)一些新的功能，例如對各種檢測對象的信息收集，檢測與跟蹤指定范圍內(nèi)的復(fù)雜目標(biāo)，等等。為了在無線傳感器網(wǎng)絡(luò)中監(jiān)測傳感器網(wǎng)絡(luò)的活動情況以實(shí)現(xiàn)一些具體的網(wǎng)絡(luò)操作和網(wǎng)絡(luò)應(yīng)用，節(jié)點(diǎn)的位置信息非常重要[1]。事件發(fā)生的位置以及節(jié)點(diǎn)的信息都建立在監(jiān)測信息的基礎(chǔ)上，毋庸置疑，沒有定位信息的監(jiān)測消息往往是毫無意義的[2]。因此，位置信息在無線傳感器網(wǎng)絡(luò)應(yīng)用中起到了關(guān)鍵作用。

在現(xiàn)階段，常見的測距方法包括：到達(dá)時間(ToA)、到達(dá)時間差(TDoA)、到達(dá)角度(AoA)和接收信號強(qiáng)度指示器(RSSI)等等。這種類型的算法雖然精度較高，但同時也帶來了硬件要求極高和通信消費(fèi)嚴(yán)重等問題。因此，這些方法并不適用于低能耗或低成本的應(yīng)用程序。具體的定位算法可以根據(jù)節(jié)點(diǎn)處理信息的方式劃分為集中式定位和分布式定位，或根據(jù)是否需要測量距離或角度信息劃分為基于測距的定位和無需測距的定位。無需測距的定位算法不需要測量絕對距離或方向，依靠網(wǎng)絡(luò)連通性的信息或其他方法即可完成定位。常見的此類算法有凸定位算法、質(zhì)心定位算法、DV-hop定位算法、不定型定位算法、APIT算法等。

文中首先介紹了APIT算法的演變史并總結(jié)了每種算法的優(yōu)缺點(diǎn)，指出了未來的研究方向。在此基礎(chǔ)上，詳細(xì)分析了費(fèi)馬點(diǎn)模型及基于中垂線分割的PB-APIT算法的思想，提出了一種基于三角形中線垂面分割的APIT-3D的改進(jìn)算法(vertical plane of triangle midline-approximate point-in-triangulation test-3D，VTM-APIT-3D)，并通過仿真來驗(yàn)證和評估算法的性能。

1 相關(guān)技術(shù)研究

APIT算法于2003年提出[3]，存在的一些問題包括：(1)錨節(jié)點(diǎn)稀疏時對網(wǎng)絡(luò)覆蓋率影響較大，網(wǎng)絡(luò)邊緣處的未知節(jié)點(diǎn)定位難，可擴(kuò)展性較弱；(2)需要判斷測試三角形內(nèi)的靜止未知節(jié)點(diǎn)是否出現(xiàn)假陽性；(3)重疊區(qū)域中節(jié)點(diǎn)的定位精確度需要改進(jìn)。對于APIT算法存在的問題，提出了一些改進(jìn)算法：文獻(xiàn)[4]提出了一種基于三角形重心掃描的改進(jìn)APIT算法，顯著地提高了節(jié)點(diǎn)的平均精度。文獻(xiàn)[5]提出了近似三角形內(nèi)點(diǎn)APIT定位算法和DV-HOP定位算法相結(jié)合的混合定位算法，并證明了其有效性。文獻(xiàn)[6]將未知節(jié)點(diǎn)升級為錨節(jié)點(diǎn)，提出了一種基于中垂線分割的算法，命名為PB-APIT。三角形被每一邊的垂直平分線劃分為4或6個子區(qū)域，通過檢測的信號強(qiáng)度來確認(rèn)未知節(jié)點(diǎn)位于某一個子區(qū)域，該方案使定位精度大約提高18%，解決了問題1；文獻(xiàn)[7]降低了“In-To-Out Error”和“Out-To-In Error”誤判的可能性，以增加判斷的正確性；文獻(xiàn)[8]提出將重疊區(qū)域劃分為多個子區(qū)域以減小三角形區(qū)域的大小，解決了問題3。然而，由于無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)是隨機(jī)分布的，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的建立相當(dāng)困難，上面討論的改進(jìn)算法只能分析一些特殊情況，隨機(jī)性問題仍然是一個難點(diǎn)。

此外，現(xiàn)實(shí)中的無線傳感器網(wǎng)絡(luò)往往被布局在復(fù)雜的三維地形中，為了實(shí)現(xiàn)三維環(huán)境下更為精確的節(jié)點(diǎn)定位，一些文獻(xiàn)對二維的APIT算法進(jìn)行了改進(jìn)，將其擴(kuò)展到三維定位上來。文獻(xiàn)[9]在APIT-3D算法中使用了正中面的概念。如果傳感器網(wǎng)絡(luò)部署在近似立方體空間中，即可借助正中面和通信半徑去除無節(jié)點(diǎn)包含的立方體，以縮小節(jié)點(diǎn)的定位范圍。文獻(xiàn)[10]在APIT中使用蒙特卡洛方法和RSSI濾波器采樣方法，仿真結(jié)果表明MC-APIT的最低位置誤差高達(dá)10%。文獻(xiàn)[11]提出一種融合了APIT，RSSI和PSO且無需測距的定位算法。該算法在信標(biāo)節(jié)點(diǎn)交換信息的過程中對信標(biāo)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)的RSSI測量結(jié)果進(jìn)行加權(quán)，基于強(qiáng)度來測量距離。通過PSO和成本函數(shù)對相鄰節(jié)點(diǎn)的位置和速度矢量連續(xù)迭代，最終使用APIT通過PSO計(jì)算的信標(biāo)節(jié)點(diǎn)和相鄰節(jié)點(diǎn)的距離來計(jì)算未知節(jié)點(diǎn)的坐標(biāo)。文獻(xiàn)[12]認(rèn)為APIT算法的網(wǎng)絡(luò)覆蓋率過低，因此提出了結(jié)合DV-hop的APIT算法，改進(jìn)后的算法解決了未知節(jié)點(diǎn)周圍的鄰居信標(biāo)節(jié)點(diǎn)少于三個就無法定位的問題。實(shí)驗(yàn)結(jié)果表明，該算法的定位精度提高了7.4%，網(wǎng)絡(luò)覆蓋率提高了31.3%。通過對這些研究的深入分析，文獻(xiàn)[13]提出了基于費(fèi)馬點(diǎn)分離的FM-APIT-3D算法，利用費(fèi)馬點(diǎn)將大三棱錐劃分為四塊小三棱錐。當(dāng)無線通信半徑為30時，該算法的定位精度提高至多約17.2%，網(wǎng)絡(luò)覆蓋率始終是100%。

上述文獻(xiàn)均為了解決無線傳感器網(wǎng)絡(luò)中更為精確的節(jié)點(diǎn)定位問題，但是以上大部分定位算法僅適用于二維平面中，部分可用于三維環(huán)境中的定位算法也存在定位精度與網(wǎng)絡(luò)覆蓋率較低的問題。故文中利用數(shù)學(xué)模型對現(xiàn)有的三維定位算法進(jìn)行改進(jìn)，以提高定位精度與網(wǎng)絡(luò)覆蓋率。

2 基礎(chǔ)模型分析

2.1 費(fèi)馬點(diǎn)模型

費(fèi)馬點(diǎn)是三維空間內(nèi)的特殊點(diǎn)，類似于質(zhì)心和內(nèi)部中心。如果存在一個點(diǎn)，它到某有限點(diǎn)集的所有頂點(diǎn)的距離和最小，這一點(diǎn)便被稱為費(fèi)爾馬點(diǎn)。在任意三棱錐中，費(fèi)馬點(diǎn)必然唯一存在且可以將三棱錐劃分為四個子三棱錐。建立三維坐標(biāo)系后，三棱錐的四個頂點(diǎn)為A(x1,y1,z1)、B(x2,y2,z2)、C(x3,y3,z3)、D(x4,y4,z4)，可以通過式1計(jì)算費(fèi)馬點(diǎn)F(xF,yF,zF)：

(1)

文獻(xiàn)[14]提出的FM-APIT-3D算法和文獻(xiàn)[12]提出的DFPLE算法均使用費(fèi)馬點(diǎn)模型定位未知節(jié)點(diǎn)。除此之外，費(fèi)馬點(diǎn)模型還可被用于其他算法中。文獻(xiàn)[15]提出了一種允許計(jì)算是從云跨越到網(wǎng)絡(luò)的無線傳感器網(wǎng)絡(luò)分布式平臺，它減少了傳感器網(wǎng)絡(luò)中的傳輸、中間網(wǎng)絡(luò)以及云基礎(chǔ)設(shè)施。該平臺是完全分布式的，允許均勻網(wǎng)絡(luò)中的每一個節(jié)點(diǎn)接受來自用戶的連續(xù)查詢，找到所有滿足用戶查詢的節(jié)點(diǎn)，再找到一個最佳節(jié)點(diǎn)(費(fèi)馬點(diǎn))對網(wǎng)絡(luò)進(jìn)行查詢，并為用戶提供結(jié)果。文獻(xiàn)[16]提出了一種基于三角剖分的bmO(nlogn)最短路徑算法，結(jié)合改進(jìn)的Dijkstra算法和費(fèi)馬點(diǎn)構(gòu)建一個低能見度圖，可以在較短的時間內(nèi)計(jì)算出近似最短路徑。文獻(xiàn)[17]提出利用費(fèi)馬點(diǎn)進(jìn)行3D注視定位，該方法使用基于3D重建場景的激光雷達(dá)對一個自由漫游的眼動儀進(jìn)行定位，提供了在復(fù)雜的靜態(tài)環(huán)境(例如犯罪現(xiàn)場)中進(jìn)行搜索任務(wù)的策略。

以上算法均通過使用費(fèi)馬點(diǎn)劃分空間來達(dá)到優(yōu)化定位模型的目的，但仍存在一些問題：

(1)費(fèi)馬點(diǎn)模型借助費(fèi)馬點(diǎn)來估計(jì)節(jié)點(diǎn)的位置，但因分割前后均使用APIT-3D算法來判斷未知節(jié)點(diǎn)的有效范圍，算法過程重復(fù)且單一。

(2)費(fèi)馬點(diǎn)模型多次把未知節(jié)點(diǎn)估計(jì)在一個形為三棱錐的有效范圍內(nèi)，再通過計(jì)算這些三棱錐重疊范圍的質(zhì)心來估計(jì)未知節(jié)點(diǎn)的坐標(biāo)。由于同為三棱錐的估計(jì)范圍容易造成累積誤差，導(dǎo)致定位精度較低。

(3)未知節(jié)點(diǎn)通信范圍內(nèi)的鄰居錨節(jié)點(diǎn)有很大的概率會少于四個，這會嚴(yán)重影響定位精度或?qū)е戮W(wǎng)絡(luò)覆蓋率降低。錨節(jié)點(diǎn)的密度是影響定位精度的關(guān)鍵因素，錨節(jié)點(diǎn)越多，定位精度越高，但單純地添加錨節(jié)點(diǎn)又會增加能耗和成本。

(4)APIT算法選擇周圍鄰居節(jié)點(diǎn)密度相對較高的未知節(jié)點(diǎn)來模擬運(yùn)動。當(dāng)未知節(jié)點(diǎn)周圍的鄰居節(jié)點(diǎn)密度較低時，勢必會影響到算法的實(shí)施過程。

因此，文中提出一種新的使用費(fèi)馬點(diǎn)模型的三維定位算法，其定位精度和網(wǎng)絡(luò)覆蓋率與FM-APIT-3D算法和DFPLE算法相比均有所提高。

2.2 PB-APIT算法

PB-APIT算法針對二維的APIT算法進(jìn)行改進(jìn)，是一種僅適用于二維平面的二維定位算法。該算法的執(zhí)行步驟如下：

(1)第一步與APIT算法相似，未知節(jié)點(diǎn)與周圍的鄰居節(jié)點(diǎn)交換各自從測試三角形的三個錨節(jié)點(diǎn)接收到的信息，比較二者接收到的信號強(qiáng)弱，也順便比較未知節(jié)點(diǎn)自身從測試三角形的三個錨節(jié)點(diǎn)接收到的信號強(qiáng)弱。

(2)利用PIT算法判斷未知節(jié)點(diǎn)位于測試三角形的內(nèi)部或外部。若未知節(jié)點(diǎn)周圍存在一個鄰居節(jié)點(diǎn)，它接收到的來自測試三角形的三個錨節(jié)點(diǎn)的信號強(qiáng)度都大于或小于未知節(jié)點(diǎn)所接收到的，則該未知節(jié)點(diǎn)位于測試三角形內(nèi)；反之，則位于測試三角形外。

(3)如果未知節(jié)點(diǎn)位于某測試三角形的內(nèi)部，則利用測試三角形三邊的中垂線對測試三角形進(jìn)行分割。對于直角三角形和鈍角三角形，可被分割為四個小區(qū)域；對于銳角三角形，可被分割為六個。

(4)由于已經(jīng)比較過未知節(jié)點(diǎn)從測試三角形的三個錨節(jié)點(diǎn)接收到信號的強(qiáng)弱，故可以直接判斷出未知節(jié)點(diǎn)位于哪個小區(qū)域內(nèi)。

PB-APIT算法與APIT算法的不同之處在于，有效區(qū)域不再是三角形而是分割后的小區(qū)域，求出所有小區(qū)域的重疊區(qū)域，其質(zhì)心即為未知節(jié)點(diǎn)的坐標(biāo)。有效區(qū)域從三角形到多邊形小區(qū)域的改變，減少了累積誤差的產(chǎn)生，提高了定位精度，有著較好的使用前景。但由于現(xiàn)實(shí)中的無線傳感器網(wǎng)絡(luò)往往被布局在復(fù)雜的三維地形中，二維的PB-APIT算法在現(xiàn)實(shí)場景中使用受限，故文中將適用于三維環(huán)境的費(fèi)馬點(diǎn)模型與PB-APIT算法中的分割思想結(jié)合，提出一種基于三角形中線垂面分割的APIT-3D的改進(jìn)算法(簡稱VTM-APIT-3D)。

3 VTM-APIT-3D算法

3.1 算法流程

(1)通過執(zhí)行APIT-3D算法找到所有包含有未知節(jié)點(diǎn)的三棱錐。

(2)在某一三棱錐中找到一個名為費(fèi)馬點(diǎn)的特殊點(diǎn)，將該點(diǎn)鏈接到其他四個頂點(diǎn)，把三棱錐分割成四個部分，然后通過APIT-3D算法判斷哪個子三棱錐中包含有未知節(jié)點(diǎn)。

(3)在該子三棱錐內(nèi)，找到頂點(diǎn)不含費(fèi)馬點(diǎn)的三角形，取其任意一邊作該邊的中線，再過這條中線作三角形面的中線垂面，把該三棱錐劃分為兩部分。

(4)之前執(zhí)行步驟2中的APIT-3D算法時已經(jīng)得出未知節(jié)點(diǎn)從該三角形的三個錨節(jié)點(diǎn)接收到信號的強(qiáng)弱，根據(jù)信號強(qiáng)弱判斷未知節(jié)點(diǎn)位于中線垂面兩側(cè)的哪一側(cè)。若存在兩個錨節(jié)點(diǎn)接收到的信號強(qiáng)度一樣大的情況，則可認(rèn)為未知節(jié)點(diǎn)位于中線垂面兩側(cè)的任意小區(qū)域中。

(5)再通過同樣的方法找到其他包含未知節(jié)點(diǎn)的分割小區(qū)域，通過求這些不規(guī)則小區(qū)域重疊范圍的質(zhì)心來估計(jì)未知節(jié)點(diǎn)的坐標(biāo)。

3.2 三角形中線垂面的定義

VTM-APIT-3D算法中所提到的三角形中線垂面是指在某三角形的任一邊作它的中線，然后過這條線作一個與該三角形所在平面垂直的面，這個面便被稱為三角形中線垂面。如圖1所示，三角形的三個頂點(diǎn)坐標(biāo)分別為A(x1,y1,z1)，B(x2,y2,z2)，C(x3,y3,z3)，M為BC的中點(diǎn)。

直線AM的方程可簡寫為：

(2)

平面ABC的法向量可簡寫為：

(3)

三角形中線垂面AMPQ的方程為：

(4)

如圖1所示，三角形ABC的中線為直線AM，其中線垂面為面AMPQ。通過APIT-3D算法已得知未知節(jié)點(diǎn)N位于三棱錐F-ABCN內(nèi)，且已比較過未知節(jié)點(diǎn)N從三角形ABC的三個錨節(jié)點(diǎn)接收到信號的強(qiáng)弱。若錨節(jié)點(diǎn)B接收到的來自未知節(jié)點(diǎn)N的信號強(qiáng)度比錨節(jié)點(diǎn)C接收到的信號強(qiáng)度都大，則N位于中線垂面偏B的一側(cè)；反之，N位于中線垂面偏C的一側(cè)。

圖1 三角形中線垂面分割模型

4 實(shí)驗(yàn)仿真和結(jié)果分析

本節(jié)對VTM-APIT-3D算法、DFPLE算法和FM-APIT-3D算法的性能進(jìn)行詳細(xì)的對比和分析。仿真模擬實(shí)驗(yàn)在Intel雙核2.3 GHz CPU，4 GB內(nèi)存，Matlab2014a的平臺上進(jìn)行。所采用的網(wǎng)絡(luò)布局為隨機(jī)分布在100 m×100 m×100 m大小的立方體網(wǎng)絡(luò)中的200個節(jié)點(diǎn)，并選中其中N個節(jié)點(diǎn)作為錨節(jié)點(diǎn)，其余為未知節(jié)點(diǎn)。

4.1 性能評估

算法改進(jìn)的目的之一就是提高定位精度，定位精度由定位誤差判斷，定位誤差越小，定位精度越高。未知節(jié)點(diǎn)i的定位誤差計(jì)算公式如下：

(5)

其中，(xi-act,yi-act)為節(jié)點(diǎn)i的實(shí)際位置；(xi-est,yi-est)為節(jié)點(diǎn)i的估計(jì)位置；R為節(jié)點(diǎn)i的通信半徑。

假設(shè)該網(wǎng)絡(luò)中一共有M個節(jié)點(diǎn)，其中N個為錨節(jié)點(diǎn)(i=1至i=N為錨節(jié)點(diǎn)，i=N+1至i=M為未知節(jié)點(diǎn))，則所有未知節(jié)點(diǎn)的平均定位誤差如下：

(6)

下文從定位精度與網(wǎng)絡(luò)覆蓋率的角度，比較VTM-APIT-3D算法、DFPLE算法和FM-APIT-3D算法的性能。

4.2 VTM-APIT-3D算法仿真結(jié)果

取隨機(jī)分布在100 m×100 m×100 m大小的立方體網(wǎng)絡(luò)中的200個節(jié)點(diǎn)進(jìn)行仿真實(shí)驗(yàn)，其中20個節(jié)點(diǎn)為錨節(jié)點(diǎn)，其余為未知節(jié)點(diǎn)。定位結(jié)果如表1所示。

表1 定位結(jié)果分析(R=15)

從表1可以看出，VTM-APIT-3D算法定位精度較高，所有的未知節(jié)點(diǎn)都能被定位且定位誤差較小，因此該算法在優(yōu)化定位方面效果較為理想。

4.3 不同錨節(jié)點(diǎn)數(shù)量下的定位精度

如圖2所示，當(dāng)節(jié)點(diǎn)通信半徑R=16，且錨節(jié)點(diǎn)的數(shù)目N從1逐漸增加到50時，三種算法的定位精度均有所提高。由于參考節(jié)點(diǎn)數(shù)量和測試三棱錐數(shù)量的增加，未知節(jié)點(diǎn)定位的估計(jì)范圍被縮小，定位精度自然就提高了。此外，錨節(jié)點(diǎn)對節(jié)點(diǎn)定位的可能性有直接影響。當(dāng)錨節(jié)點(diǎn)數(shù)量較少時，VTM-APIT-3D算法的定位精度明顯優(yōu)于DFPLE算法和FM-APIT-3D算法。VTM-APIT-3D算法改進(jìn)了定位模塊的劃分，縮小了定位的估計(jì)范圍，加快了定位速度。定位的估計(jì)范圍可減少至其他算法的二分之一。更重要的是，VTM-APIT-3D算法可以解決無法定位的情況，所以定位精度有較大提高。

圖2 不同錨節(jié)點(diǎn)數(shù)量下的平均定位誤差

4.4 不同通信半徑下的定位精度

如圖3所示，當(dāng)錨節(jié)點(diǎn)數(shù)量N=18，且節(jié)點(diǎn)通信半徑R從1逐漸增加到30時，三種算法的平均定位誤差都快速降低。這是因?yàn)镽的增大使未知節(jié)點(diǎn)可以與更多的錨節(jié)點(diǎn)進(jìn)行通信，所以測試三棱錐的數(shù)量不斷增長，節(jié)點(diǎn)的估計(jì)范圍逐漸減小。由于節(jié)點(diǎn)通信半徑的大小對定位精度的影響尤為明顯，可以得出結(jié)論：VTM-APIT-3D算法的定位精度明顯優(yōu)于DFPLE算法和FM-APIT-3D算法。隨著R的增加，一跳通信范圍內(nèi)的錨節(jié)點(diǎn)數(shù)目也會更多，VTM-APIT-3D算法獲得的測試三棱錐數(shù)量也更多。當(dāng)R=30時，VTM-APIT-3D算法的定位精度提高了約17.2%。

圖3 不同通信半徑下的平均定位誤差

5 結(jié)束語

文中提出利用中線垂面切割三維區(qū)域的思想，減少了使用費(fèi)馬點(diǎn)模型的算法中多次把未知節(jié)點(diǎn)估計(jì)在三棱錐形狀的有效范圍內(nèi)造成的累積誤差。仿真結(jié)果表明，與其他使用費(fèi)馬點(diǎn)模型的DFPLE算法和FM-APIT-3D算法相比，利用VTM-APIT-3D算法在三維環(huán)境中對未知節(jié)點(diǎn)進(jìn)行定位，定位精度和網(wǎng)絡(luò)覆蓋率均有明顯提高。當(dāng)無線通信半徑為30時，其定位精度提高至多約17.2%，網(wǎng)絡(luò)覆蓋率始終是100%。當(dāng)然，該算法相對于DFPLE算法和FM-APIT-3D算法而言時間復(fù)雜度較高，網(wǎng)絡(luò)能耗也有所增加，今后的研究方向應(yīng)在提高定位精度和網(wǎng)絡(luò)覆蓋率的同時注重減少定位所需的能量消耗。