一種基于移動(dòng)信標(biāo)節(jié)點(diǎn)加余弦定理的DV-Hop改進(jìn)算法

胡平霞 丁鋒 鄧阿琴 曾斯 朱鵬

摘? ?要：為提高無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位精度，文章提出了一種基于移動(dòng)信標(biāo)節(jié)點(diǎn)加余弦定理的MCDV-Hop改進(jìn)算法。該算法從改變移動(dòng)信標(biāo)節(jié)點(diǎn)移動(dòng)軌跡基礎(chǔ)上通過余弦定理修正跳距，在模擬WSN場(chǎng)景下，通過仿真實(shí)驗(yàn)表明，MCDV-Hop改進(jìn)算法提高了網(wǎng)絡(luò)資源利用率，在一定程度上表現(xiàn)出較穩(wěn)定的定位精度。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò);定位;移動(dòng)信標(biāo)節(jié)點(diǎn);余弦定理

中圖分類號(hào)： TP393? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks， WSN）作為一個(gè)新的網(wǎng)絡(luò)模型在軍事、民用及商用領(lǐng)域都有著巨大的應(yīng)用價(jià)值，逐漸成為國內(nèi)外學(xué)者的研究熱點(diǎn)。由于無線傳感器網(wǎng)絡(luò)應(yīng)用的復(fù)雜性，網(wǎng)絡(luò)節(jié)點(diǎn)的位置信息顯得尤為重要，節(jié)點(diǎn)定位技術(shù)成為WSN的關(guān)鍵技術(shù)之一。節(jié)點(diǎn)定位技術(shù)是指在無線傳感器網(wǎng)絡(luò)中，通過已知節(jié)點(diǎn)位置信息估算未知節(jié)點(diǎn)位置信息的一種技術(shù)。在無線傳感器網(wǎng)絡(luò)中，已知節(jié)點(diǎn)稱為信標(biāo)節(jié)點(diǎn)，由于相對(duì)未知節(jié)點(diǎn)來說信標(biāo)節(jié)點(diǎn)成本高，且需硬件支持，因此通常根據(jù)實(shí)際應(yīng)用部署少量的信標(biāo)節(jié)點(diǎn)，通過信標(biāo)節(jié)點(diǎn)的位置信息來測(cè)算未知節(jié)點(diǎn)的位置。

根據(jù)節(jié)點(diǎn)定位過程中是否需要測(cè)量信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)間的距離，將定位算法分成免測(cè)距定位算法（Range-free）和基于測(cè)距定位算法（Range-based）兩種。其中，無需測(cè)距定位算法由于在不增加硬件開銷的情況下其定位精度基本上能滿足實(shí)際應(yīng)用，具有較大的研究?jī)r(jià)值，引起國內(nèi)外學(xué)者的關(guān)注。文獻(xiàn)[1～8]就不同的思路對(duì)非測(cè)距定位技術(shù)進(jìn)行不同的研究，提出了不同的解決方案。其中，文獻(xiàn)[5]介紹了一種利用最鄰近信標(biāo)節(jié)點(diǎn)的平均跳距以及加權(quán)后的M跳內(nèi)信標(biāo)節(jié)點(diǎn)的平均跳距，來測(cè)算未知節(jié)點(diǎn)的位置信息，M為增設(shè)的門限值。文獻(xiàn)[6]介紹了通過信標(biāo)節(jié)點(diǎn)的功率控制，通過信標(biāo)節(jié)點(diǎn)的輔助提出了基于全網(wǎng)信標(biāo)節(jié)點(diǎn)修正單個(gè)信標(biāo)節(jié)點(diǎn)的平均跳距。文獻(xiàn)[7]在經(jīng)典DV-Hop算法的基礎(chǔ)上，對(duì)節(jié)點(diǎn)間的跳數(shù)值和平均每跳跳距進(jìn)行校正和修正。文獻(xiàn)[8]使用加權(quán)雙曲線定位算法（WH）思想及加權(quán)DV-Hop（WDV-Hop）思想相結(jié)合的思路。非測(cè)距定位算法，不論是在理論方面，還是技術(shù)應(yīng)用方面，都是未來的重要研究方向，高精度的定位成為研究關(guān)鍵技術(shù)之一。本文所做的工作就是以提高定位精度為目標(biāo)提出改進(jìn)的DV-Hop算法。

2 介紹經(jīng)典算法

2.1經(jīng)典DV-Hop算法

經(jīng)典DV-Hop算法根據(jù)網(wǎng)絡(luò)中的跳數(shù)測(cè)算未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)直線距離，從而得到未知節(jié)點(diǎn)的位置信息。經(jīng)典DV-Hop算法由于不需要增加額外硬件開銷且計(jì)算量相對(duì)較小、容易實(shí)現(xiàn)等特點(diǎn)得到國內(nèi)外研究者的關(guān)注。經(jīng)典DV-Hop算法對(duì)未知節(jié)點(diǎn)的定位過程為三點(diǎn)。

（1）確定未知節(jié)點(diǎn)與網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)間的最小跳數(shù)值

信標(biāo)節(jié)點(diǎn)全網(wǎng)廣播本節(jié)點(diǎn)位置信息，其它傳感節(jié)點(diǎn)收到信息后保存自身到信標(biāo)節(jié)點(diǎn)數(shù)據(jù)信息，信標(biāo)節(jié)點(diǎn)i的位置信息表示為，未知節(jié)點(diǎn)到網(wǎng)絡(luò)中其它信標(biāo)節(jié)點(diǎn)i的最小跳數(shù)值表示為，該數(shù)據(jù)信息記為。

（2）估算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間的距離

①信標(biāo)節(jié)點(diǎn)自身平均跳距估算

公式1

通過公式1計(jì)算信標(biāo)節(jié)點(diǎn)間的平均跳距，，分別表示是信標(biāo)節(jié)點(diǎn)i、j的坐標(biāo)，是信標(biāo)節(jié)點(diǎn)i和信標(biāo)節(jié)點(diǎn)j之間的最小跳數(shù)。

②未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)距離估算

公式2

通過公式2來估算未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離，是未知節(jié)點(diǎn)選擇最近的信標(biāo)節(jié)點(diǎn)i的跳距平均值，是未知節(jié)點(diǎn)u到信標(biāo)節(jié)點(diǎn)v的最小跳數(shù)值。

（3）確定未知節(jié)點(diǎn)位置

網(wǎng)絡(luò)中的未知節(jié)點(diǎn)根據(jù)第（2）步的估算結(jié)果，建立自身的位置矩陣，形成線性方程式，最后通過最小二乘法計(jì)算未知節(jié)點(diǎn)位置。

2.2 基于移動(dòng)信標(biāo)節(jié)點(diǎn)的DV-Hop改進(jìn)算法

MADV-Hop[9]是一種基于移動(dòng)信標(biāo)節(jié)點(diǎn)的DV-Hop改進(jìn)算法，通過在固定位置配置移動(dòng)信標(biāo)節(jié)點(diǎn)，移動(dòng)信標(biāo)節(jié)點(diǎn)按一定軌跡移動(dòng)構(gòu)建出多個(gè)虛擬信標(biāo)節(jié)點(diǎn)、采用多個(gè)虛擬信標(biāo)節(jié)點(diǎn)的位置信息來估算未知節(jié)點(diǎn)位置，取多次估算的平均值。仿真結(jié)果表明，該算法在降低成本和提高定位精度方面都有不錯(cuò)的表現(xiàn)。

3 MCDV-Hop改進(jìn)算法

本文提出了一種基于移動(dòng)信標(biāo)節(jié)點(diǎn)加余弦定理的MCDV-Hop算法，優(yōu)化了移動(dòng)信標(biāo)節(jié)點(diǎn)位置及移動(dòng)軌跡，在一定程度上降低了信標(biāo)節(jié)點(diǎn)廣播浪費(fèi)，通過余弦定理修正跳距[10]提高定位精準(zhǔn)度。

3.1 改進(jìn)思路

（1）優(yōu)化移動(dòng)信標(biāo)節(jié)點(diǎn)部署及移動(dòng)軌跡

MADV-Hop算法部署的移動(dòng)信標(biāo)節(jié)點(diǎn)呈矩形分布，如圖1所示，在中心位置、四個(gè)角及區(qū)域內(nèi)部署Q、A1-A4、B1-B4共9個(gè)移動(dòng)信標(biāo)節(jié)點(diǎn)。其中，四個(gè)角的移動(dòng)信標(biāo)節(jié)點(diǎn)在廣播時(shí)，有一半的廣播信息面向區(qū)域外，存在廣播浪費(fèi)現(xiàn)象，因此對(duì)移動(dòng)信標(biāo)節(jié)點(diǎn)位置和移動(dòng)軌跡的優(yōu)化十分必要。

改進(jìn)后的算法在的監(jiān)測(cè)區(qū)域中的固定位置部署9個(gè)移動(dòng)信標(biāo)節(jié)點(diǎn)，如圖2所示。其中，信標(biāo)節(jié)點(diǎn)G部署在位置（），且為唯一的固定的信標(biāo)節(jié)點(diǎn)，a1-a4 4個(gè)移動(dòng)信標(biāo)節(jié)點(diǎn)分別部署在正方形監(jiān)測(cè)區(qū)域的4邊的中間（即）位置，而b1-b4 4個(gè)移動(dòng)信標(biāo)節(jié)點(diǎn)分別部署在距離4個(gè)邊緣的中間部分。

以移動(dòng)信標(biāo)節(jié)點(diǎn)a1、b1為例，它們各自按一定的間距△d沿著外圓和內(nèi)圓逆時(shí)針移動(dòng)，會(huì)形成一定數(shù)量的虛擬信標(biāo)節(jié)點(diǎn)。每次移動(dòng)到新位置就廣播一次位置信息，為減少浪費(fèi)，每次移動(dòng)的新位置不能與之前廣播過的虛擬信標(biāo)節(jié)點(diǎn)位置重復(fù)。當(dāng)全部移動(dòng)信標(biāo)節(jié)點(diǎn)所形成的虛擬信標(biāo)節(jié)點(diǎn)對(duì)自身位置廣播達(dá)到一定次數(shù)（一般取4次）或更多時(shí)，停止移動(dòng)。由于移動(dòng)信標(biāo)節(jié)點(diǎn)是沿圓形軌跡運(yùn)動(dòng)，移動(dòng)后的新位置坐標(biāo)在原位置基礎(chǔ)上，通過余弦定理和移動(dòng)距離△d進(jìn)行計(jì)算。

（2）余弦定理校正平均跳距

由于網(wǎng)絡(luò)中節(jié)點(diǎn)的分布存在緊密和稀疏的差異，當(dāng)節(jié)點(diǎn)稀疏且呈不均勻分布時(shí)經(jīng)典DV-Hop算法的定位結(jié)果會(huì)出現(xiàn)較大概率的誤差，從而影響了定位精度，通過余弦定理對(duì)估算后的平均跳距離進(jìn)行修正，減少誤差，提高定位精度。

根據(jù)連接到每個(gè)信標(biāo)節(jié)點(diǎn)最小跳數(shù)的傳輸路線，選擇路線中間節(jié)點(diǎn)。如圖3和圖4所示，為奇數(shù)時(shí)，選擇路徑的中間節(jié)點(diǎn)即可;為偶數(shù)時(shí)，選擇路徑中間的兩跳都將作為中間節(jié)點(diǎn)。其中，中間節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)連接所形成的夾角為。

可以證明[10]當(dāng)為奇數(shù)時(shí)：

公式3

當(dāng)為偶數(shù)時(shí)：

公式4

是兩個(gè)信標(biāo)節(jié)點(diǎn)間的跳次，是兩個(gè)信標(biāo)節(jié)點(diǎn)間的跳數(shù)。最后的校正調(diào)整值correct_ value可由平均跳距、實(shí)際跳距和跳數(shù)得出：

公式5

通過上述跳距校正值來校正跳距。

3.2 MCDV-Hop算法定位思想

改進(jìn)算法偽代碼描述如圖5所示，定位過程描述為八點(diǎn)。

（1）啟動(dòng)網(wǎng)絡(luò)并完成初始化。初始化工作包括節(jié)點(diǎn)信息、移動(dòng)信標(biāo)節(jié)點(diǎn)移動(dòng)軌跡。

（2）信標(biāo)節(jié)點(diǎn)使用洪泛算法廣播自身位置信息，廣播次數(shù)為4次。

（3）鄰節(jié)點(diǎn)處理到達(dá)的數(shù)據(jù)包。鄰節(jié)點(diǎn)判斷到達(dá)的數(shù)據(jù)包是不是首次來自該信標(biāo)節(jié)點(diǎn)，若是首次收到則直接保存;不是則比較當(dāng)前數(shù)據(jù)包的最小跳數(shù)和已經(jīng)保存數(shù)據(jù)包的最小跳數(shù)，選擇跳數(shù)較小的數(shù)據(jù)包保存。

（4）計(jì)算平均跳距，并計(jì)算未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離。

（5）修正平均跳距。選擇中間節(jié)點(diǎn)，獲得角度，使用余弦定理修正跳距，見公式3、公式4、公式5，使用修正后的平均跳距計(jì)算未知節(jié)點(diǎn)距離。

（6）估算未知節(jié)點(diǎn)位置坐標(biāo)。根據(jù)信標(biāo)節(jié)點(diǎn)坐標(biāo)信息和未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)間的距離信息建立位置矩陣，采用最小二乘法計(jì)算未知節(jié)點(diǎn)坐標(biāo)。

（7）信標(biāo)節(jié)點(diǎn)按△d移動(dòng)，更新位置后返回第（2）步。

（8）在未知節(jié)點(diǎn)至少得到3次以上自身坐標(biāo)后，取平均值。

4 模擬仿真實(shí)驗(yàn)

4.1 仿真環(huán)境及參數(shù)說明

仿真實(shí)驗(yàn)在Matlab2016a環(huán)境下進(jìn)行，仿真參數(shù)如表1所述。

模擬WSN場(chǎng)景為二維平面區(qū)域，節(jié)點(diǎn)分布見圖6，其中三角形代表信標(biāo)節(jié)點(diǎn)，菱形代表未知節(jié)點(diǎn)。在100m×100m的正方形區(qū)域內(nèi)布置100個(gè)未知節(jié)點(diǎn)和9個(gè)移動(dòng)信標(biāo)節(jié)點(diǎn)，其中未知節(jié)點(diǎn)坐標(biāo)隨機(jī)，移動(dòng)信標(biāo)節(jié)點(diǎn)坐標(biāo)預(yù)設(shè)，初始化后所有節(jié)點(diǎn)均能正常工作。考慮未知節(jié)點(diǎn)坐標(biāo)的隨機(jī)性，選擇100次仿真計(jì)算的平均值作為對(duì)比結(jié)果。

平均相對(duì)定位誤差計(jì)算公式為：

公式6

其中U是節(jié)點(diǎn)數(shù)，v 是信標(biāo)節(jié)點(diǎn)數(shù)，M為通信半徑，truei為坐標(biāo)真實(shí)值，cali為坐標(biāo)估算值。

4.2 仿真實(shí)驗(yàn)結(jié)果

（1）定位誤差分析

改進(jìn)算法的定位誤差如圖7所示，縱軸為估算的節(jié)點(diǎn)坐標(biāo)與實(shí)際坐標(biāo)的偏差，橫軸為未知節(jié)點(diǎn)個(gè)數(shù)，最小誤差在5%以下，最大誤差約為25%。

（2）通信半徑對(duì)定位精度影響分析

在其它仿真參數(shù)不變的情況下改變通信半徑，對(duì)DV-Hop算法、MADV-Hop算法及改進(jìn)后的算法MCDV-Hop的定位精度進(jìn)行對(duì)比，定位半徑分別為20m、25m、30m、35m、40m、45m。圖8表明3種算法的定位精度在較大通信半徑情況下表現(xiàn)良好，隨著通信半徑增加定位誤差呈下降趨勢(shì)。DV-Hop算法定位精度受通信半徑變化的影響相對(duì)較小;通信半徑有30m以下時(shí)，改進(jìn)算法MCDV-Hop的定位精度由于移動(dòng)信標(biāo)節(jié)點(diǎn)按圓形軌跡運(yùn)動(dòng)，以減少廣播資源浪費(fèi)為前提犧牲少許覆蓋率，因此定位精度略小于原MCDV-Hop算法;MCDV-Hop改進(jìn)算法在通信半徑30m處開始保持平緩下降趨勢(shì)，因此當(dāng)通信半徑較大時(shí)，MCDV-Hop算法表現(xiàn)出比DV-Hop算法、MADV-Hop算法較優(yōu)的定位精度。

5 結(jié)束語

通過定位誤差仿真實(shí)驗(yàn)及通信半徑對(duì)定位精度仿真實(shí)驗(yàn)影響仿真實(shí)驗(yàn)可以看出，改進(jìn)算法MCDV-Hop仿真環(huán)境下保持較穩(wěn)定的定位誤差，對(duì)比DV-Hop算法和MADV-Hop算法，在節(jié)約資源降低成本前提下當(dāng)通信半徑達(dá)到一定值時(shí)，表現(xiàn)出穩(wěn)定、較小的定位精度。

基金項(xiàng)目：

1.衡陽市科技計(jì)劃項(xiàng)目（項(xiàng)目編號(hào)：2016KJ20）;

2.湖南省教育廳科學(xué)研究項(xiàng)目（項(xiàng)目編號(hào)：16C0565）;

3.衡陽市社會(huì)科學(xué)聯(lián)合會(huì)項(xiàng)目（項(xiàng)目編號(hào)：2017D107）;

4.湖南環(huán)境生物職業(yè)技術(shù)學(xué)院支柱工程項(xiàng)目（項(xiàng)目編號(hào)：湘環(huán)院教字〔2017〕46號(hào)）。

參考文獻(xiàn)

[1] Koen Langendoen，Niels Reijers.Distributed localization in wireless sensor networks： a quantitative comparison [J]. Computer Networks， 2003， 43（4）： 499-518.

[2] Zhongmin Pei，Zhidong Deng，Shuo Xu，Xiao Xu.Anchor-Free localization methord for moblie targets in coal mine wireless sensor networks[J].SENSORS， 2009， 9（4）：2836-2850.

[3] Yun Wang， Xiaodong Wang， Demin Wang，and Dharma P. Agrawal. Range-free localization algorithm using expected[J].IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS， 2009， 20（10）：1540-1552.

[4] He Yuanhua， Li Hongsheng.A distributed node localization algorithm based on believable factor wireless sensor network[A].Proceedings-5th International Conference on wireless Communications， Networking and Mobile Computing （WiCOM 2009） [C]. Beijing， 2009：1-4.

[5] HU Y，LI X. An improvement of DV-Hop localization algorithm for wireless sensor networks [J]. Telecommunication Systems，2013，53（1）：13-18.

[6] 陶志勇，魏強(qiáng)，劉影.多功率錨節(jié)點(diǎn)輔助的DV-Hop定位算法[J].計(jì)算機(jī)工程與應(yīng)用，2014（21） ：121-124，156.

[7] 夏少波，鄒建梅，朱曉麗，等.無線傳感器網(wǎng)絡(luò)DV-Hop定位算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用，2015（2） ：340-344.

[8] MASS-SANCHEZ J，RUIZ-IBARRA E，et al. Weighted Hyperbolic DV-Hop Positioning Node Localination Algorithm in WSNs[J].Wireless Personal Communications，2017，96（1-23）：5011-5033.

[9] 馮友兵，馬艷，魏玉婷.基于移動(dòng)錨節(jié)點(diǎn)的改進(jìn)DV-Hop算法[[J].計(jì)算機(jī)科學(xué)，2015， 42（s2）：277-279.

[10] Wu H， Deng M， Xiao L， et al. Cosine Theorem-based DV-Hop Localization Algorithm in Wireless Sensor Networks[J]. Information Technology Journal， 2011，10（2）：239-245.

作者簡(jiǎn)介：

胡平霞（1984-），女，漢族，湖南永州人，廣西師范大學(xué)，碩士，湖南環(huán)境生物職業(yè)技術(shù)學(xué)院，副教授;主要研究方向和關(guān)注領(lǐng)域：計(jì)算機(jī)軟件與理論、職業(yè)教育教學(xué)改革。

丁鋒（1984-），男，漢族，湖南常德人，中南林業(yè)科技大學(xué)，本科，湖南環(huán)境生物職業(yè)技術(shù)學(xué)院，助理研究員;主要研究方向和關(guān)注領(lǐng)域：計(jì)算機(jī)軟件與理論。

鄧阿琴（1980-），女，漢族，湖南醴陵人，南華大學(xué)，碩士，湖南環(huán)境生物職業(yè)技術(shù)學(xué)院，副研究員;主要研究方向和關(guān)注領(lǐng)域：網(wǎng)絡(luò)理論基礎(chǔ)研究。

曾斯（1984-），女，漢族，湖南衡陽人，衡陽師范學(xué)院，碩士，湖南環(huán)境生物職業(yè)技術(shù)學(xué)院，講師;主要研究方向和關(guān)注領(lǐng)域：網(wǎng)絡(luò)基礎(chǔ)理論研究、計(jì)算機(jī)教育。

朱鵬（1981-），男，漢族，湖南衡陽人，東華理工大學(xué)，本科，湖南環(huán)境生物職業(yè)技術(shù)學(xué)院，實(shí)驗(yàn)師;主要研究方向和關(guān)注領(lǐng)域：計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)用。