基于迭代分割的無(wú)線傳感器網(wǎng)絡(luò)定位算法

張婧，國(guó)晶

（長(zhǎng)春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春 130022）

隨著物聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)（WSNs，wireless sensor networks）憑借著其低成本、微型化、低功耗和靈活的組網(wǎng)方式、鋪設(shè)方式以及適合移動(dòng)目標(biāo)等特點(diǎn)稱為物聯(lián)網(wǎng)的底層支撐技術(shù)［1］。它正被廣泛的應(yīng)用在國(guó)防、醫(yī)療、環(huán)境、目標(biāo)跟蹤等多個(gè)領(lǐng)域。明確傳感器節(jié)點(diǎn)的具體位置，是大多數(shù)應(yīng)用服務(wù)中不可或缺的一部分。例如：在國(guó)防中只有知道突發(fā)事件（如槍聲、爆炸等）的具體位置，軍隊(duì)才能夠?qū)κ掳l(fā)地及時(shí)采取應(yīng)對(duì)措施；對(duì)于環(huán)境監(jiān)測(cè)中只有知道火災(zāi)的準(zhǔn)確方位才能指導(dǎo)消防人員進(jìn)行撲火操作；對(duì)于入侵監(jiān)控，只有知道入侵者的行動(dòng)軌跡才能進(jìn)行追蹤［2］。因此，無(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)是大多數(shù)應(yīng)用的基礎(chǔ)，如果只知道發(fā)生的事件，卻不知道具體的位置，感知的數(shù)據(jù)可能失去意義。同時(shí)，明確傳感器節(jié)點(diǎn)所在的位置，可以提高網(wǎng)絡(luò)的路由效率，實(shí)現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡和網(wǎng)絡(luò)拓?fù)涞淖耘渲茫拐麄€(gè)網(wǎng)絡(luò)的覆蓋質(zhì)量得到提升［3］。因此，無(wú)線傳感器網(wǎng)絡(luò)定位是一項(xiàng)必不可少的關(guān)鍵技術(shù)。

目前，利用全球定位系統(tǒng)（GPS）來(lái)獲取節(jié)點(diǎn)的位置信息是比較簡(jiǎn)單且常用的方法。然而，由于昂貴的硬件和能源問(wèn)題，在每個(gè)節(jié)點(diǎn)上部署GPS顯然不符合WSN中普通節(jié)點(diǎn)成本低、體積小的要求。因此，通常利用少量已知位置信息的節(jié)點(diǎn)（信標(biāo)節(jié)點(diǎn)），并通過(guò)一些定位算法來(lái)實(shí)現(xiàn)對(duì)未知節(jié)點(diǎn)的定位［2］。無(wú)線傳感器網(wǎng)絡(luò)的定位算法可根據(jù)是否需要測(cè)量節(jié)點(diǎn)間的歐氏距離或角度分為基于測(cè)距的定位算法與非測(cè)距的定位算法。其中基于測(cè)距的定位算法有TOA（基于時(shí)間的定位方法）［4］、TDOA（基于信號(hào)傳輸時(shí)間差的定位方法）［5］、AOA（基于信號(hào)角度的定位方法）［6］以及RSSI（基于信號(hào)強(qiáng)度的定位方法）［7-8］等。非測(cè)距定位算法主要有質(zhì)心算法［9］、APIT算法［10］、DV-Hop算法［11-12］等。由于非測(cè)距的定位算法無(wú)需增加額外的硬件成本，算法簡(jiǎn)單易實(shí)現(xiàn)，在能耗方面相比測(cè)距的定位算法有一定的優(yōu)勢(shì)，因而針對(duì)非測(cè)距算法中的APIT進(jìn)行改進(jìn)將有一定意義。

國(guó)內(nèi)外學(xué)者針對(duì)APIT定位算法中存在的定位精度低的問(wèn)題，提出了不少改進(jìn)的方法。當(dāng)未知節(jié)點(diǎn)鄰近信標(biāo)節(jié)點(diǎn)分布不均勻或者未知節(jié)點(diǎn)靠近由信標(biāo)節(jié)點(diǎn)組成三角形的某一條邊時(shí)，APIT算法可能會(huì)產(chǎn)生節(jié)點(diǎn)誤判（內(nèi)部節(jié)點(diǎn)誤判成外部節(jié)點(diǎn)或外部節(jié)點(diǎn)誤判成內(nèi)部節(jié)點(diǎn)）。針對(duì)節(jié)點(diǎn)誤判產(chǎn)生的誤差，文獻(xiàn)［13］利用三角形面積或角度和的方法對(duì)節(jié)點(diǎn)產(chǎn)生的誤判進(jìn)行修正。但由于RSSI測(cè)距具有不準(zhǔn)確性，無(wú)法得到精確的面積或角度之和，因而使得未知節(jié)點(diǎn)無(wú)法準(zhǔn)確定位。文獻(xiàn)［14］通過(guò)部署虛擬信標(biāo)節(jié)點(diǎn)雖然能夠有效判斷未知節(jié)點(diǎn)在三角形的內(nèi)部還是外部，但部署虛擬信標(biāo)節(jié)點(diǎn)會(huì)消耗較多的計(jì)算資源以及時(shí)間。文獻(xiàn)［15］提出了一種協(xié)同系數(shù)APIT定位算法，利用RSSI測(cè)距和加權(quán)三角坐標(biāo)的計(jì)算方法來(lái)對(duì)未知節(jié)點(diǎn)進(jìn)行定位。雖然達(dá)到了減少定位誤差和擴(kuò)展定位覆蓋率的效果，但該方法大大增加了硬件成本以及能耗。因此，綜合各個(gè)改進(jìn)算法的優(yōu)勢(shì)與弊端，將改進(jìn)的APIT算法以及質(zhì)心算法相融合，能夠有效地提高APIT算法的定位覆蓋率以及定位精度。

1 APIT定位算法

1.1 APIT算法定位原理

APIT是一種實(shí)現(xiàn)成本較低、操作簡(jiǎn)單、易于實(shí)現(xiàn)并且定位精度較高的算法。它的基本原理是未知節(jié)點(diǎn)首先收集鄰近信標(biāo)節(jié)點(diǎn)的信息，然后從這些信標(biāo)節(jié)點(diǎn)中任意選取三個(gè)節(jié)點(diǎn)組成三角形。假設(shè)集合中有n個(gè)信標(biāo)節(jié)點(diǎn)，則共有種不同的選取方法。通過(guò)這些不同的選取方法逐一判斷未知節(jié)點(diǎn)是否位于每個(gè)三角形的內(nèi)部。最后，通過(guò)計(jì)算包含目標(biāo)節(jié)點(diǎn)所在的三角形的重疊區(qū)域的質(zhì)心，并將質(zhì)心作為未知節(jié)點(diǎn)所在的位置。如圖1所示，P點(diǎn)為重疊區(qū)域的質(zhì)心，即未知節(jié)點(diǎn)所在的位置［10，13］。

圖1 APIT定位原理

由于在無(wú)線傳感器網(wǎng)絡(luò)中大多數(shù)節(jié)點(diǎn)都是靜止的，所以APIT利用網(wǎng)絡(luò)中相對(duì)較高的節(jié)點(diǎn)密度來(lái)模擬節(jié)點(diǎn)移動(dòng)，利用無(wú)線信號(hào)的傳播強(qiáng)弱來(lái)描述是否遠(yuǎn)離或靠近信標(biāo)節(jié)點(diǎn)。其判定原理如圖2所示，如果節(jié)點(diǎn)P運(yùn)動(dòng)至1的位置，將同時(shí)遠(yuǎn)離信標(biāo)節(jié)點(diǎn)A、B、C，則P點(diǎn)在DABC外。另外，如果節(jié)點(diǎn)P運(yùn)動(dòng)至節(jié)點(diǎn)1的位置，將靠近A遠(yuǎn)離B、C，并依次對(duì)2、3、4進(jìn)行相同的判斷，則可判定未知節(jié)點(diǎn)P在DABC內(nèi)。

圖2 PIT原理

1.2 APIT算法存在的誤差

（1）In-To-Out和Out-To-In錯(cuò)誤

在APIT定位算法中，當(dāng)節(jié)點(diǎn)的密度較低時(shí)，可能會(huì)產(chǎn)生內(nèi)部節(jié)點(diǎn)錯(cuò)判成外部節(jié)點(diǎn)（In-To-Out）和外部節(jié)點(diǎn)錯(cuò)判成內(nèi)部節(jié)點(diǎn)（Out-To-In）的錯(cuò)誤。如圖3（a）所示，當(dāng)未知節(jié)點(diǎn)P模擬運(yùn)動(dòng)2或3的位置時(shí)，未知節(jié)點(diǎn)P沒(méi)有同時(shí)靠近或遠(yuǎn)離三個(gè)信標(biāo)節(jié)點(diǎn)A、B、C，則可能發(fā)生Out-To-In錯(cuò)誤［15］。同理，圖3（b）未知節(jié)點(diǎn)P模擬運(yùn)動(dòng)到4的位置時(shí)，同時(shí)遠(yuǎn)離三個(gè)信標(biāo)節(jié)點(diǎn)，則被判定未知節(jié)點(diǎn)在三角形外，可能產(chǎn)生 In-To-Out錯(cuò)誤［15］。

（2）重疊區(qū)域過(guò)大引起的誤差

當(dāng)節(jié)點(diǎn)分布不均勻或部分未知節(jié)點(diǎn)鄰近的信標(biāo)節(jié)點(diǎn)數(shù)量較少時(shí)，可能會(huì)導(dǎo)致包含目標(biāo)節(jié)點(diǎn)所在的三角形的重疊區(qū)域過(guò)大，進(jìn)而將其重疊區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的坐標(biāo)會(huì)造成較大的誤差。

圖3 誤差分析

2 改進(jìn)的APIT算法

2.1 三角形內(nèi)點(diǎn)的判定

為了盡量減少APIT算法中的In-To-Out和Out-To-In引起的誤差以及盡可能的提高定位精度。判定內(nèi)點(diǎn)的方法如下：

根據(jù)同向法對(duì)節(jié)點(diǎn)進(jìn)行判定。同向法的基本原理為：假設(shè)存在一個(gè)點(diǎn)P以及DABC。判斷P點(diǎn)是否在DABC內(nèi)。則需判斷：

（1）P點(diǎn)和A點(diǎn)在BC這條直線的同一側(cè)；

（2）P點(diǎn)和B點(diǎn)在AC這條直線的同一側(cè)；

（3）P點(diǎn)和C點(diǎn)在AB這條直線的同一側(cè)。

同時(shí)滿足上述三種條件，則證明P點(diǎn)在DABC內(nèi)，否則，P點(diǎn)在DABC外。

如圖4所示，判斷P點(diǎn)和A點(diǎn)在BC這條直線的同一側(cè)，則過(guò)A點(diǎn)作BC的垂線交于F點(diǎn)，即∠AFB=∠AFC=90°。

若P點(diǎn)和A點(diǎn)在同一側(cè)，

則∠AFP＜∠AFB，∠AFP＜∠AFC

故∠AFP＜90°

否則，∠AFP＞90°

圖4 同側(cè)判定方法

通過(guò)上述證明，同理如圖5所示，可得到如下命題：

命題1：若未知節(jié)點(diǎn)P在由三個(gè)信標(biāo)節(jié)點(diǎn)組成的DABC內(nèi)，則∠AFP，∠BHP，∠CMP的角度均小于90°。

命題2：若未知節(jié)點(diǎn)P在由三個(gè)信標(biāo)節(jié)點(diǎn)組成的DABC外，則∠AFP，∠BHP，∠CMP中必然存在一個(gè)角大于90°。

其中F、H、M分別為A點(diǎn)、B點(diǎn)、C點(diǎn)到對(duì)邊的垂足。

圖5 角度判定

相應(yīng)角度的計(jì)算方式如下：

（1）通過(guò)RSSI測(cè)距的數(shù)學(xué)模型公式［9］：

式中，d0為參考距離；Pr(d0)表示無(wú)線信號(hào)對(duì)應(yīng)的接收功率；Pr(d)為接收機(jī)接收到的無(wú)線射頻信號(hào)功率；n為傳播因子；d表示信號(hào)的發(fā)射機(jī)器與接收機(jī)器之間的距離，即未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的距離。

（2）如圖6所示，通過(guò)兩點(diǎn)間的距離公式求出三個(gè)信標(biāo)節(jié)點(diǎn)A（x1，y1），B（x2，y2），C（x3，y3）之間的距離為：

（3）由點(diǎn)到直線的距離公式求出AF的距離：

其中已知A、C的坐標(biāo)，則a=y3-y2，b=x2-x3，c=x3×y2-x2×y3。

由余弦定理可得：

（4）求出判定角度：

圖6 角度計(jì)算

如果存在某一個(gè)三角形包含未知節(jié)點(diǎn)，則該三角形被定義為有效三角形。為了得到更精確的定位結(jié)果，即對(duì)有效三角形可進(jìn)行區(qū)域的劃分與迭代，最終求出未知節(jié)點(diǎn)的坐標(biāo)。

2.2 有效三角形的劃分與迭代

為了進(jìn)一步提高未知節(jié)點(diǎn)的定位精度，在判定未知節(jié)點(diǎn)在三個(gè)信標(biāo)節(jié)點(diǎn)所組成的三角形內(nèi)之后，可以通過(guò)作垂線的方法來(lái)縮小未知節(jié)點(diǎn)所在區(qū)域。如圖7所示，A，B，C為信標(biāo)節(jié)點(diǎn)。在DABC內(nèi)，角度由小到大的排列順序?yàn)椤螦，∠B，∠C，過(guò)C點(diǎn)作AB的垂線交于F點(diǎn)，即可求出最小角度A、垂足F以及未知節(jié)點(diǎn)P組成的角度∠AFP的大小。若∠AFP＞90°，則未知節(jié)點(diǎn)P在DBCF內(nèi)，否則，未知節(jié)點(diǎn)P在DACF內(nèi)。

圖7 區(qū)域劃分

通過(guò)上述方法進(jìn)行迭代分割，可得到如圖8所示的迭代示意圖。P點(diǎn)為未知節(jié)點(diǎn)，三個(gè)信標(biāo)節(jié)點(diǎn)組成的三角形為DABC，最大角度為∠C，最小角度為∠A。迭代過(guò)程如下：

（1）過(guò)A點(diǎn)作BC的垂線交于F點(diǎn)，求出F點(diǎn)的坐標(biāo)以及通過(guò)RSSI測(cè)距得到AP、BP、CP的距離；

（2）利用余弦定理可求出∠AFP角度。

（3）若 ∠AFP＞90°，則P點(diǎn)在DABF區(qū)域。否則，P點(diǎn)在DACF區(qū)域并保留P點(diǎn)所在的區(qū)域。假設(shè)P點(diǎn)在DABF區(qū)域，即令DABF中的最大角度為∠A，最小角度為∠C。

（4）重復(fù)以上步驟，直到P點(diǎn)所在的三角形區(qū)域?yàn)榫W(wǎng)格所能查找到的最小定位的區(qū)域（利用網(wǎng)格掃描法［16］所能探測(cè)到的最小單元格區(qū)域）為止。

（5）迭代結(jié)束。

圖8 迭代示例圖

綜上，改進(jìn)APIT算法的流程圖如圖9所示。

圖9 APIT算法流程圖

3 算法仿真

為了驗(yàn)證算法的有效性，通過(guò)MATLAB分別利用原始APIT算法、文獻(xiàn)［13］提出基于角度和改進(jìn)的APIT算法以及基于迭代分割的無(wú)線傳感器網(wǎng)絡(luò)定位算法進(jìn)行仿真實(shí)驗(yàn)，并結(jié)合實(shí)驗(yàn)數(shù)據(jù)對(duì)三個(gè)算法進(jìn)行性能分析與比較。實(shí)驗(yàn)場(chǎng)景設(shè)定在1 000 m×1 000 m的二維平面內(nèi)，節(jié)點(diǎn)隨機(jī)分布在監(jiān)測(cè)區(qū)域內(nèi)。

在仿真實(shí)驗(yàn)中，RSSI的各個(gè)參數(shù)值如表1所示。

表1 實(shí)驗(yàn)參數(shù)

場(chǎng)景1：設(shè)定通信半徑R=100，節(jié)點(diǎn)總數(shù)N=300。平均運(yùn)行50次，可得到如表2所示數(shù)據(jù)。

通過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)表2的分析，可得出當(dāng)節(jié)點(diǎn)總數(shù)不變時(shí)，待定位節(jié)點(diǎn)的平均定位誤差和信標(biāo)節(jié)點(diǎn)比例之間的關(guān)系，如圖10所示。

圖10 節(jié)點(diǎn)比例與定位誤差對(duì)比圖

原始APIT算法和文獻(xiàn)［13］利用角度和改進(jìn)的APIT算法的平均定位誤差隨著信標(biāo)節(jié)點(diǎn)比例的增加而減小。這是因?yàn)樾艠?biāo)節(jié)點(diǎn)比例增加的同時(shí)，包含未知節(jié)點(diǎn)所在的三角形的重疊區(qū)域會(huì)隨之減小，使得定位誤差越來(lái)越小。如圖10所示，基于迭代分割的無(wú)線傳感器定位算法隨著信標(biāo)節(jié)點(diǎn)比例的增加，定位誤差趨于穩(wěn)定且一直保持較高的精度。因?yàn)榛诘指畹臒o(wú)線傳感器定位算法運(yùn)用最小三角形迭代思想求出包含未知節(jié)點(diǎn)的最小區(qū)域代替原始算法中多個(gè)三角形的重疊區(qū)域。總之，兩種改進(jìn)算法的定位精度均高于原始APIT算法的定位精度，并且基于迭代分割的無(wú)線傳感器定位算法的定位精度最高。

場(chǎng)景2：設(shè)定通信半徑R=100，信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)為：anchors=nodes·ρ，ρ=0.3。平均運(yùn)行50次，可得到如表2所示數(shù)據(jù)。

通過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)表3的分析，得到待定位節(jié)點(diǎn)的平均定位誤差和節(jié)點(diǎn)數(shù)量之間的關(guān)系，如圖11所示。

圖11 節(jié)點(diǎn)數(shù)量與定位誤差對(duì)比圖

表2 實(shí)驗(yàn)數(shù)據(jù)

表3 實(shí)驗(yàn)數(shù)據(jù)

當(dāng)信標(biāo)節(jié)點(diǎn)比例不變時(shí)，隨著區(qū)域內(nèi)節(jié)點(diǎn)數(shù)量的增加，使得待定位節(jié)點(diǎn)鄰近信標(biāo)節(jié)點(diǎn)的數(shù)量不斷增加，故節(jié)點(diǎn)的平均定位誤差的變化趨勢(shì)同樣會(huì)隨著節(jié)點(diǎn)數(shù)量的增加而減小。基于迭代分割的無(wú)線傳感器網(wǎng)絡(luò)定位算法的定位精度明顯優(yōu)于原始APIT算法和文獻(xiàn)［13］利用角度和改進(jìn)的APIT算法的定位精度。

通過(guò)場(chǎng)景1與場(chǎng)景2的比較分析，基于迭代分割的無(wú)線傳感器網(wǎng)絡(luò)定位算法的定位精度比利用角度和改進(jìn)的APIT算法平均提高15.1%，較原始APIT算法平均提高24.6%。

4 結(jié)論

針對(duì)APIT定位算法存在的誤差，基于迭代分割的無(wú)線傳感器定位算法主要從兩個(gè)方面進(jìn)行了誤差修正。首先，對(duì)于APIT算法存在的兩種典型錯(cuò)誤In-To-Out和Out-To-In錯(cuò)誤，引入了一種新的判斷內(nèi)部節(jié)點(diǎn)的方法，該方法能夠有效的避免上述兩種錯(cuò)誤的產(chǎn)生；其次，當(dāng)未知節(jié)點(diǎn)被判定在三角形內(nèi)部的情況下，利用迭代分割方法進(jìn)一步縮小三角形區(qū)域，從而確定最終定位區(qū)域。通過(guò)上述兩種方法進(jìn)行了多次仿真實(shí)驗(yàn)，結(jié)果表明，基于迭代分割的無(wú)線傳感器定位算法可有效降低定位誤差，且當(dāng)信標(biāo)節(jié)點(diǎn)比例不高或者節(jié)點(diǎn)密度變大時(shí)能夠保持算法的穩(wěn)定性。