無線傳感器節(jié)點定位技術(shù)的研究及改進

周亞羅 劉文廣 王莎莎 程銳涵

【關(guān)鍵詞】DV-HOP算法 跳距 修正

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks， WSN）是一種分布式傳感網(wǎng)絡(luò)，由大量微型、低成本、低功耗的傳感器節(jié)點組成，通過無線通信方式形成了一個多跳的自組織的網(wǎng)絡(luò)系統(tǒng)。傳感器節(jié)點自身定位是無線傳感器網(wǎng)絡(luò)定位機制的核心內(nèi)容，定位技術(shù)是無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一，對節(jié)點定位技術(shù)的研究具有重要的理論意義和應(yīng)用價值。

由于成本原因，傳感器節(jié)點中只有少數(shù)裝有GPS，稱為錨節(jié)點，所謂節(jié)點定位技術(shù)是只利用少數(shù)錨節(jié)點的位置坐標計算出大量未知節(jié)點的坐標位置。現(xiàn)有的節(jié)點定位算法主要分為兩類：一類是基于測距技術(shù)的定位算法，利用節(jié)點間的距離或角度來測距，常見的信號強度法（Received Signal Strength Indication，RSSI）、時間法（Time of Arrival，TOA）、時間差法（Time Difference of Arrival，TDOA）和角度法（Angle of Arrival，AOA）。基于測距技術(shù)的定位算法，定位精度相對較高，但硬件成本較高，容易受到環(huán)境因素的影響。另一類是基于網(wǎng)絡(luò)連通性的定位算法主要包括：質(zhì)心法、APIT算法、DV-HOP算法等。對硬件要求低、功耗小，可擴展性強，更能滿足傳感器網(wǎng)絡(luò)低功耗、低成本的要求。

1 傳統(tǒng)DV-HOP算法概述

DV-HOP 算法主要根據(jù)網(wǎng)絡(luò)的連通性，利用多跳特性進行定位。算法簡單，成本低，在各向同性的密集網(wǎng)絡(luò)中可以得到理想的定位精度。在惡劣的網(wǎng)絡(luò)拓撲環(huán)境中，定位精度有待提高。DV—Hop算法的定位過程分為四步：

第一步：計算未知節(jié)點與每個錨節(jié)點的最小跳數(shù)

錨節(jié)點在網(wǎng)絡(luò)中周期性發(fā)送自身信息，包含編號ID、自身坐標和跳數(shù)，初始跳數(shù)為0。通信范圍內(nèi)的其他節(jié)點收到信息后，與同一ID號的跳數(shù)比較，記錄下這些信息中的最小跳數(shù)值并將跳數(shù)值加1，轉(zhuǎn)發(fā)給它的鄰居節(jié)點。錨節(jié)點周期性廣播，直至未知節(jié)點記錄下與每個錨節(jié)點之間的最小跳數(shù)

第二步：計算每個錨節(jié)點每跳平均跳距HopSizeii。

利用各個錨節(jié)點之間的距離和跳數(shù)，求取每個錨節(jié)點對應(yīng)的每跳平均跳距。

（1）

式中：

（xi，yi） ，（xj，yj） 分別為錨節(jié)點i和j的坐標；

hij是節(jié)點i和節(jié)點j之間的的跳數(shù)。

第三步：確定未知節(jié)點跳距校正值，求取未知節(jié)點與各錨節(jié)點之間的距離。

校正值為未知節(jié)點與錨節(jié)點之間的每跳距離，未知節(jié)點與每個錨節(jié)點之間的距離=跳距校正值×跳數(shù)。傳統(tǒng)DV-HOP 算法采用距離未知節(jié)點跳數(shù)最小的錨節(jié)點的平均每跳距離作為校正值，并在網(wǎng)絡(luò)中廣播。

第四步：計算未知節(jié)點坐標。

根據(jù)未知節(jié)點與錨節(jié)點之間的距離di、錨節(jié)點坐標（xi，yi），求取未知節(jié)點坐標（x，y）。根據(jù)距離公式，列出未知節(jié)點與各錨節(jié)點的距離相應(yīng)的方程組：

解方程組，分別用第1個，第2個…第n-1個方程減去最后一個方程得到以下方程組：

上述方程組可用線性方程表示：AX=B，通過最小均方差估計方法，得到未知節(jié)點的坐標為。

2 傳統(tǒng)DV-HOP算法存在的問題及改進

DV-HOP 算法的核心算法是距離=跳數(shù)×跳距，但無論是錨節(jié)點的每跳距離還是未知節(jié)點每跳距離的校正值采用的都是平均或最小估計，在WSN節(jié)點密度非常高的情況下，定位精度較高。最后一步利用距離求坐標，一般采用的三邊定位或極大似然估計法，誤差較大。

2.1 平均每跳距離的估計值

網(wǎng)絡(luò)節(jié)點隨機分布，沒有規(guī)律，且各錨節(jié)點之間的跳數(shù)不成直線，但在計算錨節(jié)點平均每跳距離時采用的是各錨節(jié)點之間的直線距離，因此計算錨節(jié)點平均每一跳距離存在誤差，影響定位精度。馮江，朱強等提出對錨節(jié)點的平均每一跳距離進行加權(quán)，提出基于加權(quán)系數(shù)矩陣的DV-Hop改進算法；馬淑麗，趙建平提出最佳指數(shù)值概念，用最佳指數(shù)值下的公式計算錨節(jié)點平均每一跳距離。

2.2 未知節(jié)點每跳跳距的校正值

未知節(jié)點與每個錨節(jié)點之間的距離=跳距校正值×跳數(shù)，跳數(shù)一定的情況下，跳距校正值對定位是否準確起著決定性作用。傳統(tǒng)算法無論是采用距離未知節(jié)點跳數(shù)最小的錨節(jié)點的平均每跳距離還有采用全網(wǎng)所有錨節(jié)點的平均值作為未知節(jié)點的校正值，計算未知節(jié)點與各錨節(jié)點間距離，誤差都是比較大的。使用單個錨節(jié)點的平均每跳距離的估計值不能準確地反映網(wǎng)絡(luò)中節(jié)點的真實情況，采用全網(wǎng)錨節(jié)點平均值受到與未知節(jié)點距離較遠的錨節(jié)點的影響會使得誤差增大，且計算量加大。趙雁航，錢志鴻等在研究中只接收最近3個錨節(jié)點的平均每跳距離值進行加權(quán)計算未知節(jié)點的校正值。

2.3 未知節(jié)點的坐標定位計算

傳統(tǒng)DV-Hop算法，未知節(jié)點的坐標計算一般情況下采用的是極大似然估計法，對矩陣AB依賴性強，且當ATA為病態(tài)矩陣時，通過多邊定位法所估計出的未知節(jié)點坐標不僅誤差很大，而且定位精度的穩(wěn)定性較差，有時甚至得出錯誤的結(jié)果。一些學(xué)者將節(jié)點定位問題轉(zhuǎn)化為求最優(yōu)解問題，喬欣，常飛等用擬牛頓法對未知節(jié)點坐標的最小二乘解進行迭代優(yōu)化，李道全，劉月月，孫付龍等將DV-Hop算法初步定位結(jié)果作為初解，引入steffensen迭代模型進行迭代求最優(yōu)解；趙雁航，錢志鴻等用改進的粒子群（PSO）算法解未知節(jié)點坐標，改進粒子群算法，優(yōu)化定位中的迭代過程，能夠快速找到最優(yōu)解，提高了定位精度，降低了計算量和網(wǎng)絡(luò)開銷。

3 本文對DV-HOP 算法的改進

本文針對影響 DV-HOP 算法精度的兩個方面，分別在定位階段和位置估計階段對原算法進行了改進。

3.1 對錨節(jié)點跳距進行修正

式（1）中的每個錨節(jié)點每跳平均跳距HopSizeii，是利用錨節(jié)點之間的直線距離求出的平均跳距，而實際節(jié)點之間大部分都是非直線距離，因此該計算一定存在誤差。我們要利用估算錨節(jié)點與其他錨節(jié)點之間估算距離與實際距離之間的誤差來修正該錨節(jié)點的每跳平均跳距。設(shè)有n個錨節(jié)點，第i個錨節(jié)點的跳距修正值為ΔHOPi，則

其中：

dij為錨節(jié)點i，j之間的實際距離；

dij為錨節(jié)點i，j之間的估算距離，

hij為錨節(jié)點I，j之間的最小跳數(shù)；

修正后，錨節(jié)點i的每跳跳距HOPi=HopSizei+ΔHopi。

3.2 未知節(jié)點跳距的校正值的計算

未知節(jié)點每跳跳距的校正值采用最近節(jié)點跳距和全網(wǎng)平均跳距均有較大誤差，節(jié)點之間非直線分布，導(dǎo)致節(jié)點之間跳數(shù)越多，累積誤差越大，定位精度就越低。趙雁航，錢志鴻等在研究中只接收最近3個錨節(jié)點的平均每跳距離值，曾子維，馮章皓研究中只接收相應(yīng)未知節(jié)點周圍跳數(shù)在10跳及以內(nèi)的錨節(jié)點的跳距。但距離與跳數(shù)之間并不成正比的關(guān)系，尤其在節(jié)點數(shù)量較少的情況下，跳數(shù)少但有可能距離大。因此，本研究采用n跳范圍內(nèi)m個距離最近的個錨節(jié)點跳距加權(quán)計算未知節(jié)點的跳距校正值。設(shè)未知節(jié)點i附近滿足條件的m個錨節(jié)點跳距權(quán)值為wij，則有

3.3 坐標估算

取與未知節(jié)點n跳范圍內(nèi)的錨節(jié)點，再利用極大似然估計的方法計算自身位置。為消除累計誤差對最后計算結(jié)果的影響，在原計算方法的基礎(chǔ)上，引入一個加權(quán)矩陣W，加權(quán)系數(shù)為

，si為相應(yīng)未知節(jié)點周圍跳數(shù)在n跳及以內(nèi)的錨節(jié)點總數(shù)， 加權(quán)矩陣W如下式：

可得出未知節(jié)點的坐標為。

4 算法仿真及結(jié)果分析

為實驗改進后DV-HOP算法的定位精度，采用MATLAB平臺進行仿真驗證。定位過程中，節(jié)點數(shù)目及分布、錨節(jié)點的密度、通信半徑等參數(shù)對定位精度影響很大。仿真環(huán)境設(shè)置在100m×100m的正方形區(qū)域內(nèi)，100個網(wǎng)絡(luò)節(jié)點隨機分布，利用5跳距離內(nèi)最近的3個錨節(jié)點跳距加權(quán)計算得出未知節(jié)點校正值，通信半徑R=20，錨節(jié)點密度分別為10%，20%，30%，40%，50%，計算其定位誤差。定位誤差ERR用定位距離誤差與通信距離之間的比值來表示，

。式中，（x，y）為定位坐標，（xi，yi）為實際坐標，R為通信半徑，N為待定位節(jié)點個數(shù)

為驗證算法，節(jié)點隨機分布，☆代表錨節(jié)點，○代表未知節(jié)點，利用錨節(jié)點已知坐標通過改進的DV-HOP算法定位未知節(jié)點的坐標位置。如圖1、2所示。

從仿真結(jié)果中看出，隨著錨節(jié)點數(shù)量的增多，傳統(tǒng)的DV-Hop算法和改進的DV-Hop算法的定位精度均有所提高，但改進后的算法定位精度更高，誤差下降更平穩(wěn)，說明改進后的算法穩(wěn)定性更強，對于任意分布的WSN定位系統(tǒng)的適應(yīng)性更強。

參考文獻

[1]馮江，朱強，吳春春.改進的DV-Hop定位算法研究[J].計算機工程， 2012，38（19）：74-81.

[2]馬淑麗，趙建平.無線傳感器網(wǎng)絡(luò)中DV—Hop定位算法的改進[J].通信技術(shù)，2015，48（07）：840-844.

[3]趙雁航，錢志鴻，尚小航，程超。基于跳距修正粒子群優(yōu)化的WSN定位算法[J].通信學(xué)報，2013，34（9）：105-114.

[4]喬欣，常飛，丁恩杰，王桃.基于跳距修正的WSN 擬牛頓迭代定位算法[J].傳感技術(shù)學(xué)報，2014，27（6），797-801.

[5]李道全，劉月月，孫付龍.基于DV-Hop的WSN網(wǎng)絡(luò)節(jié)點定位算法[J].計算機仿真，2014，31（4）：303-306.

[6]曾子維，馮章皓.WSN中基于不同跳距修正的改進DV-HOP定位算法[J].遼寧科技大學(xué)學(xué)報，2015，38（5）：376-381.