無線傳感器網(wǎng)絡(luò)中的DV—HOP定位改進(jìn)算法
加入技術(shù)交流群
無線傳感器網(wǎng)絡(luò)是由大量隨機(jī)分布的傳感器節(jié)點(diǎn)組成，是一種分布式的、自組織的網(wǎng)絡(luò)。其關(guān)鍵技術(shù)包括：網(wǎng)絡(luò)拓?fù)淇刂啤⒐?jié)點(diǎn)定位、時鐘同步、數(shù)據(jù)融合、路由協(xié)議等。而節(jié)點(diǎn)定位問題則是無線傳感器網(wǎng)絡(luò)中的一個最為基本和重要的問題。目前，無線傳感器網(wǎng)絡(luò)定位算法可以分為基于測距和基于非測距的定位算法?；跍y距定位常用的測量方法有TOA、TDOA、AOA、RSSI，盡管這些技術(shù)相對精度高，但是對硬件要求很高。基于非測距定位常用的測量方法有：DV-Hop、質(zhì)心、APIT、MDS—MAP。
DV—Hop為典型的基于非測距定位，其對硬件要求低，實(shí)現(xiàn)簡單。它的不足之處在于計(jì)算平均跳距及定位坐標(biāo)時會產(chǎn)生誤差。因此針對DV—Hop算法的缺陷，提出了一系列的改進(jìn)算法，參考文獻(xiàn)對原始算法中的平均跳距進(jìn)行改進(jìn)，使用多個錨節(jié)點(diǎn)估算平均距離并且采用歸一化加權(quán)的平均跳距。參考文獻(xiàn)提出了基于幾何學(xué)的定位算法，利用幾何學(xué)中的斜率方法來判斷錨節(jié)點(diǎn)間的位置關(guān)系，從中選取最優(yōu)的錨節(jié)點(diǎn)序列，從而更精確地確定未知節(jié)點(diǎn)。參考文獻(xiàn)引入共線度的概念，利用共線度參數(shù)，動態(tài)地調(diào)節(jié)未知節(jié)點(diǎn)可以收集的鄰居錨節(jié)點(diǎn)的距離閾值，挑選網(wǎng)絡(luò)中好的錨節(jié)點(diǎn)組進(jìn)行位置估計(jì)，最后再用加權(quán)估計(jì)機(jī)制來得到最終的節(jié)點(diǎn)位置估計(jì)。這些方法都在一定程度上提高了定位精度。
本文針對DV—Hop算法中計(jì)算平均跳距和三邊定位兩方面存在的定位誤差，提出了改進(jìn)的算法。首先利用全網(wǎng)平均跳距來糾正單個錨節(jié)點(diǎn)的平均跳距，然后在最后計(jì)算三邊定位時，利用節(jié)點(diǎn)間連通度的不同，選擇最優(yōu)組合的3個錨節(jié)點(diǎn)來參與定位，進(jìn)一步提高定位精度。
1 DV—Hop算法介紹
美國路特葛斯大學(xué)的Dragos Niculescu等人利用距離矢量路由和GPS定位原理提出一系列分布式定位算法，合稱APS，DV—Hop算法就是其中的一種。
DV—Hop分為3個步驟實(shí)現(xiàn)：
①錨節(jié)點(diǎn)i廣播自身的位置信息IDi。初始跳數(shù)0，每發(fā)送一個節(jié)點(diǎn)信息，跳數(shù)就加1，然后轉(zhuǎn)發(fā)，直到網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都收到錨節(jié)點(diǎn)的信息包。如果節(jié)點(diǎn)收到同一個錨節(jié)點(diǎn)不同的跳數(shù)信息，只取最小的跳數(shù)信息。
②當(dāng)錨節(jié)點(diǎn)i接收到其他錨節(jié)點(diǎn)的位置和最小跳數(shù)信息后，就可以計(jì)算出平均每跳距離(Average Hop Distance，AHD)的計(jì)算公式：
其中，(xi，yi)、(xj，yj)分別為錨節(jié)點(diǎn)i、j的坐標(biāo)；hij為兩個錨節(jié)點(diǎn)之間的跳數(shù)。未知節(jié)點(diǎn)只接收離它最近的錨節(jié)點(diǎn)的AHDi，hopi為未知節(jié)點(diǎn)離最近錨節(jié)點(diǎn)的跳數(shù)，再根據(jù)跳數(shù)信息，即可算得未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離P：
P=AHDi×hopi (2)
③當(dāng)未知節(jié)點(diǎn)獲得3個或者更多的錨節(jié)點(diǎn)信息時，可以利用三邊定位或者最大似然相似求出未知節(jié)點(diǎn)的位置。(x，y)為未知節(jié)點(diǎn)的坐標(biāo)，(xi，yi)為已知錨節(jié)點(diǎn)的坐標(biāo)。根據(jù)式(2)即可算出未知節(jié)點(diǎn)的坐標(biāo)：
2 改進(jìn)后的DV—Hop算法
本文主要對DV—Hop算法里的第2步和第3步進(jìn)行改進(jìn)，第1步與原算法相同。原算法中，在第2步計(jì)算平均跳距的時候，未知節(jié)點(diǎn)接收來自最近的錨節(jié)點(diǎn)的平均跳距。但是由于網(wǎng)絡(luò)節(jié)點(diǎn)分布的不均勻性，導(dǎo)致單個錨節(jié)點(diǎn)計(jì)算的平均跳距存在著一定的誤差，因此本文引入全網(wǎng)平均跳距與單個錨節(jié)點(diǎn)平均跳距的均值來修正原算法中的平均跳距。在第3步中，錨節(jié)點(diǎn)的位置信息對定位精度影響很大，本文利用節(jié)點(diǎn)間連通度的不同，選取最優(yōu)的3個錨節(jié)點(diǎn)，以減小定位誤差。
2．1 平均跳距的改進(jìn)
將全網(wǎng)平均跳距與單個錨節(jié)點(diǎn)估算出來的AHDi取平均來代替經(jīng)典算法中的平均跳距，這樣未知節(jié)點(diǎn)既有全網(wǎng)的估算信息，也具有離它最近的錨節(jié)點(diǎn)的估算平均跳距AHDi的局部信息。全網(wǎng)平均跳距公式為：
其中，n為網(wǎng)絡(luò)中的錨節(jié)點(diǎn)的個數(shù)。
修正后的平均跳距AHD公式為：
AHD=(AHDall+AHDi)／2 (5)
2．2 基于選擇性的3個錨節(jié)點(diǎn)
基于選擇性的錨節(jié)點(diǎn)的定位算法利用連通度的不同，在三邊節(jié)點(diǎn)定位時，選擇最優(yōu)的3個錨節(jié)點(diǎn)定位，使其定位誤差最小。節(jié)點(diǎn)分布圖如圖1所示。未知節(jié)點(diǎn)N1利用三邊定位時可以用不同的3個錨節(jié)點(diǎn)組(P1，P2，P3)、(P1，P2，P4)、(P2，P3，P4)、(P1，P3，P4)來定位。而用最大似然估計(jì)計(jì)算時，則選用(P1，P2，P3，P4)來定位，這樣不同的錨節(jié)點(diǎn)組肯定會產(chǎn)生不同的定位位置。
2．2．1 基本規(guī)則
用未知節(jié)點(diǎn)與每個錨節(jié)點(diǎn)的最小跳數(shù)來定義連通度，用數(shù)組來表示。比如N1到所有錨節(jié)點(diǎn)的連通度為[1，1，2，5]。這樣圖1中的所有的未知節(jié)點(diǎn)的連通度可以用數(shù)組表示，如表1所列。
評論