無線傳感器網(wǎng)絡(luò)區(qū)域混合感知的APIT定位算法

楊雪，王輝

（南京工業(yè)大學(xué) 電子與信息工程學(xué)院，江蘇 南京211816）

無線傳感器網(wǎng)絡(luò)區(qū)域混合感知的APIT定位算法

楊雪，王輝

（南京工業(yè)大學(xué) 電子與信息工程學(xué)院，江蘇 南京211816）

針對(duì)無線傳感器網(wǎng)絡(luò)的特點(diǎn),在深入分析現(xiàn)有近似三角形內(nèi)點(diǎn)測(cè)試(APIT)定位算法的基礎(chǔ)上，提出一種改進(jìn)機(jī)制，即區(qū)域混合感知的近似三角形內(nèi)點(diǎn)測(cè)試(RMA_APIT)定位算法。該算法根據(jù)網(wǎng)絡(luò)的部署情況，自動(dòng)調(diào)整未知節(jié)點(diǎn)的定位區(qū)域并引入輔助節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)進(jìn)行定位，從而提高定位精度。仿真結(jié)果表明，采用RMA_APIT定位算法，節(jié)點(diǎn)的定位精度和有效定位比都有較大提高。

無線傳感器網(wǎng)絡(luò)；定位；近似三角形內(nèi)點(diǎn)測(cè)試；混合感知；輔助節(jié)點(diǎn)

無線傳感器網(wǎng)絡(luò)(WSNs)的大量應(yīng)用都需要網(wǎng)絡(luò)中節(jié)點(diǎn)的地理位置信息。另外，了解傳感器節(jié)點(diǎn)位置信息還可以提高路由效率，為網(wǎng)絡(luò)提供命名空間，向部署者報(bào)告網(wǎng)絡(luò)的覆蓋質(zhì)量，實(shí)現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡及網(wǎng)絡(luò)拓?fù)涞淖耘渲肹1]。無線傳感器網(wǎng)絡(luò)的定位問題主要分為兩類：(1)無線傳感器網(wǎng)絡(luò)對(duì)自身傳感器節(jié)點(diǎn)的定位；(2)利用傳感器節(jié)點(diǎn)對(duì)外部目標(biāo)的跟蹤定位，而節(jié)點(diǎn)自身的定位是實(shí)現(xiàn)外部目標(biāo)跟蹤定位的基礎(chǔ)[2]。參考文獻(xiàn)[1]對(duì)目前存在的部分定位算法的原理及特點(diǎn)做了詳盡的分析和描述，并給出了定位系統(tǒng)和定位算法的性能評(píng)價(jià)參數(shù)。到目前為止，現(xiàn)有的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法都有各自的特點(diǎn)和應(yīng)用范圍，根據(jù)定位的需求，各算法在性能評(píng)價(jià)參數(shù)上各有取舍,沒有哪一種算法是絕對(duì)優(yōu)秀的。綜合考慮算法的各個(gè)性能評(píng)價(jià)參數(shù)，使節(jié)點(diǎn)的定位精度最優(yōu)是定位算法的主要目標(biāo)。定位算法的分類有很多種,根據(jù)定位過程中是否測(cè)量實(shí)際節(jié)點(diǎn)間的距離，可以把現(xiàn)有的定位算法主要分為兩類:基于距離(Range-based)的定位算法和與距離無關(guān)(Range-free)的定位算法[3]?；诰嚯x的定位算法利用 RSSI、TDOA、TOA和 AOA等技術(shù)測(cè)量節(jié)點(diǎn)之間的距離,然后用數(shù)學(xué)方法計(jì)算節(jié)點(diǎn)的坐標(biāo),該定位算法能夠?qū)崿F(xiàn)節(jié)點(diǎn)的精確定位，但對(duì)節(jié)點(diǎn)的硬件要求比較高。由于硬件成本、能耗等原因，人們提出了與距離無關(guān)的定位技術(shù)。與距離無關(guān)的定位算法對(duì)硬件要求比較低，定位精度隨之降低，但是能夠滿足大多數(shù)應(yīng)用的要求，典型的與距離無關(guān)定位算法主要有MDS算法、DV-HOP算法、Amorphous算法、Centroid算法等。

本文首先深入分析現(xiàn)有近似三角形內(nèi)點(diǎn)測(cè)試(APIT)[4]定位算法的原理和性能，針對(duì)目前該算法仍然存在的問題，并充分考慮無線傳感器網(wǎng)絡(luò)的特點(diǎn)，提出一種區(qū)域混合感知的近似三角形內(nèi)點(diǎn)測(cè)試(RMA_APIT)定位算法。其核心思想是節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)的連接情況應(yīng)用不同的方法感知節(jié)點(diǎn)定位區(qū)域，目的是為了自動(dòng)調(diào)整節(jié)點(diǎn)的定位區(qū)域，從而提高定位精度。通過一系列的仿真實(shí)驗(yàn)證明，RMA_APIT算法能夠很好地適應(yīng)WSNs的特點(diǎn),相比于APIT算法,RMA_APIT算法能夠提供更加精確的定位服務(wù)。

1 RMA_APIT理論模型和算法描述

1.1 APIT算法

APIT 定位算法是一種基于區(qū)域的定位算法[5]，其核心思想是把鄰居錨節(jié)點(diǎn)組成的多個(gè)三角形的交疊區(qū)域的質(zhì)心作為節(jié)點(diǎn)的估計(jì)位置。APIT算法假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)具有獲取鄰居節(jié)點(diǎn)信息的能力，未知節(jié)點(diǎn)在通信傳播過程中獲取所有鄰居錨節(jié)點(diǎn)的信息以及所有鄰居節(jié)點(diǎn)的信息，信息包括鄰居錨節(jié)點(diǎn)的位置信息、未知節(jié)點(diǎn)及鄰居節(jié)點(diǎn)到達(dá)錨節(jié)點(diǎn)的能量信息。假設(shè)未知節(jié)點(diǎn)i共有n個(gè)鄰居錨節(jié)點(diǎn),則n個(gè)鄰居錨節(jié)點(diǎn)可以組成Cn3個(gè)三角形,對(duì)所有包含該未知節(jié)點(diǎn)i的三角形求交疊區(qū)域,交疊區(qū)域的質(zhì)心即為未知節(jié)點(diǎn)i的估計(jì)位置。

APIT算法具有定位精度高、通信開銷小等優(yōu)點(diǎn)[6]，它能夠很好地適應(yīng)WSNs中的節(jié)點(diǎn)定位，但深入研究APIT算法原理及其流程后，可以發(fā)現(xiàn)APIT算法也有不足之處：

(1)未知節(jié)點(diǎn)的鄰居錨節(jié)點(diǎn)數(shù)小于3時(shí)，未知節(jié)點(diǎn)就成為不可定位節(jié)點(diǎn)；

(2)未知節(jié)點(diǎn)具有3個(gè)或者3個(gè)以上鄰居錨節(jié)點(diǎn)，但節(jié)點(diǎn)在任何3個(gè)鄰居錨節(jié)點(diǎn)組成的三角形外部時(shí)，未知節(jié)點(diǎn)就成為不可定位節(jié)點(diǎn)；

(3)未知節(jié)點(diǎn)的鄰居錨節(jié)點(diǎn)數(shù)較少，如只有3個(gè)鄰居錨節(jié)點(diǎn)時(shí)，鄰居錨節(jié)點(diǎn)能組成的三角形數(shù)較少，InToOut錯(cuò)誤或OutToIn錯(cuò)誤對(duì)節(jié)點(diǎn)的定位有較大影響；

(4)未知節(jié)點(diǎn)在部署區(qū)域的邊緣時(shí)，未知節(jié)點(diǎn)的某一側(cè)不會(huì)出現(xiàn)鄰居錨節(jié)點(diǎn)，這樣會(huì)使得未知節(jié)點(diǎn)不在鄰居錨節(jié)點(diǎn)組成的三角形內(nèi)部，導(dǎo)致未知節(jié)點(diǎn)成為不可定位節(jié)點(diǎn)。

針對(duì)APIT存在的諸多弊端，本文提出一種改進(jìn)算法，即區(qū)域混合感知的APIT定位算法(RMA_APIT)。該算法根據(jù)網(wǎng)絡(luò)連接情況，對(duì)節(jié)點(diǎn)的定位區(qū)域進(jìn)行了調(diào)整，以減少不可定位節(jié)點(diǎn)數(shù)目及提高節(jié)點(diǎn)定位精度。

1.2 網(wǎng)絡(luò)模型及假設(shè)

為方便對(duì)RMA_APIT算法進(jìn)行理論闡述,假設(shè)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)部署在邊長(zhǎng)為R的正方形區(qū)域內(nèi)。網(wǎng)絡(luò)中普通節(jié)點(diǎn)的通信半徑γ，錨節(jié)點(diǎn)的通信半徑是普通節(jié)點(diǎn)的α(α＞1)倍，節(jié)點(diǎn)的鄰居錨節(jié)點(diǎn)數(shù)閾值為 K。網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都可以獲得鄰居節(jié)點(diǎn)的信息。另外，根據(jù)無線傳感器網(wǎng)絡(luò)在應(yīng)用中的特點(diǎn)，模型假設(shè)節(jié)點(diǎn)的通信區(qū)域不一定為理想的圓形區(qū)域。

1.3 RMA_APIT算法

仔細(xì)分析APIT算法存在的問題可以發(fā)現(xiàn)，應(yīng)用APIT算法不能進(jìn)行定位的節(jié)點(diǎn)可以分為兩類：第一類，鄰居錨節(jié)點(diǎn)數(shù)大于等于3而不能進(jìn)行定位的未知節(jié)點(diǎn)；第二類,鄰居錨節(jié)點(diǎn)數(shù)小于3而不能進(jìn)行定位的未知節(jié)點(diǎn)。

為有效減少第一類不可定位節(jié)點(diǎn)的數(shù)目，不是直接判斷未知節(jié)點(diǎn)i是否在錨節(jié)點(diǎn)組成的三角形MNP內(nèi)部，而是在節(jié)點(diǎn)進(jìn)行定位前判斷未知節(jié)點(diǎn)的鄰居錨節(jié)點(diǎn)數(shù)是否大于閾值K，若大于則用APIT進(jìn)行定位；若節(jié)點(diǎn)的鄰居錨節(jié)點(diǎn)數(shù)小于等于閾值K，如圖1所示，圖中設(shè)K=3，則采用下述區(qū)域混合感知技術(shù)進(jìn)行定位。

首先，如圖1所示，圖中三角形實(shí)心點(diǎn)表示錨節(jié)點(diǎn)，圓形實(shí)心點(diǎn)表示普通節(jié)點(diǎn)，錨節(jié)點(diǎn)的通信區(qū)域是以錨節(jié)點(diǎn)為圓心、錨節(jié)點(diǎn)通信半徑αγ為半徑的圓形區(qū)域，且未知節(jié)點(diǎn)一定在其鄰居錨節(jié)點(diǎn)的通信區(qū)域內(nèi)，所以未知節(jié)點(diǎn)i一定在其鄰居錨節(jié)點(diǎn) M、N、P通信區(qū)域的交疊區(qū)域內(nèi)，即圖中A區(qū)域。

然后判斷未知節(jié)點(diǎn)是否在錨節(jié)點(diǎn)M、N、P組成的三角形內(nèi)部。若未知節(jié)點(diǎn)i不在三角形MNP內(nèi)部或In-ToOut錯(cuò)誤時(shí)，則A區(qū)域即為未知節(jié)點(diǎn)i的定位區(qū)域，即A區(qū)域的質(zhì)心位置為未知節(jié)點(diǎn)i的估計(jì)位置，如圖1(a)所示。若未知節(jié)點(diǎn)i在三角形MNP的內(nèi)部，則用三角形MNP與A區(qū)域的交疊區(qū)域作為未知節(jié)點(diǎn)i的定位區(qū)域，即圖1(b)中的B區(qū)域，B區(qū)域的質(zhì)心即為未知節(jié)點(diǎn)i的估計(jì)位置。通過區(qū)域混合感知技術(shù)可對(duì)鄰居錨節(jié)點(diǎn)數(shù)小于閾值K的未知節(jié)點(diǎn)進(jìn)行更加精確的定位。

針對(duì)第二類不能定位節(jié)點(diǎn)，本文引入輔助節(jié)點(diǎn)進(jìn)行定位。首先對(duì)整個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行第一輪定位，記錄下不能定位的節(jié)點(diǎn)j；然后判斷未知節(jié)點(diǎn)j的鄰居錨節(jié)點(diǎn)數(shù)與已經(jīng)被定位的鄰居節(jié)點(diǎn)數(shù)之和是否大于等于3個(gè)，如果未知節(jié)點(diǎn)j的鄰居錨節(jié)點(diǎn)數(shù)與已經(jīng)被定位的鄰居節(jié)點(diǎn)數(shù)之和大于等于3個(gè),則把已經(jīng)定位的鄰居節(jié)點(diǎn)當(dāng)做輔助錨節(jié)點(diǎn),應(yīng)用RMA_APIT算法對(duì)未知節(jié)點(diǎn)j進(jìn)行第二輪定位，否則未知節(jié)點(diǎn)視為不可定位節(jié)點(diǎn)，如圖2所示，圖中三角形空心點(diǎn)表示輔助錨節(jié)點(diǎn)。

基于以上描述，給出RMA_APIT定位算法的執(zhí)行流程圖，如圖3所示。

2 仿真結(jié)果及分析

為了有效評(píng)估RMA_APIT算法的性能，本文通過仿真實(shí)驗(yàn)的方法將其與APIT算法進(jìn)行比較分析。

2.1 仿真實(shí)驗(yàn)設(shè)計(jì)

影響節(jié)點(diǎn)定位精度的因素很多，本實(shí)驗(yàn)主要選擇節(jié)點(diǎn)數(shù)目、錨節(jié)點(diǎn)比重和節(jié)點(diǎn)無線傳輸模式的不規(guī)則度作為仿真參數(shù)，觀察這些參數(shù)變化對(duì)節(jié)點(diǎn)定位精度和節(jié)點(diǎn)有效定位比的影響。參數(shù)定義如下：節(jié)點(diǎn)數(shù)目定義為部署區(qū)域內(nèi)的節(jié)點(diǎn)總數(shù)，包括普通節(jié)點(diǎn)和錨節(jié)點(diǎn)，用N表示；錨節(jié)點(diǎn)比重為錨節(jié)點(diǎn)數(shù)與節(jié)點(diǎn)數(shù)目的比例，用Ar表示；節(jié)點(diǎn)有效定位比定義為能夠被定位的節(jié)點(diǎn)數(shù)(Nl)占節(jié)點(diǎn)數(shù)目的比例，如式(1)所示，用ELR表示。

實(shí)驗(yàn)中具體的參數(shù)取值見表1。

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

2.2 仿真結(jié)果分析

圖4和圖5分別給出了節(jié)點(diǎn)數(shù)目對(duì)節(jié)點(diǎn)定位精度及ELR的影響。從圖4中可以看出，隨著節(jié)點(diǎn)數(shù)目的增加，兩種算法的定位精度都在提高，但在相同節(jié)點(diǎn)數(shù)目的情況下，RMA_APIT算法的定位精度比APIT算法的定位精度高。圖5仿真結(jié)果顯示節(jié)點(diǎn)有效定位比隨著節(jié)點(diǎn)數(shù)目增加而增加；在節(jié)點(diǎn)數(shù)目很低或很高時(shí)，兩種算法的節(jié)點(diǎn)有效定位比很接近，節(jié)點(diǎn)數(shù)目在100～350之間時(shí)，RMA_APIT算法的節(jié)點(diǎn)有效定位比明顯高于APIT算法的節(jié)點(diǎn)有效定位比，這是因?yàn)樵诠?jié)點(diǎn)數(shù)目很低時(shí)，未知節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)目都很少，RMA_APIT算法的區(qū)域混合感知技術(shù)受到限制，能夠引入輔助節(jié)點(diǎn)進(jìn)行定位的節(jié)點(diǎn)數(shù)少，故節(jié)點(diǎn)有效定位比不會(huì)有明顯提高；在節(jié)點(diǎn)數(shù)目很高時(shí)，兩種定位算法的節(jié)點(diǎn)有效定位比都接近1，因此也比較接近；當(dāng)節(jié)點(diǎn)數(shù)目在 100～350之間時(shí)，RMA_APIT算法能夠很好地調(diào)整未知節(jié)點(diǎn)的定位區(qū)域，并引入輔助節(jié)點(diǎn)進(jìn)行定位，可以很好地減少不能定位的節(jié)點(diǎn)數(shù)，故RMA_APIT算法的節(jié)點(diǎn)有效定位比要明顯高于APIT算法的節(jié)點(diǎn)有效定位比。

圖6和圖7顯示了錨節(jié)點(diǎn)比重對(duì)節(jié)點(diǎn)定位精度和ELR的影響。仿真的節(jié)點(diǎn)數(shù)目為200時(shí)，錨節(jié)點(diǎn)比重從0.05逐漸增加到0.4。從仿真結(jié)果可以看出，隨著錨節(jié)點(diǎn)比重的增加，RMA_APIT算法和APIT算法的定位精度與節(jié)點(diǎn)有效定位比ELR都在增加。在錨節(jié)點(diǎn)比重相同的情況下，RMA_APIT算法的節(jié)點(diǎn)有效定位比全部大于APIT算法的節(jié)點(diǎn)有效定位比，RMA_APIT算法的定位精度也普遍比APIT算法的定位精度高，只有在錨節(jié)點(diǎn)比重很小(Ar=0.05)時(shí)，RMA_APIT算法的定位精度比 APIT算法的定位精度稍低，這是因?yàn)殄^節(jié)點(diǎn)數(shù)太少會(huì)導(dǎo)致節(jié)點(diǎn)定位誤差較大，若再引入輔助節(jié)點(diǎn)進(jìn)行定位，會(huì)使誤差累積太大，從而影響RMA_APIT算法在低錨節(jié)點(diǎn)比重場(chǎng)景下的整體性能。

3 結(jié)論與展望

節(jié)點(diǎn)定位技術(shù)是WSNs中關(guān)鍵的支撐技術(shù)之一。本文對(duì)APIT定位算法進(jìn)行改進(jìn)，提出了區(qū)域混合感知的近似三角形內(nèi)點(diǎn)測(cè)試(RMA_APIT)定位算法。RMA_APIT算法根據(jù)網(wǎng)絡(luò)連接情況，對(duì)未知節(jié)點(diǎn)的定位區(qū)域進(jìn)行調(diào)整并引入輔助節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)定位。仿真實(shí)驗(yàn)結(jié)果證明，RMA_APIT算法能夠適應(yīng)無線傳感器網(wǎng)絡(luò)的特點(diǎn)，相比于APIT算法，在節(jié)點(diǎn)數(shù)目相同、錨節(jié)點(diǎn)比重相同的情況下，RMA_APIT算法能夠提供更加優(yōu)質(zhì)的定位服務(wù)，在獲得相同定位精度的要求下，RMA_APIT算法更能節(jié)省網(wǎng)絡(luò)部署的成本。下一步的工作是研究網(wǎng)絡(luò)模型及網(wǎng)絡(luò)部署情況對(duì)算法的影響，使算法能夠在更加真實(shí)的網(wǎng)絡(luò)環(huán)境中取得理想的定位效果。

[1]王福豹,史龍,任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報(bào),2005,16(5):857-868

[2]周四清,陳銳標(biāo).無線傳感器網(wǎng)絡(luò)APIT定位算法及其改進(jìn)[J].計(jì)算機(jī)工程,2009,35(7):87-89.

[3]馮秀芳,崔秀鋒,祈會(huì)波.無線傳感器網(wǎng)絡(luò)中基于移動(dòng)錨節(jié)點(diǎn)的APIT的改進(jìn)定位算法[J].傳感技術(shù)學(xué)報(bào),2011,24(2):269-274.

[4]HE T,HUANG C,BLUM B M,et al.Range-free localization schemes for large scale sensor networks[C].Proceedings of ACM MobiCom,San Diego,California,USA,2003:81-95.

[5]MA D,Meng J E,Wang Bang,et al.Range-free wireless sensor networks localization based on hop-count quantization[J].Springer,2010,DOI:10.1007/s11235-010-9395-y.

[6]周勇,夏士雄,丁士飛,等.基于三角形重心掃描的改進(jìn)APIT無線傳感器網(wǎng)絡(luò)自定位算法[J].計(jì)算機(jī)研究與發(fā)展,2009,46(4):566-574.

A region mixed-aware APIT algorithm for WSNs

Yang Xue,Wang Hui
(College of Electronics and Information Engineering,Nanjing University of Technology,Nanjing 211816,China)

This work begins with a thorough investigation of APIT localization algorithm.On this basis,a region mixed-aware algorithm(RMA_APIT)is proposed.Based on the deployment of the network,RAM_APIT adjusts the positioning area of the unknown node automatically and introduces assistant nodes that used to position the unknown node,thereby improving positioning accuracy.Simulation results show that RAM_APIT algorithm improves positioning accuracy of a node and the ratio of effective localization nodes significantly.

WSNs;localization;APIT;mixed-aware;assistant node

TP393

A

0258-7998(2012)03-0113-04

2011-09-24)

楊雪，女，1986年生，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)。

王輝，女，1962年生，博士，教授，碩士生導(dǎo)師，主要研究方向：光傳輸理論與系統(tǒng)、信號(hào)處理與控制技術(shù)。