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

費(fèi)辰陽(yáng)，邵樹(shù)金，邢竹萍，潘幼岳，張愛(ài)清

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

0 引言

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

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

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

1 DV-Hop算法誤差與分析

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

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

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

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

平均跳距計(jì)算公式為：

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

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

dij=Average×hopij。

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

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

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

1.2 誤差分析

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

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

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

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

2 RSSI分級(jí)跳數(shù)

2.1 誤差分析

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

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

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

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

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

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

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

Pass Loss模型：

(1)

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

遮擋因子模型：

(2)

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

(3)

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

(4)

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

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

(5)

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

(6)

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

3 基于節(jié)點(diǎn)密度的算法改進(jìn)

3.1 誤差分析

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

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

以下算法對(duì)上述兩條誤差來(lái)源進(jìn)行矯正。

3.2 余弦定理矯正平均跳距

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

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

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

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

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

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

(7)

(8)

3.2.2 夾角范圍的證明

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

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

3.2.3 余弦定理求校正值

(9)

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

3.2.4 適用條件

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

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

3.3 區(qū)域劃分

3.3.1 劃分算法

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

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

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

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

3.3.2預(yù)劃分

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

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

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

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

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

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

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

dik=Hopsizek×hik。

(10)

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

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

X=(ATA)-1ATb。

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

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

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

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

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

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

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

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

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

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

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

6 實(shí)驗(yàn)仿真

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

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

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

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

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

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

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

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

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

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

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

本實(shí)驗(yàn)將整個(gè)區(qū)域分成6個(gè)部分，各自的節(jié)點(diǎn)相對(duì)平均定位誤差如圖12所示。

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

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

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

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

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