基于DV-Hop算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法

歐永青

（中郵建技術(shù)有限公司，江蘇 南京 210012）

0 引 言

在科技迅速發(fā)展的今天，無(wú)線傳感器網(wǎng)絡(luò)在科技研究領(lǐng)域中的熱度始終高居不下。其中，無(wú)線傳感器網(wǎng)絡(luò)未知節(jié)點(diǎn)的定位方法是其所有研究方向中一個(gè)比較主流的方向，這是由于網(wǎng)絡(luò)節(jié)點(diǎn)定位是所有研究方向中的重要的前提，無(wú)論是自動(dòng)監(jiān)測(cè)、自動(dòng)控制還是進(jìn)行多設(shè)備無(wú)線通信，監(jiān)測(cè)對(duì)象的位置坐標(biāo)都是必不可少的基礎(chǔ)信息，確定網(wǎng)絡(luò)節(jié)點(diǎn)的位置信息對(duì)無(wú)線傳感器網(wǎng)絡(luò)的研究工作具有十分重要的意義[1]。利用傳統(tǒng)網(wǎng)絡(luò)節(jié)點(diǎn)定位方法，定位精度低，且隨著網(wǎng)絡(luò)錨節(jié)點(diǎn)比例、密度、結(jié)構(gòu)的變化，其產(chǎn)生的誤差較大，不利于后續(xù)工作。鑒于此，本文考慮節(jié)點(diǎn)定位精度，針對(duì)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法進(jìn)行了設(shè)計(jì)和研究，并在其中采用了DV-Hop算法?；贒V-Hop算法的定位技術(shù)省略了測(cè)距這一比較煩瑣的步驟，大大降低了工作難度，簡(jiǎn)化了工作流程，且該算法對(duì)硬件的要求低，可擴(kuò)展性好，可適應(yīng)各種類型的無(wú)線傳感器網(wǎng)絡(luò)，同時(shí)不易受到信標(biāo)節(jié)點(diǎn)數(shù)量、類別、密度等因素的影響，實(shí)現(xiàn)過(guò)程簡(jiǎn)單，定位精度較高。在實(shí)驗(yàn)論證中，將設(shè)計(jì)的方法與傳統(tǒng)定位方法進(jìn)行了分析比較，結(jié)果證明基于DV-Hop算法的定位方法在不同網(wǎng)絡(luò)錨節(jié)點(diǎn)比例的條件下依然能保持較高的定位精度，可以改善傳統(tǒng)定位方法定位誤差大的缺陷。

1 利用DV-Hop算法設(shè)計(jì)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法

定位無(wú)線傳感器網(wǎng)絡(luò)未知節(jié)點(diǎn)的方法根據(jù)是否需要測(cè)量節(jié)點(diǎn)間的距離而不同，一般情況下，將節(jié)點(diǎn)定位技術(shù)歸為2類，測(cè)距定位和免測(cè)距定位技術(shù)。利用測(cè)距技術(shù)定位節(jié)點(diǎn)，不僅定位流程復(fù)雜，而且定位精度較低。為了獲得良好的定位精度，本文采用免測(cè)距流程的DV-Hop算法實(shí)現(xiàn)節(jié)點(diǎn)定位[2]。其算法流程如圖1所示。

圖1 DV-Hop算法流程

DV-Hop定位算法是在距離矢量計(jì)算的基礎(chǔ)上提出來(lái)的，利用DV-Hop算法定位未知節(jié)點(diǎn)需要信標(biāo)節(jié)點(diǎn)在網(wǎng)絡(luò)中進(jìn)行隨機(jī)廣播信息，然后通過(guò)最小跳數(shù)計(jì)算待測(cè)節(jié)點(diǎn)之間的距離，求解待測(cè)節(jié)點(diǎn)的位置坐標(biāo)后對(duì)未知節(jié)點(diǎn)坐標(biāo)進(jìn)行位置修正。至此，完成無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位。

1.1 信標(biāo)節(jié)點(diǎn)信息廣播

錨節(jié)點(diǎn)在網(wǎng)絡(luò)中采用隨機(jī)撒播（也叫泛洪）的方式將自身信息廣播出去，這里的信息包括自身坐標(biāo)以及跳數(shù)，使得周邊的鄰居節(jié)點(diǎn)接收其所散播的信息并隨機(jī)組成一個(gè)數(shù)據(jù)包，進(jìn)而與其通信范圍內(nèi)的所有鄰居節(jié)點(diǎn)實(shí)現(xiàn)雙向通信，通過(guò)這個(gè)過(guò)程來(lái)計(jì)算網(wǎng)絡(luò)中全部節(jié)點(diǎn)的最小跳數(shù)[3]。

錨節(jié)點(diǎn)廣播信息的具體過(guò)程為信標(biāo)節(jié)點(diǎn)根據(jù)距離矢量路由協(xié)議，采用泛洪的方式向其周圍的鄰居節(jié)點(diǎn)傳播信息，鄰居節(jié)點(diǎn)接收到信息并生成一個(gè)包含信標(biāo)節(jié)點(diǎn)標(biāo)識(shí)符、自身坐標(biāo)、信號(hào)強(qiáng)度以及初始值為0的跳數(shù)信息的數(shù)據(jù)包，數(shù)據(jù)包的結(jié)構(gòu)如圖2所示。

圖2 信標(biāo)節(jié)點(diǎn)數(shù)據(jù)包信息結(jié)構(gòu)

根據(jù)圖2可知，當(dāng)信標(biāo)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)接收到其傳播的信息時(shí)，會(huì)通過(guò)標(biāo)記ID的形式記錄該數(shù)據(jù)包之前是否已經(jīng)接收過(guò)，若是重復(fù)接收且信標(biāo)節(jié)點(diǎn)與該鄰居節(jié)點(diǎn)之間的跳數(shù)小于信標(biāo)節(jié)點(diǎn)傳播的跳數(shù)信息，則舍棄該數(shù)據(jù)包[4]。然后繼續(xù)接收并分析下一個(gè)數(shù)據(jù)包，保留最小跳數(shù)，忽略較大的跳數(shù)信息，同時(shí)將跳數(shù)值增加1位，再次將該數(shù)據(jù)包轉(zhuǎn)發(fā)到網(wǎng)絡(luò)中。在整個(gè)過(guò)程中，要一直保證信標(biāo)節(jié)點(diǎn)與網(wǎng)絡(luò)中的未知節(jié)點(diǎn)間的跳數(shù)距離為最小值。

1.2 計(jì)算平均跳距

信標(biāo)節(jié)點(diǎn)在經(jīng)過(guò)第一階段的隨機(jī)散播信息后，每個(gè)鄰居節(jié)點(diǎn)都通過(guò)標(biāo)記ID的方式保留了一張網(wǎng)絡(luò)路由信息，該信息保存了當(dāng)前節(jié)點(diǎn)與其他所有信標(biāo)節(jié)點(diǎn)之間最小跳數(shù)，根據(jù)該表可以計(jì)算得到待測(cè)節(jié)點(diǎn)j與信標(biāo)節(jié)點(diǎn)i之間的最小跳數(shù)，計(jì)算公式為

式中：(xi,yi)為已知小波節(jié)點(diǎn)的位置坐標(biāo)；(xj,yj)為待測(cè)節(jié)點(diǎn)的坐標(biāo)；hij為信標(biāo)節(jié)點(diǎn)與待測(cè)節(jié)點(diǎn)之間的最小跳數(shù)。

在這個(gè)階段中，網(wǎng)絡(luò)中的任意階段也會(huì)接收到多個(gè)信標(biāo)節(jié)點(diǎn)傳播來(lái)的跳數(shù)信息，而待測(cè)節(jié)點(diǎn)只標(biāo)記最初接收到的跳數(shù)作為自己的平均最小跳數(shù)，這個(gè)策略確保了待測(cè)節(jié)點(diǎn)能夠從與其距離最近的信標(biāo)節(jié)點(diǎn)接收最小跳數(shù)信息。

計(jì)算出待測(cè)節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間的最小跳數(shù)值后，信標(biāo)節(jié)點(diǎn)把帶有最小跳數(shù)值和生存期字段的信息轉(zhuǎn)發(fā)到網(wǎng)絡(luò)中的其他錨節(jié)點(diǎn)，待測(cè)節(jié)點(diǎn)接收到期傳播的信息后，在多個(gè)傳播跳數(shù)信息的信標(biāo)節(jié)點(diǎn)中抓取一個(gè)距離自己最近的信標(biāo)節(jié)點(diǎn)，同時(shí)舍棄距離較遠(yuǎn)的剩余信標(biāo)節(jié)點(diǎn)，并利用最小跳數(shù)值計(jì)算自身所在位置與各個(gè)信標(biāo)節(jié)點(diǎn)間的每跳平均距離[5]。利用如下公式計(jì)算每跳平均距離

式中：Dij為信標(biāo)節(jié)點(diǎn)i與待測(cè)節(jié)點(diǎn)j之間的平均跳距；hij為信標(biāo)節(jié)點(diǎn)與待測(cè)節(jié)點(diǎn)間的最小跳段數(shù)距離。

在每跳平均距離基礎(chǔ)之上采用三邊測(cè)量法，根據(jù)幾何位置關(guān)系對(duì)未知節(jié)點(diǎn)進(jìn)行精準(zhǔn)定位。

1.3 定位未知節(jié)點(diǎn)坐標(biāo)

在對(duì)無(wú)線網(wǎng)絡(luò)傳感器未知節(jié)點(diǎn)的定位過(guò)程中，最廣泛使用的定位方法是三邊測(cè)量法。經(jīng)研究表明，該方法定位精度較高，可準(zhǔn)確定位待測(cè)節(jié)點(diǎn)坐標(biāo)，因此本文也采用三邊測(cè)量法來(lái)定位網(wǎng)絡(luò)未知節(jié)點(diǎn)[6]。在一個(gè)二維平面內(nèi)，只有明確未知節(jié)點(diǎn)與多個(gè)信標(biāo)節(jié)點(diǎn)之間的平均距離D，才能準(zhǔn)確獲得位置節(jié)點(diǎn)的位置坐標(biāo)。

在某無(wú)線傳感器網(wǎng)絡(luò)中隨機(jī)設(shè)置A、B、C3個(gè)錨節(jié)點(diǎn)，其位置坐標(biāo)分別用(xa,ya)、(xb,yb)和(xc,yc)表示，且其與待測(cè)節(jié)點(diǎn)之間的每跳距離為D1、D2、D3；設(shè)未知節(jié)點(diǎn)U的位置坐標(biāo)為(x,y)，利用三邊測(cè)量法，根據(jù)空間位置關(guān)系，則

求解公式（3）可以得到未知節(jié)點(diǎn)U的坐標(biāo)(x,y)為

為了保證計(jì)算結(jié)果的準(zhǔn)確性，同時(shí)為了提高定位精度，通常需要采用驗(yàn)算的方式來(lái)確定未知節(jié)點(diǎn)的坐標(biāo)是否準(zhǔn)確。具體方法為：將未知節(jié)點(diǎn)與已知精度交換位置，即將已知當(dāng)做未知，將求得的未知節(jié)點(diǎn)坐標(biāo)當(dāng)做已知，利用反向推理法來(lái)驗(yàn)證上述計(jì)算過(guò)程求得的位置坐標(biāo)與實(shí)際坐標(biāo)是否存在偏差，從而得知估算的位置信息是否準(zhǔn)確。

1.4 待測(cè)節(jié)點(diǎn)位置修正

假設(shè)網(wǎng)絡(luò)中存在一信標(biāo)節(jié)點(diǎn)，用B表示，對(duì)于在網(wǎng)絡(luò)中的未知節(jié)點(diǎn)i，利用式（1）和式（2），計(jì)算出錨節(jié)點(diǎn)與待測(cè)節(jié)點(diǎn)間的跳距，然后利用節(jié)點(diǎn)坐標(biāo)計(jì)算方法求出信標(biāo)節(jié)點(diǎn)的位置坐標(biāo)，再將計(jì)算結(jié)果與其真實(shí)坐標(biāo)進(jìn)行相減計(jì)算，可以得到信標(biāo)節(jié)點(diǎn)的位置修正因子。計(jì)算公式為

式中：(xb,yb)為信標(biāo)節(jié)點(diǎn)B的真實(shí)坐標(biāo)；(xi,yi)為信標(biāo)節(jié)點(diǎn)計(jì)算得出的坐標(biāo)。利用該公式計(jì)算求出所有已知信標(biāo)節(jié)點(diǎn)的位置修正因子后，根據(jù)如下公式計(jì)算出網(wǎng)絡(luò)平均修正因子

式中：n為網(wǎng)絡(luò)中西部節(jié)點(diǎn)的數(shù)量。

基于網(wǎng)絡(luò)平均修正因子，對(duì)位置節(jié)點(diǎn)位置坐標(biāo)進(jìn)行修正，公式為

式中：(Δx,Δy)為網(wǎng)絡(luò)平均修正因子；(x,y)為未知節(jié)點(diǎn)初始計(jì)算位置坐標(biāo)；(x′,y′)為經(jīng)過(guò)修正后未知節(jié)點(diǎn)的最終位置坐標(biāo)。

2 實(shí)驗(yàn)論證

2.1 實(shí)驗(yàn)準(zhǔn)備

為了進(jìn)一步驗(yàn)證本文提出的節(jié)點(diǎn)定位法具有更好的有效性，在MATLAB7.0仿真軟件開展仿真實(shí)驗(yàn)。在設(shè)置實(shí)驗(yàn)環(huán)境以及算法參數(shù)時(shí)，為了確保實(shí)驗(yàn)過(guò)程和結(jié)果具有一定的真實(shí)性和可比性，將網(wǎng)絡(luò)中400 m×400 m的正方形作為實(shí)驗(yàn)仿真的監(jiān)測(cè)區(qū)域。網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都極不均勻地分布在監(jiān)測(cè)區(qū)域中，共計(jì)500個(gè)，其中大部分為未知節(jié)點(diǎn)，只有很少一部分為已知坐標(biāo)位置的信標(biāo)節(jié)點(diǎn)。其位置獲取方式為通過(guò)GPS定位和人工部署，為了避免其他因素對(duì)實(shí)驗(yàn)結(jié)果可能產(chǎn)生的干擾，將節(jié)點(diǎn)的通信半徑統(tǒng)一設(shè)為40 m[7]。本次仿真的環(huán)境參數(shù)設(shè)置見表1。

表1 仿真環(huán)境參數(shù)設(shè)置

2.2 實(shí)驗(yàn)說(shuō)明

在對(duì)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位中，一般將絕對(duì)定位誤差作為評(píng)價(jià)標(biāo)準(zhǔn)，其代表未知節(jié)點(diǎn)的計(jì)算坐標(biāo)與實(shí)際坐標(biāo)間的偏差，是一個(gè)標(biāo)量指標(biāo)。絕對(duì)定位誤差計(jì)算公式為

式中：error為節(jié)點(diǎn)絕對(duì)定位誤差；為利用前文設(shè)計(jì)的方法計(jì)算求出的節(jié)點(diǎn)坐標(biāo)；(xi,yi)為未知節(jié)點(diǎn)的真實(shí)坐標(biāo)。

2.3 實(shí)驗(yàn)結(jié)果

為了直觀地比較出本文設(shè)計(jì)的定位算法的性能優(yōu)劣，對(duì)同一無(wú)線傳感器網(wǎng)絡(luò)在不同錨節(jié)點(diǎn)比例的條件下，采用對(duì)比方法，將傳統(tǒng)定位方法與設(shè)計(jì)的定位方法進(jìn)行節(jié)點(diǎn)定位對(duì)比，并根據(jù)定位結(jié)果分析2種方法的定位誤差。為了保證實(shí)驗(yàn)結(jié)果的可靠性，對(duì)該網(wǎng)絡(luò)共進(jìn)行100次仿真實(shí)驗(yàn)，并取100次定位誤差的平均值作為本實(shí)驗(yàn)的最終絕對(duì)定位誤差。對(duì)比結(jié)果如圖3所示。

圖3 對(duì)比結(jié)果

由圖3可知，無(wú)線傳感器網(wǎng)絡(luò)中的錨節(jié)點(diǎn)比例小于15%時(shí)，傳統(tǒng)定位方法的定位誤差比較小，然而隨著錨節(jié)點(diǎn)比例的不斷增大，其定位誤差也逐漸變大。反觀本文設(shè)計(jì)的定位方法，其絕對(duì)定位誤差隨著網(wǎng)絡(luò)中錨節(jié)點(diǎn)比例的上升一直呈單調(diào)下降趨勢(shì)，由此可以證明，本文設(shè)計(jì)的節(jié)點(diǎn)定位方法的定位精度遠(yuǎn)遠(yuǎn)高于傳統(tǒng)定位方法，能夠滿足實(shí)際應(yīng)用中對(duì)定位精度的要求，該算法的適應(yīng)性更強(qiáng)。

3 結(jié) 論

本文利用DV-Hop算法設(shè)計(jì)并研究了無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法。通過(guò)信標(biāo)節(jié)點(diǎn)在網(wǎng)絡(luò)中泛洪廣播的方式將自身信息以數(shù)據(jù)包的形式傳播給鄰居節(jié)點(diǎn)，使得待測(cè)節(jié)點(diǎn)獲得自己與已知信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，基于最小跳數(shù)，計(jì)算兩者之間的平均跳距，根據(jù)空間幾何關(guān)系，采用圓心三邊測(cè)量法，計(jì)算得出待測(cè)節(jié)點(diǎn)的位置坐標(biāo)，并利用位置修正因子對(duì)位置節(jié)點(diǎn)的位置坐標(biāo)進(jìn)行修正，在一定程度上提高了定位精度。經(jīng)實(shí)驗(yàn)論證表明，本文設(shè)計(jì)的基于DV-Hop算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法，在不同網(wǎng)絡(luò)條件下，其絕對(duì)定位誤差較小，可實(shí)現(xiàn)精準(zhǔn)定位，可以成為該領(lǐng)域中一種有效的節(jié)點(diǎn)定位方案。