無線傳感器網(wǎng)絡(luò)的改進DV-hop定位算法研究

周 凱，周培釗，付文涵，魏勝非

(東北師范大學(xué)物理學(xué)院，吉林 長春 130024)

0 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)是被人為隨機部署在需要檢測區(qū)域的大量節(jié)點通過自組織(ad-hoc)而組成的網(wǎng)絡(luò).隨著經(jīng)濟的發(fā)展和科技的創(chuàng)新，無線傳感器網(wǎng)絡(luò)得到了較大的發(fā)展，其在家居生活、軍事戰(zhàn)場、工業(yè)制造等領(lǐng)域的應(yīng)用變得越來越廣泛，其中節(jié)點定位算法作為無線傳感器網(wǎng)絡(luò)的一個重要應(yīng)用，受到了國內(nèi)外學(xué)者的廣泛關(guān)注.

無線傳感器網(wǎng)絡(luò)定位指的是針對網(wǎng)絡(luò)中未知節(jié)點位置的確定，主要是采用已知錨節(jié)點的位置來估計未知節(jié)點和剩余節(jié)點的距離以及跳數(shù)[1].目前，節(jié)點定位技術(shù)日益成熟，根據(jù)是否借助距離信息將其分為兩種[2]，分別為需要測距的定位算法和非測距的定位算法.需要測距的定位算法主要是借助外部硬件設(shè)備得到節(jié)點與節(jié)點之間的距離信息，常見的測距定位算法有到達時間(Time of Arrival，TOA)、到達時間差(Time Difference of Arrival，TDOA)、到達角度(Angle of Arrival，AOA)、接收信號指示強度(Received Signal Strength Indication，RSSI)等；非測距的定位算法主要是通過已知位置的錨節(jié)點確定未知節(jié)點的位置，常見的非測距定位算法有近似三角形測試算法(Approximate PIT Test，APIT)、距離向量跳躍算法(Distance Vector Hop，DV-hop)等.

測距定位算法測得的距離雖然比較準確，但是需要額外的外部設(shè)備，對于電池體積較小的傳感器節(jié)點來說負擔較重，這無疑會減少傳感器節(jié)點的工作時間，降低無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)壽命；非測距的定位算法雖然定位精度不如非測距算法，但是不需要外部設(shè)備的支持[3]，無形之中降低了成本，減少了能量的消耗.

DV-hop算法作為非測距算法中的典型代表成為國內(nèi)外研究的熱點，該算法受環(huán)境的影響較小，不需要額外的硬件設(shè)備支持，所以適應(yīng)于成本低、規(guī)模大、節(jié)點配置簡單的無線傳感器網(wǎng)絡(luò)[4].針對DV-hop算法的定位缺陷，國內(nèi)外很多學(xué)者對該算法進行了改進，文獻[5]在進行未知節(jié)點定位時，使錨節(jié)點先后采用兩個通信半徑廣播自身信息，從而獲得未知節(jié)點與錨節(jié)點更準確的跳數(shù)，得到未知節(jié)點更精確的坐標；文獻[6]主要對傳統(tǒng)DV-hop算法中的跳數(shù)和跳距進行改進，首先將錨節(jié)點的通信半徑拆分為4個通信半徑，分別進行以相應(yīng)的通信半徑進行廣播，獲得較精確的跳數(shù)，同時與未知節(jié)點臨近的錨節(jié)點的跳距都會根據(jù)到待定位節(jié)點的跳數(shù)而產(chǎn)生一個權(quán)值，從而產(chǎn)生新的跳距，參與到后續(xù)的計算過程中；文獻[7]主要針對DV-hop算法平均跳距誤差較大的問題，將參與未知節(jié)點定位的錨節(jié)點的平均跳距按跳數(shù)進行分配加權(quán)系數(shù)，使得后續(xù)的計算過程誤差更小；文獻[8]首先利用節(jié)點的通信半徑與影響節(jié)點跳數(shù)的相關(guān)參數(shù)對全局跳數(shù)值進行協(xié)同優(yōu)化，以使節(jié)點間的跳數(shù)趨于合理，然后根據(jù)最佳指數(shù)的最小均方誤差準則計算平均跳距，并與單跳平均誤差共同修正平均跳距，從而進一步降低平均跳距的誤差；文獻[9]首先基于信標節(jié)點估計距離與真實距離的差值，提出了一種全網(wǎng)絡(luò)的有效跳距，其次在信標節(jié)點與未知節(jié)點間多跳計算過程中增添了修正值，最后利用列文伯格-馬夸爾特算法估計未知節(jié)點的最優(yōu)位置，有效地提高了算法的定位精度.

本文主要研究DV-hop節(jié)點定位算法，通過分析傳統(tǒng)DV-hop算法的誤差，糾正節(jié)點之間的跳數(shù)以及修正未知節(jié)點與錨節(jié)點之間的跳距，使得跳數(shù)與跳距更加趨于合理化，最后利用改進的最小二乘法進行計算，進一步提升了未知節(jié)點的定位精度.

1 傳統(tǒng)DV-hop定位算法與誤差分析

1.1 傳統(tǒng)DV-hop算法定位算法原理

DV-hop算法中主要將節(jié)點分為錨節(jié)點與未知節(jié)點，錨節(jié)點在整個網(wǎng)絡(luò)中占有一定的比例，因為錨節(jié)點本身帶有GPS定位系統(tǒng)，而未知節(jié)點本身不具有定位系統(tǒng)，所以該算法主要利用待定位節(jié)點與錨節(jié)點的跳數(shù)與跳距來計算兩者之間的距離，該算法主要分為3個步驟，分別為確定最小跳數(shù)、計算未知節(jié)點到錨節(jié)點之間的距離、確定未知節(jié)點的坐標.

1.1.1 確定未知節(jié)點與錨節(jié)點之間的最小跳數(shù)

已知自身位置的錨節(jié)點通過洪泛協(xié)議以其通信半徑向外廣播帶有自身位置和跳數(shù)初始化的數(shù)據(jù)包，當鄰居節(jié)點接收到錨節(jié)點的數(shù)據(jù)包之后，更新數(shù)據(jù)包中的跳數(shù)信息，也就是跳數(shù)加一，然后繼續(xù)將數(shù)據(jù)包轉(zhuǎn)發(fā)，同時未知節(jié)點會忽略來自同一錨節(jié)點的較大的跳數(shù)數(shù)據(jù)包，保存到錨節(jié)點最小跳數(shù)的數(shù)據(jù)包，通過此種轉(zhuǎn)發(fā)方式，每個節(jié)點都得到了到網(wǎng)絡(luò)中每個錨節(jié)點的最小跳數(shù)與最短路徑[10].

1.1.2 計算未知節(jié)點到錨節(jié)點之間的距離

圖1 DV-hop算法中節(jié)點分布示意圖

傳統(tǒng)DV-hop算法在計算距離時，主要采用距離待定位節(jié)點最近的錨節(jié)點的平均跳距作為計算到每個錨節(jié)點的平均跳距，如圖1所示，離待定位節(jié)點B最近的錨節(jié)點為L2，L2的平均跳距計算過程為

(1)

此時B節(jié)點將(1)式計算出來的跳距作為自身的跳距，分別計算到3個錨節(jié)點的距離：

(2)

1.1.3 確定未知節(jié)點的坐標

利用三邊測距法或者是最大似然估計法來計算未知節(jié)點的坐標.三邊測量法是節(jié)點定位中計算未知節(jié)點坐標常用的方法[11]，假設(shè)未知節(jié)點的坐標是(x，y)，已知3個錨節(jié)點的坐標分別為(x1，y1)，(x2，y2)，(x3，y3)，具體的計算過程為

(3)

將上面3個式子展開之后，用第3個式子分別與上述3個式子相減，可以將(3)式轉(zhuǎn)化為如(4)式矩陣相乘的形式，將3個式子中的距離記為d1，d2，d3未知節(jié)點的坐標，通過對矩陣運算獲得

AX=B；

(4)

(5)

(6)

(7)

然后通過計算該坐標矩陣即可獲得未知節(jié)點的坐標.

在實際的無線傳感器網(wǎng)絡(luò)中，錨節(jié)點與未知節(jié)點是隨機分布的，可能參與到未知節(jié)點坐標計算的錨節(jié)點個數(shù)為n(n≥3)個，此時采用最大似然估計法來計算未知節(jié)點的坐標誤差更小，最大似然估計法的計算過程與上述過程相同，區(qū)別是參與到未知節(jié)點定位的錨節(jié)點的個數(shù)不同導(dǎo)致的方程個數(shù)不同，其次在最后使用最小二乘法來計算未知節(jié)點的坐標為

X=(ATA)-1ATB.

(8)

1.2 傳統(tǒng)DV-hop算法誤差分析

DV-hop算法用平均跳距乘以到錨節(jié)點最小跳數(shù)的乘積來近似表示未知節(jié)點到錨節(jié)點的距離[12]，所以在后續(xù)計算過程中計算出來的坐標值也是不準確的.首先在該算法中，跳數(shù)不合理是一個重要原因，假設(shè)錨節(jié)點通信半徑為50 m，在廣播階段，與之相距直線距離為5和40 m的節(jié)點都在其通信半徑范圍內(nèi)，所以將兩者的跳數(shù)都記為1跳，這是不合理的，在后續(xù)的計算過程中會進一步加大誤差；同時，未知節(jié)點在計算與相鄰錨節(jié)點的距離時，通常采用離未知節(jié)點最近的錨節(jié)點的跳距，沒有考慮到全局網(wǎng)絡(luò)以及錨節(jié)點的分布情況，這樣就會忽略其他錨節(jié)點的跳距，在計算距離時會增大定位的不確定性；最后，在計算節(jié)點位置時，通常采用最小二乘法，普通的最小二乘法認為每項誤差對總體回歸直線的偏離程度全部相同，等價于權(quán)值都賦為1，各方程可信度相同.然而由于模型中誤差項存在異方差性，每項誤差對總體回歸直線的偏離程度不同，此時普通最小二乘法無法確定各錨節(jié)點參與定位的可信度，得到的估計值不滿足最優(yōu)估計[13].

2 傳統(tǒng)DV-hop定位算法改進

2.1 節(jié)點之間跳數(shù)的改進

圖2 錨節(jié)點廣播示意圖

錨節(jié)點A以通信半徑R進行洪泛見圖2，由圖2可知，未知節(jié)點C和未知節(jié)點B都在錨節(jié)點A的通信半徑內(nèi)，所以兩者皆可以接收到來自A的信息，此時C點和B點接收到含有位置信息和跳數(shù)信息的初始化數(shù)據(jù)包之后，此時分別將跳數(shù)加1，但是，B點和C點到A點的直線距離不同，所以兩者的跳數(shù)應(yīng)該不同.

具體步驟是通過設(shè)置錨節(jié)點的能量消耗模型，針對不同的發(fā)射距離D，選擇不同的發(fā)射功率，定義如下的能量消耗模型，其中發(fā)送和接收m的數(shù)據(jù)需要消耗的能量公式為

(9)

通過上述過程，使得錨節(jié)點與相鄰節(jié)點之間的跳數(shù)值更加接近真實跳數(shù)，將改進的跳數(shù)值加入到跳距運算的過程中，會進一步減少跳數(shù)不精確帶來的定位誤差.

2.2 跳距的改進

針對傳統(tǒng)DV-hop定位算法在選擇跳距時考慮片面的問題，本文首先采用改進的跳數(shù)來計算跳距，然后得到參與未知節(jié)點定位的錨節(jié)點的跳距.

如圖1所示，L1，L2，L33個錨節(jié)點分別通過改進的跳數(shù)來計算跳距，假設(shè)3個錨節(jié)點得到的跳距改進值分別為Di，Dj，Dk，此時定義3個錨節(jié)點的平均每跳距離誤差為

(10)

其中：w1為平均每跳誤差因子；hopij，hopik，hopjk為兩兩錨節(jié)點之間的跳數(shù).3個錨節(jié)點新的跳距為

(11)

假設(shè)參與未知節(jié)點定位的錨節(jié)點的個數(shù)為n個，定義平均每跳誤差因子為

(12)

節(jié)點i和節(jié)點j是n個錨節(jié)點中任意的兩個錨節(jié)點，且i和j是n個錨節(jié)點之中任意的兩個錨節(jié)點，n個錨節(jié)點的新跳距為

(13)

考慮到錨節(jié)點距離未知節(jié)點的遠近以及誤差水平，距離遠的錨節(jié)點所帶來的誤差不一定大，而距離未知節(jié)點較近的錨節(jié)點所帶來的誤差不一定小，所以未知節(jié)點在選擇跳距時，應(yīng)充分考慮誤差以及距離所帶來的影響，首先考慮距離帶來的影響，定義錨節(jié)點i的權(quán)重系數(shù)為

(14)

式中：hopui表示待定位節(jié)點與錨節(jié)點i的跳數(shù)；hopuj表示待定位節(jié)點與錨節(jié)點j的跳數(shù)；n表示參與到未知節(jié)點定位的所有錨節(jié)點.

考慮誤差所帶來的影響，理想的情況應(yīng)該是誤差大的錨節(jié)點在未知節(jié)點的定位過程中參與度低，而誤差小的錨節(jié)點參與度高[15]，定義誤差因子為：

(15)

(16)

(17)

定義誤差參與度因子

(18)

(18)式說明，誤差較大的錨節(jié)點在未知節(jié)點位置定位的過程中參與度越低，將誤差參與度因子歸一化處理[16]，綜合誤差參與度因子以及跳數(shù)權(quán)重，分別將兩者的影響因子設(shè)置為0.5，則新的跳距為

(19)

2.3 未知節(jié)點的定位

雖然對未知節(jié)點與錨節(jié)點之間跳數(shù)和跳距進行修正，但是未知節(jié)點與待定位錨節(jié)點之間的距離較真實值仍然會存在誤差，所以在使用最小二乘法迭代求解時，仍然會產(chǎn)生迭代誤差，在改進的最小二乘法中，引入加權(quán)系數(shù)矩陣，采用不同的加權(quán)系數(shù)矩陣進行定位[17].已知參與未知節(jié)點定位的錨節(jié)點的坐標為(x1，y1)，(x2，y2)，(x3，y3)，…，(xn，yn)，未知節(jié)點的坐標為(x，y).根據(jù)改進的跳數(shù)和改進跳距計算得到未知節(jié)點到每個錨節(jié)點的距離分別為d1，d2，d3，…，dn，可得

(20)

(21)

3 仿真結(jié)果與分析

仿真采用MATLAB2016a將節(jié)點隨機分布在100 m×100 m的正方形區(qū)域內(nèi)，觀察錨節(jié)點的比例、節(jié)點的總數(shù)量、節(jié)點的通信半徑對于平均節(jié)點定位誤差的影響.圖3是節(jié)點隨機分布示意圖，圖3中設(shè)置100個節(jié)點，20個錨節(jié)點，星號代表錨節(jié)點，圓點代表未知節(jié)點.

本文選用相對定位誤差作為衡量節(jié)點定位的效果，公式為

(22)

式中：N代表節(jié)點的總數(shù)，B代表錨節(jié)點的數(shù)量，R代表節(jié)點的通信半徑，(x，y)是節(jié)點位置的真實值，(xi，yi)是節(jié)點位置的估計值.

圖4是DV-hop算法中每個節(jié)點的定位誤差，由圖4可以看到節(jié)點的誤差分布不均勻，這和節(jié)點的分布位置有關(guān)，節(jié)點分布均勻，誤差的總體水平會下降，節(jié)點分布不均勻，誤差的總體水平較高.

圖3 節(jié)點隨機分布示意圖

圖4 每個節(jié)點絕對誤差分布示意圖

為了對改進的算法進行評估，在相同的網(wǎng)絡(luò)環(huán)境下，每改變一次變量對實驗?zāi)M10次，取平均值作為最后的結(jié)果，將通信半徑、錨節(jié)點的比例以及節(jié)點的數(shù)量作為3個變量對本文改進的算法、DDV-hop算法以及原算法進行仿真，比較三者之間的定位精度.

(1) 節(jié)點總數(shù)相同，錨節(jié)點的比例相同，通信半徑不同.

圖5 算法隨通信半徑改變的誤差比較

圖5是各個算法隨節(jié)點的通信半徑的改變定位誤差而改變的效果仿真圖，節(jié)點的總數(shù)相同，錨節(jié)點的比例相同，通信半徑分別從30 m取到60 m.從圖5中可以看出，隨著通信半徑的增加，算法的誤差逐漸減小.從仿真結(jié)果來看，本文改進算法相對于傳統(tǒng)的DV-hop算法和DDV-hop算法更優(yōu)，定位精度更高，誤差更小.

(2) 節(jié)點總數(shù)相同，通信半徑相同，錨節(jié)點的比例不同.

錨節(jié)點的比例是影響算法穩(wěn)定度的一個重要原因(見圖6)，隨著錨節(jié)點比例的增加，本文改進算法的定位精度變化不是很明顯，波動范圍較小，傳統(tǒng)的DV-hop算法的波動范圍較大.同DDV-hop算法相比，本文改進算法的定位精度更高，定位精度提高了15%左右；相對于傳統(tǒng)的DV-hop算法來說，定位精度提高了25%左右.

圖6 算法隨錨節(jié)點比例改變的誤差比較

圖7 算法隨節(jié)點總數(shù)改變的誤差比較

(3)通信半徑相同，錨節(jié)點的比例相同，節(jié)點的總數(shù)不同.

節(jié)點總數(shù)的增加，會導(dǎo)致節(jié)點的定位精度的變化(見圖7).從圖7可以看出，隨著節(jié)點總數(shù)的增加，定位精度相對不會升高，而是相對保持一個平穩(wěn)的狀態(tài)，特別是相對于本文改進算法來說，因為隨著節(jié)點數(shù)的增加，需要錨節(jié)點參加定位的頻率就越大，同時受到參與度因子的影響，節(jié)點的定位精度相對穩(wěn)定，不會有太大的起伏變化.

4 結(jié)束語

首先對傳統(tǒng)的DV-hop算法的原理以及工作過程進行了介紹，分析了引起DV-hop算法誤差的主要原因，利用多通信半徑的方法進行改進跳數(shù)，利用跳數(shù)加權(quán)以及錨節(jié)點的參與度作為考量錨節(jié)點參與未知節(jié)點定位的主要因素，進行改進跳距，同時在計算未知節(jié)點位置的過程中加入誤差的協(xié)方差矩陣和加權(quán)系數(shù)矩陣來改進傳統(tǒng)的最小二乘法，最后通過仿真實驗將改進的DV-hop算法以及DDV-hop算法、傳統(tǒng)的DV-hop算法進行比較，相對于后兩者，改進算法的定位誤差進一步減小，定位精度進一步提高.