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

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

0 引言

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

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

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

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

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

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

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

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

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

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

1.1.2 計(jì)算未知節(jié)點(diǎn)到錨節(jié)點(diǎn)之間的距離

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

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

(1)

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

(2)

1.1.3 確定未知節(jié)點(diǎn)的坐標(biāo)

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

(3)

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

AX=B；

(4)

(5)

(6)

(7)

然后通過計(jì)算該坐標(biāo)矩陣即可獲得未知節(jié)點(diǎn)的坐標(biāo).

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

X=(ATA)-1ATB.

(8)

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

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

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

2.1 節(jié)點(diǎn)之間跳數(shù)的改進(jìn)

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

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

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

(9)

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

2.2 跳距的改進(jìn)

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

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

(10)

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

(11)

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

(12)

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

(13)

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

(14)

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

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

(15)

(16)

(17)

定義誤差參與度因子

(18)

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

(19)

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

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

(20)

(21)

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

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

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

(22)

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

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

圖3 節(jié)點(diǎn)隨機(jī)分布示意圖

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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