時(shí)雨農(nóng)，劉海隆

(電子科技大學(xué)資源與環(huán)境學(xué)院，四川 成都 611731)

近年來(lái)，隨著無(wú)線傳感器技術(shù)的不斷發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)在生態(tài)環(huán)境監(jiān)測(cè)中也得到了大量應(yīng)用[1]。 其中野外生態(tài)環(huán)境要素的位置信息是重要的參數(shù)之一，因經(jīng)典的二維WSN 定位方法無(wú)法反映地形、植株高度等空間上的差異，會(huì)產(chǎn)生較大的誤差，因此針對(duì)WSN 的三維定位算法也就成為重要的研究方向[2-4]。

WSN 三維定位算法可以分為測(cè)距(rangebased)的和非測(cè)距(range-free)兩種[5]。 測(cè)距定位算法包括基于信號(hào)強(qiáng)度(RSS， Received Signal Strength)來(lái)進(jìn)行距離測(cè)量的RSSI 定位算法[6]、利用信號(hào)傳輸時(shí)延測(cè)距的TOA(Time of Arrival)定位算法[7]、基于到達(dá)時(shí)間差的TDOA(Time Difference of Arrival)定位算法[8]和綜合信號(hào)發(fā)射和接收角度與時(shí)延的AOA(Angle of Arrival)定位算法[9]等。 測(cè)距定位算法在精確度上有一定優(yōu)勢(shì)，但是因?yàn)閷?duì)設(shè)備有所要求，定位成本相對(duì)較高，且測(cè)量結(jié)果易受到WSN 節(jié)點(diǎn)所處環(huán)境的影響[10]，因此適用于室內(nèi)或者環(huán)境均勻分布的室外WSN 三維定位。 非測(cè)距定位算法包括基于三角形內(nèi)點(diǎn)測(cè)試法的APIT 算法[11]、基于網(wǎng)絡(luò)連通性的質(zhì)心定位算法[12]和基于距離矢量路由和GPS 定位思想的DV-Hop 定位算法[13]等。 非測(cè)距定位算法功耗較小，受環(huán)境影響不大，但是精度相對(duì)較低，適合用于低功耗、低成本的室外無(wú)線傳感器網(wǎng)絡(luò)定位[14]。

DV-Hop 定位算法是由Dragos Niculescu 等人提出的一種非測(cè)距定位算法[15]，其工作過(guò)程簡(jiǎn)單、易實(shí)現(xiàn)、并且不需要測(cè)距設(shè)備，但精度相對(duì)較差，有不少學(xué)者對(duì)其進(jìn)行了改進(jìn)[16-20]。 本文針對(duì)環(huán)境監(jiān)測(cè)中對(duì)于戶(hù)外復(fù)雜地形WSN 三維定位的需要，分析了傳統(tǒng)DV-Hop 算法誤差產(chǎn)生的原因，并在此基礎(chǔ)上以?xún)?yōu)化跳數(shù)和跳距為核心改進(jìn)了傳統(tǒng)算法，得到了一種更精確的DV-Hop 改進(jìn)三維定位算法。

1 三維DV-Hop 算法原理

傳統(tǒng)三維DV-Hop 定位算法主要分為以下三個(gè)步驟[21-28]:

①計(jì)算信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)間的最小跳數(shù)

首先網(wǎng)絡(luò)中的信標(biāo)節(jié)點(diǎn)(錨節(jié)點(diǎn))廣播自身信息，節(jié)點(diǎn)每接收到一個(gè)信息就更新它到該節(jié)點(diǎn)的最小跳數(shù)并處理后轉(zhuǎn)發(fā)；若該信息來(lái)自自身，則忽略，以確保所有節(jié)點(diǎn)都能保存自身與其他任一信標(biāo)節(jié)點(diǎn)間的最小跳數(shù)。

②估算未知節(jié)點(diǎn)的平均每跳距離

每個(gè)信標(biāo)節(jié)點(diǎn)確定自身位置之后，位于(xi，yi，zi)的信標(biāo)節(jié)點(diǎn)i就可根據(jù)以下公式確定自身的平均每跳距離:

式中:(xj，yj，zj)為錨節(jié)點(diǎn)j的位置，hopi，j為i、j兩個(gè)信標(biāo)節(jié)點(diǎn)之間的最短跳數(shù)。 得到平均每跳距離后，信標(biāo)節(jié)點(diǎn)將其廣播出去，而每個(gè)未知節(jié)點(diǎn)會(huì)記錄自己所接受的第一個(gè)數(shù)值，并將其作為自己的平均跳距。

③計(jì)算未知節(jié)點(diǎn)的位置

設(shè)未知節(jié)點(diǎn)U的位置為(x，y，z)，平均跳距為Hopsize，與其能直接通信的信標(biāo)節(jié)點(diǎn)位置和跳數(shù)分別為(x1，y1，z1)、(x2，y2，z2)、(x3，y3，z3)、…、(xn，yn，zn)，hop1、hop2、hop3、…、hopn。 則此點(diǎn)到相應(yīng)的信標(biāo)節(jié)點(diǎn)的預(yù)測(cè)距離分別為d1、d2、d3、…、dn，其中

根據(jù)四邊定位計(jì)算法則，可列出以下方程組:

誤差e為

根據(jù)最小二乘估計(jì)的優(yōu)化規(guī)則min(B-AX)T(B-AX)，對(duì)X求偏導(dǎo)，并令其值為0，則可以得到X的估計(jì)值:

2 三維DV-Hop 算法定位誤差成因分析

2.1 仿真參數(shù)設(shè)計(jì)

利用MATLAB R2020a 軟件根據(jù)以上步驟對(duì)經(jīng)典三維DV-Hop 算法進(jìn)行仿真，仿真具體數(shù)據(jù)如表1所示。 仿真結(jié)果如圖1(a)所示，圖中點(diǎn)號(hào)“·”代表未知節(jié)點(diǎn)，星號(hào)“*”代表信標(biāo)節(jié)點(diǎn)。

表1 經(jīng)典三維DV-Hop 算法仿真參數(shù)設(shè)置

根據(jù)經(jīng)典DV-Hop 定位算法，可計(jì)算出未知節(jié)點(diǎn)的具體位置，稱(chēng)為測(cè)算位置。 圖1(b)表示的是經(jīng)過(guò)經(jīng)典DV-Hop 算法計(jì)算后各未知節(jié)點(diǎn)的預(yù)測(cè)位置，圖中加號(hào)“+”節(jié)點(diǎn)表示預(yù)測(cè)的未知節(jié)點(diǎn)位置，圖中將各未知節(jié)點(diǎn)與其對(duì)應(yīng)的預(yù)測(cè)位置連接起來(lái)以表示對(duì)應(yīng)關(guān)系。

圖1 節(jié)點(diǎn)分布與定位結(jié)果圖

2.2 通信距離與信標(biāo)節(jié)點(diǎn)占比對(duì)定位誤差的影響

本文通過(guò)改變信標(biāo)節(jié)點(diǎn)占比和最大通信半徑的方法來(lái)測(cè)算誤差大小并尋找誤差規(guī)律。 由于無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布具有隨機(jī)性，為保證實(shí)驗(yàn)結(jié)果的代表性，每次實(shí)驗(yàn)結(jié)果均為1 000 次重復(fù)仿真結(jié)果的平均值。 圖2(a)是在保持信標(biāo)節(jié)點(diǎn)占比(60%)不變的情況下，改變通信半徑，得到的節(jié)點(diǎn)定位平均相對(duì)誤差；圖2(b)是保持最大通信半徑(40 m)不變，改變信標(biāo)節(jié)點(diǎn)占比，得到的節(jié)點(diǎn)定位平均相對(duì)誤差。

圖2 通信距離與信標(biāo)節(jié)點(diǎn)占比對(duì)定位誤差的影響

分析圖3 可知，在達(dá)到一定的信標(biāo)節(jié)點(diǎn)占比和通信半徑后，經(jīng)典DV-Hop 算法可以進(jìn)行較為精確的定位。 在信標(biāo)節(jié)點(diǎn)占比不變的情況下，最大通信半徑越大，定位的相對(duì)誤差越小，最低接近20%；同樣的，在最大通信半徑不變的情況下，信標(biāo)節(jié)點(diǎn)占比越大，相對(duì)定位誤差越小，最低接近34%。

2.3 跳數(shù)對(duì)定位誤差的影響

圖3 為未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間測(cè)算距離與實(shí)際距離的誤差值仿真結(jié)果。 實(shí)驗(yàn)中將信標(biāo)節(jié)點(diǎn)占比設(shè)為40%，通信距離設(shè)為30 m，并重復(fù)1 000 次求得平均值。 由圖可得，相隔跳數(shù)較少的節(jié)點(diǎn)距離估算誤差較小。

圖3 相隔跳數(shù)對(duì)測(cè)距誤差的影響

2.4 誤差成因總結(jié)

結(jié)合仿真結(jié)果與理論分析，可以得出傳統(tǒng)DVHop 定位算法的主要誤差來(lái)源:

①最小跳數(shù)計(jì)算

在經(jīng)典DV-Hop 算法中，如果兩個(gè)節(jié)點(diǎn)互在對(duì)方的最大通信范圍內(nèi)，就將這兩個(gè)節(jié)點(diǎn)間跳數(shù)記為1跳。 但是由于通信距離是一個(gè)較大的區(qū)間，節(jié)點(diǎn)間的實(shí)際距離卻可以有相當(dāng)大的差別。 如圖4 所示。

圖4 節(jié)點(diǎn)A 周邊節(jié)點(diǎn)示意圖

對(duì)于節(jié)點(diǎn)A 來(lái)說(shuō)，最外圈的圓表示最大通信半徑，而其他三個(gè)節(jié)點(diǎn)B、C、D 都處于這一半徑之內(nèi)，在跳數(shù)統(tǒng)計(jì)上這三點(diǎn)與節(jié)點(diǎn)A 的跳數(shù)都是1 跳，但是這三者與A 的距離卻有著不同差別，代入計(jì)算后會(huì)造成誤差。

②平均跳距計(jì)算

經(jīng)典DV-Hop 算法中，未知節(jié)點(diǎn)選擇與自己跳數(shù)最少的信標(biāo)節(jié)點(diǎn)的平均跳距作為自身的平均跳距。 而在實(shí)際網(wǎng)絡(luò)中，不同節(jié)點(diǎn)在不同區(qū)域內(nèi)的分布并不是完全均勻的，節(jié)點(diǎn)分布密集的區(qū)域平均跳距較小，反之則平均跳距較大，若以單一跳距作為所有節(jié)點(diǎn)的計(jì)算要素，就不能正確反映整體網(wǎng)絡(luò)分布狀況。

③計(jì)算方法

由于DV-Hop 算法中最后的距離估算采用的是直接相乘方法，這在相關(guān)節(jié)點(diǎn)共線的情況下誤差較小。 但是實(shí)際情況中節(jié)點(diǎn)的布設(shè)較為隨機(jī)，不同節(jié)點(diǎn)間的網(wǎng)絡(luò)拓?fù)鋱D并不是直線，直接相乘會(huì)造成較大誤差。

3 三維DV-Hop 定位算法的改進(jìn)與精度驗(yàn)證

3.1 算法改進(jìn)

針對(duì)上述對(duì)DV-Hop 算法誤差的分析，本文提出了以下幾點(diǎn)優(yōu)化方案:

①細(xì)化跳數(shù)

針對(duì)跳數(shù)計(jì)算的問(wèn)題，本文提出細(xì)化跳數(shù)的方法。 由于1 跳的代表范圍較大，可將一跳細(xì)分為更小的區(qū)間。 對(duì)節(jié)點(diǎn)來(lái)說(shuō)，設(shè)其周?chē)赤従庸?jié)點(diǎn)與其的距離為d，最大通信半徑為R，跳數(shù)hop 則為:

細(xì)分跳數(shù)后，跳數(shù)和距離之間的比值更接近正比關(guān)系。 進(jìn)而在之后的運(yùn)算中更加精確地計(jì)算節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)間的距離。 顯然，m的取值越大，跳數(shù)細(xì)分程度越高，計(jì)算結(jié)果就會(huì)更加精確。 但是，實(shí)際使用中，更細(xì)分的跳數(shù)會(huì)帶來(lái)兩個(gè)問(wèn)題:第一，更細(xì)分的跳數(shù)意味著節(jié)點(diǎn)需要更多次地按照不同通信半徑洪泛廣播信號(hào)，導(dǎo)致無(wú)線傳感器節(jié)點(diǎn)耗能過(guò)多，這與無(wú)線傳感器需要長(zhǎng)期存活的要求相違背；第二，實(shí)際應(yīng)用中，較高的細(xì)分系數(shù)需要無(wú)線傳感器對(duì)信號(hào)強(qiáng)度有極高的靈敏度，在實(shí)地試驗(yàn)中由于電磁環(huán)境復(fù)雜，多種無(wú)線信號(hào)混雜干擾，無(wú)線傳感器難以分辨更細(xì)的跳數(shù)，因此可能會(huì)產(chǎn)生新的誤差。 綜合能耗、性能與實(shí)際情況，本文將采用m=2 的細(xì)分系數(shù)。

②信標(biāo)節(jié)點(diǎn)平均跳距計(jì)算修正

DV-Hop 算法中對(duì)于信標(biāo)節(jié)點(diǎn)平均跳距的計(jì)算都是基于無(wú)偏估計(jì)準(zhǔn)則。 即通過(guò)令式(11)為0 來(lái)計(jì)算平均跳距Hopsizei:

式中:N為信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)。 但在實(shí)驗(yàn)中，根據(jù)誤差分布的高斯特性，使用均方誤差比只使用方差要更為合理。 因此本文將式(12)進(jìn)行等值變換得

根據(jù)無(wú)偏估計(jì)計(jì)算法則，對(duì)式(12)進(jìn)行一階求導(dǎo)，并令其為0，可得符合最小均方誤差的平均跳距:

③未知節(jié)點(diǎn)平均跳距選擇

傳統(tǒng)DV-Hop 算法中未知節(jié)點(diǎn)直接采用離自己最為接近的信標(biāo)節(jié)點(diǎn)的平均跳距作為自身的跳距。根據(jù)圖3 仿真結(jié)果可以發(fā)現(xiàn)，信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)的跳數(shù)越大，測(cè)算出來(lái)的距離誤差就越大；直接取用離自身最近的信標(biāo)節(jié)點(diǎn)的數(shù)據(jù)確實(shí)可以避免更遠(yuǎn)節(jié)點(diǎn)對(duì)應(yīng)跳數(shù)所造成的誤差影響，但卻無(wú)法完全代表節(jié)點(diǎn)周?chē)乃芯W(wǎng)絡(luò)分布狀況。 因此，可將離與未知節(jié)點(diǎn)一定跳數(shù)t內(nèi)的信標(biāo)節(jié)點(diǎn)的平均跳距納入未知節(jié)點(diǎn)平均跳距計(jì)算之中，以權(quán)重的形式加入計(jì)算。由于距離越遠(yuǎn)節(jié)點(diǎn)的距離誤差越大，綜合考慮后設(shè)定信標(biāo)節(jié)點(diǎn)i的權(quán)系數(shù)wi為:

式中:跳數(shù)限制t，根據(jù)仿真實(shí)驗(yàn)結(jié)果，與環(huán)境大小l與通信半徑R有關(guān)，即

最終求得未知節(jié)點(diǎn)的加權(quán)平均跳距為:

3.2 仿真精度驗(yàn)證

3.2.1 實(shí)驗(yàn)環(huán)境設(shè)置

實(shí)驗(yàn)采用MATLAB R2020a 軟件進(jìn)行仿真，詳細(xì)數(shù)據(jù)如表2 所示。

表2 仿真參數(shù)設(shè)置

3.2.2 仿真結(jié)果分析

①信標(biāo)節(jié)點(diǎn)比例對(duì)定位精度的影響

圖5(a)表示了在固定通信半徑為40 m 的情況下，優(yōu)化算法與經(jīng)典DV-Hop 算法之間的精度差距。由結(jié)果可得，在固定通信距離的情況下，信標(biāo)節(jié)點(diǎn)占比較小時(shí)，經(jīng)典算法和優(yōu)化算法精度比較接近，這是因?yàn)樾艠?biāo)節(jié)點(diǎn)數(shù)量過(guò)少，大部分的未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的跳數(shù)都較大，測(cè)算的距離誤差較大，進(jìn)而導(dǎo)致最終定位的誤差率較高；但是當(dāng)信標(biāo)節(jié)點(diǎn)數(shù)量增多后，優(yōu)化效果逐漸得到體現(xiàn)，定位誤差大幅下降，并且下降趨勢(shì)逐漸趨緩。 比起傳統(tǒng)定位算法，優(yōu)化后的定位算法定位精度平均提高25%左右。

圖5 經(jīng)典算法與優(yōu)化算法精度比較

②節(jié)點(diǎn)通信半徑對(duì)定位精度的影響

圖5(b)表示了在固定信標(biāo)節(jié)點(diǎn)比例為60%的情況下，優(yōu)化算法與經(jīng)典DV-Hop 算法之間的精度差距。 由結(jié)果可知，在通信距離較近的情況下，很多節(jié)點(diǎn)無(wú)法與信標(biāo)節(jié)點(diǎn)直接通信，或者相距跳數(shù)較大，這種情況下經(jīng)典DV-Hop 算法和改進(jìn)后的算法的定位精度都受到較大影響。 相對(duì)于經(jīng)典算法，優(yōu)化后的DV-Hop 算法精度得到大幅提高。 在最大通信半徑較小的情況下，優(yōu)化后的算法與經(jīng)典算法差距不大；但在最大通信半徑超過(guò)一定值后，優(yōu)化算法精度顯著提高，并隨著通信距離的增大逐漸穩(wěn)定，這是由于在較大的通信距離下細(xì)化的跳數(shù)所能帶來(lái)的優(yōu)化效應(yīng)慢慢降低，并趨向于穩(wěn)定。 相較于傳統(tǒng)DV-Hop算法，改進(jìn)算法將定位精度平均提高約30%。

4 結(jié)束語(yǔ)

本文通過(guò)仿真和理論分析的方法研究傳統(tǒng)DVHop 算法的誤差，并基于傳統(tǒng)DV-Hop 算法的缺陷，提出了一種改進(jìn)后的DV-Hop 算法。 通過(guò)多通信半徑的方式來(lái)細(xì)分節(jié)點(diǎn)跳數(shù)，以達(dá)到提高節(jié)點(diǎn)間距離估計(jì)的精確度；通過(guò)調(diào)整平均跳距計(jì)算公式的方式改進(jìn)了信標(biāo)節(jié)點(diǎn)的平均跳距計(jì)算；利用傳統(tǒng)DVHop 算法得出的規(guī)律以權(quán)重的形式改進(jìn)了未知節(jié)點(diǎn)平均跳距的選取。 仿真結(jié)果說(shuō)明，本文提出的改進(jìn)算法相對(duì)于傳統(tǒng)算法，在相同WSN 網(wǎng)絡(luò)中，具有更高的定位精度。