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

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

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

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

1 引言

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

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

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

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

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

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

公式1

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

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

公式2

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

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

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

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

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

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

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

3.1 改進(jìn)思路

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

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

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

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

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

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

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

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

公式3

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

公式4

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

公式5

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

3.2 MCDV-Hop算法定位思想

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

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

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

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

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

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

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

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

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

4 模擬仿真實驗

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

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

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

平均相對定位誤差計算公式為：

公式6

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

4.2 仿真實驗結(jié)果

（1）定位誤差分析

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

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

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

5 結(jié)束語

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

基金項目：

1.衡陽市科技計劃項目（項目編號：2016KJ20）;

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

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

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

參考文獻(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] 陶志勇，魏強，劉影.多功率錨節(jié)點輔助的DV-Hop定位算法[J].計算機工程與應(yīng)用，2014（21） ：121-124，156.

[7] 夏少波，鄒建梅，朱曉麗，等.無線傳感器網(wǎng)絡(luò)DV-Hop定位算法的改進(jìn)[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] 馮友兵，馬艷，魏玉婷.基于移動錨節(jié)點的改進(jìn)DV-Hop算法[[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.

作者簡介：

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

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

鄧阿琴（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ǔ)理論研究、計算機教育。

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