多通信半徑的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法*

馬淑麗，趙建平

（曲阜師范大學(xué)物理工程學(xué)院，山東曲阜273165）

多通信半徑的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法*

馬淑麗，趙建平*

（曲阜師范大學(xué)物理工程學(xué)院，山東曲阜273165）

為了實(shí)現(xiàn)無線傳感器網(wǎng)絡(luò)中基于無需測距DV-Hop定位算法的高精度定位，改進(jìn)基于2、3通信半徑的DV-Hop節(jié)點(diǎn)定位算法，并利用最小均方差準(zhǔn)則改進(jìn)計(jì)算平均每跳距離的公式，在最佳指數(shù)值下，修正錨節(jié)點(diǎn)平均每跳距離。MATLAB仿真結(jié)果表明，改進(jìn)的算法在隨機(jī)分布環(huán)境能提高節(jié)點(diǎn)定位精度；在最佳指數(shù)值下，進(jìn)一步提升節(jié)點(diǎn)定位精度；在錨節(jié)點(diǎn)人工部署環(huán)境下，大大提高節(jié)點(diǎn)定位精度。改進(jìn)的算法實(shí)現(xiàn)高精度定位同時(shí)，不需要增加網(wǎng)絡(luò)泛洪次數(shù)和硬件成本。

無線傳感器網(wǎng)絡(luò)；節(jié)點(diǎn)定位；DV-Hop；最小均方差；節(jié)點(diǎn)部署

EEACC:6150Pdoi:10.3969/j.issn.1004-1699.2016.04.021

隨著微控制系統(tǒng)與短距離無線通信技術(shù)［1］的發(fā)展，無線傳感器網(wǎng)絡(luò)WSN（Wireless Sensor Network）技術(shù)作為新興的物聯(lián)網(wǎng)重要技術(shù)之一，在過去的十幾年時(shí)間迅速發(fā)展。無線傳感器網(wǎng)絡(luò)技術(shù)廣泛應(yīng)用于農(nóng)業(yè)監(jiān)控、核輻射檢測、森林監(jiān)測、敵軍領(lǐng)域偵查等人不能長時(shí)間滯留的環(huán)境，由大量微型傳感器節(jié)點(diǎn)組成［2］，每個(gè)節(jié)點(diǎn)由傳感器模塊、無線通信模塊、控制模塊、存儲(chǔ)模塊、計(jì)算模塊等構(gòu)成。節(jié)點(diǎn)將采集到的物理界［3］的信息最終傳送到監(jiān)控中心或用戶。一些跟蹤定位的應(yīng)用如森林防火、搜索和救援［2］、敵軍區(qū)域監(jiān)測［4］等不僅需要知道節(jié)點(diǎn)采集的事件信息還需要知道事件發(fā)生的位置，所以節(jié)點(diǎn)定位技術(shù)在無線傳感器網(wǎng)絡(luò)中相當(dāng)重要［2］。根據(jù)位置是否已知，節(jié)點(diǎn)分為兩類，一類是位置固定即人工部署［2］或有GPS、北斗等導(dǎo)航設(shè)備的節(jié)點(diǎn)。這類節(jié)點(diǎn)知道自己的位置信息，稱為錨節(jié)點(diǎn)，成本比一般節(jié)點(diǎn)高，在定位過程中能量消耗也比較大［4］，所以網(wǎng)絡(luò)中錨節(jié)點(diǎn)的數(shù)量較少［2，4］。另一類節(jié)點(diǎn)通過飛機(jī)撒落等途徑隨機(jī)分布［2，4］在網(wǎng)絡(luò)中，不知道自身位置信息，是需要定位的節(jié)點(diǎn)，稱為未知節(jié)點(diǎn)。未知節(jié)點(diǎn)依靠錨節(jié)點(diǎn)來定位，當(dāng)未知節(jié)點(diǎn)得到超過三個(gè)錨節(jié)點(diǎn)位置信息及距離時(shí)［4］，可用三邊測量法、多邊測量法等估算自身位置。一般，根據(jù)是否基于節(jié)點(diǎn)間精確距離的定位，將定位技術(shù)分為兩大類，一類是高成本、高定位精度的基于測距（Range-Based）的定位［2，5］。這類定位技術(shù)，需要知道節(jié)點(diǎn)之間的精確距離或角度［1-2］，然后用三邊測量法或三角形［1］關(guān)系定位。如RSSI定位算法，節(jié)點(diǎn)需要微波發(fā)射硬件設(shè)備，向周圍發(fā)射無線微波信號(hào)，接收節(jié)點(diǎn)根據(jù)信號(hào)的強(qiáng)弱［2］，通過信號(hào)衰減模型公式計(jì)算與其它節(jié)點(diǎn)間的精確距離。另一類定位技術(shù)是低成本、低精度的基于無需測距（Range-Free）的定位［2，5］，這類定位技術(shù)不需要增加節(jié)點(diǎn)硬件設(shè)施，根據(jù)節(jié)點(diǎn)間的網(wǎng)絡(luò)信息傳輸記錄錨節(jié)點(diǎn)坐標(biāo)信息和節(jié)點(diǎn)間的跳數(shù)值［5］，然后估算節(jié)點(diǎn)間的距離。如DV-Hop（Distance Vector-Hop［6］）算法，節(jié)點(diǎn)根據(jù)到錨節(jié)點(diǎn)間的跳數(shù)和坐標(biāo)信息，估算節(jié)點(diǎn)間的距離，由于估算時(shí)將跳段距離代替直線距離［7］，誤差很大，定位精度不高。在一般的粗精度定位應(yīng)用中，定位精度在0.4以下即可［8-10］滿足。

文獻(xiàn)［11］提出基于雙通信半徑的DV-Hop算法，文獻(xiàn)［12］提出基于3通信半徑的DV-Hop算法，文獻(xiàn)［13］提出基于多通信半徑的加權(quán)DV-Hop算法，都大大提高了定位精度。文獻(xiàn)［13］指出通信半徑越多定位誤差越小，但是錨節(jié)點(diǎn)泛洪次數(shù)越多，能量消耗越大，由于無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)由單獨(dú)電源供電，電池的消耗［10］直接影響整個(gè)網(wǎng)絡(luò)的生命周期，所以本文只考慮改進(jìn)基于2、3通信半徑的多通信半徑DV-Hop算法。文獻(xiàn)［14］提出最佳指數(shù)值概念，并將改進(jìn)的DV-Hop算法應(yīng)用在文獻(xiàn)［15］提出的一種錨節(jié)點(diǎn)人工部署環(huán)境。本文結(jié)合上述文獻(xiàn)，改進(jìn)DV-hop算法。主要思想是將錨節(jié)點(diǎn)分配多個(gè)通信半徑，未知節(jié)點(diǎn)固定為一個(gè)通信半徑，采用最小均方差準(zhǔn)則下的最佳指數(shù)值進(jìn)一步減小錨節(jié)點(diǎn)平均每跳距離誤差，從而提高節(jié)點(diǎn)定位精度。

1　DV-Hop定位算法與分析

1.1DV-Hop算法

DV-Hop定位算法是由美國羅格斯大學(xué)（Rutgers University）Dragos Niculescu等人在2003年提出的6種分布式定位算法之一［15］。

假設(shè)前提:網(wǎng)絡(luò)中錨節(jié)點(diǎn)與未知節(jié)點(diǎn)都是隨機(jī)分布，且有相同的通信半徑，通信范圍是以自身為圓點(diǎn)的圓。節(jié)點(diǎn)間可以互相通信，即具有接收和發(fā)送信息的功能。每個(gè)節(jié)點(diǎn)還具有計(jì)算［16］、存儲(chǔ)功能［2］。

DV-Hop算法定位步驟:

Step 1錨節(jié)點(diǎn)以泛洪的模式［17］向網(wǎng)絡(luò)發(fā)送自身坐標(biāo)信息和初始跳數(shù)值0。

Step 2節(jié)點(diǎn)接收到信息后保存，并將跳數(shù)值加1后轉(zhuǎn)發(fā)出去。多次轉(zhuǎn)發(fā)過程中，節(jié)點(diǎn)只保存較小的錨節(jié)點(diǎn)跳數(shù)值和未曾保存過的錨節(jié)點(diǎn)坐標(biāo)信息，當(dāng)接收到比已經(jīng)保存的跳數(shù)值大的信息則舍棄，停止轉(zhuǎn)發(fā)。最終，網(wǎng)絡(luò)中所有節(jié)點(diǎn)保存到每個(gè)錨節(jié)點(diǎn)的坐標(biāo)信息和與其它錨節(jié)點(diǎn)間的最小跳數(shù)值［17］。

Step 3錨節(jié)點(diǎn)根據(jù)保存的其他錨節(jié)點(diǎn)坐標(biāo)信息，計(jì)算出與其它錨節(jié)點(diǎn)間的距離。然后，根據(jù)保存的與其它錨節(jié)點(diǎn)間的最小跳數(shù)值，計(jì)算平均每跳距離，并作為校正值，向網(wǎng)絡(luò)第二次泛洪廣播。

一般，平均每跳距離根據(jù)無偏估計(jì)準(zhǔn)則計(jì)算，需滿足:

得出:

dHopi是錨節(jié)點(diǎn)i的平均每跳距離。dij是錨節(jié)點(diǎn)i、j間的距離。hij是錨節(jié)點(diǎn)i、j間的最小跳數(shù)。xi，yi是錨節(jié)點(diǎn)i坐標(biāo)值，xj，yj是錨節(jié)點(diǎn)j坐標(biāo)值。

Step 4未知節(jié)點(diǎn)只接收并保存離自己最近的錨節(jié)點(diǎn)校正值，即只接收第一個(gè)送達(dá)的錨節(jié)點(diǎn)校正值。

Step 5未知節(jié)點(diǎn)根據(jù)保存的與錨節(jié)點(diǎn)間的最小跳數(shù)值，和接收到的平均每跳距離（校正值）計(jì)算出與每個(gè)錨節(jié)點(diǎn)的估算距離。

Step 6未知節(jié)點(diǎn)得知至少3個(gè)錨節(jié)點(diǎn)的估算距離時(shí)，用極大似然法、多邊測量法等估算自身坐標(biāo)。

極大似然法計(jì)算節(jié)點(diǎn)坐標(biāo):

其中di是未知節(jié)點(diǎn)與錨節(jié)點(diǎn)i間的估算距離，xi，yi是錨節(jié)點(diǎn)i坐標(biāo)值，n是錨節(jié)點(diǎn)個(gè)數(shù)，x，y是未知節(jié)點(diǎn)估算坐標(biāo)值。

1.2DV-Hop定位誤差分析

只是利用錨節(jié)點(diǎn)坐標(biāo)信息和信息傳輸?shù)奶鴶?shù)值定位，節(jié)點(diǎn)真實(shí)坐標(biāo)與定位坐標(biāo)之間誤差很大。

如圖1（a）所示，網(wǎng)絡(luò)中分布著A、B、C 3個(gè)錨節(jié)點(diǎn)，其他為未知節(jié)點(diǎn)。錨節(jié)點(diǎn)B的平均每跳距離為，計(jì)算的錨節(jié)點(diǎn)B的平均每跳距離要小于實(shí)際平均每跳距離，誤差較大。且錨節(jié)點(diǎn)B到錨節(jié)點(diǎn)A、C的每一跳距離長短不一樣，每兩跳段間都有角度（非180°），所以用直線距離除以跳數(shù)，求得錨節(jié)點(diǎn)的平均每跳距離并作為校正值，校正值誤差很大。未知節(jié)點(diǎn)用校正值乘以最小跳數(shù)值估算與錨節(jié)點(diǎn)間的距離，導(dǎo)致估算距離誤差很大，最終影響定位結(jié)果的精確度。一般，網(wǎng)絡(luò)中未知節(jié)點(diǎn)占大多數(shù)，錨節(jié)點(diǎn)占少數(shù)。未知節(jié)點(diǎn)分布密度遠(yuǎn)大于錨節(jié)點(diǎn)的分布密度，再加上錨節(jié)點(diǎn)隨機(jī)分布，錨節(jié)點(diǎn)間的距離時(shí)大時(shí)小，計(jì)算錨節(jié)點(diǎn)平均每一跳距離時(shí)誤差波動(dòng)大。所以考慮錨節(jié)點(diǎn)均勻分布減小誤差。

圖1　網(wǎng)絡(luò)結(jié)構(gòu)

在計(jì)算平均每跳距離時(shí)可以用多個(gè)通信半徑計(jì)算跳數(shù)，可以得到更精確的跳數(shù)值。如圖1（b）所示。D、E、F為錨節(jié)點(diǎn)，a、b、c、d、e為未知節(jié)點(diǎn)，通信半徑為R。錨節(jié)點(diǎn)D與未知節(jié)點(diǎn)a、b的距離分別為R、0.5R，但是錨節(jié)點(diǎn)D向未知節(jié)點(diǎn)a、b發(fā)送信息時(shí)跳數(shù)值都是加1。同樣，錨節(jié)點(diǎn)E與未知節(jié)點(diǎn)b、c的距離都為0.5 R，但是錨節(jié)點(diǎn)E向未知節(jié)點(diǎn)b、c發(fā)信息時(shí)跳數(shù)值是1。假如錨節(jié)點(diǎn)有兩個(gè)通信半徑分別為R、R/2，則當(dāng)使用R/2通信半徑時(shí)，節(jié)點(diǎn)D與b間的跳數(shù)值可以為0.5，節(jié)點(diǎn)E與b、c間跳數(shù)值可以為0.5。

文獻(xiàn)［18-19］證明最小均方差準(zhǔn)則下的定位誤差要高于無偏估計(jì)準(zhǔn)則下的定位誤差。計(jì)算平均每跳距離可以考慮用基于最小均方誤差準(zhǔn)則，需滿足:

2　算法的改進(jìn)與應(yīng)用環(huán)境

2.1基于雙通信半徑DV-Hop算法

文獻(xiàn)［11］提出基于雙通信半徑的DV-Hop改進(jìn)算法，使錨節(jié)點(diǎn)有2個(gè)通信半徑，分別為R/2、R，未知節(jié)點(diǎn)1個(gè)通信半徑R。假設(shè)網(wǎng)絡(luò)中錨節(jié)點(diǎn)有延時(shí)發(fā)射信號(hào)功能，能調(diào)節(jié)信號(hào)發(fā)射的功率，使錨節(jié)點(diǎn)有兩個(gè)通信半徑，一種功率使通信半徑為R/2，另一種功率使通信半徑為R（即與未知節(jié)點(diǎn)發(fā)射功率相同）。文獻(xiàn)［11］提出的基于雙通信半徑DV-Hop算法步驟:

Step 1錨節(jié)點(diǎn)以通信半徑R/2向網(wǎng)絡(luò)第一次泛洪廣播自身位置信息和初始跳數(shù)值0.5，接收到的節(jié)點(diǎn)保存位置信息和初始跳數(shù)值。

Step 2錨節(jié)點(diǎn)延時(shí)T時(shí)間，以通信半徑R向網(wǎng)絡(luò)第二次泛洪廣播自身位置信息和初始跳數(shù)值0。若接收節(jié)點(diǎn)已經(jīng)保存該錨節(jié)點(diǎn)的位置信息和初始跳數(shù)值0.5，則舍棄，并將位置信息和跳數(shù)值0.5以通信半徑R轉(zhuǎn)播出去；若接收節(jié)點(diǎn)沒有接收到第一次泛洪的信息，則保留第二次泛洪錨節(jié)點(diǎn)的位置信息和初始跳數(shù)值，并將初始跳數(shù)值加1后與位置信息以通信半徑R轉(zhuǎn)播出去。不斷轉(zhuǎn)播過程，接收節(jié)點(diǎn)只接收并保存較小跳數(shù)值的信息，將跳數(shù)值加1后轉(zhuǎn)播。最終，所有節(jié)點(diǎn)保存與錨節(jié)點(diǎn)的最小跳數(shù)值和錨節(jié)點(diǎn)的坐標(biāo)信息。

Step 3錨節(jié)點(diǎn)根據(jù)最小跳數(shù)值和坐標(biāo)信息計(jì)算平均每跳距離，計(jì)算如式（2）。

Step 4錨節(jié)點(diǎn)將平均每跳距離作為校正值向網(wǎng)絡(luò)第三次泛洪廣播。未知節(jié)點(diǎn)只接收并保存離自己最近的錨節(jié)點(diǎn)校正值。剩余步驟與DV-Hop相同。

以上基于雙通信半徑的DV-Hop算法，比DV-Hop算法大大提高了定位精度。但是，在第二次泛洪時(shí)，若發(fā)送節(jié)點(diǎn)為未知節(jié)點(diǎn)，接收節(jié)點(diǎn)為錨節(jié)點(diǎn)，則未知節(jié)點(diǎn)到其一跳范圍內(nèi)的錨節(jié)點(diǎn)間的跳數(shù)值記為1。如果未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離為R/2范圍內(nèi)，跳數(shù)值仍記1則導(dǎo)致計(jì)算平均每跳距離時(shí)的誤差很大。如圖1（b），未知節(jié)點(diǎn)d、e向錨節(jié)點(diǎn)F發(fā)送信息，如果按文獻(xiàn)［11］算法，則跳數(shù)值都是加1，而未知節(jié)點(diǎn)d、e與錨節(jié)點(diǎn)F間距離分別為R、R/2。所以文獻(xiàn)［11］算法只是將第一次泛洪時(shí)錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的跳數(shù)值記為0.5或1，沒有考慮轉(zhuǎn)播過程中精化跳數(shù)值。

本文在文獻(xiàn)［11］算法的基礎(chǔ)上進(jìn)一步精化跳數(shù)值。在第一次泛洪中，接收節(jié)點(diǎn)記錄下與自己R/2距離內(nèi)的錨節(jié)點(diǎn)的編號(hào)。在第二次泛洪中，第一次泛洪中的接收節(jié)點(diǎn)轉(zhuǎn)播信息時(shí)，將錨節(jié)點(diǎn)的編號(hào)信息也轉(zhuǎn)播。如果接收節(jié)點(diǎn)為編號(hào)對應(yīng)的錨節(jié)點(diǎn)，該錨節(jié)點(diǎn)轉(zhuǎn)播信息時(shí)，將跳數(shù)值加0.5后轉(zhuǎn)播，而不是加1后轉(zhuǎn)播。將改進(jìn)的算法命名為2-DV-Hop（A）。

文獻(xiàn)［14］在求平均每跳距離時(shí)，提出最小均方差準(zhǔn)則下的最佳指數(shù)值概念，并驗(yàn)證了在最佳指數(shù)值概念下可以提高定位精度2%左右。在2-DV-Hop（A）算法基礎(chǔ)上，本文結(jié)合文獻(xiàn)［14］，進(jìn)一步改進(jìn)算法，命名為2-DV-Hop（B）。在Step 3中用最佳指數(shù)值概念修正平均每跳距離。文獻(xiàn)［14］改進(jìn)式（9）中分母hij的指數(shù)，精化錨節(jié)點(diǎn)i的平均每跳距離dHopi，如式（10）。本文找出在不同錨節(jié)點(diǎn)覆蓋率和不同通信半徑下指數(shù)值α的最佳值，即使定位精度最高時(shí)的指數(shù)值，代入式（10）求平均每跳距離。

2.2基于三通信半徑DV-Hop定位算法

文獻(xiàn)［12］在文獻(xiàn)［11］基礎(chǔ)上提出基于三通信半徑DV-Hop算法，使錨節(jié)點(diǎn)有三種發(fā)射功率，一種功率使通信半徑為R/3，另一種功率使通信半徑為2R/3，還有一種功率使通信半徑為R，即與未知節(jié)點(diǎn)信號(hào)發(fā)射功率相同。本文改進(jìn)的基于三通信半徑的DV-Hop步驟:

Step 1錨節(jié)點(diǎn)以通信半徑R/3向網(wǎng)絡(luò)第一次泛洪廣播自身位置信息和初始跳數(shù)值1/3，接收到的節(jié)點(diǎn)保存位置信息和初始跳數(shù)值，并記錄下錨節(jié)點(diǎn)的編號(hào)，標(biāo)記為第一次泛洪中錨節(jié)點(diǎn)的編號(hào)。

Step 2錨節(jié)點(diǎn)延時(shí)T時(shí)間，以通信半徑2R/3向網(wǎng)絡(luò)第二次泛洪廣播自身位置信息和初始跳數(shù)值2/3，接收到的節(jié)點(diǎn)若已經(jīng)保存位置信息和初始跳數(shù)值1/3，則舍棄，否則記錄下錨節(jié)點(diǎn)的編號(hào)，并標(biāo)記為第二次泛洪中錨節(jié)點(diǎn)的編號(hào)。

Step 3錨節(jié)點(diǎn)再延時(shí)T時(shí)間，以通信半徑R向網(wǎng)絡(luò)第三次泛洪廣播自身位置信息和初始跳數(shù)值0，接收到的節(jié)點(diǎn)若已經(jīng)保存位置信息和初始跳數(shù)值1/3或2/3，則舍棄，且將位置信息和跳數(shù)值1/3 或2/3以通信半徑R轉(zhuǎn)播出去。接收節(jié)點(diǎn)若沒有接收到第一、二次泛洪的信息，則將初始跳數(shù)值加1后再將信息以R通信半徑轉(zhuǎn)播出去。不斷轉(zhuǎn)播，接收節(jié)點(diǎn)只接收并保存較小跳數(shù)值的信息。第一、二次泛洪中的接收節(jié)點(diǎn)在轉(zhuǎn)播信息時(shí)，也轉(zhuǎn)播錨節(jié)點(diǎn)的編號(hào)信息。如果接收節(jié)點(diǎn)為第一次泛洪中編號(hào)對應(yīng)的錨節(jié)點(diǎn)，錨節(jié)點(diǎn)將跳數(shù)值加1/3后轉(zhuǎn)播；如果接收節(jié)點(diǎn)為第二次泛洪中編號(hào)對應(yīng)的錨節(jié)點(diǎn)，錨節(jié)點(diǎn)將跳數(shù)值加2/3后轉(zhuǎn)播。其它接收節(jié)點(diǎn)將跳數(shù)值加1后轉(zhuǎn)播。最終，所有節(jié)點(diǎn)保存與錨節(jié)點(diǎn)的最小跳數(shù)值和錨節(jié)點(diǎn)的坐標(biāo)信息。將上述改進(jìn)的算法命名為3-DV-Hop（A）。

Step 4錨節(jié)點(diǎn)根據(jù)最小跳數(shù)值和坐標(biāo)信息計(jì)算平均每跳距離，計(jì)算如式（10）。用最佳指數(shù)值概念修正平均每跳距離，先求出使定位精度最高時(shí)的指數(shù)值α，然后再求平均每跳距離。將該步改進(jìn)的算法命名為3-DV-Hop（B）。

Step 5錨節(jié)點(diǎn)將平均每跳距離作為校正值向網(wǎng)絡(luò)第四次泛洪廣播。未知節(jié)點(diǎn)只接收離自己最近的錨節(jié)點(diǎn)校正值。剩余步驟與DV-Hop相同。

2.3錨節(jié)點(diǎn)人工部署方式

很多文獻(xiàn)從錨節(jié)點(diǎn)部署方式上提高定位精度，文獻(xiàn)［12，15，20-21］分別提出了4種錨節(jié)點(diǎn)人工部署方式。經(jīng)研究，文獻(xiàn)［15］部署方式較為占優(yōu)勢。本文將算法應(yīng)用在文獻(xiàn)［15］環(huán)境中，命名為2-DV-Hop（C）、3-DV-Hop（C）。文獻(xiàn)［15］提出的錨節(jié)點(diǎn)部署方式:將正方形區(qū)域劃分為m個(gè)大小相同的小正方形，每個(gè)小正方形內(nèi)切圓中心放置1個(gè)錨節(jié)點(diǎn)，其他未知節(jié)點(diǎn)隨機(jī)分布。如圖2所示，m為錨節(jié)點(diǎn)個(gè)數(shù)。

圖2　文獻(xiàn)［15］節(jié)點(diǎn)分布環(huán)境

3　MATLAB仿真結(jié)果分析

用MATLAB7.0軟件，設(shè)立仿真環(huán)境在100 m× 100 m正方形二維區(qū)域，節(jié)點(diǎn)總數(shù)100個(gè)，錨節(jié)點(diǎn)覆蓋率分別取4%、9%、16%、25%、36%、49%。未知節(jié)點(diǎn)隨機(jī)分布，通信半徑分別取20 m、30 m、40 m、50 m。將本文算法與DV-Hop算法、文獻(xiàn)［11］算法、文獻(xiàn)［12］算法對比，由于節(jié)點(diǎn)分布隨機(jī)性，仿真100次取平均值。

定位精度（Accuracy）指網(wǎng)絡(luò)中全部節(jié)點(diǎn)（N個(gè)）的平均定位誤差與節(jié)點(diǎn)通信半徑R的比值，值越小說明定位精度越高，計(jì)算如（11）式。

（xi，yi）、（x0i，y0i）分別指未知節(jié)點(diǎn)i的定位坐標(biāo)與實(shí)際坐標(biāo)。

3.1隨機(jī)分布多通信半徑DV-Hop算法

將錨節(jié)點(diǎn)與未知節(jié)點(diǎn)隨機(jī)分布，仿真本文2-DV-Hop（A）算法、3-DV-Hop（A）算法和DV-Hop算法、文獻(xiàn)［11］雙通信半徑算法、文獻(xiàn)［12］三通信半徑算法。如圖3所示，2-DV-Hop（A）算法比文獻(xiàn)［11］雙通信半徑算法占優(yōu)勢，通信半徑30 m，錨節(jié)點(diǎn)覆蓋率9%時(shí)，能提高定位精度1.23%。3-DV-Hop（A）算法比文獻(xiàn)［12］三通信半徑算法占優(yōu)勢，通信半徑30 m，錨節(jié)點(diǎn)覆蓋率 9%時(shí)，能提高定位精度1.64%。2-DV-Hop（A）算法、3-DV-Hop（A）算法分別比DV-Hop算法提高定位精度10%左右、15%左右。

圖3　5種算法對比

3.2隨機(jī)分布多通信半徑DV-Hop算法最佳指數(shù)

在錨節(jié)點(diǎn)隨機(jī)分布環(huán)境下，取不同的α代入式（10），仿真2-DV-Hop（B）算法和3-DV-Hop（B）算法，并與本文2-DV-Hop（A）算法和3-DV-Hop（A）算法對比，驗(yàn)證文獻(xiàn)［14］最佳指數(shù)值概念對本文改進(jìn)算法的有效性。通信半徑分別取20 m、 30 m、40 m、50 m。以錨節(jié)點(diǎn)覆蓋率25%為例，如圖4所示，在1.9～2.0指數(shù)值范圍內(nèi)，存在不同的最佳指數(shù)值使2-DV-Hop（B）算法和3-DV-Hop（B）在不同的通信半徑內(nèi)比原2-DV-Hop（A）算法和3-DV-Hop（A）算法定位精度高，且能達(dá)到最高定位精度。

圖4　4種算法對比

同理，找出其它錨節(jié)點(diǎn)覆蓋率下使定位精度最高時(shí)的指數(shù)，即最佳指數(shù)。經(jīng)研究，在不同的錨節(jié)點(diǎn)覆蓋率和不同的通信半徑R下，對應(yīng)不同的最佳指數(shù)α，如表1所示，α取1.91～2.04范圍。

表1　本文算法最佳指數(shù)（隨機(jī)分布）

將最佳指數(shù)代入本文2-DV-Hop（B）算法、3-DV-Hop（B）算法，并與DV-Hop算法、文獻(xiàn)［11］雙通信半徑算法、文獻(xiàn)［12］三通信半徑算法對比。如圖5所示，在隨機(jī)分布環(huán)境，最佳指數(shù)下，2-DV-Hop（B）算法比文獻(xiàn)［11］雙通信半徑算法占優(yōu)勢，通信半徑30 m，錨節(jié)點(diǎn)覆蓋率9%時(shí)，提高定位精度1.42%。3-DV-Hop（B）算法比文獻(xiàn)［12］三通信半徑算法占優(yōu)勢，通信半徑30 m，錨節(jié)點(diǎn)覆蓋率9%時(shí)，提高定位精度1.89%。2-DV-Hop（B）算法、3-DV-Hop（B）算法分別比DV-Hop算法提高定位精度11%左右、15%左右。

圖5　五種算法對比

3.3本文算法在文獻(xiàn)［15］環(huán)境中應(yīng)用

按照文獻(xiàn)［15］提出的錨節(jié)點(diǎn)部署方式，仿真本文算法2-DV-Hop（C）、3-DV-Hop（C），求最佳指數(shù)α。如表2，最佳指數(shù)α取1.89～2.40范圍。

表2　本文算法最佳指數(shù)（文獻(xiàn)［15］環(huán)境）

將最佳指數(shù)代入本文2-DV-Hop（B）算法、3-DV-Hop（B）算法，并與DV-Hop算法、文獻(xiàn)［11］雙通信半徑算法、文獻(xiàn)［12］三通信半徑算法對比。如圖6所示，在錨節(jié)點(diǎn)均勻部署環(huán)境，最佳指數(shù)下，2-DV-Hop（C）算法比文獻(xiàn)［11］雙通信半徑算法占優(yōu)勢，通信半徑30 m，錨節(jié)點(diǎn)覆蓋率9%時(shí)，提高定位精度6.26%。3-DV-Hop（C）算法比文獻(xiàn)［12］三通信半徑算法占優(yōu)勢，通信半徑30 m，錨節(jié)點(diǎn)覆蓋率9%時(shí)，提高定位精度5.52%。2-DV-Hop（C）算法、3-DV-Hop（C）算法分別比DV-Hop算法提高定位精度16%左右、19%左右。

圖6　五種算法對比

4　結(jié)語

首先分析了DV-Hop算法定位誤差來源，陳述了基于2、3通信半徑DV-Hop定位算法及其不足。然后，改進(jìn)基于2、3通信半徑的DV-Hop算法，在錨節(jié)點(diǎn)覆蓋率9%，通信半徑30 m時(shí)，比DV-Hop算法分別提高定位精度9.9%、15%。結(jié)合并改進(jìn)最小均方差準(zhǔn)則下求平均每跳距離的公式，在最佳指數(shù)下，本文算法進(jìn)一步提高定位精度，在錨節(jié)點(diǎn)覆蓋率9%，通信半徑30 m時(shí)，比DV-Hop算法分別提高定位精度11.3%、15.3%。最后，將算法應(yīng)用在錨節(jié)點(diǎn)人工部署未知節(jié)點(diǎn)隨機(jī)分布環(huán)境中，大大提高了定位精度。在錨節(jié)點(diǎn)覆蓋率9%，通信半徑30 m時(shí)，又分別提高了定位精度16.2%、19.1%。

［1］ Hadir A，Zine-Dine K，Bakhouya M，et al.An Optimized DV-Hop Localization Algorithm Using Average Hop Weighted Mean in WSNs［C］//Codes，Cryptography and Communication Systems （WCCCS），2014 5th Workshop on，IEEE，Nov.2014:25-29.

［2］ Qingjiang Shi，Chen He，Hongyang Chen，et al.Distributed Wireless Sensor Network Localization Via Sequential Greedy Optimization Algorithm［J］.IEEE Transactions on Signal Processing，2010，58（6）:3328-3340.

［3］ Zhang R，Ingelrest F，Barrenetxea G，et al.The Beauty of the Commons:Optimal Load Sharing by Base Station Hopping in Wireless Sensor Networks［J］.IEEE Journal on Selected Areas in Communications，2015，33（8）:1480-1491；

［4］ Hadir A，Zine-Dine K，Bakhouya M，et al.An Improved DV-Hop Localization Algorithm for Wireless Sensor Networks［C］//Next Generation Networks and Services（NGNS），2014 Fifth International Conference on.IEEE，May2014:330-334.

［5］ Bang Wang，Guang Wu，Shu Wang，et al.Localization Based on Adaptive Regulated Neighborhood Distance for Wireless Sensor Networks with a General Radio Propagation Model［J］.IEEE.Sensors Journal，2014，14（11）:3754-3762.

［6］ Dai Ying，Wang Jianping，Chongwei Zhang.Improvement of DVHop Localization Algorithms for Wireless Sensor Networks［C］// Wireless Communications Networking and Mobile Computing （WiCOM），2010 6th International Conference on IEEE，Sept 2010:1-4.

［7］ 夏少波，朱曉麗，鄒建梅.基于跳數(shù)修正的DV-Hop改進(jìn)算法［J］.傳感技術(shù)學(xué)報(bào)，2015，28（5）:757-762. XIA Shaobo，ZHU Xiaoli，ZO U Jiaumei.The Improved DV-Hop Algorithm Based on Hop Count［J］.Chinese Journal of Sensors and Actuators，2015，28（5）:757-762.

［8］ 江禹生，馮硯毫，管芳，等.無線傳感網(wǎng)非測距三維節(jié)點(diǎn)定位算法［J］.西安電子科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，39（5）: 140-147. JIANG Yusheng，F(xiàn)ENG Yanhao，GUAN Fang，et al.Range-Free Three-Dimensional Node Location Algorithm for the Wireless SensorNetwork［J］.JournalofXidianUniversity，2012，39（5）:140-147.

［9］ 周正.無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)自定位技術(shù)［J］.中興通信技術(shù)，2005，11（4）:51-56. ZHOU Z.Self-Localization Technologies for Wireless Sensor Network Nodes［J］.ZTE Communications，2005，11（4）:51-56.

［10］王翥，郝曉強(qiáng)，王玲.基于錨節(jié)點(diǎn)選擇的無線傳感器網(wǎng)絡(luò)定位算法［J］.計(jì)算機(jī)研究與應(yīng)用，2010，47（S）:31-34. Wang Zhu，Hao Xiaoqiang，Wang Ling.Choice of Location-Based Anchor Node Localization Algorithmfor Wireless Sensor Networks［J］.Journal of Computer Research and Development，2010，47（S）:31-34.

［11］李娟，劉禹，錢志鴻.于雙通信半徑的傳感器網(wǎng)DV-Hop定位算法［J］.吉林大學(xué)學(xué)報(bào)（工學(xué)版），2014，44（2）:502-507. LI Juan，LIU Yu，QIAN Zhihong，et al.Improved DV-Hop Localization Algorithm Based on Two Communication Ranges for Wireless Sensor Network［J］.Journal of Jilin University（Engineering and Technology Edition），2014，44（2）:502-507.

［12］黃炎炎，陳向東，倪進(jìn)權(quán)，等.改進(jìn)的DV-Hop無線傳感器網(wǎng)絡(luò)定位算法［J］.通信技術(shù)，2014，47（7）:765-769. HUANG Y Y，CHEN X D，NI J Q，et al.An Improved DV-Hop Localization Algorithm for Wireless Sensor Networks［J］.Communications Technology，2014，47（7）:765-769.

［13］劉士興，黃俊杰，劉宏銀，等.基于多通信半徑的加權(quán)DV-Hop定位算法［J］.傳感技術(shù)學(xué)報(bào)，2015，28（6）:883-887. LIU S X，HUANG J J，LIU H Y，et al.An Improving DV-Hop Algorithm Based on Multi Communication Radius［J］.Chinese Journal of Sensors and Actuators，2015，28（6） :883-887.

［14］馬淑麗，趙建平.無線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)［J］.通信技術(shù)，2015，48（7）:840-844. MA S L，ZHAO J P，ZHANG B T.The Improvement of DV-Hop Algorithm in Wirless Sensor Networks［J］.Communications Technology，2015，48（7）:840-844.

［15］馬淑麗，趙建平，張炳婷，等.WSN中節(jié)點(diǎn)定位方法的改進(jìn)［J］.通信技術(shù)，2015，48（4）:453-457. MA S L，ZHAO J P，ZHANG B T，et al.Improvement of Node Locating Algorithm in WSN［J］.Communications Technology，2015，48（4）:453-457；

［16］Zhou H，Xia S，Jin M，et al.Localized and Precise Boundary Detection in 3-D Wireless Sensor Networks［J］.IEEE/ACM Transactions on Networking，2014（99）:1-1.

［17］MaungNAM，KawaiM.ExperimentalEvaluationsofRSSThreshold-Based Optimised DV-HOP Localisation for Wireless Ad-Hoc Networks［J］.IET，Electronics Letters，2014，50（17）:1246-1248.

［18］魏全瑞，劉俊，韓九強(qiáng).改進(jìn)的無線傳感器網(wǎng)絡(luò)無偏距離估計(jì)與節(jié)點(diǎn)定位算法［J］.西安交通大學(xué)學(xué)報(bào)，2014，48（6）:1-6. WEI Quanrui，LIU Jun，HAN Jiuqiang.An Improved DV-Hop Node Localization Algorithm Based on Unbiased Estimation for Wireless Sensor Networks［J］.Journal of Xi'an Jiaotong University，2014，48（6）:1-6.

［19］嵇瑋瑋，劉中.定位算法在隨機(jī)傳感器網(wǎng)絡(luò)中的應(yīng)用研究［J］.電子與信息學(xué)報(bào)，2008，30（4）:970-974. Ji Weiwei，Liu Zhong.Study on the Application of DY-Hop Localization Algorithms to Random Sensor Networks［J］.Journal of Electronics&Information Technology，2008，30（4）:970-974.

［20］宮娜娜，武海艷.傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布均勻性與定位性能的關(guān)系［J］.電子測量技術(shù)，2014，37（12）:80-85. GONG N N，WU H Y.The Relationship between the Sensor Network Node Distribution Uniformity and Positioning Performance ［J］.Electronic Measurement Technology，2014，37（12）:80-85.

［21］Yousi Zheng，Lei Wan，Zhi Sun，et al.A Long Range DV-Hop Localization Algorithm with Placement Strategy in Wireless Sensor Networks［C］//Wirless Communications，Networking and Mobile Computing，WiCOM 4th International Conference on［s.l.］: IEEE，2008:1-5.

馬淑麗（1989-），女，碩士研究生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、無線通信技術(shù)，marrymiffy@sohu.com；

趙建平（1964-），男，教授，主要研究方向?yàn)闊o線通信技術(shù)。

Multi Communication Ranges DVHop Localization Algorithm for Wireless Sensor Network*

MA Shuli，ZHAO Jianping*
（College of Physics Engineering，Qufu Normal University，Qufu Shandong 273165，China）

In order to realize high precision positioning of DV-Hop localization algorithm based on rang-free in wireless sensor network，this paper improved the DV-Hop localization algorithm based on 2 or 3 communication radius，and improved the average per hop distance by the least mean square error criterion.The anchor node average per hop distance is repaired in the best index value.MATLAB simulation results show that the improved algorithm can improve the localization accuracy in randomly distributed environment，further enhance the localization accuracy in the best index，and greatly improve localization accuracy in the anchor node deploying artificial environment.The improved algorithm can achieve high precision positioning without increasing the number of flood and the cost in the network.

wireless sensor network；node localization；dv-hop；least mean square error criterion；nodes distribution

TP393

A

1004-1699（2016）04-0593-08

項(xiàng)目來源:國家自然科學(xué)基金項(xiàng)目（11302118）；山東省自然科學(xué)基金項(xiàng)目（ZR2014FM011）；山東省高等學(xué)?？萍加?jì)劃項(xiàng)目（J12LN08）

2015-10-09修改日期:2016-01-15