基于改進(jìn)DV—Hop算法的無線傳感網(wǎng)節(jié)點(diǎn)定位算法研究

王亞芳　蔡暢　劉俊杰

摘要：無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)是無線傳感器網(wǎng)絡(luò)重要的技術(shù)之一，而如何最大限度提高節(jié)點(diǎn)定位精度是無線傳感器網(wǎng)絡(luò)定位研究領(lǐng)域的一個難點(diǎn)。本文首先研究了傳統(tǒng)的DV-Hop定位算法，提出一種基于RSSI修正的DV-Hop并可以升級輔助錨節(jié)點(diǎn)定位算法。仿真結(jié)果表明，在相同網(wǎng)絡(luò)連通度的情況下，改進(jìn)算法提高了定位覆蓋率，同時具有更高的定位精度。

關(guān)鍵詞：無線傳感網(wǎng)；借點(diǎn)定位；DV-Hop算法

中圖分類號：TP3

文獻(xiàn)標(biāo)識碼A

文章編號2095-6363（2017）04-0080-02

無線傳感網(wǎng)是由大量設(shè)置在研究區(qū)域的傳感器節(jié)點(diǎn)，通過無線網(wǎng)絡(luò)組成的一個多跳組織網(wǎng)絡(luò)，集數(shù)據(jù)采集、數(shù)據(jù)處理和數(shù)據(jù)傳輸于一身。無線傳感網(wǎng)絡(luò)能應(yīng)用到很多方面，而位置信息是解決很多問題的前提，只有了解傳感器節(jié)點(diǎn)的位置信息，才能對事件做出應(yīng)對措施。定位技術(shù)是無線傳感器網(wǎng)絡(luò)的重要研究方向，該技術(shù)通過網(wǎng)絡(luò)中一些已知位置的節(jié)點(diǎn)使用這些節(jié)點(diǎn)相互交換信息，運(yùn)用某種已經(jīng)存在算法求得未知節(jié)點(diǎn)的位置信息。無線傳感器通常由兩種借點(diǎn)構(gòu)成，一種節(jié)點(diǎn)是已經(jīng)確定自己在網(wǎng)絡(luò)中位置，也就是錨節(jié)點(diǎn)（AnchorNode），另一種是未知節(jié)點(diǎn)（unknow），這種節(jié)點(diǎn)需要通過其他錨節(jié)點(diǎn)來最終確認(rèn)自己的位置信息。

無線傳感網(wǎng)定位算法大概可以分為基于測距的定位算法和基于非測距的定位算法。基于測距的定位算法是根據(jù)測量節(jié)點(diǎn)之間的角度或者直接顯示的距離來實(shí)現(xiàn)的，這種算法在定位方面能夠表現(xiàn)的比較精確，但對于硬件要求較高?；诜菧y距的定位算法根據(jù)節(jié)點(diǎn)與節(jié)點(diǎn)之間的相互連通關(guān)系就可以實(shí)現(xiàn)對目標(biāo)節(jié)點(diǎn)的鎖定，對于硬件要求低。DV-Hop定位算法不依賴于測距方法，利用多跳錨節(jié)點(diǎn)信息直接參與節(jié)點(diǎn)定位，大大提高了定位覆蓋率，故本文采用DV-Hop算法對無線傳感網(wǎng)節(jié)點(diǎn)進(jìn)行定位。

1.改進(jìn)的DV-Hop定位算法

在無線傳感網(wǎng)中進(jìn)行定位時，DV-Hop算法可以通過少量的錨節(jié)點(diǎn)比例進(jìn)行定位，為定位節(jié)省成本。如果錨節(jié)點(diǎn)比例太低，不存在足夠多的錨節(jié)點(diǎn)為未知節(jié)點(diǎn)進(jìn)行定位，那就必須利用通信范圍外的錨節(jié)點(diǎn)進(jìn)行距離估算，就會出現(xiàn)誤差。改進(jìn)DV-Hop算法主要從定位精度和定位覆蓋率這兩個評價指標(biāo)入手，在跳段距離和升級錨節(jié)點(diǎn)兩方面進(jìn)行改進(jìn)，以達(dá)到減小誤差、提高定位精度及覆蓋率的目的。

1.1修正一跳跳距

一跳跳距在整個網(wǎng)絡(luò)定位過程中起著至關(guān)重要的作用，本文的改進(jìn)算法借助于RSSI測距技術(shù)對第一跳測距結(jié)果進(jìn)行校正。具體步驟如下。1）監(jiān)測網(wǎng)絡(luò)中節(jié)點(diǎn)互相廣播信息包，獲得傳感器節(jié)點(diǎn)間連通性，同時得出節(jié)點(diǎn)間的跳數(shù)值hopij以及任意鄰居節(jié)點(diǎn)間的RSSI。2）對網(wǎng)絡(luò)中的節(jié)點(diǎn)間的跳數(shù)值進(jìn)行修正。本文舍棄傳統(tǒng)算法中跳數(shù)均為整數(shù)的思想，對RSSI進(jìn)行歸一化處理，隨后把這些值當(dāng)作節(jié)點(diǎn)間的跳數(shù)值。3）計(jì)算全網(wǎng)平均跳距。4）計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)距離。在選擇錨節(jié)點(diǎn)時，選擇跳數(shù)值最小的錨節(jié)點(diǎn)。5）未知節(jié)點(diǎn)坐標(biāo)計(jì)算。

1.2升級輔助錨節(jié)點(diǎn)

在無線傳感網(wǎng)中，錨節(jié)點(diǎn)的不規(guī)則存在，使某些未知節(jié)點(diǎn)不能接收到錨節(jié)點(diǎn)的信息，導(dǎo)致這些未知節(jié)點(diǎn)難以實(shí)現(xiàn)定位。本文采用輔助錨節(jié)點(diǎn)技術(shù)來提高整個定位算法的覆蓋率。引入優(yōu)先級Pri的概念，采用優(yōu)先級把已經(jīng)實(shí)現(xiàn)定位的未知節(jié)點(diǎn)升級為錨節(jié)點(diǎn)，再把這些錨節(jié)點(diǎn)應(yīng)用到后續(xù)的定位中。

網(wǎng)絡(luò)中的錨節(jié)點(diǎn)廣播自身信息給未知節(jié)點(diǎn)，未知節(jié)點(diǎn)接收信息，計(jì)算優(yōu)先級并排序。未知節(jié)點(diǎn)的優(yōu)先級pri的大小由信息包數(shù)量不同來決定，當(dāng)未知節(jié)點(diǎn)接收到不同錨節(jié)點(diǎn)的信息包時，優(yōu)先級pri加l，依次計(jì)算出所有未知節(jié)點(diǎn)的優(yōu)先級，并設(shè)置一個鏈表，鏈表的表頭即鏈表中最大的優(yōu)先級Pri。升級為錨節(jié)點(diǎn)的未知節(jié)點(diǎn)從鏈表中刪除，輔助錨節(jié)點(diǎn)和網(wǎng)絡(luò)中原本的錨節(jié)點(diǎn)再次進(jìn)行廣播，然后再次按優(yōu)先級重新排列鏈表，直到循環(huán)完最后一個未知節(jié)點(diǎn)就結(jié)束。

2.仿真與分析

本文使用MATLAB軟件對改進(jìn)算法和傳統(tǒng)DV Hop定位算法進(jìn)行仿真比較，驗(yàn)證改進(jìn)DV Hop定位算法是否具有更好的定位性能。

對整體定位誤差進(jìn)行分析，在同一網(wǎng)絡(luò)連通度（取20）情況下進(jìn)行仿真。

由圖1可知，在錨節(jié)點(diǎn)的密度由小到大的整個過程中，改進(jìn)算法的定位誤差在逐漸減小，并且改進(jìn)算法的總體定位誤差值始終低于傳統(tǒng)DV-Hop算法。

如圖2所示，隨著錨節(jié)點(diǎn)比例的增大，改進(jìn)算法和傳統(tǒng)算法的定位覆蓋率都在增大，但是在錨節(jié)點(diǎn)比例低于8%時，傳統(tǒng)算法的定位覆蓋率始終低于改進(jìn)算法的定位覆蓋率。

3.結(jié)論

本文針對無線傳感網(wǎng)的借點(diǎn)定位問題，在傳統(tǒng)DVHop定位算法基礎(chǔ)上，利用RssI技術(shù)修正一跳跳距，并根據(jù)定位需求升級輔助錨節(jié)點(diǎn)。通過MATLAR對改進(jìn)后的算法進(jìn)行仿真，驗(yàn)證了改進(jìn)算法的有效性，經(jīng)過仿真并分析，改進(jìn)DV-Hop定位算法可以有效降低定位誤差，同時提高定位精度，在覆蓋率方面也有優(yōu)良的表現(xiàn)。