胡玉蘭,于 溪,趙青杉

(忻州師范學(xué)院，山西 忻州 034000)

0 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)是指由大量的傳感器構(gòu)成的分布式傳感器網(wǎng)絡(luò).由于其具有低功耗、體積小、價(jià)格低等優(yōu)點(diǎn)進(jìn)而被廣泛利用.因此WSN在監(jiān)測(cè)網(wǎng)絡(luò)部署區(qū)域發(fā)揮著重要的作用，其中的DV-Hop定位機(jī)制也廣受歡迎，人們針對(duì)其存在的缺陷與不足在各種方向進(jìn)行改進(jìn)完善，此文即針對(duì)其中一種改進(jìn)的算法進(jìn)行的研究.

1 研究背景及現(xiàn)狀

節(jié)點(diǎn)定位在無線傳感網(wǎng)絡(luò)中起著至關(guān)重要的作用.由于無需測(cè)距定位技術(shù)的低成本優(yōu)勢(shì)，許多學(xué)者致力于改進(jìn)其算法進(jìn)而在低成本的前提下減小定位誤差：劉珍等人針對(duì)細(xì)菌覓食優(yōu)化算法的缺陷提出了基于非線性遞減的余弦自適應(yīng)步長，并改進(jìn)細(xì)菌位置的更新方式、優(yōu)勝略汰的選擇標(biāo)準(zhǔn)和遷徙方式對(duì)原算法進(jìn)行優(yōu)化[1].劉文遠(yuǎn)等人針對(duì)DV-Hop節(jié)點(diǎn)定位算法的缺陷引入權(quán)重及有選擇的使用錨節(jié)點(diǎn)估計(jì)位置，進(jìn)而減小誤差[2].范海紅等人都是通過加權(quán)重增強(qiáng)DV-Hop定位算法的準(zhǔn)確率[3].張中芳等人提出了利用量子粒子群優(yōu)化算法對(duì)DV-Hop節(jié)點(diǎn)定位算法進(jìn)行優(yōu)化求解提高定位精度[4].童宇行等人是采用限制跳數(shù)的方法，將已經(jīng)定位的未知節(jié)點(diǎn)變?yōu)樾艠?biāo)節(jié)點(diǎn)繼續(xù)輔助定位[5].夏少波等人是采用節(jié)點(diǎn)密度區(qū)域劃分的方法，依據(jù)網(wǎng)絡(luò)的連通度和節(jié)點(diǎn)密度限制參與估算的信標(biāo)節(jié)點(diǎn)的跳數(shù)[6].景路路等人是利用不同的信標(biāo)節(jié)點(diǎn),計(jì)算出不同的平均跳距,使它更接近于實(shí)際的平均每跳距離[7].針對(duì)通過跳距優(yōu)化后的定位算法定位誤差的積累造成定位精度下降的問題，提出了一種跳距優(yōu)化的改進(jìn)型DV-Hop定位算法，引入跳數(shù)細(xì)化的方法，來減小計(jì)算跳距時(shí)產(chǎn)生的誤差，進(jìn)而細(xì)化平均每跳距離，使得未知節(jié)點(diǎn)定位誤差率減小，最后利用最小二乘法求位置節(jié)點(diǎn)坐標(biāo).

2 DV-Hop節(jié)點(diǎn)定位算法

2.1 無線網(wǎng)絡(luò)技術(shù)

無線傳感技術(shù)在通信、信息交流等方面給我們帶來了不可忽視的便利，近些年來，各類無線傳感技術(shù)層出不窮，尤其是利用無線傳感而發(fā)展起來的節(jié)點(diǎn)定位技術(shù).現(xiàn)有的節(jié)點(diǎn)定位算法可分為兩類[8]：一類是需要測(cè)量距離的算法，目前這類測(cè)距技術(shù)主要包括有TOA ( Timeof Arrival) 、RSSI (Received Signal Strength Indicator) ，AOA ( Angleof Arrival )和TDOA ( Time Difference on Arrival) 等，雖然此類技術(shù)能夠更加精確的定位，但網(wǎng)絡(luò)中的節(jié)點(diǎn)需要增加作為測(cè)距的硬件，增加了成本；另一類是無需測(cè)量距離的節(jié)點(diǎn)定位算法，其中包括有、質(zhì)心算法( CentroidAlgorithm)，DV-Hop( DistanceVector-Hop) 算法等，此類型算法不僅有效降低成本、而且效率高、受環(huán)境因素影響較小，雖然定位誤差率稍高，但其在可接受范圍內(nèi)，是可以滿足大部分需求的，因此投入使用非常廣泛.

2.2 傳統(tǒng)DV-Hop節(jié)點(diǎn)定位算法

圖1 傳統(tǒng)算法實(shí)現(xiàn)的流程

DV-Hop定位算法是一種應(yīng)用非常廣泛的定位方法，它是由美國路特格斯大學(xué)的Dragos Niculescu等人提出的一種不需要測(cè)量距離的定位機(jī)制，它是利用多個(gè)知道位置信息的信標(biāo)節(jié)點(diǎn)來實(shí)現(xiàn)未知節(jié)點(diǎn)的定位，其定位的覆蓋面積較廣[9，10].

傳統(tǒng)DV-Hop定位算法的基本流程：

其中估算平均每跳距離部分，在已知兩個(gè)相鄰信標(biāo)節(jié)點(diǎn)之間的距離以及兩者之間的最小跳數(shù)，可利用式(1) 估算平均每跳距離，其中，(xi，yi)，(xj，yj)是信標(biāo)節(jié)點(diǎn)i、j的坐標(biāo)，hj是信標(biāo)節(jié)點(diǎn)i與j(i≠j)之間的跳段數(shù).

利用式(2)則可計(jì)算未知節(jié)點(diǎn)與信標(biāo)結(jié)點(diǎn)之間的距離.

(1)

di=hi×HopSizeij(i≠j).

(2)

圖2 傳統(tǒng)DV-Hop算法拓?fù)鋱D

下面是實(shí)際的舉例：

如圖2所示的拓?fù)鋱D，其中A1,A2,A3是信標(biāo)節(jié)點(diǎn)，N為欲求位置信息的未知節(jié)點(diǎn)，假設(shè)未知節(jié)點(diǎn)N從A2獲得校正值.采用上述公式，可以得到信標(biāo)節(jié)點(diǎn)A2的平均跳距為:

( 40 +86) / ( 2+ 5) = 18.

(3)

它與節(jié)點(diǎn)A1，A2，A3之間的距離分別為：54，36，54.

最后可利用三邊測(cè)量法確定節(jié)點(diǎn)N的位置.

DV-Hop算法不需要測(cè)量距離也不需未知節(jié)點(diǎn)知道自身位置信息，對(duì)節(jié)點(diǎn)的配置要求不高，可以減小開支，且結(jié)構(gòu)簡單，易于實(shí)現(xiàn).其缺點(diǎn)是估計(jì)的距離要大于實(shí)際距離，并且其受節(jié)點(diǎn)密度、信標(biāo)節(jié)點(diǎn)密度影響較大，誤差率不穩(wěn)定.

3 改進(jìn)的DV-Hop節(jié)點(diǎn)定位算法

3.1 基本思想

通過對(duì)傳統(tǒng)DV-Hop節(jié)點(diǎn)定位算法的分析可知，平均每跳距離的估算誤差嚴(yán)重影響了節(jié)點(diǎn)定位的準(zhǔn)確率，因此細(xì)化跳數(shù)顯得尤為重要.本次改進(jìn)通過細(xì)化通信半徑實(shí)現(xiàn)，分為3次實(shí)驗(yàn)，R指的是未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)都使用的通信半徑.

第一次實(shí)驗(yàn)新增的0.5R為信標(biāo)節(jié)點(diǎn)專用通信半徑.將信標(biāo)節(jié)點(diǎn)的信息發(fā)送面積分為兩種,即將所有節(jié)點(diǎn)分為兩種，如圖3所示，將兩個(gè)部分分別命名為A，B.由于A區(qū)域是最小區(qū)域，所以A區(qū)域內(nèi)的節(jié)點(diǎn)能接收到信標(biāo)節(jié)點(diǎn)傳遞距離在R內(nèi)的信息，而B區(qū)域的節(jié)點(diǎn)則只能接收到信標(biāo)節(jié)點(diǎn)傳遞距離大于0.5R的信息.

因此最小跳數(shù)從原來的1跳降低到了0.5跳，降低了原來因跳數(shù)的判斷產(chǎn)生的誤差.節(jié)點(diǎn)在收到信標(biāo)節(jié)點(diǎn)發(fā)來的信息后，再以R為半徑將此信息繼續(xù)傳播出去.最終，每個(gè)節(jié)點(diǎn)都獲得了到達(dá)信標(biāo)節(jié)點(diǎn)的最小跳數(shù).

第二次實(shí)驗(yàn)將信標(biāo)節(jié)點(diǎn)的信息發(fā)送面積分為四種,即將所有節(jié)點(diǎn)分為四種，如圖3.2所示，將兩個(gè)部分分別命名為A、B、C、D.最小跳數(shù)變?yōu)?.25跳.

圖3 實(shí)驗(yàn)一細(xì)化跳距示意圖圖4 實(shí)驗(yàn)二細(xì)化跳距示意圖

第三次實(shí)驗(yàn)將信標(biāo)節(jié)點(diǎn)的信息發(fā)送面積分為5種,即將所有節(jié)點(diǎn)分為5種，如圖4所示，將兩個(gè)部分分別命名為A，B，C，D，E.最小跳數(shù)變?yōu)?.2跳.

下面通過實(shí)例來分析：

圖5 實(shí)驗(yàn)三細(xì)化跳距示意圖圖6 細(xì)化跳距算法示例

以實(shí)驗(yàn)三為例，圖6與圖2作對(duì)比：A1與A2之間的跳數(shù)原來為2，經(jīng)過細(xì)化之后可分為0.4和1相加得1.4.A2與N之間的跳數(shù)原來為2，經(jīng)過細(xì)化之后可分為0.2和0.4相加得0.6.N與A3之間的跳數(shù)原來為3，經(jīng)過細(xì)化之后可分為0.8，0.6和0.6相加得2.

(4)

式(4)比式(3)更接近與真實(shí)值.

3.2 詳細(xì)步驟

以實(shí)驗(yàn)三為例：

第一步：獲取最小跳數(shù)

1)網(wǎng)絡(luò)初始化，信標(biāo)節(jié)點(diǎn)第一次向外傳遞發(fā)送自己的分組信息.當(dāng)信標(biāo)節(jié)點(diǎn)的信息傳播距離在0.2R以內(nèi)時(shí)，接收到信息的節(jié)點(diǎn)將最小跳數(shù)記為0.2.為了降低信息傳播的費(fèi)用支出，此時(shí)相鄰節(jié)點(diǎn)暫且不繼續(xù)信息的轉(zhuǎn)發(fā).

2)信標(biāo)節(jié)點(diǎn)第二次向外傳遞發(fā)送自己的信息分組.信標(biāo)節(jié)點(diǎn)的信息傳播距離在0.2R到0.4R之間，此時(shí)最小跳數(shù)的選擇同傳統(tǒng)的DV-Hop算法相同：若節(jié)點(diǎn)第一次收到信標(biāo)節(jié)點(diǎn)的分組信息，則最小跳數(shù)為0.4；若節(jié)點(diǎn)在此之前已經(jīng)收到過之前的信息分組，則舍棄較大的跳數(shù)值，因此最小跳數(shù)為之前的0.2.

3)信標(biāo)節(jié)點(diǎn)第三次、四、五次向外傳遞信息并獲得最小跳數(shù)原理同上.

第二步：估算平均每跳距離

經(jīng)過第一步的節(jié)點(diǎn)之間的信息傳送，可以得到相鄰信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù)，已知信標(biāo)節(jié)點(diǎn)的坐標(biāo)，可以利用勾股定理求得兩個(gè)信標(biāo)節(jié)點(diǎn)之間的實(shí)際距離，最后利用上述式(1)計(jì)算可得平均每跳距離.

第三步：求得未知節(jié)點(diǎn)坐標(biāo)

經(jīng)過前兩步的計(jì)算可以得到未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù)與平均每跳距離，利用上述式(2)的最小跳數(shù)乘以平均每跳距離可以求得未知節(jié)點(diǎn)距信標(biāo)節(jié)點(diǎn)的距離，最后利用最小二乘法求未知節(jié)點(diǎn)坐標(biāo).

實(shí)驗(yàn)一、二同上述步驟.

4 仿真結(jié)果分析

4.1 仿真實(shí)驗(yàn)環(huán)境

MATLAB中假設(shè)仿真環(huán)境為邊長100 m的正方形區(qū)域.

4.2 仿真實(shí)驗(yàn)部署

4.2.1 隨錨節(jié)點(diǎn)數(shù)目和節(jié)點(diǎn)變化的定位誤差率

在100*100的正方形區(qū)域隨機(jī)分布節(jié)點(diǎn)，分別在錨節(jié)點(diǎn)數(shù)目逐漸增加以及在節(jié)點(diǎn)數(shù)目逐漸增加的情況下平均定位誤差，相同比例的錨節(jié)點(diǎn)和節(jié)點(diǎn)情況下，對(duì)比傳統(tǒng)DV-Hop節(jié)點(diǎn)定位算法，實(shí)驗(yàn)進(jìn)行了10次，并將10次實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)到一起便于分析.并增加跳距細(xì)化程度，更改代碼，重新運(yùn)行，觀察結(jié)果.

圖7 仿真節(jié)點(diǎn)分布圖

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

本次實(shí)驗(yàn)的全部節(jié)點(diǎn)均為隨機(jī)分布，下圖7即為其中一次的節(jié)點(diǎn)分布圖.

4.4 仿真實(shí)驗(yàn)分析

由于節(jié)點(diǎn)是每次實(shí)驗(yàn)隨機(jī)分布的，因此只能通過傳統(tǒng)算法與改進(jìn)算法定位誤差的大致差值來判斷減小誤差的量.

通過圖8、圖9、圖10可以看出相比于傳統(tǒng)算法，改進(jìn)后的算法信息傳播距離細(xì)化程度越大，在錨節(jié)點(diǎn)數(shù)大于10后，隨錨節(jié)點(diǎn)變化的節(jié)點(diǎn)定位誤差減小的越多.

通過圖11、圖12、圖13可以看出相比于傳統(tǒng)算法，改進(jìn)后的算法信息傳播距離細(xì)化程度越大，隨節(jié)點(diǎn)變化的節(jié)點(diǎn)定位誤差減小的越多.

圖8 實(shí)驗(yàn)一隨錨節(jié)點(diǎn)變化仿真結(jié)果圖圖9 實(shí)驗(yàn)二隨錨節(jié)點(diǎn)變化仿真結(jié)果圖

圖10 實(shí)驗(yàn)三隨錨節(jié)點(diǎn)變化仿真結(jié)果圖圖11 實(shí)驗(yàn)一隨節(jié)點(diǎn)變化仿真結(jié)果圖

圖12 實(shí)驗(yàn)二隨節(jié)點(diǎn)變化仿真結(jié)果圖圖13 實(shí)驗(yàn)三隨節(jié)點(diǎn)變化仿真結(jié)果圖

5 結(jié)束語

本文首先對(duì)無線網(wǎng)絡(luò)技術(shù)做了分析概述，并詳細(xì)介紹傳統(tǒng)的DV-Hop節(jié)點(diǎn)定位算法，分析其優(yōu)缺點(diǎn)，明確誤差的來源.在此基礎(chǔ)上引入一種改進(jìn)的DV-Hop算法，此算法利用細(xì)化跳距的方式減小誤差，并由此算法提出進(jìn)一步的改進(jìn)想法：細(xì)化程度越高，誤差率越低.針對(duì)此想法在Matlab上分別針對(duì)信標(biāo)節(jié)點(diǎn)變化、節(jié)點(diǎn)變化進(jìn)行了兩種仿真實(shí)驗(yàn)，并通過實(shí)驗(yàn)進(jìn)一步證明了在錨節(jié)點(diǎn)數(shù)足夠大的情況下細(xì)化程度越高，誤差率越低.

在本次實(shí)驗(yàn)中，也遇到了許多困難，首先是對(duì)Matlab語言的不熟悉，導(dǎo)致對(duì)代碼的改進(jìn)不順利，以后會(huì)更加精進(jìn)對(duì)語言的學(xué)習(xí).其次本文都是在相同條件下進(jìn)行10次實(shí)驗(yàn)，盡可能減小拓?fù)浣Y(jié)構(gòu)的影響，通信半徑也會(huì)影響定位誤差率，未來會(huì)進(jìn)一步改進(jìn).