無(wú)線傳感器節(jié)點(diǎn)定位技術(shù)的研究及改進(jìn)

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

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

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

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

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

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

第一步：計(jì)算未知節(jié)點(diǎn)與每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)

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

第二步：計(jì)算每個(gè)錨節(jié)點(diǎn)每跳平均跳距HopSizeii。

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

（1）

式中：

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

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

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

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

第四步：計(jì)算未知節(jié)點(diǎn)坐標(biāo)。

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

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

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

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

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

2.1 平均每跳距離的估計(jì)值

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

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

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

2.3 未知節(jié)點(diǎn)的坐標(biāo)定位計(jì)算

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

3 本文對(duì)DV-HOP 算法的改進(jìn)

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

3.1 對(duì)錨節(jié)點(diǎn)跳距進(jìn)行修正

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

其中：

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

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

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

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

3.2 未知節(jié)點(diǎn)跳距的校正值的計(jì)算

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

3.3 坐標(biāo)估算

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

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

可得出未知節(jié)點(diǎn)的坐標(biāo)為。

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

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

。式中，（x，y）為定位坐標(biāo)，（xi，yi）為實(shí)際坐標(biāo)，R為通信半徑，N為待定位節(jié)點(diǎn)個(gè)數(shù)

為驗(yàn)證算法，節(jié)點(diǎn)隨機(jī)分布，☆代表錨節(jié)點(diǎn)，○代表未知節(jié)點(diǎn)，利用錨節(jié)點(diǎn)已知坐標(biāo)通過(guò)改進(jìn)的DV-HOP算法定位未知節(jié)點(diǎn)的坐標(biāo)位置。如圖1、2所示。

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

參考文獻(xiàn)

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

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

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

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

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

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