無線傳感器網絡非測距定位算法比較

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

無線傳感器網絡非測距定位算法比較

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

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

無線傳感網絡；非測距定位算法

0 引言

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

1 質心定位算法

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

其中，（xi，yi）為待測節點通信范圍內能夠進行信息交互的信標節點坐標，（x，y）為待測節點坐標。

2 APIT定位算法

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

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

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

3 DV-HOP定位算法

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

（1）最小跳數值的記錄

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

（2）平均跳距的計算

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

其中，hj表示兩節點間的跳數，求得平均跳距后，與最小跳數相乘，將該值近似為實際距離。

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

根據所求節點間的實際距離，利用三邊測量法得到所求節點的位置。

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

定位算法性能的比較大致從節點分布的類型、定位的誤差、所需硬件的成本、可擴展性等方面進行比較的，下面對這幾項參數進行簡單的介紹。

(1)節點分布類型

在定位區域內，參考節點部署的密度越大，定位的精確度也就會越高，但也會對硬件設備造成更大的損耗。

(2)定位誤差

待測節點的定位誤差可以體現最終的定位效果。

(3)硬件成本

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

(4)可擴展性

傳統的定位算法往往只有在特定的環境和條件下才能到達預想的定位效果，隨著科技的發展，硬件設備的升級，傳統的定位算法能夠有所改進，適用性更強。

5 算法比較與分析

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

表1 基于非測距的定位算法的各項參數比較

[1]李建中,高宏．無線傳感器網絡的研究進展[J]．計算機研究與發展,2016,45(01)：1-15．

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

[3]張濤,余翔宇,藍俊健,等．改進的無線傳感器網絡節點虛擬力部署方法[J]．計算機應用研究,2015,32(11)：3356-3358．

[4]孫利民,李建中,陳渝,等．無線傳感器網絡[M]．北京：清華大學出版社,2005．

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