無線傳感器網絡的改進DV-hop定位算法研究

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

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

0 引言

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

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

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

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

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

1 傳統DV-hop定位算法與誤差分析

1.1 傳統DV-hop算法定位算法原理

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

1.1.1 確定未知節點與錨節點之間的最小跳數

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

1.1.2 計算未知節點到錨節點之間的距離

圖1 DV-hop算法中節點分布示意圖

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

(1)

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

(2)

1.1.3 確定未知節點的坐標

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

(3)

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

AX=B；

(4)

(5)

(6)

(7)

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

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

X=(ATA)-1ATB.

(8)

1.2 傳統DV-hop算法誤差分析

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

2 傳統DV-hop定位算法改進

2.1 節點之間跳數的改進

圖2 錨節點廣播示意圖

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

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

(9)

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

2.2 跳距的改進

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

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

(10)

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

(11)

假設參與未知節點定位的錨節點的個數為n個，定義平均每跳誤差因子為

(12)

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

(13)

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

(14)

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

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

(15)

(16)

(17)

定義誤差參與度因子

(18)

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

(19)

2.3 未知節點的定位

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

(20)

(21)

3 仿真結果與分析

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

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

(22)

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

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

圖3 節點隨機分布示意圖

圖4 每個節點絕對誤差分布示意圖

為了對改進的算法進行評估，在相同的網絡環境下，每改變一次變量對實驗模擬10次，取平均值作為最后的結果，將通信半徑、錨節點的比例以及節點的數量作為3個變量對本文改進的算法、DDV-hop算法以及原算法進行仿真，比較三者之間的定位精度.

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

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

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

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

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

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

圖7 算法隨節點總數改變的誤差比較

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

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

4 結束語

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