安徽理工大學(xué) 戴海祥 洪 炎 楊東東 黃國維 丁冰倩

無線傳感器網(wǎng)絡(luò)非測距定位算法比較

安徽理工大學(xué) 戴海祥 洪 炎 楊東東 黃國維 丁冰倩

基于非測距技術(shù)的定位方法沒必要知道節(jié)點(diǎn)間距離，因此對硬件的要求較低，在無線傳感網(wǎng)絡(luò)中被廣泛的應(yīng)用。通過對各種非測距定位算法的原理分析，從節(jié)點(diǎn)的分布密度、測量誤差、硬件消耗、分布形式、擴(kuò)展性等方面對無線傳感器網(wǎng)絡(luò)非測距定位算法進(jìn)行比較，分析出各算法的優(yōu)缺點(diǎn)及可應(yīng)用的范圍，對無線傳感網(wǎng)絡(luò)定位算法的研究和選擇有重要意義。

無線傳感網(wǎng)絡(luò)；非測距定位算法

0 引言

基于非測距技術(shù)的定位方法顧名思義就是不需要知道兩個節(jié)點(diǎn)之間的距離為多少，因此在硬件方面這類算法的要求相比于其他算法較低，在無線傳感網(wǎng)絡(luò)中被廣泛的應(yīng)用。目前該定位算法主要有兩類，一種是對節(jié)點(diǎn)間距離進(jìn)行估計，再用三邊定位算法進(jìn)行定位；另一種是通過節(jié)點(diǎn)間信息的交互逐漸縮小未知節(jié)點(diǎn)所在的區(qū)域，反復(fù)多次后將區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的位置。

1 質(zhì)心定位算法

該算法的原理是，信標(biāo)節(jié)點(diǎn)不斷發(fā)送自己的位置、ID等信息，在通信范圍內(nèi)的待測節(jié)點(diǎn)接受這些信息，當(dāng)待測節(jié)點(diǎn)接受到信息的信標(biāo)節(jié)點(diǎn)的個數(shù)超過三個時，就可以將信標(biāo)節(jié)點(diǎn)組成的幾何圖形的質(zhì)心作為待測節(jié)點(diǎn)的最終位置。公式如(1)所示：

其中，（xi，yi）為待測節(jié)點(diǎn)通信范圍內(nèi)能夠進(jìn)行信息交互的信標(biāo)節(jié)點(diǎn)坐標(biāo)，（x，y）為待測節(jié)點(diǎn)坐標(biāo)。

2 APIT定位算法

APIT定位算法簡單來說就是從與待測節(jié)點(diǎn)能夠進(jìn)行信息交互的鄰居節(jié)點(diǎn)中任意取出3個組成三角形，然后用PIT判定法來判斷待測節(jié)點(diǎn)和三角形的位置關(guān)系，按照以上的方法核對所有的三角形組合，最終得出待測節(jié)點(diǎn)在這些三角形重疊的區(qū)域中。如圖1所示。

圖1 APIT定位算法基本原理圖

如圖1所示，陰影部分表示所有包含待測節(jié)點(diǎn)的錨節(jié)點(diǎn)三角形最終重疊的部分，將該部分的幾何中心近似為待測節(jié)點(diǎn)的定位坐標(biāo)。

3 DV-HOP定位算法

DV-Hop算法的最主要的思想是：利用估計的兩節(jié)點(diǎn)間的距離作為實(shí)際的距離，然后利用三邊測量法得到所求節(jié)點(diǎn)的位置，具體步驟如下：

（1）最小跳數(shù)值的記錄

錨節(jié)點(diǎn)不停地向外發(fā)送自己的信息，如果待測節(jié)點(diǎn)在其通信半徑內(nèi)，就會接受這些信息，其中包括錨節(jié)點(diǎn)的ID，跳數(shù)值，具體的位置等，接收點(diǎn)將最小跳數(shù)值記錄，如果接收到同一錨節(jié)點(diǎn)的信息，則將較大的那個跳數(shù)值刪除，同時將跳數(shù)值加1，重復(fù)以上過程直到接受點(diǎn)記錄到了定位區(qū)域內(nèi)所有錨節(jié)點(diǎn)的最小跳數(shù)值。

（2）平均跳距的計算

定位區(qū)域內(nèi)錨節(jié)點(diǎn)的個數(shù)為n，假設(shè)任意選取其中的兩個i,j的坐標(biāo)為（xi，yi），（xj，yj），在得知跳數(shù)、ID、位置等信息后，由公式(2)計算出平均跳距。

其中，hj表示兩節(jié)點(diǎn)間的跳數(shù)，求得平均跳距后，與最小跳數(shù)相乘，將該值近似為實(shí)際距離。

（3）三邊測量法定最終位置

根據(jù)所求節(jié)點(diǎn)間的實(shí)際距離，利用三邊測量法得到所求節(jié)點(diǎn)的位置。

4 基于非測距的定位算法的比較

定位算法性能的比較大致從節(jié)點(diǎn)分布的類型、定位的誤差、所需硬件的成本、可擴(kuò)展性等方面進(jìn)行比較的，下面對這幾項(xiàng)參數(shù)進(jìn)行簡單的介紹。

(1)節(jié)點(diǎn)分布類型

在定位區(qū)域內(nèi)，參考節(jié)點(diǎn)部署的密度越大，定位的精確度也就會越高，但也會對硬件設(shè)備造成更大的損耗。

(2)定位誤差

待測節(jié)點(diǎn)的定位誤差可以體現(xiàn)最終的定位效果。

(3)硬件成本

無線傳感網(wǎng)絡(luò)需要考慮的因素有很多，其中比較重要的因素就是硬件成本和整個網(wǎng)絡(luò)的能耗問題，一方面是所用傳感器節(jié)點(diǎn)的數(shù)量、大小、種類、能耗等，另一方面是節(jié)點(diǎn)之間進(jìn)行數(shù)據(jù)和信息傳輸時網(wǎng)絡(luò)的損耗和算法對數(shù)據(jù)進(jìn)行處理的消耗。

(4)可擴(kuò)展性

傳統(tǒng)的定位算法往往只有在特定的環(huán)境和條件下才能到達(dá)預(yù)想的定位效果，隨著科技的發(fā)展，硬件設(shè)備的升級，傳統(tǒng)的定位算法能夠有所改進(jìn)，適用性更強(qiáng)。

5 算法比較與分析

由表1可知，雖然質(zhì)心定位算法方法原理簡單，但定位精度太低，適合運(yùn)用于一些對定位精度要求不太高的情況。DV-HOP算法相比較而言雖然誤差較小且有著不錯可擴(kuò)展性，但是功耗較大，如果能在這方面有所改進(jìn)，這兩種算法的應(yīng)用前景將會很廣泛。相比較而言，APIT 定位算法定位精度不錯且可擴(kuò)展性較強(qiáng)，硬件消耗也較低，但是該算法的定位效果對節(jié)點(diǎn)部署的密度依賴性太強(qiáng)，如果在這方面有所改進(jìn)，APIT算法的應(yīng)用前景將會有很大的提升。

表1 基于非測距的定位算法的各項(xiàng)參數(shù)比較

[1]李建中,高宏．無線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J]．計算機(jī)研究與發(fā)展,2016,45(01)：1-15．

[2]石為人,袁久銀,雷璐寧．無線傳感器網(wǎng)絡(luò)覆蓋控制算法研究[J]．自動化學(xué)報,2009,35(5)：540-545．

[3]張濤,余翔宇,藍(lán)俊健,等．改進(jìn)的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)虛擬力部署方法[J]．計算機(jī)應(yīng)用研究,2015,32(11)：3356-3358．

[4]孫利民,李建中,陳渝,等．無線傳感器網(wǎng)絡(luò)[M]．北京：清華大學(xué)出版社,2005．

戴海祥（1994—），男，江蘇人，研究生，主要研究方向：無線傳感網(wǎng)絡(luò)定位。