胡玉蘭,于 溪,趙青杉

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

0 引言

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

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

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

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

2.1 無線網(wǎng)絡技術

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

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

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

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

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

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

利用式(2)則可計算未知節(jié)點與信標結點之間的距離.

(1)

di=hi×HopSizeij(i≠j).

(2)

圖2 傳統(tǒng)DV-Hop算法拓撲圖

下面是實際的舉例：

如圖2所示的拓撲圖，其中A1,A2,A3是信標節(jié)點，N為欲求位置信息的未知節(jié)點，假設未知節(jié)點N從A2獲得校正值.采用上述公式，可以得到信標節(jié)點A2的平均跳距為:

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

(3)

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

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

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

3 改進的DV-Hop節(jié)點定位算法

3.1 基本思想

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

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

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

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

圖3 實驗一細化跳距示意圖圖4 實驗二細化跳距示意圖

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

下面通過實例來分析：

圖5 實驗三細化跳距示意圖圖6 細化跳距算法示例

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

(4)

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

3.2 詳細步驟

以實驗三為例：

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

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

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

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

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

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

第三步：求得未知節(jié)點坐標

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

實驗一、二同上述步驟.

4 仿真結果分析

4.1 仿真實驗環(huán)境

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

4.2 仿真實驗部署

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

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

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

4.3 仿真實驗結果圖

本次實驗的全部節(jié)點均為隨機分布，下圖7即為其中一次的節(jié)點分布圖.

4.4 仿真實驗分析

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

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

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

圖8 實驗一隨錨節(jié)點變化仿真結果圖圖9 實驗二隨錨節(jié)點變化仿真結果圖

圖10 實驗三隨錨節(jié)點變化仿真結果圖圖11 實驗一隨節(jié)點變化仿真結果圖

圖12 實驗二隨節(jié)點變化仿真結果圖圖13 實驗三隨節(jié)點變化仿真結果圖

5 結束語

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

在本次實驗中，也遇到了許多困難，首先是對Matlab語言的不熟悉，導致對代碼的改進不順利，以后會更加精進對語言的學習.其次本文都是在相同條件下進行10次實驗，盡可能減小拓撲結構的影響，通信半徑也會影響定位誤差率，未來會進一步改進.