非測距無線傳感器網絡定位算法研究

張水鋒1， 程 慶 2 ，陳帥1 1.淮南師范學院電子工程學院 2.淮南師范學院計算機學院

非測距無線傳感器網絡定位算法研究

張水鋒1， 程 慶 2 ，陳帥1 1.淮南師范學院電子工程學院 2.淮南師范學院計算機學院

本文介紹了無線傳感器網絡定位的原理及分類，闡述了非測距WSN算法中的質心算法的原理、DV-HOP算法的原理、APIT算法原理以及Amorphous 算法原理。同時對質心算法和DV-HOP算法進行了matlab仿真，并分析了非測距算法定位的誤差。

無線傳感器網絡定位 非測距 質心算法 DV-HOP算法

由分布在監測區域里的無線傳感器節點構成無線傳感器網絡(Wireless Sensor Network, WSN)。它是目前科技的前沿研究領域，具有高度集成和高度交叉的特點，主要應用于軍事領域、農業生產、生態監測與災害預警、基礎設施狀態監測、工業領域、智能交通、醫療系統以及信息家電設備等領域。

1 無線傳感器網絡定位原理及分類

無線傳感器網絡的一個基本功能是節點的定位，它對于無線傳感器網絡的定位起著至關重要的主要。無線傳感器網絡定位根據是否需要測量距離，可以分為測距定位算法和非測距定位算法。測距定位算法是要測量節點間的距離或者角度信息，然后使用三邊測量、三角測量或者最大似然估計定位算法實現節點間定位。而非測距定位算法，不需要測量節點間的距離，通過一些其他信息實現定位。測距定位算法主要包括RSSI、TOA、TDOA和AOAO等算法，非測距定位算法主要包括質心算法、DV-HOP算法、Amorphous 算法和 APIT 算法等。

2 非測距WSN定位算法原理

非測距的定位算法由于對硬件的要求比較低，得到了廣泛的使用。非測距的算法主要有四種，算法原理如下。

質心算法是利用節點之間的簡單幾何關系估算未知節點的坐標位置。DV-Hop(Distance Vector-Hop)定位算法的執行過程為：信標節點向鄰居節點廣播一個信息，該信息包含信標節點的節點編號、坐標和跳數計數數據，跳數的初始值設為 0，節點會根據收到的數據報更新計數表，保證每次計算到每個信標節點的最小跳數。當它收到來自同一個節點的信息時，比較其中的跳數計數，當大于對應的最小計數時，簡單的丟棄該信息。否則，更新相應的最小跳數，并把信息的跳數計數加一，然后以廣播的形式轉發到整個網絡，供其他節點參考修改。APIT 算法的基本思想是：遍歷未知節點的所有鄰居信標節點，每次都拿出三個節點組成一個三角形，判斷未知節點是否處于該三角形區域內，確定完所有的三角形區域后會形成一個交集區域，未知節點的坐標即為該交集區域的質心。Amorphous的無線傳感器網絡定位算法，在算法初始階段，信標節點發送位置信息并在全網內傳播，未知節點以自己的通信半徑乘以最小跳數計算到信標節點的距離，然后采用極大似然法計算坐標。

3 質心算法和DV-HOP算法的matlab仿真

對于前面提到的四種非測距的定位算法，本文主要對質心算法和DV-HOP算法進行了仿真，結果如下。

質心算法信標節點與未知節點仿真圖

質心算法誤差仿真圖

DV-Hop算法信標節點與未知節點仿真圖

DV-Hop算法誤差仿真圖

4 小結

從上面的仿真結果可知質心算法的誤差較大，定位精度也不如DV-Hop 算法。質心算法由于只是簡單的取鄰居信標節點所組成的不規則多邊形，因此其定位精度不是很高。DV-Hop 算法需要每個信標節點計算自己的平均每跳距離，該算法計算未知節點到信標節點的距離時的累積誤差要小很多，所以DV-Hop 算法的定位精度較高。

[1]孫利民，李建中，陳渝，等. 無線傳感器網絡[M]. 北京:清華大學出版社，2006.

[2]崔莉，鞠海玲，苗勇，李天璞，劉巍，趙澤. 無線傳感器網絡研究進展[J]. 計算機研究與發展，2005，42(l): 163-174.

[3]杜新恒，程良倫. 無線傳感器網絡中距離無關定位算法的研究[J].計算機工程與應用2008，44(33): 119-121.

TN962

A

淮南師范學院科學研究基金項目(2016xj46)；2 01 3 高校省級自然科學研究項目( K j 2 01 3 z 2 9 7 )。