基于區(qū)域劃分和余弦定理的DV-Hop算法改進

費辰陽，邵樹金，邢竹萍，潘幼岳，張愛清

(安徽師范大學(xué) 物理與電子信息學(xué)院，安徽 蕪湖 241000)

0 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSN)是一種分布式傳感網(wǎng)絡(luò)，網(wǎng)絡(luò)中的傳感器通過無線方式通信，網(wǎng)絡(luò)配置靈活。基于這些特點，無線傳感器網(wǎng)絡(luò)對人類生活和社會進步起到很大的作用。由于無線傳感器網(wǎng)絡(luò)需要對環(huán)境進行監(jiān)測、探測和采集數(shù)據(jù)等，這些都需要包含定位信息，因此，定位技術(shù)是無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一。

無線傳感器網(wǎng)絡(luò)定位算法分成兩個大類：無需測距(Range-Free)定位算法和基于測距(Range-Based)的定位算法。無需測距定位技術(shù)不需要直接測量距離和角度信息，而是通過對節(jié)點間的距離進行估計或者確定包含未知節(jié)點的可能區(qū)域來確定未知節(jié)點的位置。無需測距定位算法主要有質(zhì)心定位算法(Centroid)、距離向量-跳段定位算法(Vector-Hop,DV-Hop)、近似三角形質(zhì)心定位算法(Approximate Point-in-Triangulation Test,APTI)等。質(zhì)心定位算法位置估計精確度和信標(biāo)節(jié)點的密度、分布有很大關(guān)系，DV-Hop定位算法利用多跳信標(biāo)節(jié)點信息來參與節(jié)點定位，APTI定位算法通過計算包含目標(biāo)節(jié)點所有三角形的重疊區(qū)域，并求解質(zhì)心來進行定位。這些算法或多或少都存在一些缺陷和問題，導(dǎo)致定位的精度不高。其中DV-Hop算法因?qū)?jié)點的硬件要求低、實現(xiàn)簡單等優(yōu)點被廣泛應(yīng)用，但由于其定位精度受節(jié)點分布的影響，在有些場景中定位誤差比較大。

針對 DV-HOP 在節(jié)點隨機分布的網(wǎng)絡(luò)環(huán)境下存在較大誤差的問題，已取得了一些研究成果。文獻[1-4]均提出通過RSSI測距優(yōu)化節(jié)點間的跳數(shù)來減小定位誤差。其中，文獻[1]算法提出：首先利用節(jié)點間RSSI值與基準(zhǔn)RSSI值的比值量化節(jié)點間跳數(shù)，使整數(shù)跳數(shù)轉(zhuǎn)化為連續(xù)跳數(shù)，并在量化跳數(shù)的基礎(chǔ)上對信標(biāo)節(jié)點平均跳距進行重估，然后對各信標(biāo)節(jié)點平均跳距進行加權(quán)處理以修正未知節(jié)點平均跳距，最后利用未知節(jié)點與最近信標(biāo)節(jié)點的距離關(guān)系對未知節(jié)點坐標(biāo)的估計誤差進行修正。文獻[2]在RSSI測距優(yōu)化節(jié)點間的跳數(shù)的基礎(chǔ)上，使用校正因子修正DV-Hop算法中的平均跳距，并采用無約束優(yōu)化算法代替?zhèn)鹘y(tǒng)的最小二乘法來計算未知節(jié)點坐標(biāo)。文獻[3]研究的RADV-Hop算法引入RSSI進行跳數(shù)分級來修正節(jié)點間跳數(shù)，并基于最小均方準(zhǔn)則修正跳距。文獻[4]利用RSSI測距技術(shù),定義信標(biāo)節(jié)點的平均跳距誤差,并利用信標(biāo)節(jié)點的平均跳距誤差對未知節(jié)點與信標(biāo)節(jié)點之間的距離進行修正。文獻[5-6]均提出通過余弦定理來調(diào)整估計跳距；文獻[7-8]的核心思想是優(yōu)化信標(biāo)節(jié)點的部署，為一定范圍內(nèi)的未知節(jié)點合理分配最優(yōu)信標(biāo)節(jié)點，進一步提高定位進度；文獻[9-10]提出采用基于加權(quán)重值的最小二乘法來計算未知節(jié)點的坐標(biāo)。結(jié)合以上算法的優(yōu)點，本文提出基于區(qū)域劃分和余弦定理的DV-Hop改進算法(Region Division and Cosine Theorem improving DV-Hop,RDCTDV-Hop)，提高定位精度。

1 DV-Hop算法誤差與分析

1.1 DV-Hop定位技術(shù)

DV-Hop算法實現(xiàn)步驟為：

① 計算未知節(jié)點與每個信標(biāo)節(jié)點的最小跳數(shù)：使用經(jīng)典距離矢量交換協(xié)議，每個節(jié)點維護一個表(x,y,h)，其中x，y，h分別代表信標(biāo)節(jié)點坐標(biāo)和到該信標(biāo)節(jié)點的跳數(shù)。每個信標(biāo)節(jié)點發(fā)送一個包含自身位置信息和跳段個數(shù)的廣播分組，跳段個數(shù)初始化為0。節(jié)點收到信標(biāo)節(jié)點的廣播分組后，檢驗分組跳段數(shù)是否小于節(jié)點表內(nèi)的存儲值，是則更新該表，然后跳段數(shù)加1并廣播該分組，否則丟棄該分組。最終所有的未知節(jié)點均能獲得距離每個信標(biāo)節(jié)點的最小跳數(shù)。

② 計算未知節(jié)點與信標(biāo)節(jié)點的距離：每個信標(biāo)節(jié)點根據(jù)自身表中記錄的其他信標(biāo)節(jié)點的坐標(biāo)信息和跳數(shù)，按照式(1)計算出平均跳段距離并將其利用可泛洪法進行廣播，每個節(jié)點均只接收第一個跳段距離，忽略后來到達(dá)的，確保絕大多數(shù)節(jié)點可以從最近的信標(biāo)節(jié)點接收平均跳段距離。最后未知節(jié)點可計算自身到達(dá)相應(yīng)信標(biāo)節(jié)點的距離。

平均跳距計算公式為：

式中，(xi,yi)，(xj,yj)為節(jié)點i,j的位置坐標(biāo);hopij為節(jié)點i和j間的跳數(shù)距離。

未知節(jié)點到信標(biāo)節(jié)點計算公式為：

dij=Average×hopij。

當(dāng)節(jié)點分布如圖1所示時,各段距離具體計算如下：

圖1 節(jié)點分布1Fig.1 Node distribution 1

③ 未知節(jié)點通過三邊定位或多邊定位算法計算自身的坐標(biāo)。

1.2 誤差分析

第一階段，由于傳感器節(jié)點都是隨機分布，分組在被廣播的過程中可能存在沖突素，節(jié)點得到信標(biāo)節(jié)點的最小跳數(shù)存在一定偏差，且跳數(shù)越多，偏差越大。

第二階段，估算平均跳段距離時，利用的是除本節(jié)點外所有其他信標(biāo)節(jié)點，所以得到的是全部范圍內(nèi)的平均跳距離，不能反映局部范圍內(nèi)的網(wǎng)絡(luò)密度分布情況。此外，如圖2所示，信標(biāo)節(jié)點間客觀存在空間方位，節(jié)點間因為存在角度而產(chǎn)生誤差。在實際測量中這種情況很容易出現(xiàn)，尤其是在節(jié)點密度較大時這種情況發(fā)生的可能性也會更大。

圖2 節(jié)點分布2Fig.2 Node distribution 2

第三階段，分布密度的不均勻?qū)е滦艠?biāo)節(jié)點距離方差較大，尤其是在信標(biāo)節(jié)點密度較小時，信標(biāo)節(jié)點間距離的方差會更大，出現(xiàn)的誤差也會越大。另外，每個節(jié)點間的距離都不固定，跳數(shù)是非連續(xù)跳段，當(dāng)按照平均跳段距離和跳數(shù)估計距離時，存在較大誤差。

2 RSSI分級跳數(shù)

2.1 誤差分析

在經(jīng)典DV-Hop算法中，未知節(jié)點只保留最先接收到的平均跳段距離，這個平均跳段距離往往來自于距其最近的信標(biāo)節(jié)點。這將導(dǎo)致單跳距離產(chǎn)生的誤差較大，如圖3所示，會導(dǎo)致實際距離與估測距離之間的偏差較大，從而影響未知節(jié)點的定位精度。

圖3 單跳誤差示意圖Fig.3 Schematic diagram of single hop error

對于相距未知節(jié)點較近的信標(biāo)節(jié)點，由于它們之間的跳數(shù)較少，每跳產(chǎn)生的誤差能夠相互抵消的可能性較更小，當(dāng)誤差相互疊加后會使得估計距離與實際距離之間的偏差更大。

對于相距未知節(jié)點較遠(yuǎn)的信標(biāo)節(jié)點，他們之間的跳數(shù)足夠多，誤差在累加的過程中能夠相互抵消的可能性較大。但由于未知節(jié)點與信標(biāo)節(jié)點相距較遠(yuǎn)，而未知節(jié)點所獲取的平均跳段距離是由其臨近節(jié)點提供的，所以如果仍然用這個平均跳段距離去計算，顯然會存在較大誤差。

2.2 RSSI跳數(shù)分級原理

參考文獻[1-2]中指出，為了減小由跳數(shù)引起的誤差，可采用RSSI測距對跳數(shù)進行分級改進的思路。在減小每跳實際距離與平均跳段距離誤差的同時也可以增加跳數(shù)，使每跳誤差在累加過程中能夠相互抵消的可能性增大，令估測距離更加接近實際距離。

RSSI測距技術(shù)的原理是：根據(jù)發(fā)送端到傳輸端之間的信息傳輸功率損耗，在一些特定損耗模型的基礎(chǔ)上，接收端由損耗功率估算出信息傳輸距離。其中較為常用的信號傳輸模型是對數(shù)-常態(tài)分布模型，根據(jù)文獻[1]具體可分為兩種：Pass Loss模型和遮擋因子模型。

Pass Loss模型：

(1)

式中，P(d0)和P(d)分別表示與發(fā)送端相距d0和d處接收端收到的信號功率，η為路徑損耗因子，通常取值在2～4，由此可以通過接收功率的大小與參考距離的接收功率進行比較進而估算出距離。

遮擋因子模型：

(2)

式中，相距發(fā)送端d0和d的接收功率用分貝表示即[P(d0)]dB和[P(d)]dB。Xσ為遮擋因子，是平均值為0的高斯分布變量，其描述了接收信號強度隨距離的變化關(guān)系，即表示信號功率本身隨距離的變化與環(huán)境因素?zé)o關(guān)，也可以用信號的發(fā)射功率[Pt]dB表示，同時還可以將式(3)看做信號傳輸過程中的路徑損耗，用[PL]dB表示，則式(2)可以表示為式(4)：

(3)

[P(d)]dB=[Pt]dB-[PL]dB。

(4)

假設(shè)將一跳劃分為g級，根據(jù)文獻[3]取節(jié)點的通信半徑做為參考距離d0，可由式(2)通過接收信號的功率確定分級后的跳數(shù)。其判斷規(guī)則如下：

若某節(jié)點接收到的功率[P(d)]dB滿足式(5)，則該節(jié)點到發(fā)生信號節(jié)點間的跳數(shù)為i/g。

(5)

節(jié)點i到j(luò)間的總跳數(shù)hij可以表示為：

(6)

式中，n表示節(jié)點i到j(luò)的節(jié)點總數(shù)。

3 基于節(jié)點密度的算法改進

3.1 誤差分析

在一定的區(qū)域范圍內(nèi)，節(jié)點密度越高該區(qū)域的節(jié)點分布相應(yīng)會更均勻。而在DV-Hop算法中，節(jié)點分布越均勻，其誤差越低，定位精確度越高；節(jié)點分布越不均勻，其誤差也就越高，定位精確度越低。

當(dāng)節(jié)點密度較高時，由于其物理屬性產(chǎn)生的誤差將會升高而無法忽略，從而增加其整體定位誤差，降低定位精確度。

以下算法對上述兩條誤差來源進行矯正。

3.2 余弦定理矯正平均跳距

圖4 傳感器網(wǎng)絡(luò)節(jié)點結(jié)構(gòu)Fig.4 Node structure of sensor network

3.2.1 中間節(jié)點的選擇

根據(jù)連接到每個信標(biāo)節(jié)點的最小跳數(shù)的傳輸路線，將路線中間的節(jié)點作為中間節(jié)點，設(shè)Jp_Num為節(jié)點間的跳數(shù)。

當(dāng)Jp_Num為奇數(shù)，選擇路線的中間節(jié)點，如圖5(a)所示；當(dāng)Jp_Num為偶數(shù)，選擇路線中間的兩跳都作為中間節(jié)點，其中α、β為中間節(jié)點與兩端信標(biāo)節(jié)點之間連線所形成的夾角，如圖5(b)所示。

(a) 信標(biāo)節(jié)點B1與B3之間跳數(shù)為奇數(shù)

設(shè)dHopB2為利用余弦定理所求出的平均跳距。結(jié)合圖5(a)可證明，當(dāng)Jp_Num為奇數(shù)時，計算公式為式(7)；由圖5(b)可證明，當(dāng)Jp_Num為偶數(shù)時，計算公式為式(8)。

(7)

(8)

3.2.2 夾角范圍的證明

角度與傳輸路徑示意如圖6所示，節(jié)點A、B之間有兩條路線，分別是A-C-B和A-D-B，由幾何關(guān)系可知A-C-B比A-D-B路線更短，更加接近AB的值，而α>β，且α更接近180°。由三角形三邊關(guān)系可知，當(dāng)α越接近180°時，A-C-B的距離越接近AB，所要繞行的路線更短，而使用傳統(tǒng)DV-Hop測距得到的平均跳距誤差也就越小。

圖6 角度與傳輸路徑示意圖Fig.6 Schematic diagram of angle and transmission path

3.2.3 余弦定理求校正值

(9)

可使用校正值對傳統(tǒng)法計算的平均跳距進行校正，減少誤差。

3.2.4 適用條件

由概率知識可知，在一定區(qū)域內(nèi)，由于節(jié)點間的坐標(biāo)各不相同，當(dāng)該區(qū)域內(nèi)節(jié)點數(shù)量越多時，傳感器的排列情況越少，分布越均勻，若不考慮節(jié)點間的空間夾角，則隨著節(jié)點數(shù)量的增加，傳統(tǒng)算法所得到的平均跳距越準(zhǔn)確，誤差越小。

本文提出的改進策略可以減少節(jié)點非直線分布造成的誤差，且該算法的誤差隨節(jié)點密度增加而減少。

3.3 區(qū)域劃分

3.3.1 劃分算法

根據(jù)參考文獻[7-8]中的移動信標(biāo)算法，本文設(shè)計出區(qū)域合并的算法。根據(jù)節(jié)點密度越大，誤差越小的結(jié)論，DCMDV-Hop算法采用先區(qū)域劃分再對未知節(jié)點進行計算處理的方法，對傳統(tǒng)的DV-Hop算法進行改進，使其節(jié)點密度較小區(qū)域的誤差得以降低，從而降低其整體誤差。

具體方案如下：將整個無線傳感器網(wǎng)絡(luò)所占地區(qū)的面積平均分成幾等份(如圖7所示)，先進行預(yù)劃分，然后計算出各個面積中所包含的節(jié)點總個數(shù)。節(jié)點個數(shù)最多的兩個區(qū)域合并(圖7(b)中的a和b兩個區(qū)域)，并計算出其中的未知節(jié)點坐標(biāo)。將已知區(qū)域同剩余區(qū)域中節(jié)點個數(shù)最多的區(qū)域(圖7(b)中的區(qū)域c)合并，再計算未知節(jié)點坐標(biāo)。剩余的未知區(qū)域用以此類推的方法進行計算，如圖8所示，直到計算出所有的未知節(jié)點坐標(biāo)(合并的區(qū)域不一定相鄰)。

(a) 劃分前的區(qū)域示意圖

圖8 區(qū)域合并Fig.8 Region merging

3.3.2預(yù)劃分

在具體實施算法之前，需要對區(qū)域進行預(yù)劃分來判斷點是否在區(qū)域內(nèi)。如圖8所示，具體步驟如下：

① 使用均分面積形狀的原則，預(yù)先設(shè)定劃分規(guī)則，得到子區(qū)域；

② 基于無線傳感器通信半徑一定的原理，通過預(yù)發(fā)送代理數(shù)據(jù)包得到可能在所劃分區(qū)域中的未知節(jié)點；

③ 根據(jù)參考文獻[8]，可使用RSSI測距技術(shù)，排除在步驟②中所得到未知節(jié)點中不屬于此區(qū)域的未知節(jié)點，得到此區(qū)域中的未知節(jié)點；

④ 在每個區(qū)域中重復(fù)步驟②～③過程，得到所有區(qū)域中的未知節(jié)點。

4 未知節(jié)點的坐標(biāo)估算

設(shè)未知節(jié)點Ui到信標(biāo)節(jié)點Bk的距離可用式(10)表示，hik為兩個節(jié)點間的最小跳數(shù)：

dik=Hopsizek×hik。

(10)

假設(shè)n個信標(biāo)節(jié)點的坐標(biāo)分別為(x1,y1),(x2,y2),…,(xn,yn)，未知節(jié)點到各個信標(biāo)節(jié)點的距離為d1,d2,…,dn。若未知節(jié)點Ui的坐標(biāo)為(x,y)，則可由兩點間距離公式求得n個方程組合的一組矩陣：

根據(jù)參考文獻[9-10],未知節(jié)點的坐標(biāo)可用最小二乘法來計算：

X=(ATA)-1ATb。

5 DCMDV-Hop算法實現(xiàn)步驟

DCMDV-Hop算法針對 DV-Hop 算法定位精度比較低的缺點，引入 RSSI 對跳數(shù)進行量化分級處理，使用余弦定理減少在節(jié)點密度過大時因空間角度導(dǎo)致節(jié)點路徑曲折過多而引起的誤差，同時引入?yún)^(qū)域劃分思想減少在節(jié)點密度較小區(qū)域的誤差。DCMDV-Hop算法實現(xiàn)步驟如下：

① 網(wǎng)絡(luò)初始化。啟動無線傳感器網(wǎng)絡(luò)，生成坐標(biāo)矩陣。

② 使用RSSI分級計算跳數(shù)。根據(jù)能量衰減規(guī)律，測得節(jié)點間的大致距離，使用分級量化方式測算跳數(shù)，降低跳數(shù)誤差。

③ 預(yù)劃分區(qū)域。使用預(yù)劃分算法，設(shè)置規(guī)則對當(dāng)前需要定位的未知節(jié)點進行區(qū)域劃分，為后續(xù)定位做準(zhǔn)備。

④ 區(qū)域劃分算法。使用劃分算法，依次對預(yù)劃分后所得子區(qū)域中的未知節(jié)點進行定位。

⑤ 平均跳距計算。使用傳統(tǒng)DV-Hop算法得出各個子區(qū)域中未知節(jié)點的平均跳距，為了降低因無線傳感器的物理屬性對平均跳距所造成的誤差，運用余弦定理矯正算法，使用式(9)對各個區(qū)域中所求得平均跳距進行矯正。

⑥ 最小二乘法估算未知節(jié)點坐標(biāo)。

⑦ 將計算出的未知節(jié)點作為信標(biāo)節(jié)點應(yīng)用于下一子區(qū)域中，計算出其未知節(jié)點的坐標(biāo)。

本文算法流程如圖9所示，與傳統(tǒng) DV-Hop 算法相比，該算法在確保節(jié)點間估計距離誤差較小的同時，不增加網(wǎng)絡(luò)的通信量，提高了節(jié)點的定位精度。

圖9 DCMDV-Hop算法流程Fig.9 DCMDV-Hop algorithm flow chart

6 實驗仿真

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

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

表1 仿真參數(shù)說明

模擬無線傳感器網(wǎng)絡(luò)場景為二維平面區(qū)域，節(jié)點分布如圖10所示。其中紅色“*”為信標(biāo)節(jié)點，黑色“·”為未知節(jié)點。在面積為100 m×100 m的正方形區(qū)域內(nèi)隨機分布200個節(jié)點?？紤]到節(jié)點的不確定性，本實驗采取多次仿真取平均值。

圖10 模擬場景節(jié)點分布Fig.10 Distribution of nodes in simulated scene

6.2 仿真實驗分析

使用Matlab對DCMDV-Hop算法進行仿真以尋找其定位誤差規(guī)律。

① 本文使用了4區(qū)域劃分與6區(qū)域劃分在通信半徑50 m與40 m的實驗環(huán)境下，對節(jié)點定位誤差與節(jié)點個數(shù)之間的關(guān)系進行了研究，仿真結(jié)果如圖11所示。

(a) 通信半徑R = 50 m時

當(dāng)信標(biāo)節(jié)點個數(shù)上升時，由于信標(biāo)節(jié)點密度上升使得信標(biāo)分布更加均勻，進而減少平均跳距誤差，但當(dāng)信標(biāo)節(jié)點個數(shù)較多時，節(jié)點實際存在的相對位置對平均跳距所產(chǎn)生的誤差將不能被忽略，導(dǎo)致誤差會再次開始增加。

② 信標(biāo)節(jié)點密度對使用DCMDV-Hop算法所劃分出的各子區(qū)域未知節(jié)點定位精度的影響對比分析如下。

本實驗將整個區(qū)域分成6個部分，各自的節(jié)點相對平均定位誤差如圖12所示。

圖12 6個子區(qū)域誤差比較Fig.12 Comparison of errors of six sub-area

由圖12可知，起始計算的區(qū)域由于信標(biāo)節(jié)點密度逐漸上升,使得節(jié)點分布更加均勻，誤差逐漸降低，但每計算一個區(qū)域得到未知節(jié)點坐標(biāo)應(yīng)用于下一區(qū)域的計算時,都會累計一定的誤差，此誤差使得計算得出的未知節(jié)點與信標(biāo)節(jié)點的距離同其坐標(biāo)不匹配，導(dǎo)致后面的區(qū)域誤差逐漸上升。

從仿真結(jié)果可以看出，DCMDV-Hop與傳統(tǒng)的DV-Hop相比，定位誤差有明顯減少，但由于各區(qū)域信標(biāo)節(jié)點數(shù)量的不確定性，以及前面區(qū)域的坐標(biāo)誤差會對后續(xù)區(qū)域坐標(biāo)計算有所影響，導(dǎo)致其整體定位穩(wěn)定性有所下降。

7 結(jié)束語

針對DV-Hop在節(jié)點定位中所存在的不足之處，本文從三方面進行改進：① 使用對信標(biāo)節(jié)點按照一定原則劃分，增加其每一部分的均勻度以減小跳距跳數(shù)的誤差；② 在節(jié)點密度較大的子區(qū)域中，由于節(jié)點密度過大會使節(jié)點間空間角度路徑曲折過多，令這些誤差較大而無法被忽略，可以使用余弦定理算法降低這一誤差；③ 使用多通信半徑減少傳統(tǒng)DV-Hop，不考慮節(jié)點間距離實際情況使用單一跳數(shù)劃分原則下，所造成的誤差。由以上仿真結(jié)果可知，對比傳統(tǒng)DV-Hop，本文提出的DCMDV-Hop算法定位精度有較大提升，且在規(guī)模較大的節(jié)點網(wǎng)絡(luò)中擁有更大的提升。但本文的改進算法依然存在不足之處：在仿真運行時，該算法運行效率明顯低于傳統(tǒng)DV-Hop，通信開銷較大。進一步研究算法以降低其通信開銷，提升運行效率是以后研究工作的重點。